Intro to Discrete Structures Lecture 5 Pawel M Wocjan School of Electrical Engineering and Computer Science University of Central Florida wocjan eecs ucf edu Intro to Discrete StructuresLecture 5 p 1 25 Office Hours Tuesday 2 45pm 4 00pm Thursday 1 00pm 2 15pm Intro to Discrete StructuresLecture 5 p 2 25 Nested Quantifiers Two quantifiers are nested if one is within the scope of the other such as x y x y 0 Everything within the scope of a quantifier can be thought of as a propositional function Define the propositional functions Q x yP x y P x y x y 0 Then we have x y x y 0 x yP x y xQ x Intro to Discrete StructuresLecture 5 p 3 25 Thinking of Quantification as Loops In working with quantification of more than one variable it is sometimes helpful to think in terms of nested loops Of course if there are infinitely many elements in the domain of some variable we cannot actually loop through all values Nevertheless this way of thinking is helpful in understanding nested quantifiers For example x yP x y corresponds to for x do for y do if P x y return F end for end for return T Intro to Discrete StructuresLecture 5 p 4 25 Thinking of Quantification as Loops For example x yP x y corresponds to for x do temp F for y do if P x y then temp T break end for if temp return F end for return T Intro to Discrete StructuresLecture 5 p 5 25 Order of Quantifiers x yP x y y xP x y True if P x y is T for every pair x y False if there is a pair x y for which P x y is F x yP x y y xP x y True if there is a pair x y for which P x y is T False if P x y is F for every pair x y Intro to Discrete StructuresLecture 5 p 6 25 Order of Quantifiers x yP x y True if for every x there is a y for which P x y is T False if there is an x such that P x y is F for every y x yP x y True if there is an x for which P x y is T for every y False if for every x there is a y for which P x y is F Intro to Discrete StructuresLecture 5 p 7 25 Reading Assignment Translating Mathematical Statements into Statements Involving Nested Quantifiers Translating from Nested Quantifiers to English Translating English Sentences into Logical Expressions Intro to Discrete StructuresLecture 5 p 8 25 Negating Nested Quantifiers Example 14 Express the negation of x y xy 1 so that no negation precedes a quantifier x y xy 1 De Morgan x y xy 1 De Morgan x y xy 1 x y xy 6 1 Intro to Discrete StructuresLecture 5 p 9 25 Truth Value of Quantified Expressions Determine the truth value of x y xy 1 Assume that the domain is equal to R Intro to Discrete StructuresLecture 5 p 10 25 Truth Value of Quantified Expressions Determine the truth value of x y xy 1 Assume that the domain is equal to R x y xy 1 F because for x 0 there is no y such that 0 y 1 This statement becomes T if we change the domain to be equal to R R 0 all real numbers except for 0 In words this statement means that every nonzero real x number has a multiplicative inverse y 1 x Intro to Discrete StructuresLecture 5 p 11 25 Rules of Inference Proof in mathematics are valid arguments that establish the truth of mathematical statements By argument we mean a sequence of statements that end with a conclusion By valid we mean that the conclusion or final statement of the argument must follow logically from the truth of the preceeding statements or premises of the argument That is an argument is valid if and only if it is impossible for all the premises to be true and the conclusion to be false Intro to Discrete StructuresLecture 5 p 12 25 Example If you have current password then you can log onto the network You have a current password Therefore You can log onto the network Intro to Discrete StructuresLecture 5 p 13 25 Formal notation Formally we write p q p q Intro to Discrete StructuresLecture 5 p 14 25 Formal Notation Meaning Let p1 p2 pn and c be compound propositions The notation p1 p2 pn c means p1 p2 pn c T p1 p2 pn are called the premises and c is called the conclusion Intro to Discrete StructuresLecture 5 p 15 25 I Rules of Inference Modus ponens p p q q Modus tollens q p q p Intro to Discrete StructuresLecture 5 p 16 25 II Rules of Inference Hypothetical syllogism p q q r p r Disjuctive syllogism p q p q Intro to Discrete StructuresLecture 5 p 17 25 III Rules of Inference Addition p p q Simplification p q p Intro to Discrete StructuresLecture 5 p 18 25 IV Rules of Inference Conjunction p q p q Resolution p q p r q r Intro to Discrete StructuresLecture 5 p 19 25 Resolution The inference rule resolution p q p r q r is based on the tautology p q p r q r We recover disjunctive syllogism by setting r F p q p q Intro to Discrete StructuresLecture 5 p 20 25 Rules of Inference for Quantified Statements Universal instantiation xP x P c Universal generalization P c for an arbitrary c xP x Intro to Discrete StructuresLecture 5 p 21 25 Rules of Inference for Quantified Statements Existential instantiation xP x P c for some element c Existential generalization P c for an some element c xP x Intro to Discrete StructuresLecture 5 p 22 25 Universal Modus Ponens Universal Modus Ponens x P x Q x P a where a is a particular element in the domain Q a Assume that For all positive integers n if n is greater than 4 then n2 is less than 2n is true Use UMP to show that 1002 2100 Let P n n 4 and Q n n2 2n The statement corresponds to n P n Q n UMT implies that Q 100 is T P 100 is T Intro to Discrete StructuresLecture 5 p 23 25 Universal Modus Tollens Universal Modus Tollens x P x Q x Q a where a is a particular element in the domain P a Intro to Discrete StructuresLecture 5 p 24 25 Introduction to Proofs Some Terminology Axioms or postulates Theorem Proposition Lemma Lemmas or Lemmata Corollary Proof Conjecture Intro to Discrete StructuresLecture 5 p 25 25
View Full Document
Unlocking...