述語の演算と真理集合
述語の演算と真理集合
述語でも、「かつ」「または」「ではない」という言葉と述語を組み合わせて新しい述語を作ることができる
命題計算と同じcFQ2f7LRuLYP.icon
$ 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を代入して初めて真理値が決定できるようになるんだなcFQ2f7LRuLYP.icon
さて，述語$ 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\}だよなーcFQ2f7LRuLYP.icon
でもこの直感はよくないので筋道立てて考える必要がある
問われているのは$ 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になるはず
集合に詳しい小人さんがミスを直してくれた、ありがとうcFQ2f7LRuLYP.icon
$ \{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)
なるほどなーcFQ2f7LRuLYP.icon
論理演算子$ \to,\ \leftrightarrowについても同様
真理集合がややこしいので書いとくか
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)
いや言ってそんなにすごくないか…