離散数学
論理回路の復習、ブール代数 (1)
応用情報工学科
准教授 松野 裕
2016 年 10 月 1 日
1 はじめに
本講義では、情報工学で用いられる離散数学の基礎を、いくつかの題材の中で学ぶ。現時点での講義予定内 容は以下である。
• 論理回路、ブール代数
• プログラミング言語など（予定）
授業予定は以下である。
• 10.1, 10.8, 10.15(泉 先 生), 10.22, 10.29, 11.12, 11.19(中 間 試 験), 11.26, 12.10, 12.17, 12.24, 1.14, 1.21(期末試験)
毎回の授業は、5分程度で前回の演習の解説、60分程度の授業、残りの時間を演習に当てる。授業の資料は moodleに置いてある。登録キーは“dm2016”である。
2 論理回路の復習
本授業では情報工学で用いられる数学的構造の例としてブール代数を紹介するが、その前に簡単に論理回路 の復習をする。論理回路には組合せ回路と順序回路がある。前者は入力のみによって出力が一意に決まるのに 対し、後者は入力と回路の状態（メモリなど）によって出力が決まる。
2.1 組合せ回路と論理関数
2進数の組合せ回路を考える。入力と出力は一つまたは複数の変数で表現され、その変数の取りうる値は、 0または1となる。このことを数学的に記述すると、以下になる。
F : (X0, . . . , Xm−1) → (Y0, . . . , YN −1) Xi, Yj∈ {0, 1}
1
この式は、ある2進数の組合せ回路は、入力変数がX1, . . . , Xm−1, 出力変数Y1, . . . , Yn−1の(論理)関数F であることを表している。以下では、出力が１変数である以下を考える。
F : (X0, . . . , Xm−1) → Y Xi, Y ∈ {0, 1}
2.2 ３つの基本論理演算
組 合 せ 回 路 で 用 い ら れ る 、最 も 基 本 的 な 関 数 はAN D, OR, N OT で あ る 。そ れ ぞ れ の 真 理 値 表 お よ び MIL(Military Standard)記法で表した図を示す。MIL記法については*1などを参照してほしい。
A B Q= AN D(A, B)
0 0 0
0 1 0
1 0 0
1 1 1
A B Q= OR(A, B)
0 0 0
0 1 1
1 0 1
1 1 1
A Q= N OT (A)
0 1
1 0
2.3 完備性の証明
すべての論理関数を、少数の基本論理演算の組合せで表現できるとき、その基本論理演算の集合を完備集合
(Complete Set)という。論理回路を設計する立場から見れば、完備性とは、数種類の基本論理回路を組み合
わせることで、どんな複雑な組合せ回路も実現できることを示している。
定理1 {AN D, OR, N OT }は完備集合である。ただし、AN D, ORはともに2入力とする。
証明
数学的帰納法を用いる。任意のM入力の論理関数をF(X0, . . . , XM −1)とする。M = 1のときは、論理関 数は、F(X0) = X0とF(X0) = N OT (X0)だけであり、明らかに{AN D, OR, N OT }で表される。
いま、任意のM 入力の論理関数が{AN D, OR, N OT }で表されるとする。ここで、任意のM+ 1入力の 論理関数F′(X0, . . . , XM −1, XM)を考える。F′は以下を満たす。
F′(X0, . . . , XM −1, XM) = OR(AN D(F′(X0, . . . , XM −1,0), N OT (XM)), AN D(F′(X0, . . . , XM −1,1), XM))
ここで、F′(X0, . . . , XM −1,0)とF′(X0, . . . , XM −1,1)はM 入力関数と見 なすことができる。仮 定により {AN D, OR, N OT }で表すことができる。F′(X0, . . . , XM −1, XM)は{AN D, OR, N OT }で表すことがで きる。
*1https://ja.wikipedia.org/wiki/MIL 論理記号
2
3 ブール代数
ブール代数(論理代数、Boolean Algebra)とは、論理変数と論理関数（論理演算）を扱う代数のことであ る。AN Dは·（掛け算の記号、論理積）でORは+（足し算の記号:論理和）で、N OT は変数の上に横棒を 入れる(X)。例えば
F = X · Y + Z · W
は、(XとY のN OT)のAN Dをとり、(ZのN OTとW のAN D)とのORをとるという論理演算の結果 がFであることを表している。ブール代数で様々な論理関数を表現するとき、これら以外の基本演算を必要 としないことは前節の完備性の証明でわかる。ブール代数の演算規則を示す。
• AN D
X· 0 = 0, X · 1 = X, X · X = X, X · X = 0, X · Y = Y · X (交換法則) X· (Y · Z) = (X · Y ) · Z (結合法則)
• OR
X+ 0 = X, X + 1 = 1, X + X = X, X + X = 1, X + Y = Y + X (交換法則) X+ (Y + Z) = (X + Y ) + Z (結合法則)
• N OT
X= X
• 結合法則
X· (Y + Z) = X · Y + X · Z X+ Y · Z = (X + Y ) · (X + Z)
• ド・モルガンの法則
X+ Y = X · Y X· Y = X + Y
これらは論理関数の簡単化などに使われる。例としてA· (A + B) = Aを示す。
A· (A + B) = A · A + A · B = A + A · B = A · 1 + A · B = A · (1 + B) = A · 1 = A
ブール代数は代数系と呼ばれる数学的構造の一種である。代数系とは、ある集合X とそこでの算法（演算 規則）Rの族の組のことを指す。ブール代数は、代数系として表すと、({0, 1}, ·, +, )と表される。·, +, は上記の演算規則を満たす。
論理回路の各素子は以下のようにブール代数によって表現でき、一つの論理回路は、ブール代数の集合の要 素の一つに対応する。
• AN D(A, B) = A · B
• OR(A, B) = A + B
• N OT (A) = A
• N OR(A, B) = A + B
• N AN D(A, B) = A · B
• XOR(A, B) = A ⊕ B
• EQ(A, B) = A ⊙ B
3
参考文献
本講義では論理回路入門、坂井修一著、培風館を参考にした。
4
