論理和標準形(disjunctive normal form, DNF)

論理和標準形の定義

あらゆる論理式は論理和標準形と呼ばれる形で表すことができます。 (論理積標準形というものもありますが、この授業ではやりません。)

高校では、直線の方程式の標準形とか、平面の方程式の標準形を習ったと 思います。式を標準形に必ず直せることがわかっていると、色々と便利だというのは知っているでしょう。 論理式の論理和標準形というのも、そのようなものの一種だと思えばよいでしょう。

以下では、「論理式 B が XXXXXXX の形をしている」というのを

B ≡ XXXXXXX

と書くことにします。

論理式 A が論理和標準形であるというのは、A が次のような形をしている ことを言います:

A ≡ B1 ∨ B2 ∨ … ∨ Bn (n ≧ 0) ……(a)

ここで、各 Bi は

Bi ≡ C1 ∧ C2 ∧ … ∧ Cm (m ≧ 0, m は i ごとに違ってよい。) ……(b)

の形で、各 Cj は

Cj ≡ v または Cj ≡ ¬v (v は変数)

の形。 ただし、上の(a)で n = 0 の時は、

A ≡ F

を意味するものとし、(b) で m = 0 の時は

Bi ≡ T

を意味するものとします。

(注) n ≧ 1 の時は A ≡ B1 ∨ B2 ∨ … ∨ Bn = F ∨ B1 ∨ B2 ∨ … ∨ Bn なので、n = 0 の時は A ≡ F と決めておくのが自然です。 同じように、m ≧ 1 の時は Bi ≡ C1 ∧ C2 ∧ … ∧ Cm = T ∧ C1 ∧ C2 ∧ … ∧ Cm なので、m = 0 の時は Bi ≡ T と決めておくのが自然です。

     n
    Σ ai は、n が0の時は 0とする、という数学の約束と同じようなものです。
    i=1
    あるいは、m が 0 の時は m! = 1 という約束と同じようなものです。

論理和標準形の例

• (例1) x XOR y は (x ∨ y)∧¬(x∧y) と表せましたが、これは論理和標 準形ではありません。(∨より外側に∧があるし、変数以外のものに¬が ついています。) しかし、(x∧¬y) ∨ (¬x∧y) と表せば、これは論理和標準形です。
• (例2) もっと単純な x ∨ (¬x∧y) とか x ∨ y も論理和標準形です。
• (例3) x∧¬y には論理和の記号が1つもありませんが、それでも論理和標準形です。
• (例4) x のように変数1コだけでも論理和標準形です。
• (例5) ¬¬x は¬が二重についているので論理和標準形ではありません。 しかし、この二重否定を除去すれば、論理和標準形 x になります。
• (例6) ¬(x ∧ y) は ∧ の外側に ¬ があるので論理和標準形ではありません。
• (例7) T だけでも論理和標準形です。F だけでもそうです。

どういう時にダメかを考えたほうがわかりやすいかも知れません。

• ∨, ∧, ¬以外の論理記号があってはいけません(T と F は使っても OK)。
• ∨の外側に∧や¬があってはいけません。
• ∧の外側に¬があってはいけません。(∨はあってもよい。)
• ¬が二重になっていてはいけません。

※論理式 A に対して、論理和標準形であるような B で A = B であるもの を「A の論理和標準形」と言います。 例えば、 x XOR y = ¬((x→y)∧(y→x)) = (x∧¬y) ∨ (¬x∧y) であって、(x∧¬y) ∨ (¬x∧y) は論理和標準形ですから、 (x∧¬y) ∨ (¬x∧y) は ¬((x→y)∧(y→x)) の論理和標準形です。

(注) A の論理和標準形は一般に1通りではありません。

与えられた論理式を変形して、その論理和標準形を求める

1. A の中に B → C のような形をしている部分があったら、それを全部 ¬B ∨ C の形に書き換えます。これで、式の中の論理演算記号は ¬, ∧, ∨ だけになります。
2. 次の (i)〜(vi) を可能な限りくり返します:
   1. ¬T を F に書き換える。
   2. ¬F を T に書き換える。
   3. T ∧ B あるいは B ∧ T の形があったら、B に書き換える。
   4. F ∧ B あるいは B ∧ F の形があったら、F に書き換える。
   5. T ∨ B あるいは B ∨ T の形があったら、T に書き換える。
   6. F ∨ B あるいは B ∨ F の形があったら、B に書き換える。
   これで、T と F は単独で現れる以外には現れなくなります。
3. 次のような書き換えをできる限りくり返します:
   1. 二重否定の除去を使って ¬¬ B を、B に書き換える。
   2. ド・モルガンの法則を使って ¬(B ∧ C) を ¬B ∨ ¬C に書 き換える。
   3. ド・モルガンの法則を使って ¬(B ∨ C) を ¬B ∧ ¬C に書 き換える。
   これら(i)〜(iii)のくり返しにより、¬はどんどん式の内側に入って行 き(あるいは消滅し)、ついには、変数の直前にしか ¬ がつかなくなり ます。
4. B ∧ (C ∨ D) (あるいは (C ∨ D) ∧ B) の形があったら、 分配律を使って (B∧C) ∨ (B∧D) の形に書き換えることを可能な限りくり返す。 これで、∨ の外側に ∧ が出てくることはなくなります。

これで論理和標準形になるはずです。

式変形により論理和標準形を求める例

¬(x → y∧z) の論理和標準形を求めてみましょう。

この最後の式はちゃんと論理和標準形になっています。

真理値表から論理和標準形を作る

例で説明します。 次のような真理値表で与えられる演算を考えます。

          x  y  z   f(x,y,z)
        ---------------------
          F  F  F      F
          F  F  T      F
          F  T  F      T   ← (a)
          F  T  T      F
          T  F  F      T   ← (b)
          T  F  T      F
          T  T  F      T   ← (c)
          T  T  T      F

T が書かれている段に着目します。 まず、(a)に着目します。x が偽で、y が真で、z が偽の時、f(x,y,z) は真です。 つまり、

(i) ¬x ∧ y ∧ ¬z が真の時に f(x,y,z) は真です。

つぎに(b) に着目します。

(ii) x ∧ ¬y ∧ ¬z が真の時に f(x,y,z) は真です。

最後に (c) に着目します。

(iii) x ∧ y ∧ ¬z が真の時に f(x,y,z) は真です。

以上の(i)〜(iii) の場合以外には、f(x,y,z) が真になることはありません。 また、(i)〜(iii)の3つの場合のうちの2つ以上が同時に起こることはありませ ん。(排他的)

従って、f(x,y,z) = (¬x ∧ y ∧ ¬z) ∨ (x ∧ ¬y ∧ ¬z) ∨ (x ∧ y ∧ ¬z)

これは、論理和標準形になっています。

以上で、論理和標準形を求める2つのやり方を説明しましたが、両方とも覚え て下さい。

式の簡単化

さっきの f(x,y,z) = (¬x ∧ y ∧ ¬z) ∨ (x ∧ ¬y ∧ ¬z) ∨ (x ∧ y ∧ ¬z) は、標準形にはなっているが、必ずしも簡単とは言えません。 (x ∧ ¬y ∧ ¬z) ∨ (x ∧ y ∧ ¬z) の部分は簡単にできます。

        (x ∧ ¬y ∧ ¬z) ∨ (x ∧ y ∧ ¬z) 
        = (x ∧ ¬z ∧ ¬y ) ∨ (x ∧ ¬z ∧ y) 
        = (x ∧ ¬z) ∧ (¬y ∨ y)     (共通部分でくくる)
        = (x ∧ ¬z) ∧ T
        = x ∧ ¬z

結局、全体の式は f(x,y,z) = (¬x ∧ y ∧ ¬z) ∨ (x ∧ ¬z) になります。これは再び論理和標準形になっていて、元の式よりも簡単です。 なお、これも ¬z でくくることができて、次のようになります:

f(x,y,z) = (¬x ∧ y ∨ x) ∧ ¬z

この式は論理和標準形ではないので注意しましょう。しかし、これをさらに変 形すると:

        f(x,y,z) = (¬x ∧ y ∨ x) ∧ ¬z
                 = (¬x ∨ x)∧ (y ∨ x) ∧ ¬z  (分配律)
                 = T ∧ (y ∨ x) ∧ ¬z  (相補律)
                 = (y ∨ x) ∧ ¬z

となってもっと簡単になり、分配律を使って展開すると、

                 = y ∧ ¬z ∨ x ∧ ¬z

のように最も簡単な論理和標準形になります。

真理値表から作った論理和標準形は大抵長い式になりますが、上のようにして簡単 化ができる場合も多いです。

注) この授業の試験で「論理和標準形を求めなさい」と言われた場合、簡単化をする必要はありません。

上で使った論理式の簡単化の一方法をまとめておくと、

(A ∧ B) ∨ (A ∧ ¬B) のような形の論理式があったら、A に簡単化できる

ということになります。

  証明: (A ∧ B) ∨ (A ∧ ¬B) = A ∧ (B ∨ ¬B) (分配律)
                               = A ∧ T          (相補律)
                               = A

ブール代数

ここまでで、T と F からなる集合 {T, F} の上に与えられた色々な演算(¬, ∧,∨など)について学んできました。

一般に、ある集合の上にいくつかの演算が与えられているものを「代数」とい います。我々が考えてきた {T, F} とその上の演算の集まりも代数の一種で、 ブール代数と呼ばれます。厳密に言うと、ど ういう集合の上にどういう演算が定められていて、それらの演算に関してどのよ うな公理が成り立つときブール代数と呼ぶのかをきっちり定義しなければいけま せん。その詳細については省略しますが、公理についてだけ少し言っておくと、 ブール代数の公理というのは、x ∧ y = y ∧ x とか x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z) とかx ∨ ¬x = T のような法則だと思って下さい。そういうも のがいくつか与えられていて、それらが成り立っていればブール代数と言うのだ と思えばいいでしょう。

ブール代数以外に大学で習う代数と言うと、例えば線型代数(ベクトル空間) があります。

バッファ、ゲート

バッファ(Buffer)回路

入力をただそのまま出力に出すだけの回路も時に必要となります。 (ただ入力を電線で出力につないでいるだけではなく。トランジスタなどを 使って、信号を整えるなどの働きをしています。) これをバッファ回路といいます。(論理回路に対して簡単化などの変形をし ている時に回路の一部分にバッファ回路ができることもあります。)

      入力    出力
    ----------------
       L       L
       H       H

論理素子、論理ゲート

バッファ回路やAND回路のような基本的な回路も、中身を見れば、トランジス タなどの部品の組合せによってできています。しかし、これらの回路はあまり にも基本的であるため、中身の詳細は忘れて、あたかもこれらの回路自体が電 気的な素子であるかのように考えて、それらを組合せてもっと大きな回路を設 計します。そこで、上のような基本的な論理回路は、しばしば「論理素子」と 呼ばれます。あるいは、論理ゲートという言い方をすることもよくあります。

ゲート(Gate)というのは、もちろん「門」のことですが、実際これら回路を 「ゲート」のように考えて、電気信号がゲートを通ろうとする時に通過を止 められたり、加工をされたりするという見方をすると、回路を理解しやすく なることが多いのです。

例えば、ある AND ゲートの入力を x と y としましょう。 論理式 x ∧ y において、x を H (つまり T) にしてみると、 H ∧ y = y となるので、y がそのまま出力に出ます。 ところが、x を L に固定してみると、 L ∧ y = L となるので、信号 y を どんなに変化させてやっても、その変化は出力に伝わらず、出力はずっと L のままです。

このことに対して次のような見方ができます:

• x はこの門(ゲート)をコントロールするための端子(制御入力)である。
• x を H にすると、y はゲートを通れるようになる。
• x を L にすると、y はゲートを通れなくなり、ゲートの出力は L に固定 される。

このように見てやると、論理素子がゲートと呼ばれる理由がわかってくるで しょう。

もう一つの例として、XOR ゲートをとります。入力を x, y としましょう。

ですから、次のような見方ができます。

• x は制御入力。
• x を L に固定してやると、y がそのまま出力に出て行く。
• x を H に固定してやると、y の真・偽(H・L)が反転したものが出力に出る。

つまり、x を変えることで、真偽の反転・非反転の機能を切り換えられると 見ることができます。

x が L の時は、y についてのバッファ回路になり、x が H の時は y につ いての NOT 回路になるといってもよいでしょう。そう考えると、入力 x を 変えることで、バッファ回路と NOT 回路を切り換えられると見ることもで きます。