命題論理 ⑦

Prop&Proof

$P\Rightarrow Q$ を仮定する。この仮定のもとで
$$ (P\lor Q)\Leftrightarrow Q $$
を示せばよい。

1. $(P\lor Q)\Rightarrow Q$ を示す。
   $P\lor Q$ を仮定する。選言除去により場合分けする。
   まず、$P$ が成り立つと仮定する。このとき、仮定 $P\Rightarrow Q$ と $P$ から、含意除去により $Q$ が従う( 証明はコチラ )。
   次に、$Q$ が成り立つと仮定する。このとき、ただちに $Q$ が成り立つ。
   したがって、いずれの場合にも $Q$ が従う。
   ゆえに、選言除去により、仮定 $P\lor Q$ から $Q$ が従う。よって、
   $$ (P\lor Q)\Rightarrow Q $$
   が成り立つ。
   $ $
2. $Q\Rightarrow(P\lor Q)$ を示す。
   $Q$ を仮定する。このとき、選言導入により
   $$ P\lor Q $$
   が成り立つ( 証明はコチラ )。よって、
   $$ Q\Rightarrow(P\lor Q) $$
   が成り立つ。

-1. と 2. より、双条件により
$$ (P\lor Q)\Leftrightarrow Q $$
が成り立つ。したがって、仮定 $P\Rightarrow Q$ のもとで
$$ (P\lor Q)\Leftrightarrow Q $$
が成り立つので、
$$ (P\Rightarrow Q)\Rightarrow\bigl((P\lor Q)\Leftrightarrow Q\bigr) $$
が成り立つ。
以上より、
$$ (P\Rightarrow Q)\Rightarrow\bigl((P\lor Q)\Leftrightarrow Q\bigr) $$
は恒真式である。
$$ \Box$$

$P\Rightarrow Q$ を仮定する。
この仮定のもとで
$$ (P\land Q)\Leftrightarrow P $$
を示す。

1. $(P\land Q)\Rightarrow P$ を示す。
   $P\land Q$ を仮定する。連言除去( 証明はコチラ )により、$P$ が従う。
   したがって、仮定 $P\land Q$ から $P$ が導けたので、
   $$ (P\land Q)\Rightarrow P $$
   が成り立つ。
2. $P\Rightarrow(P\land Q)$ を示す。
   $P$ を仮定する。いま、最初の仮定 $P\Rightarrow Q$ と、仮定 $P$ から、含意除去により $Q$ が従う( 証明はコチラ )。
   したがって、$P$ と $Q$ がともに成り立つので、
   $$ P\land Q $$
   が成り立つ。よって、仮定 $P$ から $P\land Q$ が導けたので、
   $$ P\Rightarrow(P\land Q) $$
   が成り立つ。

-1. と 2. より、双条件により
$$ (P\land Q)\Leftrightarrow P $$
が成り立つ。
したがって、仮定 $P\Rightarrow Q$ のもとで
$$ (P\land Q)\Leftrightarrow P $$
が導けたので、
$$ (P\Rightarrow Q)\Rightarrow\bigl((P\land Q)\Leftrightarrow P\bigr) $$
が成り立つ。
以上より、
$$ (P\Rightarrow Q)\Rightarrow\bigl((P\land Q)\Leftrightarrow P\bigr) $$
は恒真式である。
$$ \Box$$

次の双方向を示す。

1. $((P\lor Q)\Rightarrow R)\Rightarrow((P\Rightarrow R)\land(Q\Rightarrow R))$ を示す。
   $(P\lor Q)\Rightarrow R$ を仮定する。まず、$P\Rightarrow R$ を示す。
   $P$ を仮定する。このとき、選言導入( 証明はコチラ )により
   $$ P\lor Q $$
   が成り立つ。
   仮定 $(P\lor Q)\Rightarrow R$ と $P\lor Q$ から、含意除去により $R$ が従う( 証明はコチラ )。
   したがって、仮定 $P$ から $R$ が導けたので、
   $$ P\Rightarrow R $$
   が成り立つ。
   $ $
   次に、$Q\Rightarrow R$ を示す。
   $Q$ を仮定する。このとき、選言導入により
   $$ P\lor Q $$
   が成り立つ( 証明はコチラ )。
   仮定 $(P\lor Q)\Rightarrow R$ と $P\lor Q$ から、含意除去により $R$ が従う( 証明はコチラ )。
   したがって、仮定 $Q$ から $R$ が導けたので、
   $$ Q\Rightarrow R $$
   が成り立つ。
   $ $
   以上より、$P\Rightarrow R$ と $Q\Rightarrow R$ がともに成り立つので、
   $$ (P\Rightarrow R)\land(Q\Rightarrow R) $$
   が成り立つ。
   したがって、仮定 $(P\lor Q)\Rightarrow R$ から $(P\Rightarrow R)\land(Q\Rightarrow R)$ が導けたので、
   $$ ((P\lor Q)\Rightarrow R)\Rightarrow((P\Rightarrow R)\land(Q\Rightarrow R)) $$
   が成り立つ。
   $ $
2. $((P\Rightarrow R)\land(Q\Rightarrow R))\Rightarrow((P\lor Q)\Rightarrow R)$ を示す。
   $(P\Rightarrow R)\land(Q\Rightarrow R)$ を仮定する。
   連言除去により、
   $$ P\Rightarrow R $$
   および
   $$ Q\Rightarrow R $$
   が成り立つ( 証明はコチラ )。
   いま、$(P\lor Q)\Rightarrow R$ を示すため、$P\lor Q$ を仮定する。
   選言除去により場合分けする。
   まず、$P$ が成り立つと仮定する。このとき、$P\Rightarrow R$ と $P$ から、$R$ が従う( 証明はコチラ )。
   次に、$Q$ が成り立つと仮定する。このとき、$Q\Rightarrow R$ と $Q$ から、$R$ が従う( 証明はコチラ )。
   したがって、いずれの場合にも $R$ が従うので、選言除去により、仮定 $P\lor Q$ から $R$ が従う。
   よって、仮定 $P\lor Q$ から $R$ が導けたので、
   $$ (P\lor Q)\Rightarrow R $$
   が成り立つ。
   したがって、仮定 $(P\Rightarrow R)\land(Q\Rightarrow R)$ から $(P\lor Q)\Rightarrow R$ が導けたので、含意導入により
   $$ ((P\Rightarrow R)\land(Q\Rightarrow R))\Rightarrow((P\lor Q)\Rightarrow R) $$
   が成り立つ。
   $ $

-1. と 2. より、双条件導入により
$$ ((P\lor Q)\Rightarrow R)\Leftrightarrow((P\Rightarrow R)\land(Q\Rightarrow R)) $$
が成り立つ。
以上より、
$$ ((P\lor Q)\Rightarrow R)\Leftrightarrow((P\Rightarrow R)\land(Q\Rightarrow R)) $$
は恒真式である。
$$ \Box$$

次の双方向を示す。

1. $(P\Rightarrow(Q\land R))\Rightarrow((P\Rightarrow Q)\land(P\Rightarrow R))$ を示す。
   $P\Rightarrow(Q\land R)$ を仮定する。まず、$P\Rightarrow Q$ を示す。
   $P$ を仮定する。仮定 $P\Rightarrow(Q\land R)$ と $P$ から、
   $$ Q\land R $$
   が従う( 証明はコチラ )。
   よって、連言除去により
   $$ Q $$
   が従う( 証明はコチラ )。
   したがって、仮定 $P$ から $Q$ が導けたので、
   $$ P\Rightarrow Q $$
   が成り立つ。
   $ $
   次に、$P\Rightarrow R$ を示す。
   $P$ を仮定する。仮定 $P\Rightarrow(Q\land R)$ と $P$ から、
   $$ Q\land R $$
   が従う( 証明はコチラ )。
   よって、連言除去により
   $$ R $$
   が従う( 証明はコチラ )。
   したがって、仮定 $P$ から $R$ が導けたので、
   $$ P\Rightarrow R $$
   が成り立つ。
   $ $
   以上より、$P\Rightarrow Q$ と $P\Rightarrow R$ がともに成り立つので、連言導入により
   $$ (P\Rightarrow Q)\land(P\Rightarrow R) $$
   が成り立つ。
   したがって、仮定 $P\Rightarrow(Q\land R)$ から $(P\Rightarrow Q)\land(P\Rightarrow R)$ が導けたので、
   $$ (P\Rightarrow(Q\land R))\Rightarrow((P\Rightarrow Q)\land(P\Rightarrow R)) $$
   が成り立つ。
   $ $
2. $((P\Rightarrow Q)\land(P\Rightarrow R))\Rightarrow(P\Rightarrow(Q\land R))$ を示す。
   $(P\Rightarrow Q)\land(P\Rightarrow R)$ を仮定する。
   連言除去により
   $$ P\Rightarrow Q $$
   および
   $$ P\Rightarrow R $$
   が成り立つ( 証明はコチラ )。
   いま、$P\Rightarrow(Q\land R)$ を示すため、$P$ を仮定する。
   $P\Rightarrow Q$ と $P$ から、含意除去により
   $$ Q $$
   が従う( 証明はコチラ )。
   また、$P\Rightarrow R$ と $P$ から、
   $$ R $$
   が従う( 証明はコチラ )。
   したがって、$Q$ と $R$ がともに成り立つので、連言導入により
   $$ Q\land R $$
   が成り立つ。
   よって、仮定 $P$ から $Q\land R$ が導けたので、
   $$ P\Rightarrow(Q\land R) $$
   が成り立つ。
   したがって、仮定 $(P\Rightarrow Q)\land(P\Rightarrow R)$ から $P\Rightarrow(Q\land R)$ が導けたので、
   $$ ((P\Rightarrow Q)\land(P\Rightarrow R))\Rightarrow(P\Rightarrow(Q\land R)) $$
   が成り立つ。

-1. と 2. より、双条件導入により
$$ (P\Rightarrow(Q\land R))\Leftrightarrow((P\Rightarrow Q)\land(P\Rightarrow R)) $$
が成り立つ。
以上より、
$$ (P\Rightarrow(Q\land R))\Leftrightarrow((P\Rightarrow Q)\land(P\Rightarrow R)) $$
は恒真式である。
$$ \Box$$

真理値表により示す。
$$ \begin{array}{|c|c|c|c|c|c|c|} \hline P & Q & R & \neg Q & P\land \neg Q & (P\land \neg Q)\Rightarrow R & P\Rightarrow(Q\lor R) \\ \hline T & T & T & F & F & T & T \\ T & T & F & F & F & T & T \\ T & F & T & T & T & T & T \\ T & F & F & T & T & F & F \\ F & T & T & F & F & T & T \\ F & T & F & F & F & T & T \\ F & F & T & T & F & T & T \\ F & F & F & T & F & T & T \\ \hline \end{array} $$
表より、任意の真理値割当てに対して、
$$ (P\land \neg Q)\Rightarrow R $$
が真であるならば、
$$ P\Rightarrow(Q\lor R) $$
も真である。
したがって、
$$ \bigl((P\land \neg Q)\Rightarrow R\bigr) \Rightarrow \bigl(P\Rightarrow(Q\lor R)\bigr) $$
は恒真式である。
$$ \Box$$