論理演算の言い換え

含意、同等、排他的論理和はいずれも否定、論理積、論理和を用いて間接的に定義可能です。
含意 同等 排他的論理和
< 前のページ
次のページ >

含意の言い換え

論理式\(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 \)が含まれません。

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

次へ進む 質問・コメント(プレミアム会員限定) 演習問題(プレミアム会員限定)
Share on facebook
Share on twitter
Share on email
< 前のページ
次のページ >

プレミアム会員になると、質問やコメントの投稿と閲覧、プレミアムコンテンツ(命題の証明や演習問題とその解答)へのアクセスなどが可能になります。プレミアム会員の方は以下からログインしてください。

会員登録 | パスワードを忘れましたか?

有料のプレミアム会員になると、質問やコメントの投稿と閲覧、プレミアムコンテンツ(命題の証明や演習問題とその解答)へのアクセスなどが可能になります。

ワイズのユーザーは年齢・性別・学歴・社会的立場などとは関係なく「学ぶ人」として対等であり、お互いを人格として尊重することが求められます。ユーザーが快適かつ安心して「学ぶ」ことに集中できる環境を整備するため、広告やスパム投稿、他のユーザーを貶めたり威圧する発言、学んでいる内容とは関係のない不毛な議論などはブロックすることになっています。詳細はガイドラインをご覧ください。

本サイトは MathJax を実装しているため、コメント文中で LaTex コマンドを利用することで美しい数式を入力できます。その際、インライン数式は\(数式\)で、ディスプレイ数式は$$数式$$という形式でそれぞれ入力してください。 例えば、\(ax^{2}+bx+c=0\)と入力すると\(ax^{2}+bx+c=0\)と表示され、$$ax^{2}+bx+c=0$$と入力すると$$ax^{2}+bx+c=0$$と表示されます。MathJax(LaTex)の文法については次のサイト( https://easy-copy-mathjax.xxxx7.com )などを参照してください。 紙に手書きした数式や図をカメラやスマホで撮影した上で、コメント欄に張り付けることもできます。その場合、コメント入力欄にある「ファイルを選択」ボタンをクリックした上で画像をアップロードしてください。アップロード可能な画像フォーマットは jpg, gif, png の 3 種類、ファイルサイズの上限は 5 MB です。PDF ファイルの添付も可能です。

誤字脱字、リンク切れ、内容の誤りを発見した場合にはコメントに投稿するのではなく、以下のフォームからご連絡をお願い致します。

プレミアム会員だけが質問やコメントを投稿・閲覧できます。

命題論理