Homework 3 - Logic

EECS 592 
Homework 3 - Logic

Instructions:
This assignment must be submitted electronically via Canvas. If you want to do it by hand (pen/pencil
and paper), scan it and submit a .pdf.
This is an individual assignment, do not discuss, or share any answers with other students. Late
submissions will be accepted up to 3 days, with a 10% penalty per day.
1. Evaluating Logical Statements (10 points)
State whether each of the following statements is true or false and provide a simple explanation why.
A. (A ∧ B) ⊨ (A ⇔ B)
B. (A ⇔ B) ⊨ (A ∨ B)
C. (A ∧ B) ⇒ C ⊨ (A ⇒ C) ∨ (B ⇒ C)
D. (A ∨ B) ∧ ( ¬C ∨ ¬D ∨ E) ⊨ (A ∨ B) ∧ (¬D ∨ E)
E. (C ∨ (¬A ∧ ¬B) ) ≡ ( (A ⇒ C) ∧ (B ⇒ C) )
F. For 2 sentences α and β: α ⊨ β if and only if ( α ⇒ β ) is valid
G. For 2 sentences α and β: α ≡ β if and only if ¬( α ⇔ β ) is unsatisfiable
1
H. The following sentence is valid: (¬B ⇒ A) ⇒ (¬A ⇒ ¬B)
I. The following sentence is satisfiable:(A ∧ B) ∧ ¬(A ⇒ B)
J. The following sentence is unsatisfiable: (A ⇔ B) ∧ ( ¬A ∨ B)
2
2. Conjunctive Normal Form + Resolution (8 points)
A. Convert the following sentences into Conjunctive Normal Form:
● D ∧ ¬B ⇒ E
● A ∧ C ∧ D ⇒ F
● A ∧ (D ∨ F) ⇒ C
● F ⇔ ¬B
B. Add the following two sentences to the sentences from part A:
● A
● D
Prove that E is true using resolution (show each individual resolution step with the 2 clauses
involved and the new clause that is produced).
3
3. First-Order Logic Quantifiers (6 points)
This problem involves translating between English and FOL in a pizza domain. This domain will have
the following predicates:
● Crust(c) - the type of pizza crust, valid constants are { Thin, Thick, Stuffed }
● Topping(t) - an pizza topping, valid constants are { Peperoni, Mushrooms, Anchovies }
● Person(p) - various people, valid constants are { Ann, Bruce, Christine }
● GoesWith(t, c) - Whether a topping t goes with a crust c
● Likes(p, c, t) - Whether person p likes crust c with topping t
Translate the following sentences into FOL:
A. " Peperoni goes with any pizza crust"
B. "There is a topping that goes with stuffed crust"
C. "Every crust type has at least one topping that goes with it"
Translate the following into natural English sentences:
D. ∀ c, Crust(c) ⇒ ¬Likes(Ann, c, Mushrooms)
E. ∀ p, Person(p) ⇒ ∃ t, Topping(t) ∧ Likes( p, Thin, t )
F. ∃ p, Person(p) ∧ ∀ t, Topping(t) ⇒ Likes(p, Thick, t)
4
4. First-Order Logic Semantics (6 points)
Suppose you were creating a knowledge base with information about US coins. Consider the
statement "A quarter is worth more than a penny, nickel, or dime." Suppose you were going to encode
this information as a sentence in a knowledge base using First-Order Logic. Show what sentence you
would need under the two different semantics described below. Use the constants Penny, Nickel,
Dime, and Quarter and the predicate WorthMore(x, y). (E.g. WorthMore(Dollar, Quarter)).
A. How would you write this as a FOL sentence for a KB that uses database semantics? That is, it
uses the unique-names, closed-world, and domain closure assumptions.
B. How would you have to write this as a FOL sentence for a KB that has regular FOL semantics
(has none of the above assumptions)?
5. Unification (4 points)
For each pair of sentences, give the most general unifier if it exists. If it does not, explain why. Note
that all constants are uppercase letters and all variables are lowercase letters.
A. P( A, B, B ) P( x, y, z )
B. P( y , G( A, B ) ) P( G( x, x ), y )
C. P( F(x), x ) P( F( y ), A )
D. P( F(A), A, z ) P( F( x ), y, G( B ) )
6. Resolution Refutation (16 points)
5
We are given a knowledge base with the following assertions:
1) All wolves howl.
2) Anyone who has cats as pets will not have mice.
3) Anyone who is a light sleeper can’t live near anything that howls.
4) Frank either has cats or lives near wolves.
5) If Frank is a light sleeper, Frank has mice.
Use the following relations to write the above sentences in FOL, then convert all the sentences to
CNF (2 points each):
 Wolf(x) – x is a wolf
 Howl(x) – x howls
 Have(x,y) – x has y
 Cat(y) – y is a cat
 Mouse(z) – z is a mouse
 LS(x) – x is a light sleeper
 Near(x,y) – x lives near y
Now use resolution refutation to prove that Frank is not a light sleeper. (6 points)
Score summary:
1. Evaluating Logical Statements ____/10
2. Conjunctive Normal Form + Resolution ____/8
3. First-Order Logic Quantifiers ____/6
4. First-Order Logic Semantics ____/6
5. Unification ____/4
6. Resolution Refutation ____/16
Total ____/50
6