論理回路の話

2進数の話をした時に、2進数を採用するメリットの1つとして

「1,0」の区別を「真,偽」の区別に対応させることにより、論理演算と数値 演算を統一的に簡単に扱える

ということを言ったと思います

以下では、実際にどのようにして論理的な演算(あるいは回路)を用いてコンピュー タ内の様々な処理を行うことができるのかについて説明します。

論理式(論理関数)

数値的な演算を表すのに、数学では計算式を用いますね。それと同じように、 論理的な演算を表すのに「論理式」というものを用います。

計算式で例えば y = 3 × x ＋ 1 のように文字(この例では x と y)を使うのと同様, 論理式でも文字を用いま す。ただし、「文字」というよりも、「変数」と呼ぶことが多いので、以下で は変数ということにします。(数値的な変数と区別するのに「論理変数」など と言ったりもします。) 計算式の変数(文字)は、一般に実数とか複素数を表すことが多いわけで、 上の例では x に実数 4 を当てはめれば、y = 3 × 4 ＋ 1 となって y = 13 となります。 しかし、論理式では真偽を扱うので、個々の変数は真偽を表します。 真偽を表す値を真理値または論理値と言っています。 以下では「真」を T, 「偽」を F と書くことにしましょう。 つまり、論理式の中に出てくる変数は T か F かを表しています。

文献によって書き方は様々です。tt, ff と書くものもあれば、true, false と書くもの、F の代りに T の上下を逆さまにした字(⊥)を使うものなど色々 です。

T を2進数の 1, F を2進数の 0 に対応づけて考えることが多いので、 最初から T の代わりに 1, F の代わりに 0 を書くことも多いのですが、 ここではあえて、T, F と 1, 0 を別々にしておきます。 あとで皆さんが真理値になれてきたらごっちゃにするかも知れません。

数に対して「×」「＋」「−」などの演算があるのと同様、真理値に対しても 「∧」「∨」「¬」などの演算があります。変数や T, F に対してこれらの演算 を何度か施すことによって論理式が得られます。例えば、x ∧ (y ∨ ¬z) は 1 つの論理式です。

論理回路

論理回路とは

論理演算を電子回路で実現することができます。そのような回路を論理回路 と言います。

論理回路には大きく分けて

• 組合せ論理回路
• 順序論理回路

の2種類があります。

組合せ論理回路というのは、出力が入力だけによって決まるものです。

順序論理回路というのは、回路がいくつかの内部状態を持ち、出力は入力と その時の回路の内部状態によって決まるようなものです。内部状態は、時間 の経過によって変化し得ますが、現在の内部状態と入力とに応じて次にどの ような内部状態に変わるかが決まります。例えば、CPU はレジスタをいくつ か持っていますが、レジスタの値というのは、CPU の内部状態の一部です。 CPU は、現在のレジスタの値によって次に行なう処理を変える、といったこ とができなければならないから、順序回路をたくさん含んでいます。

順序回路の話は少し難しいので、組合せ論理回路の話の後で説明します。 順序回路については、回路に内部状態を持たせるための一種の記憶回路であ る「フリップフロップ回路」の説明をするにとどめます。 (SRAM というのは、フリップフロップ回路を多数集積したようなものだと思 えばよいでしょう。ただし、フリップフロップ回路の種類や作り方にも色々 あって、この授業で説明する作り方は、SRAM を作る時の方法とは違います。)

真理値と電圧・電流の対応

真理値の真偽の区別を電圧・電流の高低・大小の区別に対応させることによ り、論理演算を電子回路でうまく扱える、という話は以前にしました。 実際には、マイクロプロセッサの内部では、真偽の区別(あるいは 1,0 の区 別)を電流の大小で表すことはほとんどありません。 電流を流すと電力を消費し、発熱するからです。

そこで、真偽の区別は多くの場合電圧の高低で区別します。以下、そのよう な回路だけを考えることにします。

区別のしかた(つまり、真偽を電圧の高低に対応させるやり方)には、次の2 通りがあります:

• 真を高電圧に対応させ、 偽を低電圧に対応させるやり方。 この対応を正論理といいます。
• 真を低電圧に対応させ、 偽を高電圧に対応させるやり方。 この対応を負論理といいます。

理屈の上では、正論理をとっても負論理をとってもよいはずですし、1つの 大きな回路の中で、一部分では正論理を使い、別の部分では負論理を使う、 ということもごく普通に行なわれています。しかし、初心者には正論理のほ うがわかりやすいと思うので、この授業ではもっぱら正論理を扱います。

論理回路においては、高電圧を H (High に由来), 低電圧を L (Low に由来) で表します。今は正論理を仮定しているので、 T を H に、F を L に対応 させることになります。

以下では、論理式で T, F と書くところを H, L と書いてしまうこともあり ます。例えば、T ∧ F = F と書くところを H ∧ L = L と書く、などです。

ついでに、H, L の区別を数の 1, 0 に対応させる時も、原則的に「H を 1 に、L を 0 に」対応させることに決めてしまいましょう。(もちろん、その 逆でも理屈の上では構わないのですが、このほうが心理的には少しわかりや すいようです。)

高電圧というのが実際に何V(ボルト)で低電圧が何Vか、というのは以下の話で は大した問題ではありません。例えば、5V 電源だけを使う回路では、H が 5V, L が 0V ということになるでしょう。昔は半導体論理回路では 5V 電源の ものが多かったのですが、最近の MPU は 1.8V とか、1.4V といった低電圧で 動くものが多くなっています。電圧が低いほうが電力消費を下げられます。

基本的な論理演算

否定(¬, not)

否定演算(¬)は T と F を逆にします。つまり、

• ¬ T = F
• ¬ F = T

です。直観的に言えば、¬x とは「x でない」という意味だと言えます。 表にすると、

    x │¬x 
  ──┼──
    F │ T 
    T │ F 

となります。 このような表を真理値表と言います。つまり、変数を含んだ式の真理値が変数に割り当てる真理値 の変化によってどのように変わるかを表にしたものです。

文献によっては、¬x の代わりに、xの上に横線を一本引いて表すことがあり ます。というより、電気関係の文献などでは、そういう書き方をしているもの のほうが多いのですが、この note に書くのにはちょっと不都合です。手で書 く時も、長ーい式を否定すると長ーい横線を書かねばならず、面倒です。 たくさん否定が出てくると、何重にも重ねて線を引くことになり、実にうっと うしいです。数理論理学関係の文献では、¬x とか 〜x と書くものが多いです。

NOT 回路(文献によっては NOT 型回路)

否定演算に相当する動作をする回路を NOT 回路といいます。

回路図の上では下のような記号で描かれます:

この記号の左側にある線が入力、右側にある線が出力です。

下の図で 0 または 1 が表示されている所をクリックすると、0 と 1 を切り替えることができ、NOT 回路の動作を確かめることができます。 (この図を表示しているソフトウェアでは、H, L をそれぞれ 1, 0 で表しています。)

1 になっている線は赤で、0 になっている線は青で表示されます。

論理積(連言, 「かつ」,「and」,「conjunction」)

「A かつ B」 を表す式を A∧B と書きます。電気関係の文献ではA・B と書く ことが多いようです。A・B だと数式の場合の掛け算と同じ記号ですが、掛け 算で A・B を AB と省略するのが多いのと同様, 「A かつ B」も AB と書くこ とがよくあります。また、数式では×と・を両方使うことが多いですが、論理 式でも A × B と書くことがあります。数理論理学の文献では A ∧ B とか A & B と書いてあることが多いです。

x∧y の真理値表を書くと、

     x  │   y  │  x∧y
  ───┼───┼────
     F  │   F  │   F
     F  │   T  │   F
     T  │   F  │   F
     T  │   T  │   T

となります。「x∧y」とは、「x かつ y」、すなわち、「x が正しくて、かつ y も正しい」という意味の式なので、「x も y も T」の時だけ x∧y は T に なる、と決めてあるわけです。

ところで、上の真理値表の T を 1 に F を 0 に置き換えてみると、

     x  │   y  │  x∧y
  ───┼───┼────
     0  │   0  │   0
     0  │   1  │   0
     1  │   0  │   0
     1  │   1  │   1

となりますが、x と y の間の縦線を取ると、

     x   y  │  x∧y
  ─────┼────
     0   0  │   0
     0   1  │   0
     1   0  │   0
     1   1  │   1

となり、左半分に

    00
    01
    10
    11

のような列ができます。これは2ビットで表せる4種類の数値を小さい順に並べ たものになっていますね。このような順序で表を書くと、書き間違い(ある組 み合せを抜かしたり、重複させてしまったり)を防ぎやすくなります。

さて、このように 0 と 1 で書いてみると、x∧y の真理値表は、ちょうど1ビッ トの2進数の掛け算の表に一致しています。これが論理演算を使って数値演算 を実現している一番簡単な例です。(ケタ数の多い掛け算にはもっとややこし い論理式が必要です。)あとで見るように、論理演算は簡単な電子回路で実現 できます。

AND 回路(AND型回路)

AND 回路は、正論理のもとで論理積(and,∧)演算に相当する動作をします。す なわち、入力端子が2つあって、その両方に H を入力した時だけ出力が H になり、入力が片方でも L なら出力は L になります。

すなわち、2つの入力を x, y とすると、回路の動作は、

  x   y   AND回路の出力
-------------------------
  L   L         L
  L   H         L
  H   L         L
  H   H         H

のような表で表されます。これは、L を F と考え、H を T と考えれば、論 理積の真理値表と同じであることがわかるでしょう。電子部品をどのように 組み合わせればこのように動作する回路が作れるかは、あとで述べます。

回路図の上では、AND 回路は下のような記号で描かれます:

下の図で AND 回路の動作を確かめて下さい。

論理和(選言,「または」,「or」,「disjunction」)

「A または B」 を表す式を A∨B と書きます。数式の場合の足し算と同じ 記号「＋」を使うこともありますが、性質はちょっと違います。

普通の数式の中に＋と×の両方が出てくるとき、計算の優先順位は×が＋より 上だというのは小学校で習っていると思います。つまり、1＋2×3は1＋(2×3)と 同じですね。それと同じように、論理式でも、A ∨ B ∧ C は A ∨ (B ∧ C) と 同じと約束します。

数理論理学の文献では A ∨ B と書いてあることが多いですが、電気関係では A ＋ B と書いてあることが多いです。しかし、この note では、あとで論理 演算と数値演算の関係について説明する時に足し算の「＋」も出てくるので、 「または」を「＋」と書くとややこしいから「∨」のほうを使うことにします。

x∨y の真理値表を書くと、

     x  │   y  │  x∨y
  ───┼───┼────
     F  │   F  │   F
     F  │   T  │   T
     T  │   F  │   T
     T  │   T  │   T

となります。「x∨y」とは、「x または y」、すなわち、「x が正しいか、y が正しいか(少なくともどちらか一方、両方でもよい)」という意味の式なので、 x か y かどちらか一方でも T になっている時 x∨y は T になり、どちらも F なら x∨y は F と決めてあるわけです。

今度も上の真理値表の T を 1 に、F を 0 に置き換えてみましょう。

     x  │   y  │  x∨y
  ───┼───┼────
     0  │   0  │   0
     0  │   1  │   1
     1  │   0  │   1
     1  │   1  │   1

おや、これは足し算の表に近く見えますが、同じではありません。 1ビットどうし足した時にくり上がりがあれば結果は2ビットになる(2進で 1+1は 10)ので、これは当たり前とも言えますが、くり上がりでできた下から2 ビット目を無視して、一番下のケタだけを見たと考えても、足し算にはなりま せん。(2進で1+1は10で、その一番下のケタは0)。

足し算と違う演算なのに電気関係の文献では x＋y のように書くので、そうい う文献を読む時は最初抵抗があるかも知れませんが、すぐなれると思います。

ややこしいのになぜ x∨y を x＋y と書くことがあるのかというと、一応ちゃ んとした理由があるのですが、話がそれるので説明はやめときます。

なお、「足し算の1ケタ目だけ」を表す論理演算はあとで出てきます。

OR 回路(OR型回路)

正論理のもとで論理和演算に相当する動作をする回路をOR 回路といいます。

      x   y   OR回路の出力
    -------------------------
      L   L         L
      L   H         H
      H   L         H
      H   H         H

以下、「正論理のもとで」というのはいちいち断わらないことにします。

回路図の上では、OR 回路は下のような記号で描かれます:

下の図で OR 回路の動作を確かめて下さい。

含意(「ならば」,「implies」,「implication」)

電子回路の文献にはあまり出てこない演算ですが、「A ならば B」を表す式 「A → B」 というのもあります。「A ⊃ B」とか 「A ⇒ B」と書くことも多 いです。

真理値表を書くと、下のようになります。

     x  │   y  │  x→y
  ───┼───┼────
     F  │   F  │   T        ← 1段目
     F  │   T  │   T        ← 2段目
     T  │   F  │   F        ← 3段目
     T  │   T  │   T        ← 4段目

このような表になる理由はすぐにはわからないと思いますから説明します。

「x → y」とは、「x ならば y」ということなので、「x が正しい時には必ず y も正しくなる」という意味です。従って、「x が正しいくせに y は正しく ない」というのはマズイわけです。だから、x が T で y が F の組合せの時は x → y は F になります。しかし、それ以外の組み合わせなら OK, つまり x → y は T とするのです。

さらに少し補足説明をします。 まず、表の中の x が T になっているところ、つまり、表の3,4段目だけを見 てみましょう。「x が正しい時には必ず y も正しい」というのですから、 4段目で y が T の時 x → y が T なのはこれでいいですね。y が F になっ ている3段目は、さっき言ったように「x が正しいくせに y が正しくない」ので、 「x → y」は正しくない、つまり F になるわけです。 わかりにくいのは、x が F の時です。つまり、表の1,2段目ですが、次のよう に考えましょう。「x が正しい時には y も正しい」という言葉は、x が正し くない時については何の制約も与えていないと考えられます。つまり、x が正 しくない時については、y が何であろうがおかまいなしです。つまり、y が T だろうが F だろうが OK, で、OK ということは、真ということだ、と考える わけです。だから、1,2段目はどちらも x → y が T になっています。

なお、含意演算に相当する動作をする回路はもちろん作れますが、「含意回路」という名前は聞いたことがありませんし、それを表す特別な記号も用意されていません。 もちろん、他の記号を組合せてそのような回路を表すことは可能ですが。

用語についての補足

この授業では「論理式」という言葉を使っていますが、「論理関数」とい う呼び方もよく使われています。電気関係の文献では大抵「論理関数」に なっています。なぜ「論理関数」と呼ぶかというと、論理式の中に変数が 現れていると、論理式を変数についての関数と見ることができるからです。 これは、高校数学で例えば x² + 1 を x の関数と見るのと同じようなも のです。

うるさいことを言うと、式と関数は違うもののはずなんですけどね。 だから、「f(x) = x² + 1 によって定義される関数 f」というような 言い方を本当はしなくちゃいけません。
なぜって、例えば同じ x² + t という式でも 「f(x) = x² + t によって定義される関数 f」 と 「g(t) = x² + t によって定義される関数 g」は別のものでしょ? つまり、どの変数についての関数と見るかを指定しなければ、式を関数と見るこ とはできないんです。でも、大抵暗黙のうちにどの変数についての関数と見るか は決まっているので、ちょっといいかげんだけど式を関数と言ったりするわけで す。
論理式の場合、特に断わらなければ、式が含んでいるすべての変数につ いての関数と考えるのが普通で、そういう意味で論理関数と呼んでいる ことが多いのです(文脈を見ればわかるはず)。

複雑な論理式

数学の式で、演算記号や変数をたくさん使うといくらでも複雑な式ができるの と同様, 論理式もいくらでも複雑になります。

そういう場合、カッコを適当に省きたいので、演算記号の優先順位をもう少し ちゃんと決めておきます。先程は∨と∧の間の優先度だけ示しましたが、¬ と → も入れて考えると、優先度の強い順に

¬, ∧, ∨, →

となります。例えば、¬A∧B は (¬A)∧B であって、¬(A∧B) ではありません。 x ∨ y → z は (x ∨ y) → z であって、x ∨ (y → z)ではありません。 まあ、まぎらわしいと思ったら、省ける時でも適当にカッコを入れましょう。

また、x ∧ y ∧ z のような式は、(x ∧ y) ∧ z のことなのか、 x ∧ (y ∧ z) のことなのか、一応決めておかなければいけないのですが、 あとでわかるように、この2つは等しい式になるのでどちらにするかは大した問題 ではありません。しかし、一応 (x ∧ y) ∧ z のことだとしておきましょう。 x ∨ y ∨ z についても同様です。

x → y → z というのはどうでしょうか? この場合、(x → y) → z と x → (y → z) は等しくないので、どちらかに決めないといけませんが、 x → (y → z) のことだ、と決めるのが論理学の業界の常識になっています。

さて、複雑な式の真理値表を考えてみましょう。 例えば、(x → y)∧(y → x) という式を考えます。 これは、「x ならば y だし、その逆も言える」ということですから、 「x と y は論理的に同値」ということです。

真理値表を書くとこうなります:

     x  │   y  │  x→y  │  y→x  │  (x→y)∧(y→x)
  ───┼───┼────┼────┼────────
     F  │   F  │   T    │   T    │   T    
     F  │   T  │   T    │   F    │   F    
     T  │   F  │   F    │   T    │   F    
     T  │   T  │   T    │   T    │   T    

このように、複雑な式の真理値表を書くときは、その部分論理式(論理式の1部 分になっているような論理式)全部について、簡単な順に表を作って行くとい いです。x→y の行と y→x の行を書いておいて、それを見ながら(x→y)∧(y→x) の行を書く、というようにやればいいわけです。

上の表を見ると、確かに、x の真理値と y の真理値が等しい時だけ (x→y)∧(y→x) の真理値は T になっていますね。だから、確かに「x と y が論理的に同値」と いう意味の式だと言っていいのです。

排他的論理和(exclusive or)

さて、今度は上の式の否定、つまり、¬((x→y)∧(y→x))を考えてみます。 上の表を利用して真理値表を書いてみると、

   x  │   y  │¬((x→y)∧(y→x))
───┼───┼─────────
   F  │   F  │        F
   F  │   T  │        T
   T  │   F  │        T
   T  │   T  │        F

となります。この表の T, F を 1, 0 に置き換えてみると、

   x  │   y  │¬((x→y)∧(y→x))
───┼───┼─────────
   0  │   0  │        0
   0  │   1  │        1
   1  │   0  │        1
   1  │   1  │        0

となります。これは 1 ビットの足し算の1のケタを求める演算になっています。

x と y から ¬((x→y)∧(y→x))を求める演算は 排他的論理和(exclusive or) と呼ばれており、x XOR y と書かれます。なぜこういう名前がついたかと いうと、or によく似ているけれども、exclusive(排他的)である所だけが違う からです。exclusive というのは、2つの事が同時に成り立ってはいけない、 という意味です。つまり、x か y かどちらかが成り立つのだけれども、同時 に成り立つのはダメ、ということです。

日常言語での「x または y」とか、「x か y」という表現は、or よりも exclusive or を意味することが多い、とよく言われます。紅茶を飲む時に 「レモンかミルクか」というのは、どちらか一方を選ぶということで、 レモンとミルクを両方入れるのはナシでしょう。

x XOR y が「x か y かどちらかだが、両方はダメ」という意味であることか ら考えると、x XOR y は

x XOR y = (x ∨ y)∧¬(x∧y)

とも表せます。また、「x だけが成り立つか、y だけが成り立つか」と考えれば、

x XOR y = x∧¬y ∨ ¬x∧y

とも表せます。

# x∧¬y ∨ ¬x∧y にカッコを補うと (x∧(¬y)) ∨ ((¬x)∧y) となります。

XOR 回路

正論理のもとでXOR演算に相当する動作をする回路をXOR 回路といいます。

回路図の上では、XOR 回路は下のような記号で描かれます:

下の図で XOR 回路の動作を確かめて下さい。

XNOR演算

XOR は (x → y) ∧ (y → x) の否定になっていましたが、逆に言うと (x → y) ∧ (y → x) は x XOR y の否定になっているので、 (x → y) ∧ (y → x) で表される演算を XNOR と言うことがあります。 (exclusive NOR) (「N」 の字が Not を意味する。) 式で書く時は、やはり、x XNOR y のように2つの式の間に書きます。

XNOR 回路

正論理のもとでXNOR演算に相当する動作をする回路をXNOR 回路といいます。

回路図の上では、XNOR 回路は下のような記号で描かれます:

下の図で XNOR 回路の動作を確かめて下さい。

色々な法則

XOR が何通りにも表せたように、ある論理式をそれと等しい働きをする別の論 理式に書き換えることが色々とできます。それらを利用すると、論理式を簡単 化したり、形を整理したりできます。論理回路を簡単化したりするのに使えま す。論理回路の高速化にも使えます。 そうした法則の代表的なものを以下に示します。

1. T ∧ x = x, F ∨ x = x
2. T ∨ x = T, F ∧ x = F
3. ¬T = F, ¬F = T
4. ¬¬ x = x (二重否定の除去)
5. x∧x = x, x∨x = x (巾等律, べきとうりつ)
6. x ∨ ¬x = T, x ∧ ¬x = F (相補律)
7. x ∧ y = y ∧ x, x ∨ y = y ∨ x (交換律)
8. x∧(x ∨ y) = x, x∨(x∧y) = x (吸収律)
9. (x ∧ y) ∧ z = x ∧ (y ∧ z), (x ∨ y) ∨ z = x ∨ (y ∨ z) (結合律)
10. x∧(y ∨ z) = x∧y ∨ x∧z, x∨(y∧z) = (x∨y) ∧ (x∨z) (分配律)
11. ¬(x ∧ y) = ¬x ∨ ¬y, ¬(x ∨ y) = ¬x ∧ ¬y (ド・モルガンの法則)
12. x → y = ¬ x ∨ y, x → y = ¬(x ∧ ¬y)

上で出てきた「巾等律」などの名前については、「律」で終わっている名前は、 「則」で終わる名前で呼ばれることも多いです。要するに、日本語訳が訳した 人によって違うだけのことです。例えば、分配律は分配則と呼ぶこともありま す。("law" の日本語訳に「律」と「則」がある。)

相補律という名前がついている2つの法則については、それぞれ別の名前もついています:

• x ∨ ¬x = T のほうには、排中律という名前がついています(law of excluded middle)。 これはなぜか排中則とは呼びません。
• x ∧ ¬x = F のほうには、矛盾律という名前がついています。

分配律の1つ目のほうは、x × (y + z) = x × y + x × z という数式とよく 似ています。この数式も分配律と呼ばれています。 分配律の2つ目に相当する数式を無理矢理書くと x + (y × z) = (x + y) × (x + z) になりますが、これは数式として正しくないので、分配律の2つ目のほうは1つ 目よりも覚えにくいと思います。

これらの法則は、一見しただけで明白なものもありますが、すぐにはわからな いようなものは、等式の両辺の真理値表をそれぞれ書いてみて、一致すること を確かめればわかります。例えば、ド・モルガンの法則の1つ目のほうは次のような 表により確かめることができます:

演習

ド・モルガンの法則

下の真理値表を完成させることにより、ド・モルガンの法則 (の片方)を確かめなさい:

「ならば」を否定と「または」で表す

下の真理値表を完成させることにより、 x→y = ¬x∨y を確認しなさい:

「ならば」を否定と「かつ」で表す

下の真理値表を完成させることにより、 x→y = ¬(x∧¬y) を確認しなさい:

「かつ」と「または」の関係

ド・モルガンの法則によって、「かつ」を「または」と否定だけで表すこと ができます。なぜなら、 x ∧ y = ¬¬(x ∧ y) (二重否定の除去(逆向き)) = ¬(¬x ∨ ¬y) (ド・モルガンの法則) となるからです。

逆に、「または」を「かつ」と否定だけで表すことができます。なぜなら、 x ∨ y = ¬¬(x ∨ y) (二重否定の除去(逆向き)) = ¬(¬x ∧ ¬y) (ド・モルガンの法則) となるからです。

実は、後でわかるように、どんな個数の変数についてのどんな論理演算でも 「かつ」と否定だけを使って表すことができます。もちろん、「または」と 否定だけで表すこともできるわけです(なぜなら、上に書いたように「かつ」 は「または」と否定で表せるから)。

その他のよく使われる演算

NAND (ナンド)演算

¬(x ∧ y) は、(「and」の否定なので、) x NAND y と書かれます。

真理値表を書いてみると、

となります。

面白いことに、NAND 演算さえあれば、全ての論理演算を表すことができま す。それを示すには、NAND を使って否定と論理積(かつ)を定義してみせれ ばいいはずですから、それをやってみましょう:

まず、

なので、否定 ¬x が x NAND x で表せました。

次に、

なので、論理積 x ∧ y が ¬(x NAND y) で表せましたが、 ¬(x NAND y) という式の先頭の ¬ は NAND で表せるので、 結局 x ∧ y は NAND だけで表せることになります。 (具体的に書けば、(x NAND y) NAND (x NAND y) になります。)

ついでに、x ∨ y も NAND で表してみましょう。さきほど見たように、 x ∨ y は ¬(¬x ∧ ¬y) で表せるので、

となり、この式の中の否定は NAND で表せるので、x ∨ y が NAND だけで 表せたことになります。 (具体的に書けば、(x NAND x) NAND (y NAND y) となります。)

NAND 演算はこのような性質を持つとともに、電子回路で実現しやすいこと から、よく使われています。

NAND 回路

正論理のもとでNAND演算に相当する動作をする回路をNAND 回路といいます。

回路図の上では、NAND 回路は下のような記号で描かれます:

下の図で NAND 回路の動作を確かめて下さい。

NOR (ノア)演算

¬(x ∨ y) は(or の否定なので) x NOR y と書かれます。

真理値表を書いてみると、

NAND でどんな演算でも表せたのと同様, NOR だけを使ってどんな演算でも 表すことができます。

宿題: NOR 演算 だけを使って ¬x, x ∨ y, x ∧ y を表して下さい。 (これはレポートではないので、考えて来るだけでよろしい。)

NOR 回路

正論理のもとでNOR演算に相当する動作をする回路をNOR 回路といいます。

回路図の上では、NOR 回路は下のような記号で描かれます:

下の図で NOR 回路の動作を確かめて下さい。