Transcript PPT
Chapter 2: The Logic of Quantified Statements. Predicate Calculus 2.3 Arguments with Quantified Statements Instructor: Hayk Melikya Introduction to Abstract Mathematics [email protected] 1 Argument #1 Universal instantiation Universal instantiation is the fundamental tool for deductive reasoning All men are mortal. Socrates is a man. Therefore, Socrates is mortal (xU)P(x)├ P(a) Introduction to Abstract Mathematics 2 Arguments with Quantified Statements Definition: An argument form is valid if no matter what particular predicates are substituted for predicate symbols in it promises, if resulting promise statements are true, then the conclusion is also true An argument is called valid iff its form is valid Rule of universal instantiation: if some property is true of everything in the domain, then this property is true for any subset in the domain Universal Modus Ponens: Premises: (x, if P(x) then Q(x)); (major) – P(a) for some a (minor) Conclusion: Q(a) Premises: (x, if P(x) then Q(x)); Conclusion: ~P(a) Universal Modus Tollens: ~Q(a) for some a Converse and inverse errors Introduction to Abstract Mathematics 3 Validity of Arguments using Diagrams Premises: All human beings are mortal; Zeus is not mortal. Conclusion: Zeus is not a human being Premises: All human beings are mortal; Felix is mortal. Conclusion: Felix is a human being Premises: No polynomial functions have horizontal asymptotes; This function has a horizontal asymptote. Conclusion: This function is not a polynomial Introduction to Abstract Mathematics 4 Diagrams for Validity (p. 104) mortal pneumonia human fever Socrates patient Diagrams can sometimes be used to: – support a validity of an argument – or, show that an argument is invalid Diagrams are not a formal proof! Introduction to Abstract Mathematics 5 Predicate Calculus Validity Propositional validity A B B A True no matter what the truth values of A and B are Predicate calculus validity z [Q(z) P(z)] → [x.Q(x) y.P(y)] True no matter what • the Domain is, • or the predicates are. That is, logically correct, independent of the specific content. Introduction to Abstract Mathematics 6 Arguments with Quantified Statements Universal instantiation: Universal modus ponens: Universal modus tollens: Introduction to Abstract Mathematics 7 ├ (xU)P(x) To prove a theorem of the form (xU)P(x) which states “for all elements x in a given universe U, the proposition P(x) is true” we select an arbitrary aU from the universe, and then prove the assertion P(a) . Let a be an arbitrary constant from the universe U. If P(a) contains no particular constant from U then P(a)├ (xU)P(x) This is called Universal Generalization Introduction to Abstract Mathematics 8 Example 1 (Universal Direct Proof) Show that all integers divisible by 6 are even. Proof: In the language of predicate logic, we write (x Z) ( 6 divides x x is even) where Z = {0,±1,± 2,...} is the universe of integers. Letting a be an integer, we assume a is divisible by 6, which means there exists an integer y which satisfies a = 6y . Rewriting this as a= 2(3y) we have a = 2k for some integer k = 3y , which proves that a is an even integer. ▌ Introduction to Abstract Mathematics 9 Universal Instantiation (UI) (xU)P(x)├ P(a) If a is an arbitrary constant from the universe U then (xU)P(x)├ P(a) This is refered as Universal Instantiation rule. Existential Instantiation (EI) (xU)P(x)├ P(a) where a is a paricular contant from univers Existantial Generalization(EG) P(a) ├ (xU)P(x) This rule says that if P(a) true for some constan from the universe U then (xU)P(x) is true Introduction to Abstract Mathematics 10 ├ (xU)P(x) To prove a theorem of the form (xU)P(x) which states “there exists an element x in a given universe U that satisfies the proposition P(x) ” the strategy is to show one or more elements xU satisfy the assertion P(x). Example 2 (Proof by Demonstration or construction) Show there exists an even prime integer. Proof: In language of predicate logic, we would write (x N)(x is even x is prime) The proof is simple because 2 is both prime and even Introduction to Abstract Mathematics 11 Proof of (x)P(x) by Contradiction: To prove the theorem (x)P(x) which says “for all x , P(x) is true” by contradiction, assume the contrary; i.e. ~(x)P(x) which is equivalent to (x) ~P(x) , which says “there exists an x such that P(x) is not true”. One then continues the Proof until arriving at a contradiction. Introduction to Abstract Mathematics 12 Example 4: (Proof by Contradiction) Show if m, n are integers, then 5m+ 20n 1. Proof: In the language of predicate logic this theorem becomes (mZ)( nZ) (5m+ 20n 1). Assuming the contrary, we have (mZ)( nZ) (5m+ 20n = 1). But the equation 5m+ 20n = 1 cannot hold since 5 divides the left side of the equation and not the right. Hence, the denial is false so the theorem is true. ▌ Introduction to Abstract Mathematics 13 Proof of (x)P(x) by Contradiction: To prove “there exists an x such that P(x) is true” assume the theorem is not true: i.e. ~(x) P(x) (x) ~P(x) which states“for all x the assertion P(x) is not true. You then continue the proof until you arrive at a contradiction of some kind. Introduction to Abstract Mathematics 14 Proving Unique Existential Theorems: To prove a theorem of the form (!x U )P(x) which states “there exists a unique element x such that P(x) is true” the strategy is to show first that some element x satisfies P(x) , then show that if two elements y, z U satisfy the assertion, then in fact they are the same; i.e. y = z. In predicate logic language, we must show (xU )P(x) (yU )(zU )[P( y) P(z) y = x] Introduction to Abstract Mathematics 15 Important Relations in Predicate Logic a) (x)(y)P(x, y) (y)(x)P(x, y) b) (x)(y)P(x, y) (y)(x)P(x, y) c) (x)[P(x) Q(x)] [ (x)P(x) (x)Q(x) ] d) (x)[P(x) Q(x)] [(x)P(x) (x)Q(x)] e) [(x)P(x) (x)Q(x)] (x)[P(x) Q(x)] f) (x)(y)P(x, y) (y)(x)P(x, y) Introduction to Abstract Mathematics 16 Not Valid z [Q(z) P(z)] → [x.Q(x) y.P(y)] Proof: Give countermodel, where z [Q(z) P(z)] is true, but x.Q(x) y.P(y) is false. Find a domain, and a predicate. In this example, let domain be integers, Q(z) be true if z is an even number, i.e. Q(z)=even(z) P(z) be true if z is an odd number, i.e. P(z)=odd(z) Validity z [Q(z) P(z)] → [x.Q(x) y.P(y)] Proof strategy: We assume z [Q(z) P(z)] and prove x.Q(x) y.P(y) Introduction to Abstract Mathematics 17 Proof and Logic We prove mathematical statement by using logic. P Q, Q R , R P PQ R not valid To prove something is true, we need to assume some axioms! This is invented by Euclid in 300 BC, who begins with 5 assumptions about geometry, and derive many theorems as logical consequences. Introduction to Abstract Mathematics 19 Validity of Arguments Hence validity of arguments is defined in the same way The difference is: – in predicate logic it is not always possible to go through all interpretations to prove that P logically implies Q Why? – The number of interpretations can be infinite Thus, proving arguments with inference rules becomes the method of choice We can also derive new inference rules for our toolbox Introduction to Abstract Mathematics 20 Power and Limits of Logic Good news: Gödel's Completeness Theorem That is, starting from a few propositional & simple predicate validities, every valid assertion can be proved using just universal generalization and modus ponens repeatedly! Thm : Given a set of axioms, there is no procedure that decide whether quantified assertions are valid. (unlike propositional formulas) Gödel's Incompleteness Theorem for Arithmetic Thm: For any “reasonable” theory that proves basic arithemetic truth, an arithmetic statement that is true, but not provable in the theory, can be constructed. No hope to find a complete and consistent set of axioms! Introduction to Abstract Mathematics 21 Practice problems 1. 2. 3. Study the Sections 3.3 and 3.4 from your textbook. Be sure that you understand all the examples discussed in class and in textbook. Do the following problems from the textbook: Exercise 3.3 # 1, 11, 16, 19, 21, 24, 30, 41, 55, 57. Exercise 3.4 # 1, 4, 11, 14, 22, 26, 32, 34. Introduction to Abstract Mathematics 22