Transcript Chapter 7-1 - Computer Science

Boolean Algebra and Computer Logic
Mathematical Structures
for Computer Science
Chapter 7.1
Copyright © 2006 W.H. Freeman & Co.
MSCS Slides
Boolean Algebra Structure
Models or Abstractions

We frequently use models or abstractions to capture
properties that may be common to different instances
or applications of the models.


Section 7.1
For example, graphs and trees are abstractions of many
real-world problems. When we reason about a graph
structure we are able to prove theorems and develop
techniques that can be applied to a variety of problems.
Mathematical structures—abstract sets of objects,
together with operations on or relationships among
those objects that obey certain rules—are often used
as models that express the similarities between
different instances.
Boolean Algebra Structure
1
Definition and Properties
A Boolean algebra is a set B on which are defined two
binary operations and and one unary operation and in
which there are two distinct elements 0 and 1 such that the
following properties hold for all x, y, z  B:
x + y = y + x (commutative properties)
(x + y) + z = x + (y + z) (associative properties)
x + (y * z) = (x + y) * (x + z) (distributive properties)
x + 0 = x (identity properties)
x + x = 1 (complement properties)
And
x * y = y * x (commutative properties)
(x* y) * z = x * (y * z) (associative properties)
x * (y + z) = (x * y) + (x * z) (distributive properties)
x * 1 = x (identity properties)
x * x = 0 (complement properties)
Section 7.1
Boolean Algebra Structure
2
Definition and Properties




Section 7.1
The formalization of a Boolean algebra structure
helps us focus on the essential features common to all
examples of Boolean algebras, and we can use these
features—these facts from the definition of a Boolean
algebra—to prove other facts about Boolean algebras.
We denote a Boolean algebra by [B, +, , , 0, 1].
Using the basic definition of Boolean algebra it is
possible to prove other properties.
Boolean algebra: forms the basis for electronics today.
Boolean Algebra Structure
3
Definition and Properties

For example, The idempotent property
x+x=x
holds in any Boolean algebra because:



Section 7.1
x + x = (x + x)  1
= (x + x)  (x + x)
= x + (x  x)
=x+0
=x
// identity property
// definition of x + x
// distributive property
// complement property for 
// identity property
Ordinary arithmetic is not a Boolean algebra because
the property x + x = x does not hold for ordinary
numbers and ordinary addition unless x is zero.
The idempotent property also holds for  : x  x
Boolean Algebra Structure
4
Definition and Properties

Hints for proving Boolean algebra equalities:




Section 7.1
Usually the best approach is to start with the more
complicated expression and try to show that it reduces
to the simpler expression.
Think of adding some form of 0 (like x  x ) or
multiplying by some form of 1 (like x + x ).
Remember the distributive property of addition over
multiplication—easy to forget because it doesn’t look
like arithmetic.
Remember the idempotent properties x + x = x and x 
x = x.
Boolean Algebra Structure
5
Definition and Properties

For x an element of a Boolean algebra B, the element
x is called the complement of x. The complement of
x satisfies:
x + x = l and x  x = 0

THEOREM ON THE UNIQUENESS OF
COMPLEMENTS
For any x in a Boolean algebra, if an element x1 exists
such that x + x1 = 1 and x  x1 = 0, then x1 = x.
Section 7.1
Boolean Algebra Structure
6
Isomorphic Boolean Algebras



Section 7.1
Two instances of a structure are isomorphic if there is
a bijection (called an isomorphism) that maps the
elements of one instance onto the elements of the
other so that important properties are preserved.
If two instances of a structure are isomorphic, each is
a mirror image of the other, with the elements simply
relabeled.
The two instances are essentially the same. Therefore,
we can use the idea of isomorphism to classify
instances of a structure, lumping together those that
are isomorphic.
Boolean Algebra Structure
7
Isomorphic Boolean Algebras






Section 7.1
Suppose we have two Boolean algebras,
[B, +, , , 0, 1] and [b, &, *, , φ, 1].
If x is in B, x is the result of performing on x the
unary operation defined in B.
If z is an element of b, z is the result of performing on
z the unary operation defined in b.
To prove isomorphism, we need a bijection f from B
onto b.
Then f must preserve in b the effects of the various
operations in B.
There are three operations, so we use three equations
to express these preservations.
Boolean Algebra Structure
8
Isomorphic Boolean Algebras
DEFINITION: ISOMORPHISM FOR
BOOLEAN ALGEBRAS
Let [B, +, , , 0, 1] and [b, &, *, ′, ϕ, 1 ] be Boolean
algebras. A function B  b is an isomorphism from
[B, +, , , 0, 1] to [b, &, *, , ϕ, 1 ] if:
1.
2.
3.
4.
Section 7.1
f is a bijection
f (x + y) = f (x) & f (y)
f (x . y) = f (x) * f (y)
f (x′) = ( f (x))
Boolean Algebra Structure
9
Isomorphic Boolean Algebras


THEOREM ON FINITE BOOLEAN ALGEBRAS
Let B be any Boolean algebra with n elements. Then n
= 2m for some m, and B is isomorphic to ({1, 2, ... ,
m}).
The theorem above gives us two pieces of
information:


Section 7.1
The number of elements in a finite Boolean algebra
must be a power of 2.
Finite Boolean algebras that are power sets are—in our
lumping together of isomorphic things—really the only
kinds of finite Boolean algebras.
Boolean Algebra Structure
10