このページをはてなブックマークに追加このページを含むはてなブックマーク このページを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};という論理関数に変換している。

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


*参考文献 [#k38cee3f]

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