Boolean Algebra

This note is to provide a summary of Boolean algebra we covered in the class. I will also mention what to memorize and what you don't have to.

Fundamental Postulates of Boolean Algebra

The basic postulate of Boolean algebra is the existence of a two-valued Boolean variable which can take any of the two distinct values 0 and 1. It is an algebraic system consisting of the set {0,1}, two binary operations OR and AND (denoted by the symbols + and , respectively), and one unary operation called NOT (denoted by an over-bar or a prime x', but for this class we will always use the prime notation for NOT.).

The three operations are defined by three truth tables.

OR Operation: x + y =z

AND Operation: xy=z

NOT Operation: x' = y

Boolean algebra follows the following interesting principle.

Duality Principle

If an algebraic expression of Boolean algebra is valid, its dual of the expression is also valid. The dual expression is obtained by replacing all OR operators with AND, all AND operators with OR, all ones with zeros and all zeros with ones.

Example)

Dual expression of a + (bc) = (a + b)(a + c) is a(b + c) = ab + ac

Dual expression of x + 1 =1 is x · 0 = 0

Basic Properties

Idempotency:

x + x = x

x·x = x

x + 1 = 1

x + 0 = x

x · 0 = 0

x · 1 = x

Commutativity:

x + y = y + x

x · y = y · x

Associativity:

(x + y) + z = x + (y + z)

(x · y) · z = x · (y · z)

Complementation:

x + x' = 1

x · x' = 0

Distributivity:

x · (y + z) = xy + xz

x + yz = (x + y)(x + z)

Theorems:

Consensus theorem:

xy + x'z + yz = xy + x'z

(x + y)(x' + z)(y + z) = (x + y)(x' + z)

DeMorgan's theorem:

(x')' = x

(x + y)' = x'y'

(xy)' = x' + y'

It is recommended that the properties and theorems shown above be memorized for this course. The other theorems shown in the text book should not be memorized. They can be easily derived using the above properties and theorems.