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

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

Division of natural numbers is associative.
∀a,b,c∈ℕ: (a/b) / c = a / (b/c)

The modulo operation is commutative for integers.
∀a,b∈ℤ: a mod b = b mod a

For rational numbers, subtraction distributes over multiplication.
∀a,b,c∈ℝ: (a·b) - c = (a-c) · (b-c)

There is a real number that is bigger than any natural number.
∃x∈ℝ: ∀a∈ℕ: a<x

All students like all authors.
∀s∈S: ∀a∈A: like(s, a)

Every author likes a student.
∀a∈A: ∃s∈S: like(a, s)

There is an author who likes all books.
∃a∈A: ∀b∈B: like(a, b)

No student likes all authors.
¬∃s∈S: ∀a∈A: like(s, a)

There is an author who dislikes all students.
∃a∈A: ∀s∈S: ¬like(a, s)

There is a book that is not liked by any student.
∃b∈B: ∀s∈S: ¬like(s, b)

There is a student who likes all autors taller than him/her.
∃s∈S: ∀a∈A: height(a)>height(s) → like(s, a)

All autors who do not like any books are not liked by any students.
∀a∈A: ((∀b∈B: ¬like(a, B)) → ∀s∈S: ¬like(s, a))

There is an author who wrote more books than his/her height in cm.
∃a∈A: |{b|wrote(a,b)}| > height(a)

No two students like the same sets of books.
∀s,t∈S: s≠t → {b|b∈B ∧ like(s,b)} ≠ {b|b∈B ∧ like(t,b)}

If a student likes a book, then he/she likes the author(s) of that book.
∀s∈S: ∀b∈B: like(s, b) → (∀a∈A: wrote(a, b) → like(s, a))

If a student likes any author, then he/she likes (exactly) three books.
∀s∈S: ∀a∈A: like(s, a) → |{b|b∈B ∧ like(s,b)}| = 3

真理表 / Truth Table (30 点)

下記の表を、論理式 ¬C∨¬A∧(B→A) の計算の途中経過と結果を記入しなだら完成しなさい。
Complete the table below, give the intermediate and final results for the Boolean formula ¬C∨¬A∧(B→A). (14 点)

上記の論理式の短い標準形とその名前を書きなさい。
Give the shorter normal form for the above formula, and its name. (4 点)

名前/name: 乗法標準形
式/formula: (A∨¬B∨¬C) ∧ (¬A∨B∨C) ∧ (¬A∨¬B∨¬C)

両方の標準形の名前を使いながら、短い方をどうやって特定できるか説明しなさい。
Using the names of both normal forms, describe how to decide which one is shorter. (4 点)

真理表の結果の列をみて、T が少なかったら加法標準形、F が少なかったら乗法標準形が短いです。

標準形の特徴を四つ列挙しなさい。/ List up four properties of the normal forms. (8 点)

1. 作成は手間がかかるが、簡単
2. どのブール関数に対しても作成可能
3. 式が浅い (回路で実装すると早い)
4. 式が長くなる可能性がある (回路は場所を要する)

公理系 / Axiomatic Systems (10 点)

次の数学の分野で有名な公理系の作成者・発見者を指定した数、書きなさい。/ Give the given number of famous creators of axiom systems for the following Mathematical fields. (5 点)

ブール論理とブール代数 / basic (Boolean) logic and Boolean algebra (3)

Huntington, Sheffer, Wolfram

平面幾何学 / plane geometry (1)

ユークリッド

自然数 / natural numbers (1)

ペアノ

公理系に必ず必要な性質を列挙しなさい。/ List the properties that all axiom systems should have. (3 点)

一貫性、完全 (性)、最小 (性)

さらに、理想な公理系の性質を列挙しなさい。/ List the additional properties that an ideal axiom system should have. (2 点)

単純性、明白 (性)

論理回路の図 / 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.

transitive closure

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

digit sum

数字和; ある数の各桁の和、例えば 12345 の数字和は 15

quadruple

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

Karnaugh map

カルノー図表; 論理関数を単純化するための図表

multi-valued logic

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

duality principle

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

vertex

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

positional notation

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

proposition

命題; 客観的に真か偽が判断できる文 (質問でもない)

free variable

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

disjunction

論理和; ∨ の演算子で表すに二項演算、両方の日演算子が偽なら偽、それ以外真

Cartesian product (set)

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

Abelian group

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

absorption law

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

octal

八進数(の); 数を 0-7 の八つの記号で表す位取り表現

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

集合 C = {4, 5, 6, 7, 8, 9} 内の関係 R が、xRy は x と y がそれぞれ 3 で割った時の余りが同じである場合、成立する。R を下記の五つの表現形式で書きなさい。/ The relation xRy on the set C = {4, 5, 6, 7, 8, 9} includes all elements for which the remainder when deviding x and y by 3 is the same.

順序対の集合 (内包的記法, 4 点): {(x,y) | x∊P ∧ y∊P ∧ (x mod 3) = (y mod 3)}

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

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

  [大きい丸括弧省略]

下記の表の第一列に授業で習った関係の性質の名称を書きなさい。第二列には、R についてその性質の有無を (〇か×で) で記入しなさい。第三列にはこの性質を逆転 (〇→× 又は ×→〇) するために必要な操作 (R の要素の追加や削除) を記述しなさい。なお、他の性質への影響は無視してよい。/ Fill in the first column of the table below with the names of the properties of relations discussed in the course. In the second column, indicate whether the property holds (〇) or not (×) for R. In the third column, indicate how the property can be inversed (〇→× or ×→〇) by adding or removing some elements. You can ignore the effect on other properties. (12 点)

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

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

    NAND(P, ¬Q) ∨ (X→Y) ∧ R     4 - 7 + 8 - 3     35 * (7 mod 3) - 9 / 4.0+2.1

  [図省略]

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

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

数学的帰納法を使って証明する。
基底: n=1: 1·2 = 2 = 1·2·3/3
帰納: 1·2 + 2·3 + ... + k·(k+1) = k·(k+1)·(k+2)/3 を前提として
1·2 + 2·3 + ... + k·(k+1) + (k+1)·(k+2) = (k+1)·(k+2)·(k+3)/3 を証明できればよい。
証明したいものから前提を両側で引くと (k+1)·(k+2) =
(k+1)·(k+2)·(k+3)/3 - k·(k+1)·(k+2)/3 = (k+1)·(k+2)·(k+3)/3 - (k+1)·(k+2)·k/3 =
((k+1)·(k+2)/3)((k+3)-k) = ((k+1)·(k+2)/3)·3 = (k+1)·(k+2) で証明が完了。
 

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

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

    2⁶⁴ mod 29

(2⁵)¹² · 16 = 32¹² · 16 ≡₂₉ 3¹² · 16 = 27⁴ · 16 ≡₂₉ -2⁴ · 16 = 2⁴ · 16 = 16 · 16 = 32 · 8 ≡₂₉ 3 · 8 = 24

    74²⁰ mod 77

74¹⁶ ≡₇₇ -3¹⁶ = 3¹⁶ = (3⁴)⁴ = 81⁴ ≡₇₇ 4⁴ = 256 ≡₇₇ = 256-231 = 25

    41¹⁰ mod 37

41¹⁰ ≡_{(mod 37)} 4¹⁰ = 2²⁰ = 32⁴ ≡_{(mod 37)} (-5)⁴= 25²≡_{(mod 37)} (-12)²= (6 · 2)²= 36 · 4≡_{(mod 37)} (-1) · 4= -4≡_{(mod 37)} 33

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

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

群の作成 / Create a Group (21 点)

n>0 の自然数の場合、{1, ..., n-1} から n とお互いに素でない (二つの数の最大公約数が1でない) 数を除いた集合と mod n の掛け算で群が作れることが知られている。/ It is known that a group can be formed for any natural number 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.

このような群を表す下記の責表を完成しなさい (左上のマスも含む)。
Complete the following Caley table (including the upper left corner) that depicts such a group. (12 点)

群 A (演算 •) の三つの公理をそれぞれ文書と式で書きなさい。
Give the three axioms for group A (operation •), both in text and as a formula. (9 点)

1. 単位元 e が存在する: (∃e∈A: ∀b∈A: e•b = b = b•e)
2. 各元 b に対して、逆元 b' が存在する: (∀b∈A: ∃b'∈A: b•b' = e = b'•b)
3. 群の演算 • において、結合率が成り立つ: (∀b,c,d∈A: (b•c)•d = b•(c•d))

基数変換 / Base Conversion (13 点)

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

含意の結合率 / Associativity of Implication (8 点)

含意の結合率を書きなさい。/ Write down the associative law for implication. (2 点)

(A → B) → C = A → (B → C)

上記の結合率を証明するか反証しなさい。/ Prove or disprove the above law. (4 点)

A=F, B=F, C=F の場合、(A → B) → C = T → F = F だが、
A → (B → C) = F → F = T なので、含意の結合率は成り立ちません。

使った証明の種類を書きなさい。/ Give the type of proof you used. (2)

反例による証明

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

各ブール代数に「基本元」と言われる元がある。ある集合のベキ集合から作られるブール代数の場合、基本元は大きさ 1 の部分集合である。/ In each Boolean Algebra, there are some elements called basic elements. In a Boolean Algebra created from a powerset of a set, the basic elements are the subsets of size 1.

ビット列とビット毎演算からブール代数を作る場合、基本元はどのようなものになるかを説明しなさい。
Explain what the basic elements are in a Boolean Algebra created from bit strings and using bitwise operations. (3 点)

基本元は、一つのビットだけが 1 (残りのビットが 0) となっているビット列である。

単位元が基本元である場合、ブール代数の大きさを書きなさい。
Give the size of the Boolean Algebra where the basic element(s) is/are equal to the unit element. (1 点) 2

基本元の数が n であるブール代数の大きさを書きなさい。
Give the size of the Boolean Algebra with n basic element(s). (2 点)

2ⁿ

[以下すべての部分問題で、零元を 1 とする。In all the following subproblems, the zero element is 1.] 単位元が 110 で、基本元が 2, 5, 11 のブール代数について、次の部分問題に答えなさい。/ For the Boolean Algebra with unit element 110 and basic elements 2, 5, and 11, answer the following questions.

自然数 110 の素因数分解は 2·5·11 です。ある自然数 e が素因数分解で異なる因数だけに分解される場合、e を単位元かつ分解の素数を基本元とするブール代数が簡単に作れる。素因数分解で同じ因数が二回以上使われる場合、 ブール代数を作るのは難しくなるか、不可能になる。/ The prime factorization of 110 is 2·5·11. If the prime factorization of a natural number e produces all different prime factors, it is easy to create a Boolean Algebra with e as the unit element and the prime factors as the basic elements. If the prime factorization of a number results in prime factors that are used multiple times, then creating a Boolean Algebra becomes more difficult or impossible.

自然数 144 の素因数分解は 2·2·2·2·3·3 である。 144 が単位元で、三つの基本元を持つブール代数を作る一つの方法は、{2, 8, 9} の集合を基本元の集合と使うことである。 144 を単位元に持つブール代数が作れる他の大きさ 3 の基本元の集合を三つ書きなさい。 The prime factorization of 144 is 2·2·2·2·3·3. One way to create a Boolean Algebra with 144 as the unit element and 3 basic elements is to use the set of basic elements {2, 8, 9}. Give the other three sets of basic elements of size 3 that can be used to create a Boolean Algebra with 144 as the unit element. (6 点)

{2, 4, 18}, {2, 3, 24}, {3, 6, 8}

自然数 144 を単位元として持つ他のブール代数の基本元の集合を書きなさい。 Give the remaining sets of basic elements that can create a Boolean Algebra with unit element 144. (7 点)

{144}, {2, 72}, {3, 48}, {4, 36}, {6, 24}, {8, 18}, {9, 16}