Turing Completeで遊んでみる

Turing CompleteというSteamで販売されているゲームを遊んでみようと思います。

NANDゲートから始めてCPUを作るまでの流れを体験できるようです。
Turing Completeを遊びながら学んだことをメモして行きます。
Zenn初投稿です。

NANDゲート

• 論理ゲートの1つ
• 否定論理積(ANDの否定)
• 二つの入力と一つの出力を持つ
• 1つ以上の入力がLowの時にHighを出力する
• どちらの入力もHighの時にLowを出力する

NANDゲートの真理値表

input1	input2	output
0	0	1
1	0	1
0	1	1
1	1	0

NANDゲートでNOTゲートを作る

NOTゲート

• 論理ゲートの1つ
• 論理否定。インバータとも呼ばれる
• 1つの入力と1つの出力を持つ
• 1つの入力の否定を出力する

NOTゲートの真理値表

input	output
0	1
1	0

1つ以上のLowがあればHigh、2つともHighならLowになるので、
回路上では1つの入力をNANDゲートの2つ入力につなげることで、NOTゲートを作成できる。

補足

ド・モルガンの法則

• ド・モルガンの法則は、ブール代数で論理和と論理積と否定の間成り立つ規則
• NANDゲートから任意の組み合わせ回路を作る出すことができる
• 組み合わせ回路を作るには論理ゲートを組み合わせる必要がある
• 論理ゲートの組み合わせを考えるには以下が必要に感じる
  1. 真理値表が書ける
  2. 真理値表からブール式を書ける
  3. ド・モルガンの法則を理解している

$$\overline{A \cup B} = \overline{A} \cap \overline{B}$$

$$\overline{A \cup B} = \overline{A} \cup \overline{B}$$

$$\overline{A_1 \cup A_2 \cup \dots \cup A_n} = \overline{A_1} \cap \overline{A_2} \cup \dots \cup \overline{A_n}$$

$$\overline{A_1 \cap A_2 \cap \dots \cap A_n} = \overline{A_1} \cup \overline{A_2} \cup \dots \cup \overline{A_n}$$

真理値表からブール式を導く

• 真理値表の中で出力が1のところのみに注目する