Formal LogicPredicate LogicInference RulesExamples: Proofs using Predicate LogicSlide 5Slide 6Slide 7Slide 8Temporary hypothesesMore ExamplesProving Verbal argumentsClass ExerciseClass exerciseFormal LogicMathematical Structures for Computer ScienceChapter 1Copyright © 2006 W.H. Freeman & Co. MSCS SlidesFormal LogicSection 1.4 Predicate Logic 2Predicate LogicSimilar to propositional logic for solving arguments, build from quantifiers, predicates and logical connectives.A valid argument for predicate logic need not be a tautology.The meaning and the structure of the quantifiers and predicates determines the interpretation and the validity of the argumentsBasic approach to prove arguments:Strip of quantifiersManipulate the unquantified wffsReinsert the quantifiersFour new inference rulesNote to remember: P(x) could be (y) (z) Q(x,y,z) Two rules to strip the qualifiers Two rules to reinsert the qualifiersSection 1.4 Predicate Logic 3Inference RulesFrom Can Derive Name / AbbreviationRestrictions on Use(x)P(x) P(t) where t is a variable or constant symbolUniversal Instantiation- uiIf t is a variable, it must not fall within the scope of a quantifier for t(x)P(x) P(t) where t is a variable or constant symbol not previously used in a proof sequenceExistential Instantiation- eiMust be the first rule used that introduces tP(x) (x)P(x)Universal Generalization- ugP(x) has not been deduced from any hypotheses in which x is a free variable nor has P(x) been deduced by ei from any wff in which x is a free variableP(x) or P(a) (x)P(x)Existential Generalization- egTo go from P(a) to (x)P(x), x must not appear in P(a)Section 1.4 Predicate Logic 4Examples: Proofs using Predicate LogicProve the following argument:All flowers are plants. Sunflower is a flower. Therefore, sunflower is a plant.P(x) is “ x is a plant”a is a constant symbol (Sunflower)Q(x) is “x is a flower”The argument is (x)[P(x)  Q(x)] Λ P(a)  Q(a)The proof sequence is as follows:•(x)[P(x)  Q(x)] hyp•P(a) hyp•P(a)  Q(a) 1, ui•Q(a) 2, 3, mpSection 1.4 Predicate Logic 5Examples: Proofs using Predicate LogicProve the argument (x)[P(x)  Q(x)] Λ [Q(y)]  [P(y)]Proof sequence:•(x)[P(x)  Q(x)] hyp•[Q(y)] hyp•P(y)  Q(y) 1, ui•[P(y)] 2, 3, mtProve the argument (x)P(x)  (x)P(x) Proof sequence:•(x)P(x) hyp•P(x) 1, ui•(x)P(x) 2, egSection 1.4 Predicate Logic 6Examples: Proofs using Predicate LogicProve the argument (x)[P(x)  Q(x)] Λ (x)P(x)  (x)Q(x)Proof sequence:•(x)[P(x)  Q(x)] hyp•(x)P(x) hyp•P(x)  Q(x) 1, ui•P(x) 2, ui : no restriction on ui about reusing a name•Q(x) 3, 4, mp•(x)Q(x) 5, ugNote: step 6 is legitimate since x is not a free variable in any hypothesis nor was ei used beforeSection 1.4 Predicate Logic 7Examples: Proofs using Predicate LogicProve the argument (x)[P(x) Λ Q(x)]  (x)P(x) Λ (x)Q(x)Proof sequence:•(x)[P(x) Λ Q(x)] hyp•P(x) Λ Q(x) 1, ui•P(x) 2, sim•Q(x) 2, sim•(x)P(x) 3, ug•(x)Q(x) 4, ug•(x)P(x) Λ ( x)Q(x) 5, 6, conSection 1.4 Predicate Logic 8Examples: Proofs using Predicate LogicProve the argument (y)[P(x)  Q(x,y)]  [P(x)  (y)Q(x,y)] Using the deduction method, we can derive(y)[P(x)  Q(x,y)] Λ P(x)  (y)Q(x,y)Proof sequence:•(y)[P(x)  Q(x,y)] hyp•P(x) hyp•P(x)  Q(x,y) 1, ui•Q(x,y) 2, 3, mp•(y)Q(x,y) 4, ugSection 1.4 Predicate Logic 9Temporary hypothesesA temporary hypothesis can be inserted into a proof sequence. If T is inserted as a temporary hypothesis and eventually W is deduced from T and other hypotheses, then the wff T  W has been deduced from other hypotheses and can be reinserted into the proof sequenceProve the argument [P(x)  (y)Q(x,y)]  (y)[P(x)  Q(x,y)] Proof sequence:•P(x)  (y)Q(x,y) hyp•P(x) temporary hypothesis•(y)Q(x,y) 1, 2, mp•Q(x,y) 3, ui•P(x)  Q(x,y) temp. hyp discharged•(y)[P(x)  Q(x,y)] 5, ugSection 1.4 Predicate Logic 10More ExamplesProve the sequence [(x)A(x)]  (x)[A(x)] To prove equivalence, implication in each direction should be provedProof sequence for [(x)A(x)]  ( x)[A(x)] •[(x)A(x)] hyp•A(x) temp. hyp•(x)A(x) 2, eg•A(x)  (x)A(x) temp. hyp discharged•[A(x)] 1, 4, mt•(x)[A(x)] 5, ugProof sequence for (x)[A(x)]  [(x)A(x)] •(x)[A(x)] hyp•(x)A(x) temp. hyp•A(a) 2, ei•[A(a)] 1, ui•[(x)[A(x)]] 3, 4, inc•(x)A(x)  [(x)[A(x)]] temp. discharged•[((x)[A(x)])] 1, dn•[(x)A(x)] 6, 7, mtSection 1.4 Predicate Logic 11Proving Verbal argumentsEvery crocodile is bigger than every alligator. Sam is a crocodile. But there is a snake, and Sam isn’t bigger than that snake. Therefore, something is not an alligator.Use C(x): x is a crocodile; A(x): x is an alligator, B(x,y): x is bigger than y, s is a constant (Sam), S(x): x is a SnakeHence prove argument (x) ( y)[C(x) Λ A(y)  B(x,y)] Λ C(s) Λ (x)(S(x) Λ [B(s,x)])  (x)[A(x)]•(x) (y )[C(x) Λ A(x)  B(x,y)] hyp•C(s) hyp•(x)(S(x ) Λ [B(s,x)]) hyp•(y)[C(s) Λ A(y)  B(s,y)] 1, ui•S(a) Λ [B(s,a)]) 3, ei•C(s) Λ A(a)  B(s,a) 4, ui•[B(s,a)] 5, sim•[C(s) Λ A(a)] 6, 7, mt•[C(s)] V [A(a)] 9, De Morgan•[[C(s)]] 2, dn•[A(a)] 9, 10, ds•(x)[A(x)] 11, egSection 1.4 Predicate Logic 12Class ExerciseProve the argument (x)[(B(x) V C(x))  A(x)]  (x)[B(x)  A(x)] Proof sequence:1. (x)[(B(x) V C(x))  A(x)] hyp2. (B(x) V C(x))  A(x) 1, ui3. B(x) temp. hyp4. B(x) V C(x) 3, add5. A(x) 2, 4, mp6. B(x)  A(x ) temp. hyp discharged7. (x)[B(x)  A(x)] 6, ugSection 1.4 Predicate Logic 13Class exerciseEvery ambassador speaks only to diplomats, and some ambassadors speak to someone. Therefore, there is a diplomat.Use A(x): x is an ambassador; S(x,y): x speaks to y; D(x): x is a diplomatProof Sequence:1. (x) (y)[(A(x) Λ S(x,y))  D(y)] hyp2. (x)(y )(A(x ) Λ S(x, y)) hyp3. (y)((A(a ) Λ S(a,y))  D(y)) 1, ui4. (y)(A(a) Λ S(a,y)) 2, ei5. A(a) Λ S(a,b) 4, ei6. (A(a) Λ S(a,b))  D(b) 3, ui7. D(b) 5, 6, mp8. (x)D(x) 7, egProve the