真理表 / Truth Table (24 点)

下記の真理表に論理式 ¬K∨H∧¬G の計算の途中経過と結果を記入しなさい。
In the truth table below, enter the intermediate and final results for the calculation of the Boolean formula ¬K∨H∧¬G (12 点)

論理式 ¬K∨H∧¬G を標準形で書きなさい。二つの標準形のうち短い方を使いなさい (4 点)。
Write the formula ¬K∨H∧¬G in normal form. Of the two normal forms, choose the shorter one.

(G∨H∨¬K) ∧ (¬G∨H∨¬K) ∧ (¬G∨¬H∨¬K)

次の論理式に相当する論理回路の図を書きなさい (各 4点)。
Draw the logic circuits diagrams for the following Boolean formulæ.

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

三つのビットのビット列から作成されるブール代数のハッセ図を書きなさい (8 点)。
Draw the Hasse diagram for a Boolean algebra created from bit strings of length 3.

上記のブール代数について各情報を表に書き込みなさい (6 点)。
For the Boolean algebra above, complete the following table.

五つのビットを使うビット列のブール代数について、下記の要素について半順序関係を次の記号で表しなさい (3 点)。
For a Boolean algebra created from bit strings of length 5, express the partial order relationship using the following symbols.

a ≦ b ∧ b ≦ a … a = b ; a ≦ b ∧ b ≰ a … a < b ; a ≰ b ∧ b ≦ a … a > b ; a ≰ b ∧ b ≰ a … a ? b

ブール代数一般の場合、どうやって半順序を演算子 △ (又は ▽) で表すのか示しなさい (3 点)。
For Boolean algebras in general, show how you can use the operator △ (or ▽) to express the partial order relation.

a ≦ b ⇔ a ▽ b = b (又は a △ b = a)

逆に、▽ (又は a △) の演算の結果を、半順序を使って表しなさい (ヒント: 結果を大きさ 1 の集合で表しなさい; 6 点)。 / In reverse, express the result of the ▽ (or ▽) operation using the half-order (hint: express the result as a set with one element).

{a △ b} = { x | x ∈ B ∧ x≦a ∧ x≦b ∧ (¬∃y∈B: (y≠x ∧ x≦y ∧ y≦a ∧ y≦b)) }
(又は {a △ b} = { x | x ∈ B ∧ a≦x ∧ b≦x ∧ (¬∃y∈B: (y≠x ∧ y≦x ∧ a≦y ∧ b≦y)) })

関係の表現 / Representations of a Relation (26 点)

集合 A = {0, 1, 2, 4, 6, 8} 内の関係 R は下記の行列で定義されている。関係 R の他の四つの表現形式を書きなさい。
The relation R on set A = {0, 1, 2, 4, 6, 8} is defined by the matrix below. Write the remaining four different representations of this relation.

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


 [大きい丸括弧省略
big parentheses left out]

  a | b     a | b
  -----     -----
  0 | 4     4 | 0
  0 | 6     6 | 0
  0 | 8     6 | 1
  1 | 6     8 | 0
  1 | 8     8 | 1
  2 | 8     8 | 2

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

順序対の集合 / set of ordered pairs (内包的記法 / connotation) (6 点): { (a, b) | a∊A ∧ b∊A ∧
(2a+4 ≦ b ∨ a/2-2 ≧ b) }

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

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

この授業で一番分かりにくかったことを書きなさい。 (決まった正解はありません。「英語」とだけ答えないこと。)
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.)

@@@@
@@@@

数式の証明 (16 点)

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

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

次の情報数学関連の英語の用語に相当する日本語の用語を書いて、簡単に説明しなさい。単にカタカナ表記にするのは避けること。
For the following English terms from Discrete Mathematics, write their Japanese equivalent and a short explanation. Do not just use Katakana.

symbolic logic

記号論理; 記号を使って法則にしたがって論理; 二値論理や多値論理等存在

total order

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

quadruple

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

bound variable

束縛変数; 量記号で束縛されている変数、作用領域以外は使用禁止

hexadecimal

十六進数 (の); 基数が16の数値の記述方法 (形容詞)

proof by counterexample

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

operator

演算子; 演算の種類を示す記号、+, -, ⋏, ¬ など

proposition

命題; 観客的に真か偽か決まっている文、質問や意見ではない

duality principle

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

axiomatization

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

universal quantifier

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

proper subset

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

交換律と結合律の比較 / Comparing Commutative and Associative Laws (22 点)

交換律と結合律を比べると、交換律が簡単に見える。しかし、いくつかの例から、結合律が根本的で簡単であることがうかがえる。下記の分野の例を説明しなさい。
When comparing the commutative law and the associative law, it looks as if the commutative law is simpler. However, from various examples, one can guess that the associative law is more fundamental and easier. Explain this for the example areas given below.

ペアノ算術 / Peano arithmetic (5 点)

ペアノの公理を使って足し算の交換律も結合律も証明できるが、結合律の証明が簡単に比べ、 交換律では二段階の数学的帰納法も必要し、結合律も使う必要があるので、結合律が簡単に見える。

群論 / Group theory (5 点)

結合律は群の一つの条件である。しかし交換律は「可換群 (アベル群)」と言われる一部の郡でしか成り立たない。 半群も単位元や逆元がないにもかかわらず、交換律がある。よって、交換律の方が根本的な法則だと思われる。

関係の合成について、結合律が成り立つことを、合成の定義を使って見せなさい (7 点)。
Show that composition of relations is associative using the definition of composition.

関係 P と Q の合成 P∘Q は P∘Q = {(x,z)| (x,y) ∈ P ∧ (y,z) ∈ Q} と定義されている。
関係 P, Q, R の場合、(P∘Q)∘R = P∘(Q∘R) を示さないといけません。
(P∘Q)∘R = {(x,w)| (x,z) ∈ P∘Q ∧ (z,w) ∈ R} のなかで (x,z) の条件を P∘Q から代入すると
(P∘Q)∘R = {(x,w)| (x,y) ∈ P ∧ (y,z) ∈ Q ∧ (z,w) ∈ R} となる。同じ結果は P∘(Q∘R) でも
P∘(Q∘R) = {(x,w)| (x,y) ∈ P ∧ (y,w) ∈ (Q∘R)} 経由で得られるので、
関係の合成について、結合率が成立する。

関係の合成について、交換律が成り立たないことを示しなさい (5 点)。
Show that composition of relations is not commutative.

関係 P が集合 A と B の直積の部分集合で、
関係 Q が集合 B と C の直積の部分集合の場合、P∘Q が可能ですが、
Q∘P でそもそも集合が合わないので、不可能。よって、交換律が成立しない。

論理関数の単純化 / Simplification of a Logic Formula (8 点)

¬S∧R ∨ ¬(S∨R) の式を段階的に単純化し、それぞれの段階でどのような性質や法則を使ったかを書きなさい。
Simplify the formula ¬S∧R ∨ ¬(S∨R) in stages, indicating at each stage which property or law you used.

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

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

例 / Example: All natural numbers are greater than -1: ∀n∈ℕ: n > -1

There is a rational number that is not an integer.

∃x∈ℚ: x∉ℤ

Every rational number is equal to the quotient of two integers.

∀q∈ℚ: ∃m,n∈ℤ: q = m/n

The size of the powerset of a set is 2 to the power of the size of the set.

|P(A)| = 2^|A|

Equivalence is transitive.

∀a,b,c∈{T, F}: a↔b ∧ b↔c ⇒ a↔c

Disjunction is associative and commutative.

∀a,b,c∈{T, F}: ((a∨b)∨c = a∨(b∨c)) ∧ (a∨b = b∨a)

Addition and multiplication for reals distribute over each other.

∀a,b,c∈ℝ: (ab + c = (a+c) · (b+c)) ∧ ((a+b) · c = ac + bc)

All students eat all fruits.

∀s∈S: ∀f∈F: eat(s,f)

Every fruit is eaten by at least one student.

∀f∈F: ∃s∈S: eat(s,f)

Not all students eat some fruit.

¬∀s∈S: ∃f∈F: eat(s,f)

Every student eats at least three fruits.

∀s∈S: |{f|f∈F ∧ eat(s,f)}| ≧ 3

There is a fruit that is not eaten by all students.

∃f∈F: ¬∀s∈S: eat(s,f)

There is no fruit that is eaten by all students.

¬∃f∈F: ∀s∈S: eat(s,f)

基数変換 / Base Conversion (13 点)

下記の基数変換の表を完成しなさい。 / Complete the base conversions in the table below.

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

次の表の計算を行いなさい。結果は被演算子と同じ基数を使って書きなさい。
Complete the calculations in the table below. For the result, use the same base as the operators.