論理式

代数でそうであったように，命題論理でも 式が定義される。 それは論理式と呼ばれる。 代数で学んだように，

$$x + y + z \quad x + y \cdot z$$

は式であるが

$$x + y + \quad x +　\cdot y \cdot z$$

は式でない。変数記号$x,y$と演算記号$+,\cdot$を用いて式を 作るためには決まりがあった。 同様に命題変数の記号$X,Y$や論理演算の記号 $\lnot,\land,\lor,\Rightarrow$ を用いて論理式を作るのにも次のような規則がある。

(1).

$T$ および $F$ は論理式である。

(2).

個々の命題変数は論理式である。

(3).

$\cal A$ が論理式ならば、$\neg\cal A$ は論理式である。

(4).

$\cal A,B$ が論理式ならば、

$$\cal A \land B, A \lor B, A \Rightarrow B$$

は、いずれも論理式である。

上の定義では$T$と$F$以外具体的な論理式は出てこない。$\cal A,B$ は不特定な論理式を表すメタ記号であって，具体的な論理式ではない。 しかし，これらの規則で無数の論理式を作りだすことができる。 例えば

$$\begin{eqnarray*} &&命題変数X,\quad Y.と真理値を表す T, \quad Fは論理式である。... ...htarrow X \lor \lnot Y も論理式 （規則(4)）\\ && \cdots \\ \end{eqnarray*}$$

上の例でも判るように，プログラム言語を学んだ人には馴染みのある 「再帰的」な定義になっている。 命題論理における論理式の全体を $\bf L$ と書くことにしよう。