日本語技法 NO.5

[figure: 論理記号の計算法。]

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

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

(1) (巾等律)P ∧ P = P, P ∨ P = P.

(2) (交換律)P ∧ Q = Q ∧ P, P ∨ Q = Q ∨ P.

(3) (結合律)(P ∧Q)∧R = P ∧(Q∧R), (P ∨Q)∨R = P ∨(Q∨R)

(4) (吸収律)(P ∧ Q) ∨ P = P, (P ∨ Q) ∧ P = P

(5) (分配律)(P ∧ Q) ∨ R = (P ∨ R) ∧ (Q ∨ R), (P ∨ Q) ∧ R = (P ∧ R) ∨ (Q ∧ R)

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

定理 5.2. (and, or の否定)

(1) ¬(P ∨ Q) = (¬P) ∧ (¬Q)

(2) ¬(P ∧ Q) = (¬P) ∨ (¬Q)

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

定理 5.3. (∀, ∃ の否定。 ) 変数 x についての命題 P (x) について、つぎのことが成り立つ。

(1) ¬(∀x(P (x))) = ∃x(¬P (x))

(2) ¬(∃x(P (x))) = ∀x(¬P (x))

定理 5.4.

¬(P ⟹ Q) = P ∧ (¬Q)

問題 5.1.

¬((P ∨ Q) ⟹ R) = (P ∧ (¬R)) ∨ (Q ∧ (¬R))

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