命題変数は論理式
命題論理では個々の具体的な命題を議論の対象とするのではなく、議論を一般化するために、真\(1\)または偽\(0\)を値として取り得る変数\begin{equation*}P,Q,\cdots
\end{equation*}を議論の対象とします。このような変数を命題変数(proposition variable)と呼びます。命題変数は命題論理の議論の対象となる最小単位です。
命題論理において議論の対象となる論理的な主張や推論はいずれも命題変数どうしを組み合わせることにより得られる式として表現されます。そのような式を論理式(formula)や命題論理式(propositional formula)などと呼びます。以下では論理式という概念を形式的に定義します。
まず、命題論理において個々の命題変数\(P,Q,\cdots \)は単独で論理式とみなされます。
命題定数は論理式
命題論理では、命題変数\(P,Q,\cdots \)が取り得る値である真理値\begin{equation*}0,1
\end{equation*}もまた特別な命題変数とみなします。つまり、真理値\(0\)を常に一定の値\(0\)を取る命題変数とみなし、\(1\)を常に一定の値\(1\)を取る命題変数とみなします。真理値\(0,1\)をこのような特別な命題変数とみなすとき、これらを命題定数(propositional constants)と呼びます。以降では、真理値\(0\)を命題定数として扱う場合には、\begin{equation*}F
\end{equation*}と表記し、真理値\(1\)を命題定数として扱う場合には、\begin{equation*}T
\end{equation*}と表記します。
先ほど定めたように命題変数は単独で論理式とみなされますが、命題定数\(T,F\)はいずれも特別な命題変数であるため、これらもまた単独で論理式とみなされます。つまり、命題定数\(F,T\)はともに論理式であるということです。
以下で「命題変数」と言う場合、特別な断りがない限り、それは命題定数\(T,F\)を含むものとします。
命題変数に論理演算子を作用させた式は論理式
命題論理では命題変数\(P,Q,\cdots \)に対して行う操作を表す記号\begin{equation*}\lnot ,\wedge ,\vee ,\veebar ,\rightarrow ,\leftrightarrow
\end{equation*}を導入した上で、これらを命題変数に作用させることにより新たな論理式を作り出します。これらの記号を論理演算子(logical operators)や論理結合子(logical connectives)などと呼び、論理演算子が表す操作を論理演算(logical operation)と呼びます。
それぞれの論理演算子の意味は後ほど解説することとして、まずは論理式という概念を形式的に定義します。
命題変数\(P\)に論理演算子\(\lnot \)を作用させることにより得られる論理式を、\begin{equation*}\lnot P
\end{equation*}で表記し、これを\(P\)の否定(negation of \(P\))と呼びます。
命題変数\(P,Q\)に論理演算子\(\wedge \)を作用させることにより得られる論理式を、\begin{equation*}P\wedge Q
\end{equation*}で表記し、これを\(P\)と\(Q\)の論理積(logical product of \(P\) and \(Q\))と呼びます。
命題変数\(P,Q\)に論理演算子\(\vee \)を作用させることにより得られる論理式を、\begin{equation*}P\vee Q
\end{equation*}で表記し、これを\(P\)と\(Q\)の論理和(logical sum of \(P\) and \(Q\))と呼びます。
命題変数\(P,Q\)に論理演算子\(\veebar \)を作用させることにより得られる論理式を、\begin{equation*}P\veebar Q
\end{equation*}で表記し、これを\(P\)と\(Q\)の排他的論理和(exclusive disjunction of \(P\) and \(Q\))と呼びます。
命題変数\(P,Q\)に論理演算子\(\rightarrow \)を作用させることにより得られる論理式を、\begin{equation*}P\rightarrow Q
\end{equation*}で表記し、これを\(P\)から\(Q\)への含意(implication from \(P\) to \(Q\))と呼びます。
命題変数\(P,Q\)に論理演算子\(\leftrightarrow \)を作用させることにより得られる論理式を、\begin{equation*}P\leftrightarrow Q
\end{equation*}と表記し、これを\(P\)と\(Q\)の同等(equivalent of \(P\) and \(Q\))と呼びます。
これらの論理式の意味については後ほど解説します。
論理式に論理演算子を作用させた式は論理式
命題論理では命題変数\(P,Q,\cdots \)に対して論理演算子\(\lnot ,\wedge ,\vee ,\veebar ,\rightarrow ,\leftrightarrow \)を作用させることにより論理式を生成するだけでなく、そのようにして生成された論理式\(A,B,\cdots \)に対して再び論理演算子\(\lnot ,\wedge ,\vee,\veebar ,\rightarrow ,\leftrightarrow \)を作用させることにより得られる式もまた論理式とみなします。
それぞれの論理演算子の意味は後ほど解説することとして、まずは論理式という概念を形式的に定義します。
論理式\(A\)に論理演算子\(\lnot \)を作用させることにより得られる論理式を、\begin{equation*}\lnot A
\end{equation*}で表記し、これを\(A\)の否定(negation of \(A\))と呼びます。
論理式\(A,B\)に論理演算子\(\wedge \)を作用させることにより得られる論理式を、\begin{equation*}A\wedge B
\end{equation*}で表記し、これを\(A\)と\(B\)の論理積(logical product of \(A\) and \(B\))と呼びます。
論理式\(A,B\)に論理演算子\(\vee \)を作用させることにより得られる論理式を、\begin{equation*}A\vee B
\end{equation*}で表記し、これを\(A\)と\(B\)の論理和(logical sum of \(A\) and \(B\))と呼びます。
論理式\(A,B\)に論理演算子\(\veebar \)を作用させることにより得られる論理式を、\begin{equation*}A\veebar B
\end{equation*}で表記し、これを\(A\)と\(B\)の排他的論理和(exclusive disjunction of \(A\) and \(B\))と呼びます。
論理式\(A,B\)に論理演算子\(\rightarrow \)を作用させることにより得られる論理式を、\begin{equation*}A\rightarrow B
\end{equation*}で表記し、これを\(A\)から\(B\)への含意(implication from \(A\) to \(B\))と呼びます。
論理式\(A,B\)に論理演算子\(\leftrightarrow \)を作用させることにより得られる論理式を、\begin{equation*}A\leftrightarrow B
\end{equation*}と表記し、これを\(A\)と\(B\)の同等(equivalent of \(A\) and \(B\))と呼びます。
これらの論理式の意味については後ほど解説します。
論理式の再帰的定義
繰り返しになりますが、命題論理において命題変数\(P,Q,\cdots \)や命題定数\(T,F\)は単独で論理式とみなされます。また、それらに論理演算子\(\lnot ,\wedge ,\vee ,\veebar ,\rightarrow ,\leftrightarrow \)を作用させることにより得られる式\(A,B,\cdots \)も論理式とみなされます。また、そのようにして得られた論理式\(A,B,\cdots \)に論理演算子\(\lnot,\wedge ,\vee ,\veebar ,\rightarrow ,\leftrightarrow \)を作用させることにより得られる式も論理式です。
以上を踏まえた上で、論理式を以下のように再帰的に定義します。
- 命題変数\(P,Q,\cdots \)は論理式である。
- 命題定数\(T,F\)は論理式である。
- \(A\)が論理式ならば、\(\left( \lnot A\right) \)は論理式である。
- \(A,B\)が論理式ならば、\(\left( A\wedge B\right) \)は論理式である。
- \(A,B\)が論理式ならば、\(\left( A\vee B\right) \)は論理式である。
- \(A,B\)が論理式ならば、\(\left( A\veebar B\right) \)は論理式である。
- \(A,B\)が論理式ならば、\(\left( A\rightarrow B\right) \)は論理式である。
- \(A,B\)が論理式ならば、\(\left( A\leftrightarrow B\right) \)は論理式である。
- 以上から論理式と判定されるものだけが論理式である。
論理式が複数の論理演算子を含む場合、それらの論理演算子を作用させる順番が問題になります。以上のルールのもとで論理式が生成された場合、より内側の括弧によって囲まれた論理演算子を優先的に作用させるものと定めます。
論理式の例をいくつか挙げます。
\end{equation*}もまた論理式です。ちなみに、\begin{eqnarray*}
&&\left( P\right) \\
&&\lnot \left( P\right)
\end{eqnarray*}などは論理式ではありません。なぜなら、これらが論理式であることを認めるルールは存在しないからです。
\end{equation*}もまた論理式です。以上の事実とルール5より、\begin{equation}
\left( \left( P\wedge Q\right) \vee R\right) \quad \cdots (1)
\end{equation}もまた論理式です。括弧の位置から明らかであるように、最初に論理積\(\left( P\wedge Q\right) \)をとった上で、この論理積\(\left( P\wedge Q\right) \)と残された命題変数\(R\)の論理和をとることにより得られる論理式が\(\left( 1\right) \)です。同様の理由により、\begin{equation}\left( P\wedge \left( Q\vee R\right) \right) \quad \cdots (2)
\end{equation}もまた論理式です。括弧の位置から明らかであるように、最初に論理和\(\left( Q\vee R\right) \)をとった上で、この論理和\(\left( Q\vee R\right) \)と残された命題変数\(P\)の論理積をとることにより得られる論理式が\(\left( 2\right) \)です。\(\left( 1\right) \)と\(\left( 2\right) \)では括弧の位置が異なるため、これらを異なる論理式として区別する必要があります。
\end{equation*}は論理式です。以上の事実とルール4より、\begin{equation*}
\left( Q\wedge \left( P\rightarrow T\right) \right)
\end{equation*}もまた論理式です。
&&\left( P\vee R\right)
\end{eqnarray*}はともに論理式です。以上の事実とルール7より、\begin{equation*}
\left( \left( P\wedge Q\right) \rightarrow \left( P\vee R\right) \right)
\end{equation*}は論理式であり、以上の事実とルール3より、\begin{equation*}
\left( \lnot \left( \left( P\wedge Q\right) \rightarrow \left( P\vee
R\right) \right) \right)
\end{equation*}もまた論理式です。
論理式中の括弧の省略
先の最後の例のように、定義にもとづいて生成された論理式が括弧\((\ )\)を多く含む場合には見づらいため、以下のルールのもとで括弧を省略できるものと定めます。
- 一番外側の括弧は省略できる。
- 括弧を省略した結果、複数の論理演算子が括弧によって遮られない形で存在している場合には、最初に\(\lnot \)を作用させ、次に\(\wedge ,\vee ,\veebar \)を作用させ、最後に\(\rightarrow ,\leftrightarrow \)を作用させる。以上のルールを踏まえた上で、論理式中の括弧を外して新たな式を得たときに、その式における論理演算子の作用の順番がもとの論理式の内容と整合的であるならば、その括弧を省略できる。
いくつか例を挙げます。
\end{equation*}は論理式ですが、先のルールより、一番外側の括弧を省略して、\begin{equation*}
\lnot P
\end{equation*}とすることができます。
\end{equation*}は論理式ですが、先のルールより、一番外側の括弧を省略して、\begin{equation*}
\left( P\wedge Q\right) \vee R
\end{equation*}と表現することもできます。ちなみに、この論理式を、\begin{equation*}
P\wedge Q\vee R
\end{equation*}と表現することはできません。なぜなら、先のルールより、\(\wedge \)と\(\vee \)は作用の順番が等しいため、\(P\wedge Q\vee R\)と記述した場合、これは\(\left( P\wedge Q\right) \vee R\)と\(P\wedge \left(Q\vee R\right) \)のどちらであるか判別できないからです。
R\right) \right) \right)
\end{equation*}は論理式ですが、先のルールより、一番外側の括弧を省略して、\begin{equation*}
\lnot \left( \left( P\wedge Q\right) \rightarrow \left( P\vee R\right)
\right)
\end{equation*}とすることができます。さらにこれを、\begin{equation*}
\lnot \left( P\wedge Q\rightarrow P\vee R\right)
\end{equation*}とすることもできます。なぜなら、\(\wedge \)と\(\vee \)は\(\rightarrow \)よりも先に作用させるルールであるため、上のような形で括弧を省略しても誤解は生じないからです。
部分論理式
命題変数\(P,Q\)に関する式\begin{equation*}\left( \left( \lnot P\right) \wedge Q\right)
\end{equation*}が論理式であることを論理式の定義から確認しましょう。まず、命題変数\begin{equation*}
P,\ Q
\end{equation*}はともに論理式です。\(P\)が論理式であるならば、\begin{equation*}\left( \lnot P\right)
\end{equation*}は論理式です。\(\left( \lnot P\right) \)と\(Q\)が論理式であるならば、\begin{equation*}\left( \left( \lnot P\right) \wedge Q\right)
\end{equation*}は論理式です。
論理式\(((\lnot P)\wedge Q)\)を生成する過程で登場したすべての論理式\(P,Q,(\lnot P)\)に\(((\lnot P)\wedge Q)\)自身を加えたものを\(((\lnot P)\wedge Q)\)の部分論理式(subformula)と呼びます。つまり、ある論理式の部分論理式とは、その論理式を生成するために部品となるすべての論理式を指します。ただし、論理式自身をその論理式の部分論理式とみなします。
以上を踏まえた上で、部分論理式の概念を以下のように再帰的に定義します。
- 論理式\(A\)自身は\(A\)の部分論理式である。
- 論理式\(A\)が論理式\(B\)を用いて\(\left( \lnot B\right) \)の形で表されているとき、\(B\)の部分論理式はすべて\(A\)の部分論理式でもある。
- 論理式\(A\)が論理式\(B,C\)を用いて\(\left( B\wedge C\right) \)という形で表されているとき、\(B,C\)の部分論理式はすべて\(A\)の部分論理式である。
- 論理式\(A\)が論理式\(B,C\)を用いて\(\left( B\vee C\right) \)という形で表されているとき、\(B,C\)の部分論理式はすべて\(A\)の部分論理式である。
- 論理式\(A\)が論理式\(B,C\)を用いて\(\left( B\veebar C\right) \)という形で表されているとき、\(B,C\)の部分論理式はすべて\(A\)の部分論理式である。
- 論理式\(A\)が論理式\(B,C\)を用いて\(\left( B\rightarrow C\right) \)という形で表されているとき、\(B,C\)の部分論理式はすべて\(A\)の部分論理式である。
- 論理式\(A\)が論理式\(B,C\)を用いて\(\left( B\leftrightarrow C\right) \)という形で表されているとき、\(B,C\)の部分論理式はすべて\(A\)の部分論理式である。
\end{equation*}の部分論理式を特定します。ルール1より、\(P\)自身は\(P\)の部分論理式です。ルール2より、\(P\)の部分論理式である\(P\)は\(\left( \lnot P\right) \)の部分論理式です。さらにルール1より、\(\left( \lnot P\right) \)自身は\(\left( \lnot P\right) \)の部分論理式です。以上より、\(\left( \lnot P\right) \)の部分論理式は、\begin{equation*}P,\ \left( \lnot P\right)
\end{equation*}であることが明らかになりました。
\end{equation*}の部分論理式を特定します。先の例において確認したように、\(\left( \lnot P\right) \)の部分論理式は\(P\)と\(\left( \lnot P\right) \)です。ルール1より、\(Q\)自身は\(Q\)の部分論理式です。ルール6より、\(\left( \lnot P\right) \)の部分論理式である\(P,\left( \lnot P\right) \)および\(Q\)の部分論理式である\(Q\)はいずれも\(\left( \left( \lnot P\right) \rightarrow Q\right) \)の部分論理式です。さらにルール1より、\(\left(\left( \lnot P\right) \rightarrow Q\right) \)自身は\(\left(\left( \lnot P\right) \rightarrow Q\right) \)の部分論理式です。以上より、\(\left( \left( \lnot P\right) \rightarrow Q\right) \)の部分論理式は、\begin{equation*}P,\ \left( \lnot P\right) ,\ Q,\ \left( \left( \lnot P\right) \rightarrow
Q\right)
\end{equation*}であることが明らかになりました。
演習問題
- \(P\)
- \(P\wedge \)
- \(P\wedge Q\)
- \(P\wedge Q)\)
- \(\left( P\wedge Q\right) \rightarrow R\)
- \(\left( \left( P\wedge Q\right) \rightarrow R\right) \vee \)
- \(\left( \left( P\wedge Q\right) \rightarrow R\right) \vee S\)
- \((\lnot P)\)
- \((\left( P\wedge Q\right) \vee R)\)
- \((\lnot ((P\wedge Q)\rightarrow (P\vee R)))\)
D\wedge E\right) \right) \right) \wedge \left( \left( \lnot F\right) \wedge
\left( G\vee \left( H\vee \left( I\vee J\right) \right) \right) \right)
\right)
\end{equation*}
- \(\left( \lnot P\right) \)
- \(\left( \left( \lnot P\right) \rightarrow Q\right) \)
- \(\left( \left( \lnot P\right) \rightarrow Q\right) \vee R\)
\end{equation*}では括弧が省略されています。すべての括弧を復元してください。
\end{equation*}では括弧が省略されています。すべての括弧を復元してください。
プレミアム会員専用コンテンツです
【ログイン】【会員登録】