Turning Completeをプレイして学んだこと＃１BASIC LOGIC編

この記事はTurning Completeをプレイして学んだ知識をまとめた記事です．
前提知識として真理値表，基本論理演算（AND，OR，NOT，NOR，NAND，XOR，XNOR），ドモルガンの法則，加法標準形，乗法標準形の変換について知っているものとして書きます．

この記事を読んでほしい人

BASIC LOGIC編で学んだこと

BASIC LOGIC編では主に４つのことについて学んだ．

完全形，ユニバーサルゲートとは

どんな真理値表でも表すことができるゲートの組み合わせを完全系という．真理値表とは，図１のように論理演算におけるすべての入力組み合わせとその結果を表形式で示したもの．
完全形は，いくつかあるが代表的な完全形を以下に紹介しておく．

ここで，フォーカスしたいのがNANDが完全形であることである．Turning Completeでは一番最初に扱う論理ゲートはNANDである．

また，単一のゲートで完全形を形成できるゲートを「ユニバーサルゲート」という．
NANDやNORはユニバーサルゲートである．

基本的な論理ゲートのNANDでの表し方

基本論理ゲートをNANDで表し方について説明する．

NOT (NAND１個)

NOTをNANDで表すには，NANDに同じ入力をする．
式で表すと以下のようになる．
　　NOT A = A NAND A
これが成り立つのは，真理値表を書いて確かめるよい．
以下図２を見るとA NAND AはNOT Aと同値であることがわかる．

表１：A NAND Aの真理値表

A	A NAND A
0	1
1	0

AND (NAND２個)

ANDをNANDで表すには，NANDに入力した後にNOTに入力すればよい．
NOTは既にNANDで表せることを確認したため，ANDもNANDで表せたといえる．
NANDゲートの個数を数えると，合計２個である．

OR (NAND３個)

ORをNANDで表すには，NANDゲートに入力する前にNOTゲートに入力するとよい．
論理式で考えると下のようになる．

数式のようにドモルガンの法則を使えば，ORになることがわかる．
NOTはNANDで表せることを確認したため，ORもNANDで表せたといえる．
NANDゲートの個数を数えると，合計３個である．

NOR (NAND４個)

NORをNANDで表すには，ORに入力した後にNOTに入力すればよい．
ORとNOTは既にNANDで表せることを確認したため，NORもNANDで表せたといえる．
NANDゲートの個数を数えると，合計４個である．

XOR (NAND４個)

「NOT，AND，ORをNANDで表せたからXORもNANDで表されることがわかるのではないか」と思う人がいると思う．ただ，それだとNANDゲートの数が多くなってしまう．最小数のNANDゲートで表す方法を考える．

XORを最小数のNANDで表す方法は２つある．
１．加法標準形にして，A AND (NOT A) = 0，B AND (NOT B) = 0を追加して，式変形していく．
２．乗法標準形にして，式変形していく．

ただ，１の方針の式変形の途中で２の乗法標準形の形が出てくるため後半の式変形は同じである．
よって，今回は１の方針で説明する．
以下が式変形である．

最後の式はすべてNANDである．よって，XORもNANDで表せた．
NANDゲートの個数を数えると，合計４個である．

XNOR(NAND５個)

XNORをNANDで表すには，XORに入力した後にNOTに入力すればよい．
XORとNOTは既にNANDで表せることを確認したため，XNORもNANDで表せたといえる．
NANDゲートの個数を数えると，合計５個である．

AND，OR，NORとNANDの関係性

「基本的な論理ゲートのNANDでの表し方」を読んで，「覚えるの大変だな～」と思った人もいるかもしれない．しかし，「AND，OR，NORとNANDの関係性」について理解すれば，簡単に覚えることができる．
AND，OR，NORをNANDで表すには，出力をNOTに入力したり，入力する前にNOTに入力して，ドモルガンの法則を用いて表した．
このことから，以下図３のような関係性が見えてくる．

図２：論理ゲートの関係性

このように入力にNOT，もしくは出力にNOTをとるかで考えればよい．

なぜNANDを使って他の論理関数を表すのか

これまでの話は，論理ゲートをNANDで表すことに焦点を当てて話していた．
ここでは「なぜNANDを使って他の論理関数を表すのか」について書く．

NANDを使って他の論理関数を表す理由は主に２つある．

単一ゲートのみを用いることで、以下のメリットがある．

トランジスタ数が少ないことで，以下のメリットがある．

ただ，ここで書いた内容はTTL回路に限る．
現在のデジタルICの主流であるCMOS回路では，NANDだけではなくNORも重要な役割を果たす．
これは，NORもNANDと同じユニバーサルゲートであり，CMOSにおいてNANDもNORもコストや動作速度が同程度で，２つの論理ゲートを使うとこで柔軟な回路設計をすることができるためであるらしい．

まだTTL回路やCMOS回路について詳しく知らないため，機会があれば勉強したい．

また，Turning CompleteのManualではユニバーサルゲートについて説明してる項目がある．そこには，「アポロの誘導コンピュータは、完全にNORゲートのみで作られていました。1960年代に設計され、RAMはわずか4KB、ディスク容量は32KBしかありませんでしたが、それでも宇宙飛行士を月へ導くことができました。」と書いてあった．

RAMが4KB，ディスク容量が32KBとあるが，最初見たときは「少な！」と思ったが，時代も違うし，もしかしたらこれぐらいが一般的かもしれないと後から思った．ハードについて詳しくないため，詳しい人が見たらどう思うのか気になる．

ブログを書く上で参考にしたもの

まとめ

BASIC LOGIC編では以下のことを学んだ．