Transcript discrete mathematics

DISCRETE MATHEMATICS
• K.H. Rosen, Discrete Maths and its
applications, McGraw-Hill.
• Course covers introduction to set theory,
functions, relations, logic, graphical
representation.
Functions
• Df A function is a rule which assigns to
each member a of a set A a unique
member b of set B. We write f: A→B.
Alternatively we write f(a)=b. So far have
been concerned with the case when
A=B=R (the set of real numbers)
• Note for each element a of A an element b
exists in B but not vice-versa.
Functions as relations
• Recall relation is a subset of AxB
• A function is a special case of relation R
where (a,b) in R implies there is no (a,b’)
in R unless b , b’ coincide and where there
is (a,b) in R for any a in A.
• Thus for a function F the following
statements are equivalent
• F(a)=b, aFb, (a,b)∈F.
Domain and Codomain of f: A→B
• A is the domain, B is the codomain of f
• Example let f be the function that rounds
up a number to the nearest integer. Hence
round(.1)=0, round (3.6)=4. So round
R→Z.
• Hence domain is the set of real numbers
whilst the codomain is the set of integers.
Image, pre-image and Range
• If f(a)=b we say b is the image of a under f.
Likewise we refer to a as the pre-image of b. We
also talk about the images and pre-images of
subsets of A and B. For example if S is a subset
of A the image of S is f(S)={f(s) | s∈S}. The
range of a function is the set f(A).
• Ex suppose f: R→R,f(x)=x², then image of 2 is 4,
pre-image of 9 is 3, Range of f is {x∈R,|x>0}.
Injective,surjective,bijective
• A function is injective if f(x)=f(y) implies
x=y. ( one to one mapping) Examples
f(x)=x+1, f(x)=x² both defined on R are
injective, not injective. But if we define only
on positive real numbers both are
injective.
• A function is surjective if for every element
b of B there exists a in A with f(a)=b. (
mapping is onto)
Example
• f:R→R f(x)=x+1 is surjective
f(x)=x² is not surjective since no x exists
with f(x)=-1. But if we define on C the set
of complex numbers both are surjective.
• Definition If f is surjective and injective we
say it is bijective ( one to one and onto)
Exercise
•
•
•
•
Consider two finite sets A and B. Evaluate:
a) The number of functions from A to B.
b) The number of injections from A to B.
c) The number of bijections from A to B.
Exercise- find examples of
functions from N to N satisfying:
•
•
•
•
a) An injection but not surjection
b) A surjection but not injection
c) A bijection
d) neither a surjection or injection
Inverse of a function
• Df The function f⁻¹:B→A is the inverse of f : A
→B and has the property that f(f⁻¹(x))=x,:x∈A
• Theorem The function f has an inverse iff f⁻¹ is
bijective. To prove this think of f⁻¹ as the relation
⋃{(b,a))},with (a,b)∈f ⊆B×A
• Since f injective there is no more than one
element of A for each element of B and since f
surjective there is no less than one element of A
for each element of B so f⁻¹ is a function
Inverse
• Now show if f has an inverse it must be bijective
• If f(a)=f(b)it follows that f⁻¹(f(a))=f⁻¹(f(b) so by
definition of inverse we have a=b so that f is
injective
• For any b in B a=f⁻¹(b) and then f(a)=f(f⁻¹(b))=b
so there is an element a in A for every b in B
with f(a)=b, so f is surjective. Since f injective
and surjective it is also bijective
INTRODUCTION TO LOGIC
• What do we mean by logic?
• Oxford Dict. The systematic use of
symbolic techniques and mathematical
techniques to determine the forms of valid
deductive argument.
• Thus logic is the common language by
which we can demonstrate the validity of
our reasoning …’
PROPOSITIONS AND
NEGATIONS
• Proposition is a declarative statement that is true or
false, but not both.
• Ex All Maths undergraduates wear sandals. False
• All Maths undergraduates have tutors. True
• If a relation is transitive then Rⁿ is transitive. True
• Hopefully the Circle Line will be running tonight. Not a
proposition.
• Propositional logic is the branch of logic dealing with
reasoning about propositions.
• We will use symbols to denote propositions. Ex let p be
the proposition all Maths students wear glasses. Let p be
the proposition that all EE1 students know how to wire a
plug. False.
NEGATION AND USE OF
PROPOSITIONS
• Use several propositions to build compound
propositions
• Df Let p be a proposition. Then the proposition ‘
It is not the case that p’ is another proposition
called the negation of p and written as ¬p. Ex
This lecture course is given at Imperial College.
Its negation is ‘ It is not the case that this lecture
course is given at Imperial College.’ OR ‘this
lecture course is not given at Imperial College.
Conjuncton and Disjunction
• Given propositions p and q the proposition ‘p and q’
written p∧q is true when both p and q are true and false
otherwise, it is called the conjunction of p and q.
• Given propositions p and q then the proposition ‘p or q’
denoted by p∨q is the proposition that is false when both
p and q are false and true otherwise. p∨q is called the
disjunction of p and q.
• Ex Suppose p is ‘Maths undergraduates love tofu’ and q
is ‘Maths undergraduates are weird’
• Then p∨q is ‘ Maths undergrads either love tofu or are
weird or both’.
• p∧q is ‘maths undergrads like tofu and are weird’.
IMPLICATIONS
• When we say p implies q, written p→q, we mean
the proposition which is false when p is true and
q is false, and true otherwise. ( think …)
• When p→q we might say ‘ if p, then q’, ‘ p is
sufficient for q’, ‘q if p’, ‘q is necessary for p’, ‘p
only if q’
• Example Suppose p is ‘I revised’ and q is ‘I
passed the exam’ Then p→q may be expresed
as ‘if I revised I passed’ ‘I passed if I revised’ or ‘I
revised only if I passed’
Implications
• There is no need for a relationship between the premise
and conclusion. Example ‘If all Maths undergrads like
tofu, then 1+1=2. True regardless of tofu.
• ‘If all Maths undergrads like tofu then 1+2=4’ True
because not all undergrads like tofu.
• ‘If we are in london 1+2=4’ False because we are in
London but 1+2 is 3.
• ‘If all Maths undergrads like tofu then 1+2=4’ True since
not all maths students like tofu.
• Note that in English ‘implies’ can also mean causes so
English considers the meaning of propositions whilst
Logic considers whether they are true or false..
CONVERSE, CONTRAPOSITIV,
AND INVERSE
• a iff b is the same as (a→b)∧(b→a) and is
written as a⇔b. Hence a⇔b is true when a and
b are both true or when a and b are both false
(and is otherwise false)
• We define b→a to be the converse of a→b.
• The contrapositive of a proposition a→b is the
proposition ¬b→¬a.
• The inverse of a→b is the proposition ¬a→¬b.
LOGICAL EQUIVALENCE
• A tautology is a compound proposition that is
always true, eg p∨¬p is a tautology.
• A contradiction is a compound proposition that is
always false. Eg p∧¬p is a contradiction.
• We say propositions p and q are logically
equivalent, written as if p≡q, if p⇔q is a
tautology. Eg ¬(p∨q)≡¬p∧¬q.. De Morgans
Theorem
• We can express an implication in terms of a
disjunction and a negation p→q≡¬p∨q
LOGIVAL EQUIVALENCE
• Hence an implication is logically equivalent
to its contrapositive
• p→q≡¬p∨q≡q∨¬p≡¬q→¬p
• If I revised, I passed ≡ if I didn’t pass I
didn’t revise.
• Likewise its converse is logically
equivalent to its inverse.
• q→p≡¬q∨p≡p∨¬q≡¬p→¬q
LOGICAL EQUIVALENCE
• The most common mistake in logic is to
assume an implication is logically
equivalent to its inverse
• Examples: ‘if I revised I passed’ is not
equivalent to ‘ if I didn’t revise I didn’t pass’
• ‘if I eat too much I will get fat’ is not
equivalent to ‘if I don’t eat too much I will
not get fat’
OPERATOR PRECEDENCE
•
•
•
•
•
BASIC RULES
a∧¬b≡a∧(¬b)
a∨b∧c≡a∨(b∧c)
a∨b→c≡(a∨b)→c
Hence order of increasing precedence is
→∨∧¬
LOGIC AND ENGLISH
LANGUAGE
• Language often ambiguous so try and identify the basic
propositions and build into logical statements.
• I sell donuts and coffee ≡ ‘I sell coffee’ ^I sell donuts’
• I am not good at golf≡¬(I am good at golf)
• If its raining its not sunny≡raining→¬sunny
• You can have chicken or fish ≡’you can have chicken’
∧’you can have fish’
• Unless causes problems!!! I will play golf if it doesn’t rain
can be ¬(′it will rain')→'I will play golf‘
• or ¬(′it will rain')⇔′I will play golf‘
PREDICATE LOGIC
• Propositional logic is limited, eg how do we
express ‘All Maths undergrads are clever’ in
terms of the cleverness of particular maths
undergrads? Or express ‘there is a maths
undergrad wearing sandals’ in terms of whether
each individual maths undergrad is wearing
sandals
• We therefore generalize the idea of a proposition
to a predicate, predicates take one or more
variable as arguments
PREDICATE LOGIC
• Examples: Let P(x) be the statement
“x>12” then P(1) is false, P(23) is true.
• Let P(x) denote the statement ‘x is a
Professor in the Mathematics Department’
then P(Hall) is true but P(Limebeer) is
false
• Thus P(x) is not true or false until we
specify an argument
UNIVERSAL QUANTIFIERS
• Suppose P(x) is the predicate ‘has a heart’
• Then we can discuss P(Hall), P(Limebeer) but
how can we say all humans have a heart.
Predicates deal with this using quantification.
• Definition The universal quantification of P(x) is
the proposition ‘P(x) is true for all values of x in
the universe of discourse’ Hence in the universe
of discourse consisting of all humans we would
say the universal quantification of P(x) is true
• Notation We write ∀xP(x) which we read as for
all x, P(x) for the universal quantification of P(x)
UNIVERSAL QUANTIFICATION
• Of course we also need to specify the
universe of discourse but here can use set
theory
• Suppose P(x) is the predicate x²≽0, then
we can say ∀x∈R P(x), ie for all real x P(x)
• but ¬(∀x∈C P(x))
EXISTENTIAL QUANTIFIER
• Suppose P(x) is’ x is wearing a necklace’ then
P(Florence) is the proposition ‘Florence is
wearing a necklace’ but how do we say ‘there is
an EE1 Student wearing a necklace’?
• Definition The existential quantification of P(x) is
the proposition ‘there exists an element x in the
universe of discourse such that P(x) is true’
• Notation we write ∃xP(x) which we read as there
exist x such that P(x). Hence if J=set of all EE!
Students we can write ∃x∈JP(x)