Assignment 3: Propositional Consequence

Assignment 3:

1 Propositional Consequence (10 points)
For each of the following entailment relations, say whether or not it is true. The text on the
left of the entailment symbol (|=) represents one or more sentences (separated by commas) that
constitute a knowledge base.
A knowledge base (KB) entails a sentence (S), KB |= S, if and only if the model of KB is a
subset of the model of S, i.e. M(KB) ⊆ M(S). You can check this using a truth table. An entailment
holds when for any assignment of variables where KB evaluates to True, S is also True.
1. A ∧ B |= B
2. A ∨ B |= A
3. ¬A |= ¬¬A
4. ¬A |= A =⇒ B
5. A ∧ (A =⇒ B) |= B
2 English to FOL (30 points)
Translate the following English sentences into first order logic, describing the intended meaning
of any non-obvious predicates. Feel free to optionally provide a more direct paraphrase of the
meaning of your logic expression in English. If you think a sentence is ambiguous, describe the
ambiguity and give logical expressions for all interpretations. You may use a notation with simple
ASCII characters for logical operators (e.g., A:∀, E:∃, =>: =⇒ , <=>: ⇐⇒ , ∧:∧, v:∨, :¬, >:>)
1. Everything is bitter or sweet.
2. Either everything is bitter or everything is sweet.
3. Everyone likes Mary, except Mary herself.
4. There is at least one person who likes Mary.
5. There is exactly one person other than Mary who likes Mary.
6. If anyone can do it, Jones can.
7. If Jones can do it, anyone can.
2
8. Roger will go out if and only if it is not raining.
9. An ancestor of an ancestor is an ancestor.
10. There is no greatest natural number.
3 Resolution Proof (60 points)
3.1 Proof 1 (30 points)
Given the following statements, all of which are assumed to be true:
• If you eat ice cream and you get sick then you are lactose intolerant.
• You eat ice cream.
• You get sick.
1. Convert these statements to propositional expressions. (10 points)
3
2. Convert these expressions into a single conjunctive normal form statement. (10 points)
3. Prove, using resolution by refutation that “You are lactose intolerant” is true. (10 points)
4
3.2 Proof 2 (30 points)
Given the following statements, all of which are assumed to be true:
• If it rains, Joe brings his umbrella.
• If Joe has an umbrella, he doesn’t get wet.
• If it doesn’t rain, Joe doesn’t get wet.
1. Convert these statements to propositional expressions. (10 points)
2. Convert these expressions into a single conjunctive normal form statement. (10 points)
5
3. Prove, using resolution by refutation that “Joe doesn’t get wet.” is true. (10 points)
6