［第５回演習：ブール代数］

１．[a] ブール代数の公理 [B₁]〜[B₄]（text p.251）だけを用いた有界律 a + 1 ＝ 1 の証明を以下に示す。それぞれの行の等号にはどの公理が用いられているかを例にならって記入せよ。

　　　a + 1
　　　＝ (a + 1) * 1　　　 　← 単位元の同一律 (3b)
　　　＝ (a + 1) * (a + a')　　← 和の補元律 (4a)
　　　＝ a + (1 * a')　　　　← 和の分配律 (2a)
　　　＝ a + (a' * 1)　　　　← 積の交換律 (1b)
　　　＝ a + a'　　　　　　← 単位元の同一律 (3b)
　　　＝ 1　　　　　　 　 ← 和の補元律 (4a)

　　[b] 吸収律 a + (a * b) ＝ a の証明を以下に示す。[a] と同様に考えよ。ただし，１ヶ所で [a] で証明した有界律を使っている。

　　　a + (a * b)
　　　＝ (a * 1) + (a * b)　　← 単位元の同一律 (3b)
　　　＝ a * (1 + b)　　　　← 積の分配律 (2b)
　　　＝ a * (b + 1)　　　　← 和の交換律 (1a)
　　　＝ a * 1　　　　　　← 和の有界律 (6a)
　　　＝ a　　　　　　 　← 単位元の同一律 (3b)

２．次のブール式を加法標準形に直せ。いずれも１つの基本積になる。式の変形には公理だけでなく定理を自由に使ってよい。なお，積の演算記号は省略されている。

　　(1) x(xy' + x'y + y'z)　　(2) (x + y')'(xy)'　　(3) y(x + yz)'　　(4) xy(x' + z') + x(x'z + y'z')

　(1) x(xy' + x'y + y'z) ＝ xy'
　(2) (x + y')'(xy)' ＝ x'y
　(3) y(x + yz)' ＝ x'yz'
　(4) xy(x' + z') + x(x'z + y'z') ＝ xz'

【注意】(1) では，カッコをはずすと xy' + xy'z となるが，この第１項は第２項を含むためこのままでは加法標準形ではない。吸収律を用いて xy' となる。
　(4) では，xyz' + xy'z' が導かれるが，この２つの項はいずれも他を含まないので，このままで加法標準形である。（従って，問題文にある「いずれも１つの基本積になる」という文章は間違いである。）ただし，xyz' + xy'z' = xz'(y + y') = xz' であるから，このブール式は xz' と表現でき，これは加法標準形である。つまり，ブール式の加法標準形は一意には決まらない。（完全加法標準形は，積や和の順序を無視すれば，一意的に決まる。）この問題の答は，xyz' + xy'z' でも xz' でも 正解である。

３．次に示すブール式について，完全加法標準形，カルノ図表，最簡加法標準形をそれぞれ求めよ。

　　(1) x(y' + z) + x'(y + z)

　　　完全加法標準形　　xyz + xy'z + xy'z' + x'yz + x'yz' + x'y'z

　　(2) x(y' + z) + (x + y')'

　　　完全加法標準形　　xyz + xy'z + xy'z' + x'yz + x'yz'

【注意】このブール式の最簡加法標準形は２通りある。問題には「全ての最簡加法標準形を求めよ」とは書いていないので，いずれか一方を書けば正解となる。ただし，何通りかある場合は，その全てを書いておくことを奨励する。