Transcript Document

DISCRETE COMPUTATIONAL
STRUCTURES
CS 23022
Fall 2005
CS 23022 OUTLINE
1.
2.
3.
4.
5.
Sets
Logic
Proof Techniques
Algorithms
Integers & Induction
6. Relations & Posets
7. Functions
8. Boolean Algebra &
Combinatorial Circuits
9.
10.
11.
12.
13.
14.
15.
16.
17.
Matrices & Closures
Congruences
Counting Principles
Discrete Probability
Recurrence Relations
Algorithm Complexity
Graph Theory
Trees & Networks
Grammars & Languages
Learning Objectives
 Learn about relations and their basic
properties
 Explore equivalence relations
 Become aware of closures
 Learn about posets
 Explore how relations are used in the design
of relational databases
Relations
 Relations are a natural way to associate
objects of various sets
Relations
 R can be described in
 Roster form
 Set-builder form
Relations
 Arrow Diagram
 Write the elements of A in one column
 Write the elements B in another column
 Draw an arrow from an element, a, of A to an element,
b, of B, if (a ,b)  R
 Here, A = {2,3,5} and B = {7,10,12,30} and R from A
into B is defined as follows: For all a  A and b  B,
a R b if and only if a divides b
 The symbol → (called an arrow) represents the
relation R
Relations
Relations
 Directed Graph
 Let R be a relation on a finite set A
 Let A = {a, b, c, d}
 R= {(a.a), (a,b), (b,b), (b,c), (b,a), (b,d), (c,d)}
 Describe R pictorially as follows:
 For each element of A , draw a small or big dot and
label the dot by the corresponding element of A
 Draw an arrow from a dot labeled a , to another dot
labeled, b , if a R b .
 Resulting pictorial representation of R is called the
directed graph representation of the relation R
Relations
Relations
 Directed graph (Digraph)
representation of R
 Each dot is called a vertex
 If a vertex is labeled, a, then it is also called
vertex a
 An arc from a vertex labeled a, to another
vertex, b is called a directed edge, or directed
arc from a to b
 The ordered pair (A , R) is a directed graph,
or digraph, of the relation R, where each
element of A is called a vertex of the
digraph
Relations
 Directed graph (Digraph)
representation of R (Continued)
 For vertices a and b , if a R b, a is adjacent
to b and b is adjacent from a
 Because (a, a)  R, an arc from a to a is
drawn; because (a, b)  R, an arc is drawn
from a to b. Similarly, arcs are drawn from b
to b, b to c , b to a, b to d, and c to d
 For an element a  A such that (a, a)  R, a
directed edge is drawn from a to a. Such a
directed edge is called a loop at vertex a
Relations
 Directed graph (Digraph)
representation of R (Continued)
 Position of each vertex is not important
 In the digraph of a relation R, there is a
directed edge or arc from a vertex a to a
vertex b if and only if a R b
Relations
 Domain and Range of the Relation
 Let R be a relation from a set A into a set B.
Then R ⊆ A x B. The elements of the relation
R tell which element of A is R-related to which
element of B
Relations
Relations
Relations
Relations
Let A = {1, 2, 3, 4} and B = {p, q, r}. Let R = {(1, q), (2, r
), (3, q), (4, p)}. Then R−1 = {(q, 1), (r , 2), (q, 3), (p,
4)}
To find R−1, just reverse the directions of the arrows
D(R) = {1, 2, 3, 4} = Im(R−1), Im(R) = {p, q, r} = D(R−1)
Relations
Relations
Relations
 Constructing New Relations from
Existing Relations
Relations
If a R b
and
b S c , then a T c requires that D(S)  Q and Im(R)  Q
Relations
Example:
Consider the relations R and S as given in
Figure 3.7.
The composition S ◦ R is given by Figure
3.8.
Relations
Relations
Relations
Relations
Relations
Relations
Relations
Example 3.1.26 continued
Relations
Relations
Example 3.1.27 continued
Relations
Relations
Example 3.1.31 continued
Relations
Relations
Example 3.1.32 continued
Relations
Relations
Relations
 Consider the relation R = {(1,
1), (2, 2), (3, 3), (4, 4), (5, 5),
(1, 4), (4, 1), (2, 3), (3, 2)} on
the set S = {1, 2, 3, 4, 5}.
 The digraph is divided into
three distinct blocks. From
these blocks the subsets {1,
4}, {2, 3}, and {5} are formed.
These subsets are pairwise
disjoint, and their union is S.
 A partition of a nonempty set
S is a division of S into
nonintersecting nonempty
subsets.
Relations
Relations
 Example: Let A denote the set
of the lowercase English
alphabet. Let B be the set of
lowercase consonants and C
be the set of lowercase
vowels. Then B and C are
nonempty, B ∩ C = , and A =
B ∪ C. Thus, {B, C} is a
partition of A.
 Let A be a set and let {A1, A2,
A3, A4, A5} be a partition of A.
Corresponding to this partition,
a Venn diagram, can be
drawn, Figure 3.13
Relations
Relations – Equivalence Classes Example
Consider the equivalence relation discussed earlier, congruence modulo m
To makes things specific, consider m=3. Then for any two integers, n and t, the relation n R t
exists iff 3 divides n – t.
The equivalence class [0] of 0 is: [0] = …,-6,-3,0,3,6,9,12… 
This is the set of all values of n where 3|n – 0, i.e n R 0, similarly
The equivalence class [1] of 1is: [1] = …,-8,-5,-2,1,4,7,10… 
This is the set of all values of n where 3|n – 1, i.e n R 1, similarly
The equivalence class [2] of 2is: [2] = …,-7,-4,-1,2,5,8,11… 
This is the set of all values of n where 3|n – 2, i.e n R 2
It can be shown that Z = [0]  [1]  [2] and P = {[0], [1], [2]} is a partition of Z
Aside :
[0] represents all elements n of Z where n/3 has a remainder = 0
[1] represents all elements n of Z where n/3 has a remainder = 1
[2] represents all elements n of Z where n/3 has a remainder = 2
Relations
Relations
Relations
Relations
Relations
 Let A = {a, b, c , d, e , f , g , h, i, j
}. Let R be a relation on A such
that the digraph of R is as
shown in Figure 3.14.
 Then a, b, c , d, e , f , c , g is a
directed walk in R as a R b,b R
c,c R d,d R e, e R f , f R c, c R
g. Similarly, a, b, c , g is also a
directed walk in R. In the walk
a, b, c , d, e , f , c , g , the
internal vertices are b, c , d, e , f
, and c , which are not distinct
as c repeats.
 this walk is not a path. In the
walk a, b, c , g , the internal
vertices are b and c , which are
distinct. Therefore, the walk a,
b, c, g is a path.
Relations
Partially Ordered Sets
Partially Ordered Sets
Partially Ordered Sets
Partially Ordered Sets
Partially Ordered Sets
Partially Ordered Sets
Partially Ordered Sets
brown R green
garage R grate
partial R partially
because brown  green (r = m = n)
because garag  grate
(r = m < n)
because partial = partial and m > n
Partially Ordered Sets
 Digraphs of Posets
 Because any partial order is also a
relation, a digraph representation of
partial order may be given.
 Example: On the set S = {a, b, c},
consider the relation
R
= {(a, a), (b, b), (c , c ), (a, b)}.
 From the directed graph it follows that
the given relation is reflexive and
transitive.
 This relation is also antisymmetric
because there is a directed edge from
a to b, but there is no directed edge
from b to a. Again, in the graph there
are two distinct vertices a and c such
that there are no directed edges from a
to c and from c to a.
Partially Ordered Sets
 Digraphs of Posets
 Let S = {1, 2, 3, 4,
6, 12}. Consider
the divisibility
relation on S,
which is a partial
order
 A digraph of this
poset is as shown
in Figure 3.20
Partially Ordered Sets
Partially Ordered Sets
 Closed Path
 On the set S = {a, b, c }
consider the relation
R = {(a, a), (b, b), (c , c ),
(a, b), (b, c ), (c , a)}
 The digraph of this relation
is given in Figure 3.21
 In this digraph, a, b, c , a
form a closed path. Hence,
the given relation is not a
partial order relation
Partially Ordered Sets
Partially Ordered Sets
Consider the poset (S,≤) where
S = {2,4,5,10,15,20} and the partial order ≤ is
the divisibility relation.
Note: a covers b in the divisibility relation iff
a / b = p , where p is prime.
Partially Ordered Sets
 Hasse Diagram
 Let S = {1, 2, 3}. Then
P(S) = {, {1}, {2}, {3}, {1,
2}, {2, 3}, {1, 3}, S}
 Now (P(S),≤) is a poset,
where ≤ denotes the set
inclusion relation. The
poset diagram of
(P(S),≤) is shown in
Figure 3.22
Partially Ordered Sets
Partially Ordered Sets
Hasse Diagram
Let S = {1, 2, 3}. Then
P(S) = {, {1}, {2}, {3}, {1,
2}, {2, 3}, {1, 3}, S}
(P(S),≤) is a poset, where
≤ denotes the set
inclusion relation
Draw the digraph of this
inclusion relation (see
Figure 3.23). Place the
vertex A above vertex B if
B ⊂ A. Now follow steps
(2), (3), and (4)
Partially Ordered Sets
Partially Ordered Sets
 Hasse Diagram
 Consider the poset (S,≤),
where S = {2, 4, 5, 10, 15, 20}
and the partial order ≤ is the
divisibility relation
 In this poset, there is no
element b ∈ S such that b  5
and b divides 5. (That is, 5 is
not divisible by any other
element of S except 5).
Hence, 5 is a minimal
element. Similarly, 2 is a
minimal element
Partially Ordered Sets
Hasse Diagram
10 is not a minimal element
because 2 ∈ S and 2 divides
10. That is, there exists an
element b ∈ S such that b < 10.
Similarly, 4, 15, and 20 are not
minimal elements
2 and 5 are the only minimal
elements of this poset. Notice
that 2 does not divide 5.
Therefore, it is not true that 2 ≤
b, for all b ∈ S, and so 2 is not
a least element in (S,≤).
Similarly, 5 is not a least
element. This poset has no
least element
Figure 3.24
Partially Ordered Sets
 Hasse Diagram
 There is no element b ∈ S
such that b 15, b > 15, and
15 divides b. That is, there is
no element b ∈ S such that 15
< b. Thus, 15 is a maximal
element. Similarly, 20 is a
maximal element.
 10 is not a maximal element
because 20 ∈ S and 10
divides 20. That is, there
exists an element b ∈ S such
that 10 < b. Similarly, 4 is not a
maximal element.
Partially Ordered Sets
Figure 3.24
 Hasse Diagram
 20 and 15 are the only
maximal elements of
this poset
 10 does not divide 15,
hence it is not true that
b ≤ 15, for all b ∈ S,
and so 15 is not a
greatest element in
(S,≤)
 This poset has no
greatest element
Partially Ordered Sets
Partially Ordered Sets – Topological Ordering
Example: Consider a poset ({1,2,4,5,12,20},|) and it’s Hasse diagram.
12
A topological ordering of the given poset is a linear
ordering which preserves the partial ordering.
20
This is an example : 1 5  2  4  20  12.
4
Other valid linear orderings swap order of 5 and 2
or 12 and 20.
5
2
1
1 5  2  4  20  12
1 2  5  4  20  12
1 5  2  4  12  20
1 2  5  4  12  20
An algorithm for obtaining a topological ordering of P =(A,R) might be1)remove a
minimal element from A; 2)output the element 3) repeat 1 and 2 until A = 
Partially Ordered Sets
Partially Ordered Sets
Partially Ordered Sets
Partially Ordered Sets
Partially Ordered Sets
Partially Ordered Sets
Partially Ordered Sets
Partially Ordered Sets
Non-distributive Lattice
Note that
a ∧ (b ∨ c ) = a ∧ 1 = a
and
0 = 0 ∨ 0 = (a ∧ b) ∨ (a ∧ c )
Now, a ≠ 0 so this is not a distributive
lattice
Partially Ordered Sets
Partially Ordered Sets
Complement
Let D30 denote the set of all
positive divisors of 30. Then D30
= {1, 2, 3, 5, 6, 10, 15, 30}.
(D30,≤) is a poset where a ≤ b if
and only if a divides b (≤ is the
divisibility relation)
D30,≤) is a poset where a ≤ b if
and only if a divides b (≤ is the
divisibility relation). Because 1
divides all elements of D30, it
follows that 1 ≤ m, for all m ∈
D30. Therefore, 1 is the least
element of this poset.
Partially Ordered Sets
Complement
Let a, b ∈ D30. Let d = gcd{a,
b} and m = lcm{a, b}. Now d |
a and d | b. Hence, d ≤ a and
d ≤ b.
This shows that d is a lower
bound of {a, b}. Let c ∈ D30
and c ≤ a, c ≤ b.
This shows that d is a lower
bound of {a, b}. Let c ∈ D30
and c ≤ a, c ≤ b. Then, c | a
and c | b and because d =
gcd{a, b}, it follows that c | d,
so c ≤ d. Thus, d = glb{a, b}.
Partially Ordered Sets
 Complement
 Because all the positive
divisors of a, b are also
divisors of 30, d ∈ D30,
so d = a ∧ b
 It can be shown that m
∈ D30 and m = a ∨ b
 Hence, (D30,≤) is a
lattice with the least
element integer 1 and
the greatest element 30
Partially Ordered Sets
Complement
For any element a ∈ D30,
(30/a) ∈ D30
Using the properties of
gcd and lcm, it can be
shown that a ∧ (30/a) = 1
and a ∨ (30/a) = 30
10 ∧ (30/10) = gcd{10, 3}
= 1 and 10 ∨ (30/10) =
lcm{10, 3} = 30
Hence, 3 is a complement
of 10 in this lattice
Partially Ordered Sets
Application: Relational Database
A database is a shared and integrated
computer structure that stores
End-user data; i.e., raw facts that are of interest
to the end user;
Metadata, i.e., data about data through which
data are integrated
A database can be thought of as a well-organized
electronic file cabinet whose contents are
managed by software known as a database
management system; that is, a collection of
programs to manage the data and control the
accessibility of the data
Application: Relational Database
 In a relational database system,
tables are considered as relations
 A table is an n-ary relation, where n is
the number of columns in the tables
 The headings of the columns of a table
are called attributes, or fields, and
each row is called a record
 The domain of a field is the set of all
(possible) elements in that column
Application: Relational Database
 Each entry in the ID column uniquely
identifies the row containing that ID
 Such a field is called a primary key
 Sometimes, a primary key may consist of
more than one field
Application: Relational Database
 Structured Query Language (SQL)
 Information from a database is retrieved via a
query, which is a request to the database for
some information
 A relational database management system
provides a standard language, called
structured query language (SQL)
 A relational database management system
provides a standard language, called
structured query language (SQL)
Application: Relational Database
Structured Query Language (SQL)
An SQL contains commands to create tables, insert
data into tables, update tables, delete tables, etc.
Once the tables are created, commands can be used
to manipulate data into those tables.
The most commonly used command for this purpose
is the select command. The select command allows
the user to do the following:
Specify what information is to be retrieved and from which
tables.
Specify conditions to retrieve the data in a specific form.
Specify how the retrieved data are to be displayed.
CSE 2353 OUTLINE
1.
2.
3.
4.
5.
Sets
Logic
Proof Techniques
Integers and Induction
Relations and Posets
6.Functions
7. Counting Principles
8. Boolean Algebra
Learning Objectives
 Learn about functions
 Explore various properties of functions
 Learn about sequences and strings
 Become familiar with the
representation of strings in computer
memory
 Learn about binary operations
Functions
Functions
Functions
Every function is a relation
Therefore, functions on
finite sets can be described
by arrow diagrams. In the
case of functions, the
arrow diagram may be
drawn slightly differently.
If f : A → B is a function
from a finite set A into a
finite set B, then in the
arrow diagram, the
elements of A are enclosed
in ellipses rather than
individual boxes.
Functions
 To determine from its arrow diagram
whether a relation f from a set A into
a set B is a function, two things are
checked:
1) Check to see if there is an arrow from
each element of A to an element of B
 This would ensure that the domain of f is the
set A, i.e., D(f) = A
2) Check to see that there is only one arrow
from each element of A to an element of
B
 This would ensure that f is well defined
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
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
Functions
 The arrow diagram in
Figure 5.7 represents
the relation g from A into
B
 Every element of A has
some image in B
 D(g ) = A
 For each a ∈ A, there
exists a unique element
b ∈ B such that g(a) = b
 g is a function from A into
B
Functions
 The image of g is
Im(g) = {a, b, c ,
d} = B
 There is only one
arrow from each
element of A to
an element of B
 g is well defined
Functions
 Let h be the relation described by
the arrow diagram in Figure 5.8
 Every element of A has some
image in B; i.e., there is an arrow
originating from each element of A
to an element of B. Therefore,
 D(h) = A
 However,element 1 has two
images in B; i.e., there are two
arrows originating from 1, one
going to a and another going to b,
so h is not well defined. Thus, the
first condition of Definition 5.1.1 is
satisfied,but the second one is not.
 Therefore, h is not a function
Functions
 The arrow diagram in
Figure 5.9 represents a
relation from A into B
 Not every element of A
has an image in B. For
example, the element 4
has no image in B. In other
words, there is no arrow
originating from 4
 Therefore, 4  D(k), so
D(k)  A
 This implies that k is not a
function from A into B
Functions
 Numeric Functions
 If the domain and the range of a function
are numbers, then the function is typically
defined by means of an algebraic formula
 Such functions are called numeric
functions
 Numeric functions can also be defined in
such a way so that different expressions
are used to find the image of an element
Functions
Functions
One-to-One, Onto and One-to-One Correspondence
Functions
Example 5.1.16
 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.
Functions
Example 5.1.18
 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.
Functions
Let A = {1,2,3,4} and
B = {a, b, c , d, e}
f : 1 → a, 2 → b, 3 → d,
4→e
For this function, the
images of distinct
elements of the domain
are distinct. Thus, f is
one-one. In this function,
for the element c of B,
the codomain, there is no
element x in the domain
such that f(x) = c ; i.e., c
has no preimage. Hence,
f is not onto B.
Functions
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.
Functions
In general, g  f ≠ f  g, even when both are defined. In other words, the
composition of functions is not commutative.
Example: f(n) = (-1)n , g(n) = 2n
Functions
Special Functions and Cardinality of a Set
Special Functions and Cardinality of a Set
Special Functions and Cardinality of a Set
Special Functions and Cardinality of a Set
Special Functions and Cardinality of a Set
If f is one-to-one, then f is left invertable.
If f is onto, then f is right invertible.
Example: f: , where f(x) = 9x + 5 is both one-to one and onto
so it is left-invertible and right-invertible
Special Functions and Cardinality of a Set
f|A’ is actually the same as f, except it’s domain is a subset of f’s domain
Special Functions and Cardinality of a Set
Special Functions and Cardinality of a Set
Special Functions and Cardinality of a Set
Special Functions and Cardinality of a Set
Special Functions and Cardinality of a Set
Special Functions and Cardinality of a Set
Note: In = {1,2,3,…,n}
Special Functions and Cardinality of a Set
Special Functions and Cardinality of a Set
Special Functions and Cardinality of a Set
Sequences and Strings
 m is the lower limit of the sum, n the upper
limit of the sum, and ai the general term of the
sum

m is the lower limit of the product, n the upper limit of
the product, and ai the general term of the product.
Sequences and Strings
 Representing Strings into Computer Memory
 A convenient way of storing a string into computer
memory is to use an array.
 Programming languages such as C++ and Java
provide a data type to manipulate strings.
 This data type includes algorithms to implement
operations such as concatenation, finding the length
of a string,determining whether a string is a substring
in another string, and finding a substring into another
string.
Binary Operations
Binary Operations
 Let A be an alphabet. Let A+ be the set of
all nonempty strings on the alphabet A. If
u, v ∈ A+,i.e., u and v are two nonempty
strings on A,then the concatenation of u
and v, uv ∈ A+. Thus, the concatenation
of strings is a binary operation on A+. Also,
by Theorem 5.3.23(ii), the concatenation
operation is associative.
 Hence, A+ becomes a semigroup with
respect to the concatenation operation.
 Called a free semigroup generated by A.
Binary Operations
 Let A* denote the set of all words
including empty word λ. By Theorem
5.3.23(i), for all s ∈ A*,
λs = s
= sλ. Thus, A* becomes a monoid with
identity 1 = λ.
 This monoid is called a free monoid
generated by A.
 If A contains more than one element,
then A* is a noncommutative monoid.