命題論理 ③

Prop & Proof

任意の真偽値割当 $v$ をとり、その論理式全体への拡張評価を $\hat v$ とする。
$P,Q$ の真偽の組 $(P,Q)$ は $(T,T),(T,F),(F,T),(F,F)$ の$4$通りである。
$\Rightarrow,\neg,\lor$ の定義より次の真理表を得る。
$$ \begin{array}{|c|c|c|c|c|} \hline P & Q & P\Rightarrow Q & \neg P & \neg P\lor Q \\ \hline T & T & T & F & T \\ T & F & F & F & F \\ F & T & T & T & T \\ F & F & T & T & T \\ \hline \end{array} $$
表より、全ての場合に $P\Rightarrow Q$ と $\neg P\lor Q$ の真偽は一致する。
従って任意の真偽値割当 $v$ とその拡張 $\hat v$ において $P\Rightarrow Q$ と $\neg P\lor Q$ は同じ真偽値をとるので、両者は同値である。
$$ \Box$$

任意の真偽値割当 $v$ をとり、その論理式全体への拡張評価を $\hat v$ とする。
$P,Q$ の真偽の組 $(P,Q)$ は $(T,T),(T,F),(F,T),(F,F)$ の$4$通りである。
$\land,\lor,\neg$ の定義より次の真理表を得る。
$$ \begin{array}{|c|c|c|c|c|c|c|} \hline P & Q & P\land Q & \neg(P\land Q) & \neg P & \neg Q & (\neg P)\lor(\neg Q) \\ \hline 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 \\ \hline \end{array} $$
表より、全ての場合に $\neg(P\land Q)$ と $(\neg P)\lor(\neg Q)$ の真偽は一致する。
任意の真偽値割当 $v$ とその拡張 $\hat v$ において両者は同じ真偽値をとるので、
$$ \neg(P\land Q)\equiv (\neg P)\lor(\neg Q) $$
が成り立つ。
$$ \Box$$

任意の真偽値割当 $v$ をとり、その論理式全体への拡張評価を $\hat v$ とする。
$P,Q$ の真偽の組 $(P,Q)$ は $(T,T),(T,F),(F,T),(F,F)$ の$4$通りである。
$\lor,\land,\neg$ の定義より次の真理表を得る。
$$ \begin{array}{|c|c|c|c|c|c|c|} \hline P & Q & P\lor Q & \neg(P\lor Q) & \neg P & \neg Q & (\neg P)\land(\neg Q) \\ \hline 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 \\ \hline \end{array} $$
表より、全ての場合に $\neg(P\lor Q)$ と $(\neg P)\land(\neg Q)$ の真偽は一致する。
従って任意の真偽値割当 $v$ とその拡張 $\hat v$ において両者は同じ真偽値をとるので、
$$ \neg(P\lor Q)\equiv (\neg P)\land(\neg Q) $$
が成り立つ。
$$ \Box$$

任意の真偽値割当 $v$ をとり、その論理式全体への拡張評価を $\hat v$ とする。
$P,Q$ の真偽の組 $(P,Q)$ は $(T,T),(T,F),(F,T),(F,F)$ の$4$通りである。
$\Rightarrow,\neg,\land$ の定義より次の真理表を得る。
$$ \begin{array}{|c|c|c|c|c|c|} \hline P & Q & P\Rightarrow Q & \neg(P\Rightarrow Q) & \neg Q & P\land \neg Q \\ \hline T & T & T & F & F & F \\ T & F & F & T & T & T \\ F & T & T & F & F & F \\ F & F & T & F & T & F \\ \hline \end{array} $$
表より、全ての場合に $\neg(P\Rightarrow Q)$ と $P\land \neg Q$ の真偽は一致する。
従って任意の真偽値割当 $v$ とその拡張 $\hat v$ において両者は同じ真偽値をとるので、
$$ \neg(P\Rightarrow Q)\equiv P\land \neg Q $$
が成り立つ。
$$ \Box$$

双条件の定義より、任意の命題 $R,S$ について
$$ R\Leftrightarrow S\ \Leftrightarrow\ (R\Rightarrow S)\land(S\Rightarrow R) $$
が成り立つ。したがって、$P\Leftrightarrow Q$ を示すには
$$ (P\Rightarrow Q)\land(Q\Rightarrow P) $$
を示せば十分である。
そこで
$$ \neg P\land\neg Q $$
を仮定する。このとき、連言の性質より
$$ \neg P $$
かつ
$$ \neg Q $$
が成り立つ。
まず、$\neg P$ が成り立っているから、含意の真理値の定義より
$$ P\Rightarrow Q $$
は真である(空虚に真)。
同様に、$\neg Q$ が成り立っているから、含意の真理値の定義より
$$ Q\Rightarrow P $$
は真である(空虚に真)。
したがって
$$ (P\Rightarrow Q)\land(Q\Rightarrow P) $$
が成り立つ。ゆえに、双条件の定義より
$$ P\Leftrightarrow Q $$
が成り立つ。以上より
$$ (\neg P\land\neg Q)\Rightarrow (P\Leftrightarrow Q) $$
が成り立つ。
$$ \Box$$

任意の真偽値割当 $v$ をとり、その論理式全体への拡張評価を $\hat v$ とする。
$P,Q,R$ の真偽の組 $(P,Q,R)$ は $2^3=8$ 通りである。
$\lor,\land$ の定義より次の真理表を得る。
$$ \begin{array}{|c|c|c|c|c|c|c|c|} \hline P & Q & R & Q \lor R & P \land (Q \lor R) & P \land Q & P \land R & (P \land Q) \lor (P \land R) \\ \hline T & T & T & T & T & T & T & T \\ T & T & F & T & T & T & F & T \\ T & F & T & T & T & F & T & T \\ T & F & F & F & F & F & F & F \\ F & T & T & T & F & F & F & F \\ F & T & F & T & F & F & F & F \\ F & F & T & T & F & F & F & F \\ F & F & F & F & F & F & F & F \\ \hline \end{array} $$
表より、全ての場合に $P \land (Q \lor R)$ と $(P \land Q)\lor(P \land R)$ の真偽は一致する。
従って任意の真偽値割当 $v$ とその拡張 $\hat v$ において両者は同じ真偽値をとるので、
$$ P \land (Q \lor R) \equiv (P \land Q) \lor (P \land R) $$
が成り立つ。
$$ \Box$$

任意の真偽値割当 $v$ をとり、その論理式全体への拡張評価を $\hat v$ とする。
$P,Q,R$ の真偽の組 $(P,Q,R)$ は $2^3=8$ 通りである。
$\lor,\land$ の定義より次の真理表を得る。
$$ \begin{array}{|c|c|c|c|c|c|c|c|} \hline P & Q & R & Q \land R & P \lor (Q \land R) & P \lor Q & P \lor R & (P \lor Q) \land (P \lor R) \\ \hline T & T & T & T & T & T & T & T \\ T & T & F & F & T & T & T & T \\ T & F & T & F & T & T & T & T \\ T & F & F & F & T & T & T & T \\ F & T & T & T & T & T & T & T \\ F & T & F & F & F & T & F & F \\ F & F & T & F & F & F & T & F \\ F & F & F & F & F & F & F & F \\ \hline \end{array} $$
表より、全ての場合に $P \lor (Q \land R)$ と $(P \lor Q)\land(P \lor R)$ の真偽は一致する。
従って任意の真偽値割当 $v$ とその拡張 $\hat v$ において両者は同じ真偽値をとるので、
$$ P \lor (Q \land R) \equiv (P \lor Q) \land (P \lor R) $$
が成り立つ。
$$ \Box$$