Transcript Discrete Mathematics - Lyle School of Engineering

Discrete Mathematics, Part IIIb
CSE 2353
Fall 2007
Margaret H. Dunham
Department of Computer Science and
Engineering
Southern Methodist University
•Some slides provided by Dr. Eric Gossett; Bethel University; St. Paul,
Minnesota
•Some slides are companion slides for Discrete Mathematical
Structures: Theory and Applications by D.S. Malik and M.K. Sen
Outline









Introduction
Sets
Logic & Boolean Algebra
Proof Techniques
Counting Principles
Combinatorics
Relations,Functions
Graphs/Trees
Boolean Functions, Circuits
2
Functions
3
Functions




Let A = {1,2,3,4} and B = {a,
b, c , d} be sets
The arrow diagram in Figure
5.6 represents the relation f
from A into B
Every element of A has
some image in B
An element of A is related to
only one element of B; i.e.,
for each a ∈ A there exists a
unique element b ∈ B such
that f (a) = b
4
Functions



Therefore, f is a function
from A into B
The image of f is the set
Im(f) = {a, b, d}
There is an arrow
originating from each
element of A to an element
of B


D(f) = A
There is only one arrow
from each element of A to
an element of B

f is well defined
5
Functions
6
Functions



Let A = {1,2,3,4} and B = {a, b, c , d}. Let f
: A → B be a function such that the arrow
diagram of f is as shown in Figure 5.10
The arrows from a distinct element of A go
to a distinct element of B. That is, every
element of B has at most one arrow
coming to it.
 If a1, a2 ∈ A and a1 = a2, then f(a1) =
f(a2). Hence, f is one-one.
Each element of B has an arrow coming to
it. That is, each element of B has a
preimage.
 Im(f) = B. Hence, f is onto B. It also
follows that f is a one-to-one
correspondence.
7
Functions




Let A = {1,2,3,4} and
B = {a, b, c , d, e}
f : 1 → a, 2 → a, 3 → a,
4 →a
For this function the
images of distinct
elements of the domain
are not distinct. For
example 1  2, but f(1) = a
= f(2) .
Im(f) = {a}  B. Hence, f is
neither one-one nor onto
B.
8
Functions
9
Functions


Let A = {1,2,3,4}, B = {a, b, c , d, e},and C =
{7,8,9}. Consider the functions f : A → B, g :
B → C as defined by the arrow diagrams in
Figure 5.14.
The arrow diagram in Figure 5.15 describes
the function
h = g ◦ f : A → C.
10
Functions
11
Outline









Introduction
Sets
Logic & Boolean Algebra
Proof Techniques
Counting Principles
Combinatorics
Relations,Functions
Graphs/Trees
Boolean Functions, Circuits
12
Outline









Introduction
Sets
Logic & Boolean Algebra
Proof Techniques
Counting Principles
Combinatorics
Relations,Functions
Graphs/Trees
Boolean Functions, Circuits
13
Mathematical System
14
Two-Element Boolean Algebra
Let B = {0, 1}.
15
16
Boolean Expressions
17
18
Two-Element Boolean Algebra
19
Minterm
20
Disjunctive Normal Form
21
Maxterm
22
Conjunctive Normal Form
23
Logical Gates and Combinatorial
Circuits
24
Logical Gates and Combinatorial
Circuits
25
Logical Gates and Combinatorial
Circuits
26
Logical Gates and Combinatorial
Circuits
27
28
29
30
31
32
33