命題代数の法則
from 論理と集合から始める数学の基礎 読書会
論理同値な命題のわかりやすい (使いやすい) パターンのこと
>命題代数の法則を使うと，わざわざ命題の真理値表を作らなくても，¬，∧，∨という記号に関する機械的な操作だけで，命題を別の形の論理同値な命題に変形することができます.つまり，命題全体を，演算¬，∧，∨に関する代数系として扱うことができます．
へー
ド・モルガンの法則はこれに該当してるんかな
関連してない
「代数系として扱うことができる」とどんないいことがあるんだろうか
頑張って真理値表で導き出そうとしていたけど、これは「そういうものだ」としてスルーしていいのか？
ルールとして与えられている状態なのか、ルールの中から導き出されているのか
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)
真理値表で確かめる
(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 |
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)
こちらも確かめてみよう
(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 |
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)
(余談)真理値表上手くできていない気がする
例
| 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すべての組み合わせを網羅する必要がある
2*2*2=8通り
thx
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)
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)
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
p∨f
| p | f | p∨f |
| T | F | T |
| F | F | F |
p\land t \ \iff p
p∧t
| p | t | p∧t |
| T | T | T |
| F | T | F |
p\lor t\ \iff t
p∨t
| p | t | p∨t |
| T | T | T |
| F | T | T |
こっちは恒真命題に等しくなるんか
p\land f \iff f
p∧f
| p | f | p∧f |
| T | F | F |
| F | F | F |
矛盾命題の真理値と等しくなる
真理値表でそうなるのはわかったけれど、さて「同一律って結局なんなんですか？」って言われると答えに窮するな
(前提を確認してなかった時のログ)
ここよくわからないな……
真理値表だとfの真偽によって変化してしまわない？
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の定義を確認したほうがよさそう
なるほど！
前ページに書いてあった
>ただし，p，q，rは命題変数で，tは恒真命題，fは矛盾命題を表すものとします.p.17
一字一句読む、できてないな……
プリントミスだろうなあ
誤→正
t→T
f→F
前提補われたから大丈夫かなとは思うけど念のため明記しておくとプリントミスではない
元を補う律？？
> ブール束においては，2つの元 A と B の結び A∪B ，交わり A∩B ，そして最大元 I と最小元0の存在と，1つの元 A に対し，A∪A'＝I，A∩A'＝0 となる元 A' を考える。これを A の補元素，あるいは単に補元という。
ははは、全然わからん
恒真命題や矛盾命題が導き出されているように思うけんども
その「補」は「補集合」と同じニュアンスの「補」
p∨\lnot p \iff t
これは排中律！
p∧\lnot p\iff f
これは矛盾律。
\lnot t\iff f
¬t ⇔f
| t | ¬t | f |
| T | F | F |
| T | F | F |
\lnot f\iff t
¬f ⇔t
| f | ¬f | T |
| F | T | T |
| F | T | T |
間違えてたので修正
否定の否定はもとに戻る
ような律？
\lnot\lnot p\iff p
¬¬p⇔p
| p | ¬p | ¬(¬p) |
| T | F | T |
| F | T | F |
二重否定除去が排中律のとこで紹介した脇道へつながる登山口ですが、今入ったら崖崩れを起こすので立ち入らないで下さい
この話題ゲーデル、エッシャー、バッハでも出てたかも？
対合律は初耳。そんな呼び方あるんだ
二回作用させるともとに戻る性質のことを対合と呼ぶそうだhttps://ja.wikipedia.org/wiki/対合
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
¬(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
¬(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 |
本当に一致しとる……
手を動かして解くと納得感がある
ベン図を描くとさらに納得感が増します
もしかして、AND検索やOR検索などでも応用できるのか？？