恒真式・恒偽式・事実式

述語論理において論理式が恒真式であるとは、任意の解釈においてその論理式の値が真であることを意味します。また、論理式が恒偽式であるとは、任意の解釈においてその論理式の値が偽であることを意味します。恒真式や恒偽式ではない論理式を事実式と呼びます。

恒真式

任意の解釈において、論理式から得られる命題の値が真である場合、その論理式を恒真式(tautology)やトートロジー(tautology)などと呼びます。恒真式を表す記号を\(\top \)と定めます。命題定数\(T\)は論理式ですから、これもまた恒真式です。

論理式\(A\)が変数の自由な現れを持たない閉論理式である場合、その解釈とは以下の2つの要素\begin{eqnarray*}
&&\left( a\right) \ \text{議論領域}D \\
&&\left( b\right) \ \text{論理式}A\text{を構成するすべての命題関数の形状}
\end{eqnarray*}の組のことであり、解釈を与えれば\(A\)から1つの命題が得られます。したがって、閉論理式\(A\)が恒真式であるとは、任意の解釈において、\(A\)から得られる命題が真であることを意味します。

例(恒真な閉論理式)
変数\(x\in X\)に関する命題関数\(P\left( x\right) \)を被演算子とする以下の閉論理式\begin{equation}
\left( \exists x\in X:\lnot P\left( x\right) \right) \leftrightarrow \lnot
\left( \forall x\in X:P\left( x\right) \right) \tag{1}
\end{equation}について考えます。量化記号\(\forall ,\exists \)の定義より、上の論理式は、\begin{equation}
\bigvee\limits_{x\in X}\lnot P\left( x\right) \leftrightarrow \lnot \left(
\bigwedge\limits_{x\in X}P\left( x\right) \right) \tag{2}
\end{equation}と変形可能です。ド・モルガンの法則より、これはさらに、\begin{equation}
\bigvee\limits_{x\in X}\lnot P\left( x\right) \leftrightarrow
\bigvee\limits_{x\in X}\lnot P\left( x\right) \tag{3}
\end{equation}と変形可能です。\(\left( 3\right) \)において\(\leftrightarrow \)の左右の論理式は等しいため、\(\leftrightarrow \)の定義より、変数\(x\)の定義域\(X\)や命題関数\(P\left( x\right) \)の形状によらず\(\left( 3\right) \)は真です。したがって、\(\left( 3\right) \)やその言い換えである\(\left( 2\right) \)や\(\left( 1\right) \)は恒真式です。

論理式\(A\)が変数\(x_{1},\cdots ,x_{n}\)の自由な現れを持つ開論理式\(A\left( x_{1},\cdots ,x_{n}\right) \)である場合、その解釈とは以下の3つの要素\begin{eqnarray*}
&&\left( a\right) \ \text{議論領域}D \\
&&\left( b\right) \ \text{論理式}A\text{を構成するすべての命題関数の形状} \\
&&\left( c\right) \ \text{変数の自由な現れに代入する値}\overline{x}_{1},\cdots ,\overline{x}_{n}
\end{eqnarray*}の組のことであり、解釈を与えれば\(A\left( x_{1},\cdots ,x_{n}\right) \)から1つの命題が得られます。したがって、開論理式\(A\left( x_{1},\cdots ,x_{n}\right) \)が恒真式であることとは、任意の解釈において、\(A\left( x_{1},\cdots ,x_{n}\right) \)から得られる命題が真であることを意味します。

例(恒真な開論理式)
変数\(x\in X\)に関する命題関数\(P\left( x\right) \)と\(Q\left( x\right) \)を被演算子とする以下の開論理式\begin{equation}
P\left( x\right) \wedge Q\left( x\right) \rightarrow P\left( x\right)
\tag{1}
\end{equation}について考えます。解釈を任意に選んだ上で、そのときに\(P\left( x\right) \)から得られる命題を\(P\left( \overline{x}\right) \)で、\(Q\left( x\right) \)から得られる命題を\(Q\left( \overline{x}\right) \)でそれぞれ表記すると、\(\left( 1\right) \)から得られる命題は、\begin{equation*}
P\left( \overline{x}\right) \wedge Q\left( \overline{x}\right) \rightarrow
P\left( \overline{x}\right)
\end{equation*}となります。これを同値変形すると、\begin{eqnarray*}
P\left( \overline{x}\right) \wedge Q\left( \overline{x}\right) \rightarrow
P\left( \overline{x}\right) &\Leftrightarrow &\lnot \left( P\left(
\overline{x}\right) \wedge Q\left( \overline{x}\right) \right) \vee P\left(
\overline{x}\right) \quad \because \rightarrow \text{の言い換え} \\
&\Leftrightarrow &\left( \lnot P\left( \overline{x}\right) \vee \lnot
Q\left( \overline{x}\right) \right) \vee P\left( \overline{x}\right) \quad
\because \text{ド・モルガンの法則} \\
&\Leftrightarrow &\left( P\left( \overline{x}\right) \vee \lnot P\left(
\overline{x}\right) \right) \vee \lnot Q\left( \overline{x}\right) \quad
\because \text{交換律} \\
&\Leftrightarrow &\top \vee \lnot Q\left( \overline{x}\right) \quad \because
\text{排中律} \\
&\Leftrightarrow &\top \quad \because \text{恒真式}\top
\text{の性質}
\end{eqnarray*}すなわち恒真式\(\top \)となります。任意の解釈のもとで同様の議論が成り立つため、\(\left( 1\right) \)が恒真式であることが明らかになりました。

 

恒偽式

任意の解釈において、論理式から得られる命題の値が偽である場合、その論理式を恒偽式(contradictory)などと呼びます。恒偽式を表す記号を\(\bot \)と定めます。命題定数\(F\)は論理式ですから、これもまた恒偽式です。

繰り返しになりますが、論理式\(A\)が変数の自由な現れを持たない閉論理式である場合、その解釈とは以下の2つの要素\begin{eqnarray*}
&&\left( a\right) \ \text{議論領域}D \\
&&\left( b\right) \ \text{論理式}A\text{を構成するすべての命題関数の形状}
\end{eqnarray*}の組のことであり、解釈を与えれば\(A\)から1つの命題が得られます。したがって、閉論理式\(A\)が恒偽式であるとは、任意の解釈において、\(A\)から得られる命題が偽であることを意味します。

例(恒偽な閉論理式)
変数\(x\in X\)に関する命題関数\(P\left( x\right) \)を被演算子とする以下の閉論理式\begin{equation}
\left( \exists x\in X:\lnot P\left( x\right) \right) \leftrightarrow \left(
\forall x\in X:P\left( x\right) \right) \tag{1}
\end{equation}について考えます。量化記号\(\forall ,\exists \)の定義より、上の論理式は、\begin{equation}
\bigvee\limits_{x\in X}\lnot P\left( x\right) \leftrightarrow \left(
\bigwedge\limits_{x\in X}P\left( x\right) \right) \tag{2}
\end{equation}と変形可能です。ド・モルガンの法則より、これはさらに、\begin{equation}
\lnot \left( \bigwedge\limits_{x\in X}P\left( x\right) \right)
\leftrightarrow \left( \bigwedge\limits_{x\in X}P\left( x\right) \right)
\tag{3}
\end{equation}と変形可能です。\(\left( 3\right) \)において\(\leftrightarrow \)の左右の論理式の一方は他方の否定であるため、\(\leftrightarrow \)の定義より、変数\(x\)の定義域\(X\)や命題関数\(P\left( x\right) \)の形状によらず\(\left( 3\right) \)は偽です。したがって、\(\left( 3\right) \)やその言い換えである\(\left( 2\right) \)や\(\left( 1\right) \)は恒偽式です。

繰り返しになりますが、論理式\(A\)が変数\(x_{1},\cdots ,x_{n}\)の自由な現れを持つ開論理式\(A\left( x_{1},\cdots ,x_{n}\right) \)である場合、その解釈とは以下の3つの要素\begin{eqnarray*}
&&\left( a\right) \ \text{議論領域}D \\
&&\left( b\right) \ \text{論理式}A\text{を構成するすべての命題関数の形状} \\
&&\left( c\right) \ \text{変数の自由な現れに代入する値}\overline{x}_{1},\cdots ,\overline{x}_{n}
\end{eqnarray*}の組のことであり、解釈を与えれば\(A\left( x_{1},\cdots ,x_{n}\right) \)から1つの命題が得られます。したがって、開論理式\(A\left( x_{1},\cdots ,x_{n}\right) \)が恒偽式であることとは、任意の解釈において、\(A\left( x_{1},\cdots ,x_{n}\right) \)から得られる命題が偽であることを意味します。

例(恒偽な開論理式)
変数\(x\in X\)に関する命題関数\(P\left( x\right) \)と\(Q\left( x\right) \)を被演算子とする以下の開論理式\begin{equation}
(P\left( x\right) \wedge \left( P\left( x\right) \rightarrow Q\left(
x\right) \right) )\wedge \lnot Q\left( x\right) \tag{1}
\end{equation}について考えます。解釈を任意に選んだ上で、そのときに\(P\left( x\right) \)から得られる命題を\(P\left( \overline{x}\right) \)で、\(Q\left( x\right) \)から得られる命題を\(Q\left( \overline{x}\right) \)でそれぞれ表記すると、\(\left( 1\right) \)から得られる命題は、\begin{equation*}
(P\left( \overline{x}\right) \wedge \left( P\left( \overline{x}\right)
\rightarrow Q\left( \overline{x}\right) \right) )\wedge \lnot Q\left(
\overline{x}\right)
\end{equation*}となります。これを同値変形すると、\begin{eqnarray*}
(P\left( \overline{x}\right) \wedge \left( P\left( \overline{x}\right)
\rightarrow Q\left( \overline{x}\right) \right) )\wedge \lnot Q\left(
\overline{x}\right) &\Leftrightarrow &(P\left( \overline{x}\right) \wedge
\left( \lnot P\left( \overline{x}\right) \vee Q\left( \overline{x}\right)
\right) )\wedge \lnot Q\left( \overline{x}\right) \quad \because \rightarrow
\text{の言い換え} \\
&\Leftrightarrow &(\left( P\left( \overline{x}\right) \wedge \lnot P\left(
\overline{x}\right) \right) \vee \left( P\left( \overline{x}\right) \wedge
Q\left( \overline{x}\right) \right) )\wedge \lnot Q\left( \overline{x}\right) \quad \because \text{分配律} \\
&\Leftrightarrow &(\bot \vee \left( P\left( \overline{x}\right) \wedge
Q\left( \overline{x}\right) \right) )\wedge \lnot Q\left( \overline{x}\right) \quad \because \text{矛盾律} \\
&\Leftrightarrow &\left( P\left( \overline{x}\right) \wedge Q\left(
\overline{x}\right) \right) \wedge \lnot Q\left( \overline{x}\right) \quad
\because \text{恒偽式}\bot \text{の性質}
\\
&\Leftrightarrow &P\left( \overline{x}\right) \wedge \left( Q\left(
\overline{x}\right) \wedge \lnot Q\left( \overline{x}\right) \right) \quad
\because \text{交換律} \\
&\Leftrightarrow &P\left( \overline{x}\right) \wedge \bot \quad \because
\text{矛盾律} \\
&\Leftrightarrow &\bot \quad \because \text{恒偽式}\bot
\text{の性質}
\end{eqnarray*}すなわち恒偽式\(\bot \)となります。任意の解釈のもとで同様の議論が成り立つため、\(\left( 1\right) \)が恒偽式であることが明らかになりました。

 

事実式

恒真式や恒偽式ではない論理式を事実式(contingency)や整合式などと呼びます。事実式から得られる命題の値は、解釈によって真にも偽にもなります。つまり、ある論理式が事実式であることは、その論理式から得られる命題が真になるような解釈と、その論理式から得られる命題が偽になるような解釈の双方が存在することを意味します。

繰り返しになりますが、論理式\(A\)が変数の自由な現れを持たない閉論理式である場合、その解釈とは以下の2つの要素\begin{eqnarray*}
&&\left( a\right) \ \text{議論領域}D \\
&&\left( b\right) \ \text{論理式}A\text{を構成するすべての命題関数の形状}
\end{eqnarray*}の組のことであり、解釈を与えれば\(A\)から1つの命題が得られます。したがって、閉論理式\(A\)が事実式であるとは、ある解釈において、\(A\)から得られる命題が真であり、別の解釈において、\(A\)から得られる命題が偽であることを意味します。

例(事実式であるような閉論理式)
変数\(x\in X\)に関する命題関数\(P\left( x\right) \)を被演算子とする以下の論理式\begin{equation}
\left( \forall x\in X:P\left( x\right) \right) \vee \left( \forall x\in
X:\lnot P\left( x\right) \right) \tag{1}
\end{equation}について考えます。全称記号\(\forall \)の定義より、上の論理式は、\begin{equation}
\left( \bigwedge\limits_{x\in X}P\left( x\right) \right) \vee \left(
\bigwedge\limits_{x\in X}\lnot P\left( x\right) \right) \tag{2}
\end{equation}と変形可能です。\(X\)の任意の値\(\overline{x}\)において命題\(P\left( \overline{x}\right) \)が真であるような解釈のもとでは、\(\left( 1\right) \)から得られる命題は真です。一方、命題\(P\left( \overline{x}\right) \)が真になるような値\(\overline{x}\)と命題\(P\left( \overline{x}\right) \)が偽になるような値\(\overline{x}\)が少なくとも1つずつ存在するような解釈のもとでは、\(\left( 1\right) \)から得られる命題は偽です。したがって、\(\left( 2\right) \)やその言い換えである\(\left( 1\right) \)は事実式です。

繰り返しになりますが、論理式\(A\)が変数\(x_{1},\cdots ,x_{n}\)の自由な現れを持つ開論理式\(A\left( x_{1},\cdots ,x_{n}\right) \)である場合、その解釈とは以下の3つの要素\begin{eqnarray*}
&&\left( a\right) \ \text{議論領域}D \\
&&\left( b\right) \ \text{論理式}A\text{を構成するすべての命題関数の形状} \\
&&\left( c\right) \ \text{変数の自由な現れに代入する値}\overline{x}_{1},\cdots ,\overline{x}_{n}
\end{eqnarray*}の組のことであり、解釈を与えれば\(A\left( x_{1},\cdots ,x_{n}\right) \)から1つの命題が得られます。したがって、開論理式\(A\left( x_{1},\cdots ,x_{n}\right) \)が事実式であるとは、ある解釈において、\(A\left( x_{1},\cdots ,x_{n}\right) \)から得られる命題が真であり、別の解釈において、\(A\left( x_{1},\cdots ,x_{n}\right) \)から得られる命題が偽であることを意味します。

例(事実式であるような開論理式)
変数\(x\in X\)に関する命題関数\begin{equation}
P\left( x\right) \tag{1}
\end{equation}について考えます。これは変数\(x\)の自由な現れを持つ開論理式です。命題\(P\left( \overline{x}\right) \)が真になるような値\(\overline{x}\)と命題\(P\left( \overline{x}\right) \)が偽になるような値\(\overline{x}\)が少なくとも1つずつ存在するような解釈の存在を踏まえると、\(\left( 1\right) \)は事実式です。

次回は必要条件と十分条件について学びます。

次へ進む 質問・コメントを投稿する 演習問題(プレミアム会員限定)
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 ファイルの添付も可能です。

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

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

述語論理
アカウント
ログイン