§８ブール代数と論理関数
［Ｄ］ 論理関数
［Ｅ］ 論理関数の展開
【今日の要点と補足】
B＝{0, 1} とする。この B はブールの頭文字だと考えてもよいし，２値あるいは２進を意味する形容詞 binary の B だと考えてもよい。n 個の集合 B の直積集合 B×B×...×B を Bn と書く。n 変数論理関数とは，Bn から B への関数である。つまり，n 個の変数 x1，x2，...，xn のそれぞれに 0 か 1 の値が与えられたとき，それらの値から一つの値（0 または 1）を対応させるものが n 変数論理関数である。n 変数論理関数を定めることは，2n 行からなる真偽表（講義ノート p.45）を定めることと等しい。
関数を変数を用いた数式で表現しようとするのはごく自然な成り行きである。集合 B において定義された加法と乗法および補元を講義ノート p.44 の［例２］で定義したものとして，論理関数を変数を用いた数式で表現することができる。ところが，同じ論理関数（真偽表が同じものになるということ）をいろいろな形で数式表現できる。例えば，前回の講義における Quiz では，(x＋y'＋z)(x＋y'＋z')(x＋y＋z) と x＋y'z が等しいことを確かめた。［前回と同様に，アルファベットの上に横棒をつける表現ができないので，要素 a の補元を a' で表している。］
論理関数を数式表現する標準的な方法として和標準形と積標準形がある。
『和標準形は，最小項の和の形で論理関数を表現する。ここで，最小項とは n 個の変数（または変数の補元）の積である。和標準形に現れる最小項は，その関数の値が 1 となる場合の変数の組から決めることができる。例えば，３変数論理関数 f(x,y,z) の場合で，３つの変数の組が (0, 1, 0) のときその関数の値が 1 となるなら，和標準形には最小項 x'・y・z' が現れる。』
上に書いた『』に挟まれた文章において「和 ←→ 積」「最小 ←→ 最大」「1 ←→ 0」「・(乗法の記号) ←→ ＋(加法の記号）」という置き換えをすれば，積標準形の説明文になる。これがブール代数の双対性 (duality) である。この置き換えに従って“例えば”以下を書き直すと次のようになる。『例えば，３変数論理関数 f(x,y,z) の場合で，３つの変数の組が (1, 0, 1) のときその関数の値が 0 となるなら，積標準形には最大項 x'＋y＋z' が現れる。』
【練習問題Ｆの答】
乗法の記号・は省略する。
f1(x,y,z)＝x'y＋y'z＋z'x
＝x'y'z＋x'yz'＋x'yz＋xy'z'＋xy'z＋xyz'
＝(x＋y＋z)(x'＋y'＋z')
f2(x,y,z)＝xy＋z(x'y＋xy')
＝x'yz＋xy'z＋xyz'＋xyz
＝(x＋y＋z)(x＋y＋z')(x＋y'＋z)(x'＋y＋z)
f3(x,y,z)＝xy＋yz'＋x'z
＝x'y'z＋x'yz'＋x'yz＋xyz'＋xyz
＝(x＋y＋z)(x'＋y＋z)(x'＋y＋z')