WIIS

教材一覧
教材一覧
教材検索
PROPOSITIONAL LOGIC

命題論理における論理演算の言い換え

目次

Share on twitter
Twitterで共有
Share on email
メールで共有

含意の言い換え

論理式\(A,B\)をそれぞれ任意に選んだとき、以下の真理値表が得られます。

$$\begin{array}{ccccc}
\hline
A & B & \lnot A & \lnot A\vee B & A\rightarrow B \\ \hline
1 & 1 & 0 & 1 & 1 \\ \hline
1 & 0 & 0 & 0 & 0 \\ \hline
0 & 1 & 1 & 1 & 1 \\ \hline
0 & 0 & 1 & 1 & 1 \\ \hline
\end{array}$$

表:含意の言い換え

つまり、任意の解釈のもとで\(A\rightarrow B\)の値は\(\lnot A\vee B\)の値と一致するため、\begin{equation*}A\rightarrow B\Leftrightarrow \lnot A\vee B
\end{equation*}という関係が成り立ちます。

命題(含意の言い換え)

任意の論理式\(A,B\)に対して、\begin{equation*}A\rightarrow B\Leftrightarrow \lnot A\vee B
\end{equation*}が成り立つ。

論理式\(A\)が部分論理式\(B\rightarrow C\)を持つとき、\(A\)中の\(B\rightarrow C\)を\(\lnot B\vee C\)に置き換えて得られる論理式を\(A^{\prime }\)で表します。上の命題より\(B\rightarrow C\)と\(\lnot B\vee C\)の真理値は任意の解釈のもとで一致するため、\(A\)と\(A^{\prime }\)の真理値もまた任意の解釈のもとで一致します。したがって、論理式の中に\(\rightarrow \)が含まれる場合には、それを\(\lnot \)と\(\vee \)に置き換えることができます。

例(含意の言い換え)
命題変数\(P,Q,R\)に関する論理式\(\left( P\wedge \lnot Q\right) \rightarrow \lnot R\)を同値変形すると、\begin{eqnarray*}\left( P\wedge \lnot Q\right) \rightarrow \lnot R &\Leftrightarrow &\lnot
\left( P\wedge \lnot Q\right) \vee \lnot R\quad \because \rightarrow \text{の言い換え} \\
&\Leftrightarrow &\left( \lnot P\vee \lnot \lnot Q\right) \vee \lnot R\quad
\because \text{ド・モルガンの法則} \\
&\Leftrightarrow &\lnot P\vee Q\vee \lnot R\quad \because \text{二重否定}
\end{eqnarray*}となります。同値変形後の論理式\(\lnot P\vee Q\vee \lnot R\)には\(\rightarrow \)が含まれません。
例(含意の言い換え)
命題変数\(P,Q,R\)に関する論理式\(\lnot P\rightarrow \lnot \left( Q\rightarrow \lnot R\right) \)を同値変形すると、\begin{eqnarray*}\lnot P\rightarrow \lnot \left( Q\rightarrow \lnot R\right) &\Leftrightarrow
&\lnot \lnot P\vee \lnot \left( \lnot Q\vee \lnot R\right) \quad \because
\rightarrow \text{の言い換え} \\
&\Leftrightarrow &\lnot \lnot P\vee \left( \lnot \lnot Q\wedge \lnot \lnot
R\right) \quad \because \text{ド・モルガンの法則} \\
&\Leftrightarrow &P\vee \left( Q\wedge R\right) \quad \because \text{二重否定}
\end{eqnarray*}となります。同値変形後の論理式\(P\vee \left( Q\wedge R\right) \)には\(\rightarrow \)が含まれません。

 

同等の言い換え

論理式\(A,B\)をそれぞれ任意に選んだとき、以下の真理値表が得られます。

$$\begin{array}{cccccc}
\hline
A & B & A\rightarrow B & B\rightarrow A & \left( A\rightarrow B\right) \wedge \left( B\rightarrow A\right) & A\leftrightarrow B \\ \hline
1 & 1 & 1 & 1 & 1 & 1 \\ \hline
1 & 0 & 0 & 1 & 0 & 0 \\ \hline
0 & 1 & 1 & 0 & 0 & 0 \\ \hline
0 & 0 & 1 & 1 & 1 & 1 \\ \hline
\end{array}$$

表:同等の言い換え

つまり、任意の解釈のもとで\(A\leftrightarrow B\)の値は\(\left( A\rightarrow B\right) \wedge \left( B\rightarrow A\right) \)の値と一致するため、\begin{equation*}A\leftrightarrow B\Leftrightarrow \left( A\rightarrow B\right) \wedge \left(
B\rightarrow A\right)
\end{equation*}という関係が成り立ちます。

命題(同等の言い換え)

任意の論理式\(A,B\)に対して、\begin{equation*}A\leftrightarrow B\Leftrightarrow \left( A\rightarrow B\right) \wedge \left(
B\rightarrow A\right)
\end{equation*}が成り立つ。

論理式\(A\)が部分論理式\(B\leftrightarrow C\)を持つとき、\begin{eqnarray*}B\leftrightarrow C &\Leftrightarrow &\left( B\rightarrow C\right) \wedge
\left( C\rightarrow B\right) \\
&\Leftrightarrow &\left( \lnot B\vee C\right) \wedge \left( \lnot C\vee
B\right)
\end{eqnarray*}という関係が成り立つため、\(A\)中の\(B\leftrightarrow C\)を\(\left( \lnot B\vee C\right) \wedge \left( \lnot C\vee B\right) \)に置き換えて得られる論理式を\(A^{\prime }\)で表すのであれば、\(A\)と\(A^{\prime }\)の真理値は任意の解釈のもとで一致します。したがって、論理式の中に\(\leftrightarrow \)が含まれる場合には、それを\(\lnot \)と\(\vee \)に置き換えることができます。

例(同等の言い換え)
命題変数\(P,Q\)に関する論理式\(P\leftrightarrow \lnot Q\)を同値変形すると、\begin{eqnarray*}P\leftrightarrow \lnot Q &\Leftrightarrow &\left( P\rightarrow \lnot
Q\right) \wedge \left( \lnot Q\rightarrow P\right) \quad \because
\leftrightarrow \text{の言い換え} \\
&\Leftrightarrow &\left( \lnot P\vee \lnot Q\right) \wedge \left( \lnot
\lnot Q\vee P\right) \quad \because \rightarrow \text{の言い換え} \\
&\Leftrightarrow &\left( \lnot P\vee \lnot Q\right) \wedge \left( Q\vee
P\right) \quad \because \text{二重否定}
\end{eqnarray*}となります。同値変形後の論理式\(\left( \lnot P\vee \lnot Q\right) \wedge \left( Q\vee P\right) \)には\(\leftrightarrow \)や\(\rightarrow \)が含まれません。
例(同等の言い換え)
命題変数\(P,Q,R\)に関する論理式\(\left( P\wedge \lnot Q\right) \leftrightarrow \lnot R\)を同値変形すると、\begin{eqnarray*}\left( P\wedge \lnot Q\right) \leftrightarrow \lnot R &\Leftrightarrow
&\left( \left( P\wedge \lnot Q\right) \rightarrow \lnot R\right) \wedge
\left( \lnot R\rightarrow \left( P\wedge \lnot Q\right) \right) \quad
\because \leftrightarrow \text{の言い換え} \\
&\Leftrightarrow &\left( \lnot \left( P\wedge \lnot Q\right) \vee \lnot
R\right) \wedge \left( \lnot \lnot R\vee \left( P\wedge \lnot Q\right)
\right) \quad \because \rightarrow \text{の言い換え} \\
&\Leftrightarrow &\left( \left( \lnot P\vee \lnot \lnot Q\right) \vee \lnot
R\right) \wedge \left( \lnot \lnot R\vee \left( P\wedge \lnot Q\right)
\right) \quad \because \text{ド・モルガンの法則} \\
&\Leftrightarrow &\left( \lnot P\vee Q\vee \lnot R\right) \wedge \left(
R\vee \left( P\wedge \lnot Q\right) \right) \quad \because \text{二重否定}
\end{eqnarray*}となります。同値変形後の論理式\(\left( \lnot P\vee Q\vee\lnot R\right) \wedge \left( R\vee \left( P\wedge \lnot Q\right) \right) \)には\(\leftrightarrow \)や\(\rightarrow \)が含まれません。

 

排他的論理和の言い換え

論理式\(A,B\)をそれぞれ任意に選んだとき、以下の真理値表が得られます。

$$\begin{array}{cccccccc}
\hline
A & B & \lnot A & \lnot B & A\wedge \lnot B & \lnot A\wedge B & \left( A\wedge \lnot B\right) \vee \left( \lnot A\wedge B\right) & A\veebar B \\ \hline
1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline
1 & 0 & 0 & 1 & 1 & 0 & 1 & 1 \\ \hline
0 & 1 & 1 & 0 & 0 & 1 & 1 & 1 \\ \hline
0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ \hline
\end{array}$$

表:排他的論理和の言い換え

つまり、任意の解釈のもとで\(A\veebar B\)の値は\(\left(A\wedge \lnot B\right) \vee \left( \lnot A\wedge B\right) \)の値と一致するため、\begin{equation*}A\veebar B\Leftrightarrow \left( A\wedge \lnot B\right) \vee \left( \lnot
A\wedge B\right)
\end{equation*}という関係が成り立ちます。

命題(排他的論理和の言い換え)
任意の論理式\(A,B\)に対して、\begin{equation*}A\veebar B\Leftrightarrow \left( A\wedge \lnot B\right) \vee \left( \lnot
A\wedge B\right)
\end{equation*}が成り立つ。

論理式\(A\)が部分論理式\(B\veebar C\)を持つとき、\(A\)中の\(B\veebar C\)を\(\left( A\wedge \lnot B\right) \vee \left( \lnot A\wedge B\right) \)に置き換えて得られる論理式を\(A^{\prime }\)で表します。上の命題より\(B\veebar C\)と\(\left( A\wedge \lnot B\right) \vee\left( \lnot A\wedge B\right) \)の真理値は任意の解釈のもとで一致するため、\(A\)と\(A^{\prime }\)の真理値もまた任意の解釈のもとで一致します。したがって、論理式の中に\(\veebar \)が含まれる場合には、それを\(\lnot ,\wedge ,\vee \)に置き換えることができます。

例(排他的論理和の言い換え)
命題変数\(P,Q\)に関する論理式\(P\veebar \lnot Q\)を同値変形すると、\begin{eqnarray*}P\veebar \lnot Q &\Leftrightarrow &\left( P\wedge \lnot \lnot Q\right) \vee
\left( \lnot P\wedge \lnot Q\right) \quad \because \veebar \text{の言い換え} \\
&\Leftrightarrow &\left( P\wedge Q\right) \vee \left( \lnot P\wedge \lnot
Q\right) \quad \because \text{二重否定}
\end{eqnarray*}となります。同値変形後の論理式\(\left( P\wedge Q\right)\vee \left( \lnot P\wedge \lnot Q\right) \)には\(\veebar \)が含まれません。
例(排他的論理和の言い換え)
命題変数\(P,Q,R\)に関する論理式\(\left( P\wedge \lnot Q\right) \veebar \lnot R\)を同値変形すると、\begin{eqnarray*}\left( P\wedge \lnot Q\right) \veebar \lnot R &\Leftrightarrow &\left(
\left( P\wedge \lnot Q\right) \wedge \lnot \lnot R\right) \vee \left( \lnot
\left( P\wedge \lnot Q\right) \wedge \lnot R\right) \quad \because \veebar
\text{の言い換え} \\
&\Leftrightarrow &\left( \left( P\wedge \lnot Q\right) \wedge \lnot \lnot
R\right) \vee \left( \left( \lnot P\vee \lnot \lnot Q\right) \wedge \lnot
R\right) \quad \because \text{ド・モルガンの法則} \\
&\Leftrightarrow &\left( P\wedge \lnot Q\wedge R\right) \vee \left( \left(
\lnot P\vee Q\right) \wedge \lnot R\right) \quad \because \text{ド・モルガンの法則}
\end{eqnarray*}となります。同値変形後の論理式\(\left( P\wedge \lnot Q\wedge R\right) \vee \left( \left( \lnot P\vee Q\right) \wedge \lnot R\right) \)には\(\veebar \)が含まれません。

 

論理式の定義:再論

論理演算子として\(\lnot,\wedge ,\vee ,\rightarrow ,\leftrightarrow ,\veebar \)を定義しましたが、先に示したように\(\rightarrow,\leftrightarrow ,\veebar \)はいずれも\(\lnot,\wedge ,\vee \)によって言い換え可能であるため、結局、論理演算子として\(\lnot ,\wedge ,\vee \)だけ与えられれば任意の論理式を表現することができます。具体的には、論理式\(A,B\)がそれぞれ任意に与えられたとき、\begin{eqnarray*}&&\left( a\right) \ A\rightarrow B\Leftrightarrow \lnot A\vee B \\
&&\left( b\right) \ A\leftrightarrow B\Leftrightarrow \left( A\rightarrow
B\right) \wedge \left( B\rightarrow A\right) \\
&&\left( c\right) \ A\veebar B\Leftrightarrow \left( A\wedge \lnot B\right)
\vee \left( \lnot A\wedge B\right)
\end{eqnarray*}などの関係が成り立つため、これらの関係を適用することにより、論理式中の\(\rightarrow,\leftrightarrow ,\veebar \)を\(\lnot ,\wedge ,\vee \)に置き換えることができます。以上の事実を踏まえると、論理式を以下のように定義しなおしても一般性は失われません。

  1. 命題変数\(P,Q,\cdots \)は論理式である。
  2. 命題定数\(T,F\)は論理式である。
  3. \(A\)が論理式ならば、\(\left( \lnot A\right) \)は論理式である。
  4. \(A,B\)が論理式ならば、\(\left( A\wedge B\right) \)は論理式である。
  5. \(A,B\)が論理式ならば、\(\left( A\vee B\right) \)は論理式である。
  6. 以上から論理式と判定されるものだけが論理式である。

 

演習問題

問題(論理演算の言い換え)
任意の論理式\(A,B\)について、\begin{equation*}\lnot \left( A\rightarrow B\right) \vee \left( A\wedge B\right)
\Leftrightarrow A
\end{equation*}が成り立つことを証明してください。

解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

問題(論理演算の言い換え)
任意の論理式\(A,B\)について、\begin{equation*}\left( A\vee B\right) \wedge \left( \lnot A\rightarrow \lnot B\right)
\Leftrightarrow A
\end{equation*}が成り立つことを証明してください。

解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

問題(論理演算の言い換え)
任意の論理式\(A,B,C\)について、\begin{equation*}\left( A\rightarrow \lnot B\right) \rightarrow C\Leftrightarrow \left(
A\wedge B\right) \vee C
\end{equation*}が成り立つことを証明してください。

解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

問題(論理演算の言い換え)
任意の論理式\(A,B\)について、\begin{equation*}\left( \left( A\rightarrow B\right) \rightarrow B\right) \rightarrow
B\Leftrightarrow A\rightarrow B
\end{equation*}が成り立つことを証明してください。

解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

問題(論理演算の言い換え)
任意の論理式\(A,B\)について、\begin{equation*}\left( A\wedge \lnot B\right) \rightarrow \left( B\wedge \lnot B\right)
\Leftrightarrow A\rightarrow B
\end{equation*}が成り立つことを証明してください。

解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

次回は対偶律について学びます。

Share on twitter
Twitterで共有
Share on email
メールで共有
RELATED KNOWLEDGE

関連知識

排他的論理和
命題論理における排他的論理和

排他的論理和は入力された 2 つの論理式に対して、それらのどちらか一方の値だけが 1 である場合にのみ 1 を値としてとる論理式を出力する論理演算です。

含意
命題論理における含意

含意 → は入力された論理式 A,B に対して、A と B の値がともに 1 である場合には 1 を値としてとり、A の値が 0 の場合には B の値によらず常に 1 を値としてとる論理式 A→B を出力する論理演算です。

同等
命題論理における同等

同等は入力された論理式 A,B に対して、A と B の値が一致する場合にのみ 1 を値としてとる論理式を出力する論理演算です。

排他的論理和
述語論理における排他的論理和

論理式 A,B に論理演算子 ⊻ を作用させることで得られる A⊻B もまた論理式です。⊻ は排他的論理和と呼ばれる論理演算子であり、論理式 A⊻B を A と B の排他的論理和と呼びます。

対称差
対称差

集合 A,B のどちらか一方だけに属する要素からなる集合を A と B の対称差と呼びます。集合 A が命題関数 P(x) から、集合 B が命題関数 Q(x) から内包的に定義されるとき、A と B の対称差は P(x) と Q(x) のどちらか一方だけが真になるような要素 x からなる集合です。

含意
述語論理における含意

論理式 A,B に論理演算子 → を作用させることで得られる A→B もまた論理式です。→ は含意と呼ばれる論理演算子であり、論理式 A→B を A から B への含意と呼びます。

同等
述語論理における同等

論理式 A,B に論理演算子 ↔ を作用させることで得られる A↔B は論理式です。↔ は同等と呼ばれる論理演算子であり、論理式 A↔B を A と B の同等と呼びます。

DISCUSSION

質問とコメント

プレミアム会員専用コンテンツです
ログイン】【会員登録

命題論理