DOC PREVIEW
UCF COT 3100 - Intro to Discrete Structures

This preview shows page 1-2-3-27-28-29 out of 29 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 29 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 29 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 29 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 29 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 29 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 29 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 29 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Hints for HW1Hints for HW1Formal Notation & MeaningI. Rules of InferenceModus Ponens -- Modus TollensII. Rules of InferenceModus Ponens -- Disjunctive syllogismIII. Rules of InferenceIV. Rules of InferenceResolutionHypothetical Syllogism -- ResolutionHypothetical Syllogism -- ResolutionRules of Inference for Quantified StatementsRules of Inference for Quantified StatementsUniversal Modus PonensUMP in MathUniversal Modus TollensIntroduction to ProofsProofs MethodsDirect ProofDirect ProofIndirect ProofIndirect ProofIndirect ProofProof StrategyDirect or Indirect Proof?Direct or Indirect Proof?Proof by ContraditionIntro to Discrete StructuresLecture 6Pawel M. WocjanSchool of Electrical Engineering and Computer ScienceUniversity of Central [email protected] to Discrete StructuresLecture 6 – p. 1/29Hints for HW1Intro to Discrete StructuresLecture 6 – p. 2/29Hints for HW1Intro to Discrete StructuresLecture 6 – p. 3/29Formal 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 6 – p. 4/29I. Rules of InferenceModus ponenspp → q∴ qModus tollens¬qp → q∴ ¬pIntro to Discrete StructuresLecture 6 – p. 5/29Modus Ponens – Modus TollensIntro to Discrete StructuresLecture 6 – p. 6/29II. Rules of InferenceHypothetical syllogismp → qq → r∴ p → rDisjuctive syllogismp ∨ q¬p∴ qIntro to Discrete StructuresLecture 6 – p. 7/29Modus Ponens – Disjunctive syllogismIntro to Discrete StructuresLecture 6 – p. 8/29III. Rules of InferenceAdditionp∴ p ∨ qSimplificationp ∧ q∴ pIntro to Discrete StructuresLecture 6 – p. 9/29IV. Rules of InferenceConjunctionpq∴ p ∧ qResolutionp ∨ q¬p ∨ r∴ q ∨ rIntro to Discrete StructuresLecture 6 – p. 10/29ResolutionThe 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 6 – p. 11/29Hypothetical Syllogism – ResolutionIntro to Discrete StructuresLecture 6 – p. 12/29Hypothetical Syllogism – ResolutionIntro to Discrete StructuresLecture 6 – p. 13/29Rules of Inference for Quantified StatementsUniversal instantiation∀xP (x)∴ P (c)Universal generalizationP (c) for an arbitrary c∴ ∀xP (x)Intro to Discrete StructuresLecture 6 – p. 14/29Rules 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 6 – p. 15/29Universal Modus PonensUniversal Modus Ponens∀x(P (x) → Q(x))P (a) , where a is a particular element in the domain∴ Q(a)Intro to Discrete StructuresLecture 6 – p. 16/29UMP in MathAssume that the statement“For all positive integers n, if n is greater than 4, then n2is less than 2n”is true. Use UMP to show that 1002< 2100.Intro to Discrete StructuresLecture 6 – p. 17/29Universal Modus TollensUniversal Modus Tollens∀x(P (x) → Q(x))¬Q(a) , where a is a particular element in the domain∴ ¬P (a)Intro to Discrete StructuresLecture 6 – p. 18/29Introduction to ProofsSome TerminologyAxiom (or Postulate)TheoremPropositionLemma (Lemmas or Lemmata)CorollaryProofConjectureIntro to Discrete StructuresLecture 6 – p. 19/29Proofs MethodsDirect ProofProof by Contraposition (or Indirect Proof)Proof by ContraditionProof by InductionIntro to Discrete StructuresLecture 6 – p. 20/29Direct ProofDefinition 1: The integer n is even if there exists an integerk such that n = 2k, and n is odd if there exists an integer ksuch that n = 2k + 1.Example 1: Give a direct proof of the theorem “If n is odd,then n2is odd.”Intro to Discrete StructuresLecture 6 – p. 21/29Direct ProofDefinition: An integer a is a perfect square if there is aninteger b such that a = b2.Example 2: Give a direct proof that if m and n are bothperfect squares, then nm is also a perfect square.Intro to Discrete StructuresLecture 6 – p. 22/29Indirect ProofExample 3: Prove that if n is an integer and 3n + 2 is odd,then n is odd.The direct approach does not work!Intro to Discrete StructuresLecture 6 – p. 23/29Indirect ProofExample 3: Prove that if n is an integer and 3n + 2 is odd,then n is odd.Use contraposition!∀n ∈ Nodd(3n + 2) → odd(n)Intro to Discrete StructuresLecture 6 – p. 24/29Indirect ProofExample 4: Prove that if n = ab, where a and b are positiveintegers, then a ≤√n and b ≤√n.Intro to Discrete StructuresLecture 6 – p. 25/29Proof StrategyWe have seen two important methods for provingtheorems of the form ∀x(P (x) → Q(x)) .These two methods arethe direct proof andthe indirect proofmethods.It takes some practice (solving homework problems) tolearn to recognize quickly the correct approach.Try first the direct approach. If it does not work then trythe indirect approach.Intro to Discrete StructuresLecture 6 – p. 26/29Direct or Indirect Proof?Definition: The real number r is rational if there existintegers p and q with q 6= 0 such that r = p/q.Example 7: Prove that the sum of two rational numbers isrational.Intro to Discrete StructuresLecture 6 – p. 27/29Direct or Indirect Proof?Example 8: Prove that if n is an integer and n2is odd, thenn is odd.Intro to Discrete StructuresLecture 6 – p. 28/29Proof by ContraditionWe can prove that p is true if we can show that¬p → (r ∨ ¬r) is true for some proposition r.Intro to Discrete StructuresLecture 6 – p.


View Full Document

UCF COT 3100 - Intro to Discrete Structures

Documents in this Course
Lab 1

Lab 1

11 pages

Functions

Functions

10 pages

Load more
Download Intro to Discrete Structures
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Intro to Discrete Structures and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Intro to Discrete Structures 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?