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 2025 ExpyDoc