(comp221)[2008](f)mid~PPSpider^_10176.pdf

Back to COMP221 Login to download

======================================================

COMP 221: Introduction to Arti.cial Intelligence (2008 Fall)

Solutions to Midterm Exam

Problem 1. [8%] Binary Logical Connectives

There are 4 binary logical connectives in propositional logic: , , ., and, ..

(a)

[2%] Theoretically speaking, how many binary connectives can there be? Show your reasoning.

There are 4 rows in the truth table of a binary logical connective. Each row has 2 possible values, giving a total of 24 = 16 possible connectives.

(b)

[6%] What are the meaning of the remaining binary logical connectives (other than the 4 connectives in propositional logic)?

Besides the 4 logical connectives: , , ., and, . for 2 symbols, say, P and Q, the other possible connectives are equivalent to: reverse implication

., P, Q, always true, and their negations.

Problem 2. [12%] First-Order Logic (FOL) Sentences

Represent the following sentences in FOL, using the following predicates/functions:

P resident(x, s): person x is the president of school s

Occur(e, y): event e occurs in year y

Mod(x, y): a function returning xmody

Born(x, y): person x is born in year y

Idnum(x): a function returning the ID number of person x

F irstDigit(n, d): d is the .rst digit of ID number n

Chinese(x): x is a Chinese

Dog(x): x is a Dog

Eat(x, y): person x eats y

Own(x, y): person x owns y

Add your own functions, constants, etc. only when it is necessary.

(a) [3%] Paul Chu is the president of HKUST.

P resident(P aulChu, HKUST ).

(b) [3%] There is a .nancial crisis every 10 years since 1980 inclusive (and the trend will continue forever).

.yy 1980 Mod(y, 10) = 0 . Occur(F inancialCrisis, y)

(c) [3%] Everyone who was born in the same year has the same .rst digit in his/her ID number.

.p .q . year Born(p, year) Born(q, year)

. (.d F irstDigit(ID(p),d) F irstDigit(ID(q),d))

(d) [3%] No Chinese eat his/her own dog.

.x .y Chinese(x) Dog(y) Eat(x, y) ..Own(x, y))

Problem 3. [20%] First-Order Logic (FOL) Resolution

If a course is easy, some students are happy. If a course has a .nal, no students are happy.

Use resolution to show that, if a course has a .nal, the course is not easy.

Lets proceed as follows. Firstly, we rewrite the description in FOL using the

following predicates:

T ake(s, c): student s takes course c

Happy(s, c): student s is happy with the course c

F inal(c): course c has a .nal

Easy(c): course c is easy

Thus, the description in FOL consists of the following axioms:

.c Easy(c) ..s T ake(s, c) Happy(s, c) .c .s F inal(c) T ake(s, c) ..Happy(s, c)

(a) [2%] Convert the above 2 axioms in conjunctive normal form (CNF).

.Easy(c) (T ake(F (c),c) Happy(F (c),c)) (.Easy(c) T ake(F (c),c)) (.Easy(c) Happy(F (c),c))

.(F inal(c) T ake(s, c)) .Happy(s, c) .F inal(c) .T ake(s, c) .Happy(s, c)

where F (c) is a Skolem function.

(b)

[2%] Write the goal sentence in FOL.

(c)