論理回路 3. 論理代数と論理関数

2015 年 4 月 17 日
小野寺秀俊
論理回路
3. 論理代数と論理関数
3.1 論理代数
論理変数 (logic variable)、2 値変数 (binary variable)
0 または 1 のいずれかの値をとる変数。
(n 変数) 論理関数 (logic function, Boolean function)
n 個の論理変数から論理変数への関数。{0, 1}n から {0, 1} への写像 (mapping)。
論理関数の表現法真理値表、論理式、カルノー図 (Karnaugh Map)、BDD(Binary Decision Diagram) など。
真理値表
論理変数の全ての組み合わせに対する論理関数の値を表にしたもの。
論理代数 (logic algebra) 集合 1, 0 上の代数系で、三つの論理演算 (logic operation) OR
演算, AND 演算, NOT 演算を持つ。ブール代数 (Boolean algebra) の最も簡単なモ
デル。
演算種
OR 演算
AND 演算
NOT 演算
x y
0 0
0 1
1 0
1 1
x+y
0
1
1
1
他の呼び方
論理和 (logical sum)
論理積 (logical product)
論理否定 (logical inverse) 反転 (complement)
x y
0 0
0 1
1 0
1 1
x·y
0
0
0
1
論理演算の優先度 NOT > AND > OR
x x
0 1
1 0
表記法
x + y, x ∪ y, x ∨ y
x · y, x ∩ y, x ∧ y
x, ¬x, x0
3.2 論理代数の持つ性質
べき等律
交換律
結合律
零元/単位元
単位元/零元
分配律
相補律
吸収律
復元律
ド・モルガンの定理
x+x=x
x+y =y+x
x + (y + z) = (x + y) + z
x+0=x
x+1=1
x · (y + z) = x · y + x · z
x+x=1
x+x·y =x
x=x
x+y =x·y
x·x=x
x·y =y·x
x · (y · z) = (x · y) · z
x·1=x
x·0=0
x + y · z = (x + y) · (x + z)
x·x=0
x · (x + y) = x
x·y =x+y
双対性 (duality) 双対原理 (principle of duality)
1 と 0, + と · を置き換えても上記の公理 (定理) が成立する。すなわち、論理代数に
おいて、等式の中の 1 と 0, + と · を入れ換えて得られる等式も成立する。
上記公理 (定理) の証明
真理値表、ベン図 (Venn diagram)、カルノー図を用いて証明することができる。
コンセンサス (consensus)
x·y+y·z+z·x=x·y+z·x
(x + y) · (y + z) · (z + x) = (x + y) · (z + x)
3.3 論理式
論理式 (logical expression) 論理変数と定数 (0, 1) に OR 演算、AND 演算、NOT 演算
を有限回施して得られる式。
リテラル (literal) 論理式に現れる論理変数およびその否定。
積項 (product term) 各変数のリテラルを高々一つしか含まない論理積。
積和形論理式 (sum-of-products expression) 積項の論理和からなる論理式。
和項 (sum term) 各変数のリテラルを高々一つしか含まない論理和。
和積形論理式 (product-of-sums expression) 和項の論理積からなる論理式。
ド・モルガン (De Morgan) の定理の一般形ある論理式の否定は、その論理式中のすべ
ての変数及び定数をその否定で置き換え、更に + と · を入れ換えて得られる論理式
に等しい。
f (x1 , x2 , · · · , xn , 0, 1, +, ·) = f (x1 , x2 , · · · , xn , 1, 0, ·, +)
3.4 論理関数の表現
真理値表 (truth table) 全ての入力に対する論理関数の値を列挙したもの。
n 入力論理関数の真理値表の行数は 2n
オンセット表現
オンセット (on set): 論理関数 f の値を 1 にする入力の集合
オフセット (oﬀ set): 論理関数 f の値を 0 にする入力の集合
他に、ドントケアセット (don’t-care set) もあり (後述)
論理式任意の論理関数は、論理式で表現可能 (次節)。同一の論理関数を表現する論理式
は複数存在する。
3.5 論理関数の論理式による表現
論理関数の論理式による表現は一意ではない。論理関数を表す積和形論理式を、論理
関数の積和形表現 (sum-of-products form) という。論理関数を表す和積形論理式を、論理
n
関数の和積形表現 (product-of-sums form) という。n 変数論理関数の個数は、22 である
(変数値の組合わせが 2n 個で、各々に対して関数値が 2 通り (0 または 1) ある)。
最小項 (minterm) 論理変数の各変数のリテラルを一つずつ含んだ積項。真理値表の各行
に一つの最小項が対応する。各変数が 1 の場合は肯定リテラル、0 の場合は否定リ
テラルとする。対応する行が成立する場合のみ、その最小項は 1 となる。
積和標準形 (canonical sum-of-products form)、加法標準形 (canonical disjunctive form)
論理関数を最小項の論理和で表したもの。関数値を 1 にする変数の組み合わせに対
応する最小項の論理和。任意の論理関数は積和標準形で一意に表現できる。表現が
一意に定まるので標準形 (canonical form) と呼ばれる。
最大項 (maxterm) 論理変数の各変数のリテラルを一つずつ含んだ和項。真理値表の各
行に一つの最大項が対応する。各変数が 1 の場合は否定リテラル、0 の場合は肯定
リテラルとする。対応する行が成立する場合のみ、その最大項は 0 となる。
和積標準形 (canonical product-of-sums form)、乗法標準形 (canonical conjunctive form)
論理関数を最大項の論理積で表したもの。関数値を 0 にする変数の組み合わせに対
応する最大項の論理積。任意の論理関数は和積標準形で一意に表現できる。
シャノン展開 (Shannon expansion) 任意の論理関数 f (x1 , · · · , xi , · · · , xn ) は、以下のよ
うに展開できる。
f (x1 , · · · , xi , · · · , xn ) = xi f (x1 , · · · , 0, · · · , xn ) + xi f (x1 , · · · , 1, · · · , xn )
任意の n 変数論理関数は、2 つの n − 1 変数論理関数に展開できる。すべての論理
変数について展開すると、最小項の和となり、積和標準形が得られる。
f (x1 , · · · , xi , · · · , xn ) をシャノン展開し (積和標準形に表し)、その全体に NOT 演算
を施したものをド・モルガンの定理を用いて展開すれば、和積標準形が得られる。
練習問題
1. 次の等式が成り立つことを示せ。
(a) ab + a b + bc = ab + a b + ac
(b) (a + abc) + (a + bc)(a + c) = a + bc
(c) ab + abc + ab = b
(d) ab + b c + ac = ab + b c
(e) a + b + a bc = a + b + c
2. 次の論理式をさらに簡単な積和形論理式にせよ
(a) (ab + bc) + (a + b)(ab + bc)
(b) ab + bc + ac
3. 次の論理関数の積和標準形と和積標準形を求めよ。
(a) f (a, b, c) = ab + bc
(b) f (a, b, c, d) =
∑
(1, 3, 7, 13, 15)
4. 次の論理関数の積和標準形をシャノン展開により求めよ。
(a) f (a, b) = a + b
(b) f (a, b, c) = (a + b)(b + c)(c + a)

Download Report