Office HoursNested QuantifiersThinking of Quantification as LoopsThinking of Quantification as LoopsOrder of QuantifiersOrder of QuantifiersReading AssignmentNegating Nested QuantifiersTruth Value of Quantified ExpressionsTruth Value of Quantified ExpressionsRules of InferenceExampleFormal notationFormal Notation & MeaningI. Rules of InferenceII. Rules of InferenceIII. Rules of InferenceIV. Rules of InferenceResolutionRules of Inference for Quantified StatementsRules of Inference for Quantified StatementsUniversal Modus PonensUniversal Modus TollensIntroduction to ProofsIntro to Discrete StructuresLecture 5Pawel M. WocjanSchool of Electrical Engineering and Computer ScienceUniversity of Central [email protected] to Discrete StructuresLecture 5 – p. 1/25Office HoursTuesday 2:45pm – 4:00pmThursday 1:00pm – 2:15pmIntro to Discrete StructuresLecture 5 – p. 2/25Nested QuantifiersTwo quantifiers are nested if one is within the scope ofthe other, such as∀x∃y(x + y = 0) .Everything within the scope of a quantifier can bethought of as a propositional function. Define thepropositional functionsQ(x) : ∃yP (x, y)P (x, y) : x + y = 0Then, we have∀x∃y(x + y = 0) ≡ ∀x∃yP (x, y) ≡ ∀xQ(x) .Intro to Discrete StructuresLecture 5 – p. 3/25Thinking of Quantification as LoopsIn 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 thedomain of some variable, we cannot actually loopthrough all values. Nevertheless, this way of thinking ishelpful in understanding nested quantifiers.For example, ∀x∀yP (x, y) corresponds tofor x dofor y doif ¬P (x, y) return Fend forend forreturn TIntro to Discrete StructuresLecture 5 – p. 4/25Thinking of Quantification as LoopsFor example, ∀x∃yP (x, y) corresponds tofor x dotemp:=Ffor y doif P (x, y) thentemp:=T;breakend forif ¬temp return Fend forreturn TIntro to Discrete StructuresLecture 5 – p. 5/25Order 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/25Order 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/25Reading AssignmentTranslating Mathematical Statements into StatementsInvolving Nested QuantifiersTranslating from Nested Quantifiers to EnglishTranslating English Sentences into Logical ExpressionsIntro to Discrete StructuresLecture 5 – p. 8/25Negating Nested QuantifiersExample 14: Express the negation of ∀x∃y(xy = 1) so thatno 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/25Truth Value of Quantified ExpressionsDetermine the truth value of ∀x∃y(xy = 1). Assume thatthe domain is equal to R.Intro to Discrete StructuresLecture 5 – p. 10/25Truth Value of Quantified ExpressionsDetermine the truth value of ∀x∃y(xy = 1). Assume thatthe domain is equal to R.∀x∃y(xy = 1) ≡ F because for x = 0 there is no y suchthat 0 · y = 1.This statement becomes T if we change the domain tobe equal to R∗:= R \ {0} (all real numbers except for 0).In words, this statement means that every nonzero realx number has a multiplicative inverse y = 1/x.Intro to Discrete StructuresLecture 5 – p. 11/25Rules of InferenceProof in mathematics are valid arguments that establishthe truth of mathematical statements.By argument, we mean a sequence of statements thatend with a conclusion.By valid, we mean that the conclusion, or finalstatement of the argument, must follow logically fromthe truth of the preceeding statements, or premises, ofthe argument.That is, an argument is valid if and only if it isimpossible for all the premises to be true and theconclusion to be false.Intro to Discrete StructuresLecture 5 – p. 12/25Example“If you have current password, then you can log ontothe network.”“You have a current password.”Therefore,“You can log onto the network.”Intro to Discrete StructuresLecture 5 – p. 13/25Formal notationFormally, we writep → qp∴ qIntro to Discrete StructuresLecture 5 – p. 14/25Formal Notation & MeaningLet p1, p2, . . . , pnand c be (compound) propositions. Thenotationp1p2...pn∴ cmeans(p1∧ p2∧ · · · ∧ pn) → c ≡ T.p1, p2, . . . , pnare called the premises and c is called theconclusion.Intro to Discrete StructuresLecture 5 – p. 15/25I. Rules of InferenceModus ponenspp → q∴ qModus tollens¬qp → q∴ ¬pIntro to Discrete StructuresLecture 5 – p. 16/25II. Rules of InferenceHypothetical syllogismp → qq → r∴ p → rDisjuctive syllogismp ∨ q¬p∴ qIntro to Discrete StructuresLecture 5 – p. 17/25III. Rules of InferenceAdditionp∴ p ∨ qSimplificationp ∧ q∴ pIntro to Discrete StructuresLecture 5 – p. 18/25IV. Rules of InferenceConjunctionpq∴ p ∧ qResolutionp ∨ q¬p ∨ r∴ q ∨ rIntro to Discrete StructuresLecture 5 – p. 19/25ResolutionThe inference rule “resolution”p ∨ q¬p ∨ r∴ q ∨ ris 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/25Rules of Inference for Quantified StatementsUniversal instantiation∀xP (x)∴ P (c)Universal generalizationP (c) for an arbitrary c∴ ∀xP (x)Intro to Discrete StructuresLecture 5 – p. 21/25Rules of Inference for Quantified StatementsExistential instantiation∃xP (x)∴ P (c) for some element cExistential generalizationP (c) for an some element c∴ ∃xP (x)Intro to Discrete StructuresLecture 5 – p. 22/25Universal Modus PonensUniversal 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 isgreater than 4, then n2is less than 2n” is true. Use UMPto show that 1002< 2100.Let P (n) : n > 4 and Q(n) : n2< 2n.The statement (*) corresponds to ∀n(P (n) → Q(n)).UMT
View Full Document
Unlocking...