命題論理での恒真式

4.恒真命題

含意を含む恒真式

複合命題「\(A\rightarrow B\)」が恒真の時\(A\Rightarrow B\)とする

同値を含む恒真式

複合命題「\(A\leftrightarrow B\)」が恒真の時\(A\Leftrightarrow B\)とする

\(P,Q\) の真理値に関わらず\((P \rightarrow Q \leftrightarrow \lnot P∨Q)=T\)
よって\(P \rightarrow Q \iff \lnot P∨Q\)である。

\(P\)\(Q\)\(\lnot P\)\(P\rightarrow Q\)\(\lnot P ∨Q\)\(P \rightarrow Q \leftrightarrow \lnot P∨Q\)
\(T\)\(T\)\(F\)\(T\)\(T\)\(T\)
\(T\)\(F\)\(F\)\(F\)\(F\)\(T\)
\(F\)\(T\)\(T\)\(T\)\(T\)\(T\)
\(F\)\(F\)\(T\)\(T\)\(T\)\(T\)

5. 主な性質

基本法則1

\( \lnot T \Leftrightarrow F \\ \lnot F \Leftrightarrow T\)

基本法則2

\( P \land T \Leftrightarrow P\)    \(P \land F \Leftrightarrow F\)
\( P \lor T \Leftrightarrow T\)    \(P \lor F \Leftrightarrow P\)

二重否定の法則

\( \lnot \lnot P \Leftrightarrow P\)

交換法則

\(P\land Q \Leftrightarrow Q \land P\)
\(P\lor Q \Leftrightarrow Q \lor P\)

結合法則

\((P\land Q) \land R \Leftrightarrow P\land ( Q \land R)\)
\((P\lor Q) \lor R\Leftrightarrow P\lor ( Q \lor R)\)

分配法則

\(P\land (Q \lor R) \Leftrightarrow (P\land Q) \lor(Q \land R)\)
\(P\lor (Q \land R) \Leftrightarrow (P\lor Q)\land ( Q \lor R)\)

吸収法則

\(P\land (P \lor Q) \Leftrightarrow P\)
\(P\lor (P \land Q) \Leftrightarrow P\)

これらも真理値表を書いて簡単に示せる

6. 排中律、矛盾律、巾等律

排中律

\(P∨(\lnot P) \Leftrightarrow T\)

矛盾律

\(P \land (\lnot P) \Leftrightarrow F\)

巾等律

\(P \land P \Leftrightarrow P \\P \lor P \Leftrightarrow P\)

7.対偶

対偶

\(P \rightarrow Q   \Leftrightarrow (\lnot Q) \rightarrow (\lnot P)\)

\(P\)\(Q\)\(\lnot P\)\(\lnot Q\)\(P\rightarrow Q\)\((\lnot Q) \rightarrow (\lnot P)\)\(P\rightarrow Q \leftrightarrow (\lnot Q) \rightarrow (\lnot P)\)
\(T\)\(T\)\(F\)\(F\)\(T\)\(T\)\(T\)
\(T\)\(F\)\(F\)\(T\)\(F\)\(F\)\(T\)
\(F\)\(T\)\(T\)\(F\)\(T\)\(T\)\(T\)
\(F\)\(F\)\(T\)\(T\)\(T\)\(T\)\(T\)

8.ドモルガンの法則

ドモルガンの法則

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

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

上記からドモルガンの法則が示せる。また\(\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\)となる。