Discrete Structures 1 - Chapter 3: Formal Proofs PDF

DISCRETE STRUCTURES 1 Chapter 3  CHAPTER 3 FORMAL PROOFS Rules of Inference  Recognize and apply rules of inference. Inference – means deriving conclusions from evidences. Evidences are the premises, they are the assumptions. Rules of Inference are used to construct more complicate...

DISCRETE STRUCTURES 1 Chapter 3  CHAPTER 3 FORMAL PROOFS Rules of Inference  Recognize and apply rules of inference. Inference – means deriving conclusions from evidences. Evidences are the premises, they are the assumptions. Rules of Inference are used to construct more complicated valid arguments. Discrete Structures 1 1. Modus Ponens: Premises-statements that you’re allowed to assume. Conclusion-is the statement that you need to prove Corresponding Tautology: (p ∧ (p →q)) → q Discrete Structures 1 1. Modus Ponens: Corresponding Tautology: (p ∧ (p →q)) → q Let p be “It is snowing.” Let q be “I will study math.” “If it is snowing then I will study math.” “It is snowing.” “Therefore I will study math.” Discrete Structures 1 2. Modus Tollens : Premises-statements that you’re allowed to assume. Conclusion-is the statement that you need to prove Corresponding Tautology: ( ¬ q ∧ (p →q)) → ¬p Discrete Structures 1 1. Modus Tollens: Corresponding Tautology: ( ¬ q ∧ (p →q)) → ¬p Let p be “it is snowing.” Let q be “I will study math.” “If it is snowing, then I will study math.” “I will not study math.” “Therefore, it is not snowing.” Discrete Structures 1 3. Hypothetical Syllogism : Premises-statements that you’re allowed to assume. Conclusion-is the statement that you need to prove Corresponding Tautology: ( (p →q) ∧ ( q→r)) → (p→r) Discrete Structures 1 3. Hypothetical Syllogism : Corresponding Tautology: ( (p →q) ∧ ( q→r)) → (p→r) Let p be “It snows.” Let q be “I will study math.” Let r be “I will get an A.” “If it snows, then I will study math.” “If I study math, then I will get an A.” “Therefore, if it snows, I will get an A.” Discrete Structures 1 4. Disjunctive Syllogism : Premises-statements that you’re allowed to assume. Conclusion-is the statement that you need to prove Corresponding Tautology: ( ¬ p ∧ (p ∨q)) → q Discrete Structures 1 4. Disjunctive Syllogism : Corresponding Tautology: ( ¬ p ∧ (p ∨q)) → q Let p be “I will study math.” Let q be “I will study literature.” “I will study math or I will study literature.” “I will not study math.” “Therefore, I will study literature.” Discrete Structures 1 5. Simplification : Premises-statements that you’re allowed to assume. Conclusion-is the statement that you need to prove Corresponding Tautology: (p ∧q) → q Discrete Structures 1 5. Simplification : Corresponding Tautology: (p ∧q) → q Let p be “I will study math.” Let q be “I will study literature.” “I will study math and literature” “Therefore, I will study literature.” Discrete Structures 1 6. Addition: Premises-statements that you’re allowed to assume. Conclusion-is the statement that you need to prove Corresponding Tautology: p → (p ∨q) Discrete Structures 1 6. Addition: Corresponding Tautology: p → (p ∨q) Let p be “I will study math.” Let q be “I will visit Las Vegas.” “I will study math.” “Therefore, I will study math or I will visit Las Vegas.” Discrete Structures 1 7. Conjunction: Premises-statements that you’re allowed to assume. Conclusion-is the statement that you need to prove Corresponding Tautology: ( ( p) ∧ (q)) →(p ∧ q) Discrete Structures 1 7. Conjunction : Corresponding Tautology: ( ( p) ∧ (q)) →(p ∧ q) Let p be “I will study math.” Let q be “I will study literature.” “I will study math.” “I will study literature.” “Therefore, I will study math and literature.” Discrete Structures 1 Exercise Prove that premises 1 – 3 entails ¬J 1. R 2. R→D 3. D → ¬J 4. D 1, 2 Modus Ponens 5. ¬J 3, 4 Modus Ponens Discrete Structures 1 Exercise Prove that premises 1 – 3 entails ¬J 1. R 2. R→D 3. D → ¬J 4. R → ¬J 2, 3 Hypothetical Syllogism 5. ¬J 1, 4 Modus Ponens Discrete Structures 1 A direct proof of a conditional statement p → q first assumes that p is true, and uses axioms (something assumed to be true), definitions, previously proved theorems, with rules of inference, to show that q is also true The above targets to show that the case where p is true and q is false never occurs – Thus, p → q is always true Discrete Structures 1 Example: Show the sum of any consecutive numbers is odd. Definition 1: an integer number ‘n’ is even if and only if there exists an integer ‘k’ such that n=2k Definition 2: an integer number ‘n’ is odd if and only if there exists an integer ‘k’ such that n=2k + 1 Definition 3: two integers ‘a’ and ‘b’ are consecutive if and only if b=a+1 Discrete Structures 1 Example: Show the sum of any consecutive numbers is odd. If ‘a’ and ‘b’ are consecutive numbers then the sum of ‘a’ and ‘b’ is odd. Discrete Structures 1 The basic idea of a direct proof is p → q 1. Assume that p is true 2. Use p to show that q is true. Discrete Structures 1 Proof: Assume that ‘a’ and ‘b’ are consecutive. Know b=a + 1 (a + b) = a + (a + 1) = 2a + 1 Remember 2k + 1 Definition 2: An integer number ‘n’ is odd if and only if there exists an integer ‘k’ such that n=2k + 1 Discrete Structures 1 The idea here is that a proposition is either true or false, but not both. We use this to show p → q by assuming that both p and ¬ q are simultaneously true and deriving a contradiction. When we reach this contradiction, it means one of our assumptions can not be correct. Discrete Structures 1 Proof: Assume that ‘a’ and ‘b’ are consecutive integers. Assume that a + b is NOT odd. If a + b is not odd then no integer k such that (a+b)=2k + 1 (a + b) = a + (a + 1) = 2a + 1 Contradiction: a + b is not equal to 2k + 1 a + b = 2a + 1 Discrete Structures 1  Proof by Induction Proof by Contrapositive Proof by Contraposition Proof of Equivalences Proof by Cases Discrete Structures 1  CHAPTER 3 FORMAL PROOFS Formal Proofs of Validity  Construct mathematical proofs that are essential in formal specifications of software development. An argument is a sequence of statements that end with a conclusion. The argument is valid if the conclusion (final statement) follows from the truth of the preceding statements (premises). Discrete Structures 1 An argument in propositional logic is sequence of propositions. All but the final proposition are called premises and the final proposition is called the conclusion. An argument is valid if the truth of all its premises implies that the conclusion is true. Discrete Structures 1 A formal proof of validity is the process or the instance of establishing the validity of statement (conclusion) by derivation from other statements (given premises) in accordance to principles of reasoning / valid arguments forms. Discrete Structures 1 Note: 1. It is a formal procedure. 2. Validity of an argument is established by deduction or derivation. 3. Derivation will follow rules. Discrete Structures 1 Format: 1. p1 2. p2 3. p3 4.. Given 5. pn / ∴c 6. Newly derived statement 7. Newly derived statement 8. Newly derived statement Must be justified by rules 9.. 10. c Discrete Structures 1 Discrete Structures 1 If a proposition q is true whenever a list or set of statements p is true, we say that q is the semantic consequence of p. Symbolically: p |= q (semantic turnstile) Formal proof of validity shows in details how, for a given valid argument, the conclusion is a semantic consequence of the given premises. Premises|= Conclusion Discrete Structures 1 What is an argument form? It is an array of symbols which contain only statement variables. It is the underlying logical form or structure of an argument, or a group of arguments. The argument form represents the premises and conclusion schematically. When the statement variables are properly substituted by statements, the result is an argument. Discrete Structures 1 Example: Argument A 1. If the monsoon comes on time, prices will come down. 2. Monsoon will come on time 3. Therefore prices will come down. Argument B 1. If Manila is in the Philippines, Manila is in Asia 2. Manila is in the Philippines. 3. Therefore, Manila is in Asia. Discrete Structures 1 The two arguments exhibit the argument form: 1. p → q 2. p 3. ∴ q From the view point of formal logic, all the arguments are substitution instances of this argument form. Discrete Structures 1 Argument forms may be valid or invalid. Valid Argument Forms are argument forms that are valid by virtue of their form. Their substitution instances will be valid by virtue of the form. Example: Discrete Structures 1 Invalid Argument Forms are argument forms that are invalid by virtue of their form. Their substitution instances will be invalid by virtue of the form. Example: p→q ¬p _____ ∴¬q This argument form is invalid. Hence, all its substitution instances are invalid. Fallacy of denying the antecedent. Discrete Structures 1 Valid arguments are truth preserving: if started with truth, they protect the truth. Because of their truth preserving quality, some of the valid argument forms will be used as “RULES of derivation” in formal proof of validity. Discrete Structures 1