Discrete Mathematics

7

Boolean Algebra

Boolean algebra is a significant tool for the analysis and design of electronic computers. It has wide applications to switching theory and logical design of electronic circuits.

7.1 DEFINITIONS AND BASIC PROPERTIES

Definition 7.1

A non-empty set B with two binary operations ∨ and ∧, a unary operation ′, and two distinct elements 0 and I is called a Boolean Algebra if the following axioms holds for any elements a, b, c ∈ B:

[B₁]: Commutative Laws

 

a ∨ b = b ∨ a    and    a ∧ b = b ∧ a.

[B₂]: Distributive Laws

 

a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c)    and    a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c).

[B₃]: Identity Laws:

 

a ∨ 0 = a    and    a ∧ I = a.

[B₄]: Complement Laws:

 

a ∨ a′ = I    and    a ∧ a′ = 0.

We shall call 0 as zero element, ...