日本語技法 No.5

論理記号の計算法。

前回までに、 and, or, not, $\implies$ , $\forall$ , $\exists$ という記号について 解説した。これらには簡単な計算規則があって、それらを知っていれば 真理表などを使わなくても論理展開の正しさが楽にわかる。 以下、簡単のため $x$ and $y$ を $x \wedge y$ , $x$ or $y$ を $x \vee y$ と書くことにする。

定理 5.1   $P,Q,R$ がどのような命題であっても、つぎのことが成り立つ。 (ただし、等号は両方の真理値が一致することを表す。)

1. (巾等律) $P \wedge P =P, \quad P \vee P = P.$
2. (交換律) $P \wedge Q = Q \wedge P,\quad P \vee Q = Q \vee P.$
3. (結合律) $(P \wedge Q)\wedge R = P \wedge(Q \wedge R),\quad (P \vee Q)\vee R = P \vee(Q \vee R)$
4. (吸収律) $(P \wedge Q)\vee P = P,\quad (P \vee Q)\wedge P = P$
5. (分配律) $(P \wedge Q)\vee R = (P \vee R) \wedge (Q\vee R), \quad (P \vee Q)\wedge R = (P \wedge R )\vee (Q \wedge R)$

証明には真理表を用いればよい。 どれも日常語で考えれば易しいことである。

定理 5.2 (and, or の否定)  

1. $\neg (P \vee Q)= (\neg P) \wedge (\neg Q )$
2. $\neg (P \wedge Q)= (\neg P) \vee (\neg Q )$

上のような記号列は、単に「見る」だけではなくて 「声に出して読む」習慣をつけるとよい。 「(xまたは y) の否定は、 (xでないか、または yでない。)」 等々。

定理 5.3 ( $\forall,\exists$ の否定。)   変数 $x$ についての 命題 $P(x)$ について、つぎのことが成り立つ。

1. $\neg (\forall x (P(x)))= \exists x (\neg P(x))$
2. $\neg (\exists x (P(x)))= \forall x (\neg P(x))$

定理 5.4  

$$\neg (P\implies Q) = P \wedge (\neg Q)$$

問題 5.1  

$$\neg ((P\vee Q)\implies R) = (P \wedge (\neg R))\vee (Q \wedge (\neg R))$$

を、真理表を用いるか、または上述の公式を何度か用いることにより、 証明しなさい。 (余力のある人はこの等式の意味も考えてみると良い。)