論理積と論理和の間には分配律と呼ばれる関係が成り立ちます。
< 前のページ
次のページ >

分配律

論理式\(A,B,C\)がそれぞれ任意に与えられたとき、解釈を任意に選んだ上で、変数の自由な現れに代入し得る値の組\(x\)を任意に選ぶと、\begin{eqnarray*}
x\in \phi \left( A\wedge \left( B\vee C\right) \right) &\Leftrightarrow
&x\in \phi \left( A\right) \wedge x\in \phi \left( B\vee C\right) \quad
\because \wedge \text{の定義} \\
&\Leftrightarrow &x\in \phi \left( A\right) \wedge \left( x\in \phi \left(
B\right) \vee x\in \phi \left( C\right) \right) \quad \because \vee \text{の定義} \\
&\Leftrightarrow &\left( x\in \phi \left( A\right) \wedge x\in \phi \left(
B\right) \right) \vee \left( x\in \phi \left( A\right) \wedge x\in \phi
\left( C\right) \right) \quad \because \text{分配律} \\
&\Leftrightarrow &x\in \phi \left( A\wedge B\right) \vee x\in \phi \left(
A\wedge C\right) \quad \because \wedge \text{の定義} \\
&\Leftrightarrow &x\in \phi \left( \left( A\wedge B\right) \vee \left(
A\wedge C\right) \right) \quad \because \vee \text{の定義}
\end{eqnarray*}すなわち、\begin{equation*}
\phi \left( A\wedge \left( B\vee C\right) \right) =\phi \left( \left(
A\wedge B\right) \vee \left( A\wedge C\right) \right)
\end{equation*}が成り立ちます。任意の解釈について同様の議論が成り立つため、\begin{equation*}
\left( a\right) \ A\wedge \left( B\vee C\right) \Leftrightarrow \left(
A\wedge B\right) \vee \left( A\wedge C\right)
\end{equation*}であることが示されました。\(\left( a\right) \)において\(\wedge \)を\(\vee \)に置き換えると、\begin{equation*}
\left( b\right) \ A\vee \left( B\wedge C\right) \Leftrightarrow \left( A\vee
B\right) \wedge \left( A\vee C\right)
\end{equation*}を得ますが、これが成り立つことも同様にして示されます。つまり、述語論理においても論理積と論理和の間に分配律(distributive law)が成り立つということです。

命題(分配律)
任意の論理式\(A,B,C\)に対して以下が成り立つ。\begin{align*}
& \left( a\right) \ A\wedge (B\vee C)\Leftrightarrow (A\wedge B)\vee
(A\wedge C) \\
& \left( b\right) \ A\vee (B\wedge C)\Leftrightarrow (A\vee B)\wedge (A\vee
C)
\end{align*}
証明を見る(プレミアム会員限定)
例(分配律)
命題関数\(P\left( x\right) \)と\(Q\left( x,y\right) \)と\(R\left( y\right) \)について、分配律より、\begin{equation*}
P\left( x\right) \wedge \left( Q\left( x,y\right) \vee R\left( y\right)
\right) \Leftrightarrow \left( P\left( x\right) \wedge Q\left( x,y\right)
\right) \vee \left( P\left( x\right) \wedge R\left( y\right) \right)
\end{equation*}が成り立ちます。
例(分配律)
命題関数\(P\left( x\right) \)と\(Q\left( x\right)\)と\(R\left( x\right) \)について、分配律より、\begin{equation*}
\forall x\ \left( P\left( x\right) \wedge \left( Q\left( x\right) \vee
R\left( x\right) \right) \right) \Leftrightarrow \forall x\ \left( \left(
P\left( x\right) \wedge Q\left( x\right) \right) \vee \left( P\left(
x\right) \wedge R\left( x\right) \right) \right)
\end{equation*}が成り立ちます。
例(分配律)
任意の命題関数\(P\left( x\right) \)と\(Q\left( x,y\right) \)について、\begin{eqnarray*}
P\left( x\right) \wedge \left( Q\left( x,y\right) \vee P\left( x\right)
\right) &\Leftrightarrow &\left( P\left( x\right) \wedge Q\left( x,y\right)
\right) \vee \left( P\left( x\right) \wedge P\left( x\right) \right) \quad
\because \text{分配律} \\
&\Leftrightarrow &\left( P\left( x\right) \wedge Q\left( x,y\right) \right)
\vee P\left( x\right) \quad \because \text{ベキ等律}
\\
&\Leftrightarrow &P\left( x\right) \vee \left( Q\left( x,y\right) \wedge
P\left( x\right) \right) \quad \because \text{交換律}
\end{eqnarray*}が成り立ちます。つまり、\(P\left( x\right) \wedge \left( Q\left( x,y\right) \vee P\left( x\right) \right) \)において\(\wedge \)と\(\vee \)を入れ替えると新たな論理式\(P\left( x\right) \vee \left( Q\left( x,y\right) \wedge P\left( x\right) \right) \)を得られますが、これらは論理的に同値です。

 

後ろからの分配

分配律に加えて交換律を踏まえると、任意の論理式\(A,B,C\)に対して、\begin{align*}
\left( A\vee B\right) \wedge C& \Leftrightarrow C\wedge \left( A\vee
B\right) \quad \because \text{交換律} \\
& \Leftrightarrow \left( C\wedge A\right) \vee \left( C\wedge B\right) \quad
\because \text{分配律} \\
& \Leftrightarrow \left( A\wedge C\right) \vee \left( B\wedge C\right) \quad
\because \text{交換律}
\end{align*}が成り立ちます。つまり、\begin{equation*}
\left( A\vee B\right) \wedge C\Leftrightarrow \left( A\wedge C\right) \vee
\left( B\wedge C\right)
\end{equation*}という形で、後ろからの分配が可能になります。同様に、\begin{equation*}
\left( A\wedge B\right) \vee C\Leftrightarrow \left( A\vee C\right) \wedge
\left( B\vee C\right)
\end{equation*}もまた成り立ちます。

命題(後ろからの分配)
任意の論理式\(A,B,C\)に対して以下が成り立つ。\begin{align*}
& \left( a\right) \ \left( A\vee B\right) \wedge C\Leftrightarrow \left(
A\wedge C\right) \vee \left( B\wedge C\right) \\
& \left( b\right) \ \left( A\wedge B\right) \vee C\Leftrightarrow \left(
A\vee C\right) \wedge \left( B\vee C\right)
\end{align*}
証明を見る(プレミアム会員限定)

次回は吸収律について学びます。

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

プレミアム会員サービス

ユーザー名とメールアドレスを入力して有料(500円/月)のプレミアム会員へアップグレードすることにより、質問やコメントの投稿と閲覧、プレミアムコンテンツ(命題の証明や演習問題、解答など)へのアクセスが可能に。
会員サービス
ログイン

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

述語論理
アカウント
ログイン