CS 3204 Operating Systems

Boolean Algebra Boolean Algebras 1

A Boolean algebra is a set B of values together with two operations, usually denoted by
+ and · , defined on the elements in the set and satisfying certain properties:

commutative laws: for all a and b in B, a+b =b+a a ⋅b = b ⋅ a

associative laws: for all a, b and c in B, ( a + b) + c = a + (b + c)

( a ⋅ b ) ⋅ c = a ⋅ (b ⋅ c )
distributive laws: for all a, b and c in B, a + (b ⋅ c) = ( a + b) ⋅ ( a + c)
a ⋅ (b + c) = ( a ⋅ b) + ( a ⋅ c)
identity laws: there exist distinct elements 0 and 1 in B, such that for all a in B,
a+0 = a a ⋅1 = a

complement laws: for each a in B, there exists an element in B, called the complement or
negation of a, such that

a + a =1 a⋅a = 0

Computer Science Dept Va Tech February 2006 Intro Computer Organization ©2006 McQuain & Ribbens

DeMorgan's Laws & More Boolean Algebras 2

DeMorgan's Laws are useful theorems that can be derived from the fundamental
properties of a Boolean algebra.

For all a and b in B, a + b = a ⋅b a ⋅b = a + b

Of course, there’s also a double-negation law: a=a

And there are absorption laws: a+a =a a⋅a = a

For our purposes, the most important Boolean algebra is the set {true, false} together with
the operations AND, OR, and NOT.

Most commonly, the values in the set are represented by 1 and 0, respectively.

Computer Science Dept Va Tech February 2006 Intro Computer Organization ©2006 McQuain & Ribbens

©William D McQuain, January 2005 1

CS 3204 Operating Systems

Example Boolean Algebras 3

Let B = {0, 1} and define operations on the elements of B as follows:

a b a+b a·b a
0 0 0 0 1

1 0 1 0 0

0 1 1 0

1 1 1 1

Then B is a Boolean algebra. The verification of the required properties is tedious but
simple.

Computer Science Dept Va Tech February 2006 Intro Computer Organization ©2006 McQuain & Ribbens

Logic Expressions and Equations Boolean Algebras 4

A logic expression is defined in terms of the three basic Boolean operators and variables
which may take on the values 0 and 1. For example:

z : x 0 ⋅ y 0 + x0 ⋅ y 0

y : ( x1 ⋅ x2 ) + ( x1 ⋅ x2 ⋅ x3 ) + x1 ⋅ ( x2 + x3 )

A logic equation is an assertion that two logic equations are equal, where equal means
that the values of the two expressions are the same for all possible assignments of values
to their variables. For example:

( )(
x 0 ⋅ y 0 + x0 ⋅ y0 = x0 + y0 ⋅ x 0 + y 0 )
Of course, equations may be true or false. What about the one above?

Computer Science Dept Va Tech February 2006 Intro Computer Organization ©2006 McQuain & Ribbens

©William D McQuain, January 2005 2

CS 3204 Operating Systems

Why do they call it "algebra"? Boolean Algebras 5

A Boolean expression can often be usefully transformed by using the theorems and
properties stated earlier:

(x 0 )( ) (
+ y0 ⋅ x 0 + y 0 = x0 + y0 + x 0 + y 0 ) ( )
= x0 ⋅ y0 + x0 ⋅ y0

= x0 ⋅ y0 + x0 ⋅ y0

This is a relatively simple example of a reduction. Try showing the following expressions
are equal:

x0 + ( y0 ⋅ z0 ) = x0 ⋅ y0 + x0 ⋅ z0

Computer Science Dept Va Tech February 2006 Intro Computer Organization ©2006 McQuain & Ribbens

Tautologies, Contradictions & Satisfiables Boolean Algebras 6

A tautology is a Boolean expression that evaluates to true (1) for all possible values of its
variables.

a+a a ⋅b + a ⋅b + a ⋅b + a ⋅b

A contradiction is a Boolean expression that evaluates to false (0) for all possible values
of its variables.

a⋅a

A Boolean expression is satisfiable if there is at least one assignment of values to its

variables for which the expression evaluates to true (1).

a ⋅b + a ⋅b

Computer Science Dept Va Tech February 2006 Intro Computer Organization ©2006 McQuain & Ribbens

©William D McQuain, January 2005 3

CS 3204 Operating Systems

Truth Tables Boolean Algebras 7

A Boolean expression may be analyzed by creating a table that shows the value of the
expression for all possible assignments of values to its variables:

a b a ⋅b a ⋅b a ⋅b + a ⋅b
0 0 0 1 1

1 0 0 0 0

0 1 0 0 0

1 1 1 0 1

Computer Science Dept Va Tech February 2006 Intro Computer Organization ©2006 McQuain & Ribbens

Proving Equations with Truth Tables Boolean Algebras 8

Boolean equations may be proved using truth tables (dull and mechanical):

a +1 = 1 a ⋅b⋅c = a + b + c

a a+1 a b c a ⋅b ⋅c a+b+c
0 1 0 0 0 1 1
1 1 0 0 1 1 1
0 1 0 1 1
0 1 1 1 1
1 0 0 1 1
1 0 1 1 1
1 1 0 1 1
1 1 1 0 0

Computer Science Dept Va Tech February 2006 Intro Computer Organization ©2006 McQuain & Ribbens

©William D McQuain, January 2005 4

CS 3204 Operating Systems

Proving Equations Algebraically Boolean Algebras 9

Boolean equations may be proved using truth tables, which is dull and boring, or using the
algebraic properties:

a +1 = 1 a ⋅b⋅c = a + b + c

a +1 = a + a + a ( ) a ⋅ b ⋅ c = (a ⋅ b ) ⋅ c

= (a + a ) + a = (a ⋅ b ) + c

= a+a = a+b+c
=1

Computer Science Dept Va Tech February 2006 Intro Computer Organization ©2006 McQuain & Ribbens

Sum-of-Products Form Boolean Algebras 10

A Boolean expression is said to be in sum-of-products form if it is expressed as a sum of

terms, each of which is a product of variables and/or their complements:

a ⋅b + a ⋅b

It's relatively easy to see that every Boolean expression can be written in this form.
Why?

The summands in the sum-of-products form are called minterms.

- each minterm contains each variables, or its complement, exactly once
- each minterm is unique, and therefore so is the representation (aside from order)
-

Computer Science Dept Va Tech February 2006 Intro Computer Organization ©2006 McQuain & Ribbens

©William D McQuain, January 2005 5

CS 3204 Operating Systems

Product-of-Sums Form Boolean Algebras 11

A Boolean expression is said to be in product-of-sums form if it is expressed as a product

of terms, each of which is a sum of variables:
(a + b ) ⋅ (a + b )

Every Boolean expression can also be written in this form, as a product of maxterms.

Facts similar to the sum-of-products form can also be asserted here.

The maxterm form can be derived by expressing the complement of the expression in
minterm form, and then complementing.

Computer Science Dept Va Tech February 2006 Intro Computer Organization ©2006 McQuain & Ribbens

Boolean Functions Boolean Algebras 12

A Boolean function takes n inputs from the elements of a Boolean algebra and produces a
single value also an element of that Boolean algebra.

For example, here are all possible 2-input Boolean functions on the set {0, 1}:

A B zero and A B xor or

0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 1 1 1 1
1 0 0 0 1 1 0 0 1 1
1 1 0 1 0 1 0 1 0 1

A B nor eq B' A' nand one

0 0 1 1 1 1 1 1 1 1
0 1 0 0 0 0 1 1 1 1
1 0 0 0 1 1 0 0 1 1
1 1 0 1 0 1 0 1 0 1

Computer Science Dept Va Tech February 2006 Intro Computer Organization ©2006 McQuain & Ribbens

©William D McQuain, January 2005 6

CS 3204 Operating Systems

Universality Boolean Algebras 13

Any Boolean function can be expressed using:

- only AND, OR and NOT
- only AND and NOT
- only OR and NOT
- only AND and XOR
- only NAND
- only NOR

The first assertion should be entirely obvious.

The remaining ones are obvious if you consider how to represent each of the functions in
the first set using only the relevant functions in the relevant set.

Computer Science Dept Va Tech February 2006 Intro Computer Organization ©2006 McQuain & Ribbens

©William D McQuain, January 2005 7