このブログの更新は Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama

メールでのご連絡は hiyama{at}chimaira{dot}org まで。

はじめてのメールはスパムと判定されることがあります。最初は、信頼されているドメインから差し障りのない文面を送っていただけると、スパムと判定されにくいと思います。

参照用 記事

含意記号に対する誤解 -- それは間違いだ

年に2,3回、誰かに向かって同じ話をしている気がするので、ブログ記事にしておきます。$`
\newcommand{\Imp}{\Rightarrow }
\newcommand{\Iff}{\Leftrightarrow }
\newcommand{\mrm}[1]{\mathrm{#1}}
\require{color}
\newcommand{\Keyword}[1]{ \textcolor{green}{\text{#1}} }%
\newcommand{\For}{\Keyword{For } }%
\newcommand{\Define}{\Keyword{Define } }%
`$

論理記号のなかで、$`\land`$(論理AND、連言)、$`\lor`$(論理OR、選言)、$`\lnot`$(論理NOT、否定)を誤解する人はあまりいない*1のですが、$`\Imp`$(含意)、$`\Iff`$(同値、双条件〈biconditional〉)については誤解している、あるいはモヤッと捉えている人がけっこういるようです。

集合 $`X`$ を固定して、$`X`$ から二値真偽値の集合 $`\{\mrm{true},\mrm{false}\}`$ への写像〈関数〉の全体を $`\mrm{Map}(X, \{\mrm{true},\mrm{false}\})`$ と書きしょう。$`\mrm{Map}(X, \{\mrm{true},\mrm{false}\})`$ の要素は、$`X`$ 上の述語〈predicate〉と呼びます。また、集合 $`X`$ のすべての部分集合の集合(ベキ集合〈powerset〉)は $`\mrm{Pow}(X)`$ と書きます。

$`X`$ 上の述語と、$`X`$ の部分集合は次のように1:1対応します。

$`\quad (p:X \to \{\mrm{true},\mrm{false}\}) \longleftrightarrow \{x\in X\mid p(x)\}`$

この対応を前提としたときに、以下の対応表は間違っています。ダメです。

述語に関して 部分集合に関して 部分集合の一言説明
$`\land`$ $`\cap`$ 共通部分
$`\lor`$ $`\cup`$ 合併
$`\lnot`$ $`{^\mrm{c}}`$ 補集合
$`\Imp`$ $`\subseteq`$ 包含関係
$`\Iff`$ $`=`$ 等しい

ダメな対応表を修正すると:

述語に関して 部分集合に関して
$`\land`$ $`\cap`$
$`\lor`$ $`\cup`$
$`\lnot`$ $`{^\mrm{c}}`$
$`\Imp`$
$`\Iff`$
$`\subseteq`$
$`=`$

疑問符のところは、広く合意された記号がないことを表します。僕が普段使っている記号でいいなら:

述語に関して 部分集合に関して
$`\land`$ $`\cap`$
$`\lor`$ $`\cup`$
$`\lnot`$ $`{^\mrm{c}}`$
$`\Imp`$ $`\triangleright`$
$`\Iff`$ $`\diamond`$
$`\vdash`$ $`\subseteq`$
$`\equiv`$ $`=`$

$`\triangleright,\,\diamond`$ は個人的に使用しているだけなので、全然一般性はありませんが、定義は次のようです。

$`\For A, B \in \mrm{Pow}(X)\\
\Define A \triangleright B := A^\mrm{c} \cup B\\
\Define A \diamond B := (A \triangleright B)\cap ( B \triangleright A)
`$

$`\vdash`$ は比較的よく使われている記号で、$`\vdash`$ の左側の命題(述語だと思ってよい)を仮定すれば右側の命題が導出されることを示します*2

集合 $`X`$ 上で常に真である恒真述語を $`\top = \top_X`$ とすると、次が言えます。

  • $`\top \longleftrightarrow X`$ と対応する。
  • $`\top \vdash (p \Imp q)`$ は、$`p \vdash q`$ と同じこと。
  • $`\top \vdash (p \Iff q)`$ は、$`p \equiv q`$ と同じこと。

ともかく、最初に挙げたダメな対応表を想定していた人には、「それは間違いだ」と言っておきます。

*1:論理ORを排他的OR(どちらか一方だけ)と誤解する人は一定数いますが。

*2:ここでの「導出」は意味論的な概念です。記号 $`\vdash`$ を実行可能な手順による証明可能性と解釈すると、記事本文とは意味が違ってきます。