next up previous
次へ: 証明問題 上へ: 特別講義2 問題1の解答例 戻る: 最小項

最大項

2.1 次の式を最大項に展開しなさい。

$\displaystyle f(x, y, z) = xy \lor \sim x z $

単位元法で解く

最初に論理の特徴である和の分配則を適用して積形式にする。

$\displaystyle f(x, y, z)$ $\displaystyle =$ $\displaystyle xy \lor \sim x z$  
  $\displaystyle =$ $\displaystyle (xy \lor \sim x)(xy \lor z)$  
  $\displaystyle =$ $\displaystyle (x \lor \sim x)(y \lor \sim x)(x \lor z)(y \lor z)$  
  $\displaystyle =$ $\displaystyle (\sim x \lor y)(x \lor z)(y \lor z)$  

各項に不足する変数の単位元を加えて分配則を適用する。

第1項： 足りない変数$ z$の単位元 $ (\sim z z = 0)$を加える(論理和)。

$\displaystyle \sim x \lor y$ $\displaystyle =$ $\displaystyle (\sim x \lor y \lor \sim z z)$  
  $\displaystyle =$ $\displaystyle (\sim x \lor y \lor \sim z)(\sim x \lor y \lor z)$  
  $\displaystyle =$ $\displaystyle M_2 \cdot M_3$  

第2項： 足りない変数$ y$の単位元 $ (\sim y y = 0)$を加える(論理和)。

$\displaystyle x \lor z$ $\displaystyle =$ $\displaystyle (x \lor z \lor \sim y y)$  
  $\displaystyle =$ $\displaystyle (x \lor z \lor \sim y)(x \lor z \lor y)$  
  $\displaystyle =$ $\displaystyle (x \lor \sim y \lor z)(x \lor y \lor z)$  
  $\displaystyle =$ $\displaystyle M_5 \cdot M_7$  

第3項： 足りない変数$ x$の単位元 $ (\sim x x = 0)$を加える(論理和)。
$\displaystyle y \lor z$ $\displaystyle =$ $\displaystyle (y \lor z \lor \sim x x)$  
  $\displaystyle =$ $\displaystyle (y \lor z \lor \sim x)(y \lor z \lor x)$  
  $\displaystyle =$ $\displaystyle (\sim x \lor y \lor z)(x \lor y \lor z)$  
  $\displaystyle =$ $\displaystyle M_3 \cdot M_7$  

第1項と第2項と第3項の最大項をまとめるとつぎのような結果になる。

% latex2html id marker 889 $\displaystyle \therefore \quad xy \lor \sim x z$ $\displaystyle =$ $\displaystyle (\sim x \lor y \lor \sim z)(\sim x \lor y \lor z)$  
    $\displaystyle \land (x \lor \sim y \lor z)(x \lor y \lor z)$  
    $\displaystyle \land (\sim x \lor y \lor z)(x \lor y \lor z)$  
  $\displaystyle =$ $\displaystyle (\sim x \lor y \lor \sim z)(\sim x \lor y \lor z)(x \lor \sim y \lor z)(x \lor y \lor z)$  
  $\displaystyle =$ $\displaystyle M_2 M_3 M_5 M_7$  

乗法標準形法で解く

$\displaystyle f(x, y, z)$ $\displaystyle =$ $\displaystyle xy\, \lor \sim x z$  
$\displaystyle f(0, 0, 0)$ $\displaystyle =$ $\displaystyle 0\cdot0\, \lor \sim 0\cdot 0 = 0$  
$\displaystyle f(0, 0, 1)$ $\displaystyle =$ $\displaystyle 0\cdot0\, \lor \sim 0\cdot 1 = 1$  
$\displaystyle f(0, 1, 0)$ $\displaystyle =$ $\displaystyle 0\cdot1\, \lor \sim 0\cdot 0 = 0$  
$\displaystyle f(0, 1, 1)$ $\displaystyle =$ $\displaystyle 0\cdot1\, \lor \sim 0\cdot 1 = 1$  
$\displaystyle f(1, 0, 0)$ $\displaystyle =$ $\displaystyle 1\cdot0\, \lor \sim 1\cdot 0 = 0$  
$\displaystyle f(1, 0, 1)$ $\displaystyle =$ $\displaystyle 1\cdot0\, \lor \sim 1\cdot 1 = 0$  
$\displaystyle f(1, 1, 0)$ $\displaystyle =$ $\displaystyle 1\cdot1\, \lor \sim 1\cdot 0 = 1$  
$\displaystyle f(1, 1, 1)$ $\displaystyle =$ $\displaystyle 1\cdot1\, \lor \sim 1\cdot 1 = 1$  

この関数値を乗法標準形に適用する。

$\displaystyle f(x, y, z)$ $\displaystyle =$ $\displaystyle \{f(0,0,0) \lor M_7\}\{f(0,0,1) \lor M_6\}\{f(0,1,0) \lor M_5\}\{f(0,1,1) \lor M_4\}$  
    $\displaystyle \land \{f(1,0,0) \lor M_3\}\{f(1,0,1) \lor M_2\}\{f(1,1,0) \lor M_1\}\{f(1,1,1) \lor M_0\}$  
  $\displaystyle =$ $\displaystyle (0 \lor M_7)(1 \lor M_6)(0 \lor M_5)(1 \lor M_4)(0 \lor M_3)(0 \lor M_2)(1 \lor M_1)(1 \lor M_0)$  
  $\displaystyle =$ $\displaystyle (0 \lor M_7)\cdot 1\cdot (0 \lor M_5)\cdot 1\cdot (0 \lor M_3)(0 \lor M_2)\cdot 1 \cdot 1$  
  $\displaystyle =$ $\displaystyle (0 \lor M_7)(0 \lor M_5)(0 \lor M_3)(0 \lor M_2)$  
  $\displaystyle =$ $\displaystyle M_7 M_5 M_3 M_2$  
  $\displaystyle =$ $\displaystyle M_2 M_3 M_5 M_7$  
  $\displaystyle =$ $\displaystyle (\sim x \lor y \lor \sim x)(\sim x \lor y \lor z)(x \lor \sim y \lor z)(x \lor y \lor z)$  


テーブル法(その1)で解く

関数値を否定した$ \sim f$の列を作る

x y z x y $ \sim x$ z f $ \sim f$
0 0 0 0 0 0 1
0 0 1 0 1 1 0
0 1 0 0 0 0 1
0 1 1 0 1 1 0
1 0 0 0 0 0 1
1 0 1 0 0 0 1
1 1 0 1 0 1 0
1 1 1 1 0 1 0

最初に否定の関数値$ \sim f$が1である行から加法標準形を求める。

$\displaystyle \sim f(x, y, z) = \sim x \sim y \sim z \lor \sim x y \sim z \lor x \sim y \sim z \lor x \sim y z $

両辺を否定し、ド・モルガンの法則を適用する。

$\displaystyle \sim \sim f(x, y, z) = \sim (\sim x \sim y \sim z \lor \sim x y \sim z \lor x \sim y \sim z \lor x \sim y z) $

つぎのように乗法標準形が求まる。

$\displaystyle f(x, y, z)$ $\displaystyle =$ $\displaystyle (x \lor y \lor z)(x \lor \sim y \lor z)(\sim x \lor y \lor z)(\sim x \lor y \lor \sim x)$  
  $\displaystyle =$ $\displaystyle (\sim x \lor y \lor \sim x)(\sim x \lor y \lor z)(x \lor \sim y \lor z)(x \lor y \lor z)$  
  $\displaystyle =$ $\displaystyle M_2 M_3 M_5 M_7$  

テーブル法その2（直接法）で解く

x y z x y $ \sim x$ z f
0 0 0 0 0 0
0 0 1 0 1 1
0 1 0 0 0 0
0 1 1 0 1 1
1 0 0 0 0 0
1 0 1 0 0 0
1 1 0 1 0 1
1 1 1 1 0 1

fが0である行の3変数 $ (x,y,z)$から直接、乗法標準形を書き出す。 なお、各変数は0を肯定、1を否定とする。例えば、$ 0\,1\,0$ は $ (x \lor \sim y \lor z)$とする。( $ \because \quad \sim (0\,1\,0) = 1 \lor 0 \lor 1$)

$\displaystyle f(x, y, z)$ $\displaystyle =$ $\displaystyle (x \lor y \lor z)(x \lor \sim y \lor z)(\sim x \lor y \lor z)(\sim x \lor y \lor \sim z)$  
  $\displaystyle =$ $\displaystyle M_7 M_5 M_3 M_2$  
  $\displaystyle =$ $\displaystyle M_2 M_3 M_5 M_7$  

2.2 次の式を最大項に展開しなさい。

$\displaystyle f(x, y, z) = x \lor y \sim z $

単位元法で解く

最初に分配則を適用してから足りない変数の単位元を加える。最後にもう一度 分配則を適用する。

$\displaystyle f(x, y, z)$ $\displaystyle =$ $\displaystyle x \lor y \sim z$  
  $\displaystyle =$ $\displaystyle (x \lor y)(x \lor \sim z)$  
  $\displaystyle =$ $\displaystyle (x \lor y \lor \sim z z)(x \lor \sim z \lor \sim y y)$  
  $\displaystyle =$ $\displaystyle (x \lor y \lor \sim z)(x \lor y \lor z)(x \lor \sim z \lor \sim y)(x \lor \sim z \lor y)$  
  $\displaystyle =$ $\displaystyle (x \lor y \lor \sim z)(x \lor y \lor z)(x \lor \sim y \lor \sim z)(x \lor y \lor \sim z)$  
  $\displaystyle =$ $\displaystyle (x \lor \sim y \lor \sim z)(x \lor y \lor \sim z)(x \lor y \lor z)$  
  $\displaystyle =$ $\displaystyle M_4 M_6 M_7$  

乗法標準形法で解く

$\displaystyle f(x, y, z)$ $\displaystyle =$ $\displaystyle x\, \lor y \sim z$  
$\displaystyle f(0, 0, 0)$ $\displaystyle =$ $\displaystyle 0\, \lor 0 \sim 0 = 0$  
$\displaystyle f(0, 0, 1)$ $\displaystyle =$ $\displaystyle 0\, \lor 0 \sim 1 = 0$  
$\displaystyle f(0, 1, 0)$ $\displaystyle =$ $\displaystyle 0\, \lor 1 \sim 0 = 1$  
$\displaystyle f(0, 1, 1)$ $\displaystyle =$ $\displaystyle 0\, \lor 1 \sim 1 = 0$  
$\displaystyle f(1, 0, 0)$ $\displaystyle =$ $\displaystyle 1\, \lor 0 \sim 0 = 1$  
$\displaystyle f(1, 0, 1)$ $\displaystyle =$ $\displaystyle 1\, \lor 0 \sim 1 = 1$  
$\displaystyle f(1, 1, 0)$ $\displaystyle =$ $\displaystyle 1\, \lor 1 \sim 0 = 1$  
$\displaystyle f(1, 1, 1)$ $\displaystyle =$ $\displaystyle 1\, \lor 1 \sim 1 = 1$  

関数値を略記する。

$\displaystyle f_0$ $\displaystyle =$ 0  
$\displaystyle f_1$ $\displaystyle =$ 0  
$\displaystyle f_2$ $\displaystyle =$ $\displaystyle 1$  
$\displaystyle f_3$ $\displaystyle =$ 0  
$\displaystyle f_4$ $\displaystyle =$ $\displaystyle 1$  
$\displaystyle f_5$ $\displaystyle =$ $\displaystyle 1$  
$\displaystyle f_6$ $\displaystyle =$ $\displaystyle 1$  
$\displaystyle f_7$ $\displaystyle =$ $\displaystyle 1$  

この関数値を乗法標準形に適用する。

$\displaystyle f(x, y, z)$ $\displaystyle =$ $\displaystyle (f_0 \lor M_7)(f_1 \lor M_6)(f_2 \lor M_5)(f_3 \lor M_4)$  
    $\displaystyle \land (f_4 \lor M_3)(f_5 \lor M_2)(f_6 \lor M_1)(f_7 \lor M_0)$  
  $\displaystyle =$ $\displaystyle (0 \lor M_7)(0 \lor M_6)(1 \lor M_5)(0 \lor M_4)(1 \lor M_3)(1 \lor M_2)(1 \lor M_1)(1 \lor M_0)$  
  $\displaystyle =$ $\displaystyle M_7 M_6 M_4$  
  $\displaystyle =$ $\displaystyle M_4 M_6 M_7$  
  $\displaystyle =$ $\displaystyle (x \lor \sim y \lor \sim z)(x \lor y \lor \sim z)(x \lor y \lor z)$  


テーブル法(直接法)で解く

x y z y $ \sim z$ f
0 0 0 0 0
0 0 1 0 0
0 1 0 1 1
0 1 1 0 0
1 0 0 0 1
1 0 1 0 1
1 1 0 1 1
1 1 1 0 1

fが0である行の3変数 $ (x,y,z)$から直接、乗法標準形を書き出す。 なお、各変数は0を肯定、1を否定とする。例えば、$ 0\,0\,1$ は $ (x \lor y \lor \sim z)$とする。( $ \because \quad \sim (0\,0\,1) = 1 \lor 1 \lor 0$)

$\displaystyle f(x, y, z)$ $\displaystyle =$ $\displaystyle (x \lor y \lor z)(x \lor y \lor \sim z)(x \lor \sim y \lor \sim z)$  
  $\displaystyle =$ $\displaystyle M_7 M_6 M_4$  
  $\displaystyle =$ $\displaystyle M_4 M_6 M_7$  

next up previous
次へ: 証明問題 上へ: 特別講義2 問題1の解答例 戻る: 最小項
MANOME Yoichi 平成17年6月17日