CSC 411: Artificial Intelligence

(Fall 2006)

Assignment 1: Chapters 1 and 2

Due by September 19, Tuesday, 2006

1. Create and justify your own definition of artificial intelligence.

2. Describe and criticize the Turing’s criteria for computer software being “intelligent”.

3. Propositional calculus

a. Prove that modus ponens ((PàQ)ÙP)àQ is sound.

b. Prove that modus tollens ((PàQ)Ù¬Q)à¬P is sound.

Hint: use truth tables to enumerate all possible interpretations

4. Predicate calculus: The following story is from N. Wirth’s Algorithms + data structures = programs (1976).

I married a widow (let’s call her W) who has a grown-up daughter (call her D). My father (F), who visited us quite often, fell in love with my step-daughter and married her. Hence my father became my son-in-law and my step-daughter became my mother. Some months later, my wife gave birth to a son (S1), who became the brother-in-law of my father, as well as my uncle. The wife of my father, that is, my step-daughter, also had a son (S2).

Using predicate calculus, create a set of expressions that represent the situation in the above story. Add expressions defining basic family relationships such as the definition of father-in-law and use modus ponens on this system to prove the conclusion that “I am my own grandfather.”

5. Unification: Attemp to unify the following pairs of expressions. Either show their most general unifiers or explain why they will not unify.

a. p(X, Y) and p(a, Z)

b. p(X, X) and p(a, b)

c. ancestor(X, Y) and ancestor(bill, father(bill))

d. ancestor(X, father(X)) and ancestor(david, george)