このページをはてなブックマークに追加このページを含むはてなブックマーク このページをlivedoor クリップに追加このページを含むlivedoor クリップ
*目次 [#hd34edc1]

#contents


*論理関数 [#ie21af28]

 論理関数をf(ASUB{1};,ASUB{2};,ASUB{3};,…,ASUB{n};)とするとき、各変数ASUB{i};のとる値(定義域)は0または1である。よって、関数がとる引数の数によって、存在しうる関数の送信が決定する。

 例えば、n=1のときは、引数はひとつなので論理関数はf(A)の形で表される。f(A)の定義域はもちろん0と1の2通りである。それぞれのAの値の組み合わせに対して、f(A)の値域として0または1をとる。ということは、Aが2通り、f(A)が2通りで4つのパターン、即ち4つの関数fを考えることができる。

|A|fSUB{0};|fSUB{1};|fSUB{2};|fSUB{3};|
|0|0|0|1|1|
|1|0|1|0|1|

・関数fSUB{0};は、何を入力しても常に0を出力する。~
・関数fSUB{1};は、fSUB{1};=Aである。~
・関数fSUB{2};は、fSUB{2};= ̄Aである。~
・関数fSUB{3};は、何を入力しても常に1を出力する。

 同様に2変数の場合のときの論理関数も考えることができる。この場合は、f(A,B)となり、AとBがそれぞれ0または1となり、その組み合わせは4通りある。その4通りの組み合わせそれぞれについて、0または1の出力が考えられる。よって、論理関数の総数は16になる。

|A|B|fSUB{0};|fSUB{1};|fSUB{2};|fSUB{3};|fSUB{4};|fSUB{5};|fSUB{6};|fSUB{7};|fSUB{8};|fSUB{9};|fSUB{10};|fSUB{11};|fSUB{12};|fSUB{13};|fSUB{14};|fSUB{15};|
|0|0|0|0|0|0|0|0|0|0|1|1|1|1|1|1|1|1|
|0|1|0|0|0|0|1|1|1|1|0|0|0|0|1|1|1|1|
|1|0|0|0|1|1|0|0|1|1|0|0|1|1|0|0|1|1|
|1|1|0|1|0|1|0|1|0|1|0|1|0|1|0|1|0|1|

 これら16種類の論理関数fはAとBで構成される論理式で表現できる。次にいくつか重要な関数を示しておく。

|論理関数|名称|論理式|
|fSUB{0};|恒偽命題(恒偽論理)|0|
|fSUB{1};|論理積(AND)|AB|
|fSUB{3};|A|A|
|fSUB{5};|B|B|
|fSUB{6};|排他的論理和(XOR)| ̄AB∨A ̄B|
|fSUB{7};|論理和(OR)|A∨B|
|fSUB{8};|論理和の否定| ̄(A∨B)|
|fSUB{13};|条件節|A⇒B|
|fSUB{14};|論理積の否定| ̄(AB)|
|fSUB{15};|恒真命題(恒真論理)|1|


*シャノンの展開定理 [#bb256918]

 n=1、即ち引数をひとつとしたときの表を再び見てもらいたい。よく見ると気が付くかもしれないが、次が成り立つ。

f(A)=f(0)fSUB{2};∨f(1)SUB{3};
f(A)=f(0) ̄A∨f(1)A

 この式に0を代入すると次のように計算できる。

f(0)
=f(0) ̄0∨f(1)0
=f(0)1
=f(0)

 一方、この式に1を代入すると次のように計算できる。

f(1)
=f(0) ̄1∨f(1)1
=f(0)0∨f(1)1
=f(1)

 よって、論理関数f(A)=f(0) ̄A∨f(1)AはAの値を0,1どちらであってもそれぞれの真理値を取る。

 ゆえに、「∀A;f(A)=f(0) ̄A∨f(1)A」が成り立つということになる。

 また、今度は2つの引数のときを見ていこう。

 表からfSUB{14};(A,B)のときを抜き出しておこう。

|A|B|fSUB{14};|
|0|0|1|
|0|1|1|
|1|0|1|
|1|1|0|

 これから次が成り立つ。

fSUB{14};(A,B)~
=f(0,0) ̄A ̄B∨f(0,1) ̄AB∨f(1,0)A ̄B∨f(1,1)AB~
=1 ̄A ̄B∨1 ̄AB∨1A ̄B∨0AB (∵表から)~
= ̄A ̄B∨ ̄AB∨A ̄B~
= ̄A ̄B∨ ̄A ̄B∨ ̄AB∨A ̄B (∵ ̄A ̄Bを∨演算で追加した。結果はかわらないからOK)~
= ̄A ̄B∨ ̄AB∨ ̄A ̄B∨A ̄B (∵並べ替え)~
= ̄A( ̄B∨B)∨ ̄B( ̄A∨A)~
= ̄A∨ ̄B (∵トートロジーの性質)~
= ̄(A∧B)

[定理]シャノンの展開定理~
変数がn個の∀の関数について次が成り立つ。~
f(ASUB{1};,ASUB{2};,ASUB{3};,…,ASUB{n};)=f(0,ASUB{2};,ASUB{3};,…,ASUB{n};) ̄ASUB{1};∨f(1,ASUB{2};,ASUB{3};,…,ASUB{n};)ASUB{1};

 n個の引数を持つf(ASUB{1};,ASUB{2};,ASUB{3};,…,ASUB{n};)をn-1個のこ引数を持つf(0,ASUB{2};,ASUB{3};,…,ASUB{n};) ̄ASUB{1};∨f(1,ASUB{2};,ASUB{3};,…,ASUB{n};)ASUB{1};という論理関数に変換している。

 つまり、論理関数の引数をひとつ減らしているわけだ。このようにして、引数の数をひとつずつ減らしていくと、最終的には論理関数を真理値だけで表現できる。このようにして最終的に表されるものを''加法標準形''という。

 加法標準系の特徴として次が挙げられる。

-真理値表の中で1となっている個所に対応する項が含まれる。
-それぞれの項は、引数に対して項を1にするような論理式になっている。

 よって、シャノンの展開定理で得られた論理関数に真理値を代入するのではなく、真理値表の中で1の個所に着目するだけで論理関数を作れるわけだ。


*カルノー図 [#g30e5443]

 次のようなf(A,B)の真理値表があったとする。

|A|B|f(A,B)|
|0|0|1|
|0|1|1|
|1|0|0|
|1|1|1|

 この表からf(A,B)の論理関数が知りたいとする。シャノンの展開定理を使って求めてもよいわけだが、式変形でちょっとテクニカルな操作が必要である(計算結果は ̄A∨B)。

 そこで、次のように表を書き換える。単に3行目と4行目の位置を交換しただけである。

|A|B|f(A,B)|
|0|0|1|
|0|1|1|
|1|1|1|
|1|0|0|

[考察1]なぜこのような操作をしたのかというと、ハミング距離が1になっている項を探しやすくするためである。

[考察2]1行目と2行目、2行目と3行目、3行目と4行目、4行目と1行目はそれぞれハミング距離が1になっている。

 このようにして、変形できそうな項が隣接するように行を並べ、その真理値表の中での位置関係を見るだけで項を導出できるかどうかを判断できるようになる。このように並べた真理値表を''カルノー図''という。

 一般にカルノー図は次のように縦横の図で表現される。先ほどの表を書き換えると次のようになる。

|行がA、列がB|0|1|
|0|1|1|
|1|0|1|

 1のところに丸印をつけてみましょう。4つの部分のうち3つ( ̄A ̄B、 ̄AB、AB)が1になっているが、この3つの項から計算を始めてしまうと式変形が難しくなってしまう。

 カルノー図をよくみると、隣接する項同士で次のような変形ができることがわかるはずだ。

- ̄A ̄B∨ ̄AB= ̄A
- ̄AB∨AB=B

 この2つの変形の部分を楕円でくくってみる。そうすると、真理値表による論理関数は、その2つの楕円の共通部分になる。よって、 ̄A∨Bと簡単にわかる。

 ここまで順序よく読んできた方はシャノンの展開定理をきちんと理解した上で、計算時にはこのカルノー図ですばやく計算できる術を身に付けたわけだ。最悪、計算だけが目的なら、このカルノー図の解釈の仕方だけ理解できれば試験とかでは十分なんとかなるだろう。

 例えば、線形代数での(3×3までの)行列式の計算のときにサラスの方法で計算してしまうだろう。これと同様な話である。


**複雑なカルノー図 [#o83daa61]

 カルノー図で論理関数を求める方法は、4変数程度であれば簡単に行える。実際にたくさんの問題を解いて慣れるのが一番だろう。

(後でここにたくさんの練習問題を載せておく)


**Don't Care [#e6675dd7]
 電子回路の世界にはDon't Careという概念がある。例えば3つのスイッチを持つ何らかのデジタル回路があったとして、これらのスイッチを3つ同時にONにされることがない場合、その出力について考える必要がない。つまり、3つ同時にONにするようなときの出力は0でも1でも構わないわけである。このような出力を''Don't care(禁止、冗長)''と呼ぶ。Don't Careは、真理値表で「φ」として記述する。

 カルノー図を楕円で囲むときに、このDon't Care部分は囲んでもよいし囲まなくてもよいわけだ。カルノー図の楕円を作成するときの自由度が高まるわけで、効率のよい楕円を描くことができる。

 次にDon't Careを含む真理値表の一例を挙げる。

|A|B|C|f(A,B,C)|
|0|0|0|0|
|0|0|1|1|
|0|1|0|0|
|0|1|1|φ|
|1|0|0|0|
|1|0|1|1|
|1|1|0|1|
|1|1|1|φ|

 これをカルノー図に変換すると次のようになる。

#ref(karuno1.jpg,center)

 よって、この論理関数は、f(A,B,C)=AB∨Cとなる。


*Quine-MeCluskey法 [#bff14f04]

 カルノー図は確かに便利だが、万能ではない。カルノー図で簡単に論理関数を求めることができるのは4変数までで、工夫しても5変数が限界である。実際にはそれ以上の変数を持っていても原理的にカルノー図で考えることができるが、楕円で囲むときの見落としや間違いが多くなってしまうのである。それではカルノー図を持ち出した意味がない。

 そこで、5変数以上の論理関数の作成として新しい方法を考える必要がある。

 カルノー図で隣接する1が出現する個所を楕円で囲んでいた。この操作は、式の簡略化(例えば、A∨ ̄A=1など)に相当するわけだ。

 言い換えると、隣接する個所を効率よく、しかも漏れなく見つけることができれば、カルノー図を使わなくてもよいわけだ。





*参考文献 [#k38cee3f]

-『工科系の論理数学入門』(カットシステム)