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, ..
[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.

[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.
[2%] Write the goal sentence in FOL.