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

分配律

論理式\(A,B,C\)がそれぞれ任意に与えられたとき、解釈を任意に選んだ上で、その場合に\(A\)から得られる命題を\(\overline{A}\)で、\(B\)から得られる命題を\(\overline{B}\)で、\(B\)から得られる命題を\(\overline{C}\)でそれぞれ表記します。すると\(\wedge \)と\(\vee \)に関する分配律より、\begin{equation*}
\overline{A}\wedge (\overline{B}\vee \overline{C})\Leftrightarrow (\overline{A}\wedge \overline{B})\vee (\overline{A}\wedge \overline{C})
\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
< 前のページ
次のページ >

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

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

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

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

本サイトは 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 ファイルの添付も可能です。

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

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

述語論理