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

述語論理における同等

目次

< 前のページ
次のページ >
Share on twitter
Twitterで共有
Share on email
メールで共有

同等の解釈

論理式の定義より、論理式\(A,B\)に論理演算子\(\leftrightarrow \)を作用させることで得られる\(A\leftrightarrow B\)もまた論理式です。\(\leftrightarrow \)は同等(equivalent)と呼ばれる論理演算子であり、論理式\(A\leftrightarrow B\)を\(A\)と\(B\)の同等(equivalent of \(A\) to \(B\))と呼びます。これは「\(A\)のとき、かつそのときに限り\(B\)である(\(A\) if and only if \(B\))」という表現に対応する論理式です。

例(同等)
以下の主張\begin{equation*}
x\text{が}2\text{で割り切れるとき、かつそのときに限り}x\text{は偶数である}
\end{equation*}はどのような論理式として定式化できるでしょうか。命題関数\(P\left( x\right) ,Q\left( x\right) \)をそれぞれ、\begin{eqnarray*}P\left( x\right) &:&x\text{は}2\text{で割り切れる} \\
Q\left( x\right) &:&x\text{は偶数である}
\end{eqnarray*}とおくと、先の主張は、\begin{equation*}
P\left( x\right) \leftrightarrow Q\left( x\right)
\end{equation*}という論理式として定式化されます。

例(同等)
以下の主張\begin{equation*}
x\text{の父または母が日本人であるとき、かつそのときに限り}x\text{は日本人である}
\end{equation*}はどのような論理式として定式化できるでしょうか。命題関数\(P\left( x\right) ,Q\left( x\right) ,R\left( x\right) \)をそれぞれ、\begin{eqnarray*}P\left( x\right) &:&x\text{の父は日本人である} \\
Q\left( x\right) &:&x\text{の母や日本人である} \\
R\left( x\right) &:&x\text{は日本人である}
\end{eqnarray*}とおくと、先の主張は、\begin{equation*}
\left( P\left( x\right) \vee Q\left( x\right) \right) \leftrightarrow
R\left( x\right)
\end{equation*}という論理式として定式化されます。また、\begin{equation*}
x\text{の両親がともに日本人であるとき、かつそのときに限り}x\text{は日本人である}
\end{equation*}という主張は、\begin{equation*}
\left( P\left( x\right) \wedge Q\left( x\right) \right) \leftrightarrow
R\left( x\right)
\end{equation*}という論理式として定式化されます。

 

同等の解釈

論理式\(A\)が変数\(x,y\)の自由な現れを持つ開論理式\(A\left( x,y\right) \)であり、論理式\(B\)が変数\(y,z\)の自由な現れを持つ開論理式\(B\left( y,z\right) \)であるものとします。このとき、\(A\)と\(B\)の同等\(A\leftrightarrow B\)は変数\(x,y,z\)の自由な現れを持つ開論理式\(\left( A\leftrightarrow B\right) \left( x,y,z\right) \)であるものと定めます。開論理式の値を特定するためには解釈、すなわち以下の3つの要素\begin{eqnarray*}&&\left( a\right) \ \text{議論領域}D \\
&&\left( b\right) \ \text{論理式}A,B\text{を構成するすべての命題関数の形状} \\
&&\left( c\right) \ \text{変数の自由な現れに代入する値}\left(
\overline{x},\overline{y},\overline{z}\right)
\end{eqnarray*}を具体的に特定する必要があります。解釈を任意に選んだ上で、\(A\left( x,y\right) \)から得られる命題を\(A\left( \overline{x},\overline{y}\right) \)で、\(B\left( y,z\right) \)から得られる命題を\(B\left( \overline{y},\overline{z}\right) \)で、\(\left( A\leftrightarrow B\right) \left( x,y,z\right) \)から得られる命題を\(\left( A\leftrightarrow B\right) \left( \overline{x},\overline{y},\overline{z}\right) \)で表記します。その上で、\(\left( A\leftrightarrow B\right) \left( \overline{x},\overline{y},\overline{z}\right) \)は\(A\left( \overline{x},\overline{y}\right) \)と\(B\left( \overline{y},\overline{z}\right) \)の(命題論理における意味での)同等であるものと定めます。つまり、これら3つの命題の真理値の間には、以下の真理値表
$$\begin{array}{ccc}\hline
A\left( \overline{x},\overline{y}\right) & B\left( \overline{y},\overline{z}\right) & \left( A\leftrightarrow B\right) \left( \overline{x},\overline{y},\overline{z}\right) \\ \hline
1 & 1 & 1 \\ \hline
1 & 0 & 0 \\ \hline
0 & 1 & 0 \\ \hline
0 & 0 & 1 \\ \hline
\end{array}$$

表:同等の値

で表される関係が成り立つものと定めるということです。任意の解釈において同様に考えます。

開論理式である\(A\left( x,y\right) \)と\(B\left( y,z\right) \)に対して、議論領域および\(A\left( x,y\right) \)と\(B\left( y,z\right) \)を構成するすべての命題関数の形状が具体的に与えられている状況を想定します。あとは変数\(x,y,z\)の自由な現れに代入する値\(\overline{x},\overline{y},\overline{z}\)を指定すれば\(A\left( x,y\right) \)から命題\(A\left( \overline{x},\overline{y}\right) \)が得られ、\(B\left( y,z\right) \)から命題\(B\left( \overline{y},\overline{z}\right) \)が得られ、さらに含意\(\left( A\leftrightarrow B\right) \left( x,y,z\right) \)から命題\(\left(A\leftrightarrow B\right) \left( \overline{x},\overline{y},\overline{z}\right) \)が得られます。\(A\left( \overline{x},\overline{y}\right) \)が真になるような値の組\(\left( \overline{x},\overline{y}\right) \)からなる集合が\(A\left( x,y\right) \)の真理集合\(\phi \left(A\right) \)であり、\(B\left( \overline{y},\overline{z}\right) \)が真になるような値の組\(\left( \overline{y},\overline{z}\right) \)からなる集合が\(B\left( y,z\right) \)の真理集合\(\phi \left( B\right) \)であり、\(\left( A\leftrightarrow B\right) \left( \overline{x},\overline{y},\overline{z}\right) \)が真になるような値の組\(\left( \overline{x},\overline{y},\overline{z}\right) \)からなる集合が\(\left( A\leftrightarrow B\right) \left( x,y,z\right) \)の真理集合\(\phi \left( A\leftrightarrow B\right) \)です。同等の定義より、任意の値の組\(\left( \overline{x},\overline{y},\overline{z}\right) \in X\times Y\times Z\)に対して、\begin{equation*}\left( \overline{x},\overline{y},\overline{z}\right) \in \phi \left(
A\leftrightarrow B\right) \Leftrightarrow \left( \overline{x},\overline{y}\right) \in \phi \left( A\right) \leftrightarrow \left( \overline{y},\overline{z}\right) \in \phi \left( B\right)
\end{equation*}という関係が成り立ちます。

ここでは話を一般化するために論理式\(A\)だけが持つ変数の自由な現れ\(x\)、論理式\(B\)だけが持つ変数の自由な現れ\(z\)、そして\(A\)と\(B\)が共有する変数の自由な現れ\(y\)について考えましたが、実際には\(A\)と\(B\)が共通の変数の自由な現れだけを持っていたり、逆に、共通の変数の自由な現れを持たない場合も起こり得ます。また、\(x,y,z\)それぞれに相当する変数の自由な現れが複数存在する場合も上と同様の議論が成り立ちます。また、論理式\(A,B\)が変数の自由な現れを持たない場合、それは閉論理式であることを意味しますが、その場合にも上と同様の議論が成り立ちます。また、開論理式と閉論理式の同等や、閉論理式どうしの同等についても同様に考えます。

例(同等の解釈)
変数\(x\)の定義域\(X\)はすべての整数からなる集合であるものとします。命題関数\(P\left( x\right) \)を、\begin{equation*}x^{2}=1
\end{equation*}と定義し、命題関数\(Q\left( x\right) \)を、\begin{equation*}x>0
\end{equation*}と定義すると、同等\(\left( P\leftrightarrow Q\right) \left( x\right) \)は、\begin{equation*}x^{2}=1\leftrightarrow x>0
\end{equation*}となります。値\(x=1\)については、\(1^{2}=1\)と\(1>0\)がともに真であるため、\begin{eqnarray*}1 &\in &\phi \left( P\right) \\
1 &\in &\phi \left( Q\right) \\
1 &\in &\phi \left( P\leftrightarrow Q\right)
\end{eqnarray*}が成り立ちます。値\(x=-1\)については、\(\left( -1\right) ^{2}=1\)が真である一方で\(-1>0\)は偽であるため、\begin{eqnarray*}-1 &\in &\phi \left( P\right) \\
-1 &\not\in &\phi \left( Q\right) \\
-1 &\not\in &\phi \left( P\leftrightarrow Q\right)
\end{eqnarray*}が成り立ちます。値\(x=0\)については、\(0^{2}=1\)と\(0>0\)はともに偽であるため、\begin{eqnarray*}0 &\not\in &\phi \left( P\right) \\
0 &\not\in &\phi \left( Q\right) \\
0 &\in &\phi \left( P\leftrightarrow Q\right)
\end{eqnarray*}が成り立ちます。任意の整数\(x\in X\)について、\begin{equation*}x\in \phi \left( P\leftrightarrow Q\right) \Leftrightarrow x\in \phi \left(
P\right) \leftrightarrow x\in \phi \left( Q\right)
\end{equation*}という関係が成立します。

例(同等の解釈)
変数\(x\)の定義域\(X\)はすべての整数からなる集合であるものとします。命題関数\(P\left( x\right) \)を、\begin{equation*}x\text{は}2\text{で割り切れる}
\end{equation*}と定義し、命題関数\(Q\left( x\right) \)を、\begin{equation*}x\text{は偶数である}
\end{equation*}と定義すると、同等\(\left( P\leftrightarrow Q\right) \left( x\right) \)は、\begin{equation*}x\text{が}2\text{で割り切れるとき、かつそのときに限り}x\text{は偶数である}
\end{equation*}となります。値\(x=4\)について、\(4\)は\(2\)で割り切れるとともに偶数であるため、\begin{eqnarray*}4 &\in &\phi \left( P\right) \\
4 &\in &\phi \left( Q\right) \\
4 &\in &\phi \left( P\leftrightarrow Q\right)
\end{eqnarray*}が成り立ちます。値\(x=5\)については、\(5\)は\(2\)で割り切れず偶数でもないため、\begin{eqnarray*}5 &\not\in &\phi \left( P\right) \\
5 &\not\in &\phi \left( Q\right) \\
5 &\in &\phi \left( P\leftrightarrow Q\right)
\end{eqnarray*}が成り立ちます。任意の整数\(x\in X\)について、\begin{equation*}x\in \phi \left( P\leftrightarrow Q\right) \Leftrightarrow x\in \phi \left(
P\right) \leftrightarrow x\in \phi \left( Q\right)
\end{equation*}という関係が成立します。

例(同等の解釈)
変数\(x\)の定義域\(X\)はすべての人からなる集合であるものとします。命題関数\(P\left( x\right) \)を、\begin{equation*}x\text{の父は日本人である}
\end{equation*}と定義し、命題関数\(Q\left( x\right) \)を、\begin{equation*}x\text{の母や日本人である}
\end{equation*}と定義し、命題関数\(R\left( x\right) \)を、\begin{equation*}x\text{は日本人である}
\end{equation*}と定義すると、\begin{equation*}
x\text{の父または母が日本人であるとき、かつそのときに限り}x\text{は日本人である}
\end{equation*}という主張は、\begin{equation*}
\left( P\left( x\right) \vee Q\left( x\right) \right) \leftrightarrow
R\left( x\right)
\end{equation*}となります。\(A\)さんの父は日本人だが母は日本人ではなく、本人は日本人であるならば、\begin{eqnarray*}A &\in &\phi \left( P\right) \\
A &\not\in &\phi \left( Q\right) \\
A &\in &\phi \left( R\right) \\
A &\in &\phi \left( \left( P\vee Q\right) \leftrightarrow R\right)
\end{eqnarray*}となります。\(B\)さんの両親が日本人で本人も日本人であるならば、\begin{eqnarray*}B &\in &\phi \left( P\right) \\
B &\in &\phi \left( Q\right) \\
B &\in &\phi \left( R\right) \\
B &\in &\phi \left( \left( P\vee Q\right) \leftrightarrow R\right)
\end{eqnarray*}となります。\(C\)さんの両親は日本人ではないが本人は日本人であるならば、\begin{eqnarray*}C &\not\in &\phi \left( P\right) \\
C &\not\in &\phi \left( Q\right) \\
C &\in &\phi \left( R\right) \\
C &\not\in &\phi \left( \left( P\vee Q\right) \leftrightarrow R\right)
\end{eqnarray*}となります。

 

演習問題

問題(同等)
変数\(x\)の定義域\(X\)は、\begin{equation*}X=\left\{ 1,2,\cdots ,10\right\}
\end{equation*}であるものとします。命題関数\(P\left( x\right) \)を、\begin{equation*}x\leq 3
\end{equation*}と定義し、命題関数\(Q\left( x\right) \)を、\begin{equation*}x\text{は偶数}
\end{equation*}と定義します。このとき、\(P\left( x\right) \)および\(Q\left(x\right) \)およびそれらの同等\(\left( P\leftrightarrow Q\right) \left( x\right) \)の真理集合をそれぞれ求めてください。
解答を見る

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

問題(同等)
変数\(x\)の定義域\(X\)は、\begin{equation*}X=\left\{ 1,2,\cdots ,10\right\}
\end{equation*}であるものとします。命題関数\(P\left( x\right) \)を、\begin{equation*}x\text{は}4\text{の倍数}
\end{equation*}と定義し、命題関数\(Q\left( x\right) \)を、\begin{equation*}x\text{は偶数}
\end{equation*}と定義します。このとき、\(P\left( x\right) \)および\(Q\left(x\right) \)およびそれらの同等\(\left( P\leftrightarrow Q\right) \left( x\right) \)の真理集合をそれぞれ求めてください。
解答を見る

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

問題(同等)
変数\(x,y\)は以下の定義域\begin{equation*}X=\left\{ 1,2,3\right\}
\end{equation*}を共有しているものとします。命題関数\(P\left( x,y\right) \)を、\begin{equation*}x+y\leq 4
\end{equation*}と定義し、命題関数\(Q\left( x\right) \)を、\begin{equation*}x\leq 2
\end{equation*}と定義します。このとき、\(P\left( x,y\right) \)および\(Q\left( x\right) \)およびそれらの同等\(\left( P\leftrightarrow Q\right) \left( x,y\right) \)の真理集合をそれぞれ求めてください。
解答を見る

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

次回は全称命題の解釈について学びます。

< 前のページ
次のページ >
Share on twitter
Twitterで共有
Share on email
メールで共有
DISCUSSION

質問とコメント

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

RELATED KNOWLEDGE

関連知識

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

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

述語論理