命題論理における論理式の定義

命題変数は論理式

命題論理では個々の具体的な命題を議論の対象とするのではなく、議論を一般化するために、真\(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 productof \(P\) and \(Q\)）と呼びます。

命題変数\(P,Q\)に論理演算子\(\vee \)を作用させることにより得られる論理式を、\begin{equation*}P\vee Q
\end{equation*}で表記し、これを\(P\)と\(Q\)の論理和（logical productof \(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 productof \(A\) and \(B\)）と呼びます。

論理式\(A,B\)に論理演算子\(\vee \)を作用させることにより得られる論理式を、\begin{equation*}A\vee B
\end{equation*}で表記し、これを\(A\)と\(B\)の論理和（logical productof \(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 \)を作用させることにより得られる式も論理式です。

以上を踏まえた上で、論理式を以下のように再帰的に定義します。

論理式が複数の論理演算子を含む場合、それらの論理演算子を作用させる順番が問題になります。以上のルールのもとで論理式が生成された場合、より内側の括弧によって囲まれた論理演算子を優先的に作用させるものと定めます。

論理式の例をいくつか挙げます。

論理式中の括弧の省略

先の最後の例のように、定義にもとづいて生成された論理式が括弧\((\ )\)を多く含む場合には見づらいため、以下のルールのもとで括弧を省略できるものと定めます。

1. 一番外側の括弧は省略できる。
2. 括弧を省略した結果、複数の論理演算子が括弧によって遮られない形で存在している場合には、最初に\(\lnot \)を作用させ、次に\(\wedge ,\vee ,\veebar \)を作用させ、最後に\(\rightarrow ,\leftrightarrow \)を作用させる。以上のルールを踏まえた上で、論理式中の括弧を外して新たな式を得たときに、その式における論理演算子の作用の順番がもとの論理式の内容と整合的であるならば、その括弧を省略できる。

いくつか例を挙げます。

部分論理式

命題変数\(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）と呼びます。つまり、ある論理式の部分論理式とは、その論理式を生成するために部品となるすべての論理式を指します。ただし、論理式自身をその論理式の部分論理式とみなします。

以上を踏まえた上で、部分論理式の概念を以下のように再帰的に定義します。

演習問題