Transcript Sets+Functions - SIUE Computer Science

MATH 224 – Discrete Mathematics
Basic Structures - Sets
Sets provide a basis for many of the data structures used in computer science. As you
already know sets are collections of any type of object without ordering and without
duplicates. The original formalization of the set was developed by the mathematician
Georg Cantor in the late 19th century.
Cantor is most famous for both his theory of sets and infinity. He developed the idea of
a hierarchy of infinities with the smallest being countable infinity sets, e.g., the
integers, followed what he called Aleph 1 (‫א‬1) the “smallest” uncountable set, e.g., the
real numbers. His theory provides the basis for the concept that some problems are not
solvable by computers.
3/27/2016
1
MATH 224 – Discrete Mathematics
Set Examples
Some examples of sets include:
1.
The set of students in this class
2.
The set N of natural number (all non-negative integers) {0, 1, 2, 3, …}
3.
The set Z of all integers both positive and negative
4.
The set Q of all rational numbers (numbers that can be expressed as p/q, where
p and q are elements of Z
5.
The set R of real numbers.
6.
The set C of complex numbers.
{…, -2, -1, 0, 1, 2, …}
Which of these sets are countable and which are uncountable?
Countable sets can also be finite. Can you name some other countable sets, both
finite and infinite?
3/27/2016
2
MATH 224 – Discrete Mathematics
Basic Set Notation
,
3/27/2016
3
MATH 224 – Discrete Mathematics
Sets and Venn Diagrams
Describe the sets represented by this Venn diagrams and there size.
Computational Problems
x≥0
Solvable by
N2
algorithms
x Z
Solvable by
computers
Letters
ASCII characters
3/27/2016
4
MATH 224 – Discrete Mathematics
Basic Set Notation
1. Vertical bars are used to indicate the size of a set or the number of elements
in a set. So far example, the set of English lowercase letters L has size
twenty six as indicated by |L| = 26 A set of this size can be put in one-to-one
correspondence with the set {0, 1, 2, ..., 25}.
2. The power set of a set is indicated by P(X). This is the set of all subsets of
X. So for example, if X = {a, b, c} then
P(X) = { , {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}
If a set has a finite number of elements, for example N, how many
elements will its power set have? Do you think that the power set of the
integers is countable? Is it possible for a finite set to contain itself?
Can you think of an example?
3/27/2016
5
MATH 224 – Discrete Mathematics
Sets with Quantifiers
Assume that we have an algorithm σ that finds square roots of numbers. This
might be indicated by something like
( x R) (x ≥ 0 → σ(x) returns the √x)
How would you describe the set of perfect squares?
x Y iff x = y2 where y is an integer or
Y = { x | x = y2 where y Z}
How would you describe the real numbers as a subset of the complex
numbers without mentioning the imaginary number i?
3/27/2016
6
MATH 224 – Discrete Mathematics
Cartesian Products and Ordered Pairs
Finally the concept of Cartesian products and order pair is important in computer
science. You have seen ordered pairs, when plotting XY coordinates on a
2-dimensional graph. The Cartesian product, A x B, of two sets consists of all
possible ordered pairs (a, b) where a A and b B. So for example if A = {1, 2, 3}
and B = {a, b}, then A x B = {(1, a), (1, b), (2, a), (2, b), (3, a), (3, b)}.
Data structures such as graphs, trees and 2-dimensional arrays may be described as
subsets of ordered pairs. Any subset of a Cartesian product is called a relation. And
under specific circumstances a relation may also be a function. As an example,
consider the set of all ordered (x, y) pairs of the grapy of y = 2x + 5. That set is
called a relation and a function. It is a subset of R x R where R is the set of real
numbers.
Why do circles and ellipses on an x ─ y coordinate graph not represent
functions while parabolas and straight lines do?
3/27/2016
7
MATH 224 – Discrete Mathematics
Set Operations
Union:
A U B = { x | x A v x B}
Intersection: A ∩ B = { x | x A ^ x B}
Difference: A – B = { x | x A ^ x B}
( stands for not in)
Complement: A′ or A = {x | x A} (It is assumed with respect to a universal set)
Symmetric Difference: A O B = {x | (x A U B) ^ (x A ∩ B)}
For example , why does A ∩ (B U C) = (A ∩ B) U (A ∩ C)?
And what about A U (A ∩ B) = A?
Could the distributive law for union be used to get the same result when union
and intersection are swapped?
3/27/2016
8
MATH 224 – Discrete Mathematics
Set Identities
Can you explain why the identities in Table 1, on Page 124 from our text are true?
3/27/2016
9
MATH 224 – Discrete Mathematics
Functions
You already know what a function is in C++. It is a routine that possibly takes
some input, performs some operations and possibly returns a value. Not all
functions in C++ correspond to functions in mathematics. To conform to a
mathematical function a C++ function must:
1.
Take input, one or more parameters
2.
Return a value that is unique for a given input
3.
Must be a constant function – that is it must not alter any values, just return
something (Well, it could be a void function with some parameters passed by
value and some passed by reference satisfying specific conditions.)
When a C++ function returns a value, will a unique input always determine
a unique output? What does a function have to do with ordered pairs?
How are mathematical functions specified?
3/27/2016
10
MATH 224 – Discrete Mathematics
Functions
In mathematics, a function has a domain, sometimes referred to as the independent
variable and a range (or codomain)* sometimes referred to as the dependent variable.
For each possible value in the domain, there must be exactly one element in the range.
An example of a function is f(x) = 2x – 3. If the domain of this function is restricted
to integer values between –5 and 2, then the function f might be described as the set
of ordered pairs {(-5, -13), (-4, -11), (-3, -9), (-2, -7), (-1, -5), (0, -3), (1, -1), (2, 1)}.
The elements in this set correspond to points on the line described by y = 2x – 3.
*Note that there is a distinction between range and the codomain. To be precise
the range is a subset of the codomain.
Why does the equation y2 + x2 = 4, not describe a function?
Why does the set {(0,1), (2, 4), (4, 8), (1, 0), (4, 2)} not describe a function?
3/27/2016
11
MATH 224 – Discrete Mathematics
Function Terminology
A function is called onto if its range is equal to the codomain. So for example,
f(x) = 2x – 3 is a function from the real numbers to the real numbers that is onto
since ( y R) x (y = 2x – 3 ) . On the other hand g(x) = 2x2 – 3 is not onto the
real numbers since no value of x results in a value for g(x) < –3. An onto function is
called a surjection.
How would you express the fact that g(x) is not an onto function using
quantifiers?
Can you give some examples of functions that are surjections?
Can you give some examples where the domain is finite?
Is a C++ function that sorts array surjective?
3/27/2016
12
MATH 224 – Discrete Mathematics
Function Terminology
A function is called one-to-one if there is exactly one value in the domain for each
value in the range.. So for example f(x) = 2x – 3 is a one-to-one function from the
real numbers to the real numbers that is ( y R, x R [(f(x) = f(y)) → x = y] . On
the other hand, g(x) = 2x2 – 3 is not one-to-one. For example, g(3) = g(-3) =15. A
one-to-one function is called an injection. Finally a function that is one-to-one and
onto is called a bijection or a one-to-one correspondence. When there is a one-toone correspondence between to sets, those sets are the same size (have the same
number of elements).
Is a C++ function that sorts arrays injective?
Can you give some examples of functions that are bijections?
Does the set of all integers have the same number of elements as the set of even
integers? Can you describe a one-to-one correspondence between these two
sets.
Is the factorial function one-to-one? Is it onto the set of all positive integers?
3/27/2016
13
MATH 224 – Discrete Mathematics
Function Terminology
A function is said to be invertible if it has an inverse. For example, the inverse of
f(x) = 2x + 5 is f-1(x) = (x – 5)/2.
How would you show that this example is correct?
The inverse of a function interchanges the domain and the range.
Does a function have to be a bijection in order to have an inverse?
Can you give some examples of functions and their inverses?
3/27/2016
14
MATH 224 – Discrete Mathematics
Function Terminology
Functions can be combined to create new functions. For example the result of two
functions may be added, for example, (f1 + f2) = f1(x) + f2(x). All arithmetic
operations may be used in a similar way including multiplication, division and
subtraction. Even more complex operations such as exponentiation, e.g., f1(x)f2(x)
may be used.
Can functions be combined in this way in C++. How would you do
exponentiation of two functions in C++?
Another operation is the composition of functions f o g(x) = f(g(x)).
What function results form f o f-1(x)? Describe the function as an equation in y
and x ?
Give an example of how to create the composition of two functions in C++.
3/27/2016
15
MATH 224 – Discrete Mathematics
Some Important Functions for programming
You should know what the floor and ceiling functions are. In C++, when doing
integer division, which of these functions is used?
Find a value for x that makes
└x┘+ └x┘ ≤└x + x┘
Another important function in programming is log2(x) written as lg(x). This function
is the inverse of 2x. So for example, since 25 = 32, it follows that lg(32) = 5.
The lg function along with the ceiling function can be used to determine the number
of bits required to represent an integer. For example, to represent 1000, requires 10
bits since lg(512) = 9 and lg(1024) = 10. Therefore 9 < lg(1000) < 10 and
┌lg (1000)┐ = 10.
Do you know an algorithm that you were taught in CS 140 or 145 that takes
┌lg(n) ┐ iterations when applied to an array with n elements?
3/27/2016
16