[開設 07/03/23=MM/DD/YY]
論理法則
P ✻ ☆x Q(x)
⇔
☆x ( P ✻ Q(x) )
☆ は ∀ と ∃ のいずれでもよく，
✻ は ∧，∨，⇒ のいずれでもよい．
また，P は変数 x を含まない．
2×3 = 6 通りの法則がある．
- (1)
-
P ∧ ∀x Q(x)
⇔
∀x ( P ∧ Q(x) )
- (2)
-
P ∧ ∃x Q(x)
⇔
∃x ( P ∧ Q(x) )
- (3)
-
P ∨ ∀x Q(x)
⇔
∀x ( P ∨ Q(x) )
- (4)
-
P ∨ ∃x Q(x)
⇔
∃x ( P ∨ Q(x) )
- (5)
-
P ⇒ ∀x Q(x)
⇔
∀x ( P ⇒ Q(x) )
- (6)
-
P ⇒ ∃x Q(x)
⇔
∃x ( P ⇒ Q(x) )
これらの法則は特に覚える必要はない．
（下の説明を読んで）理解できれば十分である．
ただし，
∀x∈A, ∃x∈A
の記法を使った論理式を，
使わない論理式に戻すとき，
変域の制限をはずした
∀x や ∃x
は全部 左に寄せられることは
知っておくと便利でしょう．
なお，
∀x Q(x) ⇒ P
⇔
∀x ( Q(x) ⇒ P )
と
∃x Q(x) ⇒ P
⇔
∃x ( Q(x) ⇒ P )
は成り立たない．
その代わり，
- (7)
-
∀x Q(x) ⇒ P
⇔
∃x ( Q(x) ⇒ P )
- (8)
-
∃x Q(x) ⇒ P
⇔
∀x ( Q(x) ⇒ P )
が成り立つ．
法則 (7) と (8) は，なおさら覚える必要はない．
法則 (1)‐(8) を使うと，
どんな論理式も，
それと論理的に同値なままで，
すべての限定記号を左端に寄せて
☆1x1
☆2x2
. . .
☆nxn
( … )
の形の論理式にすることができます
（☆i は ∀ または ∃で，
( … ) には ∀ や ∃ は含まれない）．
この形の論理式を
冠頭標準形 (prenex normal form) と言います．
なお，このことは，この授業では 覚える必要はありません．
では，
（日常的な論理にしたがって）
上の法則 (1)‐(8) を
一つ一つ確認していこう．
- (1)
P ∧ ∀x Q(x)
⇔
∀x ( P ∧ Q(x) )
-
- (⇒)
-
P ∧ ∀x Q(x)
が真なら，
P も真で，
∀x Q(x) も真である．
∀x Q(x) が真だから，
任意の x について Q(x) は真である．
よって，
任意の x について
P ∧ Q(x) が真だから，
∀x ( P ∧ Q(x) )
も真となる．
- (⇐)
-
∀x ( P ∧ Q(x) )
が真なら，
任意の x について
P ∧ Q(x) が真である．
P は x を含まないので，
x に関係なく常に真である．
一方，
任意の x について
Q(x) が真なので，
∀x Q(x) は真である．
よって，
P ∧ ∀x Q(x)
は真である．
- (2)
-
P ∧ ∃x Q(x)
⇔
∃x ( P ∧ Q(x) )
-
- (⇒)
-
P ∧ ∃x Q(x)
が真なら，
P も真で，
∃x Q(x) も真である．
∃x Q(x) が真だから，
Q(a) が真となる対象 a が存在する．
よって，
P ∧ Q(a) が真だから，
∃x ( P ∧ Q(x) )
も真となる．
- (⇐)
-
∃x ( P ∧ Q(x) )
が真なら，
ある対象 a について
P ∧ Q(a) が真である．
よって，P は真である．
また，
Q(a) が真なので，
∃x Q(x) は真である．
以上から，
P ∧ ∃x Q(x)
は真である．
- (3)
-
P ∨ ∀x Q(x)
⇔
∀x ( P ∨ Q(x) )
-
- (⇒)
-
P ∨ ∀x Q(x)
が真なら，
P と
∀x Q(x)
のうち少なくとも一方は真である．
そこで場合分けをする．
- P が真の場合．
-
P が真だから，
任意の x について
P ∨ Q(x) は真だから，
∀x ( P ∨ Q(x) )
も真となる．
- ∀x Q(x)
が真の場合．
-
∀x Q(x)
より，
任意の x について
Q(x)
が真だから，
任意の x について
P ∨ Q(x) も真となる．
よって，
∀x ( P ∨ Q(x) )
も真である．
以上から，
いずれにしろ
∀x ( P ∨ Q(x) )
は真である．
- (⇐)
-
最初から，
P が真の場合と偽の場合で
場合分けをする．
- P が真の場合．
-
P が真なので，
当然，
P ∨ ∀x Q(x)
も真である．
- P が偽の場合．
-
∀x ( P ∨ Q(x) )
が真であるという仮定から，
任意の x について，
P または Q(x) が真となる．
しかし，いま P は偽としているので，
任意の x について
Q(x) が真でなければならない．
よって，
∀x Q(x) は真である．
したがって，
P ∨ ∀x Q(x)
も真である．
- (4)
-
P ∨ ∃x Q(x)
⇔
∃x ( P ∨ Q(x) )
-
- (⇒)
-
P ∨ ∃x Q(x)
が真なら，
P と
∃x Q(x)
のうち少なくとも一方は真である．
そこで場合分けをする．
- P が真の場合．
-
P が真だから，
任意の x について
P ∨ Q(x) は真となるので，
当然，
P ∨ Q(x) が真となる
x は存在する．
よって，
∃x ( P ∨ Q(x) )
も真となる．
- ∃x Q(x)
が真の場合．
-
∃x Q(x)
より，
ある対象 a について
Q(a) は真である．
よって，
P ∨ Q(a) も真となる．
よって，
P ∨ Q(a) が真となる
対象 a があったので，
∃x ( P ∨ Q(x) )
も真である．
以上から，
いずれにしろ
∃x ( P ∨ Q(x) )
は真である．
- (⇐)
-
最初から，
P が真の場合と偽の場合で
場合分けをする．
- P が真の場合．
-
P が真なので，
当然，
P ∨ ∃x Q(x)
も真である．
- P が偽の場合．
-
∃x ( P ∨ Q(x) )
が真であるという仮定から，
P または Q(a) が真となるような
対象 a が存在する．
いま P は偽としているので，
Q(a) が真でなければならない．
よって，
∃x Q(x) は真である．
したがって，
P ∨ ∃x Q(x)
も真である．
- 注：
-
de Morgan 律を使うと，
(1) と (4) が互いに一方から他方が導け，
(2) と (3) も互いに一方から他方が導ける．
例として，
(1) を使って (4) を導こう
（他も同様である）．
|
P ∨ ∃x Q(x)
|
⇔
|
¬¬P ∨ ∃x ¬¬Q(x)
|
∵ 二重否定律
|
|
|
⇔
|
¬¬P ∨ ¬∀x ¬Q(x)
|
∵ de Morgan 律
|
|
|
⇔
|
¬ [ ¬P ∧ ∀x ¬Q(x) ]
|
∵ de Morgan 律
|
|
|
⇔
|
¬ ∀x [ ¬P ∧ ¬Q(x) ]
|
∵ (1)
|
|
|
⇔
|
∃x ¬ [ ¬P ∧ ¬Q(x) ]
|
∵ de Morgan 律
|
|
|
⇔
|
∃x [ ¬¬P ∨ ¬¬Q(x) ]
|
∵ de Morgan 律
|
|
|
⇔
|
∃x [ P ∨ Q(x) ]
|
∵ 二重否定律
|
- (5)
-
P ⇒ ∀x Q(x)
⇔
∀x ( P ⇒ Q(x) )
-
|
P ⇒ ∀x Q(x)
|
⇔
|
¬P ∨ ∀x Q(x)
|
∵ 条件命題の選言表現
|
|
|
⇔
|
∀x ( ¬P ∨ Q(x) )
|
∵ (3)
|
|
|
⇔
|
∀x ( P ⇒ Q(x) )
|
∵ 条件命題の選言表現
|
- (6)
-
P ⇒ ∃x Q(x)
⇔
∃x ( P ⇒ Q(x) )
-
|
P ⇒ ∃x Q(x)
|
⇔
|
¬P ∨ ∃x Q(x)
|
∵ 条件命題の選言表現
|
|
|
⇔
|
∃x ( ¬P ∨ Q(x) )
|
∵ (4)
|
|
|
⇔
|
∃x ( P ⇒ Q(x) )
|
∵ 条件命題の選言表現
|
- (7)
∀x Q(x) ⇒ P
⇔
∃x ( Q(x) ⇒ P )
-
|
∀x Q(x) ⇒ P
|
⇔
|
¬∀x Q(x) ∨ P
|
∵ 条件命題の選言表現
|
|
|
⇔
|
∃x ¬Q(x) ∨ P
|
∵ de Morgan 律
|
|
|
⇔
|
∃x (¬Q(x) ∨ P )
|
∵ (4)
|
|
|
⇔
|
∃x ( Q(x) ⇒ P )
|
∵ 条件命題の選言表現
|
- (8)
-
∃x Q(x) ⇒ P
⇔
∀x ( Q(x) ⇒ P )
-
|
∃x Q(x) ⇒ P
|
⇔
|
¬∃x Q(x) ∨ P
|
∵ 条件命題の選言表現
|
|
|
⇔
|
∀x ¬Q(x) ∨ P
|
∵ de Morgan 律
|
|
|
⇔
|
∀x (¬Q(x) ∨ P )
|
∵ (3)
|
|
|
⇔
|
∀x ( Q(x) ⇒ P )
|
∵ 条件命題の選言表現
|
離散構造（室伏）のホーム
