命題代数の法則
論理同値な命題のわかりやすい (使いやすい) パターンのこと 命題代数の法則を使うと,わざわざ命題の真理値表を作らなくても,¬,∧,∨という記号に関する機械的な操作だけで,命題を別の形の論理同値な命題に変形することができます.つまり,命題全体を,演算¬,∧,∨に関する代数系として扱うことができます. へーcFQ2f7LRuLYP.icon
関連してない
「代数系として扱うことができる」とどんないいことがあるんだろうか
頑張って真理値表で導き出そうとしていたけど、これは「そういうものだ」としてスルーしていいのか?
ルールとして与えられている状態なのか、ルールの中から導き出されているのか
p.18では法則が色々書かれている
同じ操作をしても等しくなる
$ 1\times1=1になるような性質
冪でも等しくなるってことか
$ p\lor p \iff p
$ p\land p \iff p
演算の結合方法を変えることのできる法則
$ (p\lor q)\lor r \iff p\lor(q\lor r)
真理値表で確かめる
table:(p\lor q)\lor r
p q r p∨q (p∨q)∨r
T T T T T
T F T T T
F T T T T
F F T F T
T T F T T
T F F T T
F T F T T
F F F F F
table:p\lor (q\lor r)
p q r q∨r p∨(q∨r)
T T T T T
T F T T T
F T T T T
F F T T T
T T F T T
T F F F T
F T F T T
F F F F F
真理値表が同じになったので
$ (p\lor q)\lor r \iff p\lor(q\lor r)
$ (p\land q)\land r \iff p\land(q\land r)
こちらも確かめてみよう
table:(p\land q)\land r
p q r p∧q (p∧q)∧r
T T T T T
T F T F F
F T T F F
F F T F F
T T F T F
T F F F F
F T F F F
F F F F F
table:p\land (q\land r)
p q r q∧r p∧(q∧r)
T T T T T
T F T F F
F T T T F
F F T F F
T T F F F
T F F F F
F T F F F
F F F F F
真理値表が同じになったので
$ (p\land q)\land r \iff p\land(q\land r)
(余談)真理値表上手くできていない気がする
table:例
B∧C A A∧(B∧C)
T T T
T F F
F T F
F F F
これなら全パターン網羅できてるできてなかった
A,BからA∧Bを導いたり、B,CからB∨Cを導いたりするプロセスは省略してもよいのだろうか
A,B,Cすべての組み合わせを網羅する必要があるtakker.icon
2*2*2=8通り
thxcFQ2f7LRuLYP.icon
2つの演算の引数を入れ替えても同じ値になる法則
$ p\lor q \iff q\lor p
$ p\land q \iff q\land p
一般に,集合Aにおける二つの演算*,〇と,Aの元a,b,cについてa*(b〇c)=(a*b)〇(a*c),(a〇b)*c=(a*c)〇(b*c)が成り立つとき,演算*は,演算〇に対して分配法則を満たすという。(世界大百科事典)
$ p\lor (q \land r) \iff (p\lor q)\land (p\lor r)
table:p∨(q∧r)⇔(p∨q)∧(p∨r)
p q r q∧r p∨(q∧r) p∨q p∨r (p∨q)∧(p∨r)
T T T T T T T T
T F T F T T T T
F T T T T T T T
F F T F F F T F
T T F F T T T T
T F F F T T T T
F T F F F T F F
F F F F F F F F
おー、一致した
$ p\land (q \lor r) \iff (p\land q)\lor (p\land r)
table:p∧(q∨r)⇔(p∧q)∨(p∧r)
p q r q∨r p∧(q∨r) p∧q p∧r (p∧q)∨(p∧r)
T T T T T T T T
T F T T T F T T
F T T T F F F F
F F T T F F F F
T T F T T T F T
T F F F F F F F
F T F T F F F F
F F F F F F F F
$ p\lor (q \lor r)のときは……?と思ったけどそれは結合律だった
ただし,p,q,rは命題変数で,tは恒真命題,fは矛盾命題を表すものとします.p.17
$ p\lor f\iff p
table:p∨f
p f p∨f
T F T
F F F
$ p\land t \ \iff p
table:p∧t
p t p∧t
T T T
F T F
$ p\lor t\ \iff t
table:p∨t
p t p∨t
T T T
F T T
$ p\land f \iff f
table:p∧f
p f p∧f
T F F
F F F
(前提を確認してなかった時のログ)
ここよくわからないな……cFQ2f7LRuLYP.icon
真理値表だとfの真偽によって変化してしまわない?
table:p∨f
p f p∨f
T T T
T F T
F T T
F F F
pがF、fがTのときは$ p\lor f\iff pにならない
$ tと$ fの定義を確認したほうがよさそうyosider.icon
なるほど!cFQ2f7LRuLYP.icon
前ページに書いてあったcFQ2f7LRuLYP.icon
ただし,p,q,rは命題変数で,tは恒真命題,fは矛盾命題を表すものとします.p.17
プリントミスだろうなあtakker.icon
誤→正
$ t→$ T
$ f→$ F
前提補われたから大丈夫かなとは思うけど念のため明記しておくとプリントミスではないnishio.icon
ブール束においては,2つの元 A と B の結び A∪B ,交わり A∩B ,そして最大元 I と最小元0の存在と,1つの元 A に対し,A∪A'=I,A∩A'=0 となる元 A' を考える。これを A の補元素,あるいは単に補元という。 ははは、全然わからん
恒真命題や矛盾命題が導き出されているように思うけんども
A∪A'=I,A∩A'=0 となる元 A'をベン図で描いてみるといいかもyosider.icon その「補」は「補集合」と同じニュアンスの「補」nishio.icon
$ p∨\lnot p \iff t
$ p∧\lnot p\iff f
$ \lnot t\iff f
table:¬t ⇔f
t ¬t f
T F F
T F F
$ \lnot f\iff t
table:¬f ⇔t
f ¬f T
F T T
F T T
間違えてたので修正cFQ2f7LRuLYP.icon
否定の否定はもとに戻る
ような律?
$ \lnot\lnot p\iff p
table:¬¬p⇔p
p ¬p ¬(¬p)
T F T
F T F
左から右($ \lnot\lnot p\implies p)が二重否定除去、右から左($ p\implies\lnot\lnot p)が二重否定導入と呼ばれますtakker.icon 二重否定除去が排中律のとこで紹介した脇道へつながる登山口ですが、今入ったら崖崩れを起こすので立ち入らないで下さい 対合律は初耳。そんな呼び方あるんだtakker.icon $ f^{-1}(f(x))=x
例:$ f:x\mapsto-x
$ f^{-1}:x\mapsto -xだから、$ f^{-1}(f(x))=-(-x)=xになる
とうとうここまで来た
$ \lnot(p\lor q)\iff \lnot p \land \lnot q
table:¬(p∨q)⇔¬p∧¬q
p q p∨q ¬(p∨q) ¬p ¬q ¬p∧¬q
T T T F F F F
T F T F F T F
F T T F T F F
F F F T T T T
$ \lnot(p\land q)\iff \lnot p \lor \lnot q
table:¬(p∧q)⇔¬p∨¬q
p q p∧q ¬(p∧q) ¬p ¬q ¬p∨¬q
T T T F F F F
T F F T F T T
F T F T T F T
F F F T T T T
本当に一致しとる……
手を動かして解くと納得感がある
ベン図を描くとさらに納得感が増しますtakker.icon もしかして、AND検索やOR検索などでも応用できるのか??cFQ2f7LRuLYP.icon