1Predicate Calculus• Subject / PredicateJohn / 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 xQuantification• ∃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 reals2Translation• 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.3Multiple 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"4Mixed 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"5Other Variations• Exactly one child attends schoolOther 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)]6Other 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 schoolOther 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=p7Other 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 schoolOther 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 ≠≠≠≠ c8Degenerate 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 QuantifiedConditional 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 Statements9Euler 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 Some poets are unsuccessful.Some athletes are unsuccessful. ∴Some poets are athletes.All college students are brilliant.All brilliant people are scientists.∴All college students are
View Full Document
Unlocking...