c 関西学院大学 石浦 菜岐佐)
「論理回路」ノート (2014 年度, http://ist.ksc.kwansei.ac.jp/∼ishiura/lc/
3
論理代数と論理関数 (2)
⊕
♣ 排他的論理和
演算
→ 演算
積和 形と 積和標準
♣ 含意
♣
形
♣ 論理式の高度な簡単化
3.1
3.1.1
排他的論理和演算
排他的論理和演算とその性質
排他的論理和 (
x
y
0
0
0
1
1
0
1
1
exclusive
-or)
x⊕y
0
1
1
0
xとyの
xとyが
一方のみが 1
異なる とき 1
基本的な性質
(1) 交換律
x⊕y =y⊕x
(2) 結合律
(x ⊕ y) ⊕ z = x ⊕ (y ⊕ z)
(3) and 演算との分配律
xy ⊕ xz
x(y ⊕ z) =
(4) 零元, 単位との演算
x⊕0=0⊕x=
x⊕1=1⊕x=
x
x
真理値表で確認
x
0
x⊕0
x
1
0
0
0
0
1
1
0
1
1
1
x⊕1
1
0
3–1
のとき 1
(5) 自分自身との演算
x⊕x=
x⊕x=
0
1
真理値表で確認
x
x
0
0
1
1
x⊕x
0
0
x
x
0
1
1
0
x⊕x
1
1
(6) not 演算は位置を交換可能
x⊕y =
x⊕y
=
x⊕y
x⊕y⊕z =x⊕y⊕z =x⊕y⊕z =x⊕y⊕z =x⊕y⊕z =x⊕y⊕z
これは例えば次のようにして示せる
⎧
⎨ (x ⊕
)⊕y = x⊕y
x⊕y =x⊕y⊕
=
⎩
x ⊕ (y ⊕
)= x⊕y
1
1
例題 3.1
1
論理関数 f (x, y, z) = x ⊕ y ⊕ z の真理値表を示せ.
まず x ⊕ y を, 次に (x ⊕ y) ⊕ z の真理値を求めればよい
x
y
z
x⊕y
0
0
0
0
0
0
1
0
0
1
0
1
0
1
1
1
1
0
0
1
1
0
1
1
1
1
0
0
1
1
1
0
(x ⊕ y) ⊕ z
0
1
1
0
1
0
0
1
x, y, z 中の 1 の個数
0
1
1
2
1
2
2
3
☆ x1 ⊕ x2 · · · ⊕ xn の直観的意味
x1 , · · · , xn の中の
1 の数が奇数
のとき 1
3–2
3.1.2
排他的論理和を含む式の簡単化
例題 3.2
与えられた論理式を簡単化せよ.
1. 相補律 x ⊕ x = 1 は or の場合と同じ.
• ab ⊕ ab
= a(b ⊕ b)
a
=
2. 吸収律は成立しない. x ⊕ 1 =
x
となる.
• a ⊕ ab
= a(1 ⊕ b)
ab
=
3. 括弧の展開は通常の論理和と同様
• (xy ⊕ yz)(y ⊕ z) ⊕ yz
= (xyy ⊕ xyz ⊕ yz y ⊕ yzz) ⊕ yz
= (0 ⊕ xyz ⊕ 0 ⊕ 0) ⊕ yz
= xyz ⊕ yz
= (x ⊕ 1)yz
xyz
=
4. x ⊕ x = 0 となることに注意.
• a(b ⊕ c) ⊕ ac
= ab ⊕ ac ⊕ ac
ab
=
5. 否定の交換 (x ⊕ y = x ⊕ y)
• (a ⊕ b ⊕ c)(a ⊕ b ⊕ c)
= (a ⊕ b ⊕ c)(
a⊕b⊕c)
= (a ⊕ b ⊕ c)
練習 3.1
次の式を簡単化せよ.
1. ab ⊕ abc ⊕ abc
2. (a ⊕ bc)(a ⊕ b)
3. ab ⊕ abc ⊕ abc
4. a ⊕ b ⊕ c
3–3
排他的論理和の and, or, not による書き換え
3.1.3
【性質 3.1】排他的論理和演算は and, or, not で表せる
xy + xy
x⊕y =
x
y
x⊕y
0
0
0
0
1
1
···
1
0
1
···
1
1
0
【重要】
xy
xy
例題 3.3 排他的論理和演算を and, or, not 演算で表すことにより, 次の等式を証明せよ.
1. x ⊕ x = 0
LHS
1
=
xx + xx
= 0+0=0
2. x ⊕ y = x ⊕ y
xy + x y =xy + x y
RHS = xy + xy
= xy · xy
< ドモルガン; A + B = A B>
LHS =
=
(x + y) · (x + y)
< ドモルガン; AB = A + B>
= xx + xy + x y + yy
= xy + x y = LHS
3.1.4
排他的論理和の応用
排他的論理和演算は，通信や暗号の分野でよく用いる
1. 誤り検出
• 単にデータだけを送る場合
(x1 , x2 , x3 , x4 ) = (1, 1, 0, 1) を送信
(x1 , x2 , x3 , x4 ) = (1, 0, 0, 1) を受信
困る
• データに「パリティ検査ビット」p を付加する
(x1 , x2 , x3 , x4 , p)= (1, 1, 0, 1,
–
(x1 , x2 , x3 , x4 , p)= (1, 0, 0, 1, 1) を受信
偶数 かどうか検査
NG なら 再送要求
送信時に付加する検査ビット p = x1 ⊕ x2 ⊕ x3 ⊕ x4
受信データの検査 x1 ⊕ x2 ⊕ x3 ⊕ x4 ⊕ p =0 なら OK
1 の個数が
–
1 ) を送信
偶数
になるようにする
1 の個数が
☆ 複数ビットの誤りを検出するしたり, 誤りを自動的に訂正する方法が種々存在する.
1 LHS
は left-hand side の略で 「左辺」を意味する. 同様に, RHS は right-hand side の略で 「右辺」を意味する.
3–4
2. 暗号化
• 単純な暗号 (しかし, 鍵が長ければ最強)
< 暗号化 >
メッセージ
⊕
鍵
10101111
< 復号 >
暗号文
11010101
鍵
01111010
暗号文
01111010
⊕
メッセージ
11010101
10101111
☆ AES などの複雑な暗号処理の中でも排他的論理和演算が用いられる
3.2
含意演算
含意 (
x
y
0
0
0
1
1
0
1
1
imply
) 演算
x→y
1
1
0
1
x
ならば
y
☆ x を「ブツを渡す」, y を「代金を支払う」とすると, x → y は「ブツを渡せば代金を支払う」になる
ここで, ブツを渡さないのに代金を支払っても, 「ブツを渡せば代金を支払う」を満たしていることに注意!
【性質 3.2】含意演算は or と not で表せる
x→y=
x+y
【重要】
例題 3.4 含意演算を or 演算および not 演算で表すことにより, 次の等式を証明せよ.
1. (x → y)(x → z) = (x → yz)
LHS = (x + y)(x + z) = x + yz
RHS = x + yz = LHS
3–5
3.3
3.3.1
積和形と積和標準形
積和形論理式
sum-of-products
次の形の論理式を積和形 (
form) と呼ぶ
abc + bc + a
積
積
積
積和
用語
(厳密な定義は付録参照)
– a, b, c, b, c, a (論理変数とその否定) を
– abc, bc, a (リテラルの論理積) を
積項数やリテラル数は, 論理式の
a + abc + cd + cd
=
4
積項数
リテラル数
積項
簡単さ
(
literal ) と呼ぶ
product term ) と呼ぶ
=
3
a+c
積項数
リテラル数
(
の尺度になる
a + cd + cd
積項数
8
リテラル
5
2
2
リテラル数
(注) 次の論理式も積和形である
a + b
積
積
積和
abc
a
積
積和
積和
積
(参考) 次の形の論理式を「和積形」(product-of-sums form) と呼ぶ
(a + b + c) (b + c) a
和
和
和
和積
練習 3.2
次の論理式 (a)∼(d) について, 下記の問いに答えよ.
(a) a + bc + abc
(b) (a + bc)(a + d)(ac + bd)
(c) a + c
(d) b
1. (a) の積項数とリテラル数はそれぞれいくらか
2. 積和形はどれか
3.3.2
積和標準形
練習 3.3
下記の空欄を埋めよ
(1) (a, b, c) が (1, 1, 1) のときにだけ 1 になる論理関数は f1 (a, b, c) = abc である
(2) (a, b, c) が (1, 0, 1) のときにだけ 1 になる論理関数は f2 (a, b, c) =
(3) (a, b, c) が (
0, 0, 1
abc
である
) のときにだけ 1 になる論理関数は f3 (a, b, c) = abc である
(4) (a, b, c) が (1, 1, 1) または (1, 0, 1) のときにだけ 1 になる論理関数は f4 (a, b, c) = abc + abc である
(5) (a, b, c) が (0, 1, 0) または (1, 1, 0) のときにだけ 1 になる論理関数は
f5 (a, b, c) =
abc
+
abc
である
(6) (a, b, c) が (0, 0, 1), (0, 1, 1), または (1, 0, 1) のときにだけ 1 になる論理関数は
f6 (a, b, c) =
abc
+
abc
+
abc
である
3–6
• 最小項 (
minterm
)
– 一つ入力組合せ ((a, b, c) = (0, 1, 0) 等) に対してのみ 1 になる積項を最小項と呼ぶ
– 最小項は,
全変数
のリテラルを含む積項である
(例) 全変数が a, b, c のとき, abc や abc は最小項である
canonical sum-of-products form)
論理関数 f を 最小項 の論理和で表わしたものを f の積和標準形という2
• 積和標準形 (
例題 3.5 次の論理関数の積和標準形を求めよ
1.
a
b
c
f (a, b, c)
0
0
0
0
0
0
0
1
1
0
1
0
0
1
1
0
1
0
0
0
1
0
1
1
1
1
0
0
1
1
1
1
⇒
abc
⇒
abc
⇒
abc
これより f (a, b, c) =
abc
+
abc
+
abc
【復習】論理関数の値を 1 にする入力の集合をオンセット (onset) という
onset(f (a, b, c)) = {(
0, 0, 1 ), ( 1, 0, 1 ), ( 1, 1, 1 )} である
積和標準形は, 論理関数のオンセットを論理式で表したもの, と言うことができる
2. g(a, b, c, d) = (3, 7, 12, 13)
onset(g) = {(
0, 0, 1, 1 ), ( 0, 1, 1, 1 ), ( 1, 1, 0, 0 ), ( 1, 1, 0, 1 )} より
g(a, b, c, d) =
abcd
+
abcd
【性質 3.3】ある論理関数を表す論理式は
+
abcd
無限に
+
abcd
存在するが, 積和標準形は
一意
「標準形」と呼ばれるのはこのため
例) 多数決関数 fmaj (a, b, c) を表現する式は複数存在する
fmaj (a, b, c)
= ab + bc + ca = ab + bc + abc = (a + b)(b + c)(c + a)
= abc + abc + abc + abc (積和標準形; 一意)
【性質 3.4】任意の論理関数は
2 最小項展開,
論理式
で表現可能.
(積和標準形を用いればよい.)
主加法標準形 (disjunctive canonical form) とも呼ばれる
3–7
.
練習 3.4
次の論理関数の積和標準形を示せ.
1. f (a, b, c)
a
b
c
f (a, b, c)
0
0
0
0
0
1
0
1
0
0
1
1
0
1
0
1
1
1
0
0
0
1
0
0
1
1
1
1
0
1
1
0
2. g(a, b, c, d) =
3.4
(1, 4, 9)
論理式の高度な簡単化
☆ 少し難しい. 現時点では必ずしもできなくてよいので, あまり深追いしないこと.
例題 3.6 与えられた論理式を簡単化せよ.
1. ドモルガンと相補律
• a + b + ab
= a+b+
a+b
< ドモルガン (逆) >
< 相補律; A + A = 1 >
=1
2. x + xy = x + y, およびその応用
• x + xy
=
x + xy
< 吸収律 x + xy = x を逆に適用して冗長な項を生成 >
+ xy
= x + (x + x)y = x + y
• a + b + abc
= (a + b) + (a + b) · c
= a+b+c
< ドモルガン >
<X + Xc = X + c を適用 >
3. 項のコピー
• x y + xy + xy
= xy +
xy + xy
+ xy
<xy を複製 >
= x(y + y) + (x + x)y = x + y
4. xy + yz + xz = xy + xz
(冗長な項の削除の一種だが, この変形は特に consensus と呼ばれる)
• xy + yz + xz
= xy +
xyz + xyz
+ xz
<yz を分割 >
= xy(1 + z) + (1 + y)xz = xy + xz
3–8
付録 3.1
用語の定義
• リテラル (literal)
論理変数またはその論理否定をリテラルと呼ぶ
(例) a, b, c が論理変数のとき, a, b, c, a, b, c はリテラルである
• 積項 (product term)
リテラルの論理積のうち, 同じ変数のリテラルを 2 個以上含まないものを積項と呼ぶ
(例) ab や abc や b や c は積項である
(例) aab や abbc は積項ではない (同じ変数のリテラルが 2 個以上含まれる)
• 積和形 (sum-of-products form)
積項の論理和からなる論理式を積和形 (論理式) と呼ぶ
(例) a + bcd + ac は積和形である
• 最小項 (minterm)
全ての変数のリテラルを含む積項を最小項という
(例) 変数集合が {a, b, c} のとき, abc や abc は最小項である (ab や a は最小項ではない)
練習問題の解答例
練習 3.1
1. ab ⊕ abc ⊕ abc = ab ⊕ ab(c ⊕ c) = ab ⊕ ab = a(b ⊕ b) = a
2. (a ⊕ bc)(a ⊕ b) = aa ⊕ ab ⊕ abc ⊕ bbc = a ⊕ ab ⊕ abc = a(1 ⊕ b) ⊕ abc = ab ⊕ abc = ab(1 ⊕ c) = abc
3. ab ⊕ abc ⊕ abc = ab(1 ⊕ c) ⊕ abc = abc ⊕ abc = a(b ⊕ b)c = ac
4. a ⊕ b ⊕ c = a ⊕ b ⊕ c = a ⊕ b ⊕ c = a ⊕ b ⊕ c
練習 3.2
1. 積項数は 3, リテラル数は 6
2. 積和形は (a), (c), (d)
練習 3.3
(2) abc
(3) 0, 0, 1
(5) abc, abc
(6) abc, abc, abc
練習 3.4
1. f (a, b, c) = a bc + abc + abc
2. g(a, b, c, d) = a b cd + abc d + ab cd
Nagisa ISHIURA
3–9
© Copyright 2024 ExpyDoc
