第1回演習問題解答例

計算機ソフトウェア工学 第一回演習問題解答例
1
問題 I
以下の論理式が正しければ⃝，間違っていれば×を答えよ．ただし，Nat は自然数全体からなる集合 {0, 1, 2, . . .}
とする（ 0 が含まれることに注意）．
解説
論理式
真偽
∀x ∈ Nat.∀y ∈ Nat.¬(y ≥ x)
×
∀x ∈ Nat.∃y ∈ Nat.y > x
⃝
∃x ∈ Nat.∀y ∈ Nat.x > y
×
∃x ∈ Nat.∀y ∈ Nat.((¬(y ≥ x)) ∨ x > 1)
⃝
∀x ∈ Nat.∀y ∈ Nat.(x ≤ 0 ⇒ y ≥ x)
⃝
∀x ∈ Nat.∃y ∈ Nat.(x < 0 ⇒ y < 0)
⃝
１番の ¬(y ≥ x) の部分は，y < x と等価．例えば x = 0, y = 1 とすれば成り立たないので×．
3 番目は，どんな x を選んでも，y として x を選べば y > x は成立しないので×．
4 番目は，x = 2 とすれば，x > 1 が成り立つので，残りの部分には関係なく正しい．
5 番目は，x ≤ 0 という前提から x = 0 なので，任意の y について y ≥ x(= 0) が成り立つ．
6 番目は，どんな x を選んでも，x < 0 という前提が偽なので，x < 0 ⇒ y < 0 は真．
問題 II
次の命題を論理式で表せ．
1.
どんな自然数 x についても，x = 2y または x = 2y + 1 を満たす自然数 y が存在する．
答： ∀x ∈ Nat.∃y ∈ Nat.(x = 2y ∨ x = 2y + 1)
2.
ある自然数 x が存在して，x はどんな自然数 y よりも小さいか等しい．
答： ∃x.∀y.(x ≤ y)
計算機ソフトウェア工学 第一回演習問題解答例
2
問題 III
X = {0, 1, 2}, Y = {1, 2, 3} とする．以下の集合の要素を書き下せ．ただし，関係 ≤ は自然数に関する通常の大
小関係とする（つまり，x ≤ y は x が y 以下であることを表す）．
X ∪Y
0, 1, 2, 3
X ∩Y
1, 2
X ×Y
(0, 1), (0, 2), (0, 3), (1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3)
∅, {1}, {2}, {3}, {1, 2}, {2, 3}, {3, 1}, {1, 2, 3}
Y
2
{x ∈ X | ∃y ∈ Y.x ≥ y}
{x ∈ 2X | 0 ∈ x}
≤ ∩(X × Y )
{(0, 1), (1, 2)}
解説
∗
1, 2
{0}, {0, 1}, {0, 2}, {0, 1, 2}
(0, 1), (0, 2), (0, 3), (1, 1), (1, 2), (1, 3), (2, 2), (2, 3)
(0, 0), (1, 1), (2, 2), (0, 1), (0, 2), (1, 2)
{x ∈ X | ∃y ∈ Y.x ≥ y} は，X の要素 x のうち，ある Y の要素 y 以上のものからなる集合．
{x ∈ 2X | 0 ∈ x} は，X の部分集合のうち，0 を要素に持つものの集合．
問題 IV
以下の集合が可算集合であるか否かを理由と共に答えよ．
1.
文字 a と b のみからなる有限長の列の集合 · · · 可算集合
a, b を 0, 1 でおきかえ，先頭に 1 を追加したものを自然数の 2 進表示とみなせば，文字 a と b のみからなる
有限長の列の集合から自然数の集合への単射が得られる．逆に自然数の 2 進表示の 0,1 を a,b で置き換えれば
自然数の集合から文字 a と b のみからなる有限長の列の集合への単射が得られる．
2.
文字 a と b のみからなる無限列の集合 · · · 非可算集合
仮に可算集合だとすると，すべての無限列に s0 , s1 , s2 , . . . と番号づけすることができる．ここで，文字列 s を
{
a if sn (n) 6= a
s(n) =
b if sn (n) = a
によって定義する（ s(n) は s の n 番目の文字を表す）．s は a, b からなる無限列なので sm = s を満たす m が
存在するが，sm (m) = a ⇔ s(m) = a ⇔ sm (m) 6= a となり矛盾．よって文字 a と b のみからなる無限列の集
合は非可算．
3.
C 言語のプログラムの集合 · · · 可算集合
プログラム中に使用できる文字の種類は有限，プログラムはそれらの有限列なので、(1) と同様．