Predicate Calculus Subject Predicate John went to the store The sky is blue Propositional Logic uses statements Predicate Calculus uses predicates predicates must be applied to a subject in order to be true or false P x means this predicate represented by P applied to the object represented by x Quantification x There exists an x x For all x s Domain set where these subjects come from x Z There exists an x in the integers x R For all x s in the reals 1 Translation A student of mine is wearing a blue shirt Domain people who are my students S Quantification There is at least one Predicate wearing a blue shirt x S such that B x where B x represents wearing a blue shirt My students are in class Domain people who are my students S Quantification All of them Predicate are in class x S such that C x where C x represents being in class Negation of Quantified Statements x people such that H x x people such that H x There is a person who is here For all people each person is not here same in meaning as There is no person here x people such that H x x people such that H x For all people each person is here There is at least one person who is not here 2 Multiple Predicate Translation A student of mine is wearing a blue shirt Domain all people P Quantification There is at least one Predicates wearing a blue shirt and is my student x P such that B x S x B x represents wearing a blue shirt S x represents being my student My students are in class Domain all people P Quantification All of them Predicates are in class and is my student x P such that S x C x C x represents being in class S x represents being my student Multiple Quantification p P c C S c p c C p P S c p p P c C S c p c C p P S c p where C all chairs and P all people and S c p represents p sitting in c 3 Mixed Multiple Quantification c C p P S c p p P c C S c p p P c C S c p c C p P S c p where C all chairs and P all people S c p represents p sitting in c Negations of Multiply Quantified Statements c C p P S c p c C p P S c p where C all chairs and P all people S c p represents p sitting in c 4 Other Variations Exactly one child attends school Other Variations Exactly one child attends school c C s S A c s p C b S p c A p b c C s S A c s p C b S p c v A p b 5 Other Variations Exactly one child attends school c C s S A c s p C b S p c A p b c C s S A c s p C b S p c v A p b At most 1 child attends school Other Variations Exactly one child attends school c C s S A c s p C b S p c A p b c C s S A c s p C b S p c v A p b At most 1 child attends school c p C s b S A c s A p b c p 6 Other Variations Exactly one child attends school c C s S A c s p C b S p c A p b c C s S A c s p C b S p c v A p b At most 1 child attends school c p C s b S A c s A p b c p At least 2 children attend school Other Variations Exactly one child attends school c C s S A c s p C b S p c A p b c C s S A c s p C b S p c v A p b At most 1 child attends school c p C s b S A c s A p b c p At least 2 children attend school c p C s b S A c s A p b p c 7 Degenerate or Vacuous Cases s B s all my students are wearing blue B s student s is wearing blue s c I s c s c I s c c s I s c I s c student s is in class c If there are no students Variants of Quantified Conditional Statements Statement x D P x Q x Contrapositive x D Q x P x Converse x D Q x P x Inverse x D P x Q x Also applies to Existentially Quantified Conditional Statements 8 Euler Diagrams Circles used to tell Truth Sets for the predicate Where the predicate applied to a object is true A dot is used to tell a specific instance If all then a completely contained circle If some then an overlapping circle All college students are brilliant Some poets are unsuccessful All brilliant people are scientists Some athletes are unsuccessful All college students are scientists Some poets are athletes U S P B C OR U A P A Rules of Inference for Quantified Statements Universal Modus Ponens Universal Modus Tollens x D P x Q x P a a D Q a x D P x Q x Q a a D P a Universal Instantiation Existential Generalization x D P x a D P a P c c D x D P x 9 Rules that DON T exist or need more clarification Existential Modus Ponens Doesn t exist Existential Modus Tollens Doesn t exist Universal Generalization P a x D P x only if a is completely arbitrary in the domain Existential Instantiation x D P x P a only if a is completely arbitrary in the domain Errors in Deduction Converse Error Inverse Error x D P x Q x Q a P a x D P x Q x P a Q a Called Asserting Called Denying the Consequence the Hypothesis 10 Easy Formal Direct Proofs by Deduction x D P x Q x Q a where a D therefore x D P x x D P x Q x x D R x P x P b where b D therefore Q b R b More Formal Direct Proofs by Deduction x D P x Q x x D P x v R x P b where b D therefore x D Q x R x x D P x Q x y D P y R y z D Q z therefore x D R x 11 A c s child c attends school s c s A c s find one child school combo which makes it true one child attends some school somewhere …
View Full Document
Unlocking...