真理表 (10 点)

下記の表に論理式 S∨¬(Q→S)∧R の計算の途中経過と結果を記入しなさい。

カルノー図表の作成 (7 点)

四変数のカルノー図表の場合、縦二変数、横二変数と配置する。横三変数の場合の真と偽の配置を、できるだけカルノー図表の使い方に合わせて下記の表 (カルノー図表の一番上の行) に記入しなさい。

標準形 (12 点)

四つの論理変数 A, B, C, D のうちちょうど一つの変数だけが F のときだけに F になる論理関数の短い方の標準形とその名称を書きなさい。

名称: 乗法標準形

式: (¬A∨¬B∨¬C∨D)∧(¬A∨¬B∨C∨¬D)∧(¬A∨B∨¬C∨¬D)∧(A∨¬B∨¬C∨¬D)

三つの論理変数 A, B, C のうち、ちょうど一つの変数だけが T のとき、または A が真のときに T になる論理関数の長い方の標準形とその名称を書きなさい。

名称: 加法標準形

式: (A∧¬B∧¬C)∨(¬A∧B∧¬C)∨(¬A∧¬B∧C)∨(A∧B∧¬C)∨(A∧¬B∧C)∨(A∧B∧C)

関係の性質 (8 点)

下記それぞれの関係の性質を集合 A の中の関係 R の条件の式で表現しなさい。

反対称的: xRy ∧ yRx → x=y

推移的: R∘R = R

反射的: ∀x∈A: xRx

対称的: ∀x,y∈A: xRy ↔ yRx

論理式の作成 (14 点)

下記の英文をそれぞれ (論理) 式に変換しなさい。

x is greater than 5 or smaller than 3.

x>5 ∨ x<3

For all y in A, P(y) is false.

∀y∈A: ¬P(y)

a is an element of A and A is a subset of B, but a is not an element of B.

a∈A ∧ A⊂B ∧ a∉BA

If p implies q and q implies r then p implies r.

(p→q ∧ q→r) → (p→r)

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

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

There exists an integer i so that the remainder of dividing i by 9 is odd.

∃i∈ℤ: (i mod 9) mod 2 = 1

x is greater than or equal to 7, and y is smaller than 5 or greater than x.

x≥7 ∧ (y<5 ∨ y>x)

論理回路の図 (12 点)

使える部品だけを用いて、指定した入力から指定した出力を出す回路の図を書きなさい。

チームの大きさの計算 (14 点)

ある選手の数 s からある選手の数 t の試合に出るチームを選ぶ組み合わせ (順不同) の数 (以降、C(s, t) と書く) を、0<t<s の場合、C(s-1, t) + C(s-1, t-1) で計算できることを授業で説明した。

C(s, t) を C(s-2, t)、C(s-2, t-1) と C(s-2, t-2) から算出する式とそれが有効な t の範囲を書きなさい (ヒント： 具体例で考えてみる)。

C(s-2, t)+ 2 C(s-2, t-1) + C(s-2, t-2); t の範囲: 1<t<s-1

C(s, t) を複数の C(s-3, ...) から算出できる式と t の有効範囲を書きなさい。

C(s-3, t)+ 3 C(s-3, t-1) + 3 C(s-3, t-2) + C(s-3, t-3); t の範囲: 2<t<s-2

上記二つの解答をみて、一般に C(s, t) を C(s-r, ...) の項から算出する場合に、係数はどうなるかを推測し、その理由を説明しなさい。

C(s, t) を C(s-r, ...) から計算する場合、係数はパスカルの三角形の r 行目になる。
その理由は、C(s, t) はパスカルの三角形の数値ですが、その数値は右上と左上の足し算
(C(s, t)=C(s-1,t)+C(s-1,t-1)) で計算される。一行上野ではなく、
r 行上から算出すると、右上と左上の足し算を経ながら複数の道ができる。
この道の数もちょうどパスカルの三角形の数となります。

基数変換 (10 点)

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

用語の説明 (28 点)

次の情報数学関連の英語の用語に相当する日本語の用語を書いて、簡単に説明しなさい。単にカタカナ表記にするのは避けること。

remainder

剰余; 整数で割るときに余った部分

positional notation

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

difference set

差集合; 集合の引き算みたいなもので、A-B の場合AにあるがBにない元の集合

empty set

空集合; 大きさ 0 (すなわち一つも元を持たない) 空の集合

prime number

素数; 自分と1でしか (余りなし) 割れない自然数

propositional variable

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

duality principle

双対原理; 恒真式が T/F と ∧/∨ を入れ替えても恒真式が恒真のまま、の原理

Cartesian product (set)

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

bitwise and

ビット毎論理積; 二つのビット列でビットごとに論理積をとる演算

bound variable

束縛変数; ある式で量記号で束縛された変数、量記号の範囲内でしか使えない

denotation

外延的記法; 集合の元を (波括弧 ({}) 内に) 全部列挙する

Abelian group

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

proof by contradiction

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

inverse relation

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

足し算の交換律の証明 (15 点)

足し算の交換律をペアノの公理を使って証明しなさい。授業で証明した足し算の結合律と s(a) = 1+a を前提にしてよい。式の変換のところ、[ ] 内にその理由を書きなさい。 (例: (x+y)+z = x+(y+z) [足し算の結合律])

証明しないといけないのは a+b = b+a
これを数学的帰納法を使って証明する。
基底: 1+a = a+1 を証明しないといけない。 1+a = s(a) [前提により]
s(a) = a+1 [ペアノの足し算の公理]。
帰納： a+k = k+a を仮定して、a+(k+1)=(k+1)+a を証明しないといけない。
a+(k+1)=(a+k)+1 [足し算の結合律]
(a+k)+1=(k+a)+1 [仮定により]
(k+a)+1=k+(a+1) [足し算の結合律]
k+(a+1)=k+(1+a) [基底により]
k+(1+a)=(k+1)+a [足し算の結合律] Q.E.D.

ブール代数と関係 (合計 22 点)

(各小問が間違っていても小問間の整合性が取れていれば部分点を与える。)

上記のハッセ図の関係を下記の三つの形式で表現しなさい。選択が必要なところ、要素の順番を昇順にしなさい。

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

  [大きい丸括弧省略]

n 進法での計算 (9 点)

次の表の計算を行いなさい。結果は被演算子と同じ基数を使って書きなさい。

量記号 (8 点)

(∃x : ∀y : P(x, y)) △ (∀y : ∃x : P(x, y)) での △ をどういう演算子にすれば全体の式が恒真になるのかを、
その理由とともに書きなさい。

△ の演算子は → にすべき。なぜなのかというと、左側の ∃x (存在する x) を x₁ とすると、
P(x₁, y) は必ず成立する。よって、左側でも全ての y において x₁ を使えば成立する。
しかし、右側の場合、それぞれの y において、x は別の値で P(x, y) が真になることも
許される (簡単な例: P(x、y) が x=y) ので、← (とそして ↔、すなわち =) にはなりません。

論理関数の単純化 (18 点)

(A→B )∨¬(¬A↔B ) の式を段階的に単純化し、それぞれの段階でどの様な性質を使ったかを書きなさい。同じ性質を複数並行に使うときには一つの段階を使ってよい。立て続けに同じ性質を使うときには立て続けに別に記入しなさい。交換律と結合律の使用はまとめて一段にしてよいが、記入を忘れずに。