¾ðÊó´ðÁÃ/¥³¥ó¥Ô¥å¡¼

情報基礎/コンピュータ数学
論理 2
情報基礎/コンピュータ数学
1 / 10
1
述語論理
2
練習問題
情報基礎/コンピュータ数学
2 / 10
述語論理
定義 4.11
A を集合とする．A から {0, 1} への関数を述語という．
例以下は全て述語である．
任意の論理関数 φ : {0, 1}n → {0, 1}
以下のような関数 φ : N → {0, 1}
{
1
φ(x) =
0
(x が素数)
(それ以外)
A を世界の都市の集合として，以下のような関数 φ : A → {0, 1}
{
1 (a が首都)
φ(a) =
0 (それ以外)
情報基礎/コンピュータ数学
3 / 10
全称命題，存在命題
定義 4.12
A を集合，φ : A{0, 1} を述語とする，また，A′ ⊆ A とする．
全称命題とは，すべての x ∈ A′ について，ϕ(x) = 1 である命題であ
り，以下のようにあらわす．∀ を全称記号という．
∀x ∈ A′ [φ(x) = 1]
存在命題とは，ある x ∈ A′ が存在して，ϕ(x) = 1 である命題であ
り，以下のようにあらわす．∃ を存在記号という．
∃x ∈ A′ [φ(x) = 1]
∀ 記号と ∃ 記号を量化子または限定子という．
論理変数，述語，∨，∧，否定及び，∀，∃ で表される式を述語論理に
よる論理式，または単に論理式という．
情報基礎/コンピュータ数学
4 / 10
例 4.6，例 4.7
例：以下は述語論理による論理式である．
命題論理による論理式
(∀ ∈ A[φ(x) = 1]) ∨ (y ∧ z)．(φ : A → {0, 1})
∀x1 ∈ A, ∀x2 ∈ A, ∀x3 ∈ A[φ(x1 , x2 , x3 , y] = 1]．(φ : A4 → {0, 1})
例：以下は，各言明に対応する論理式を記述したものである．
すべての自然数は整数である．
∀x ∈ N[x ∈ Z]
すべての実数 x に対して，x ≥ 0 ならば x2 ≤ x3 ．
∀x ∈ R[x ≥ 0 ⇒ x2 ≤ x3 ]
ある定数 c が存在して，すべての実数 x に対して，x ≥ c ならば
x2 ≤ x3 ．
∃c ∈ R, ∀x ∈ R[x ≥ c ⇒ x2 ≤ x3 ]
情報基礎/コンピュータ数学
5 / 10
問 4.4
問 4.4
以下の文章を論理式で表せ．さらに，その真偽を判定し，理由も述べよ．
すべての実数 x に対して，ある実数 y が存在して，x ≥ 0 ならば
y 2 < x を満たす．
ある実数 a が存在して，すべての実数 b に対して，2 次方程式
x2 + ax + b = 0 が実数解をもつ．
ある実数 b が存在して，すべての実数 a に対して，2 次方程式
x2 + ax + b = 0 が実数解をもつ．
すべての実数 x に対して，ある実数 a が存在して，
x ∈ {y ∈ R : |y| < a} を満たす．
ある実数 x が存在して，すべての実数 a に対して，
x ∈ {y ∈ R : |y| < a} を満たす．
情報基礎/コンピュータ数学
6 / 10
問 4.5
問 4.5
任意の述語 φ について，以下は成り立つか？成り立たないのであれば，
成り立つ例と成り立たない例を挙げよ．
∃x ∈ R, ∀y ∈ R[φ(x, y) = 1] ≡ ∀y ∈ R, ∃x ∈ R[φ(x, y) = 1]
情報基礎/コンピュータ数学
7 / 10
ド・モルガンの法則
定理 4.9
φ を任意の述語とする．このとき，以下が成り立つ．
∀x[φ(x)] ≡ ∃x[ϕ(x)]
∃x[φ(x)] ≡ ∀x[ϕ(x)]
【証明】定義より明らか．
情報基礎/コンピュータ数学
8 / 10
ド・モルガンの法則（一般形）
定理 4.10
φ を任意の述語とする．このとき，以下が成り立つ．
∀x1 , ∃x2 , ∀x3 , . . . , Qxk [φ(x1 , x2 , x3 , . . . , xk )]
≡ ∃x1 , ∀x2 , ∃x3 , . . . , Q′ xk [φ(x1 , x2 , x3 , . . . , xk )]
∃x1 , ∀x2 , ∃x3 , . . . , Qxk [φ(x1 , x2 , x3 , . . . , xk )]
≡ ∀x1 , ∃x2 , ∀x3 , . . . , Q′ xk [φ(x1 , x2 , x3 , . . . , xk )]
ここで，Q = ∀ のとき，Q′ = ∃ であり，Q = ∃ のとき，Q′ = ∀ である．
【証明】数学的帰納法により示す．
（詳細は省略）
情報基礎/コンピュータ数学
9 / 10
練習問題
練習問題 1
以下の文章を論理式で表せ．さらに，その真偽を判定し，理由も述べよ．
すべての自然数 x に対して，x/x = 1 を満たす．
ある実数 c が存在して，すべての実数 x に対して，x ≥ c ならば
x2 − cx > 0 を満たす．
ある自然数 x が存在して，すべての自然数 y に対して，x > y + 1 を
満たす．
すべての自然数 y に対して，ある自然数 x が存在して，x > y + 1 を
満たす．
ある実数 x，ある実数 y ，ある実数 z が存在して，x2 + y 2 = z 2 を満
たす．
情報基礎/コンピュータ数学
10 / 10

Download Report