Zenn
😽

真理値表から論理回路図を作る

2023/06/18に公開
turingcomplete
tech

Turing Completeというゲームをしています。
論理回路図の作り方がわからなくて詰まったので、調べたことをメモしておきます。
画像は全てTuring Completeからです。

手順

  • 真理値表を作る
  • 論理関数を作る
  • 使える論理ゲートで回路図を作る

真理値表を作る

真理値表は入力の組み合わせと出力を一覧にした表。
ANDゲートを例に考えてみる。
ANDゲートは2つの入力がどちらも1の場合に出力が1になる。

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

ORゲートを例に考えてみる。
ORゲートはいずれかの入力が1なら出力が1になる。

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

論理関数を作る

加法標準形

論理関数を作る前に加法標準形についてチェックする。
加法標準形は、真理値表で出力が1になる組み合わせをANDを使って書き、それらを全てORでつないだもの。

ANDゲートを例に考えてみる。
上記の真理値表より、出力が1になるのは入力がどちらも1の時なので以下のようになる。

A・B

次はORゲートを例に考えてみる。
上記の真理値表より、出力が1になるのはいずれかの入力が1の時なので以下のようになる。

A・\overline{B}+\overline{A}・B+A・B

真理値表から論理関数を立てる

上記の繰り返しになるが、ANDゲートを加法標準形で表現すると以下のようになる。

A・B

ORゲートを例に考えてみる。
出力が1に着目すると以下のようになる。

A・\overline{B}+\overline{A}・B+A・B

出力が0に着目して論理関数を作ってから全体を否定することで等価の論理関数が得られる。
\overline{\overline{A}・\overline{B}}

論理関数から回路図を作る

使える論理ゲートはNANDゲートのみという前提で考えてみる。
※Turing Completeで詰まったので、この部分を忘れないようにメモしておきたかった。

ANDゲート

ANDゲートはNANDゲートの否定なのでNANDゲートを2つ重ねれば良い。
1つのNANDに2つの入力を入れ、その出力を2つにして2つ目のNANDにつなぐことでNOT(否定)ゲートになる。

ANDゲートの回路図

真理値表で見ても、入力の組み合わせに対して出力が逆になっている。
AND

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

NAND

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

ORゲート

出力が1の組み合わせに着目して加法標準形で書くと、NANDゲートだけで表現するのは大変。

A・\overline{B}+\overline{A}・B+A・B

出力が0の組み合わせに着目して、その否定を加法標準形で書いてみてから論理回路図にする。
\overline{\overline{A}・\overline{B}}


それぞれの入力をNANDゲートに通して否定し、さらに各々の出力をNANDに通すことでORゲートを作ることができる。
NANDだけで表現するときは、「+」がない形が良い気がする。
上手く言語化したい。

補足

論理式の交換法則

法則名 例
交換法則
A+B=B+A
A・B=B・A
結合報告
A+(B+C)=(A+B)+C
A・(B・C)=(A・B)・C
恒等法則
A+1=1
A・1=A
A+0=A
A・0=0
同一法則
A+A=A
A・A=A
補元法則
A+\overline{A}=1
A・\overline{A}=A
復元法則
\overline{\overline{A}}=A
分配法則 A・(B+C)=A・B+A・C
吸収法則
A+A・B=A
A・(A+B)=A
ド・モルガンの法則
\overline{A+B}=\overline{A}・\overline{B}
\overline{A・B}=\overline{A}+\overline{B}

NANDゲート

真理値表

NANDゲートはANDの否定。
両方の入力が1の時のみ0となる。

input1 input2 output
0 0 1
1 0 1
0 1 1
1 1 0
NANDゲートは完全性を持つので、これさえあればどのような論理回路でも作ることができる。

論理関数

出力が1に着目して加法標準形で書いてみる。

\overline{A}・\overline{B}+A・\overline{B}+\overline{A}・B

出力が0に着目してその否定を加法標準形で書いてみる。
(こちらの方がシンプルでわかりやすい。)

\overline{A・B}

NANDゲートの回路図

Discussion