§８ブール代数と論理関数
［Ｂ］ ブール代数の性質
【今日の要点と補足】
ブール代数（Boolean algebra）は第４クオーターの講義『論理回路理論』の基礎となる代数であり，更に言えば，コンピュータの動作原理の基礎となる代数である。情報の学生であれば，a＋a＝a という式を見たら「あっ，ブール代数だ」とか「これは論理関数だな」ということが自然に思い起こされるようになるはずである。
ブール代数には二つの２項演算（加法と乗法）および一つの単項演算（補元）が定義されている。
二つの２項演算のそれぞれは結合法則・可換法則・単位法則を満たし，和の単位元は０（これを特に零元と名づけて積の単位元と区別する）であり，積の単位元は１である。（公理１・２・３）
加法と乗法に関して２種類の分配法則（公理４）が成立する。特に気をつける必要があるのは，a＋(b・c)＝(a＋b)・(a＋c) という分配法則である。これは通常の数の演算では成立しない。
補元とは，すべての要素 a について，ある性質をもつ要素（これを a の補元という）が一意的に決まるものであり，その意味では群における逆元と似ている。ただし名前が違うことからも分かるように，補元が満たすべき性質と逆元が満たすべき性質は当然別（公理５）である。［このページでは，アルファベットの上に横棒をつける表現ができないので，要素 a の補元を a' で表すことにする。試験の答案で a の補元を a' と書いても認められない。］
【今日の Quiz】
式 (x＋y'＋z)・(x＋y'＋z')・(x＋y＋z) を最も簡単な形にせよ。
（厳密には，どんなものが“簡単”なのかということを示す必要がある。今回は，ブール代数における式の変形を練習するという軽い意味で考えること。）
(x＋y'＋z)・(x＋y'＋z')・(x＋y＋z)
＝{(x＋y')＋(z・z')}・(x＋y＋z) ← 最初の二つの項に分配法則を適用
＝(x＋y'＋0)・(x＋y＋z) ← z・z'＝0，補元の性質
＝(x＋y')・(x＋y＋z) ← 零元の性質
＝x＋{y'・(y＋z)} ← 分配法則を適用
＝x＋(y'・y)＋(y'・z) ← 分配法則を適用
＝x＋0＋(y'・z) ← y'・y＝0
＝x＋(y'・z) ← 零元の性質
なお，上の式の導出においては，それぞれの演算の順序を明らかにするために必ずカッコをつけた。これは，ブール代数においては加法と乗法は対等であり，演算の優先順位はないためである。つまり，単に a＋b・c と書かれている場合，ブール代数においては a＋(b・c) の意味なのか，(a＋b)・c の意味なのかはあいまいである。しかし，通常の数の演算においては加法よりも乗法が優先されるため，a＋b・c が (a＋b)・c の意味であると考えることはあまりないだろうと思われる。そこで，カッコを用いて演算の順序が指定されていない場合は加法よりも乗法が優先されるという暗黙の了解を仮定すれば，上の式の導出は次のように書いてもよい。なお，乗法の演算記号・も省略した。
(x＋y'＋z)(x＋y'＋z')(x＋y＋z)
＝{(x＋y')＋zz'}(x＋y＋z) ← 最初の二つの項に分配法則を適用
＝(x＋y'＋0)(x＋y＋z) ← z・z'＝0，補元の性質
＝(x＋y')(x＋y＋z) ← 零元の性質
＝x＋y'(y＋z) ← 分配法則を適用
＝x＋y'y＋y'z ← 分配法則を適用
＝x＋0＋y'z ← y'・y＝0
＝x＋y'z ← 零元の性質
【期末試験対策】
教室：Ｋ101 ... 全員がこの部屋です
試験範囲：講義ノート§６〜§８
キーワード：次の英単語の意味を十分理解しておくこと
function, initial set, final set, surjection, injection, bijection, composite function, binary relation, linear order, ordered set, Hasse's diagram, quotient set, equivalence relation, equivalence class.
binary operation, unary operation, associative law, commutative law, unit element, inverse element, semigroup, unitary semigroup, group, ring, field.
Boolean algebra, compliment, de Morgan's law, n-ary logical function, Boolean function, truth table, minterm, maxterm, disjunctive normal form, minterm expansion, conjunctive normal form, maxterm expansion.
過去に確率６割以上で出題された問題文の一部：
『次に示す関数が ...，全射 ... 単射 ... 全単射 ...』
『次の順序集合の Hasse の図式を ...』
『次に示す２項関係 R について ...』
『次に示す２項演算 * が ...，半群 ... 単位的半群 ... 群 ...』
『次の３変数論理関数の和標準形 ... 積標準形 ...』