Boolean Logic Defines

Boolean logic defines an abstract mathematical structure. By a Boolean algebra we mean a set B together with two binary operations +, ∙ on B (known as addition and multiplication respectively) and a unary operation ' on B (called complementary) satisfying the following axioms:

Axiom. 1. The operations are commutative; i.e.,

a + b = b .+ a, a ∙ b = b ∙ a for all a, b ϵ B

Axiom. 2. Each binary operation distributes over the other; i.e.,

a + (b ∙ c) = (a + b) ∙ (a + c)

and a ∙ (b + c) = (a ∙ b) + (a ∙ c) for all a, b, c ϵ B

Axiom. 3. B contains distinct identity elements 0 and 1 (known as zero element and unit element) with respect to the operations +, ∙ respectively; i.e.,

a + 0 = a, a ∙ 1 = a, for every a ϵ B.
Axiom. 4. For each a ϵ B, there exists an element a' ϵ B such that a + a' = 1 and a ∙ a' = 0.

Note:

(i) a' is called the complement of a. (a')' will be denoted by a'' and so on. Very often we shall write a ∙ b as ab.

(ii) The binary operations in the definition need not be written as + and

Instead, we may use other symbols such as ∪, ∩ (known as union and intersection respectively), or, ⋁, ⋀ (known as join and meet) to denote these operations.

(iii) A Boolean algebra is generally denoted by a 6-tuple (B, +, ∙, ', 0, 1) or by (B, +, ∙, ') or, simply by the set B in it.



Examples:

1. Let A be a non-empty set and P(A) be the power set of A. Then P(A) is a Boolean algebra under the usual operations of union, intersection and complementation in P(A). The sets ∅ and A are the zero element and unit element of the Boolean algebra P(A). Observe that if A is an infinite set, then the Boolean algebra P(A) will contain infinite number of elements.

2. Let B be the set of all positive integers which are divisors of 70; i.e., B = {1, 2, 5, 7, 10, 14, 35, 70}. For any a, b ϵ B, let a + b = l.c.m of a, b; a ∙ b = h.c.f. of a, b and a' = ⁷<span style='font-size: 50%'>/₀. Then with the help of elementary properties of l.c.m. and h.c.f. it can be easily verified that (B, +, ∙, ', 1, 70) is a Boolean algebra. Here 1 is the zero element and 70 is the unit element.

We can generalize this example with the help of the following result:

Result:

Let n > 1 be an integer and B be the set of positive integers which are divisors of n. For a, b ϵ B we define a + b = l.c.m of a, b; a ∙ b = h.c.f of a, b and a' = ⁿ/₀. Then (B, +, ∙, ', 1, n) is a Boolean algebra if and only if n is square-free, i.e., n is not divisible by any square integer greater than 1.

Proof:

Using simple properties of integers and of l.c.m. and h.c.f. we can easily show that axioms (1)-(3) given in the definition of a Boolean algebra are satisfied. Now axiom (4) will hold if and only if for any a ϵ B, a and n/a have no common factor, other than 1. This condition is equivalent to n being square-free.

Note.

If n = 50 which is not square-free, B = {1, 2, 5, 10, 25, 50}. Observe that 5' = ⁵<span style='font-size: 50%'>/₅ = 10 and 5 + 5' = 5 + 10 = l.c.m of 5, 10 = 10 ≠ 50. Also, 5 ∙ 5' = 5 ∙ 10 = h.c.f of 5, 10 = 5 ≠ 1. Thus {B, +, ∙, ', 1, 50} is not a Boolean algebra.