一般的の性質の書き方 / Writing Laws in General Form (12 点)

二つの架空の演算子「∆」と「∇」で次の性質で考えられる書き方を全て列挙しなさい。
Using two imaginary operators ∆ and ∇, list all possible forms of the laws given below.

べき等律 / Idempotent Law

a∆a=a, a∇a=a

交換律 / Commutative Law

a∆b=b∆a, a∇b=b∇a

結合律 / Associative Law

(a∆b)∆c=a∆(b∆c), (a∇b)∇c=a∇(b∇c)

吸収律 / Absorption Law

a∆(a∇b)=a, a∇(a∆b)=a

分配律 / Distributive Law

a∆(b∇c)=(a∆b)∇(a∆c), (a∆b)∇c=(a∇c)∆(b∇c),
a∇(b∆c)=(a∇b)∆(a∇c), (a∇b)∆c=(a∆c)∇(b∆c)

基数変換 / Base Conversions (12 点)

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

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

duality principle

双対原理; 論理演算において恒心の式で T と F、又はとかつを入れ換えられる原理

multi-valued logic

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

deduction

演繹; 一般の原理から特定な場合を推論

proper subset

真の部分集合; 元の集合以外の部分集合、⊊とも書く

quintuple

五項組 (五字組); 順序が決まった五つの項目の組; 例: (a, b, c, d, e)

universal quantifier

全称限量子 (全称記号); 集合の全ての要素の場合、述語が成立することを表す記号

odd number

奇数; 偶数の反対で、2で割れない整数

greatest common divisor

最大公約数; 複数の整数をすべて割り切れる最大の数

proof by counterexample

反例による証明; 反例を使って、ある仮設が成り立てないことを証明する

inverse element

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

tautology

恒真; 常に真の論理式

free variable

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

digit sum

数字和; ある数の各桁の和

axiomatization

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

transitive closure

推移的閉包; ある二項関係を変わらないまで自分と繰り返し合成した結果

標準形 / Normal Forms (10 点)

三つの論理変数 A, B, C のうちちょうど一つの変数だけが T のときだけに T になる論理関数の短い方の標準形とその名称を書きなさい。/ Write the normal form for the Boolean function of three variables A, B, C where the function returns T if and only if exactly one of the variables is T, and the normal form's name. (5 点)

名称 / Name: 加法標準形

式 / Formula: ¬A∧B∧C ∨ A∧¬B∧C ∨ A∧B∧¬C ¬A∧¬B∧C ∨ A∧¬B∧¬C ∨ ¬A∧B∧¬C

標準形が「T」または「F」になる場合がある。その条件と理由を説明しなさい。
There are cases when a normal form becomes "T" or "F". Explain when and why. (5 点)

加法標準形の場合、関数の結果が必ず F の論理関数の標準形が「F」で、乗法標準形の場合、関数の結果が必ず T の場合「T」になる。 理由は、普通の作り方で式の功の数が 0 なので、演算子の単位元を使わないといけないです。

真理表 / Truth Table (12 点)

下記の表に論理式 XOR(Q, R) ∨ (P→Q) ∧ ¬R の計算の途中経過と結果を記入しなさい。
Enter the intermediate and final results for the logical formula XOR(Q, R) ∨ (P→Q) ∧ ¬R into the table below.

n 進法での計算 / Calculations in Base n (8 点)

次の表の計算を行いなさい。結果は被演算子と同じ基数を使って書きなさい。
Perform the calculations in the following table. Write the result in the same base as the operands.

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

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

関係の表現 (28 点)

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

        2 3 4 5 6 7

   2    0 0 0 1 1 1
   3    1 0 0 0 1 1
   4    0 1 0 0 0 1
   5    1 0 1 0 0 0
   6    0 0 0 1 0 0
   7    1 1 0 0 1 0

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

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

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

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

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

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

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

There is a student who likes a book. ∃s∈S: ∃b∈B: like(s, b)

All wands like all students. ∀w∈W: ∀s∈S: like(w, s)

There is a student who likes all wands. ∃s∈S: ∀w∈W: like(s, w)

There is a book that is liked by all students. ∃b∈B: ∀s∈S: like(s, b)

There is a student who dislikes all books. ∃s∈S: ∀b∈B: ¬like(s, b)

All students own a wand or a book. ∀s∈S: (∃w∈W: own(s, w)) ∨ (∃b∈B: own(s, b))

Every student own all books that he/she likes. ∀s∈S: ∀b∈B: like(s, b) → own(s, b)

If a wand likes a student, then the wand is also liked by that student.
∀w∈W: ∀s∈S: (like(w,s) → like(s,w))

Any student who owns a book owns a wand.
∀s∈S: (∃b∈B: own(s, b)) → (∃w∈W: own(s, w))

There is a student who owns five (or more) books but no wands.
∃s∈S: |{b|b∈B⋏own(s, b)}|≧5 ⋏ ¬∃w∈W: own(s, w)

No two students own the same wand.
¬∃w∈W: ∃s1,s2∈S: s1≠s2 ⋏ own(s1,w) ⋏ own(s2,w)

Only some wands like all books.
(¬∀w∈W: ∀b∈B: like(w,b)) ∧ (∃w∈W: ∀b∈B: like(w,b))

No two students own exactly the same set of books.
∀s1∈S, s2∈S: s1≠s2 → {b|b∈B ∧ own(s1,b)}≠{b|b∈B ∧ own(s2,b)}

The maximum of books owned by a student is smaller than the number of students who own a wand.
∀s∈S: |{b|b∈B ∧ own(s,b)}| < |{t|t∈S ∧ ∃w∈W: own(t, w)}|

For all rational numbers, there is a product of a complex number and an integer that is smaller than the rational number. ∀a∈ℚ: ∃b∈ℂ: ∃c∈ℤ: bc < a

ブール代数と群 / Boolean Algebras and Groups (合計 33 点)

全てのブール代数は群でもある。ビット列のブール代数の場合、群の演算がビット毎排他的又は (XOR) である。/ All Boolean Algebras are also groups. In the case of Boolean Algebras for bit strings, the group operation is exclusive or (XOR).

ビット列の長さ n の場合の群の単位元は何なのかを書きなさい。
Describe the identity element of the group of bitstrings of length n. (2 点)

全て 0 の長さ n のビット列。

集合 A の冪集合で作られるブール代数に対応する群の単位元を書きなさい。
Write the identity element of the groups corresponding to Boolean Algebras of powersets of some set A. (2 点)

{}

任意の元 g の逆元は何なのかを書きなさい。/ Describe the inverse element of an arbitrary element g of a group (2 点)

任意の g の逆元は g そのものである。

真偽値の XOR 演算を三つの基本的な論理演算で書きなさい。
Write XOR of Boolean values (T, F) in terms of the three basic logic operations. (3 点)

XOR(A,B) = ¬A∧B ∨ A∧¬B [又は/or (¬A∨¬B) ∧ (A∨B)]

冪集合で作られるブール代数の二つの元 (集合) K と M において、対応する群の演算 • を定義しなさい。/ For two sets K and M that are elements of a Boolean Algebra on a powerset, define the corresponding group operation •. (3 点)

K • M = K^c∩M ∪ K∩M^c [又は/or (K^c∪M^c) ∩ (K∪M)]

上記の単位限・逆元以外で群の公理として確認する必要がある条件を説明しなさい。
Explain what group axiom needs to be checked besides the existence of identity element and inverse elements. (2 点)

確認すべきのは群の演算の結合率が成り立つこと。

なぜ例えば (ビット列においての) ビット毎かつや (冪集合においての) 積集合で群が作れないのかを説明しなさい。
Explain why e.g. bitwise and (on bistrings) or set intersection (on powersets) cannot be used as a group operation. (3 点)

群の積表では各行・列に全ての要素がちょうど一回現れる筈ですが、この演算では成り立たないそ。

二つのブール変数の関数は合計16個ある。ビット列にビット毎に適応された場合、XOR 以外群の演算として考えられるブール関数を当てて説明してください。/ There are 16 Boolean functions of two Boolean variables. Guess and explain which of these functions besides XOR, when applied bitwise to bitstrings, may be the operation of a group. (3 点)

ビット毎同値。単位限は1だけのビット列で、逆元は要素そのもの。結合率は確認する必要があります。

式の証明 / Proof of a Formula (12 点)

n ≧ 1 の場合、1³ + 2³ + ... + n³ = 1/4 n²(n+1)² を証明しなさい。
Prove that for n ≧ 1, 1³ + 2³ + ... + n³ = 1/4 n²(n+1)².

数学的帰納法を使って証明する。
基底: n=1: 1³ = 1/4 1²(1+1)² = 1
帰納: 1³ + 2³ + ... + k³ = 1/4 k²(k+1)² を前提として 1³ + 2³ + ... + (k+1)³ = 1/4 (k+1)²(k+2)² を証明できればよい。
1³ + 2³ + ... + (k+1)³ = [前提導入]
= (1/4 k²(k+1)²) + (k+1)³ =
= 1/4 (k²(k+1)² + 4(k+1)²(k+1)) =
= 1/4 (k²+4k+4)(k+1)² =
= 1/4 (k+1)²(k+2)² で証明完了。

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

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

    4 - 3 * 7 + 5     XOR(NAND(Q, P), X)     B∨¬G∧H

      +                        XOR                          ∨
     / \                       / \                         / \
    -   5                   NAND  X                       B   ∧
   / \                      /  \                             / \
  4   *                    Q    P                           ¬   H
     / \                                                  |
    3   7                                                 G

合同算術による剰余の計算 / Calculating Remainders using Modular Arithmetic (8 点)

次の剰余演算を途中経過も含め計算しなさい。/ Calculate the following remainders, including intermediate results

    57¹⁰ mod 61

57¹⁰ ≡₆₁ -4¹⁰ = 4¹⁰ = (4³)³·4 = 64³·4 ≡₆₁ 3³·4 = 27·4 = 54·2 ≡₆₁ -7·2 = -14 ≡₆₁ 47

    6⁵⁶ mod 31

6⁵⁶ = (6²)²⁸ = 36²⁸ ≡₃₁ 5²⁸ = (5²)¹⁴ = 25¹⁴ ≡₃₁ (-6)¹⁴ = ((-6)²)⁷ = 36⁷ ≡₃₁ 5⁷ = 25³·5 ≡₃₁ (-6)³·5 = 36·-30 ≡₃₁ = 5·1 = 5