命題論理 ⑥
$P,Q$ を命題とする。このとき
$$
\bigl((P\lor Q)\land \neg P\bigr)\Rightarrow Q
$$
が成り立つ。
論理式の同値変形によって示す。
まず、含意の性質 $A\Rightarrow B\equiv \neg A\lor B$ より(
証明はコチラ
)
$$
\bigl((P\lor Q)\land \neg P\bigr)\Rightarrow Q
\equiv
\neg\bigl((P\lor Q)\land \neg P\bigr)\lor Q
$$
である。
ここで、ド・モルガンの法則より
$$
\neg\bigl((P\lor Q)\land \neg P\bigr)
\equiv
\neg(P\lor Q)\lor \neg(\neg P)
$$
であり(
証明はコチラ
)、さらにド・モルガンの法則と二重否定の法則(
証明はコチラ
)より
$$
\neg(P\lor Q)\lor \neg(\neg P)
\equiv
(\neg P\land \neg Q)\lor P
$$
となる。したがって
$$
\bigl((P\lor Q)\land \neg P\bigr)\Rightarrow Q
\equiv
\bigl((\neg P\land \neg Q)\lor P\bigr)\lor Q
$$
を得る。
結合法則(
証明はコチラ
)により
$$
\bigl((\neg P\land \neg Q)\lor P\bigr)\lor Q
\equiv
(\neg P\land \neg Q)\lor (P\lor Q)
$$
である。ここで、分配法則 $A\lor (B\land C)\equiv (A\lor B)\land(A\lor C)$ (
証明はコチラ
)を
$A:=P\lor Q$、$B:=\neg P$、$C:=\neg Q$として適用すると
$$
(\neg P\land \neg Q)\lor (P\lor Q)
\equiv
\bigl((P\lor Q)\lor \neg P\bigr)\land \bigl((P\lor Q)\lor \neg Q\bigr)
$$
となる。さらに結合法則と交換法則(
証明はコチラ
)により
$$
\bigl((P\lor Q)\lor \neg P\bigr)\land \bigl((P\lor Q)\lor \neg Q\bigr)
\equiv
\bigl((P\lor \neg P)\lor Q\bigr)\land \bigl(P\lor (Q\lor \neg Q)\bigr)
$$
である。ここで、排中律より
$$
P\lor \neg P\equiv \top,
\qquad
Q\lor \neg Q\equiv \top
$$
であるから(
証明はコチラ
)
$$
\bigl((P\lor \neg P)\lor Q\bigr)\land \bigl(P\lor (Q\lor \neg Q)\bigr)
\equiv
(\top \lor Q)\land (P\lor \top)
$$
となる。支配則より
$$
(\top \lor Q)\land (P\lor \top)
\equiv
\top \land \top
\equiv
\top
$$
である(
証明はコチラ
)。以上より
$$
\bigl((P\lor Q)\land \neg P\bigr)\Rightarrow Q
$$
は恒真式である。したがって
$$
\bigl((P\lor Q)\land \neg P\bigr)\Rightarrow Q
$$
が成り立つ。
$$ \Box$$
任意の真偽値割当 $v$ をとり、その論理式全体への拡張評価を $\hat v$ とする。
$\hat v\bigl((P\lor Q)\land \neg P\bigr)$ の真偽で場合分けする。
- $\hat v\bigl((P\lor Q)\land \neg P\bigr)=T$ の場合
連言 $\land$ の定義より
$$ \hat v(P\lor Q)=T,\qquad \hat v(\neg P)=T $$
である。
また、否定 $\neg$ の定義より
$$ \hat v(P)=F $$
である。
一方、$\hat v(P\lor Q)=T$ であるから、選言 $\lor$ の定義より
$$ \hat v(P)=T\ \text{または}\ \hat v(Q)=T $$
である。しかし $\hat v(P)=F$ であるから
$$ \hat v(Q)=T $$
でなければならない。
したがって、含意 $\Rightarrow$ の定義(後件が真なら、前件がどうであっても $X\Rightarrow Y$ は真 ※補足を参照)より
$$ \hat v\Bigl(\bigl((P\lor Q)\land \neg P\bigr)\Rightarrow Q\Bigr)=T $$
である。
$ $ - $\hat v\bigl((P\lor Q)\land \neg P\bigr)=F$ の場合
このとき前件 $\bigl((P\lor Q)\land \neg P\bigr)$ は偽である。
したがって、含意 $\Rightarrow$ の定義(前件が偽なら含意全体が真 ※補足を参照)より
$$ \hat v\Bigl(\bigl((P\lor Q)\land \neg P\bigr)\Rightarrow Q\Bigr)=T $$
である。
$ $
-以上より、いずれの場合にも
$$
\hat v\Bigl(\bigl((P\lor Q)\land \neg P\bigr)\Rightarrow Q\Bigr)=T
$$
が成り立つ。$v$ は任意であったから、任意の真偽値割当 $v$ に対して
$$
\hat v\Bigl(\bigl((P\lor Q)\land \neg P\bigr)\Rightarrow Q\Bigr)=T
$$
である。従って
$$
\bigl((P\lor Q)\land \neg P\bigr)\Rightarrow Q
$$
はトートロジーである。
$$ \Box$$
$ $
【補足】命題 $X\Rightarrow Y$ の復習
命題 $X\Rightarrow Y$ を真理値表で見ると以下である。
$$
\begin{array}{|c|c|c|}
\hline
X & Y & X\Rightarrow Y \\
\hline
T & T & T \\
T & F & F \\
F & T & T \\
F & F & T \\
\hline
\end{array}
$$
真理値表より、$X\Rightarrow Y$ が偽となるのは、前件 $X$ が真で、後件 $Y$ が偽である場合に限る。
したがって、$X\Rightarrow Y$ が真であり、しかも $X$ が真であるならば、$Y$ も真でなければならない。
また、前件 $X$ が偽ならば、含意全体は真である。
【選言除去】
$P,Q,R$ を命題とする。このとき
$$
\bigl((P\lor Q)\land(P\Rightarrow R)\land(Q\Rightarrow R)\bigr)\Rightarrow R
$$
が成り立つ。
論理式の同値変形によって示す。
まず、前件を変形する。含意の性質 $A\Rightarrow B\equiv \neg A\lor B$ により(
証明はコチラ
)
$$
(P\lor Q)\land(P\Rightarrow R)\land(Q\Rightarrow R)
\equiv
(P\lor Q)\land(\neg P\lor R)\land(\neg Q\lor R)
$$
である。
ここで、分配法則(
証明はコチラ
)
$$
(X\lor Z)\land(Y\lor Z)\equiv (X\land Y)\lor Z
$$
を $X:=\neg P,\ Y:=\neg Q,\ Z:=R$ に適用すると
$$
(P\lor Q)\land(\neg P\lor R)\land(\neg Q\lor R)
\equiv
(P\lor Q)\land\bigl((\neg P\land\neg Q)\lor R\bigr)
$$
となる。さらに、ド・モルガンの法則(
証明はコチラ
)より
$$
\neg P\land\neg Q
\equiv
\neg(P\lor Q)
$$
であるから
$$
(P\lor Q)\land\bigl((\neg P\land\neg Q)\lor R\bigr)
\equiv
(P\lor Q)\land\bigl(\neg(P\lor Q)\lor R\bigr)
$$
を得る。ここで、分配法則(
証明はコチラ
)を用いて
$$
(P\lor Q)\land\bigl(\neg(P\lor Q)\lor R\bigr)
\equiv
\bigl((P\lor Q)\land\neg(P\lor Q)\bigr)\lor\bigl((P\lor Q)\land R\bigr)
$$
となる。矛盾律(
証明はコチラ
)より
$$
(P\lor Q)\land\neg(P\lor Q)\equiv \bot
$$
であるから
$$
\bigl((P\lor Q)\land\neg(P\lor Q)\bigr)\lor\bigl((P\lor Q)\land R\bigr)
\equiv
\bot\lor\bigl((P\lor Q)\land R\bigr)
\equiv
(P\lor Q)\land R
$$
である(
証明はコチラ
)。したがって
$$
(P\lor Q)\land(P\Rightarrow R)\land(Q\Rightarrow R)
\equiv
(P\lor Q)\land R
$$
を得る。
ゆえに、式全体は
$$
\bigl((P\lor Q)\land(P\Rightarrow R)\land(Q\Rightarrow R)\bigr)\Rightarrow R
\equiv
\bigl((P\lor Q)\land R\bigr)\Rightarrow R
$$
と同値である。再び含意の性質(
証明はコチラ
)より
$$
\bigl((P\lor Q)\land R\bigr)\Rightarrow R
\equiv
\neg\bigl((P\lor Q)\land R\bigr)\lor R
$$
であり、ド・モルガンの法則(
証明はコチラ
)より
$$
\neg\bigl((P\lor Q)\land R\bigr)\lor R
\equiv
\bigl(\neg(P\lor Q)\lor\neg R\bigr)\lor R
$$
となる。結合法則(
証明はコチラ
)により
$$
\bigl(\neg(P\lor Q)\lor\neg R\bigr)\lor R
\equiv
\neg(P\lor Q)\lor(\neg R\lor R)
$$
であり、排中律(
詳しくはコチラ
)より $\neg R\lor R\equiv\top$ だから
$$
\neg(P\lor Q)\lor(\neg R\lor R)
\equiv
\neg(P\lor Q)\lor\top
\equiv
\top
$$
となる。したがって
$$
\bigl((P\lor Q)\land(P\Rightarrow R)\land(Q\Rightarrow R)\bigr)\Rightarrow R
$$
は恒真式である。よって
$$
\bigl((P\lor Q)\land(P\Rightarrow R)\land(Q\Rightarrow R)\bigr)\Rightarrow R
$$
が成り立つ。
$$ \Box$$
任意の真偽値割当 $v$ をとり、その論理式全体への拡張評価を $\hat v$ とする。
$\hat v\bigl((P\lor Q)\land(P\Rightarrow R)\land(Q\Rightarrow R)\bigr)$ の真偽で場合分けする。
- $\hat v\bigl((P\lor Q)\land(P\Rightarrow R)\land(Q\Rightarrow R)\bigr)=T$ の場合
連言 $\land$ の定義より
$$ \hat v(P\lor Q)=T,\qquad \hat v(P\Rightarrow R)=T,\qquad \hat v(Q\Rightarrow R)=T $$
である。
また、$\hat v(P\lor Q)=T$ であるから、選言 $\lor$ の定義より
$$ \hat v(P)=T\ \text{または}\ \hat v(Q)=T $$
である。ここで場合分けする。
$ $
i) $\hat v(P)=T$ の場合
すでに
$$ \hat v(P\Rightarrow R)=T $$
である。ところが、もし $\hat v(R)=F$ ならば、$\hat v(P)=T$ であることと合わせて、含意 $\Rightarrow$ の定義より
$$ \hat v(P\Rightarrow R)=F $$
となってしまい矛盾する。したがって
$$ \hat v(R)=T $$
である。
$ $
ii) $\hat v(Q)=T$ の場合
すでに
$$ \hat v(Q\Rightarrow R)=T $$
である。ところが、もし $\hat v(R)=F$ ならば、$\hat v(Q)=T$ であることと合わせて、含意 $\Rightarrow$ の定義より
$$ \hat v(Q\Rightarrow R)=F $$
となってしまい矛盾する。
したがって
$$ \hat v(R)=T $$
である。
$ $
以上より、いずれの場合にも
$$ \hat v(R)=T $$
である。ゆえに、含意 $\Rightarrow$ の定義(後件が真なら、前件がどうであっても $X\Rightarrow Y$ は真)より
$$ \hat v\Bigl(\bigl((P\lor Q)\land(P\Rightarrow R)\land(Q\Rightarrow R)\bigr)\Rightarrow R\Bigr)=T $$
である。
$ $ - $\hat v\bigl((P\lor Q)\land(P\Rightarrow R)\land(Q\Rightarrow R)\bigr)=F$ の場合
このとき前件
$$ (P\lor Q)\land(P\Rightarrow R)\land(Q\Rightarrow R) $$
は偽である。
したがって、含意 $\Rightarrow$ の定義(前件が偽なら含意全体が真)より
$$ \hat v\Bigl(\bigl((P\lor Q)\land(P\Rightarrow R)\land(Q\Rightarrow R)\bigr)\Rightarrow R\Bigr)=T $$
である。
$ $
-以上より、いずれの場合にも
$$
\hat v\Bigl(\bigl((P\lor Q)\land(P\Rightarrow R)\land(Q\Rightarrow R)\bigr)\Rightarrow R\Bigr)=T
$$
が成り立つ。$v$ は任意であったから、任意の真偽値割当 $v$ に対して
$$
\hat v\Bigl(\bigl((P\lor Q)\land(P\Rightarrow R)\land(Q\Rightarrow R)\bigr)\Rightarrow R\Bigr)=T
$$
である。従って
$$
\bigl((P\lor Q)\land(P\Rightarrow R)\land(Q\Rightarrow R)\bigr)\Rightarrow R
$$
はトートロジーである。
$$ \Box$$
$P,Q$ を命題とする。このとき、論理式
$$
((\lnot P\Rightarrow Q)\land(\lnot P\Rightarrow \lnot Q))\Rightarrow P
$$
は恒真式である。
いま、命題 $P,Q$ において、
$$
\varphi:=((\lnot P\Rightarrow Q)\land(\lnot P\Rightarrow \lnot Q))\Rightarrow P
$$
とおく。
$P,Q$ に対する任意の真理値割当を考える。$P$ と $Q$ の真理値の組は次の $4$ 通りで尽くされる。
$$
\begin{array}{|c|c|c|c|c|c|c|c|}
\hline
P & Q & \lnot P & \lnot Q & \lnot P\Rightarrow Q & \lnot P\Rightarrow \lnot Q & (\lnot P\Rightarrow Q)\land(\lnot P\Rightarrow \lnot Q) & \varphi \\
\hline
T & T & F & F & T & T & T & T \\
T & F & F & T & T & T & T & T \\
F & T & T & F & T & F & F & T \\
F & F & T & T & F & T & F & T \\
\hline
\end{array}
$$
最後の列より、任意の真理値割当に対して
$$
\varphi
$$
の真理値は $T$ である。
したがって、
$$
((\lnot P\Rightarrow Q)\land(\lnot P\Rightarrow \lnot Q))\Rightarrow P
$$
は恒真式である。
$$ \Box$$
すなわち、$\lnot P$ を仮定すると $Q$ と $\lnot Q$ がともに導かれるならば、$P$ が成り立つ。
この形は、$\lnot P$ から矛盾が導かれるならば $P$ が成り立つ、という背理法の原理を、命題論理の式として表したものである。
この記事を高評価した人
この記事に送られたバッジ
投稿者
