真理表 (合計 17 点)

下記の表に論理式 C∨¬(A→C)∧B の計算の途中経過と結果を記入しなさい。(10 点)

C∨¬(A→C)∧B の短い方の標準形とその名称を書きなさい。 (4 点)

(A∨B∨C) ∧ (A∨¬B∨C) ∧ (¬A∨B∨C); 乗法標準形 (連言標準形)

上記の標準形を出来るだけ短く書きなさい。 (3 点)

A∧B ∨ C

論理回路の図 / Diagrams of Boolean Circuits (10 点)

次の論理式の回路の図を書きなさい。/ Draw the circuits diagrams for the following Boolean formulæ.

掛け算のチェック (10 点)

下記の表の二つの非演算子 (非演算子 1 と非演算子 2) の掛け算が間違っている結果 (結果 1 又は結果 2) の右側の枠に×を付けなさい。間違っている結果は行ごと一つ。基数欄は非演算子と結果の基数を示す。

基数変換 (12 点)

次の表の基数変換を行いなさい。

関係の合成の推移的閉包 (6 点)

下記の行列 (大きな丸括弧省略) の推移的閉包を求め、求め方を説明しなさい。

   1 0 1
   0 1 0
   0 1 1

1 1 1
0 1 0
0 1 1

上記の配列を自分と合成する (配列の掛算、ただし足し算の代わりは ∨) と上記のようになる。これをさらにもとの行列と合成しても変わらないので、推移的閉包に達している。

用語の説明 / Explain Terms (30 点)

次の情報数学関連の英語の用語に相当する日本語の用語を書いて、簡単に説明しなさい。日本語の用語ではカタカナをできるだけ避けなさい。 / For the following English terms from Discrete Mathematics, write their Japanese equivalent and a short explanation. For the Japanese terms, avoid Katakana as much as possible.

inverse element

逆元; 群において、ある元 t の逆元は、t と演算して単位元になる

multi-valued logic

多値論理; 「真」と「偽」以外の値、例えば「分からない」、も使う論理

exponentiation

べき乗演算; xy の演算、x を y 回掛け合わせた結果

equivalence relation

同値関係; 反射的かつ対称的かつ推移的な関係

propositional variable

命題変数; 命題を表す (代表する) 変数

axiomatization

公理化; ある分野の理論を小数の (できれば自明) な公理と証明だけで作り上げる

vertex

節 (又は頂点); グラフで線や矢印でモスばれている点見ないなところ

permutation

順列; ある集合から順番を考慮して重複なしに元を選ぶときにできるものやその数

bitwise and

ビットごとかつ; 二つのビット列の同じ位のビット同士での論理積

free variable

自由変数; ある式で量記号で束縛されてない変数

proper subset

真の部分集合; 元の集合以外の部分集合

inverse relation

逆関係; ある2項関係の2項組を全て逆にしたもの

Peano Axioms

ペアノの公理; Guiseppe Peano が提案した算数を根本的な概念から作り上げる原理

positional notation

位取り表現; 場所によって数字の重みが違う数値の表現の一つ

difference set

差集合; A - B の場合、A に属しているが B に属してない元の集合

式の相対 / Duals of Formulæ (6 点)

次の式が恒真である前提の下、その双対を書きなさい。/ Write the dual of the following formulæ, assuming they are tautologies.

A ∧ B ∧ T = F ∨ B

A ∨ B ∨ F = T ∧ B

F ∨ ¬Q = ¬T ∨ T

T ∧ ¬Q = ¬F ∧ F

授業へのコメント / Comments about Course (9 点)

この授業で一番分かりにくかったことを書きなさい。 (決まった正解はありません。「英語」とだけ答えないこと。)
What was most difficult to understand in this course? (There is no definite answer. Do not simply answer "English".)

@@@@
@@@@

この授業で一番勉強になったことを書きなさい。 (決まった正解はありません。)
What topic in this course was most interesting for you? (There is no definite answer.)

@@@@
@@@@

一回目の授業では参考書の購入 (又は借り出し) と熟読が強く進められました。熟読した参考書の詳細 (文献情報) を書きなさい。参考書を読まなかった場合、その理由を書きなさい。

廣瀬健著、情報数学、
電子情報通信学会編、コロナ者

関係の表現 (24 点)

C = {2, 3, 4, 5, 6, 7} 内の関係 R で、xRy は x を y で割った余りが 1、又は y を x で割った余りが 2 の場合だけ真である。R を下記の五つの表現形式で書きなさい。

順序対の集合 (外延的記法): {(3,2),(3,5), (4,2),(4,3),(4,6), (5,2),(5,4),(5,7), (6,2),(6,5), (7,2),(7,3),(7,6)}

順序対の集合 (内包的記法): {(x,y) | x∊C ∧ y∊C ∧ (x mod y = 1 ∨ y mod x = 2)}

    0 0 0 0 0 0
    1 0 0 1 0 0
    1 1 0 0 1 0
    1 0 1 0 0 1
    1 0 0 1 0 0
    1 1 0 0 1 0

  [大きい丸括弧省略]

R の場合、授業で習った四つの関係の性質の有無を、「...である、...ではない」という形で書きなさい。
For R, for each of the four properties discussed in the course, write whether it holds or not. (4 点)
反射的ではない、対称的ではない、反対称的である、推移的ではない

ブール代数 / Boolean Algebra (合計 30 点)

[@@@] を定義しなさい。(2 点)

最大公約数は、引数を両方とも余りなく割れる最大の整数である。

[###] を定義しなさい。(2 点)

最小公倍数は、両方の引数の共通の最小の倍数である。

自然数 (正の整数) 一般において、以下の小問の法則について、それぞれ三つのことを書きなさい。①日本語の用語。②上記の [@@@] と [###] を使って、性質そのもの一つ (△ の代わりに gcd, ▽ の代わりに lcm を、関数の形式で使うこと。) ③その性質が恒真であることが分かるような説明。(それぞれ ４ 点)

例: commutative law: 交換率; gcd(a, b) = gcd(b, a); (説明: 都合により省略)

idempotent law: 冪等率; gcd(a, a) = a; a より大きい数では a を割れないが、a では a を割れるので、a は a を割れる最大の数、すなわち最大公倍数。

associative law: 結合率; lcm(lcm(a, b), c) = lcm(a, lcm(b, c)); 三つの自然数の最小公約数は、計算の順番に依存しないで同じ。

absorption law: 吸収率; gcd(a, lcm(a, b)) = a;
lcm(a,b) は a の倍数。a の倍数と a の最大公約数は a 以外ない。

distributive law: 分配率; gcd(a, lcm(b, c)) = lcm(gcd(a, b), gcd(a, c)); 素因数分解で考えるとわかる。gcd は共通の素因数だけ (すなわち、かつ)、lcm はどちらかに含まれている素因数を全部 (すなわち、または) を使う。 素因数ごとに論理式に置き換えられるので、恒真である。

自然数の集合 ℕ⁺ は、上記の法則が恒真であるにもかかわらずなぜブール代数でないかを書きなさい。(4 点)

零元は 1 ですが、単位限 (太字の 1) は、ℕ⁺ に最大数がないので存在しない。そうすると ⫬ も定義できない。その二つがないと、ブール代数の条件を満たない。

ビット列の数の証明 / Proof of Number of Bitstrings (27 点)

一定の長さ n の、ある規則を満たすビット列とそれらの数 nob(n) を長さ n = 5 までに次のテーブルで示す。(nob は「number of bitstrings」の略。)

規則を考え、書きなさい。ヒント: 1 のビットをよく見る。規則を満たさないビット列も考える。(3 点)

1 が連続ではない全てのビット列。

順番を上記の表の順番と同様にする場合、長さ6の規則を満たすビット列の最初の5個と最後の5個を書きなさい。(4 点)

最初の5個: 000000, 000001, 000010, 000100, 000101

最後の5個: 100100, 100101, 101000, 101001, 101010

規則を満たす長さ 6, 7, 8 それぞれのッビト列の場合の数を書きなさい (3 点):
nob(6) = 21       nob(7) = 34       nob(8) = 55

一般に長さ n の場合、規則に合うビット列の数を、n より小さい場合の数から計算できる式を書きなさい。その場合の n の有効範囲も書きなさい。(4 点)

式: nob(n) = nob(n-1) + nob(n-2)                          有効範囲: n >= 2

式の有効範囲以外の nob(n) の値を直接定義しなさい。(2 点) nob(0) = 1, nob(1) = 2

上記の式を数学的帰納法で証明しなさい。ヒント: 基底と仮定はそれぞれ二つ必要。式の変換は必要ない。ビット列の先頭を見るとよい。(10 点)

ステップ 1: 基底: 定義により、nob(0) = 1, nob(1) = 2、表で確認可能。
ステップ 2: 帰納: 証明したいこと: nob(k+1) = nob(k) + nob(k-1) (k>=1)
a. 仮定: nob(k) と nob(k-1) がそれぞれ長さ k、k-1 の、規則を満たすビット列の数。
b. 規則を満たす長さ k のビット列は規則を満たす k より小さい長さのビット列から作られる。
規則を満たす長さ k のビット列を二種類に分ける:
0 のビットからスタートするものと 1 のビットからスタートするもの。
0 のビットからスタートするものは、規則を満たす長さ k のビット列から、先頭に 0 を付けることで作成可能。その数は nob(k) である。 1 のビットからスタートするものは、その次のビットが 0 でないと規則に違反するため、必ず 10 からスタートする。 よって、1 からスタートするものは、規則を満たす長さ k-1 のビット列から、先頭に 10 を付けることで作成可能。その数は nob(k-1) である。 上記の二つの種類以外に規則を満たすビット列が存在しないので、合計は nob(k) + nob(k-1) である。Q.E.D.

nob に類似している授業で紹介された関数と nob(n) の関係を、関数の名称を含め書きなさい。(3 点)
nob(n) = fib(n+2); フィボナッチ関数

制限なしのビット列に対する、規則を満たすビット列の割合がちょうど 0.5 になる n を書きなさい。(1 点) n = 4

全小問の割合が 0.1 以下の最小の n を書きなさい。(2 点) n = 12

述語論理の式の作成 / Creating Formulæ of Predicate Logic (20 点)

下記の数、学生、ペットなどについての英文に相当する式を作成しなさい。授業で習った記号は全て使って構いません。学生の集合は S, ペットの集合は P、学生 s はペット p が好きということを like(s, p) で表す。それ以外、名前付きの述語、関係、関数を使わないこと。
Create the formulæ corresponding to the English sentences below about numbers, students, pets,... You can use all the symbols that were introduced in this course. Use S for the set of students, P for the set of pets, and like(s, p) to express that student s likes pet p. Do not use any other named predicates, relations, or functions.

例 / Example: Five and seven is greater than seven and five: 5+7 > 7+5

All students like all pets. ∀s∈S: ∀p∈P: like(s,p)

Every pet likes a student. ∀p∈P: ∃s∈S: like(p,s)

There is a student who likes every pet. ∃s∈S: ∀p∈P: like(s,p)

There is a student who is liked by all pets. ∃s∈S: ∀p∈P: like(p,s)

There is a student who is liked by all pets.

There is a pet that likes no student. ∃p∈P: ¬∃s∈S: like(p,s)

No students likes all pets. ¬∃s∈S: ∀p∈P: like(s,p)

Some student dislikes all pets. ∃s∈S: ∀p∈P: ¬like(s,p)

Every student likes two pets.

∀s∈S: ∃p,q∈P: p≠q ∧ like(s,p) ∧ like(s,q)

If every pet likes a student, then every student likes a pet.

(∀p∈P: ∃s∈S: like(p,s)) → (∀s∈S: ∃p∈P: like(s,p))

If a student likes a pet, then this pet also likes the student.

∀s∈S: ∀p∈P: (like(s,p) → like(p,s))

If a pet is liked by a student, then all students like this pet.

∀p∈P: (∃s∈S: like(s,p)) → (∀s∈S: like(s,p))

Only some pets like all students.

(¬∀p∈P: ∀s∈S: like(p,s)) ∧ (∃p∈P: ∀s∈S: like(p,s))

For all rational numbers, the addition of two rational numbers is a natural number.

∀a, b∈ℚ: a+b∈ℕ