論理と集合要約 NO.3

第 3 回目の主題 : 命題の否定と集合の補集合 ◎ and, or の否定

問題 3.1. not (P and Q) と ( not P) or ( not Q) とが同値であることを真理表を用いて示しなさい。

◎ P ⟹ Q の否定

P ⟹ Q は ( not P) or Q と同値であったので、その否定は P and (not Q) で与えられる。 ◎ ∀, ∃ の否定

「すべての X の元 x について P (x) が成り立つ」、すなわち

∀x ∈ X (P (x))

の否定は「ある X の元 x について P (x) が成り立たない」、すなわち

∃x ∈ X ( not P (x))

である。

同様に、

∃x ∈ X (P (x))

の否定は

∀x ∈ X ( not P (x))

である。

実際の場面では、上の x ∈ X のように x の制限を「集合の元か否か」で書くとは限らず、そのまま条件で書くことも多い。以下の例を参照のこと。

例 3.1.

∀ϵ > 0∃δ > 0∀x ∈ ℝ (|x − 3| < δ ⟹ |x^{2} − 9| < ϵ)

(x ↦ x^{2} が x = 3 で連続であるという命題 (真)) の否定は

(★)  ∃ϵ > 0∀δ > 0∃x ∈ ℝ ( not (|x − 3| < δ ⟹ |x^{2} − 9| < ϵ))

(x ↦ x^{2} が x = 3 で連続でないという命題 (偽)) である。このように、 ∀ や ∃ が散在する命題の

否定は、 • 順序はそのままに、

• ∀ と ∃ を入れ替え、

• 最後の結論を否定する。という手続きで得られる。さらに、命題 (★) は、 ( 「P ⟹ Q」の否定が「 P and( not Q)」であったことから、 )

∃ϵ > 0∀δ > 0∃x ∈ ℝ (|x − 3| < δ and |x^{2} − 9| ≥ ϵ)

と書き換えられる。

問題 3.2. つぎの各々の命題の否定をそれぞれ述べなさい。 (1) ∀x ∈ ℝ∃y ∈ ℝ (x + y = 0)

(2) ∀x ∈ ℝ∀z ∈ ℝ∃y ∈ ℝ (xy ≠ z)

集合 X と S が与えられたとき、

X \ S = {x; x ∈ X and x ∉ S}

を X と S の差集合という。 (X − S と書く流儀もあり、本講義の教科書ではそう書いてある。 )

とくに、 S が X の部分集合の時、 X \ S を X における補集合とよぶ。 X が分かりきっているときには ∁S と書くこともある。

論理と集合要約 NO.3

問題 3.3. 集合 X の部分集合 A, B が与えられたとする。このとき、 X を全体集合として考えて

∁(A ∩ B) = ∁A ∪ ∁B

が成り立つことを示しなさい。