第6回復習用問題解答

情報基礎
2014 年 5 月 20 日
第 6 回復習用問題解答
担当者: 脊戸和寿
第 1 問：以下の論理式を出来るだけ簡単にせよ．
1. x ∨ (x ∧ y) = x ∧ y
2. x ∧ (x ∨ y) = x ∧ y
3. (x ∧ y) ∨ (x ∧ y) = y
4. x ∧ (x ⊕ y) = x ∧ y
5. (x ⇒ y) ∨ (y ⇒ x) = 1
第 2 問：以下の真理値表を和積標準形 (CNF)，積和標準形 (DNF) で表せ．
1.
2.
x
0
0
0
0
1
1
1
1
y
0
0
1
1
0
0
1
1
z
0
1
0
1
0
1
0
1
f (x, y, z)
0
1
1
0
0
1
0
0
x
0
0
0
0
1
1
1
1
y
0
0
1
1
0
0
1
1
z
0
1
0
1
0
1
0
1
f (x, y, z)
1
0
0
1
1
1
0
1
1. CNF : (x ∨ y ∨ z)(x ∨ y ∨ z)(x ∨ y ∨ z)(x ∨ y ∨ z) ∧ (x ∨ y ∨ z)，DNF : xyz ∨ xyz ∨ xyz
2. CNF : (x ∨ y ∨ z)(x ∨ y ∨ z)(x ∨ y ∨ z)，DNF : xyz ∨ xyz ∨ xyz ∨ xyz ∨ xyz
1
第 3 問：次の文章を論理式で表し，真偽についても答えよ．その理由についても答えること．
1. すべての自然数 x について，x/x = 1．
∀x ∈ N [x/x = 1]．真，x に 0 を含まないので，x/x = 1 は成り立つ．
2. ある実数 c が存在して，すべての実数 x について，x ≥ c ならば x2 − cx > 0．
∃c ∈ R, ∀x ∈ R [x ≥ c ⇒ x2 − cx > 0]．偽，x = c のとき，x2 − cx = 0 となる．
3. ある自然数 x が存在して，すべての自然数 y について，x > y + 1．
∃x ∈ N, ∀y ∈ N [x > y + 1]．偽，x = 5 のとき，y = 5 は満たさない．
4. すべての自然数 y について，ある自然数 x が存在して，x > y + 1．
∀y ∈ N, ∃x ∈ N [x > y + 1]．真，どんな y に対しても，x = y + 2 となる x が存在する．
5. ある実数 x，ある実数 y ，ある実数 z が存在して，x2 + y 2 = z 2 .
∃x ∈ R, ∃y ∈ R, ∃z ∈ R [x2 + y 2 = z 2 ]．真，x = 3, y = 4, z = 5 とすればよい．
2

Download Report