\[\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年)の中で、アリストテレスの論理学を拡張し、代数の体系として論理学を位置づけました。それは人間の知的思考は純粋な記号操作によって表現できるという現在の人工知能（特に第二次人工知能ブーム）に通じる考えに基づいていました。ブール代数は論理学の中でも古典命題論理と密接な関係にあり、古典命題論理のモデル（意味論）として用いられています。

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

George Boole ジョージ・ブールは、チャールズ・バベッジと同じくヴィクトリア朝時代の英国の人です。正規の教育を受けたのは16歳までで、それ以降は独学で当時の最先端の数学の素養を身につけ、数々の数学論文を発表します。経済的な問題もあり大学への進学は断念し、学位を持っていませんでしたが、その業績はすでに広く知られており、30代半ばでアイルランドで新設された大学の教授になります。

現在の人工知能を牽引する深層学習（ディープラーニング）の生みの親の一人で、深層学習界のゴッドファーザーと呼ばれているジェフリー・ヒントンは、ブールの玄孫（やしゃご: 孫の孫、つまり、ひ孫の子）です。また、ブールと交流のあった数学者ド・モルガンは、世界初のプログラマとして知られているエイダの家庭教師でした。

1.2. 論理演算子

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

この授業では、値として0と1だけを扱う2要素ブール代数を学びます。一般のブール代数には、集合の和・積・補集合を扱うものなどもあります。また、二項演算子として論理積（\(\cdot\)）と論理和（\(+\)）、単項演算子として否定(\(\bar{}\))を以下のように定義します。

論理積

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

論理積は普段我々が使っている算術演算の積と一致しています。

論理和

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

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

否定

単項演算子（\(\bar{}\)）を用いて否定を次のように定義します。

\[\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ゲート

sw and

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\) を用いることもあります。

gate and

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

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

0

0

0

0

1

0

1

0

0

1

1

1

ORゲート

sw or

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


gate or

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


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

0

0

0

0

1

1

1

0

1

1

1

1

NOTゲート

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

デジタル回路では、このスイッチの役割をはたす回路をNOTゲートとよび、右図の記号で表します。 gate 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\) のように外しても構いません。

分配律

右側の性質は、普段慣れ親しんでいる算術演算とは異なることに注意してください。

復元律

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

ド・モルガンの法則

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

吸収律の証明

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

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

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

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

\(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

上の表の基本法則は真理値表ですべて証明できます。

変数の数が増えるに従って、すべての変数への値の割当てを列挙する真理値表に基づく方法はだんだんと手に負えなくなります。なぜなら、変数が \(n\) 個あるとき、真理値表に必要な組合せの数は \(2^n\) になり変数の数に対して計算時間は指数的に増加するからです。変数が20個だと、その数は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}\]
双対原理

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

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

ことによって、もう一方の等式が得られます。ブール代数では、我々が慣れ親しんでいる算術演算と異なり、積と和に対称性があるため、この性質が成り立ちます。 基本法則の表にある左側の等式から、双対原理を用いて右側の等式を導出してみてください。たとえば吸収律の左側 \(x+ x\cdot y = x\) で、0と1、\(+\) と \(\cdot\) を入れ替えると、右側の \(x\cdot(x+y) = x\) がただちに得られます。同じ手順を分配律の左側 \(x\cdot (y+z) = x\cdot y + x\cdot 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. 論理式の簡単化

【例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\) は、論理ゲートで表現すると下図のようになります。

ex1 lc

論理回路では線が交差しているだけではつながっていることになりませんので注意してください。黒丸の部分がつながっている箇所です。 この論理回路は、結局 \(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\) は、論理ゲートで表現すると下図のようになります。

ex2 lc

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

gate or
【例3】

次の論理回路を簡単化せよ
ex3 lc

まず、\(x\) と \(y\) を左から右にたどって論理ゲートを式に変換して簡単化します。

\[\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つになります。

gate and

簡単化のコツ

例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項があれば不要になります。この等式の証明は、章末の「今週の問題の解答」の【2】で扱います。

実践的な解法手順

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

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

Step 2：相補律で簡単化

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

Step 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. \(abc + abcd + \bar{a}bcd + \bar{a}bc\)

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

解答：

  1. \(x + yz\) （冗長律）

  2. \(ab + \bar{a}c + bc = ab + \bar{a}c\) （合意定理）

  3. 計算を進めると

    \[\begin{align} &x(y + z) + \bar{x}(y + z) + yz\\ &= (y + z)(x + \bar{x}) + yz\\ &= (y + z) \cdot 1 + yz\\ &= y + z + yz\\ &= y + z \quad \text{（吸収律）} \end{align}\]

  4. 計算を進めると

    \[ \begin{align} &abc + abcd + \bar{a}bcd + \bar{a}bc\\ &= abc(1 + d) + \bar{a}bc(d + 1)\\ &= abc + \bar{a}bc\\ &= bc(a + \bar{a})\\ &= bc \end{align}\]

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

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

    つまり、この論理式は入力によらず常に \(1\) となります（恒真）。

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

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\)

\(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つのみです。 一般に \(n\) 変数の論理関数は \(2^{2^n}\) 個存在します。

簡単化の例題でも見てきたように1つの論理関数にはいろいろな論理式の表現があります。2つの論理式の論理関数としての等価性を示す問題は、非常に難しい問題であることが知られています。等価性までは示せなくても、まずは、論理式の形式をできるだけ標準化しておくと便利です。そこで、論理式の標準形を定義するための準備をします。

以降では論理積の演算子「\(\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個

例)

吸収律の真理値表を例に用いることにします。
\(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\) を含んでいるので、いずれも最小項であり、その積和形なので積和標準形になっています。

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

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

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

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

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

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

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

0

0

1

0

1

1

1

0

0

1

1

1

解答：

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

\[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\\ &= \bar x + x\cdot y & \text{（相補律・単位元）}\\ &= \bar x + y & \text{（冗長律）} \end{align}\]

となります。この真理値表は \((x,y)=(1,0)\) でのみ0となるので、後で学ぶ実質含意 \(x\rightarrow y\) と一致しており、その等価式 \(\bar x + y\) が得られたことになります。

和積標準形

同様に真理値表から和積標準形にしてから、論理式を導出することも可能です。

上記の真理値表の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)\]

この論理関数の各項は \(x\) と \(y\) を含んでいるので、いずれも最大項であり、その和積形なので和積標準形になっています。

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

同じ真理値表で、\(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)=(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}\]

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)といい、数学で「ならば」とあれば、この実質含意の意味です（日常的に使う「ならば」からは若干違和感のある定義かもしれません）。

\(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】〜【3】に取り組んでください。

【1】次の論理回路について問いに答えよ

ex4 lc

(1) 論理式で表わせ
(2) (1)の論理式を簡単化して論理回路で示せ

次の問【2】と【3】は真理値表を使えば簡単に解けますが、できるだけ式変形で解くことに挑戦してみてください（できなければ真理値表を用いてもかまいません）。

【2】次の等式を示せ（左辺と右辺が等しいことを示せ）

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

【3】次の等式を示せ（左辺と右辺が等しいことを示せ）

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

3. 今週の問題の解答

まず自分で解いてから読むことをすすめます。

ブール代数の証明問題は、与えられた規則をもとに式を変形してゆくパズルだと思ってください。解いているうちに直感が養われてゆくのは、一般の四則演算と同じです。

【1】次の論理回路について問いに答えよ

ex4 lc

(1) 論理式で表わせ
(2) (1)の論理式を簡単化して論理回路で示せ

\[\begin{align} x + \bar x\cdot y + x\cdot\bar y &= x + x\cdot\bar y + \bar x\cdot y &\quad (交換律)\\ &= (x\cdot 1 + x\cdot\bar y) + \bar x\cdot y &\quad (結合律・単位元)\\ &= x\cdot(1 + \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}\]

よって、以下の論理回路に簡単化できる。

gate or

【2】次の等式を示せ（左辺と右辺が等しいことを示せ）

\[x\cdot y + \bar x\cdot z + y\cdot z = x\cdot y + \bar x\cdot z\]
\[\begin{align} x\cdot y + z\cdot\bar x + y\cdot z &= x\cdot y + \bar x\cdot z + y\cdot z &\quad (交換律)\\ &= 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 (分配律)\\ &= (x\cdot y + (x\cdot y)\cdot z) + (\bar x\cdot z + (\bar x\cdot z)\cdot y) &\quad ((結合律)・交換律)\\ &= x\cdot y + \bar x\cdot z &\quad (吸収律)\\ \end{align}\]

この証明は、2行3行目の「単位元」と「相補律」の適用がややテクニカルです。このような証明に拠らなくても、単純に分配律を適用してゆけば証明できます。以下の分配律に慣れてください。

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

証明は省きますが、分配律(と結合律と交換律)から以下の系も簡単に証明できます。

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

このような式展開は、四則演算で和と積が逆の場合は我々は自然と行っていることです。 四則演算と同様に以下の式変形はブール代数でも成り立ちます。

\[(w+x)(y+z) = wy+wz+xy+xz\]

ブール代数では和と積が対称であることに再度留意をしてください。 この分配律の一般形をただ愚直に適用してゆくことで、テクニカルな式変形をしなくても【2】は証明できます。

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

よって、両辺は等しい。

3変数なら真理値表による証明でもそれほどの手間ではありません。

表 5. 真理値表による証明
\(x\) \(y\) \(z\) \(xy\) \(yz\) \(z\bar x\) \(x\cdot y + y\cdot z + z\cdot\bar x\) \(x\cdot y + \bar x\cdot z\)

0

0

0

0

0

0

0

0

0

0

1

0

0

1

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

1

0

1

1

【3】次の等式を示せ（左辺と右辺が等しいことを示せ）

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

以下のように分配律を用いて証明できます。

\[\begin{align} \bar x\cdot \bar y\cdot z + y + z\cdot x &= (\bar x + y)(\bar y + y)(z + y) + z\cdot x & (分配律)\\ &= (\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}\]

その他、以下のような証明も可能です。例2で導いた冗長律 \(x+\bar x\cdot y = x+y\) を補題として用います。

\[\begin{align} \bar x\cdot \bar y\cdot z + y + z\cdot x &= \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+ \big((\bar x + x)\cdot z\big) & (分配律)\\ &= y+ 1\cdot z & (相補律)\\ &= y + z & (単位元)\\ \end{align}\]

以上です

← 目次へ戻る

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