An introduction to set theory as a discrete structure

This presentation introduces set theory as a basic discrete structure.

1. Spring 2003 CMSC 203 - Discrete Structures 1
… … and now for something and now for something
completely different…completely different…
Set TheorySet Theory
Actually, you will see that logic and Actually, you will see that logic and
set theory are very closely related.set theory are very closely related.

2. Spring 2003 CMSC 203 - Discrete Structures 2
Set TheorySet Theory
•Set: Collection of objects (called Set: Collection of objects (called elementselements))
•aaAA “a is an element of A” “a is an element of A”
“a is a member of A” “a is a member of A”
•aaAA “a is not an element of A” “a is not an element of A”
•A = {aA = {a
11, a, a
22, …, a, …, a
nn} } “A contains a“A contains a
11, …, a, …, a
nn””
•Order of elements is insignificantOrder of elements is insignificant
•It does not matter how often the same It does not matter how often the same
element is listed (repetition doesn’t count).element is listed (repetition doesn’t count).

3. Spring 2003 CMSC 203 - Discrete Structures 3
Set EqualitySet Equality
Sets A and B are equal if and only if they Sets A and B are equal if and only if they
contain exactly the same elements.contain exactly the same elements.
Examples:Examples:
• A = {9, 2, 7, -3}, B = {7, 9, -3, 2} :A = {9, 2, 7, -3}, B = {7, 9, -3, 2} :A = BA = B
• A = {dog, cat, horse}, A = {dog, cat, horse},
B = {cat, horse, squirrel, dog} : B = {cat, horse, squirrel, dog} :A A  B B
• A = {dog, cat, horse}, A = {dog, cat, horse},
B = {cat, horse, dog, dog} : B = {cat, horse, dog, dog} : A = BA = B

4. Spring 2003 CMSC 203 - Discrete Structures 4
Examples for SetsExamples for Sets
““Standard” Sets:Standard” Sets:
•Natural numbers Natural numbers NN = {0, 1, 2, 3, …} = {0, 1, 2, 3, …}
•Integers Integers ZZ = {…, -2, -1, 0, 1, 2, …} = {…, -2, -1, 0, 1, 2, …}
•Positive Integers Positive Integers ZZ
++
= {1, 2, 3, 4, …} = {1, 2, 3, 4, …}
•Real Numbers Real Numbers RR = {47.3, -12, = {47.3, -12, , …}, …}
•Rational Numbers Rational Numbers QQ = {1.5, 2.6, -3.8, 15, …} = {1.5, 2.6, -3.8, 15, …}
(correct definitions will follow)(correct definitions will follow)

5. Spring 2003 CMSC 203 - Discrete Structures 5
Examples for SetsExamples for Sets
•A = A =  “empty set/null set”“empty set/null set”
•A = {z}A = {z} Note: zNote: zA, but z A, but z  {z} {z}
•A = {{b, c}, {c, x, d}}A = {{b, c}, {c, x, d}} set of setsset of sets
•A = {{x, y}} A = {{x, y}} Note: {x, y} Note: {x, y} A, but {x, y} A, but {x, y}  {{x, y}} {{x, y}}
•A = {x | P(x)} A = {x | P(x)} “set of all x such that P(x)”“set of all x such that P(x)”
P(x) is the P(x) is the membership functionmembership function of set A of set A
x (P(x) x (P(x)  x xA)A)
•A = {x | xA = {x | x NN  x > 7} = {8, 9, 10, …}x > 7} = {8, 9, 10, …}
“set builder notation”“set builder notation”

6. Spring 2003 CMSC 203 - Discrete Structures 6
Examples for SetsExamples for Sets
We are now able to define the set of rational We are now able to define the set of rational
numbers Q:numbers Q:
QQ = {a/b | a = {a/b | aZZ  bbZZ
++
}, }, or or
QQ = {a/b | a = {a/b | aZZ  bbZ Z  bb0} 0}
And how about the set of real numbers R?And how about the set of real numbers R?
RR = {r | r is a real number} = {r | r is a real number}
That is the best we can do. It can neither be That is the best we can do. It can neither be
defined by enumeration nor builder function.defined by enumeration nor builder function.

7. Spring 2003 CMSC 203 - Discrete Structures 7
SubsetsSubsets
A A  B B “A is a subset of B” “A is a subset of B”
A A  B if and only if every element of A is also B if and only if every element of A is also
an element of B. an element of B.
We can completely formalize this:We can completely formalize this:
A A  B B  x (xx (xA A xxB)B)
Examples:Examples:
A = {3, 9}, B = {5, 9, 1, 3}, A A = {3, 9}, B = {5, 9, 1, 3}, A  B ? B ?truetrue
A = {3, 3, 3, 9}, B = {5, 9, 1, 3}, A A = {3, 3, 3, 9}, B = {5, 9, 1, 3}, A  B ? B ?
falsefalse
truetrue
A = {1, 2, 3}, B = {2, 3, 4}, A A = {1, 2, 3}, B = {2, 3, 4}, A 
B ?B ?

8. Spring 2003 CMSC 203 - Discrete Structures 8
SubsetsSubsets
Useful rules:Useful rules:
•A = B A = B  (A (A  B) B)  (B (B A) A)
•(A (A  B) B) (B (B  C) C)  A A  C C (see Venn Diagram)(see Venn Diagram)
UU
AA
BB
CC

9. Spring 2003 CMSC 203 - Discrete Structures 9
SubsetsSubsets
Useful rules:Useful rules:
  A for any set A A for any set A
(but (but   A may not hold for any set A) A may not hold for any set A)
•AA  A for any set A A for any set A
Proper subsets:Proper subsets:
A A  B B “A is a proper subset of B”“A is a proper subset of B”
A A  B B  x (xx (xA A  x xB) B)  x (xx (xB B  x xA)A)
oror
A A  B B  x (xx (xA A  x xB) B)  x (xx (xB B xxA) A)

10. Spring 2003 CMSC 203 - Discrete Structures 10
Cardinality of SetsCardinality of Sets
If a set S contains n If a set S contains n distinctdistinct elements, n elements, nNN,,
we call S a we call S a finite setfinite set with with cardinality ncardinality n..
Examples:Examples:
A = {Mercedes, BMW, Porsche}, |A| = 3A = {Mercedes, BMW, Porsche}, |A| = 3
B = {1, {2, 3}, {4, 5}, 6}B = {1, {2, 3}, {4, 5}, 6} |B| = 4|B| = 4
C = C =  |C| = 0|C| = 0
D = { xD = { xN N | x | x  7000 } 7000 } |D| = 7001|D| = 7001
E = { xE = { xN N | x | x  7000 } 7000 } E is infinite!E is infinite!

11. Spring 2003 CMSC 203 - Discrete Structures 11
The Power SetThe Power Set
P(A) P(A) “power set of A” (also written as “power set of A” (also written as 22
AA
))
P(A) = {B | B P(A) = {B | B  A} A} (contains all subsets of A)(contains all subsets of A)
Examples:Examples:
A = {x, y, z}A = {x, y, z}
P(A)P(A)

= {= {, {x}, {y}, {z}, {x, y}, {x, z}, {y, z}, {x, y, z}}, {x}, {y}, {z}, {x, y}, {x, z}, {y, z}, {x, y, z}}
A = A = 
P(A) = {P(A) = {}}
Note: |A| = 0, |P(A)| = 1Note: |A| = 0, |P(A)| = 1

12. Spring 2003 CMSC 203 - Discrete Structures 12
The Power SetThe Power Set
Cardinality of power sets: Cardinality of power sets: | P(A) | = 2| P(A) | = 2
|A||A|
•Imagine each element in A has an “Imagine each element in A has an “onon//offoff” switch” switch
•Each possible switch configuration in A Each possible switch configuration in A
corresponds to one subset of A, thus one element corresponds to one subset of A, thus one element
in P(A)in P(A)
zzzzzzzzzzzzzzzzzz
yyyyyyyyyyyyyyyyyy
xxxxxxxxxxxxxxxxxx
8877665544332211AA
•For 3 elements in A, there are For 3 elements in A, there are
22222 = 8 elements in P(A)2 = 8 elements in P(A)

13. Spring 2003 CMSC 203 - Discrete Structures 13
Cartesian ProductCartesian Product
The The ordered n-tupleordered n-tuple (a (a
11, a, a
22, a, a
33, …, a, …, a
nn) is an ) is an
ordered collectionordered collection of n objects. of n objects.
Two ordered n-tuples (aTwo ordered n-tuples (a
11, a, a
22, a, a
33, …, a, …, a
nn) and ) and
(b(b
11, b, b
22, b, b
33, …, b, …, b
nn) are equal if and only if they ) are equal if and only if they
contain exactly the same elements contain exactly the same elements in the same in the same
orderorder, i.e. a, i.e. a
ii = b = b
ii for 1 for 1  i i  n. n.
The The Cartesian productCartesian product of two sets is defined as: of two sets is defined as:
AAB = {(a, b) | aB = {(a, b) | aA A  b bB}B}

14. Spring 2003 CMSC 203 - Discrete Structures 14
Cartesian ProductCartesian Product
Example:Example:
A = {good, bad}, B = {student, prof}A = {good, bad}, B = {student, prof}
AAB = {B = {
(good, student),(good, student), (good, prof),(good, prof), (bad, student),(bad, student), (bad, prof)(bad, prof)}}
(prof, bad)(prof, bad)}} (student, good),(student, good), (prof, good),(prof, good), (student, bad),(student, bad), BBA = A =
{{
Example:Example: A = {x, y}, B = {a, b, c} A = {x, y}, B = {a, b, c}
AAB = {(x, a), (x, b), (x, c), (y, a), (y, b), (y, c)}B = {(x, a), (x, b), (x, c), (y, a), (y, b), (y, c)}

15. Spring 2003 CMSC 203 - Discrete Structures 15
Cartesian ProductCartesian Product
Note that:Note that:
• AA = = 
• A = A = 
• For non-empty sets A and B: AFor non-empty sets A and B: AB B  A AB B  B BAA
• |A|AB| = |A|B| = |A||B||B|
The Cartesian product of The Cartesian product of two or more setstwo or more sets is is
defined as:defined as:
AA
11AA
22……AA
nn = {(a = {(a
11, a, a
22, …, a, …, a
nn) | a) | a
iiAA
ii for 1 for 1  i i  n} n}

16. Spring 2003 CMSC 203 - Discrete Structures 16
Set OperationsSet Operations
Union: AUnion: AB = {x | xB = {x | xA A  x xB}B}
Example:Example: A = {a, b}, B = {b, c, d} A = {a, b}, B = {b, c, d}
AAB = {a, b, c, d} B = {a, b, c, d}
Intersection: AIntersection: AB = {x | xB = {x | xA A  x xB}B}
Example:Example: A = {a, b}, B = {b, c, d} A = {a, b}, B = {b, c, d}
AAB = {b}B = {b}
Cardinality: |ACardinality: |AB| = |A| + |B| - |AB| = |A| + |B| - |AB|B|

17. Spring 2003 CMSC 203 - Discrete Structures 17
Set OperationsSet Operations
Two sets are called Two sets are called disjointdisjoint if their intersection if their intersection
is empty, that is, they share no elements:is empty, that is, they share no elements:
AAB = B = 
The The differencedifference between two sets A and B between two sets A and B
contains exactly those elements of A that are contains exactly those elements of A that are
not in B:not in B:
A-B = {x | xA-B = {x | xA A  x xB}B}
Example: Example: A = {a, b}, B = {b, c, d}, A-B = {a}A = {a, b}, B = {b, c, d}, A-B = {a}
Cardinality: |A-B| = |A| - |ACardinality: |A-B| = |A| - |AB|B|

18. Spring 2003 CMSC 203 - Discrete Structures 18
Set OperationsSet Operations
The The complementcomplement of a set A contains exactly of a set A contains exactly
those elements under consideration that are not those elements under consideration that are not
in A: denoted Ain A: denoted A
c c
(or as in the text)(or as in the text)
AA
cc
= U-A = U-A
Example: Example: U = U = NN, B = {250, 251, 252, …}, B = {250, 251, 252, …}
BB
cc
= {0, 1, 2, …, 248, 249} = {0, 1, 2, …, 248, 249}
A

19. Spring 2003 CMSC 203 - Discrete Structures 19
Logical EquivalenceLogical Equivalence
Equivalence lawsEquivalence laws
–Identity laws, Identity laws, P P  T T  P, P,
–Domination laws, Domination laws, P P  F F  F, F,
–Idempotent laws, Idempotent laws, P P  P P  P, P,
–Double negation law, Double negation law,  (( P P) )  P P
–Commutative laws, Commutative laws, P P  Q Q  Q Q  P, P,
–Associative laws, Associative laws, P P  (Q (Q  R) R) ( (P P  Q) Q)  R R,,
–Distributive laws, Distributive laws, P P  (Q (Q  R) R) ( (P P  Q) Q)  (P (P  R) R),,
–De Morgan’s laws, De Morgan’s laws,  (P(PQ) Q)  (( P) P)  ( ( Q)Q)
–Law with implicationLaw with implication P P  Q Q   P P  Q Q

20. Spring 2003 CMSC 203 - Discrete Structures 20
Set IdentitySet Identity
Table 1 in Section 1.7 shows many useful equations Table 1 in Section 1.7 shows many useful equations
–Identity laws, Identity laws, AA = A = A, , AAU = AU = A
–Domination laws, Domination laws, AAU = UU = U, , AA = = 
–Idempotent laws, Idempotent laws, AAA = AA = A, , AAAA = = AA
–Complementation law, Complementation law, ((AA
cc
))
cc
= A= A
–Commutative laws, Commutative laws, AAB =B = B BA, AA, AB = BB = BAA
–Associative laws, Associative laws, AA(B(B  C) = (A C) = (AB)B)CC, …, …
–Distributive laws, Distributive laws, AA(B(BC) = (AC) = (AB)B)(A(AC)C), …, …
–De Morgan’s laws, De Morgan’s laws, (A(AB)B)
c c
= = AA
cc
BB
c, c,
(A(AB)B)
c c
= = AA
cc
BB
cc
–Absorption laws,Absorption laws, AA(A(AB) = AB) = A, , AA(A(AB) = AB) = A
–Complement laws,Complement laws,AAAA
cc
= U, A = U, AAA
cc
= = 

21. Spring 2003 CMSC 203 - Discrete Structures 21
Set IdentitySet Identity
How can we prove AHow can we prove A(B(BC) = (AC) = (AB)B)(A(AC)?C)?
Method I:Method I: logical equivalentlogical equivalent
xxAA(B(BC)C)
 xxA A  x x(B(BC)C)
 xxA A  (x (xB B  x xC)C)
 (x(xA A  x xB) B)  (x (xA A  x xC) C) (distributive law)(distributive law)
 xx(A(AB) B)  x x(A(AC)C)
 xx(A(AB)B)(A(AC)C)
Every logical expression can be transformed into an equivalent Every logical expression can be transformed into an equivalent
expression in set theory and vice versa.expression in set theory and vice versa.

22. Spring 2003 CMSC 203 - Discrete Structures 22
Set OperationsSet Operations
Method II: Membership tableMethod II: Membership table
1 means “x is an element of this set”1 means “x is an element of this set”
0 means “x is not an element of this set” 0 means “x is not an element of this set”
11111111111 1 11 1 1
11111111001 1 01 1 0
11111111001 0 11 0 1
11111111001 0 01 0 0
11111111110 1 10 1 1
00001100000 1 00 1 0
00110000000 0 10 0 1
00000000000 0 00 0 0
(A(AB) B) (A(AC)C)AACCAABBAA(B(BC)C)BBCCA B CA B C

23. Spring 2003 CMSC 203 - Discrete Structures 23
… … and the following mathematical and the following mathematical
appetizer is about…appetizer is about…
FunctionsFunctions

24. Spring 2003 CMSC 203 - Discrete Structures 24
FunctionsFunctions
A A functionfunction f from a set A to a set B is an f from a set A to a set B is an
assignmentassignment of of exactly oneexactly one element of B to element of B to eacheach
element of A.element of A.
We writeWe write
f(a) = bf(a) = b
if b is the unique element of B assigned by the if b is the unique element of B assigned by the
function f to the element a of A.function f to the element a of A.
If f is a function from A to B, we writeIf f is a function from A to B, we write
f: Af: ABB
(note: Here, “(note: Here, ““ has nothing to do with if… then)“ has nothing to do with if… then)

25. Spring 2003 CMSC 203 - Discrete Structures 25
FunctionsFunctions
If f:AIf f:AB, we say that A is the B, we say that A is the domaindomain of f and B of f and B
is the is the codomaincodomain of f. of f.
If f(a) = b, we say that b is the If f(a) = b, we say that b is the imageimage of a and a is of a and a is
the the pre-imagepre-image of b. of b.
The The rangerange of f:A of f:AB is the set of all images of B is the set of all images of allall
elements of A.elements of A.
We say that f:AWe say that f:AB B mapsmaps A to B. A to B.

26. Spring 2003 CMSC 203 - Discrete Structures 26
FunctionsFunctions
Let us take a look at the function f:PLet us take a look at the function f:PC withC with
P = {Linda, Max, Kathy, Peter}P = {Linda, Max, Kathy, Peter}
C = {Boston, New York, Hong Kong, Moscow}C = {Boston, New York, Hong Kong, Moscow}
f(Linda) = Moscowf(Linda) = Moscow
f(Max) = Bostonf(Max) = Boston
f(Kathy) = Hong Kongf(Kathy) = Hong Kong
f(Peter) = New Yorkf(Peter) = New York
Here, the range of f is C.Here, the range of f is C.

27. Spring 2003 CMSC 203 - Discrete Structures 27
FunctionsFunctions
Let us re-specify f as follows:Let us re-specify f as follows:
f(Linda) = Moscowf(Linda) = Moscow
f(Max) = Bostonf(Max) = Boston
f(Kathy) = Hong Kongf(Kathy) = Hong Kong
f(Peter) = Bostonf(Peter) = Boston
Is f still a function?Is f still a function?yesyes
{Moscow, Boston, Hong Kong}{Moscow, Boston, Hong Kong}What is its range?What is its range?

28. Spring 2003 CMSC 203 - Discrete Structures 28
FunctionsFunctions
Other ways to represent f:Other ways to represent f:
BostonBostonPeterPeter
Hong Hong
KongKong
KathyKathy
BostonBostonMaxMax
MoscowMoscowLindaLinda
f(x)f(x)xx
LindaLinda
MaxMax
KathyKathy
PeterPeter
BostonBoston
New YorkNew York
Hong KongHong Kong
MoscowMoscow

29. Spring 2003 CMSC 203 - Discrete Structures 29
FunctionsFunctions
If the domain of our function f is large, it is If the domain of our function f is large, it is
convenient to specify f with a convenient to specify f with a formulaformula, e.g.:, e.g.:
f:f:RRRR
f(x) = 2xf(x) = 2x
This leads to:This leads to:
f(1) = 2f(1) = 2
f(3) = 6f(3) = 6
f(-3) = -6f(-3) = -6
……

30. Spring 2003 CMSC 203 - Discrete Structures 30
FunctionsFunctions
Let fLet f
11 and f and f
22 be functions from A to be functions from A to RR..
Then the Then the sumsum and the and the productproduct of f of f
11 and f and f
22 are also are also
functions from A to functions from A to RR defined by: defined by:
(f(f
11 + f + f
22)(x) = f)(x) = f
11(x) + f(x) + f
22(x)(x)
(f(f
11ff
22)(x) = f)(x) = f
11(x) f(x) f
22(x)(x)
Example:Example:
ff
11(x) = 3x, f(x) = 3x, f
22(x) = x + 5(x) = x + 5
(f(f
11 + f + f
22)(x) = f)(x) = f
11(x) + f(x) + f
22(x) = 3x + x + 5 = 4x + 5(x) = 3x + x + 5 = 4x + 5
(f(f
11ff
22)(x) = f)(x) = f
11(x) f(x) f
22(x) = 3x (x + 5) = 3x(x) = 3x (x + 5) = 3x
22
+ 15x + 15x

31. Spring 2003 CMSC 203 - Discrete Structures 31
FunctionsFunctions
We already know that the We already know that the rangerange of a function of a function
f:Af:AB is the set of all images of elements aB is the set of all images of elements aA.A.
If we only regard a If we only regard a subsetsubset S SA, the set of all A, the set of all
images of elements simages of elements sS is called the S is called the imageimage of S. of S.
We denote the image of S by f(S):We denote the image of S by f(S):
f(S) = {f(s) | sf(S) = {f(s) | sS}S}

32. Spring 2003 CMSC 203 - Discrete Structures 32
FunctionsFunctions
Let us look at the following well-known function:Let us look at the following well-known function:
f(Linda) = Moscowf(Linda) = Moscow
f(Max) = Bostonf(Max) = Boston
f(Kathy) = Hong Kongf(Kathy) = Hong Kong
f(Peter) = Bostonf(Peter) = Boston
What is the image of S = {Linda, Max} ?What is the image of S = {Linda, Max} ?
f(S) = {Moscow, Boston}f(S) = {Moscow, Boston}
What is the image of S = {Max, Peter} ?What is the image of S = {Max, Peter} ?
f(S) = {Boston}f(S) = {Boston}

33. Spring 2003 CMSC 203 - Discrete Structures 33
Properties of FunctionsProperties of Functions
A function f:AA function f:AB is said to be B is said to be one-to-oneone-to-one (or (or
injectiveinjective), if and only if), if and only if
x, yx, yA (f(x) = f(y) A (f(x) = f(y)  x = y) x = y)
In other words:In other words: f is one-to-one if and only if it f is one-to-one if and only if it
does not map two distinct elements of A onto the does not map two distinct elements of A onto the
same element of B.same element of B.

34. Spring 2003 CMSC 203 - Discrete Structures 34
Properties of FunctionsProperties of Functions
And again…And again…
f(Linda) = Moscowf(Linda) = Moscow
f(Max) = Bostonf(Max) = Boston
f(Kathy) = Hong Kongf(Kathy) = Hong Kong
f(Peter) = Bostonf(Peter) = Boston
Is f one-to-one?Is f one-to-one?
No, Max and Peter are No, Max and Peter are
mapped onto the same mapped onto the same
element of the image.element of the image.
g(Linda) = Moscowg(Linda) = Moscow
g(Max) = Bostong(Max) = Boston
g(Kathy) = Hong Kongg(Kathy) = Hong Kong
g(Peter) = New Yorkg(Peter) = New York
Is g one-to-one?Is g one-to-one?
Yes, each element is Yes, each element is
assigned a unique assigned a unique
element of the image.element of the image.

35. Spring 2003 CMSC 203 - Discrete Structures 35
Properties of FunctionsProperties of Functions
How can we prove that a function f is one-to-one?How can we prove that a function f is one-to-one?
Whenever you want to prove something, first take Whenever you want to prove something, first take
a look at the relevant definition(s):a look at the relevant definition(s):
x, yx, yA (f(x) = f(y) A (f(x) = f(y)  x = y) x = y)
Example:Example:
f:f:RRRR
f(x) = xf(x) = x
22
Disproof by counterexample:
f(3) = f(-3), but 3 f(3) = f(-3), but 3  -3, so f is not one-to-one. -3, so f is not one-to-one.

36. Spring 2003 CMSC 203 - Discrete Structures 36
Properties of FunctionsProperties of Functions
… … and yet another example:and yet another example:
f:f:RRRR
f(x) = 3xf(x) = 3x
One-to-one: One-to-one: x, yx, yA (f(x) = f(y) A (f(x) = f(y)  x = y) x = y)
To show:To show: f(x) f(x)  f(y) whenever x f(y) whenever x  y ( y (indirect proofindirect proof))
x x  y y
 3x 3x  3y 3y
 f(x) f(x)  f(y), f(y),
so if x so if x  y, then f(x) y, then f(x)  f(y), that is, f is one-to-one. f(y), that is, f is one-to-one.

37. Spring 2003 CMSC 203 - Discrete Structures 37
Properties of FunctionsProperties of Functions
A function f:AA function f:AB with A,B B with A,B  R is called R is called strictly strictly
increasingincreasing, if , if
x,yx,yA (x < y A (x < y  f(x) < f(y)), f(x) < f(y)),
and and strictly decreasingstrictly decreasing, if, if
x,yx,yA (x < y A (x < y  f(x) > f(y)). f(x) > f(y)).
Obviously, a function that is either strictly Obviously, a function that is either strictly
increasing or strictly decreasing is increasing or strictly decreasing is one-to-oneone-to-one..

38. Spring 2003 CMSC 203 - Discrete Structures 38
Properties of FunctionsProperties of Functions
A function f:AA function f:AB is called B is called ontoonto, or , or surjectivesurjective, if , if
and only if for every element band only if for every element bB there is an B there is an
element aelement aA with f(a) = b.A with f(a) = b.
In other words, f is onto if and only if its In other words, f is onto if and only if its rangerange is is
its its entire codomainentire codomain..
A function f: AA function f: AB is a B is a one-to-one correspondenceone-to-one correspondence, ,
or a or a bijectionbijection, if and only if it is both one-to-one , if and only if it is both one-to-one
and onto.and onto.
Obviously, if f is a bijection and A and B are finite Obviously, if f is a bijection and A and B are finite
sets, then |A| = |B|.sets, then |A| = |B|.

39. Spring 2003 CMSC 203 - Discrete Structures 39
Properties of FunctionsProperties of Functions
Examples:Examples:
In the following examples, we use the arrow In the following examples, we use the arrow
representation to illustrate functions f:Arepresentation to illustrate functions f:AB. B.
In each example, the complete sets A and B are In each example, the complete sets A and B are
shown.shown.

40. Spring 2003 CMSC 203 - Discrete Structures 40
Properties of FunctionsProperties of Functions
Is f injective?Is f injective?
No.No.
Is f surjective?Is f surjective?
No.No.
Is f bijective?Is f bijective?
No.No.
LindaLinda
MaxMax
KathyKathy
PeterPeter
BostonBoston
New YorkNew York
Hong KongHong Kong
MoscowMoscow

41. Spring 2003 CMSC 203 - Discrete Structures 41
Properties of FunctionsProperties of Functions
Is f injective?Is f injective?
No.No.
Is f surjective?Is f surjective?
Yes.Yes.
Is f bijective?Is f bijective?
No.No.
LindaLinda
MaxMax
KathyKathy
PeterPeter
BostonBoston
New YorkNew York
Hong KongHong Kong
MoscowMoscow
PaulPaul

42. Spring 2003 CMSC 203 - Discrete Structures 42
Properties of FunctionsProperties of Functions
Is f injective?Is f injective?
Yes.Yes.
Is f surjective?Is f surjective?
No.No.
Is f bijective?Is f bijective?
No.No.
LindaLinda
MaxMax
KathyKathy
PeterPeter
BostonBoston
New YorkNew York
Hong KongHong Kong
MoscowMoscow
LLüübeckbeck

43. Spring 2003 CMSC 203 - Discrete Structures 43
Properties of FunctionsProperties of Functions
Is f injective?Is f injective?
No! f is not evenNo! f is not even
a function!a function!
LindaLinda
MaxMax
KathyKathy
PeterPeter
BostonBoston
New YorkNew York
Hong KongHong Kong
MoscowMoscow
LLüübeckbeck

44. Spring 2003 CMSC 203 - Discrete Structures 44
Properties of FunctionsProperties of Functions
Is f injective?Is f injective?
Yes.Yes.
Is f surjective?Is f surjective?
Yes.Yes.
Is f bijective?Is f bijective?
Yes.Yes.
LindaLinda
MaxMax
KathyKathy
PeterPeter
BostonBoston
New YorkNew York
Hong KongHong Kong
MoscowMoscow
LLüübeckbeckHelenaHelena

45. Spring 2003 CMSC 203 - Discrete Structures 45
InversionInversion
An interesting property of bijections is that An interesting property of bijections is that
they have an they have an inverse functioninverse function..
The The inverse functioninverse function of the bijection f:A of the bijection f:AB is B is
the function fthe function f
-1-1
:B:BA with A with
ff
-1-1
(b) = a whenever f(a) = b. (b) = a whenever f(a) = b.

46. Spring 2003 CMSC 203 - Discrete Structures 46
InversionInversion
Example:Example:
f(Linda) = Moscowf(Linda) = Moscow
f(Max) = Bostonf(Max) = Boston
f(Kathy) = Hong Kongf(Kathy) = Hong Kong
f(Peter) = Lf(Peter) = Lüübeckbeck
f(Helena) = New Yorkf(Helena) = New York
Clearly, f is bijective.Clearly, f is bijective.
The inverse function The inverse function
ff
-1-1
is given by: is given by:
ff
-1-1
(Moscow) = Linda(Moscow) = Linda
ff
-1-1
(Boston) = Max(Boston) = Max
ff
-1-1
(Hong Kong) = Kathy(Hong Kong) = Kathy
ff
-1-1
(L(Lüübeck) = Peterbeck) = Peter
ff
-1-1
(New York) = Helena(New York) = Helena
Inversion is only Inversion is only
possible for bijectionspossible for bijections
(= invertible functions)(= invertible functions)

47. Spring 2003 CMSC 203 - Discrete Structures 47
InversionInversion
LindaLinda
MaxMax
KathyKathy
PeterPeter
BostonBoston
New YorkNew York
Hong KongHong Kong
MoscowMoscow
LLüübeckbeckHelenaHelena
ff
ff
-1-1
ff
-1-1
:C:CP is no P is no
function, because function, because
it is not defined it is not defined
for all elements of for all elements of
C and assigns two C and assigns two
images to the pre-images to the pre-
image New York.image New York.

48. Spring 2003 CMSC 203 - Discrete Structures 48
CompositionComposition
The The compositioncomposition of two functions g:A of two functions g:AB and B and
f:Bf:BC, denoted by fC, denoted by fg, is defined by g, is defined by
(f(fg)(a) = f(g(a))g)(a) = f(g(a))
This means that This means that
• firstfirst, function g is applied to element a, function g is applied to element aA,A,
mapping it onto an element of B, mapping it onto an element of B,
• thenthen, function f is applied to this element of , function f is applied to this element of
B, mapping it onto an element of C. B, mapping it onto an element of C.
• ThereforeTherefore, the composite function maps , the composite function maps
from A to C. from A to C.

49. Spring 2003 CMSC 203 - Discrete Structures 49
CompositionComposition
Example:Example:
f(x) = 7x – 4, g(x) = 3x,f(x) = 7x – 4, g(x) = 3x,
f:f:RRRR, g:, g:RRRR
(f(fg)(5) = f(g(5)) = f(15) = 105 – 4 = 101g)(5) = f(g(5)) = f(15) = 105 – 4 = 101
(f(fg)(x) = f(g(x)) = f(3x) = 21x - 4g)(x) = f(g(x)) = f(3x) = 21x - 4

50. Spring 2003 CMSC 203 - Discrete Structures 50
CompositionComposition
Composition of a function and its inverse:Composition of a function and its inverse:
(f(f
-1-1
f)(x) = ff)(x) = f
-1-1
(f(x)) = x(f(x)) = x
The composition of a function and its inverse The composition of a function and its inverse
is the is the identity functionidentity function i(x) = x. i(x) = x.

51. Spring 2003 CMSC 203 - Discrete Structures 51
GraphsGraphs
TheThe graphgraph of a functionof a function f:Af:AB is the set of B is the set of
ordered pairs {(a, b) | aordered pairs {(a, b) | aA and f(a) = b}.A and f(a) = b}.
The graph is a subset of AThe graph is a subset of AB that can be B that can be
used to visualize f in a two-dimensional used to visualize f in a two-dimensional
coordinate system.coordinate system.

52. Spring 2003 CMSC 203 - Discrete Structures 52
Floor and Ceiling FunctionsFloor and Ceiling Functions
The The floorfloor and and ceilingceiling functions map the real functions map the real
numbers onto the integers (numbers onto the integers (RRZZ).).
The The floorfloor function assigns to r function assigns to rRR the largest the largest
zzZZ with z with z  r, denoted by r, denoted by rr..
Examples:Examples: 2.32.3 = 2, = 2, 22 = 2, = 2, 0.50.5 = 0, = 0, -3.5-3.5 = -4 = -4
The The ceilingceiling function assigns to r function assigns to rRR the smallest the smallest
zzZZ with z with z  r, denoted by r, denoted by rr..
Examples:Examples: 2.32.3 = 3, = 3, 22 = 2, = 2, 0.50.5 = 1, = 1, -3.5-3.5 = -3 = -3

53. Spring 2003 CMSC 203 - Discrete Structures 53
Now, something aboutNow, something about
BooleanAlBooleanAl
gebragebra
(section 10.1)(section 10.1)

54. Spring 2003 CMSC 203 - Discrete Structures 54
Boolean AlgebraBoolean Algebra
Boolean algebra provides the operations and the Boolean algebra provides the operations and the
rules for working with the set rules for working with the set {0, 1}.{0, 1}.
These are the rules that underlie These are the rules that underlie electronic electronic
circuitscircuits, and the methods we will discuss are , and the methods we will discuss are
fundamental to fundamental to VLSI designVLSI design..
We are going to focus on three operations:We are going to focus on three operations:
• Boolean complementation,Boolean complementation,
• Boolean sum, andBoolean sum, and
• Boolean productBoolean product

55. Spring 2003 CMSC 203 - Discrete Structures 55
Boolean OperationsBoolean Operations
The The complementcomplement is denoted by a bar (on the slides, is denoted by a bar (on the slides,
we will use a minus sign). It is defined bywe will use a minus sign). It is defined by
-0 = 1 and -1 = 0.-0 = 1 and -1 = 0.
The The Boolean sumBoolean sum, denoted by + or by OR, has the , denoted by + or by OR, has the
following values:following values:
1 + 1 = 1, 1 + 0 = 1, 0 + 1 = 1, 0 + 0 = 01 + 1 = 1, 1 + 0 = 1, 0 + 1 = 1, 0 + 0 = 0
The The Boolean productBoolean product, denoted by , denoted by  or by AND, has or by AND, has
the following values:the following values:
1 1  1 = 1, 1 1 = 1, 1  0 = 0, 0 0 = 0, 0  1 = 0, 0 1 = 0, 0  0 = 0 0 = 0

56. Spring 2003 CMSC 203 - Discrete Structures 56
Boolean Functions and ExpressionsBoolean Functions and Expressions
Definition:Definition: Let B = {0, 1}. The variable x is called a Let B = {0, 1}. The variable x is called a
Boolean variableBoolean variable if it assumes values only from B. if it assumes values only from B.
A function from BA function from B
nn
, the set {(x, the set {(x
11, x, x
22, …, x, …, x
nn) |x) |x
iiB, B,
1 1  i i  n}, to B is called a n}, to B is called a Boolean function of Boolean function of
degree ndegree n..
Boolean functions can be represented using Boolean functions can be represented using
expressions made up from the variables and expressions made up from the variables and
Boolean operations.Boolean operations.

57. Spring 2003 CMSC 203 - Discrete Structures 57
Boolean Functions and ExpressionsBoolean Functions and Expressions
The The Boolean expressionsBoolean expressions in the variables x in the variables x
11, x, x
22, …, , …,
xx
nn are defined recursively as follows: are defined recursively as follows:
• 0, 1, x0, 1, x
11, x, x
22, …, x, …, x
nn are Boolean expressions. are Boolean expressions.
• If EIf E
11 and E and E
22 are Boolean expressions, then (-E are Boolean expressions, then (-E
11), ),
(E (E
11EE
22), and (E), and (E
11 + E + E
22) are Boolean expressions.) are Boolean expressions.
Each Boolean expression represents a Boolean Each Boolean expression represents a Boolean
function. The values of this function are obtained function. The values of this function are obtained
by substituting 0 and 1 for the variables in the by substituting 0 and 1 for the variables in the
expression.expression.

58. Spring 2003 CMSC 203 - Discrete Structures 58
Boolean Functions and ExpressionsBoolean Functions and Expressions
For example, we can create Boolean expression in For example, we can create Boolean expression in
the variables x, y, and z using the “building blocks”the variables x, y, and z using the “building blocks”
0, 1, x, y, and z, and the construction rules:0, 1, x, y, and z, and the construction rules:
Since x and y are Boolean expressions, so is xy.Since x and y are Boolean expressions, so is xy.
Since z is a Boolean expression, so is (-z).Since z is a Boolean expression, so is (-z).
Since xy and (-z) are expressions, so is xy + (-z).Since xy and (-z) are expressions, so is xy + (-z).
… … and so on…and so on…

59. Spring 2003 CMSC 203 - Discrete Structures 59
Boolean Functions and ExpressionsBoolean Functions and Expressions
Example:Example: Give a Boolean expression for the Give a Boolean expression for the
Boolean function F(x, y) as defined by the following Boolean function F(x, y) as defined by the following
table:table:
111100
000011
001111
000000
F(x, y)F(x, y)yyxx
Possible solution:Possible solution: F(x, y) = (-x) F(x, y) = (-x)yy

60. Spring 2003 CMSC 203 - Discrete Structures 60
Boolean Functions and ExpressionsBoolean Functions and Expressions
Another Example:Another Example:
Possible solution I:Possible solution I:
F(x, y, z) = -(xz + y)F(x, y, z) = -(xz + y)
00
00
11
11
F(x, y, z)F(x, y, z)
11
00
11
00
zz
0000
1100
1100
0000
yyxx
00
00
00
11
11
00
11
00
1111
1111
0011
0011
Possible solution II:Possible solution II:
F(x, y, z) = (-(xz))(-y)F(x, y, z) = (-(xz))(-y)

61. Spring 2003 CMSC 203 - Discrete Structures 61
Boolean Functions and ExpressionsBoolean Functions and Expressions
There is a simple method for deriving a Boolean There is a simple method for deriving a Boolean
expression for a function that is defined by a expression for a function that is defined by a
table. This method is based on table. This method is based on mintermsminterms..
Definition:Definition: A A literal literal is a Boolean variable or its is a Boolean variable or its
complement. A complement. A mintermminterm of the Boolean variables x of the Boolean variables x
11, ,
xx
22, …, x, …, x
nn is a Boolean product y is a Boolean product y
11yy
22…y…y
nn, where y, where y
ii = x = x
ii
or yor y
ii = -x = -x
ii..
Hence, a minterm is a product of n literals, with Hence, a minterm is a product of n literals, with
one literal for each variable.one literal for each variable.

62. Spring 2003 CMSC 203 - Discrete Structures 62
Boolean Functions and ExpressionsBoolean Functions and Expressions
Consider F(x,y,z) again:Consider F(x,y,z) again:
F(x, y, z) = 1 if and F(x, y, z) = 1 if and
only if:only if:
x = y = z = 0 orx = y = z = 0 or
x = y = 0, z = 1 orx = y = 0, z = 1 or
x = 1, y = z = 0x = 1, y = z = 0
Therefore,Therefore,
F(x, y, z) =F(x, y, z) =
(-x)(-y)(-z) +(-x)(-y)(-z) +
(-x)(-y)z +(-x)(-y)z +
x(-y)(-z)x(-y)(-z)
00
00
11
11
F(x, y, z)F(x, y, z)
11
00
11
00
zz
0000
1100
1100
0000
yyxx
00
00
00
11
11
00
11
00
1111
1111
0011
0011

63. Spring 2003 CMSC 203 - Discrete Structures 63
Boolean Functions and ExpressionsBoolean Functions and Expressions
Definition:Definition: The Boolean functions F and G of n The Boolean functions F and G of n
variables are variables are equalequal if and only if F(b if and only if F(b
11, b, b
22, …, b, …, b
nn) = ) =
G(bG(b
11, b, b
22, …, b, …, b
nn) whenever b) whenever b
11, b, b
22, …, b, …, b
nn belong to B. belong to B.
Two different Boolean expressions that represent Two different Boolean expressions that represent
the same function are called the same function are called equivalentequivalent..
For example, the Boolean expressions xy, xy + 0, For example, the Boolean expressions xy, xy + 0,
and xyand xy1 are equivalent.1 are equivalent.

64. Spring 2003 CMSC 203 - Discrete Structures 64
Boolean Functions and ExpressionsBoolean Functions and Expressions
The The complement complement of the Boolean function F is the of the Boolean function F is the
function –F, where –F(bfunction –F, where –F(b
11, b, b
22, …, b, …, b
nn) = ) =
-(F(b-(F(b
11, b, b
22, …, b, …, b
nn)).)).
Let F and G be Boolean functions of degree n. The Let F and G be Boolean functions of degree n. The
Boolean sum F+GBoolean sum F+G and and Boolean product FGBoolean product FG are then are then
defined bydefined by
(F + G)(b(F + G)(b
11, b, b
22, …, b, …, b
nn) = F(b) = F(b
11, b, b
22, …, b, …, b
nn) + G(b) + G(b
11, b, b
22, …, b, …, b
nn))
(FG)(b(FG)(b
11, b, b
22, …, b, …, b
nn) = F(b) = F(b
11, b, b
22, …, b, …, b
nn) G(b) G(b
11, b, b
22, …, b, …, b
nn))

65. Spring 2003 CMSC 203 - Discrete Structures 65
Boolean Functions and ExpressionsBoolean Functions and Expressions
Question:Question: How many different Boolean functions of How many different Boolean functions of
degree 1 are there?degree 1 are there?
Solution:Solution: There are four of them, F There are four of them, F
11, F, F
22, F, F
33, and F, and F
44::
00
11
FF
33
11
00
FF
22
110011
110000
FF
44FF
11xx

66. Spring 2003 CMSC 203 - Discrete Structures 66
Boolean Functions and ExpressionsBoolean Functions and Expressions
Question:Question: How many different Boolean functions of How many different Boolean functions of
degree 2 are there?degree 2 are there?
Solution:Solution: There are 16 of them, F There are 16 of them, F
11, F, F
22, …, F, …, F
1616::
11
00
00
00
FF
22
00
00
00
00
FF
11
001100
110011
001111
000000
FF
33yyxx
11
11
11
00
FF
88
00
11
11
00
FF
77
00
00
00
11
FF
99
00
00
11
00
FF
55
11
11
00
00
FF
44
11
00
11
00
FF
66
00
11
00
11
FF
1111
11
00
00
11
FF
1010
00
11
11
11
FF
1212
11
00
11
11
FF
1414
00
00
11
11
FF
1313
11
11
00
11
FF
1515
11
11
11
11
FF
1616

67. Spring 2003 CMSC 203 - Discrete Structures 67
Boolean Functions and ExpressionsBoolean Functions and Expressions
Question:Question: How many different Boolean functions How many different Boolean functions
of degree n are there?of degree n are there?
Solution:Solution:
There are 2There are 2
nn
different n-tuples of 0s and 1s. different n-tuples of 0s and 1s.
A Boolean function is an assignment of 0 or 1 to A Boolean function is an assignment of 0 or 1 to
each of these 2each of these 2
nn
different n-tuples. different n-tuples.
Therefore, there are Therefore, there are 22
22
nn
different Boolean different Boolean
functions.functions.

68. Spring 2003 CMSC 203 - Discrete Structures 68
DualityDuality
There are useful identities of Boolean expressions There are useful identities of Boolean expressions
that can help us to transform an expression A into that can help us to transform an expression A into
an equivalent expression B an equivalent expression B (see Table 5 on page (see Table 5 on page
705 in the textbook).705 in the textbook).
We can derive additional identities with the help We can derive additional identities with the help
of the of the dualdual of a Boolean expression. of a Boolean expression.
The dual of a Boolean expression is obtained by The dual of a Boolean expression is obtained by
interchanging Boolean sums and Boolean products interchanging Boolean sums and Boolean products
and interchanging 0s and 1s.and interchanging 0s and 1s.

69. Spring 2003 CMSC 203 - Discrete Structures 69
DualityDuality
Examples:Examples:
The dual of The dual of x(y + z)x(y + z) is isx + yz.x + yz.
The dual of The dual of -x-x1 + (-y + z) 1 + (-y + z) isis(-x + 0)((-y)z).(-x + 0)((-y)z).
The The dual of a Boolean function Fdual of a Boolean function F represented by represented by
a Boolean expression is the function represented a Boolean expression is the function represented
by the dual of this expression.by the dual of this expression.
This dual function, denoted by FThis dual function, denoted by F
dd
, , does not dependdoes not depend
on the particular Boolean expression used to on the particular Boolean expression used to
represent F.represent F.

70. Spring 2003 CMSC 203 - Discrete Structures 70
DualityDuality
Therefore, an identity between functions Therefore, an identity between functions
represented by Boolean expressions represented by Boolean expressions remains validremains valid
when the duals of both sides of the identity are when the duals of both sides of the identity are
taken.taken.
We can use this fact, called the We can use this fact, called the duality principleduality principle, ,
to derive new identities.to derive new identities.
For example, consider the absorption law For example, consider the absorption law
x(x + y) = xx(x + y) = x..
By taking the duals of both sides of this identity, By taking the duals of both sides of this identity,
we obtain the equation we obtain the equation x + xy = xx + xy = x, which is also an , which is also an
identity (and also called an absorption law).identity (and also called an absorption law).

71. Spring 2003 CMSC 203 - Discrete Structures 71
Definition of a Boolean AlgebraDefinition of a Boolean Algebra
All the properties of Boolean functions and All the properties of Boolean functions and
expressions that we have discovered also apply to expressions that we have discovered also apply to
other mathematical structuresother mathematical structures such as such as
propositions and sets and the operations defined propositions and sets and the operations defined
on them.on them.
If we can show that a particular structure is a If we can show that a particular structure is a
Boolean algebra, then we know that all results Boolean algebra, then we know that all results
established about Boolean algebras apply to this established about Boolean algebras apply to this
structure.structure.
For this purpose, we need an For this purpose, we need an abstract definitionabstract definition
of a Boolean algebra.of a Boolean algebra.

72. Spring 2003 CMSC 203 - Discrete Structures 72
Definition of a Boolean AlgebraDefinition of a Boolean Algebra
Definition:Definition: A Boolean algebra is a set B with two A Boolean algebra is a set B with two
binary operations binary operations  and and , elements 0 and 1, and a , elements 0 and 1, and a
unary operation – such that the following unary operation – such that the following
properties hold for all x, y, and z in B:properties hold for all x, y, and z in B:
x x  0 = x and x 0 = x and x  1 = x 1 = x (identity laws)(identity laws)
x x  (-x) = 1 and x (-x) = 1 and x  (-x) = 0 (-x) = 0 (domination laws)(domination laws)
(x (x  y) y)  z = x z = x  (y (y  z) and z) and
(x (x  y) y)  z = x z = x  (y (y  z) and z) and (associative laws)(associative laws)
x x  y = y y = y  x and x x and x  y = y y = y  x x (commutative laws)(commutative laws)
x x  (y (y  z) = (x z) = (x  y) y)  (x (x  z) and z) and
x x  (y (y  z) = (x z) = (x  y) y)  (x (x  z) z) (distributive laws)(distributive laws)

73. Spring 2003 CMSC 203 - Discrete Structures 73
Logic GatesLogic Gates
Electronic circuits consist of so-called gates.Electronic circuits consist of so-called gates.
There are three basic types of gates:There are three basic types of gates:
xx
yy
x+yx+y
OR gateOR gate
AND gateAND gate
xx
yy
xyxy
xx -x-x
inverterinverter

74. Spring 2003 CMSC 203 - Discrete Structures 74
Logic GatesLogic Gates
Example:Example: How can we build a circuit that computes How can we build a circuit that computes
the function xy + (-x)y ?the function xy + (-x)y ?
xy + (-x)yxy + (-x)y
xx
yy
xyxy
xx -x-x
yy
(-x)y(-x)y

75. Spring 2003 CMSC 203 - Discrete Structures 75
Logic, Sets, and Boolean AlgebraLogic, Sets, and Boolean Algebra
LogicLogic SetSet Boolean AlgebraBoolean Algebra
FalseFalse  00
TrueTrue UU 11
AAB B AABB AABB
AABB AABB A+BA+B
AA AA
CC
Compare the equivalence laws of themCompare the equivalence laws of them
A