Document

演習課題 No6 は少なくない学生さんから「分からない」
「難しい」
「答えを
知りたい」などの質問が寄せられていました．そこで，中間テストの前なの
で，そのような気分に返ってなれないかもしれませんが，気になって就眠で
きない（昔，そんなギャグでうけていた漫才がありましたが）人が居ては困
るので，敢て，１つの解答例を示してみました．
「１つの」と書いたのは，こ
のような課題には「答え方は無数に存在する」との立場で，あまり『模範解
答』などを求めて欲しくないと考えているので，あくまで「１つ」の考え方
である点を強調しています．是非とも，
（そのようなものの考え方・
・
「解答方
法」ではありません）理解して欲しいと考えています．
真理値表を使用しないで
1
真理値表を使用すると「総ての組み合わせ」を試すことができるので，ほぼ
いつでも有効な解答となります（もちろん，少しは例外もあるでしょうが）．
しかし，真理値表を使用しないでとなると，式変形で確認するしかないので，
一般には少し難しい（あるいは時間が掛かる）ことになります．
ここで「x OR y と xAND(NOTy)ORy とが同値となることを，真理値表
を使用しないで，どちらも積和標準形および和積標準形に式変形して，証明
してください．
」という問題ですが，その真意は，与えられた論理関数は「積
和標準形」「和積標準形」に一意に変形可能すなわち，
「積和標準形あるいは
和積標準形は必ず一通りである」という性質を使用して，２つの論理関数
• 「x OR y」すなわち，f1 (x, y) = x + y
• 「xAND(NOTy)ORy」すなわち，f2 (x, y) = xȳ + y
を「積和標準形」あるいは「和積標準形」に変形することによって，両者を
比較する問題となります．
1.1
積和標準形へ式変形する
シャノンの展開定理（積和標準形版）を思い出してください．どのような
論理関数でも f (x) = x̄f (0) + xf (1) の形式に展開（＝式変形）できることは
既に証明済みですね．そこで，２変数の論理関数 f (x, y) も同様に展開，すな
わち式変形可能です．この時，２変数の論理関数の「積和標準形」は必ず，
f (0, 0)x̄ȳ + f (0, 1)x̄y + f (1, 0)xȳ + f (1, 1)xy
と式変形できますね．
（実は，
「真理値表」でもこの値を必要とすることは全く
同じなのですが・
・）
1
1. 「x OR y」すなわち，f1 (x, y) = x + y の場合
f1 (0, 0) = 0 + 0 = 0
f1 (0, 1) = 0 + 1 = 1
f1 (1, 0) = 1 + 0 = 1
f1 (1, 1) = 1 + 1 = 1
2. 「xAND(NOTy)ORy」すなわち，f2 (x, y) = xȳ + y の場合
f2 (0, 0) = 00̄ + 0 = 0
f2 (0, 1) = 01̄ + 1 = 1
f2 (1, 0) = 10̄ + 0 = 1 + 0 = 1
f2 (1, 1) = 11̄ + 1 = 1
なる論理演算を行うことで，２つの論理関数：f1 (x, y) と f2 (x, y) の値（係
数に相当する部分）が総て決定できます．
次に，シャノンの展開定理（積和標準形版）を活用することで，
1. 「x OR y」すなわち，f1 (x, y) = x + y の場合
f1 (x, y) = f1 (0, 0)x̄ȳ + f1 (0, 1)x̄y + f1 (1, 0)xȳ + f1 (1, 1)xy と式変形
でき，上で求めた，f1 (0, 0) = 0，f1 (0, 1) = 1，f1 (1, 0) = 1 および
f1 (1, 1) = 1 を代入すれば，
f1 (x, y) = 0x̄ȳ + 1x̄y + 1xȳ + 1xy = x̄y + xȳ + xy
となります（これは一意な式変形なので心配はご無用です）．
2. 「xAND(NOTy)ORy」すなわち，f2 (x, y) = xȳ + y の場合
f2 (x, y) = f2 (0, 0)x̄ȳ + f2 (0, 1)x̄y + f2 (1, 0)xȳ + f2 (1, 1)xy と式変形
でき，上で求めた，f2 (0, 0) = 0，f2 (0, 1) = 1，f2 (1, 0) = 1 および
f2 (1, 1) = 1 を代入すれば，
f2 (x, y) = 0x̄ȳ + 1x̄y + 1xȳ + 1xy = x̄y + xȳ + xy
となります（当然，これも一意な式変形となります）．
従って，２つの論理関数の「積和標準形」が全く同じとなるので，
「両者は同
値」であると言えます．
以下はその意味では「蛇足」とも言えますが，シャノンの展開定理（和積
標準形版）を活用することになります．
2
1.2
和積標準形へ式変形する
シャノンの展開定理（和積標準形版）を利用します．どのような論理関数
でも f (x) = (x̄ + f (1))(x + f (0)) の形式に展開（＝式変形）できることは既
に証明済みですし，双対性 (Principle of Duality) より常に導出可能とも言え
ます．そこで，２変数の論理関数 f (x, y) も同様に展開，すなわち式変形可能
です．この時，２変数の論理関数の「和積標準形」は必ず，
(f (1, 1) + x̄ + ȳ)(f (1, 0) + x̄ + y)(f (0, 1) + x + ȳ)(f (0, 0) + x + y)
と式変形可能です．
既に，４つの係数：f (0, 0),f (0, 1),f (1, 0), および f (1, 1) の値は，前のサブ
節で導出済みです．
そこで，シャノンの展開定理（和積標準形版）を f1 (x, y) および f2 (x, y) に
適用することで，
1. 「x OR y」すなわち，f1 (x, y) = x + y の場合
f1 (x, y) = (f1 (1, 1)+x̄+ȳ)(f1 (1, 0)+x̄+y)(f1 (0, 1)+x+ȳ)(f1 (0, 0)+x+
y) と式変形でき，上で求めた，f1 (0, 0) = 0，f1 (0, 1) = 1，f1 (1, 0) = 1
および f1 (1, 1) = 1 を代入すれば，f1 (x, y) = (1 + x̄ + ȳ)(1 + x̄ + y)(1 +
x + ȳ)(0 + x + y) = (1)(1)(1)(0 + x + y) = x + y となります．
（実は f1 (x, y) は既に「和積標準形」だった訳ですね）．
2. 「xAND(NOTy)ORy」すなわち，f2 (x, y) = xȳ + y の場合
f2 (x, y) も f2 (x, y) = (f2 (1, 1) + x̄ + ȳ)(f2 (1, 0) + x̄ + y)(f2 (0, 1) +
x + ȳ)(f2 (0, 0) + x + y) と式変形でき，上で求めた，f2 (0, 0) = 0，
f2 (0, 1) = 1，f2 (1, 0) = 1 および f2 (1, 1) = 1 を代入すれば，f2 (x, y) =
(1+ x̄+ ȳ)(1+ x̄+y)(1+x+ ȳ)(0+x+y) = (1)(1)(1)(0+x+y) = x+y
となります．
今更ですが，
「和積標準形」はどのような論理関数でも一意の形式なの
で，当然，一致しますね．
ということで，２つの論理関数の「和積標準形」が全く同じ表現なので，
「両
者は同値」であるとの結論はここでも再確認できます．
2
真理値表を使用して
次に「⊕ を Ex-OR 記号とするとき，論理式 (x ⊕ y)AND(y ⊕ z)AND(z
⊕ x) を簡単な論理式で表現してください．
」という問題を真理値表を使用す
る方法とそうでない方法で考えてみましょう．
3
2.1
真理値表を使用してもよい場合
真理値表を使用してもよいとなると，いろいろと便利です（また，表記も
簡便となります）．
まず，2 つの論理変数 a, b からなる論理式 (a ⊕ b) は表 1 となります．
表 1: 論理式 (a ⊕ b) の真理値表
a
b
(a ⊕ b)
0
0
0
1
0
1
1
1
0
1
1
0
そこで，３つの論理式：(x ⊕ y)，(y ⊕ z)，(z ⊕ x) の真理値表は表 2 で表
現されます．
表 2: 論理式：(x ⊕ y)，(y ⊕ z)，(z ⊕ x) の真理値表
x
y
z
(x ⊕ y)
(y ⊕ z)
(z ⊕ x)
0
0
0
0
0
0
0
0
0
0
1
1
1
0
1
0
1
1
1
1
0
1
0
1
1
1
0
0
0
1
1
1
0
1
1
0
1
1
1
1
0
1
0
0
1
0
1
0
従って，題意の「論理式 (x ⊕ y)AND(y ⊕ z)AND(z ⊕ x) 」とは (x⊕y)(y ⊕
z)(z ⊕ x) なので，(x ⊕ y)，(y ⊕ z) および (z ⊕ x) の内，１つでもゼロがあ
れば，その AND(すなわち論理積) はゼロとなるので，
(x ⊕ y)(y ⊕ z)(z ⊕ x) = 0
と言える．これを真理値表で表現すれば，次の表 3 となります．
すなわち，
「⊕ を Ex-OR 記号とするとき，論理式 (x ⊕ y)AND(y ⊕ z)AND(z
⊕ x) を簡単な論理式で表現する」と真理値表の「表 3」より，論理変数 x, y, z
の値によらず，常にゼロ，すなわち，(x ⊕ y)(y ⊕ z)(z ⊕ x) = 0 となる，と
言えます．
4
表 3: 論理式：(x ⊕ y)，(y ⊕ z)，(z ⊕ x) の真理値表，その２
x
y
z
(x ⊕ y)
(y ⊕ z)
(z ⊕ x)
(x ⊕ y)AND(y ⊕ z)AND(z ⊕ x)
0
0
0
0
0
0
0
0
0
0
1
1
0
0
1
1
1
1
0
0
0
0
1
1
1
0
0
1
0
1
1
1
1
0
0
1
1
1
0
0
0
0
1
1
1
1
0
1
0
0
1
0
1
0
0
0
2.2
真理値表を使用しない場合
では，便利な真理値表をしない場合はどうなるでしょうか．もちろん，先
に述べた「積和標準形」あるいは「和積標準形」に変形することで解答する
ことも可能です．上でも述べたように，関数値（シャノンの展開定理の係数
に相当する値）を総て決定する作業と真理値表を作成する作業とは同値とも
言えます．従って，ここでは，少しだけ趣向を変えて，式変形だけで解答し
てみましょう．
「論理式 (x ⊕ y)AND(y ⊕ z)AND(z ⊕ x) 」は
(x ⊕ y)(y ⊕ z)(z ⊕ x)
と表記できるのは上で既に述べました．
(x ⊕ y)(y ⊕ z)(z ⊕ x) = (x̄y + xȳ)(ȳz + yz̄)(z̄x + z x̄)
(1)
= (x̄y ȳz + x̄yyz̄ + xȳ ȳz + xȳyz̄)(z̄x + z x̄) (2)
= (0 + x̄yz̄ + xȳz + 0)(z̄x + z x̄)
(3)
= (x̄yz̄ + xȳz)(z̄x + z x̄)
(4)
= x̄yz̄ z̄x + x̄yz̄z x̄ + xȳz z̄x + xȳzz x̄
(5)
=
(6)
0+0+0+0=0
上の式変形は容易に理解できるとは思いますが，念のため，少しだけ補足し
ておきます．
式 (1) は「排他的論理和 (Exclusive OR)」の定義式ですね．式 (2) は前半
の２項だけを分配則に従って展開しています．式 (3) は aā = 0 なる関係式，
5
および aa = a なる関係式を用いて簡単化しています．式 (4) を同様に分配則
を用いて展開すると式 (5) を得ます．しかし，ここでも aā = 0 なる関係式な
どを用いて，式 (6) を導くことができます．
Last updated: 平成 27 年 12 月 3 日
今井慈郎 Yoshiro Imai
6

Download Report