教材一覧
教材一覧
教材検索
PREDICATE LOGIC

述語論理における分配律

目次

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

分配律

論理式\(A,B,C\)がそれぞれ任意に与えられたとき、解釈を任意に選んだ上で、その場合に\(A\)から得られる命題を\(\overline{A}\)で、\(B\)から得られる命題を\(\overline{B}\)で、\(B\)から得られる命題を\(\overline{C}\)でそれぞれ表記します。すると命題論理における\(\wedge \)と\(\vee \)に関する分配律より、\begin{eqnarray*}&&\left( a\right) \ \overline{A}\wedge (\overline{B}\vee \overline{C})\Leftrightarrow (\overline{A}\wedge \overline{B})\vee (\overline{A}\wedge
\overline{C}) \\
&&\left( b\right) \ \overline{A}\vee (\overline{B}\wedge \overline{C})\Leftrightarrow (\overline{A}\vee \overline{B})\wedge (\overline{A}\vee
\overline{C})
\end{eqnarray*}が成り立ちます。任意の解釈において同様の議論が成立するため、\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*}が成り立つことが示されました。つまり、述語論理においても論理積と論理和の間に分配律(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 twitter
Twitterで共有
Share on email
メールで共有
DISCUSSION

質問とコメント

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

RELATED KNOWLEDGE

関連知識

分配律
命題論理における分配律

論理積と論理和の間には分配律と呼ばれる関係が成り立ちます。つまり、論理和との論理積は論理積どうしの論理和と論理的に同値であり、論理積との論理和は論理和どうしの論理積と論理的に同値です。

述語論理