━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
数理論理学 確認問題７
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

●問1

次の各否定命題に括弧内の論理法則を順に適用して，¬Ｂ か ¬Q(x) が現れる
簡単な形に同値変形せよ．使った論理法則を各行に明示すること．

(1) ¬(Ａ∧Ｂ)　(ド・モルガン，⇒の¬と∨による表現)
(2) ¬(Ａ⇒Ｂ)　(⇒の¬と∨による表現，ド・モルガン，二重否定)
(3) ¬∃x (P(x) ∧ Q(x))　(ド・モルガン，(1)の結果)
(4) ¬∀x (P(x) ⇒ Q(x))　(ド・モルガン，(2)の結果)

●問2

平方数全体の集合を S で表すと，「x は平方数である」という述語は x∈S と表せる．
以下の各命題を S，＝，＜，∈，整数，変数，論理記号，括弧 を使った論理式で表せ．
不要な括弧は省いてもよいが，その他の略記は使わないこと．

(1) 121 と 484 は共に平方数である．
(2) どの平方数もみな非負である．
(3) 負の平方数は存在しない．
(4) 異なる平方数が存在する．

──────────────────────────────────────

●答1 (否定命題の同値変形)

(1)
　 ¬(Ａ∧Ｂ)
⇔ ¬Ａ∨¬Ｂ       (ド・モルガン：連言の否定)
⇔ Ａ⇒¬Ｂ        (⇒ の ¬, ∨ による表現)

(2)
　 ¬(Ａ⇒Ｂ)
⇔ ¬(¬Ａ∨Ｂ)     (⇒ の ¬, ∨ による表現)
⇔ ¬¬Ａ∧¬Ｂ      (ド・モルガン：選言の否定)
⇔ Ａ∧¬Ｂ        (二重否定)

(3)
　 ¬∃x (P(x) ∧ Q(x))
⇔ ∀x ¬(P(x) ∧ Q(x))     (ド・モルガン：存在の否定)
⇔ ∀x (¬P(x) ∨ ¬Q(x))    ((1)：連言の否定)
⇔ ∀x (P(x) ⇒ ¬Q(x))     ( 　　　〃　　　)

(4)
　 ¬∀x (P(x) ⇒ Q(x))
⇔ ∀x ¬(P(x) ⇒ Q(x))     (ド・モルガン：全称の否定)
⇔ ∃x (P(x) ∧ ¬Q(x))     ((2)：含意の否定)

［解説］

次の各命題の組が論理同値であることは良く使うので覚えておくとよい．
Ａ⇒Ｂ と ¬Ａ ∨ Ｂ
¬(Ａ∧Ｂ) と ¬Ａ∨¬Ｂ
¬(Ａ∨Ｂ) と ¬Ａ∧¬Ｂ
¬ ∀x P(x) と ∃x ¬P(x)
¬ ∃x P(x) と ∀x ¬P(x)

条件付きの全称と存在とは，次の形の論理式である．
∀x ( P(x) ⇒ Q(x) )      P(x) を満たす全ての x について，Q(x) が成り立つ
∃x ( P(x) ∧ Q(x) )      P(x) を満たすある x について，Q(x) が成り立つ
(3) では，条件付き全称の否定を，条件付き存在で表し，
(4) では，条件付き存在の否定を，条件付き全称で表している，
ということに注意する．

●答2 (論理式による表現：全称と存在)

(教科書 p.106 確認問題1.16 の解答と解説を参照)

［解説］

数学の文献に書かれた文章を論理式に翻訳し，再び文章に戻す練習を繰り返すとよい．

各論理式の略記を以下に示す．

(1') 121,484∈S
(2') ∀x∈S x≧0
(3') ¬ ∃x∈S x＜0
(4') ∃x,y∈S x≠y

論理記号に関する以下の略記を使っている（S は集合を表し P は述語記号を表す）．
(1) x∈S ∧ y∈S を x,y∈S と略記
(2) ∀x ( x∈S ⇒ P(x) ) を ∀x∈S P(x) と略記
(3) ∃x ( x∈S ∧ P(x) ) を ∃x∈S P(x) と略記
(4) ∃x1 ∃x2 … ∃xn P(x1,x2,…,xn) を ∃x1,x2,…,xn P(x1,x2,…,xn) と略記

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
授業のホームページ

山田 俊行
https://www.cs.info.mie-u.ac.jp/~toshi/