Top / 論理関数

論理関数

Tweet

目次 †

論理関数 †

　論理関数をf(A1,A2,A3,…,An)とするとき、各変数Aiのとる値（定義域）は0または1である。よって、関数がとる引数の数によって、存在しうる関数の送信が決定する。

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

・関数f0は、何を入力しても常に0を出力する。
・関数f1は、f1=Aである。
・関数f2は、f2=￣Aである。
・関数f3は、何を入力しても常に1を出力する。

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

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

シャノンの展開定理 †

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

f(A)=f(0)f2∨f(1)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つの引数のときを見ていこう。

　表からf14(A,B)のときを抜き出しておこう。

　これから次が成り立つ。

f14(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(A1,A2,A3,…,An)をn-1個のこ引数を持つf(0,A2,A3,…,An)￣A1∨f(1,A2,A3,…,An)A1という論理関数に変換している。

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

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

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

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

カルノー図 †

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

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

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

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

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

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

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

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

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

• ￣A￣B∨￣AB＝￣A
• ￣AB∨AB＝B

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

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

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

複雑なカルノー図 †

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

7セグメントLEDと論理関数 †

　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が光る）。

Don't Care †

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

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

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

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

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

論理関数の簡略化のアプローチ †

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

Quine-MeCluskey法 †

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

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

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

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

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

　ハミング距離は次のDHで求める値（距離）である。

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

　まず、からハミング距離の順に、真理値が1となっている項を上から並べる。並び終えると次のようになる。

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

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

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

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

参考文献 †

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