WIIS

述語論理

述語論理における否定

目次

前のページ:

命題関数の解釈

Mailで保存
Xで共有

否定

論理式の定義より、論理式\(A\)に論理演算子\(\lnot \)を作用させることにより得られる、\begin{equation*}\lnot A
\end{equation*}もまた論理式です。\(\lnot \)は否定(negation)と呼ばれる論理演算子であり、論理式\(\lnot A\)を\(A\)の否定(negation of \(A\))と呼びます。これは「\(A\)ではない(not \(A\))」という表現に対応する論理式です。

例(否定)
「\(x\)は素数ではない」という言明を定式化するとき、命題関数\(P\left( x\right) \)を、\begin{equation*}P\left( x\right) :x\text{は素数ではない}
\end{equation*}とおいたのでは「〜ではない」という表現を上手く表現できていません。そこで、命題関数\(Q\left( x\right) \)を、\begin{equation*}Q\left( x\right) :x\text{は素数である}
\end{equation*}とおいた上で、言明を、\begin{equation*}
\lnot Q\left( x\right) :x\text{は素数ではない}
\end{equation*}と表現するほうが望ましいです。

例(否定)
命題関数\(P\left( x\right) ,Q\left( y\right) ,R\left(x,y\right) \)をそれぞれ、\begin{eqnarray*}P\left( x\right) &:&x\text{は偶数である}
\\
Q\left( y\right) &:&y\text{は奇数である}
\\
R\left( x,y\right) &:&x+y\text{は奇数である}
\end{eqnarray*}と定義するとき、これらの否定は、\begin{eqnarray*}
\lnot P\left( x\right) &:&x\text{は偶数ではない} \\
\lnot Q\left( y\right) &:&y\text{は奇数ではない} \\
\lnot R\left( x,y\right) &:&x+y\text{は奇数ではない}
\end{eqnarray*}などとなります。

例(否定)
命題関数\(P\left( x,y\right) ,Q\left( x,y\right) \)をそれぞれ、\begin{eqnarray*}P\left( x,y\right) &:&x\text{は}y\text{の夫である} \\
Q\left( x,y\right) &:&y\text{は}x\text{の妻である}
\end{eqnarray*}と定義するとき、これらの否定は、\begin{eqnarray*}
\lnot P\left( x,y\right) &:&x\text{は}y\text{の夫ではない} \\
\lnot Q\left( x,y\right) &:&y\text{は}x\text{の妻ではない}
\end{eqnarray*}などとなります。

 

否定の解釈

論理式\(A\)が与えられたとき、その否定\(\lnot A\)もまた論理式です。論理式の値を特定するためには何らかの解釈を与える必要があります。解釈が与えられたとき、その解釈のもとで\(A\)から得られる命題を\(\overline{A}\)で表記し、同じ解釈のもとで\(\lnot A\)から得られる命題を\(\lnot \overline{A}\)で表記します。その上で、任意の解釈のもとで\(\lnot \overline{A}\)は\(\overline{A}\)の否定であるものと定めます。つまり、解釈を任意に選んだとき、以下の真理値表

$$\begin{array}{cc}
\hline
\overline{A} & \lnot \overline{A} \\ \hline
1 & 0 \\ \hline
0 & 1 \\ \hline
\end{array}$$

で表される関係が成り立つものとして否定\(\lnot \)を定義するということです。

以上が述語論理における否定の定義です。定義を踏まえた上で、以下では、論理式\(A\)が開論理式である場合や閉論理式である場合など様々なケースにおいて、その否定\(\lnot A\)がどのようなものになるのかを整理するとともに具体例を提示します。

 

開論理式の否定

変数\(x\)の自由な現れを持つ開論理式\(A\left( x\right) \)が与えられたとき、その否定\(\lnot A\left( x\right) \)もまた変数\(x\)の自由な現れを持つ開論理式です。これらの開論理式の値を特定するためには解釈、すなわち以下の3つの要素\begin{eqnarray*}&&\left( a\right) \ \text{議論領域(}x\text{の定義域)} \\
&&\left( b\right) \ \text{論理式}A\text{を構成するすべての命題関数の形状} \\
&&\left( c\right) \ \text{変数}x\text{の自由な現れに代入する値}\overline{x}
\end{eqnarray*}を具体的に特定する必要がありますが、否定の定義より、解釈としてどのようなものを選んだ場合においても、\(\lnot A\left( x\right) \)から得られる命題は\(A\left(x\right) \)から得られる命題の否定になります。つまり、解釈を任意に選んだ上で、その解釈のもとで\(A\left( x\right) \)から得られる命題を\(\overline{A}\left( \overline{x}\right) \)で表記し、同じ解釈のもとで\(\lnot A\left(x\right) \)から得られる命題を\(\lnot \overline{A}\left( \overline{x}\right) \)で表記するとき、この2つの命題の真理値の間には、以下の真理値表

$$\begin{array}{cc}
\hline
\overline{A}\left( \overline{x}\right) & \lnot \overline{A}\left( \overline{x}\right) \\ \hline
1 & 0 \\ \hline
0 & 1 \\ \hline
\end{array}$$

で表される関係が常に成り立つということです。

例(否定の解釈)
変数\(x\)の定義域\(X\)は、\begin{equation*}X=\left\{ 1,2,3\right\}
\end{equation*}であるものとします。命題関数\(P\left( x\right) \)を、\begin{equation*}P\left( x\right) :x^{2}=1
\end{equation*}と定めると、その否定\(\lnot P\left( x\right) \)は、\begin{equation*}\lnot P\left( x\right) :x^{2}\not=1
\end{equation*}となります。変数\(x\)の自由な表れに値\(1\in X\)を代入すると以下の命題\begin{eqnarray*}P\left( 1\right) &:&1^{2}=1 \\
\lnot P\left( 1\right) &:&1^{2}\not=1
\end{eqnarray*}が得られますが、\(P\left(1\right) \)は真である一方で\(\lnot P\left( 1\right) \)は偽です。また、値\(2\in X\)を代入すると以下の命題\begin{eqnarray*}P\left( 2\right) &:&2^{2}=1 \\
\lnot P\left( 2\right) &:&2^{2}\not=1
\end{eqnarray*}が得られますが、\(P\left(2\right) \)は偽である一方で\(\lnot P\left( 2\right) \)は真です。
例(否定の解釈)
変数\(x\)の定義域\(X\)は、\begin{equation*}X=\left\{ \text{茨城},\text{栃木},\text{群馬},\text{埼玉},\text{千葉},\text{東京},\text{神奈川}\right\}
\end{equation*}であるものとします。命題関数\(P\left( x\right) \)を、\begin{equation*}P\left( x\right) :x\text{の人口は}800\text{万人以上}
\end{equation*}と定めると、その否定\(\lnot P\left( x\right) \)は、\begin{equation*}\lnot P\left( x\right) :x\text{の人口は}800\text{万人未満}
\end{equation*}となります。変数\(x\)の自由な表れに値「東京」を代入すると以下の命題\begin{eqnarray*}P\left( \text{東京}\right) &:&\text{東京の人口は}800\text{万人以上} \\
\lnot P\left( \text{東京}\right) &:&\text{東京の人口は}800\text{万人未満}
\end{eqnarray*}が得られますが、\(P\left( \text{東京}\right) \)は真である一方で\(\lnot P\left( \text{東京}\right) \)は偽です。また、値「茨城」を代入すると以下の命題\begin{eqnarray*}P\left( \text{茨城}\right) &:&\text{茨城の人口は}800\text{万人以上} \\
\lnot P\left( \text{茨城}\right) &:&\text{茨城の人口は}800\text{万人未満}
\end{eqnarray*}が得られますが、\(P\left( \text{茨城}\right) \)は偽である一方で\(\lnot P\left( \text{茨城}\right) \)は偽です。

同じことを真理集合を用いて表現すると以下のようになります。

命題(否定の真理集合)

変数\(x\)の自由な現れを持つ開論理式\(A\left( x\right) \)が与えられているものとする。\(x\)の定義域\(X\)および\(A\left( x\right) \)を構成するすべての命題関数の形状を任意に選んだ上で、その場合に\(A\left( x\right) \)から得られる開論理式を\(\overline{A}\left( x\right) \)で表記し、否定\(\lnot A\left( x\right) \)から得られる開論理式を\(\lnot \overline{A}\left( x\right) \)で表記する。\(\overline{A}\left( x\right) \)の真理集合を\(\phi \left( \overline{A}\right) \)で表記し、\(\lnot \overline{A}\left( x\right) \)の真理集合を\(\phi \left( \overline{A}\right) \)で表記する。その上で、変数\(x\)の自由な現れに代入する値\(\overline{x}\in X\)を任意に選んだとき、以下の関係\begin{equation*}\overline{x}\in \phi \left( \lnot \overline{A}\right) \Leftrightarrow
\overline{x}\not\in \phi \left( \overline{A}\right)
\end{equation*}が成り立つ。

証明

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

例(否定の真理集合)
変数\(x\)の定義域\(X\)は、\begin{equation*}X=\left\{ 1,2,3\right\}
\end{equation*}であるものとします。命題関数\(P\left( x\right) \)を、\begin{equation*}P\left( x\right) :x^{2}=1
\end{equation*}と定めると、その否定\(\lnot P\left( x\right) \)は、\begin{equation*}\lnot P\left( x\right) :x^{2}\not=1
\end{equation*}となります。これらの真理集合は、\begin{eqnarray*}
\phi \left( P\right) &=&\left\{ 1\right\} \\
\phi \left( \lnot P\right) &=&\left\{ 2,3\right\}
\end{eqnarray*}です。任意の値\(x\in X\)について、以下の関係\begin{equation*}x\in \phi \left( \lnot P\right) \Leftrightarrow x\not\in \phi \left( P\right)
\end{equation*}が成立しています。

例(否定の真理集合)
変数\(x\)の定義域\(X\)は、\begin{equation*}X=\left\{ \text{茨城},\text{栃木},\text{群馬},\text{埼玉},\text{千葉},\text{東京},\text{神奈川}\right\}
\end{equation*}であるものとします。命題関数\(P\left( x\right) \)を、\begin{equation*}P\left( x\right) :x\text{の人口は}800\text{万人以上}
\end{equation*}と定めると、その否定\(\lnot P\left( x\right) \)は、\begin{equation*}\lnot P\left( x\right) :x\text{の人口は}800\text{万人未満}
\end{equation*}となります。これらの真理集合は、\begin{eqnarray*}
\phi \left( P\right) &=&\left\{ \text{東京},\text{神奈川}\right\} \\
\phi \left( \lnot P\right) &=&\left\{ \text{茨城},\text{栃木},\text{群馬},\text{埼玉},\text{千葉}\right\}
\end{eqnarray*}です。任意の値\(x\in X\)について、以下の関係\begin{equation*}x\in \phi \left( \lnot P\right) \Leftrightarrow x\not\in \phi \left( P\right)
\end{equation*}が成立しています。

開論理式が複数の変数の自由な現れを持つ場合にも同様に考えます。

変数\(x,y\)の自由な現れを持つ開論理式\(A\left( x,y\right) \)が与えられたとき、その否定\(\lnot A\left( x,y\right) \)もまた変数\(x,y\)の自由な現れを持つ開論理式です。これらの開論理式の値を特定するためには解釈、すなわち以下の3つの要素\begin{eqnarray*}&&\left( a\right) \ \text{議論領域(}x,y\text{の定義域)} \\
&&\left( b\right) \ \text{論理式}A\text{を構成するすべての命題関数の形状} \\
&&\left( c\right) \ \text{変数}x,y\text{の自由な現れに代入する値}\overline{x},\overline{y}
\end{eqnarray*}を具体的に特定する必要がありますが、否定の定義より、解釈としてどのようなものを選んだ場合においても、\(\lnot A\left( x,y\right) \)から得られる命題は\(A\left(x,y\right) \)から得られる命題の否定になります。つまり、解釈を任意に選んだ上で、その解釈のもとで\(A\left( x,y\right) \)から得られる命題を\(\overline{A}\left( \overline{x},\overline{y}\right) \)で表記し、同じ解釈のもとで\(\lnot A\left( x,y\right) \)から得られる命題を\(\lnot \overline{A}\left( \overline{x},\overline{y}\right) \)で表記するとき、この2つの命題の真理値の間には、以下の真理値表

$$\begin{array}{cc}
\hline
\overline{A}\left( \overline{x},\overline{y}\right) & \lnot \overline{A}\left( \overline{x},\overline{y}\right) \\ \hline
1 & 0 \\ \hline
0 & 1 \\ \hline
\end{array}$$

で表される関係が常に成り立つということです。

例(否定の解釈)
変数\(x,y\)の定義域\(X,Y\)は、\begin{equation*}X=Y=\left\{ 1,2\right\}
\end{equation*}であるものとします。命題関数\(P\left( x,y\right) \)を、\begin{equation*}P\left( x,y\right) :x+y\leq 3
\end{equation*}と定めると、その否定\(\lnot P\left( x,y\right) \)は、\begin{equation*}\lnot P\left( x,y\right) :x+y>3
\end{equation*}となります。変数\(x,y\)の自由な表れに値\(1,2\)をそれぞれ代入すると以下の命題\begin{eqnarray*}P\left( 1,2\right) &:&1+2\leq 3 \\
\lnot P\left( 1,2\right) &:&1+2>3
\end{eqnarray*}が得られますが、\(P\left(1,2\right) \)は真である一方で\(\lnot P\left( 1,2\right) \)は偽です。

同じことを真理集合を用いて表現すると以下のようになります。

命題(否定の真理集合)

変数\(x,y\)の自由な現れを持つ開論理式\(A\left( x,y\right) \)が与えられているものとする。\(x,y\)の定義域\(X,Y\)および\(A\left( x,y\right) \)を構成するすべての命題関数の形状を任意に選んだ上で、その場合に\(A\left( x,y\right) \)から得られる論理式を\(\overline{A}\left( x,y\right) \)で表記し、否定\(\lnot A\left( x,y\right) \)から得られる論理式を\(\lnot \overline{A}\left( x,y\right) \)で表記する。\(\overline{A}\left( x\right) \)の真理集合を\(\phi \left( \overline{A}\right) \)で表記し、\(\lnot \overline{A}\left( x\right) \)の真理集合を\(\phi \left( \overline{A}\right) \)で表記する。その上で、変数\(x,y\)の自由な現れに代入する値からなる組\(\left( \overline{x},\overline{y}\right) \in X\times Y\)を任意に選んだとき、\begin{equation*}\left( \overline{x},\overline{y}\right) \in \phi \left( \lnot \overline{A}\right) \Leftrightarrow \left( \overline{x},\overline{y}\right) \not\in \phi
\left( \overline{A}\right)
\end{equation*}という関係が成り立つ。

証明

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

例(否定の真理集合)
変数\(x,y\)の定義域\(X,Y\)は、\begin{equation*}X=Y=\left\{ 1,2\right\}
\end{equation*}であるものとします。命題関数\(P\left( x,y\right) \)を、\begin{equation*}P\left( x,y\right) :x+y\leq 3
\end{equation*}と定めると、その否定\(\lnot P\left( x,y\right) \)は、\begin{equation*}\lnot P\left( x,y\right) :x+y>3
\end{equation*}となります。これらの真理集合は、\begin{eqnarray*}
\phi \left( P\right) &=&\left\{ \left( 1,1\right) ,\left( 1,2\right)
,\left( 2,1\right) \right\} \\
\phi \left( \lnot P\right) &=&\left\{ \left( 2,2\right) \right\}
\end{eqnarray*}です。任意の値の組\(\left( x,y\right) \in X\times Y\)について、以下の関係\begin{equation*}\left( x,y\right) \in \phi \left( \lnot P\right) \Leftrightarrow \left(
x,y\right) \not\in \phi \left( P\right)
\end{equation*}が成立しています。

有限\(n\)個の変数\(x_{1},\cdots ,x_{n}\)の自由な現れを持つ開論理式\(A\left( x_{1},\cdots ,x_{n}\right) \)の否定についても同様に考えます。

例(否定の解釈と真理集合)
変数\(x,y,z\)の定義域\(X,Y,Z\)は、\begin{equation*}X=Y=Z=\left\{ 1,2\right\}
\end{equation*}であるものとします。命題関数\(P\left( x,y,z\right) \)を、\begin{equation*}P\left( x,y,z\right) :x+y+z=3
\end{equation*}と定めると、その否定\(\lnot P\left( x,y,z\right) \)は、\begin{equation*}\lnot P\left( x,y,z\right) :x+y+z\not=3
\end{equation*}となります。これらの真理集合は、\begin{eqnarray*}
\phi \left( P\right) &=&\left\{ \left( 1,1,1\right) \right\} \\
\phi \left( \lnot P\right) &=&\left\{ \left( 1,1,2\right) ,\left(
1,2,1\right) ,\left( 2,1,1\right) ,\left( 1,2,2\right) ,\left( 2,1,1\right)
,\left( 2,2,1\right) ,\left( 2,2,2\right) \right\}
\end{eqnarray*}です。任意の値の組\(\left( x,y,z\right) \in X\times Y\times Z\)について、以下の関係\begin{equation*}\left( x,y,z\right) \in \phi \left( \lnot P\right) \Leftrightarrow \left(
x,y,z\right) \not\in \phi \left( P\right)
\end{equation*}が成立しています。

 

閉論理式の否定の解釈

変数の自由な現れを持たない閉論理式\(A\)が与えられたとき、その否定\(\lnot A\)もまた閉論理式です。これらの閉論理式の値を特定するためには解釈、すなわち以下の2つの要素\begin{eqnarray*}&&\left( a\right) \ \text{議論領域} \\
&&\left( b\right) \ \text{論理式}A\text{を構成するすべての命題関数の形状}
\end{eqnarray*}を具体的に特定する必要があります。否定の定義より、解釈としてどのようなものを選んだ場合においても、\(\lnot A\)から得られる命題は\(A\)から得られる命題の否定になります。つまり、解釈を任意に選んだ上で、\(A\)から得られる命題を\(\overline{A}\)で表記し、\(\lnot A\)から得られる命題を\(\lnot \overline{A}\)で表記するとき、この2つの命題の真理値の間には、以下の真理値表

$$\begin{array}{cc}
\hline
\overline{A} & \lnot \overline{A} \\ \hline
1 & 0 \\ \hline
0 & 1 \\ \hline
\end{array}$$

で表される関係が常に成り立つということです。

例(否定の解釈)
変数\(x\)の定義域\(X\)はすべての実数からなる集合であるものとします。命題関数\(P\left( x\right) \)を、\begin{equation*}P\left( x\right) :x^{2}\geq 0
\end{equation*}と定めた上で、以下の論理式\begin{equation*}
\forall x\in X:P\left( x\right)
\end{equation*}すなわち、\begin{equation}
\forall x\in X:x^{2}\geq 0 \quad \cdots (1)
\end{equation}を定義します。これは閉論理式です。その否定は、\begin{equation}
\lnot \left( \forall x\in X:x^{2}\geq 0\right) \quad \cdots (2)
\end{equation}となります。否定の定義より、\(\left( 1\right) \)と\(\left(2\right) \)の真理値は逆転します。詳細は後述しますが、\(\left( 1\right) \)が真である一方で\(\left( 2\right) \)は偽です。

 

演習問題

問題(否定の解釈)
変数\(x\)の定義域\(X\)はすべての自然数からなる集合であるものとします。命題関数\(P\left(x\right) \)を、\begin{equation*}x<3
\end{equation*}と定義したとき、その否定\(\lnot P\left( x\right) \)の真理集合を求めてください。
解答を見る

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

問題(否定の解釈)
変数\(x,y\)の定義域\(X,Y\)はともに\(1\)以上\(3\)以下の自然数からなる集合\(\left\{1,2,3\right\} \)であるものとします。命題関数\(P\left( x,y\right) \)を、\begin{equation*}x+y\text{は奇数である}
\end{equation*}と定義したとき、その否定\(\lnot P\left( x,y\right) \)の真理集合を求めてください。
解答を見る

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

問題(否定の解釈)
変数\(x\)の定義域は、\begin{equation*}X=\left\{ x_{1},x_{2},x_{3}\right\}
\end{equation*}であり、これはある組織のメンバーからなる集合であるものとします。変数\(y\)の定義域は、\begin{equation*}Y=\left\{ y_{1},y_{2},y_{3}\right\}
\end{equation*}であり、これは別の組織のメンバーからなる集合であるものとします。命題変数\(P\left( x,y\right) \)を、\begin{equation*}x\text{と}y\text{は知り合いである}
\end{equation*}と定義します。\(x_{1}\)は\(y_{1} \)と知り合いであり、\(x_{2}\)は\(y_{1}\)および\(y_{3}\)と知り合いであり、\(x_{3}\)は自分と別の組織に知り合いがいません。否定\(\lnot P\left( x,y\right) \)の真理集合を求めてください。
解答を見る

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

問題(否定の解釈)
論理式の定義より、命題関数\(P\left( x\right) \)の否定\(\lnot \)は論理式であるため、さらにその否定\(\lnot \left( \lnot P\left( x\right) \right) \)もまた論理式です。これを\(\lnot \lnot P\left( x\right) \)と表記します。このとき、\begin{equation*}\phi \left( P\right) =\phi \left( \lnot \lnot P\right)
\end{equation*}という関係が成り立つことを証明してください。

解答を見る

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

関連知識

前のページ:

命題関数の解釈

Mailで保存
Xで共有

質問とコメント

プレミアム会員専用コンテンツです

会員登録

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

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

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

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