関係の性質の不可能な組み合わせ (合計 12 点)

授業で扱った関係の四つの性質の有無の組み合わせの中で、不可能な組み合わせが存在する。その組み合わせと不可能な理由を述べなさい。

不可能な性質の組み合わせ (6 点)

対照的、反対照的、推移的でない

不可能の理由 (6 点)

対照的と反対照的というのは行列表現で対角線以外の場所は全部 0 であるという意味。 しかしそのような行列は自分と掛け算しても結果が変わらない、即ち推移的である。酔って上記の性質の組み合わせは不可能。

n 進法での計算 (6 点)

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

吸収律の証明 (合計 12 点)

下記表の空欄を埋めながら論理演算の吸収律を吸収律以外の論理演算の性質から証明しなさい。(8 点)

二つの吸収律の証明には共通点がある。その理由を説明しなさい。(4 点)

双対原理を使っている。双対原理というのは、ある論理演算の性質で「∧」と「∨」、それに「T」と「F」を入れ替えることで「双対な」性質が作れるていうことである。

真理表 (10 点)

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

「万能」な論理関数 (合計 24 点)

二つの論理変数の関数の中で、NAND と NOR は「万能」、即ちその関数一つだけで他の論理関数全てが作れる、ということがよく知られている。 T や F も引数として許す場合、更に「万能」な論理関数が増える。

論理関数 BAN3(A, B) = A∧¬B がなぜ「万能」であるかを説明しなさい。(6 点)

なぜなら、∧、∨、¬ では全ての論理関数が作られるが、
BAN3(T,A) で ¬、BAN3(A,¬B) で ∧、更にでモーガンの法則を使えば
∨ も BAN3 で作られ、そこからすべての二変数の論理関数が作られる。

論理関数 f(A, B) がそれぞれ F, T, A, B, ¬A, ¬B, A∨B, A∧B の八つの場合、なぜ万能でないかをそれぞれ説明しなさい。(8 点)

F と T の場合、引数の値に依存しなくて、一つの結果しか作れない。
A, B, ¬A と ¬B の場合、一つの引数にしか依存しなくて、
二つの引数に依存する関数が作れない。
A∨B と A∧B はいくら組み合わせてもそれぞれ「入力が全部偽だけのとき偽」、
「入力が全て新の真だけ真」なので、否定が作れない。

XOR(A, B) は万能なのかどうかを明記の上、その理由を証明しなさい。(10 点)

XOR は万能ではありません。なぜなら、先ず
第一段階で XOR 演算一つ考える。XOR(T,T)=XOR(F,F)=XOR(A,A)=XOR(B,B)=F;
XOR(T,F)=XOR(F,T)=T; XOR(A,F)=XOR(F,A)=A, XOR(A,T)=XOR(T,A)=¬A (B で同様);
XOR(A,B)=XOR(B,A); この段階で追加されたものは ¬A と ¬B だけ。
第二段階で ¬A と ¬B も含め新たに作られる関数を考える。XOR(¬A,T), XOR(¬A,F),
XOR(¬A,A), XOR(¬A,¬A) と XOR(¬A,¬B) は新しい結果に至らないのは明らか。計算すると
XOR(¬A,B) は A↔B 又は ¬XOR(A,B) で書ける。この時点で二項論理関数の半分
(F, T, A, B, ¬A, ¬B, XOR, ↔) は XOR で表せるが、
それをいくら組み合わせてもそのほかの論理関数が表せないことが分かる

基数変換 (8 点)

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

用語の説明 (20 点)

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

proposition

命題; 真偽が客観的で決まる文、質問や意見はだめ

half adder

半加算器; 二進数一ビットと一ビットを足し、合計と繰り上がりを出力する回路

Peano Axioms

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

semiorder relation

反順序関係; 反射的、反対称的かつ推移的な関係

inverse element

逆元; 群の場合、ある元の逆元は一緒に演算すると単位元になる

permutation

順列; ある集合から元を重複なしに順番を考慮して選ぶときにできるもの

universal set

全体集合; ある演算において対象となる言すべてを含まれる集合

associative law

結合律; ある演算子 △ において、a△(b△c)=(a△b)△c が成立すること

proof by counterexample

判例による証明; 判例を示すことで、ある主張の一般性に反証する

congruence class

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

情報テクノロジーにおける証明 (6 点)

情報テクノロジーにおいて、三つの証明の応用を列挙しなさい。

データ構造の性質の証明

アルゴリズムの正しさや性質の証明

プログラムの変更の正しさの証明

関係の表現 (15 点)

G = {2, 3, 5, 7, 11} 内の関係 R で、x Ry が次の三つの条件:

1. x は y の二倍より大きい
2. y は x の三倍以上
3. x+y は奇数

のいずれかを満たすと真になる。R を下記の五つの表現形式で書きなさい。

順序対の集合 (外延的記法): {(2,3), (2,5), (2,7), (2,11), (3,2), (3,11), (5,2), (7,2), (7,3), (11,2), (11,3), (11,5)}

順序対の集合 (内包的記法): {(x,y) | x∊C ∧ y∊C ∧ (x>2y ∨ 3x≤y ∨ (x+y) mod 2 = 1)}

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

  [大きい丸括弧省略]

量記号と含意 (合計 12 点)

¬(∃x: P(x) → ∀y: ¬Q(y)) を途中経過を見せながら単純化しなさい。(6 点)

¬(∃x: P(x) → ∀y: ¬Q(y)) =
¬(¬∃x: P(x) ∨ ∀y: ¬Q(y)) =
¬¬∃x: P(x) ∧ ¬∀y: ¬Q(y) =
¬¬∃x: P(x) ∧ ∃y: ¬¬Q(y) =
∃x: P(x) ∧ ∃y: Q(y)

上記の単純化の最初と最後の具体例を考えて、説明しなさい。 (6 点)

P(x) は「x に雨が降る」で、Q(y) は「y に雪が降る」とする。
そうすると最初のところは「あるところに雨が降るならばどこにも
雪が降らない、のが間違っている」ということである。最後のは「あるところに
雨が降るかつある (違うかもしれない) ところに雪が降る」ということです。

式の証明 (10 点)

合同式の一つの性質、a≡b ⇒ aⁿ≡bⁿ (mod m) をもう一つの合同式の性質、a≡b ∧ c≡d ⇒ ac≡bd (mod m) を使って、 n≥0 の場合に証明しなさい。 m 以外の法を使わないならば、証明中「(mod m)」を省略してよい。

数学的帰納法を使って証明する:
基底: n=0 の場合、 a≡b ⇒ a⁰≡b⁰ は a⁰=b⁰=1 のため明らか。
帰納: a≡b ⇒ a^k≡b^k を前提として、 a≡b ⇒ a^k+1≡b^k+1 を証明しないといけない。
そこで c=a^k、d=b^k にすると、
もともとの a≡b かつ前提から c=a^k ≡ b^k=d から
a^k+1=aa^k=ac ≡ bd=bb^k=b^k+1
それによって帰納が証明され、a≡b ⇒ aⁿ≡bⁿの証明が完了。

論理関数のの標準形 (合計 12 点)

次の論理式の標準形の名称を記述の上、もう一つの標準形に変換しなさい。

¬A∧¬B ∨ A∧B (3 点)

名称: 加法標準形 [又は選言標準形]

もう一つの標準形: (A∨¬B) ∧ (¬A∨B)

(A∨¬B∨C) ∧ (A∨¬B∨¬C) ∧ (¬A∨¬B∨¬C) (6 点)

名称: 乗法標準形 [又は連言標準形]

もう一つの標準形 (*): ¬A∧¬B∧¬C ∨ ¬A∧¬B∧C ∨ A∧¬B∧¬C ∨ A∧¬B∧C ∨ A∧B∧¬C

(*) の標準形を単純化しなさい。 (3 点)

¬B ∨ A∧B∧¬C

論理回路の図 (10 点)

次の論理式に相当する回路の図を書きなさい。