\[\newcommand{\TT}[1]{\texttt{#1}} \newcommand{\uB}[2]{{\underbrace{\TT{#1}}_{\TT{#2}}}}\]

1. ブール代数

この章から、コンピューターのハードウェアの話に入ります。

コンピューターの複雑な動作は、0と1のビット列の演算の積み重ねで成り立っています。次の章では、論理回路を簡単にする方法と、2進法による2つの数の足し算を行う加算回路の作り方を学びます。この章では、その基礎となるブール代数と、ブール代数の式を電子回路で表す論理回路を学びます。

シャノンは、情報理論の発表よりも約10年さかのぼった1937年に、MITの修士論文「リレーとスイッチング回路の記号解析」で、リレー回路の設計にある種の代数の体系が使えることを明らかにしました。これは彼が21歳のときの仕事で、後に「20世紀で最も重要な修士論文の一つ」と評されることもあります。当時は電話の自動交換機の設計が主な応用でした。しかし、電磁石を用いた機械的なスイッチの仕組みであるリレーから、半導体を用いたスイッチになり、コンピューターの設計に用いられるようになっても彼の理論は依然として有効であり、現在のコンピューターの論理回路設計の基礎となっています。

シャノンが用いた代数の体系はブール代数です。ブール代数は、19世紀の数学者ブールによって提案された体系を発展させたものです。ブールは、30代後半に発表した著書「論理と確率の数学的な理論の基礎となる思考法則の研究」(1854年)の中で、アリストテレスの論理学を拡張し、代数の体系として論理学を位置づけました。人間の推論を記号の操作として表すという考え方は、記号と規則で推論を行う人工知能の研究（1950年代以降の初期の人工知能や、1980年代に広まったエキスパートシステムなど）にも通じるものです。ブール代数は論理学の中でも古典命題論理と密接な関係にあり、古典命題論理のモデル（意味論）として用いられています。

1.1. 歴史的背景と人物エピソード

ジョージ・ブールの肖像
図 1. ジョージ・ブール

ジョージ・ブール(1815〜1864)は、チャールズ・バベッジと同じくヴィクトリア朝時代の英国の人です。家業が傾いたため、16歳で学校の助教師として働き始め、それ以降は独学で当時の最先端の数学を身につけ、数々の数学論文を発表します。大学で学ぶことはなく学位も持っていませんでしたが、その業績はすでに広く知られており、1849年、33歳のときにアイルランドで新設された大学(クイーンズ・カレッジ・コーク)の数学の教授になります。

現在の人工知能を牽引する深層学習（ディープラーニング）の生みの親の一人で、深層学習界のゴッドファーザーと呼ばれ、2024年にノーベル物理学賞を受賞したジェフリー・ヒントンは、ブールの玄孫（やしゃご: 孫の孫、つまり、ひ孫の子）です。また、ブールと交流のあった数学者ド・モルガンは、「世界初のプログラマ」とよばれることのあるエイダ・ラブレスに、主に手紙で数学を教えていました。

1.2. 論理演算子

コンピューター内部では0と1を値とする演算だけを用いて、複雑な計算が行われています。以下では、まず3つの基本となる論理演算子と、それに対応するデジタル回路の基本要素である論理ゲートを導入します。

ここでは、値として0と1だけを扱う2要素ブール代数を学びます。一般のブール代数には、集合の和・積・補集合を扱うものなどもあります。2つの値に対する演算(二項演算子)として論理積（\(\cdot\)）と論理和（\(+\)）を、1つの値に対する演算(単項演算子)として否定(値や変数の上に棒を引いて \(\bar x\) のように書く)を、以下のように定義します。

論理積

\[\begin{align} 0\cdot0 &= 0\\ 0\cdot1&=0\\ 1\cdot0&=0\\ 1\cdot1&=1 \end{align}\]

0と1だけについてみれば、論理積は普段の掛け算と同じ結果になります。

論理和

\[\begin{align} 0+0 &= 0 \\ 0+1&=1 \\ 1+0&=1 \\ 1+1&=1 \end{align}\]

論理和では \(1+1=1\) となることに注意してください。

否定

値の上に引いた棒で否定を表し、次のように定義します。

\[\begin{align} \bar 0 &= 1 \\ \bar 1 &=0 \end{align}\]

否定は値を0と1の間で反転する演算です。ブール代数における0と1を「偽」と「真」におきかえれば、論理和は命題論理の「または」に対応し、論理積は命題論理の「かつ」に対応しています。また、当然ですが \(0\neq 1\) で、変数は0か1どちらかの値しかとりません。つまり、\(x\neq 0\) なら必ず \(x=1\) であり、\(x\neq 1\) なら必ず \(x=0\) です。

この演算は自然に次のようなスイッチの配置として解釈できます。

ANDゲート

直列につないだ2つのスイッチと電球
図 2. 直列のスイッチ

2つの直列に接続したスイッチ \(x\) と \(y\) を考えます。右の図では、\(x\) と \(y\) の両方のスイッチがONになったときだけ電球に光が点きます。スイッチがOFFのとき0、ONのとき 1、電球のONとOFFも同様に値0と1にそれぞれ対応させます。すると電球のONとOFFは、\(x\) と \(y\) の論理積で計算できます。これを \(x\cdot y\) と書きます（曖昧さがなければ「\(\cdot\)」は省略して、\(xy\) とも書きます）。また、記号として \(x\land y\) を用いることもあります。

ANDゲート
図 3. ANDゲートの記号

デジタル回路ではこのスイッチの役割をはたす回路をANDゲートとよび、右図の記号で表します。左側の2本の線が入力、右側の1本が出力です。

表 1. 論理積
\(x\) \(y\) \(x\cdot y\)

0

0

0

0

1

0

1

0

0

1

1

1

ORゲート

並列につないだ2つのスイッチと電球
図 4. 並列のスイッチ

こんどは2つの並列に接続したスイッチ \(x\) と \(y\) を考えます。右の図では、\(x\) と \(y\) のいずれか1つでもスイッチがONになれば電球に光が点きます。すると電球のON/OFFは \(x\) と \(y\) の論理和で計算できます。これを \(x+y\) と書きます（記号として \(x\lor y\) を用いることもあります）。 スイッチ \(x\) と \(y\) は、両方をONにしても電球はONになりますから、\(1+1=1\) となるわけです。

ORゲート
図 5. ORゲートの記号

デジタル回路ではこのスイッチの役割をはたす回路をORゲートとよび、右図の記号で表します。

表 2. 論理和
\(x\) \(y\) \(x+y\)

0

0

0

0

1

1

1

0

1

1

1

1

NOTゲート

押すと切れるスイッチと電球
図 6. 押すと切れるスイッチ

否定は、論理積や論理和と異なり、1つの値に対する演算（単項演算）です。右図のようなスイッチを考えます。このスイッチは、ふだんは接点がつながっていて(ON)、押すと接点が離れてOFFになります。押すを1、離すを0とすると、電球はスイッチを押すと消え、スイッチを離すと点きます。このように逆の振る舞いをするスイッチを「否定」演算として定義します。値や変数の上に棒を引いて \(\bar x\) のように表現します（記号として \(\neg x\) または \(x'\) を用いることもあります）。

NOTゲート
図 7. NOTゲートの記号

デジタル回路では、このスイッチの役割をはたす回路をNOTゲートとよび、右図の記号で表します。出力側の小さな丸が「否定」を表します。

表 3. 否定
\(x\) \(\bar x\)

0

1

1

0

【身近なブール代数：検索】

論理積・論理和・否定は、抽象的な 0 と 1 の演算にみえますが、実は毎日のように使っています。検索エンジンで「コンピューター 歴史」と空白で区切って打てば両方を含むページが(多くの検索エンジンでは空白が AND の意味になります)、「猫 OR 犬」なら少なくとも一方を含むページが、「マック -ハンバーガー」(マイナスは否定)なら「ハンバーガー」という語を含まない「マック」のページが絞り込まれます。図書館の蔵書検索やデータベースの条件指定(SQL の WHERE 句など)も同じ仕組みです。各ページが条件に合うかどうかを 1(合致)か 0(非合致)で判定し、AND・OR・NOT で組み合わせているのです。こうした検索は、ブールの名にちなんでブール検索ともよばれます。

1.3. ブール代数の基本性質

ブール代数で定義された3つの演算、論理積、論理和、否定と、定数0,1、および括弧を用いて論理式を構成できます。論理式では、演算の優先順位を、我々が普段慣れ親しんでいる算術演算と同様に定めます。つまり、括弧で順序が明示されていないときは、否定を最も強く（最初に）計算し、次に論理積、最後に論理和を計算することにします。 たとえば、\(x+y\cdot z\) は、 \((x+y)\cdot z\) ではなく、\(x+(y\cdot z)\) の順に計算することとします。

表 4. 基本法則

単位元

\(x\cdot 1=x\)

\(x+0=x\)

零元

\(x\cdot 0=0\)

\(x+1=1\)

冪等律

\(x\cdot x=x\)

\(x+x=x\)

結合律

\(x\cdot(y\cdot z) = (x\cdot y)\cdot z\)

\(x+(y+z)=(x+y)+z\)

相補律

\(x\cdot \bar x = 0\)

\(x+\bar x = 1\)

交換律

\(x\cdot y = y\cdot x\)

\(x+ y = y+ x\)

分配律

\(x\cdot (y+z) = x\cdot y + x\cdot z\)

\(x+ y\cdot z = (x+y)\cdot(x+z)\)

吸収律

\(x+ x\cdot y = x\)

\(x\cdot(x+y) = x\)

復元律

\(\bar{\bar x}=x\)

ド・モルガンの法則

\(\overline{x+y} = \bar x\cdot \bar y\)

\(\overline{x\cdot y} = \bar x + \bar y\)
単位元

演算を適用しても結果が変わらない値を単位元とよびます。つまり、論理積では1、論理和では0が単位元となります。 スイッチを思い描くと、単位元の左側の式は、常にONになっているスイッチと直列に繋がれたスイッチ \(x\) があると、\(x\) によって、全体のスイッチのON/OFFが決まることを表しています。また、右側の式は、常にOFFになっているスイッチと並列に繋がれたスイッチ \(x\) があると、\(x\) によって全体のスイッチのON/OFFが決まることを表しています。

零元

演算の適用結果が定数となるような値を零元とよびます。つまり、論理積では0、論理和では1が零元となります。これも単位元と同様にスイッチの挙動で理解してみましょう。

冪等律

同じ値同士の論理積と論理和は、やはり同じ値になります。同じ動作をするスイッチを直列にしても並列にしても、1つのときと挙動は同じです。

結合律

論理積と論理和は、2つの値に適用される演算子（二項演算子）ですが、計算の結果は括弧の順番に依存しませんので、\(x\cdot y\cdot z\) のように外しても構いません。

分配律

左側は普段の計算と同じ形ですが、右側の性質は普段の算術演算では成り立たないことに注意してください。たとえば普段の計算では \(1+2\times 3=7\) ですが、\((1+2)\times(1+3)=12\) です。ブール代数では右側も成り立ちます(後の「分配律をスイッチで確かめる」を参照)。

復元律

否定の否定は肯定になります。

ド・モルガンの法則

否定を括弧の中に分配すると、論理積と論理和が入れ替わります。日常の言葉でも同じことが起きています。「赤くて(かつ)丸い、ではない」は、「赤くない、または、丸くない」と同じです(両方を満たすものだけを否定するので、どちらか一方でも欠ければよい)。逆に「赤い、または、丸い、ではない」は「赤くなく、かつ、丸くない」と同じです。後で学ぶ論理回路の簡単化やNANDゲートだけによる回路構成で、くり返し使う重要な法則です。

吸収律の証明

x+x・yのスイッチ回路
図 8. 吸収律の左辺 \(x+x\cdot y\) のスイッチ

ここで、いくつかの方法で吸収律

\[x+ x\cdot y = x\]

が成り立つことを確認してみましょう。左辺の式 \(x+ x\cdot y\) はスイッチとして解釈すると右図のようになります。このスイッチの挙動は \(x\) によって決まることは明らかでしょう。

厳密に吸収律を証明するには、次の2通りの方法があります。1つ目の方法は以下のように変数への値の割当てをすべて列挙する方法です。次の表の1列目(左端の列)と4列目(右端の列)の値が、どの行でも等しいことから、吸収律が証明できます。このように、論理式に含まれる変数への値(0と1)の割当てをすべて列挙して、対応する論理式の値を並べた表を真理値表といいます。

表 5. 吸収律の真理値表
\(x\) \(y\) \(x\cdot y\) \(x + x\cdot y\)

0

0

0

0

0

1

0

0

1

0

0

1

1

1

1

1

基本法則の表の法則は、どれも真理値表で証明できます。たとえばド・モルガンの法則 \(\overline{x+y} = \bar x\cdot \bar y\) は、次の表の4列目と7列目が等しいことから確かめられます。

表 6. ド・モルガンの法則の真理値表
\(x\) \(y\) \(x+y\) \(\overline{x+y}\) \(\bar x\) \(\bar y\) \(\bar x\cdot\bar y\)

0

0

0

1

1

1

1

0

1

1

0

1

0

0

1

0

1

0

0

1

0

1

1

1

0

0

0

0

変数の数が増えるに従って、すべての変数への値の割当てを列挙する真理値表に基づく方法はだんだんと手に負えなくなります。なぜなら、変数が \(n\) 個あるとき、真理値表に必要な組合せの数は \(2^n\) になり変数の数に対して計算時間は指数的に増加するからです。変数が20個だと、その数は \(2^{20}=1{,}048{,}576\) で100万を超えます。それでも、まだコンピューターを使えば大したことのない数です。では、変数が40個を超えるとどうでしょう。組合せは1兆を超えます。仮に毎秒10億通りを確認できても、40変数で約18分、60変数で約37年です。実際の時間は論理式の大きさや実装・機器にも依存します。単純な列挙法はすぐに手に負えなくなります。

2つ目の証明方法は、以下のように代数的に式変形して求める方法です（基本法則の表で吸収律より上にある性質は、すでに成り立つものとして使います）。

\[\begin{align} x+x\cdot y &= x\cdot 1 + x\cdot y & (単位元)\\ &= x\cdot(1 + y) & (分配律)\\ &= x\cdot 1 & (零元)\\ &= x & (単位元) \end{align}\]

分配律をスイッチで確かめる

基本法則のうち、分配律の右側 \(x+ y\cdot z = (x+y)\cdot(x+z)\) は、普段の計算にはない性質なので、スイッチで確かめておきましょう。左辺 \(x+ y\cdot z\) は、スイッチ \(x\) と、直列につないだ \(y\)・\(z\) とを並列につないだ回路です(下の左図)。右辺 \((x+y)\cdot(x+z)\) は、「\(x\) と \(y\) の並列」と「\(x\) と \(z\) の並列」を直列につないだ回路です(下の右図)。右図の2つの \(x\) は連動していて、同時にON・OFFすると考えてください。

x+y・zのスイッチ回路
図 9. 分配律の左辺 \(x+ y\cdot z\)
(x+y)・(x+z)のスイッチ回路
図 10. 分配律の右辺 \((x+y)\cdot(x+z)\)

  • \(x\) がONのとき: 左図は上の経路で電流が流れます。右図も、左右どちらの並列部分も \(x\) の経路で通じるので流れます。

  • \(x\) がOFFのとき: 左図は下の経路、つまり \(y\) と \(z\) が両方ONのときだけ流れます。右図も、左の並列部分には \(y\)、右の並列部分には \(z\) が必要なので、\(y\) と \(z\) が両方ONのときだけ流れます。

どちらの場合も2つの回路の振る舞いは同じなので、左辺と右辺は等しいことがわかります。

双対原理

ブール代数の基本法則で示した表は、復元律を除いてすべて左右で等式が対称性を持っています。一方の等式で、

0と1を入れ替えて、かつ論理和(\(+\))と論理積(\(\cdot\))を入れ替える

ことによって、もう一方の等式が得られます。このように入れ替えて得られる式を、もとの式の双対といいます。ブール代数では、我々が慣れ親しんでいる算術演算と異なり、積と和に対称性があるため、この性質が成り立ちます。基本法則の組が双対になっているので、基本法則を使って証明できた等式があれば、証明の各段階を双対に置き換えることで、その双対の等式も成り立ちます。これを双対原理といいます。

入れ替えるときは、計算の順序が変わらないように必要に応じて括弧を補います。たとえば吸収律の左側 \(x+ x\cdot y = x\) は \(x+ (x\cdot y) = x\) という意味なので、0と1、\(+\) と \(\cdot\) を入れ替えると、右側の \(x\cdot(x+y) = x\) が得られます。同じ手順を分配律の左側 \(x\cdot (y+z) = x\cdot y + x\cdot z\) に適用して、右側の等式が出てくることを確かめてみましょう。

答え

\(x\cdot (y+z) = (x\cdot y) + (x\cdot z)\) の論理積と論理和を入れ替えると、\(x+ (y\cdot z) = (x+ y) \cdot (x+ z)\) となり、分配律の右側が得られます。

発展: ド・モルガンの法則を他の法則から導く(読み飛ばせます)

ド・モルガンの法則は真理値表によって簡単に証明できますが、以下のように他の基本法則から代数的に導出することもできます。

まず、準備として

\[ x+y=1 \quad\text{かつ}\quad x\cdot y=0 \quad\text{ならば}\quad x=\bar y\]

を証明します。

以下の式を考えます。

\[ (x+y)\cdot\bar y = x\cdot\bar y + y\cdot\bar y = x\cdot\bar y + 0 = x\cdot\bar y\]

ここで、\(x+y=1\) と仮定すると、左辺は以下のようにも変形できます。

\[ (x+y)\cdot\bar y = 1\cdot\bar y = \bar y\]

よって、\(x+y=1\) の仮定のもとで、

\[ x\cdot\bar y = \bar y \qquad \cdots①\]

が成り立ちます。

次に以下の式を考えます。

\[ x\cdot\bar y + x\cdot y = x\cdot(\bar y + y) = x\cdot 1 = x\]

ここで、\(x\cdot y=0\) を仮定すると、左辺は以下のようにも変形できます。

\[ x\cdot\bar y + x\cdot y = x\cdot\bar y + 0 = x\cdot\bar y\]

よって、\(x\cdot y=0\) の仮定のもとで、

\[ x = x\cdot\bar y \qquad \cdots②\]

が成り立ちます。

よって、①と②から以下が成り立ちます。

\[x = \bar y\]

これを利用して、以下を示します。

\[ (x+y) + \bar x\bar y = 1 \quad\text{かつ}\quad (x+y)\cdot \bar x\bar y=0 \quad\text{から}\quad \overline{x + y} = \bar x \bar y\]
\[\begin{align*} (x+y) + \bar x\bar y &= y + (x+\bar x\bar y) & \text{(結合・交換律)}\\ &= y + (x+\bar y) & \text{(冗長律、後の例2で証明)}\\ &= x + (y+\bar y) & \text{(結合・交換律)}\\ &= x + 1 & \text{(相補律)}\\ &= 1 & \text{(零元)}\\ \end{align*}\]
\[\begin{align*} (x+y) \cdot \bar x\bar y &= x\cdot\bar x\bar y + y\cdot\bar x\bar y & \text{(分配律)}\\ &= (x\bar x)\bar y + (y\bar y)\bar x & \text{(交換・結合律)}\\ &= 0\cdot\bar y + 0\cdot\bar x & \text{(相補律)}\\ &= 0 + 0 & \text{(零元)}\\ &= 0 \end{align*}\]

よって、以下が成り立ちます。

\[\overline{x + y} = \bar x\cdot \bar y \qquad \cdots③\]

また、これを用いて以下もただちに成り立ちます。

\[\begin{align*} \overline{x\cdot y} &= \overline{\bar{\bar x}\cdot \bar{\bar y}} & \text{(復元律)}\\ &= \overline{\overline{\bar x + \bar y}} & \text{(③)}\\ &= \bar x + \bar y & \text{(復元律)} \end{align*}\]

1.4. 論理式の簡単化

同じ論理関数を表す論理式はいくつもあり、式が簡単なほど、少ない論理ゲートで回路を作れます。ここでは基本法則を使って式を簡単にする練習をし、あわせて論理式と論理回路の対応を見ていきます。

論理式を論理回路にするには、式を計算する順にゲートを並べます。変数を左端の入力とし、否定、論理積、論理和の順(括弧があれば内側から)にゲートを置いて、最後のゲートの出力を回路全体の出力にします。この教材ではゲートの入力を2つに限るので、\(a+b+c\) のように3つ以上をまとめる演算は、\((a+b)+c\) のようにゲートを2つ使って表します。逆に、回路図から論理式を読むときは、入力側(左)から順に、各ゲートの出力にその時点の式を書き込んでいきます(例3)。

【例1】

式 \(x\cdot y + x\cdot \bar y\) を簡単化せよ
\[\begin{align} x\cdot y + x\cdot \bar y &= x\cdot(y+\bar y) & (分配律)\\ &= x\cdot 1 & (相補律)\\ &= x & (単位元) \end{align}\]

式 \(x\cdot y + x\cdot \bar y\) は、論理ゲートで表現すると下図のようになります。青い文字は、各ゲートの出力が表す式です。

x・y+x・ȳの論理回路
図 11. 例1の論理回路

論理回路では線が交差しているだけではつながっていることになりませんので注意してください。黒丸の部分がつながっている箇所です。上の図では、\(x\) から下へ延びる線が \(y\) の横線と交差していますが、黒丸がないのでつながっていません。 この論理回路は、結局 \(x\) と等しいので、ただ \(x\) を結線すればよいということになります。コンピューター等の論理回路設計では、できるだけ回路を単純化して、できるだけ少ない論理ゲートで回路を組むことがコスト、消費電力、速度の面から重要です。

また、双対原理を用いると

\[(x+ y)\cdot (x+\bar y)=x\]

が成り立つこともただちにわかります。

【例2】

式 \(x+\bar x\cdot y\) を簡単化せよ
\[\begin{align} x+\bar x\cdot y &= (x+\bar x)\cdot(x+y) & (分配律)\\ &= 1\cdot (x+y) & (相補律)\\ &= x+y & (単位元) \end{align}\]

この等式 \(x+\bar x\cdot y = x+y\) を冗長律とよびます（後の「簡単化のコツ」や章末の練習問題でも補題として使います）。

式 \(x+\bar x\cdot y\) は、論理ゲートで表現すると下図のようになります。

x+x̄・yの論理回路
図 12. 例2の論理回路

この論理回路が簡単化によってORゲート1つになります。

ORゲート
図 13. 例2を簡単化した回路
【例3】

次の論理回路を簡単化せよ
例3の論理回路
図 14. 例3の論理回路

まず、\(x\) と \(y\) を左から右にたどって、各ゲートの出力を式で表します。上のANDゲートには \(x\) と \(\bar y\) が入るので出力は \(x\cdot\bar y\)、下のANDゲートの出力は \(x\cdot y\)、ORゲートの出力はその論理和、最後のANDゲートはそれと \(y\) の論理積です。

各ゲートの出力に途中の論理式を書き込んだ例3の論理回路
図 15. 例3の回路の各ゲートの出力を式で表す

こうして得られた式を簡単化します。

\[\begin{align} (x\cdot \bar y + x\cdot y)\cdot y &= x\cdot \bar y \cdot y + x\cdot y\cdot y & \quad (分配律・結合律)\\ &= x\cdot 0 + x\cdot y\cdot y & \quad (交換律・相補律)\\ &= 0 + x\cdot y\cdot y & \quad (零元)\\ &= x\cdot y\cdot y & \quad (交換律・単位元)\\ &= x\cdot y & \quad (冪等律)\\ \end{align}\]

よって、簡単化によってANDゲート1つになります。なお、括弧の中の \(x\cdot \bar y + x\cdot y\) は例1の式と同じなので、例1の結果を使えば \((x\cdot \bar y + x\cdot y)\cdot y = x\cdot y\) とすぐに求めることもできます。

ANDゲート
図 16. 例3を簡単化した回路

簡単化のコツ

例1〜例3でみた変形を、よく使うパターンとして整理しておきます。どれも基本法則の組合せにすぎませんが、最初にどの法則を狙うかの見当がつくと、式変形がぐっと楽になります。

戦略1：共通因子をくくり出す

基本形：\(xy + xz = x(y + z)\)

例：

\[\begin{align} abc + abd + acd &= a(bc + bd + cd)\\ xy + \bar{x}y &= y(x + \bar{x}) = y \cdot 1 = y \end{align}\]
戦略2：相補律で1や0を作る

基本形：\(x + \bar{x} = 1\), \(x \cdot \bar{x} = 0\)

例：

\[\begin{align} x(y + \bar{y}) &= x \cdot 1 = x\\ x + y\bar{y} &= x + 0 = x \end{align}\]
戦略3：吸収律を探す

基本形：\(x + xy = x\), \(x(x + y) = x\)

例：

\[\begin{align} a + abc &= a\\ a(a + b + c) &= a \end{align}\]
戦略4：冗長律を使う

基本形：\(x + \bar{x}y = x + y\)

覚え方：「\(x\)が真なら全体が真、\(x\)が偽なら \(y\) で決まる」

例：

\[\begin{align} a + \bar{a}bc &= a + bc\\ xy + \bar{x}yz &= xy + yz \quad \text{（yでくくってから冗長律）} \end{align}\]

発展形(合意定理)：\(xy + \bar{x}z + yz = xy + \bar{x}z\)

\(yz\) の項(合意項)は前の2項があれば不要になります。この等式の証明は、章末の練習問題の問題6で扱います。

実践的な解法手順

手順1：項を整理・グループ化

\[\text{例：} abc + \bar{a}bc + abcd + \bar{a}bcd \rightarrow bc(a + \bar{a}) + bcd(a + \bar{a})\]

手順2：相補律で簡単化

\[\rightarrow bc \cdot 1 + bcd \cdot 1 = bc + bcd\]

手順3：吸収律で最終簡単化

\[\rightarrow bc(1 + d) = bc \cdot 1 = bc\]

【練習問題】式の簡単化

練習: 式の簡単化

次の論理式を簡単化せよ。

  1. \(x + \bar{x}yz\)

  2. \(ab + \bar{a}c + bc\)

  3. \(x(y + z) + \bar{x}(y + z) + yz\)

  4. \(xyz + xy\bar z + x\bar y\)

  5. \(\overline{\bar x + y} + \overline{x\cdot\bar y}\)（ド・モルガンの法則を使う）

解答

  1. \(x + yz\)。冗長律 \(x+\bar x\cdot Y = x+Y\) の \(Y\) を \(yz\) とみなします。

  2. \(ab + \bar{a}c\)。合意定理(戦略4の発展形)そのものです。基本法則だけで示すには、\(bc\) に \(1=a+\bar a\) を掛けて分けます。

    \[\begin{align} ab + \bar{a}c + bc &= ab + \bar{a}c + (a+\bar a)bc & \text{（相補律・単位元）}\\ &= (ab + abc) + (\bar{a}c + \bar{a}bc) & \text{（分配律・交換律・結合律）}\\ &= ab + \bar{a}c & \text{（吸収律）} \end{align}\]

  3. \(y+z\)。共通因子 \(y+z\) をくくり出します。

    \[\begin{align} x(y + z) + \bar{x}(y + z) + yz &= (y + z)(x + \bar{x}) + yz & \text{（分配律）}\\ &= (y + z) \cdot 1 + yz & \text{（相補律）}\\ &= y + z + yz & \text{（単位元）}\\ &= y + z & \text{（吸収律）} \end{align}\]

    最後の段階は、\(z + yz = z\) に吸収律を使っています。

  4. \(x\)。先に \(xy\) でくくると、例1と同じ形が2回現れます。

    \[\begin{align} xyz + xy\bar z + x\bar y &= xy(z + \bar z) + x\bar y & \text{（分配律）}\\ &= xy + x\bar y & \text{（相補律・単位元）}\\ &= x(y + \bar y) = x & \text{（分配律・相補律・単位元）} \end{align}\]

  5. 常に \(1\)。まず2つの否定にド・モルガンの法則を適用してから簡単化します。

    \[\begin{align} \overline{\bar x + y} + \overline{x\cdot\bar y} &= \bar{\bar x}\cdot\bar y + (\bar x + \bar{\bar y}) & \text{（ド・モルガン）}\\ &= x\cdot\bar y + \bar x + y & \text{（復元律）}\\ &= \bar x + x\cdot\bar y + y & \text{（交換律）}\\ &= \bar x + \bar y + y & \text{（冗長律）}\\ &= \bar x + 1 = 1 & \text{（相補律・零元）} \end{align}\]

    つまり、この論理式は入力によらず常に \(1\) となります（恒真）。冗長律は \(\bar x + \bar{\bar x}\cdot\bar y\) の形で使っています。否定の否定を外すのを忘れて \(\bar x\cdot\bar y + (x+y)\) などとしないよう注意しましょう。

1.5. プログラムによる論理演算

ほぼすべての汎用プログラミング言語は、通常の算術演算に加えて論理演算のための文法を備えていますので、実際に真理値表を作成して確認することができます。例1の真理値表を作成するプログラムを Python と Julia で示します。

for x in [False, True]:
  for y in [False, True]:
    print(x, y, (x and y) or (x and not y), sep='\t')
for x ∈ [false, true], y ∈ [false, true]
  println(x, "\t", y, "\t", (x & y) | (x & !y))
end

どちらも、次のように4行の真理値表を出力します(Python の場合。Julia では false・true と小文字で表示されます)。3列目が1列目の \(x\) と一致しており、例1の簡単化の結果 \(x\cdot y + x\cdot \bar y = x\) を確かめられます。

False	False	False
False	True	False
True	False	True
True	True	True

2つの論理式が等しいかどうかも、すべての割当てを試して確かめられます。次の Python プログラムは、後の練習問題6の等式(合意定理)の両辺を、0と1の8通りの割当てで比べます。& は論理積、| は論理和、1 - x は否定の代わりです。

from itertools import product

ok = True
for x, y, z in product([0, 1], repeat=3):   # 8通りの割当て
    lhs = (x & y) | ((1 - x) & z) | (y & z)
    rhs = (x & y) | ((1 - x) & z)
    print(x, y, z, lhs, rhs)
    ok = ok and lhs == rhs
print("すべて等しい" if ok else "異なる割当てがある")

このように真理値表を作って確かめる方法は確実ですが、変数が増えると割当ての数 \(2^n\) が急激に増えることは、吸収律の証明のところで見たとおりです。

1.6. 論理式の標準形

\(n\) 個の値（0または1）を受け取り、1つの値（0または1）を返す関数を \(n\) 変数論理関数といいます。より形式的に書くと、以下の \(f\) によって定義される関数のことです。

\[f: \{0,1\}^n \rightarrow \{0,1\}\]

たとえば、論理積 \(f(x,y)=x\cdot y\) は2変数論理関数ですし、否定 \(f(x)=\bar x\) は1変数論理関数です。 ところで、1変数論理関数は何種類存在するでしょうか。真理値表で列挙してみましょう。\(x=0,1\) の2行それぞれに出力0/1の2通りがあるので、出力列の組合せは \(2^2=4\) 通りあり、対応する関数が \(f_1\)から \(f_4\) まで4種類あることがわかります。

  • \(f_1(x)=0\)

  • \(f_2(x)=1\)

  • \(f_3(x)=x\)

  • \(f_4(x)=\bar x\)

表 7. 1変数論理関数の真理値表
\(x\) \(f_1\) \(f_2\) \(f_3\) \(f_4\)

0

0

1

0

1

1

0

1

1

0

2変数論理関数の真理値表は、行数が \(2^2=4\) なので、出力列の組合せは \(2^4=16\) 通り、つまり16種類の関数が存在することになります。そのうち、これまでに出てきた2変数の演算は論理積と論理和です。後で扱う実質含意もこの16種類の一つで、\(x\) だけ、\(\bar y\) だけ、定数0などを返す関数も16種類に含まれます。 一般に \(n\) 変数の論理関数は \(2^{2^n}\) 個存在します。

簡単化の例題でも見てきたように1つの論理関数にはいろいろな論理式の表現があります。2つの論理式が同じ論理関数を表すかどうか(等価性)の判定は、真理値表を使えば必ずできますが、変数が多いときに効率よく判定する方法は知られていません。「等しくない」ことの判定は、後の章で学ぶ充足可能性問題(SAT)と同じ難しさをもつ(NP完全である)ことが知られています。等価性を直接示さなくても、まずは、論理式の形式をできるだけ標準化しておくと便利です。そこで、論理式の標準形を定義するための準備をします。

以降では論理積の演算子「\(\cdot\)」をたびたび省略しますので注意してください。

【リテラル】

論理式に含まれる変数 \(x\) について、\(x\) もしくは \(\bar x\) をリテラルとよぶ。特に、\(x\) を正リテラル、\(\bar x\) を負リテラルとよぶ。

例)

論理式 \(x\bar y (x+\bar z)\) において、\(x\), \(\bar y\), \(\bar z\) は各々リテラルです。
【項】

同じ変数からなるリテラルが2回以上出現しないようなリテラルの論理積、またはリテラルの論理和を項とよぶ。

リテラルの論理積による項を積項、論理和による項を和項とよぶ。

例)

論理積 \(x\bar y \bar z\) は項ですが、\(x\bar y \bar x\) は \(x\) のリテラルが2回出現しているので項ではありません。また、論理積にはなっていませんが \(\bar x\) のような単独のリテラルも項とします。
例)

論理和 \(x+\bar y + \bar z\) は項ですが、\(x + \bar y + \bar x\) は \(x\) のリテラルが2回出現しているので項ではありません。また、論理和にはなっていませんが \(\bar x\) のような単独のリテラルも項とします。

単独のリテラルからなる項については、積項かつ和項であるとします。

【積和形】

積項の論理和の形をしている論理式を積和形とよぶ。

例)

\(x \bar y \bar z + y z + z\) は積和形です。
【和積形】

和項の論理積の形をしている論理式を和積形とよぶ。

例)

\((x + \bar y + \bar z) (y + z) z\) は和積形です。
【最小項】

論理関数の変数すべてをリテラルとして含む積項を最小項(minterm)とよぶ。

【積和標準形】

論理関数を重複のない最小項の論理和として表した論理式を積和標準形(完全積和形。英語では canonical DNF)とよぶ。なお、単に DNF(Disjunctive Normal Form)といえば、最小項に限らない積和形一般を指すことが多い。

最小項は、ただ1つの入力パターン(0,1の値の組合せ)のみで1となる項です。

例(2変数 \(f(x,y)\)のケース)

  • 項 \(\bar x\bar y\)

    • \((x, y)=(0,0)\) でのみ1なので最小項

  • 項 \(\bar xy\)

    • \((x, y)=(0,1)\) でのみ1なので最小項

  • 項 \(x\)

    • \((x, y)=(1,0)\) または \((1,1)\) で1 (よって、\(x\)は2変数の論理関数においては最小項ではない)

【最大項】

論理関数の変数すべてをリテラルとして含む和項を最大項(maxterm)とよぶ。

【和積標準形】

論理関数を重複のない最大項の論理積として表した論理式を和積標準形(完全和積形。英語では canonical CNF)とよぶ。なお、単に CNF(Conjunctive Normal Form)といえば、最大項に限らない和積形一般を指すことが多い。

最大項は、ただ1つの入力パターン(0,1の値の組合せ)のみで0となる項です。

例(2変数 \(f(x,y)\)のケース)

  • 項 \(x+y\)

    • \((x,y)=(0,0)\) でのみ 0 なので最大項

    • 0になる組合せ1個、1になる組合せ3個

  • \(x+\bar y\)

    • \((x,y)=(0,1)\) でのみ0 なので最大項

    • 0になる組合せ1個、1になる組合せ3個

  • \(x\)

    • \((x,y)=(0,0)\)または \((0,1)\) で0なので2変数の論理関数においては最大項ではない

    • 0になる組合せ2個、1になる組合せ2個

以下では、吸収律の左辺 \(f(x,y)=x+x\cdot y\) の真理値表を例に、真理値表から標準形を作る方法を説明します。

表 8. 吸収律の左辺 \(f(x,y)=x+x\cdot y\) の真理値表
\(x\) \(y\) \(f(x,y)\)

0

0

0

0

1

0

1

0

1

1

1

1

積和標準形

上記の真理値表の3列目（一番右側の列）が1になっている行は、3行目と4行目（下側の2行）です。3行目は \((x,y)=(1,0)\)、4行目は \((x,y)=(1,1)\) であり、\(x\)と\(y\)が各々この値をとったときだけ、論理関数 \(f(x,y)\) は1となることから、以下のように表すことができます（\(x=1\) を \(x\)、 \(x=0\) を \(\bar x\) として、\(y\) も同様に変換してから項を作ります）。

\[f(x,y)=x\bar y + x y\]

この式を言葉で表すと、「この論理式 \(f(x,y)\) が \(1\) となるのは『\(x=1\) かつ \(y=0\) のとき』または、『\(x=1\) かつ \(y=1\) のとき』の2つのみである」ということになります。この論理関数の各項は \(x\) と \(y\) を含んでいるので、いずれも最小項であり、その積和形なので積和標準形になっています。

手順を図にまとめると次のようになります。どんな真理値表が与えられても、この手順で機械的に論理式が作れます。

真理値表から積和標準形を作る手順
図 17. 真理値表から積和標準形を作る手順

後は、積和標準形を簡単化することにより、以下の結果が得られます（この場合は真理値表をみれば明らかですが…）。

\[\begin{align} f(x,y)&=x\bar y + x y\\ &=x (\bar y + y) & \quad (分配律)\\ &=x\cdot 1 & \quad (相補律)\\ &=x & \quad (単位元) \end{align}\]

和積標準形

同様に真理値表から和積標準形を作ってから、論理式を導出することもできます。今度は、\(f\) が0になる行に注目します。

同じ吸収律の真理値表で、3列目（一番右側の列）が0になっている行は、1行目と2行目（上側の2行）です。1行目は \((x,y)=(0,0)\)、2行目は \((x,y)=(0,1)\) であり、\(x\)と\(y\)が各々この値をとったときだけ、論理関数 \(f(x,y)\) は 0 となることから、以下のように表すことができます（\(x=0\) を \(x\)、 \(x=1\) を \(\bar x\) として、\(y\) も同様に変換してから項を作ります）。

\[f(x,y)=(x + y)(x + \bar y)\]

この式を言葉で表すと、「\(f(x,y)\) が0となるのは、\(x+y\) が0になるとき(\((x,y)=(0,0)\))か、\(x+\bar y\) が0になるとき(\((x,y)=(0,1)\))のどちらかで、それ以外は1」ということです。論理積は、どれか1つでも0の因子があれば0になるからです。この論理関数の各項は \(x\) と \(y\) を含んでいるので、いずれも最大項であり、その和積形なので和積標準形になっています。

手順を図にまとめると次のようになります。積和標準形の手順と比べると、選ぶ行(0と1)、否定を付ける条件、つなぐ演算(論理和と論理積)がそれぞれ入れ替わっています。

真理値表から和積標準形を作る手順
図 18. 真理値表から和積標準形を作る手順

直接的ではありませんが、積和標準形からの変形で、和積標準形を導出することもできます。

同じ真理値表で、\(f(x,y)=0\) の行から \(x=0\) を \(\bar x\)、\(x=1\) を \(x\) として最小項を作り、その論理和全体を否定します（\(\overline{f(x,y)}\) の積和標準形を作ることに相当します）。

\[f(x,y)=\overline{\bar x \bar y + \bar xy}\]

これに、ド・モルガンの法則と復元律を適用すると以下の式が得られます。

\[f(x,y)=\overline{\bar x \bar y}\cdot\overline{\bar xy}=(\bar{\bar x} + \bar{\bar y})(\bar{\bar x} + \bar y)=(x + y)(x + \bar y)\]

後は、和積標準形を簡単化することにより、以下の結果が得られます(交換律は省略しています)。

\[\begin{align} f(x,y)&=(x + y)(x + \bar y)\\ &= (x+y)x + (x+y)\bar y & \quad (分配律)\\ &= x + (x+y)\bar y & \quad (吸収律)\\ &= x + x\bar y + y\bar y & \quad (分配律)\\ &= x + x\bar y & \quad (相補律)\\ &=x & \quad (吸収律) \end{align}\]

【練習問題】真理値表から標準形へ

練習: 真理値表から標準形を作る

次の真理値表で表される論理関数 \(f(x,y)\) について、(1) 積和標準形で表し、それを簡単化せよ。(2) 和積標準形で表せ。

\(x\) \(y\) \(f(x,y)\)

0

0

1

0

1

1

1

0

0

1

1

1
解答

(1) \(f(x,y)\) が1となるのは \((x,y)=(0,0),(0,1),(1,1)\) の3行です。各行から最小項(値が1の変数はそのまま、0の変数は否定)を作って論理和をとると、積和標準形

\[f(x,y)=\bar x\cdot\bar y + \bar x\cdot y + x\cdot y\]

が得られます。これを簡単化すると

\[\begin{align} f(x,y) &= \bar x(\bar y + y) + x\cdot y & \text{（分配律）}\\ &= \bar x + x\cdot y & \text{（相補律・単位元）}\\ &= \bar x + y & \text{（冗長律）} \end{align}\]

となります。

(2) \(f(x,y)\) が0となるのは \((x,y)=(1,0)\) の1行だけです。この行から最大項(値が0の変数はそのまま、1の変数は否定)を作ると \(\bar x + y\) となり、和積標準形は最大項1つだけの

\[f(x,y)=\bar x + y\]

です。(1)の簡単化の結果と一致しています。0の行が少ない関数では、和積標準形の方が短くなります。なお、この関数は後の「ブール代数と推論」で扱う実質含意 \(x\rightarrow y\) と同じものです。

1.7. 最小項と最大項

なぜ論理関数の変数すべてを含む項を最小項とよぶのでしょうか。ここでは、2変数 \(x\), \(y\) から構成される論理関数 \(f(x,y)\) について考えてみます。

  • 項 \(\bar xy\) が \(1\) となる \((x,y)\) の組合せは \((0,1)\) のみ

  • 項 \(xy\) が \(1\) となる \((x,y)\) の組合せは \((1,1)\) のみ

これに対して、

  • 項 \(x\) が \(1\) となる \((x,y)\) の組合せは \((1,0)\) または \((1,1)\) の2通り

  • 項 \(\bar y\) が \(1\) となる \((x,y)\) の組合せは \((0,0)\) または \((1,0)\) の2通り

です。つまり、論理関数 \(f(x,y)\) に含まれるすべての変数のリテラルを含む積項は、値が \(1\) となる変数の組合せがちょうど1通りしかなく、これが可能な最小の数なので最小項とよばれるのです。

同様に最大項についても考えてみましょう。

  • 項 \(\bar x + y\) が \(1\) となる \((x,y)\) の組合せは、\((0,0)\), \((0,1)\), \((1, 1)\) の3通り

    • これは、項 \(\bar x + y\) が \(0\) となる \((x,y)\) の唯一の組合せ \((1,0)\) を除く全ての組合せであることに注意

  • 項 \(x + y\) が \(1\) となる \((x,y)\) の組合せは \((0,1)\), \((1,1)\), \((1, 0)\) の3通り

これに対して

  • 項 \(\bar x\) が \(1\) となる \((x,y)\) の組合せは \((0,0)\), \((0,1)\) の2通り

  • 項 \(y\) が \(1\) となる \((x,y)\) の組合せは \((0,1)\), \((1,1)\) の2通り

です。つまり、論理関数 \(f(x,y)\) に含まれるすべての変数のリテラルを含む和項は値が \(1\) となる変数の組合せが最大の3通り(変数の数を \(n\) とすると \(2^n-1\) 通り)存在するので最大項なのです。

ブール代数では、リテラルの論理積も論理和も「項(term)」と呼びます。一方で、論理学ではリテラルの論理和を「節(clause)」と呼びます。

「最小」「最大」という名前は、ブール関数の間の大小関係に由来します。同じ変数 \(x_1, x_2, \ldots, x_n\) 上のブール関数 \(f\) と \(g\) の大小関係を、次のように定義します。

\[f \leq g \;\Leftrightarrow\; \forall (x_1, x_2, \ldots, x_n) \in \{0, 1\}^n \quad f(x_1, x_2, \ldots, x_n) \leq g(x_1, x_2, \ldots, x_n)\]

つまり、すべての入力に対して \(f\) の値が \(g\) の値以下であるとき \(f\leq g\) とします。この大小関係のもとで、最小項は積項(の表す関数)の中で0でない最小のもの、最大項は和項の中で1でない最大のものになっています。

1.8. ブール代数と推論 (とばしてかまいません)

ブール代数はもともと論理的思考の道具として考えられたものですので、簡単な論理推論についてみてみましょう。 \(x\) かつ \(x \rightarrow y\) が成り立てば、推論結果として \(y\) が得られるという推論は、モーダスポネンス(modus ponens、前件肯定)として知られています。

さて、「\(x\) ならば \(y\)」 を表す \(x \rightarrow y\) は、「\(x\) が真ならば \(y\) も真」つまり、「\(x=1\) ならば \(y=1\) 」であり、\(x=1\) であるにもかかわらず \(y=0\) となることはありません。よって、下のような真理値表によって表すことができます。このようにして定義される論理演算子を実質含意(material implication)といい、数学で「ならば」とあれば、この実質含意の意味です（日常的に使う「ならば」からは若干違和感のある定義かもしれません）。

表 9. 実質含意の真理値表
\(x\) \(y\) \(x\rightarrow y\)

0

0

1

0

1

1

1

0

0

1

1

1

この真理値表で \(x\rightarrow y\) の値が0になるのは \((x,y)=(1,0)\) の1行だけです。和積標準形の作り方(「論理式の標準形」の節)にしたがって、この行から最大項を作ってみましょう。値が1の変数は否定して \(\bar x\)、値が0の変数はそのまま \(y\) として論理和を作ると、この行でだけ0になる最大項 \(\bar x + y\) が得られます。0になる行はこの1行だけですから、\(x\rightarrow y\) はこの最大項1つだけからなる和積標準形と等価、つまり \(x\rightarrow y = \bar x + y\) であることがわかります。

今、\(x\) と \(x\rightarrow y\) が成り立っているので、以下のように式を立てて変形することにより、\(y\) が得られます。

\[\begin{align} x\cdot (x\rightarrow y) &= x\cdot (\bar x + y) & \quad \text{（実質含意）}\\ &= x\cdot \bar x + x\cdot y & \quad \text{（分配律）} \\ &= 0 + x\cdot y & \quad \text{（相補律）}\\ &= x\cdot y & \quad \text{（単位元）}\\ \end{align}\]

ここで、前提より \(x=1\) かつ \(x\rightarrow y=1\) なので左辺は \(1\) です。よって \(x\cdot y=1\) となり、これは \(x=1\) かつ \(y=1\) を意味しますから、\(y=1\) が得られます。

このようにして、前提 \(x\) と \(x \rightarrow y\) が真であれば、結論として \(y\) が真であることが代数的にも確認できました。

2. 練習問題

基本の確認から順に並べています。各問題の解答と解説は直後に折りたたんであるので、まず自分で解いてから開いてください。

ブール代数の証明問題は、与えられた規則をもとに式を変形してゆくパズルだと思ってください。解いているうちに直感が養われてゆくのは、一般の四則演算と同じです。式変形で行き詰まったら、真理値表で答えを確かめてから、どの法則を使えばよいかを考えるのも一つの方法です。

問題1: 真理値表を作る

論理関数 \(f(x,y,z)=(x+\bar y)\cdot z\) について答えよ。

(1) 3変数の真理値表は何行になるか。
(2) 途中の列 \(\bar y\)、\(x+\bar y\) も含めて真理値表を完成させよ。
(3) \(f=1\) となる入力 \((x,y,z)\) をすべて答えよ。

解答

(1) 各変数が0か1の2通りなので、\(2^3=8\) 行です。

(2) 次のとおりです。\((x,y,z)\) を 000, 001, …, 111 と2進数の順に並べると、書きもらしを防げます。

\(x\) \(y\) \(z\) \(\bar y\) \(x+\bar y\) \(f=(x+\bar y)\cdot z\)

0

0

0

1

1

0

0

0

1

1

1

1

0

1

0

0

0

0

0

1

1

0

0

0

1

0

0

1

1

0

1

0

1

1

1

1

1

1

0

0

1

0

1

1

1

0

1

1

(3) \((x,y,z)=(0,0,1),(1,0,1),(1,1,1)\) の3通りです。\(z=0\) の行は、論理積の相手が0なので、\(x+\bar y\) の値によらずすべて0になります。

問題2: ド・モルガンの法則と双対

(1) \(\overline{x\cdot\bar y + z}\) を、否定が変数1つずつにだけかかる形に変形せよ。
(2) 「雨が降っていて、かつ、風が強い」の否定を、「かつ」「または」を使って言い換えよ。
(3) 冗長律 \(x+\bar x\cdot y = x+y\) の双対の等式を書き、それが成り立つことを式変形で確かめよ。

解答

(1) \((\bar x + y)\cdot \bar z\)。外側から順にド・モルガンの法則を使います。

\[\begin{align} \overline{x\cdot\bar y + z} &= \overline{x\cdot\bar y}\cdot\bar z & \text{（ド・モルガン）}\\ &= (\bar x + \bar{\bar y})\cdot\bar z & \text{（ド・モルガン）}\\ &= (\bar x + y)\cdot\bar z & \text{（復元律）} \end{align}\]

否定を中に入れるたびに、\(+\) と \(\cdot\) が入れ替わる点に注意します。\(\bar x\cdot y\cdot\bar z\) のように演算を入れ替え忘れたり、\(\bar{\bar y}\) を \(\bar y\) のままにしたりするのがよくある誤りです。また、括弧 \((\bar x + y)\) を外すと意味が変わってしまいます。

(2) 「雨が降っていない、または、風が強くない」。両方がそろった状態だけを否定するので、どちらか一方が欠けていればよいのです。「雨が降っていなくて、かつ、風が強くない」は誤りです。

(3) 双対は \(x\cdot(\bar x + y) = x\cdot y\) です(左辺は \(x+(\bar x\cdot y)\) なので、入れ替えるときに括弧を補います)。確かめると

\[x\cdot(\bar x + y) = x\cdot\bar x + x\cdot y = 0 + x\cdot y = x\cdot y\]

となり、成り立ちます(分配律・相補律・単位元)。

問題3: 回路図から論理式へ

次の論理回路について問いに答えよ。

問題3の論理回路
図 19. 問題3の論理回路

(1) 出力 \(f\) を論理式で表せ。
(2) (1)の論理式を簡単化して、論理回路で示せ。

解答

(1) 入力側から順に、各ゲートの出力を式で書き込むと次のようになります。

各ゲートの出力を書き込んだ問題3の論理回路
図 20. 問題3の回路の各ゲートの出力

したがって \(f = x + (\bar x\cdot y + x\cdot\bar y)\) です。論理和は結合律が成り立つので、括弧を外して \(f = x + \bar x\cdot y + x\cdot\bar y\) と書いてかまいません。

(2) \(f = x+y\) です。

\[\begin{align} x + \bar x\cdot y + x\cdot\bar y &= x + x\cdot\bar y + \bar x\cdot y &\quad (交換律)\\ &= x + \bar x\cdot y &\quad (吸収律)\\ &= (x + \bar x)\cdot(x + y) &\quad (分配律)\\ &= 1\cdot(x + y) &\quad (相補律)\\ &= x + y &\quad (単位元) \end{align}\]

2行目は、吸収律 \(x+x\cdot\bar y=x\) を使っています。3行目以降は冗長律(例2)と同じです。よって、ORゲート1つの回路に簡単化できます。

ORゲート
図 21. 問題3を簡単化した回路

なお、途中に現れる \(\bar x\cdot y + x\cdot\bar y\) は、\(x\) と \(y\) が異なるときだけ1になる関数で、次の章で排他的論理和として扱います。

問題4: 論理式から回路図へ

論理式 \(f = x\cdot\bar y + \bar x\cdot z\) を、2入力のANDゲート・ORゲートとNOTゲートを使った論理回路で描け。また、\(x=1\) のときと \(x=0\) のときで、\(f\) はそれぞれどの入力で決まるか答えよ。

解答

式を計算する順(否定 → 論理積 → 論理和)にゲートを並べると、次のようになります。NOTゲート2個、ANDゲート2個、ORゲート1個です。\(x\) は2か所で使うので、黒丸で分岐させます。\(x\) から下へ延びる線と \(y\) の線は交差するだけで、つながっていません。

x・ȳ+x̄・zの論理回路
図 22. \(x\cdot\bar y + \bar x\cdot z\) の論理回路

\(x=1\) のとき \(\bar x=0\) なので、下のANDゲートの出力は0になり、\(f = 1\cdot\bar y + 0 = \bar y\) です。\(x=0\) のときは上のANDゲートの出力が0になり、\(f = z\) です。つまり、この回路は \(x\) の値によって、\(\bar y\) と \(z\) のどちらを出力するかを切り替えています。

ゲートの記号の向き(入力が左、出力が右)と、NOTゲートの出力側の小さな丸を忘れないようにしましょう。

問題5: 真理値表から積和標準形へ(多数決)

3人の投票 \(x, y, z\)(賛成なら1、反対なら0)を入力とし、2人以上が賛成したときだけ1を出力する論理関数 \(f(x,y,z)\) を考える。

(1) 真理値表を作れ。
(2) 積和標準形で表せ。
(3) 簡単化せよ。

解答

(1) 1の個数が2以上の行で \(f=1\) です。

\(x\) \(y\) \(z\) \(f\)

0

0

0

0

0

0

1

0

0

1

0

0

0

1

1

1

1

0

0

0

1

0

1

1

1

1

0

1

1

1

1

1

(2) \(f=1\) の4行から最小項を作ります。

\[f = \bar x y z + x\bar y z + x y\bar z + x y z\]

(3) \(f = xy + yz + zx\) です。\(xyz\) は他の3つの項のどれとも1文字違いなので、冪等律で \(xyz\) を3つに増やしてから、それぞれと組にします。

\[\begin{align} f &= \bar x y z + x\bar y z + x y\bar z + x y z + x y z + x y z & \text{（冪等律）}\\ &= (\bar x + x) y z + x (\bar y + y) z + x y (\bar z + z) & \text{（交換律・結合律・分配律）}\\ &= yz + xz + xy & \text{（相補律・単位元）} \end{align}\]

「2人以上が賛成」は「どれか2人が両方賛成」と言い換えられるので、2人ずつの組の論理積を論理和でつないだ形になる、と考えても同じ結果が得られます。この関数は、次の章で学ぶ全加算器の桁上がり(3つの1ビットの和で上の桁へ繰り上がるか)と同じ論理関数です。

問題6: 合意定理を示す

次の等式が成り立つこと(左辺と右辺が等しいこと)を示せ。真理値表を使えば簡単に示せますが、できるだけ式変形で示してみよう。

\[x\cdot y + \bar x\cdot z + y\cdot z = x\cdot y + \bar x\cdot z\]
解答

\(y\cdot z\) に \(1 = x+\bar x\) を掛けて2つに分け、吸収律で消します。

\[\begin{align} x\cdot y + \bar x\cdot z + y\cdot z &= x\cdot y + \bar x\cdot z + 1\cdot (y\cdot z) &\quad (単位元)\\ &= x\cdot y + \bar x\cdot z + (x+\bar x)\cdot (y\cdot z) &\quad (相補律)\\ &= x\cdot y + \bar x\cdot z + x\cdot y\cdot z+ \bar x\cdot y\cdot z &\quad (分配律・結合律)\\ &= \big(x\cdot y + (x\cdot y)\cdot z\big) + \big(\bar x\cdot z + (\bar x\cdot z)\cdot y\big) &\quad (交換律・結合律)\\ &= x\cdot y + \bar x\cdot z &\quad (吸収律) \end{align}\]

1行目から2行目の「\(1\) を \(x+\bar x\) に置き換える」変形はややテクニカルですが、消したい項を2つに分けて、それぞれを残す項に吸収させるという、よく使う方法です。

別解: 分配律を愚直に使う

ブール代数では、論理和についての分配律 \(x + yz = (x + y)(x + z)\) も成り立つので、積和形を和積形に「展開」できます。たとえば、同じように分配律と結合律・交換律を使うと

\[wx + yz = (w + y)(w + z)(x + y)(x + z)\]

が得られます。普段の計算で \((w+x)(y+z) = wy+wz+xy+xz\) と展開するのと、和と積の役割を入れ替えたものです。一般に、積項の論理和は「各積項から1文字ずつ選んで論理和をとったもの」をすべて論理積でつないだ形に展開できます。これを両辺に適用します。

左辺の3つの積項 \(xy\)、\(\bar xz\)、\(yz\) から1文字ずつ選ぶ8通りを並べると

\[\begin{align} \text{左辺} &= (x+\bar x+y)(x+\bar x+z)(x+z+y)(x+z+z)\\ &\quad\ \cdot(y+\bar x+y)(y+\bar x+z)(y+z+y)(y+z+z)\\ &= (x+y+z)(x+z)(\bar x+y)(\bar x+y+z)(y+z) & \text{（相補律・零元・冪等律など）}\\ &= (x+z)(\bar x+y)(y+z) & \text{（吸収律）} \end{align}\]

となります。最後の段階では、吸収律の右側 \(a\cdot(a+b)=a\) を \(a=y+z\) として使い、\((y+z)(x+y+z)\) と \((y+z)(\bar x+y+z)\) をどちらも \(y+z\) にしています。右辺も同様に展開すると

\[\text{右辺} = (x+\bar x)(x+z)(y+\bar x)(y+z) = (x+z)(\bar x+y)(y+z)\]

となり、両辺は等しくなります。

3変数なら真理値表による証明もそれほどの手間ではありません。次の表の7列目と8列目が、すべての行で等しくなっています。

表 10. 問題6の真理値表
\(x\) \(y\) \(z\) \(xy\) \(\bar xz\) \(yz\) \(xy + \bar xz + yz\) \(xy + \bar xz\)

0

0

0

0

0

0

0

0

0

0

1

0

1

0

1

1

0

1

0

0

0

0

0

0

0

1

1

0

1

1

1

1

1

0

0

0

0

0

0

0

1

0

1

0

0

0

0

0

1

1

0

1

0

0

1

1

1

1

1

1

0

1

1

1

表から、\(yz=1\) となる行(4行目と8行目)では、必ず \(xy\) か \(\bar xz\) のどちらかも1になっていることがわかります。これが、\(yz\) の項が不要になる理由です。

問題7: 等式を示す

次の等式が成り立つこと(左辺と右辺が等しいこと)を示せ。

\[\bar x\cdot\bar y\cdot z + y+ x\cdot z = y + z\]
解答

例2で導いた冗長律 \(a+\bar a\cdot b = a+b\) を補題として使うと、短く示せます。

\[\begin{align} \bar x\cdot \bar y\cdot z + y + x\cdot z &= \big(y+\bar y\cdot (\bar x\cdot z)\big) + x\cdot z & (交換律・結合律)\\ &= (y+ \bar x\cdot z) + x\cdot z & (冗長律)\\ &= y+ (\bar x\cdot z + x\cdot z) & (結合律)\\ &= y+ (\bar x + x)\cdot z & (分配律)\\ &= y+ 1\cdot z & (相補律)\\ &= y + z & (単位元) \end{align}\]

2行目では、冗長律の \(a\) を \(y\)、\(b\) を \(\bar x\cdot z\) としています。

別解として、論理和についての分配律 \(y + abc = (y+a)(y+b)(y+c)\) を使うこともできます。

\[\begin{align} \bar x\cdot \bar y\cdot z + y + x\cdot z &= (\bar x + y)(\bar y + y)(z + y) + x\cdot z & (分配律)\\ &= (\bar x + y)(z + y) + x\cdot z & (相補律・単位元)\\ &= \bar x\cdot z +\bar x\cdot y+ y\cdot z + y + x\cdot z & (分配律・冪等律)\\ &= (\bar x + x)\cdot z +(\bar x + z + 1)\cdot y & (交換律・分配律)\\ &= y + z & (相補律・零元・単位元) \end{align}\]
問題8: 論理関数の数と、AND・OR・NOTで作れる理由

(1) 3変数の論理関数 \(f: \{0,1\}^3 \rightarrow \{0,1\}\) は全部で何種類あるか。
(2) どんな論理関数でも、NOTゲートと2入力のANDゲート・ORゲートを組み合わせた論理回路で作れる。その理由を、積和標準形を使って説明せよ。

解答

(1) \(2^{2^3}=2^8=256\) 種類です。真理値表は \(2^3=8\) 行あり、各行の出力を0か1に決めるごとに別の関数になるので、\(2\times 2\times\cdots\times 2=2^8\) 通りです。「\(2^3=8\) 種類」は行数を答えてしまった誤りです。

(2) 論理関数が与えられれば、真理値表を作れます。\(f=1\) の行があれば、その行ごとに最小項(各変数か、その否定の論理積)を作り、それらを論理和でつなぐと、\(f\) と同じ関数を表す積和標準形が得られます(「論理式の標準形」の節の手順)。最小項に必要な否定はNOTゲートで、\(n\) 個のリテラルの論理積は2入力ANDゲートを \(n-1\) 個つなげば作れます。最小項どうしの論理和も、2入力ORゲートをつないで作れます。\(f=1\) の行が1つもない関数(常に0)は、\(x\cdot\bar x\) のように作れます。したがって、どんな論理関数も、この3種類のゲートで回路にできます。

ただし、この方法で作る回路は大きくなりがちです。同じ関数をより少ないゲートで作るための簡単化の方法を、次の章で学びます。

← 目次へ戻る

© 久保山哲二 「コンピューター科学概論」講義資料 — CC BY-NC-SA 4.0 (表示 - 非営利 - 継承)で公開しています。