Predicate Logic and Proofs in CSE 311

Slide Note
Embed
Share

Explore the translation of statements into predicate logic, learn about inference proofs and nested quantifiers, and delve into the application of logical thinking in real-world scenarios. Discover a new way of constructing proofs and understand notation laws of inference. Engage in interactive proofs and practice arguments to strengthen your understanding. Don't miss out on the experimental logical thinking challenges in HW2!


Uploaded on Nov 28, 2024 | 0 Views


Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript


  1. Warm up translate to predicate logic: For every ?, if ? is prime, then ? is odd or ? = 2. Inference Proofs and Nested Unalike Quantifiers CSE 311 Spring 2022 Lecture 6

  2. Announcements HW2 came out on Wednesday (available on the webpage). The last problem is about logical thinking in the real world. It s an experiment! We haven t given this type of problem in 311 before. Please bear with us as we figure out how to word these questions.

  3. Today A lecture in 2 parts. Part 1: A new way of thinking of proofs: Here s one way to get an iron-clad guarantee: 1. Write down all the facts we know. 2. Combine the things we know to derive new facts. 3. Continue until what we want to show is a fact. Part 2: , in the same sentence.

  4. Notation Laws of Inference We re using the symbol A LOT. Too much Some new notation to make our lives easier. If we know both both ? and ? ?,? We can conclude any (or all) of ?,? ?,? means therefore I knew ?,? therefore I can conclude ?,?. ? ?,? Modus Ponens, i.e. ? ? ? ?), in our new notation. ?

  5. Another Proof Let s keep going. I know If it is raining then I have my umbrella and I do not have my umbrella I can conclude It is not raining! What s the general form? How do you think the proof will go? If you had to convince a friend of this claim in English, how would you do it? [(? ?) ?] ?

  6. A proof! We know ? ? and ?; we want to conclude ?. Let s try to prove it. Our goal is to list facts until our goal becomes a fact. We ll number our facts, and put a justification for each new one.

  7. A proof! We know ? ? and ?; we want to conclude ?. Let s try to prove it. Our goal is to list facts until our goal becomes a fact. We ll number our facts, and put a justification for each new one. Given Given Contrapositive of 1. Modus Ponens on 3,2. 1. ? ? 2. ? 3. ? ? 4. ?

  8. Try it yourselves Suppose you know ? ?, ? ?,and ?. Give an argument to conclude ?. pollev.com/uwcse311 Help me adjust my explanation

  9. Try it yourselves Suppose you know ? ?, ? ?,and ?. Give an argument to conclude ?. Given Given Given Modus Ponens 1,3 Contrapositive of 2 Modus Ponens 5,4 1. ? ? 2. ? ? 3. ? 4. ? 5. ? ? 6. ?

  10. More Inference Rules We need a couple more inference rules. These rules set us up to get facts in exactly the right form to apply the really useful rules. A lot like commutativity and distributivity in the propositional logic rules. I know the fact ? ? ? ? Eliminate I can conclude ? is a fact and ? is a fact separately separately. ?,?

  11. More Inference Rules In total, we have two for and two for , one to create the connector, and one to remove it. ? ? Eliminate ?;? Intro ? ? ?,? ? ? ?, ? Intro Eliminate ? ?,? ? ? None of these rules are surprising, but they are useful.

  12. The Direct Proof Rule We ve been implicitly using another rule today, the direct proof rule Write a proof given ? conclude ? ? ? Direct Proof rule ? ? ? ? This rule is different from the others ? ?is not a single fact. It s an observation that we ve done a proof. (i.e. that we showed fact ? starting from ?.) We will get a lot of mileage out of this rule starting next time.

  13. Caution Be careful! Logical inference rules can only be applied to entire They cannot be applied to portions of a statement (the way our propositional rules could). Why not? Suppose we know ? ?, ?. Can we conclude ?? Given Given Introduce (1) Introduce (2) Modus Ponens 3,4. entire facts. 1. ? ? ? Intro 2. ? ? ?,? ? 3. ? ? ? 4. ? ? 5. ?

  14. One more Proof Show if we know: ?,?, ? ? ? ? ,? ? we can conclude ?.

  15. One more Proof Show if we know: ?,?, ? ? ? ? ,? ? we can conclude ?. Given Given Given Given Intro (1,2) Modus Ponens (3,5) Eliminate (6) Modus Ponens (4,7) 1. ? 2. ? 3. [ ? ? ? ? ] 4. ? ? 5. ? ? 6. ? ? 7. ? 8. ?

  16. Inference Rules ? ? ? ? Eliminate Direct Proof rule ?,? ? ? ? ?, ? ? ?;? Eliminate Modus Ponens ? ? ?;? Intro You can still use all the propositional logic equivalences too! ? ? ? Intro ? ?,? ?

  17. Quantifiers

  18. Quantifiers (for A All) and (there E Exists) Write these statements in predicate logic with quantifiers. Let your domain of discourse be cats This sentence implicitly makes a statement about all cats! If a cat is fat, then it is happy. ?[Fat ? Happy ? ]

  19. Quantifiers Writing implications can be tricky when we change the domain of discourse. For every cat: if the cat is fat, then it is happy. Domain of Discourse: cats What if we change our domain of discourse to be all mammals? We need to limit ? to be a cat. How do we do that? ?[Fat ? Happy ? ] ?[(Cat ? Fat ? ) Happy ? ] ?[Cat ? (Fat ? Happy ? )]

  20. Quantifiers Which of these translates For every cat: if a cat is fat then it is happy. when our domain of discourse is mammals ? ?[(Cat ? Fat ? ) Happy ? ] ?[Cat ? (Fat ? Happy ? )] For all mammals, if ? is a cat and fat then it is happy [if ? is not a cat, the claim is vacuously true, you can t use the promise for anything] For all mammals, that mammal is a cat and if it is fat then it is happy. [what if ? is a dog? Dogs are in the domain, but uh-oh. This isn t what we meant.] To limit variables to a portion of your domain of discourse under a universal quantifier add a hypothesis to an implication.

  21. Quantifiers Existential quantifiers need a different rule: To limit variables to a portion of your domain of discourse under an existential quantifier AND the limitation together with the rest of the statement. There is a dog who is not happy. Domain of discourse: dogs ?( Happy(?))

  22. Quantifiers Which of these translates There is a dog who is not happy. when our domain of discourse is mammals ? ?[(Dog ? Happy ? ] ?[Dog ? Happy ? )] There is a mammal, such that if ? is a dog then it is not happy. [this can t be right plug in a cat for ? and the implication is true] There is a mammal that is both a dog and not happy. [this one is correct!] To limit variables to a portion of your domain of discourse under an existential quantifier AND the limitation together with the rest of the statement.

  23. Negating Quantifiers What happens when we negate an expression with quantifiers? What does your intuition say? Negation Original Every positive integer is prime There is a positive integer that is not prime. ?( Prime(?)) Domain of discourse: positive integers ? Prime(?) Domain of discourse: positive integers

  24. Negating Quantifiers Let s try on an existential quantifier Original Negation Every positive integer is composite or odd. There is a positive integer which is prime and even. ?( Prime ? Even ? ) Domain of discourse: positive integers ?(Prime ? Even ? ) Domain of discourse: positive integers To negate an expression with a quantifier 1. Switch the quantifier ( becomes , becomes ) 2. Negate the expression inside

  25. Negation Translate these sentences to predicate logic, then negate them. All cats have nine lives. ? ??? ? ???????? ?,9 ?(??? ? ???????? ?,9 ) There is a cat without 9 lives. All dogs love every person. ? ? ??? ? ?????(?) ???? ?,? ? ?(??? ? ????? ? ???? ?,? ) There is a dog who does not love someone. There is a dog and a person such that the dog doesn t love that person. There is a cat that loves someone. ? ?(??? ? ????? ? ????(?,?) ? ?(??? ? ????? ? ???? ?,? ) For every cat and every human, the cat does not love that human. Every cat does not love any human ( no cat loves any human )

  26. Negation with Domain Restriction ? ?(??? ? ????? ? ????(?,?) ? ?([??? ? ????? ? ] ???? ?,? ) There are lots of equivalent expressions to the second. This one is by far the best because it reflects the domain restriction happening. How did we get there? There s a problem in this week s section handout showing similar algebra.

  27. Nested Quantifiers

  28. Nested Quantifiers Translate these sentences using only quantifiers and the predicate AreFriends(?,?) Everyone is friends with someone. Someone is friends with everyone.

  29. Nested Quantifiers Translate these sentences using only quantifiers and the predicate AreFriends(?,?) Everyone is friends with someone. Someone is friends with everyone. ?( ? AreFriends(?,?)) ?( ? AreFriends(?,?)) ? ? AreFriends(?,?) ? ? AreFriends(?,?)

  30. Nested Quantifiers ? ? ?(?,?) For every ? there exists a ? such that ? ?,?is true. ? might change depending on the ? (people have different friends!). ? ? ?(?,?) There is an ? such that for all ?,?(?,?)is true. There s a special, magical ? value so that ? ?,? is true regardless of ?.

  31. Nested Quantifiers Let our domain of discourse be {?,?,?,?,?} And our proposition ?(?,?) be given by the table. What should we look for in the table? ? A A B B C C D D E E ?(?,?) A A T T T T T B B T F F T F ? ?? ?,? C C F T F F F ? D D F F F F T ? ??(?,?) E E F F F T F

  32. Nested Quantifiers Let our domain of discourse be {?,?,?,?,?} And our proposition ?(?,?) be given by the table. What should we look for in the table? ? A A B B C C D D E E ?(?,?) A A T T T T T B B T F F T F ? ?? ?,? A row, where every entry is T C C F T F F F ? D D F F F F T ? ??(?,?) In every row there must be a T E E F F F T F

  33. Keep everything in order Keep the quantifiers in the same order in English as they are in the logical notation. There is someone out there for everyone is a ? ? statement in everyday English. It would never never be phrased that way in mathematical English We ll only every write for every person, there is someone out there for them.

  34. Try it yourselves Every cat loves some human. There is a cat that loves every human. Let your domain of discourse be mammals. Use the predicates Cat(?), Dog(?), and Loves(?,?) to mean ? loves ?.

  35. Try it yourselves Every cat loves some human. There is a cat that loves every human. ? (Cat ? ?[Human(?) Loves(?,?)]) ? ?(Cat ? [Human(?) Loves(?,?)]) ? (Cat ? ?[Human ? Loves(?,?)]) ? ?(Cat ? [Human(?) Loves(?,?)])

  36. Negation How do we negate nested quantifiers? The old rule still applies. To negate an expression with a quantifier 1. Switch the quantifier ( becomes , becomes ) 2. Negate the expression inside ( ? ? ? ? ?,? ? ?,? ) ?( ? ? ? ?,? ? ?,? ) ? ?( ? ? ?,? ? ?,? ) ? ? ?( ? ?,? ? ?,? ) ? ? ?[ ? ?,? ? ?,? ]

  37. More Translation For each of the following, translate it, then say whether the statement is true. Let your domain of discourse be integers. For every integer, there is a greater integer. ? ?(Greater(?,?))(This statement is true: ? can be ? + 1 [? depends on ?]) There is an integer ?, such that for all integers ?, ?? is equal to 1. ? ?(Equal(??,1))(This statement is false: no single value of ? can play that role for every ?.) ? ?(Equal ? + ?,1 ) For every integer, ?, there is an integer ? such that ? + ? = 1 (This statement is true, ? can depend on ?)

More Related Content