Transcript Mathematical Foundations

Mathematical Preliminaries
• Sets,
Set Operations, and Boolean Algebra
• Logic and Proof Techniques
• Set Product, Relations and Functions
• Equivalence Relations and Partial Orders
• Countable Sets
• Recursive Definitions
• Graphs
Sets, Set Operations
• Sets : A set is an unordered collection of objects, usually with some common
property
• Examples – set of integers, set of symbols {alphabet}, set of syntactic
types, set of symbol strings (language)
• Subsets : A is a subset of B (written A  B) if every element of A is also an
element of B (written  x  A  x  B)
• Exercise : Show transitivity of  (i.e. A  B and B  C  A  C )
• Set Operations :
•  : x  A  B iff x  A or x  B
•  : x  A  B iff x  A and x  B
• ~ : x  ~A iff x  A
• Characteristic Vectors : If A is a set of n elements (cardinality n), and B  A,
then Bv is a binary vector with ith component corresponding to ith element xi of A
and vi = 1 if xi  A and vi = 0 otherwise.
• Example: A = {a,b,c,d}. Then 0101 represents B = {b,d} and 1001
represents C = {a,d}.
• Exercise : Describe the construction of the characteristic vector of
•A  B
•AB
•~A
Set Specification
• Set specification : A set is specified by giving a rule or definition which
determines which objects are in the set.
• List – if the set is finite, a list of objects belonging to the set is often used
to specify the set. Exercise : Write pseudo code to perform set operations
for two sets specified by ordered lists.
• For infinite or large finite sets, the following methods of specification are
used:
• Property – A property possesed by all and only those set elements is
given.
• Acceptor – A finite state acceptor is used for languages (sets of
strings) for which only a finite number of things need to be remembered.
• Recursive methods – a finite basis set is given along with rules for
forming the reset of the elements from existing elements.
• Grammars – Languages are specified by a finite set of rules which
either give basis elements or tell how to build more complex strings
from simpler ones.
Boolean Algebra
– Boolean Algebra :
•
Two binary operations ( + , * ) and a unary operation ( ~ ) defined
as follows:
– 0 + 0 = 0, 0 + 1 = 1 + 0 = 1, 1 + 1 = 1
– 0 * 0 = 0 * 1 = 1 * 0 = 0, 1 * 1 = 1
– ~0 = 1 and ~1 = 0
– Subset Specification
• Let U be a set {x1, x2, . . Xn} and A any subset.
• Subset A can be specified by a boolean vector of n bits called the
characteristic vector of A
• The ith bit of the characteristic vector = 1 if xi is in A and 0 otherwise.
• Exercise : Describe the relation between Boolean Algebra and Set
Operations.
• Exercise : Write pseudo code to perform Union, Intersection and
Complement given charateristic vectors.
Propositional Logic
• A declarative statement such as “Bill is a CS student”
has a truth value of T or F and is denoted by P (a truth
variable)
• Propositions may be combined with logical operators
and the composite statement has value as shown below.
P  Q is true if either P or Q are true and false if both are false
P  Q is true if both P and Q are true and false if either is false.
¬ P is true if P is false and false if P is true
P  Q is true if P and Q have the same truth value and false if
their values differ
– P  Q is false if P is true and Q is false and true otherwise.
– Exercise – Construct truth tables for each operation.
–
–
–
–
• A tautology is always true.
– P  Q  ¬ P  Q is a tautology.
– P  (Q  R)  (P  Q)  (P  R) is a tautology.
Rules of Inference
•
•
•
•
P , P  Q then Q - modus ponens
¬ Q, P  Q then ¬ P - modus tollens
Exercise : Show by truth table.
Induction
– P1 is true
– Pi  Pi+1 is true for all i
• Then Pi is true for all i
Example of Induction
• Pi : Sum of integers from 1 to n is
n(n+1)/2.
– P1 : Sum of integers from 1 to 1 is 1
which equals 1(1+1)/2 so P1 true.
– Pi  Pi+1 : If Pi is true, then sum of
integers from 1 to n+1 is sum of
integers from 1 to n + n+1, which is
n(n+1)/2 + (n+1) = (n/2 + 1)(n+1) =
(n+2)(n+1)/2 so Pi+1 is true.
– so Pi  Pi+1 is true for all i
Cartesian Set Product and Relations
• Cartesian Product
• The product of two sets A = {a1, .. am} and B = {b1, .. bn} is a
set, denoted by A  B, of ordered pairs (ai,bj) of cardinality
m*n.
• Example : A = {a,b} and B = {1,2,3}
• A  B = {(a,1),(a,2),(a,3),(b,1),(b,2),(b,3)}
• Relations
• A relation R between two sets A,B is a subset of their product
A  B. That is, R is a relation between A,B if R  A  B
• Example :  is a relation between {1,2,3} and itself since  is a
subset of {1,2,3}  {1.2.3}
• Exercise : What are the elements of  as a relation between
{1,2,3} and itself?
Functions
• Functions : A function f from A into B. written f : A  B where A is
called the domain of f and B the range, is a relation between A and B
for which
•  a  A,  b  B for which (a,b)  f written f(a) = b
• for each input in the domain A, there is an output
• if (a,b1)  f and (a,b2)  f, then b1 = b2.
• the output is unique.
• Exercise : Consider A = {1,2,3} and B = {a,b} Which of the following
are functions from A into B?
• R = {(2,b),(3,a)}
• S = {(3,b),(2,a),(1,a)}
• T = {(1,b),(2,a),(1,a)}
Properties of Functions
• Onto Functions
• A function f : D → R is onto the range R if every element of R
occurs as an output for some input in the domain D.
• f : {1,2} → {a,b,c} with f(1) = a, f(2) = c is not onto {a,b,c} because
b does not occur as an output for any input.
• g : {1,2,3} → {a,b} with f(1) = a, f(2) = a and f(3) = b is onto {a,b}
because both a and b occur as outputs for some input
• 1-1 Functions
• A function f : D → R is 1-1 if every element of R occurs as at
most one output of some input in the domain D.
• f : {1,2} → {a,b,c} with f(1) = a, f(2) = c is a 1-1 function.
• g : {1,2,3} → {a,b} with f(1) = a, f(2) = a and f(3) = b is not 1-1.
• Inverse function
• The inverse f -1 of a function f maps the range onto the domain as
follows:
• f -1(b) = a iff f(a) =b.
Power Sets
• If A is a set, its power set 2A is the set of all
subsets of A.
• Exercise: Construct the power set of A = {a,b,c}
• Exercise: Construct the function f which has 2A
as domain and the set of corresponding
characteristic vectors as range.
Equivalence Relations and Partial Orders
Let R be a relation on A so R  R  R
• R is reflexive if a R a a, a  A
• R is symmetric if a R b  b R a
• R is anti-symmetric if a R b and b R a  a=b
• R is transitive if a R c if a R b and b R c.
• A relation which is reflexive, symmetric and
transitive is called an equivalence relation.
• An equivalence relation partitions a set A
into disjoint equivalence classes.
• A relation which is reflexive, anti-symmetric
and transitive is called a partial order.
Countable Sets
Finite Sets
• If  a 1-1, onto function from A onto {1,..,n}
then A is finite of cardinality n.
•If A is finite of cardinality n then  a 1-1,
onto function from A onto {1,..,n}.
Infinite sets
• A is countable (and infinite) if  a 1-1, onto
function from A onto the postive integers.
• Exercise : Show the set of integers – {0} is
countable
Exercise : Show the set of integers – {0} is
countable
• Construct a 1-1 onto function F from set of
integers – {0} onto set of positive integers
• Set of integers – {0} =
–
{negative integers}  {positive integers}
– Let x be negative integer :
• F(x) = 2 * |x+1| + 1 so F(-1) = 1, F(-2) = 3, F(-3) = 5, ..
So sub range of F for negative integers is odd integers
– Let x be positive integer :
• F(x) = 2*x so F(1) = 2, F(2) = 4, F(3) = 6, .. So sub
range of F for positive integers is even integers
Recursive Definitions
Peano’s Axioms (for the natural numbers)
A recursive definition of N, the set of natural
numbers, is constructed using the success
function s : s(n) = n+1
• Basis : 0 € N
• Recursive step: If n € N, then s(n) € N
• Closure : n € N   p € N and s(p) = n
Graphs
• A graph
G consists of a relation E on a set V with
• the elements of V called the vertices of G
• the elements of E called the edges of G
• the graph is directed if the relation is not symmetric and
undirected if the relation is symmetric.
Let E be the relation “is a factor of” on {1,2,3,4,5,6,7,8}. A diagram of the
graph of this relation is show below.
2
1
3
5
7
8
4
4
6
Paths, Circuits and Trees
• Paths : A simple path in a graph is a sequence of vertices v1, v2 . . Vn such
that for i = 1 to n-1, (vi,vi+1) is an edge of the graph and vertices are distinct,
except for possible the first and last.
• Connected : A vertex u is connected to every vertex v for which there is a
path from u to v.
• Connected Graph : A connected graph is one in which every vertex is
connected to every other vertex.
• Circuits : A circuit is a simple path for which the first and last vertices are
the same.
• Tree : A tree is a graph with
• no circuits
• is connected.
• Exercise. Prove that a tree with n vertices has n-1 edges.
A tree with n vertices has n-1 edges.
• Basis : A tree with 1 vertex has 0 edges.
• Inductive Step: If a tree with n vertices has
n-1 edges, show that a tree with n+1
vertices has n edges.
– Let T be a tree with n+1 vertices.
• Find a vertex v of degree 1 so edge e = (v,u) is
only edge incident with v.
• Delete v and e so remainder is tree (why?) with n
vertices and must have n-1 edges by inductive
hypothesis.
• Original tree has (n-1) + 1 = n edges. QED