命題論理 ③

Prop&Proof

任意の真偽値割当
$$ v:\{P,Q\}\to\{T,F\} $$
をとり、その論理式全体への拡張評価を $\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:\{P,Q\}\to\{T,F\} $$
をとり、その論理式全体への拡張評価を $\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:\{P,Q\}\to\{T,F\} $$
をとり、その論理式全体への拡張評価を $\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:\{P,Q\}\to\{T,F\} $$
をとり、その論理式全体への拡張評価を $\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$$

任意の真偽値割当
$$ v:\{P,Q\}\to\{T,F\} $$
をとり、その論理式全体への拡張評価を $\hat v$ とする。
示すべきことは
$$ \hat v\bigl((\neg P\land\neg Q)\Rightarrow(P\Leftrightarrow Q)\bigr)=T $$
である。
含意の真理表より、
$$ \hat v(\neg P\land\neg Q)=F $$
であれば、
$$ \hat v\bigl((\neg P\land\neg Q)\Rightarrow(P\Leftrightarrow Q)\bigr)=T $$
である(空虚に真)。よって、以下では
$$ \hat v(\neg P\land\neg Q)=T $$
の場合を考える。
このとき、$\land$ の真理表より
$$ \hat v(\neg P)=T \quad\text{かつ}\quad \hat v(\neg Q)=T $$
である。
したがって、$\neg$ の真理表より
$$ v(P)=F \quad\text{かつ}\quad v(Q)=F $$
である。
ゆえに、含意の真理表より
$$ \hat v(P\Rightarrow Q)=T $$
かつ
$$ \hat v(Q\Rightarrow P)=T $$
である。
ここで、$P\Leftrightarrow Q$ は
$$ (P\Rightarrow Q)\land(Q\Rightarrow P) $$
の略記であるから、
$$ \hat v(P\Leftrightarrow Q)=T $$
である。したがって、
$$ \hat v\bigl((\neg P\land\neg Q)\Rightarrow(P\Leftrightarrow Q)\bigr)=T $$
である。
以上より、任意の真偽値割当 $v$ に対して
$$ \hat v\bigl((\neg P\land\neg Q)\Rightarrow(P\Leftrightarrow Q)\bigr)=T $$
が成り立つ。
ゆえに、
$$ (\neg P\land\neg Q)\Rightarrow(P\Leftrightarrow Q) $$
はトートロジーである。
$$ \Box$$

任意の真偽値割当
$$ v:\{P,Q,R\}\to\{T,F\} $$
をとり、その論理式全体への拡張評価を $\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:\{P,Q,R\}\to\{T,F\} $$
をとり、その論理式全体への拡張評価を $\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$$