このページをはてなブックマークに追加このページを含むはてなブックマーク このページを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};|
|A|fSUB{0};|fSUB{1};|fSUB{2};|fSUB{3};|h
|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};|
|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};|h
|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で構成される論理式で表現できる。次にいくつか重要な関数を示しておく。

|論理関数|名称|論理式|
|論理関数|名称|論理式|h
|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};|
|A|B|fSUB{14};|h
|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)

#divid(s,thorem)
[定理]シャノンの展開定理~
変数が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};
#divid(e,thorem)

 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)|
|A|B|f(A,B)|h
|0|0|1|
|0|1|1|
|1|0|0|
|1|1|1|

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

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

|A|B|f(A,B)|
|A|B|f(A,B)|h
|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|
|行がA、列がB|0|1|h
|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までの)行列式の計算のときにサラスの方法で計算してしまうだろう。これと同様な話である。

#divid(s,notice)
[例]

|BGCOLOR(#C0C0C0):CENTER:AB\CD|BGCOLOR(#C0C0C0):CENTER:00|BGCOLOR(#C0C0C0):CENTER:01|BGCOLOR(#C0C0C0):CENTER:11|BGCOLOR(#C0C0C0):CENTER:10|
|BGCOLOR(#C0C0C0):CENTER:00|BGCOLOR(#FF99CC):CENTER:1|CENTER:0|CENTER:0|BGCOLOR(#FF99CC):CENTER:1|
|BGCOLOR(#C0C0C0):CENTER:01|CENTER:0|BGCOLOR(#99CCFF):CENTER:1|BGCOLOR(#99CCFF):CENTER:1|CENTER:0|
|BGCOLOR(#C0C0C0):CENTER:11|CENTER:0|BGCOLOR(#99CCFF):CENTER:1|BGCOLOR(#99CCFF):CENTER:1|CENTER:0|
|BGCOLOR(#C0C0C0):CENTER:10|CENTER:0|CENTER:0|CENTER:0|CENTER:0|

-ピンク色の部分より、&mimetex("\bar{A}\cdot\bar{B}\cdot\bar{D}");
-青色の部分より、&mimetex("B \cdot D");

 よって、&mimetex("\bar{A}\cdot\bar{B}\cdot\bar{D} + B \cdot D"); ◇

#divid(e,notice)

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

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

(後でここにたくさんの練習問題を載せておく)
***7セグメントLEDと論理関数 [#n3719504]

 [[7セグメントLED]]は10進数1桁の表示回路である。入力ABCDの4ビット、出力a〜gの7つの[[LED]]である。例えばABCD=0000が入力されれば、0が表示される(a,b,c,d,e,fのLEDが光る)。またABCD=0101が入力されれば5が表示される(a,c,d,f,gのLEDが光る)。


#divid(s,notice)
[例]出力d(一番底辺のLED)を表示するための論理関数を考える。

 dの部分が光るのは、7セグメントLEDが0,2,3,5,6,8の6つの場合である。

-ABCD=0000⇒0
-ABCD=0010⇒2
-ABCD=0011⇒3
-ABCD=0101⇒5
-ABCD=0110⇒6
-ABCD=1000⇒8

 dの論理関数の主加法標準形は次のようになる。

&mimetex("d = \bar{A}\bar{B}\bar{C}\bar{D} + \bar{A}\bar{B}C\bar{D} + \bar{A}\bar{B}CD + \bar{A}B\bar{C}D + \bar{A}BC\bar{D} + A\bar{B}\bar{C}\bar{D}");

 次に、この論理関数をカルノー図を用いて簡略化する。

1:4変数カルノー図にdの6つの最小項のところを1と書き込む。

#img(http://security2600.sakura.ne.jp/main2/image1/7LED1.jpg)
#img(,clear)

2:すると孤立した1は、&mimetex("\bar{A}B\bar{C}D");の最小項だけである。

3:4つ組の1には含まれない2つ組の1の部分を楕円で書き込む(半楕円は向かい側と繋がる)。それらは&mimetex("\bar{B}\bar{C}\bar{D}");,&mimetex("\bar{A}\bar{B}\bar{D}");,&mimetex("\bar{A}\bar{B}C");,&mimetex("\bar{A}C\bar{D}");の4つある。

#img(http://security2600.sakura.ne.jp/main2/image1/7LED2.jpg)
#img(,clear)

4:以上で4つ組以上はなく、すべての1が楕円で囲まれた。主項は次の5つとなる。

-&mimetex("\bar{A}B\bar{C}D");
-&mimetex("\bar{B}\bar{C}\bar{D}");
-&mimetex("\bar{A}\bar{B}\bar{D}");
-&mimetex("\bar{A}\bar{B}C");
-&mimetex("\bar{A}C\bar{D}");

5:このうち、&mimetex("\bar{A}\bar{B}\bar{D}");以外は必須項となる(チェック印が付いている)。よて、必須項は次の4つとなる。

-&mimetex("\bar{A}B\bar{C}D");
-&mimetex("\bar{B}\bar{C}\bar{D}");
-&mimetex("\bar{A}\bar{B}C");
-&mimetex("\bar{A}C\bar{D}");

6:ゆえに簡略化された論理関数は次の通りである。

&mimetex("d = \bar{A}B\bar{C}D + \bar{B}\bar{C}\bar{D} + \bar{A}\bar{B}C + \bar{A}C\bar{D}"); ◇
#divid(e,notice)

**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)|
|A|B|C|f(A,B,C)|h
|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となる。


*論理関数の簡略化のアプローチ [#x951b479]

-論理関数の変形による簡略化
--論理関数に関する公理・定理を用いて論理式を変形し、より簡単な回路を導く方法。
-Veitch図やカルノー図などによる簡略化
--論理関数を図式化し、図形的に簡略化を行う方法。
--機械的に行えるので初心者向け。
--ただし入力の数が増えるにつれて図が大きく複雑になるので、5つ以上の入力を持つ回路には不向きである。
-クワイン-マクラスキー(Quine-McClukey)法による簡略化
--コンピュータを用いて、自動的に簡略化を行うのに適した方法。
--多数の入力を持つ回路でも簡略化が可能である。


*Quine-MeCluskey法 [#bff14f04]

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

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

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

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

 Quine-MeCluskey(クワイン・マクラスキー)法とは、ハミング距離を利用して論理関数を作成する手法である。
 ''Quine-MeCluskey(クワイン・マクラスキー)法''とは、ハミング距離を利用して論理関数を作成する手法である。

 ハミング距離は次のDSUB{H};で求める値(距離)である。
 [[ハミング距離]]は次のDSUB{H};で求める値(距離)である。

&mimetex("\normalsize\displaystyle D_H=\normalsize {\sum_{i=1}^na_i \oplus b_i}");

 まず、次の表から論理関数を作成する手順を示す。

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

 まず、&mimetex("\widebar{A} \widebar{B} \widebar{C}");からハミング距離の順に、真理値が1となっている項を上から並べる。並び終えると次のようになる。

#img(http://s-akademeia.sakura.ne.jp/main/image9/d1.jpg)
#img(,clear)

 なお、わかりやすいようにそれぞれの項に 銑イ糧峭罎鯢佞韻討い襦

 次に、変数をひとつ減らしたものを右側の列に追加する。そのときハミング距離が1である2つの項を探して、それらの論理和を求める。

 同様にして、変数がひとつになるまで繰り返す。

#img(http://s-akademeia.sakura.ne.jp/main/image9/d2.jpg)
#img(,clear)

 ここで、 銑イ里垢戮討魎泙爐茲Δ柄塙腓錣擦鮃佑┐襦いくつかのパターンが考えられるが、組み合わせる個数がもっとも少ない組合わせを選択するようにする。
 ´△&mimetex("\widebar{A} \widebar{C}");と↓きイBを組み合わせることで、 銑イ鬚垢戮憧泙燹よって、論理関数&mimetex("\widebar{A} \widebar{C} \wedge B");を得ることができる。

#img(http://s-akademeia.sakura.ne.jp/main/image9/d3.jpg)
#img(,clear)


*参考文献 [#k38cee3f]

-『工科系の論理数学入門』(カットシステム)
-『イラスト・図解 デジタル回路のしくみがわかる本』
-『情報処理技術者試験ポケットスタディ 応用情報技術者』
-『コンピュータの動くしくみ』