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.

No sample solution.

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

Turing’s criteria:

Under the Turing Test setting, the computer software is said “intelligent” if the interrogator cannot tell the machine from the human.

Criticisms:

· The criteria is bias toward purely symbolic problem-solving tasks

· The criteria does not test abilities requiring perceptual skill

3. Propositional calculus

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

Use truth table to enumerate all possible interpretations, shown in the following truth table. From the truth table below, you can see that wherever the premises are true, the first line in the truth table, the conclusion is also true, and ((PàQ)ÙP)àQ is always true.

P Q PàQ PÙ(PàQ) (PÙ(PàQ))àQ

T T T T T

T F F F T

F T T F T

F F T F T

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

Similarly, the truth table below shows that modus tollens is sound.

P Q PàQ ¬Q (PàQ)Ù ¬Q ¬P ((PàQ)Ù ¬Q)à ¬P

T T T F F F T

T F F T F F T

F T T F F T T

F F T T T T T

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.”

(1) father(X, Z) Ù parent(Z, Y) à grandfather(X, Y)

(2) father(X, Y) Ù marry(Y, Z) à father-in-law(X, Z)

(3) marry(X, Y) Ù mother(X, Z) à step-father(Y, Z)

(4) father-in-law(X,Y)Ú setp-father(X, Y) à father(X, Y)

(5) father(X, Y) Ú mother(X, Y) à parent(X, Y)

(6) marry(W, I)

(7) mother(W, D)

(8) father(F, I)

(9) marry(D, F)

(10) step-father(I, D) from (3), (6), (7) and modus ponens

(11) father(I, D) from (4), (10) and modus ponens

(12) father-in-law(I, F) from (2), (9), (11) and modus ponens

(13) father(I, F) from (4), (12) and modus ponens

(14) parent(F, I) from (8), (5) and modus ponens

(15) grandfather(I, I) from (1), (13), (14) and modus ponens

5. Unification: Attempt 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)

The mgu is {a/X, Y/Z}.

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

Fails to unify since both a and b cannot be substituted for X.

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

The mgu is {bill/X, father(bill)/Y}.

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

Unifies only if george is the father(david). Function evaluation should be added to the unification algorithm.