Assignment 3: Logic

Introduction

This assignment does not involve any programming; it's a set of exercises to develop your understanding of logic. You should submit your homework as a single PDF via Sakai.

Propositional Logic

Question 1 (10 points)  We have discussed the binary connectives AND, OR, IF and IFF. How many binary connectives are possible? (Think about the number of functions from two inputs to one binary output.) Prove that AND, OR, and negation are sufficient, i.e., that any other connective can be replaced by a combination of these.

Question 2 (10 points) Do problem 7.14, noting that "Horn form" refers to a collection of (implicitly conjoined) Horn clauses.

Predicate Logic

Question 3 (10 points)

1. Write out the following statements in first order logic:
   • All birds can fly.
   • Tweety is a penguin.
   • All penguins are birds.
   using predicates penguin(), fly(), and bird().
2. Convert your first order logic sentences to canonical form.
   
3. Provide a resolution proof that tweety can fly. For your resolution proof, please use the proof tree form shown in Figure 9.11 (or 9.12) in the textbook.

Question 4 (10 points)

1. Augment your knowledge base from the previous problem with the following:
   • Penguins cannot fly
   • Barak Obama has a US birth certificate
   using the predicate has_us_birth_certificate() or hubc() for short.
2. Convert the new sentences that you've added to canonical form.
3. Provide a resolution proof that Barak Obama was born in Kenya. You can use born_in_kenya() or bic() as a predicate.

Question 5 (10 points) This question is about propositionalizing (see page 324, and note that we have no function symbols for this question). Consider your knowledge base for question 3, and assume that there are just 10 objects in the universe (tweety plus 9 more).

1. Derive an expression for the number of predicates that would be created if we propositionalized all quantified statements in the knowledge base.
2. What proposition would you need to prove to determine if all penguins can fly?