述語の演算と真理集合
from 論理と集合から始める数学の基礎 読書会
述語の演算と真理集合
述語でも、「かつ」「または」「ではない」という言葉と述語を組み合わせて新しい述語を作ることができる
命題計算と同じ
P(x)\land Q(x)：P(x)かつQ(x)
P(x)\lor Q(x)：P(x)またはQ(x)
\lnot P(x)：P(x)ではない
上3つはいずれもxについての述語である
もちろん、xの変域について考えておく必要がある
テキストでは3.3の節においては「集合Uを固定し, 変数xの変域は常にUとし, 自由変数Xについての述語のみを考え」るとのこと
xに何らかの値aを代入するとこれらが命題となる
P(a)\land Q(a)
P(a)\lor Q(a)
\lnot P(a)
aを代入して初めて真理値が決定できるようになるんだな
述語は変数を含んでいて、変数の値を定めれば真か偽かを判断できる文や式なので当たり前である
>さて，述語P(x)， Q(x) の真理集合がそれぞれA，Bのとき，述語P(x) \land Q(x)，P(x) \lor Q(x)，\lnot P(x) の真理集合は何でしょうか. (p.30)
前に使った述語で例をあげてみよう
変数xの変域を\Nとして、P(x),Q(x)を自由変数xの述語であるとする
P(x)が「x+1=2」、Q(x)が「x^2-3x+2=0」とする
このとき真理集合AはA=\{1\}、真理集合BはB=\{1,2\}
では
P(x) \land Q(x)
これは直感からすると\{1\}だよなー
でもこの直感はよくないので筋道立てて考える必要がある
忘れちゃならない「定義にかえれ」
問われているのはP(x) \land Q(x)の真理集合
使えそうな材料
1. P(x)とQ(x)の真理集合はそれぞれA,Bである
2. 前提条件より、真理集合AはA=\{1\}、真理集合BはB=\{1,2\}
xに1ではない他の値(a)が入るとP(a)は偽になるし、
Q(x)にも1, 2ではない他の値(a)が入るとQ(a)は偽になる
時間切れなのでおやすみ
真理集合を問われているので、つまりはP(a)\land Q(a)が真になるような集合は何かを答えればいいんだろう多分
そうなると、A\sout{\land}\cap Bになるはず
集合に詳しい小人さんがミスを直してくれた、ありがとう
\{1\}
ここでなんか「あれ？述語や論理値の話をしていたのになぜか集合の世界にいるぞ？」と少しくらっとしてる
P(x) \lor Q(x)
上と同様。P(a)\lor Q(a)が真となるような集合を表せば良い
なのでこれはA\cup Bだな
\lnot P(x)
\lnot P(a)が真となるような集合を表せばいいわけだから・・・
\lnot Aかなあ
いやちがった、補集合だった
A^cですね
>論理演算\land, \lor, \lnotを組み合わせた述語の構成は，真理集合を考えることによって，集合演算\cap,\cup,(\cdot)^cを組み合わせた集合の構成に翻訳することができます．(p.31)
なるほどなー
論理演算子\to,\ \leftrightarrowについても同様
cf.含意と同値の論理演算子
真理集合がややこしいので書いとくか
1. P(x)\to Q(x)は\lnot P(x)\lor Q(x)と等しい
2. P(x)\leftrightarrow Q(x)は(P(x)\land Q(x))\lor (\lnot P(x)\land \lnot Q(x))と等しい
ややこしい！
これらを真理集合バージョンに書き直すと
1. \{x|P(x)\to Q(x)\}=(\{x|P(x)\})^c \cup \{x|Q(x)\}
2. \{x|P(x)\leftrightarrow Q(x)\}=(\{x|P(x)\} \cap \{x|Q(x)\})\cup((\{x|P(x)\})^c \cap (\{x|Q(x)\})^c)
いや言ってそんなにすごくないか…
自分がやっている範囲の数学で、こんな集合が使われているとこ見たことない
応用例存在するのかな？