命題の同値性

4.命題の同値性

命題の同値性

命題(関数)\(P\)と\(Q\)が同値であるとは値によらず常に真偽を共にすることであり、\(P\equiv Q\)と表す

コメント

命題「\(P\iff Q\)」がトートロジーであると言うことである。
ある命題の真偽を判定するのが困難な場合、同値な命題の真偽を代わりに調べることができる条件である

\(P\)\(Q\)\(P\Rightarrow Q\)\(\lnot P\)\(\lnot P ∨Q\)

上記の表から\(P \Rightarrow Q \equiv \lnot P∨Q\)である。

5.対偶法

対偶法

\(P \Rightarrow Q \equiv (\lnot Q) ∨ (\lnot P)\)

\(P\)\(Q\)\(P\Rightarrow Q\)\(\lnot P\)\(\lnot Q\)\((\lnot Q) \Rightarrow (\lnot P)\)
コメント

対偶法は上記のように真偽が一致することを利用している

6.ドモルガンの法則

ドモルガンの法則

    \( \lnot (P∧Q) \Leftrightarrow   (\lnot {P})∨(\lnot {Q})\)     \( \lnot (P∨Q) \Leftrightarrow   (\lnot{P})∧(\lnot{Q})\)

\(P\)\(Q\)\(P∧ Q\)\(\lnot {P∧ Q}\)\(\lnot P\)\(\lnot Q\)\(\lnot {P}∨\lnot {Q}\)
\(P\)\(Q\)\(P∨ Q\)\(\lnot {P∨ Q}\)\(\lnot P\)\(\lnot Q\)\(\lnot {P}∧ \lnot {Q}\)
ドモルガンの法則の一般化

上記からドモルガンの法則が示せる。また\(\lnot (P_1∧ P_2∧ ...∧P_n)\)のようにn個の場合でも\((P_2∧ ...P_n)\)を一つの命題と考えると\(\lnot P_1 ∨\lnot(P_2∧ ...P_n)\)となり、同じように\(n-1\)回繰り返すことで\(\lnot P_1 ∨\lnot P_2∨ ...∨\lnot P_n\)となる。

論理演算の順序

\(\lnot, (∧,∨),(\Rightarrow,\iff)\)の順番で作用させる。