Boolean Algebra

It is an algebraic system introduced by British mathematician G. Boole as a field for logical calculations, and has a wide range of applications, including not only logic and set theory but also computer circuit design. The theory is a two-valued predicate logic, where the set of all logical formulas is F, and for any logical formulas p and q, p=q satisfies p≡q (p and q are equivalent). Consider the three logical operations p∨q (p or q), p∧q (p and q), and ~p (negation of p). In this case, the following formulas hold.

(1) p∨q=q∨p p∧q=q∧p
(2) p∨(q∨r)=(p∨q)∨r
p∧(q∧r)=(p∧q)∧r
(3) (p∨q)∧q=q
(p∧q)∨q=q
(4) (p∨q)∧r
=(p∧r)∨(q∧r)
(p∧q)∨r
=(p∨r)∧(q∨r)
Regardless of the logical expressions p and q,
p∨～p=q∨～q,
p∧～p=q∧～q
So, if p∨～p and p∧～p are expressed as 1 (true) and 0 (false), respectively,
(5) p∨～p=1 p∧～p=0
Let us generalize this. That is, suppose that a set B contains at least two elements 1 and 0, and that for two elements x and y in B, elements of B such as x∨y, x∧y, and x ^* are defined, and that they satisfy the following conditions, where x ^* represents the complement of x.

(1) x∨y=y∨x x∧y=y∧x
(2) x∨(y∨r)=(x∨y)∨r
x ∧ (y ∧ r) = (x ∧ y) ∧ r
(3) (x∨y)∧y=y
(x∧y)∨y=y
(4) (x∨y)∧r
=(x∧r)∨(y∧r)
(x∧y)∨r
=(x∨r)∧(y∨r)
(5) x∨x ^* =1 x∧x ^* =0
In this case, B is called Boolean algebra, and the binary operations x∨y, x∧y and the unary operation x ^* are called Boolean operations. From these conditions (1) to (5), we have De Morgan's laws: (x∨y) ^* =x ^* ∧y ^* ,(x∧y) ^* =x ^* ∨y ^*
In addition, if x≦y means x∧y=x (which is equivalent to x∨y=y), then B is an ordered set, and x∨y (x∧y) is the smallest (largest) element that is greater (smaller) than x and y. In the predicate logic above, for logical expressions p and q, p≦q means p→q (if p, then q).

Next, let P(A) be all subsets of set A. The elements x and y of P(A) are both subsets of A. For these x and y, if x ∨ y, x ∧ y, and x ^* are respectively the union, intersection, and complement of x with respect to A, they become subsets of A and are elements of P(A). If we take A as 1 and the empty set as 0, they are also elements of P(A). These operations also satisfy conditions (1) to (5). Therefore, P(A) is a Boolean algebra with respect to these Boolean operations. In this case, x ≦ y coincides with the inclusion relation xy of the sets.

[Toshio Nishimura]

Source: Shogakukan Encyclopedia Nipponica About Encyclopedia Nipponica Information | Legend

イギリスの数学者G・ブールが論理計算の場として導入した代数系で、論理学、集合論への適用だけでなく、コンピュータの回路設計など、その応用範囲は広い。理論は二値の述語論理で、論理式全体の集合をFとし、任意の論理式pとqについて、p=qとはp≡q（pとqは同値）が成り立つこととする。三つの論理演算p∨q（pあるいはq）、p∧q（pかつq）、～p（pの否定）を考える。このとき次の式が成り立つ。

(1)　p∨q=q∨p　p∧q=q∧p
(2)　p∨(q∨r)=(p∨q)∨r
　　　　p∧(q∧r)=(p∧q)∧r
(3)　(p∨q)∧q=q
　 　　 (p∧q)∨q=q
(4)　(p∨q)∧r
　　　 =(p∧r)∨(q∧r)
　　　　(p∧q)∨r
　　　 =(p∨r)∧(q∨r)
論理式pとqのいかんにかかわらず、
　　 p∨～p=q∨～q,
　 　p∧～p=q∧～q
である。そこで、p∨～p,p∧～pをそれぞれ1（真）と0（偽）で表すと、
(5)　p∨～p=1　p∧～p=0
である。これを一般化する。すなわち、集合Bは少なくとも二つの元1と0を含み、Bの二つの元xとyには、x∨y,x∧y,x^*というBの元が定義されていて、次の条件を満たすとする。ここでx^*はxの補元を表す。

(1)　x∨y=y∨x　x∧y=y∧x
(2)　x∨(y∨r)=(x∨y)∨r
　　　　x∧(y∧r)=(x∧y)∧r
(3)　(x∨y)∧y=y
　　　　(x∧y)∨y=y
(4)　(x∨y)∧r
　　　 =(x∧r)∨(y∧r)
　　　　(x∧y)∨r
　　　 =(x∨r)∧(y∨r)
(5)　x∨x^*=1　x∧x^*=0
このときBをブール代数といい、二項演算x∨y,x∧yと一項演算x^*をブール演算という。この条件(1)～(5)から、ド・モルガンの法則
　　(x∨y)^*=x^*∧y^*,(x∧y)^*=x^*∨y^*
が導かれる。また、x≦yをx∧y=x（これはx∨y=yと同値）のこととすれば、Bは順序集合となり、x∨y(x∧y)は、xとyより大（小）なる最小（最大）の元になる。前の述語論理では、論理式pとqについて、p≦qはp→q（pならばq）のことである。

　次に集合計算について考える。集合Aの部分集合の全体をP(A)とする。P(A)の元x、yはともにAの部分集合である。これらのx、yに対して、x∨y,x∧y,x^*をそれぞれ、xとyの和集合、共通集合、Aに対するxの補集合とすれば、それらはそれぞれAの部分集合となり、P(A)の元である。1としてAを、0として空集合をとれば、それらはまたP(A)の元である。そして、これらの演算はまた条件(1)～(5)を満たす。したがって、P(A)はこれらのブール演算に関してブール代数である。この場合、x≦yは、集合の包含関係xyと一致する。

［西村敏男］

出典　小学館　日本大百科全書(ニッポニカ)日本大百科全書(ニッポニカ)について　情報 | 凡例