Transcript Set Theory

Boolean Algebras
Lecture 27
Section 5.3
Wed, Mar 7, 2007
Boolean Algebras
In a Boolean algebra, we abstract the basic
properties of sets and logic and make them
the defining properties.
 A Boolean algebra has three operators

+ Addition (binary)
  Multiplication (binary)
 — Complement (unary)

Properties of a Boolean
Algebra

Commutative Laws
a+b=b+a
ab=ba


Associative Laws
(a + b) + c = a + (b + c)
 (a  b)  c = a  (b  c)

Properties of a Boolean
Algebra

Distributive Laws
a + (b  c) = (a + b)  (a + c)
 a  (b + c) = (a  b) + (a  c)


Identity Laws: There exist elements, which
we will label 0 and 1, that have the
properties
a+0=a
a1=a

Properties of a Boolean
Algebra

Complement Laws
a +a = 1
 a a = 0

Set-Theoretic Interpretation
Let B be the power set of a universal set U.
 Interpret + to be ,  to be , and — to be
complementation.
 Then what are the interpretations of 0 and
1?
 Look at the identity and complement laws:

A  0 = A, A  1 = A
 A  Ac = 1, A  Ac = 0

Logic Interpretation
Let B be a collection of statements.
 Interpret + to be ,  to be , and — to be .
 Then what are the interpretations of 0 and
1?
 Look at the identity and complement laws:

p  0 = p, p  1 = p
 p  p = 1, p  p = 0

Binary Interpretation
Let B be the set of all binary strings of
length n.
 Interpret + to be bitwise “or,”  to be bitwise
“and,” and — to be bitwise complement.
 Then what are the interpretations of 0 and
1?
 Look at the identity and complement laws:

x | 0 = x, x & 1 = x
 x | x = 1, x & x = 0

Other Interpretations
Let n be any positive integer that is the
product of distinct primes. (E.g., n = 30.)
 Let B be the set of divisors of n.
 Interpret + to be gcd,  to be lcm, and — to
be division into n.
 For example, if n = 30, then

a + b = gcd(a, b)
 a  b = lcm(a, b)
 a = 30/a.

Other Interpretations
Then what are the interpretations of “0” and
“1”?
 Look at the identity and complement laws.

a + “0” = gcd(a, “0”) = a,
 a  “1” = lcm(a, “1”) = a,
 a +a = gcd(a, 30/a) = “1”,
 a a = lcm(a, 30/a) = “0”.

Connections
How are all of these interpretations
connected?
 Hint: The binary example is the most basic.

Set-Theoretic Interpretation
Let B be the power set of a universal set U.
 Reverse the meaning of + and  :

+ means ,
  means .

Then what are the interpretations of 0 and
1?
 Look at the identity and complement laws:

A  0 = A, A  1 = A
 A  Ac = 1, A  Ac = 0

Duality

One can show that in each of the
preceding examples, if we
Reverse the interpretation of + and 
 Reverse the interpretations of 0 and 1

the result will again be a Boolean algebra.
 This is called the Principle of Duality.
Other Properties
The other properties appearing in Theorem
1.1.1 on p. 14 can be derived as theorems.
 Double Negation Law



The complement ofa is a.
Idempotent Laws
a+a=a
aa=a

Other Properties

Universal Bounds Laws
a+1=1
a0=0


DeMorgan’s Laws
( a  b)  a  b
( a  b)  a  b
Other Properties

Absorption Laws
a + (a  b) = a
 a  (a + b) = a


Complements of 0 and 1
0 = 1
 1 = 0

The Idempotent Laws
Theorem: Let B be a boolean algebra. For
all a  B, a + a = a.
 Proof:


aa=aa+0
= a  a + a a
= a  (a +a)
=a1
= a.
The Idempotent Laws

Prove the other idempotent law
a a = a.
The Laws of Universal
Bounds
Theorem: Let B be a boolean algebra. For
all a  B, a + 1 = 1.
 Proof:


a + 1 = a + (a +a)
= (a + a) +a
= a +a
= 1.
The Laws of Universal
Bounds

Prove the other law of universal bounds:
a 0 = 0.
A Very Handy Lemma
Lemma: Let B be a boolean algebra and let
a, b  B. If a + b = 1 and a  b = 0, then b
=a.
 Proof:

The Lemma Applied
Corollary: Let p and q be propositions. If
p  q = T and p  q = F, then q = p.
 Corollary: Let A and B be sets. If A  B =
U and A  B =, then B = Ac.
 Corollary: Let x and y be ints. If x | y
== 1 and x & y == 0, then y == x.

DeMorgan’s Laws
Theorem: Let B be a boolean algebra. For
all a, b  B, the complement of (a + b)
equalsa b.
 Proof:

We show that (a + b) + (a b) = 1 and that
(a + b)  (a b) = 0.
 It will follow from the Lemma thata b is
the complement of a + b.

DeMorgan’s Laws
(a + b) + (a b) = (a + b + a’).(a + b + b’)
= (1 + b).(1 + a)
= 1.1
= 1.
 (a + b).(a’.b’) = a. a’.b’ + b. a’.b’
= 0.b’ + 0.a’
=0+0
= 0.

DeMorgan’s Laws

Therefore,a b is the complement of a +
b.
The Other DeMorgan’s Law
Prove the law that a +b is the
complement of a  b.
 Prove the law of double negation, that the
complement ofa is a.

Applications
These laws are true for any interpretation
of a Boolean algebra.
 For example, if a and b are integers, then

gcd(a, lcm(a, b)) = a
 lcm(a, gcd(a, b)) = a


If x and y are ints, then
x | (x & y) == x
 x & (x | y) == x
