ブール代数 / Boolean Algebra (12 点)

基数変換 / Base Conversions (12 点)

次の表の基数変換を行いなさい。/ Carry out the base conversions in the following table.

真理表、標準形、単純化 / Truth Table, Normal Forms, and Formular Simplification (40 点)

論理式 A = XOR(D, E) ∨ ¬E ∧ (C→D) について、 次の問題に回答しなさい。
Answer the following subproblems for the logical formula A = XOR(D, E) ∨ ¬E ∧ (C→D).

下記の真理表に論理式 A の計算の途中経過と結果を記入しなさい。
Complete the truth table below with the intermediate and final results for formula A. (12 点)

論理式 A の二つの標準形とその名前を書きなさい。/ Write the two normal forms for formula A, and their names. (10 点)

短い方の標準形 / shorter NF: 名前/name: 乗法標準形
式/formula: (C∨¬D∨¬E) ∧ (¬C∨D∨E) ∧ (¬C∨¬D∨¬E)

長い方の標準形 / longer NF: 名前/name: 加法標準形
式/formula: ¬C∧¬D∧¬E ∨ ¬C∧¬D∧E ∨ ¬C∧D∧¬E ∨ C∧¬D∧E ∨ C∧D∧¬E

論理式 A を基本的な論理演算子 (∧、∨、¬) のみの式に段階的に変換し、できるだけ単純化してください。段階ごとに、どの様な性質を使ったかを書きなさい。 同じ性質を複数並行に使うときには一つの段に記入してよい。立て続けに同じ性質を使うときには別の段に記入しなさい。 交換律と結合律の使用はまとめて一段に記入しなさい。/ Step by step simplify formula A as much as possible, to use only the basic logical operators (∧、∨、¬). For each step, indicate the law used. When applying the same law in parallel, use a single step. When applying the same law in sequence, use multiple steps. Use a single step for commutative and associative laws together.(18 点)

ヒント 1: XOR(X, Y) を「XOR の定義」で ¬(X↔Y) に変換できます。
Hint 1: XOR(X, Y) can be converted to ¬(X↔Y) in a single step using "definition of XOR".

ヒント 2: 単純化の結果を片方の標準形と比較することで、結果の確認ができます (カルノー図表の応用)。
Hint 2: The result of the simplification can be checked using one of the normal forms, and the Karnaugh map.

論理回路の図 / Circuit Diagram (10 点)

次の論理式に相当する回路の図を書きなさい。/ Write the circuit diagrams corresponding to the following logic formulæ.

用語の説明 / 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.

total order

全順序 (全形順序); 全ての要素の間順序が決まっている関係

digital root

数字根; ある数の各桁の和を、一ケタになるまで取り続けた結果

Cartesian product (set)

直積 (集合); 複数の集合からすべての組み合わせを選んだ順序対や n字組の集合

difference set

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

Peano Axioms

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

Abelian group

可換群; 交換律が成り立つ群

inverse relation

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

congruence class

合同類; (ある法に対し) 合同である数全てを含まれる集合

absorption law

吸収律; A ∧ (A∨B) = A など

bitwise or

ビットごと又は; 二つのビット列の同じ位のビット同士での又は

bound variable

束縛された変数; ある量記号の影響の下の変数

proof by contradiction

背理法; 矛盾を使った証明の方法

equivalence relation

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

transitive closure

推移的閉包; ある関係を結果が変わらなくなるまで自分と結合した結果

tautology

恒真; 常に真の論理式

関係の表現 / Representations for a Relation (34 点)

集合 P = {4, 5, 6, 7, 8, 9} 内の関係 R は下記の表で与えられている。R を残りの四つの表現形式で書きなさい。
The relation R on the set Q = {4, 5, 6, 7, 8, 9} is given below as a matrix. Write the remaning four representations of R.

           0 1 0 1 0 1
           1 0 1 0 1 0
           0 1 0 1 0 1
           1 0 1 0 1 0
           0 1 0 1 0 1
           1 0 1 0 1 0
           [大きい丸括弧省略]
        

順序対の集合 (内包的記法) / set of ordered pairs (connotation) (4 点):
{(x,y) | x∊P ∧ y∊P ∧ (y+x) mod 2 = 1)}

順序対の集合 (外延的記法) / set of ordered pairs (denotation) (4 点): {(4,5), (4,7), (4,9), (5,4), (5,6), (5,8), (6,5), (6,7), (6,9), (7,4), (7,6), (7,8), (8,5), (8,7), (8,9), (9,4), (9,6), (9,8)}

  1 0 1 0 1 0
  0 1 0 1 0 1
  1 0 1 0 1 0
  0 1 0 1 0 1
  1 0 1 0 1 0
  0 1 0 1 0 1
  (大きい丸括弧省略)

木による式の構造の表現 / Representing the structure of formulæ by trees (12 点)

次の式を木の形で書きなさい。/ Write the following formulæ as trees.

    20 / 3 * 5 / 7     XOR(D, E) ∨ ¬E ∧ (C→D)     15 - 3 / 7 - 12

  [図省略]

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

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

There is a student who likes all actors. ∃s∈S: ∀m∈M: like(s, m)

All actors like all students. ∀m∈M: ∀s∈S: like(m, s)

Every student likes an actor. ∀s∈S: ∃m∈M: like(s, m)

There is an actor who is liked by every student. ∃m∈M: ∀s∈S: like(s, m)

No actor likes any student. ¬∃m∈M: ∃s∈S: like(m, s)

There is an actor who dislikes all students. ∃m∈M: ∀s∈S: ¬like(m, s)

Every actor is liked by a student. ∀m∈M: ∃s∈S: like(s, m)

An actor who likes a student is also liked by that student.
∀m∈M: (∃s∈S: (like(m,s) → like(s,m))

No student likes all actors.
∀s∈S: ¬∀m∈M: like(s, m)

Any student who likes an actor also likes another actor.
∀s∈S: (∃m1∈M: like(s, m1) → (∃m2∈M: m1≠m2 ⋏ like(s, m2))

All actors who do not like any students are not liked by any students. ∀m∈M: ((∀s∈S: ¬like(m, s)) → ∀s∈S: ¬like(s, m))

There are more actors taller than 200cm than students smaller than 150cm.
|{m|m∈M ∧ height(m)>200}| > |{s|s∈S ∧ height(m)<150}|

No two students like the same actor.
∀s1∈S, s2∈S: s1≠s2 → {m|m∈M ∧ like(s1,m)}∪{m|m∈M ∧ like(s2,m)} = {}

All actors over 250cm height like all students, but there is no actor who likes any student.
(∀m∈M: (height(m)>250 → ∀s∈S: like(m, s))) ∧ ¬∃m∈M: ∃s∈S: like(m, s)

If exactly two students like all actors, then these students are liked by all actors.
∃s1∈S: ∃s2∈S: (∀m∈M: like(s1,m)∧like(s2,m)) → ∀m∈M: like(m,s1)∧like(m,s2)

群と合同算術 / Groups and Modular Arithmetic (31 点)

n>0 が素でない場合、{1, ..., n-1} から n とお互いに素でない (二つの数の最大公約数が1でない) 数を除いた集合と mod n の掛け算で群が作れることも知られている。/ It is also known that a group can be formed for any non-prime n>0, by removing any numbers co-prime with n (i.e. where the GCD of the two numbers is not 1) from the set {1, ..., n-1} and multiplication modulo n.

n=9 の場合、この集合は {1, 2, 4, 5, 7, 8} となる。/ For n=9, this set is {1, 2, 4, 5, 7, 8}.

n=14 の場合、この集合を書きなさい。Write this set for n=14. (3 点) {1, 3, 5, 9, 11, 13}

上記の四つの積表の群の間で、すぐ同形と判断できる二つを部分問題番号で列挙し、理由を説明しなさい。/ For the four groups above with Caley tables, list up (by using the number of the subproblem) the two groups that can immediately be identified as isomorphic, and explain the reason. (3 点)

部分問題 1 と 5 の群が銅系である。1→1, 3→2, 7→3, 9→4 が対応し、要素の配置が全く同じのため。

上記の四つの責表の群のうち、他の群と絶対同形でない群を部分問題番号で特定し、その理由を説明しなさい。/ For the four groups above with Caley tables, identify (by the number of the subproblem) the group that is definitely not isomorphic to any of the other groups, and explain the reason. (3 点)

部分問題 4 の群では単位元が対角線上にある (どの元も自分の逆元である) ので、他の群と同形でない。

残りの一つの群はどうやって、ほかのどの群と同形なのかすぐわかるようにできるかを説明しなさい。必要に応じて責表を使いなさい。/ For the one remaining group, explain how to make sure that it is easy to see which other group(s) it is isomorphic to. If necessary, use a Caley table. (6 点)

部分問題 2 の責表で最後の二つの行と列を交換すると、次の積表ができる。0→1, 1→2, 3→3, 2→4 で部分問題 1 の群との同形がすぐわかる。

数式の証明 (16 点)

最初の n-1 個の正の整数の二乗の合計が (n-1)·n·(2n-1)/6 であることを証明しなさい。
Prove that the sum of the squares of the first n-1 positive integers is (n-1)·n·(2n-1)/6.
例えば / As an example, n=6 の場合、1 + 4 + 9 + 16 + 25 = 5·6·11/6

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

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

¬B ∨ F = ¬C∧T: ¬B ∧ T = ¬C ∨ F

¬X∧F = ¬F∧X: ¬X ∨ T = ¬T ∨ X

授業へのコメント / 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.)

@@@@

一回目の授業では参考書の購入 (又は借り出し) と熟読が強く進められました。熟読した参考書の詳細を書きなさい。
In the first lecture, I recommended to read a textbook in parallel to the lecture. Which textbook did you read?

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