WIIS

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

述語論理における否定

目次

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

否定

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

例(否定)
以下の主張\begin{equation*}
x\text{は素数ではない}
\end{equation*}をどのような論理式として定式化できるでしょうか。命題関数\(P\left( x\right) \)を、\begin{equation*}P\left( x\right) :x\text{は素数ではない}
\end{equation*}と定義したのでは「ではない」というニュアンスを上手く表現できていません。そこで、命題関数\(P\left(x\right) \)を改めて、\begin{equation*}P\left( x\right) :x\text{は素数である}
\end{equation*}と定義すれば、\begin{equation*}
\lnot P\left( x\right) :x\text{は素数ではない}
\end{equation*}となり、この論理式であれば否定\(\lnot \)を用いて「ではない」というニュアンスを表現できているため、こちらの方が望ましい定式化です。
例(否定)
命題関数\(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\)が変数\(x\)の自由な現れを持つ開論理式\(A\left( x\right) \)であるとき、その否定\(\lnot A\)もまた変数\(x\)の自由な現れを持つ開論理式\(\lnot A\left( x\right) \)であるものと定めます。開論理式の値を特定するためには解釈、すなわち以下の3つの要素\begin{eqnarray*}&&\left( a\right) \ \text{議論領域} \\
&&\left( b\right) \ \text{論理式}A\text{を構成するすべての命題関数の形状} \\
&&\left( c\right) \ \text{変数}x\text{の自由な現れに代入する値}\overline{x}
\end{eqnarray*}を具体的に特定する必要があります。解釈を任意に選んだ上で、\(A\left( x\right) \)から得られる命題を\(A\left( \overline{x}\right) \)で表記し、\(\lnot A\left( x\right) \)から得られる命題を\(\lnot A\left( \overline{x}\right) \)で表記します。その上で、\(\lnot A\left( \overline{x}\right) \)は\(A\left( \overline{x}\right) \)の(命題論理における意味での)否定であるものと定めます。つまり、この2つの命題の真理値の間には、以下の真理値表
$$\begin{array}{cc}\hline
A\left( \overline{x}\right) & \lnot A\left( \overline{x}\right) \\
\hline
1 & 0 \\ \hline
0 & 1 \\ \hline
\end{array}$$

表:否定の値

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

開論理式\(A\)に対して、議論領域および\(A\)を構成するすべての命題関数の形状が具体的に与えられている状況を想定します。あとは変数\(x\)の自由な現れに代入する値\(\overline{x}\)を指定すれば\(A\left( x\right) \)から命題\(A\left( \overline{x}\right) \)が得られ、\(\lnot A\left( x\right) \)から命題\(\lnot A\left( \overline{x}\right) \)が得られます。\(A\left( \overline{x}\right) \)が真になるような値\(\overline{x}\)からなる集合が\(A\left( x\right) \)の真理集合\(\phi \left( A\right) \)であり、\(\lnot A\left( \overline{x}\right) \)が真になるような値\(\overline{x}\)からなる集合が\(\lnot A\left(x\right) \)の真理集合\(\phi \left( \lnot A\right) \)です。否定の定義より、任意の値\(\overline{x}\in X\)に対して、\begin{equation*}\lnot A\left( \overline{x}\right) \text{は真}\Leftrightarrow
A\left( \overline{x}\right) \text{は偽}
\end{equation*}という関係が成り立ちますが、真理集合を用いてこれを表現すると、\begin{equation*}
\overline{x}\in \phi \left( \lnot A\right) \Leftrightarrow \overline{x}\not\in \phi \left( A\right)
\end{equation*}となります。つまり、値\(\overline{x}\)が否定\(\lnot A\)の真理集合の要素であることと、その値\(\overline{x}\)がもとの開論理式\(A\)の真理集合の要素でないことは必要十分です。

複数の変数\(x_{1},\cdots ,x_{n}\)を持つ開論理式\(A\left( x_{1},\cdots ,x_{n}\right) \)の否定についても同様に考えます。また、閉論理式\(A\)の否定についても同様に考えます。

例(否定の解釈)
変数\(x\)の定義域\(X\)は、\begin{equation*}X=\left\{ 1,2,3\right\}
\end{equation*}であるものとします。命題関数\(P\left( x\right) \)を、\begin{equation*}x^{2}=1
\end{equation*}と定義すると、その真理集合は、\begin{equation*}
\phi \left( P\right) =\left\{ 1\right\}
\end{equation*}となります。一方、否定\(\lnot P\left( x\right) \)は、\begin{equation*}x^{2}\not=1
\end{equation*}であり、その真理集合は、\begin{equation*}
\phi \left( \lnot P\right) =\left\{ 2,3\right\}
\end{equation*}となります。任意の値\(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*}x\text{の人口は}800\text{万人以上}
\end{equation*}と定義すると、その真理集合は、\begin{equation*}
\phi \left( P\right) =\left\{ \text{東京},\text{神奈川}\right\}
\end{equation*}となります。一方、否定\(\lnot P\left( x\right) \)は、\begin{equation*}x\text{の人口は}800\text{万人未満}
\end{equation*}であり、その真理集合は、\begin{equation*}
\phi \left( \lnot P\right) =\left\{ \text{茨城},\text{栃木},\text{群馬},\text{埼玉},\text{千葉}\right\}
\end{equation*}となります。任意の値\(x\in X\)について、\begin{equation*}x\in \phi \left( \lnot P\right) \Leftrightarrow x\not\in \phi \left(
P\right)
\end{equation*}という関係が成立しています。

例(否定の真理集合)
変数\(x,y\)の定義域\(X,Y\)は、\begin{equation*}X=Y=\left\{ 1,2\right\}
\end{equation*}であるものとします。変数\(P\left( x,y\right) \)を、\begin{equation*}x+y\leq 3
\end{equation*}と定義すると、その真理集合は、\begin{equation*}
\phi \left( P\right) =\left\{ \left( 1,1\right) ,\left( 1,2\right) ,\left(
2,1\right) \right\}
\end{equation*}となります。一方、否定\(\lnot P\left( x\right) \)は、\begin{equation*}x+y>3
\end{equation*}であり、その真理集合は、\begin{equation*}
\phi \left( \lnot P\right) =\left\{ \left( 2,2\right) \right\}
\end{equation*}となります。任意の値の組\(\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*}という関係が成立しています。

 

演習問題

問題(否定)
変数\(x\)の定義域\(X\)はすべての自然数からなる集合であるものとします。命題関数\(P\left(x\right) \)を、\begin{equation*}x<3
\end{equation*}と定義したとき、その否定\(\lnot P\left( x\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*}という関係が成り立つことを証明してください。

解答を見る

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

次回は論理積の解釈について解説します。

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

関連知識

否定
命題論理における否定

否定は入力された論理式に対して、それとは逆の値をとる論理式を出力する論理演算です。

余事象
余事象

事象 A の補集合として定義される事象を A の余事象と呼びます。これは「事象 A が起こらない」という現象に相当する事象です。

差集合
補集合

集合 A に属さない要素からなる集合を A の補集合と呼びます。集合 A が命題関数 P(x) から内包的に定義されるとき、A の補集合とは、命題 P(x) が偽になるような要素 x からなる集合です。

否定
命題論理における否定除去

論理式 A とその否定 ¬A がともに真である場合には恒偽式が導かれます。これは否定除去と呼ばれる推論規則です。

否定
命題論理における否定導入

論理式 A から恒偽式が導かれる場合には ¬A は必ず真になります。これは否定導入と呼ばれる推論規則です。否定導入は背理法と呼ばれる証明方法の根拠になります。

前件否定
命題論理における後件否定

論理式 A,B について、「AならばB」と「Bではない」という前提から「Aではない」という結論を導く推論規則を後件否定やモーダストレンスなどと呼びます。

補集合
補集合法則

ある集合とその補集合の共通部分は空集合になります。また、ある集合とその補集合の和集合は全体集合になります。これを補集合法則と呼びます。

二重否定
二重補集合の法則

集合の補集合は集合であるため、さらにその補集合をとることができます。そして、この集合はもとの集合と等しいことが保証されます。補集合が満たすこのような性質を二重補集合の法則と呼びます。

DISCUSSION

質問とコメント

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

述語論理