CS480 – Assignment 5

Description

1. Convert each of the following FOL sentences into CNF form.
a. x P(x)  Q(x)
b. xy P(x,y)  Q(x)
c. x P(x)  Q(x)
d. xy P(x,y)  Q(y,x)
e. xy P(x,y)
f. xy P(x,y)
g. xyz P(x,y,z)
h. xyz P(x,y,z)
i. x(y P(x,y)  Q(y))  R(x)
j. x(y P(x,y)  Q(y))  R(x)
2. We are given the following pairs of FOL sentences. For each pair of sentences, provide a
substitution to unify the sentences. If no such substitution exists, please write so.
a. P(x)
b. P(A)
c. P(x)  Q(x, A)
d. P(B)  Q(x, A)
e. P(x)  Q(A, x)
f. P(x)  Q(A, B)
g. P(x, A)  Q(A, x)
h. P(B, y)  Q(y, B)
i. P(x)  Q(F(x))
j. P(A)  Q(F(A))
k. P(x, A)  Q(F(x), x)
l. P(B, y)  Q(F(B), B)
m. P(x, A)  Q(F(x), x)
n. P(B, y)  Q(F(A), A)
o. P(x, y)  Q(F(A), B)
p. P(x, y)  Q(x, y)
q. P(x, y)  Q(F(A), A)
r. P(x, y)  Q(x, y)
s. P(x, y)  Q(F(x), y)
t. P(z, y)  Q(z, y)
3. We are given the following joint distribution for variables A, B, and C. Please compute the
requested probabilities. Show each probability distribution as a table/vector. Feel free to use a
calculator.
a. P(A, C)
b. P(C)
c. P(A|C)
d. P(A, B | C)
e. P(B | A, C)
4. We are given random variables X2, X3, …, Xn, where n>2. (There is no X1). Please answer the
following questions.
a. Assuming all variables are binary, how many independent parameters are needed to
represent
i. P(X2)?
ii. P(Xn)?
iii. P(X2, X3, …, Xn)?
iv. P(X2 | X3, …, Xn)?
v. P(X2, X3, …, Xn-1| Xn)?
b. Assuming the size of the domain of Xi is i for all i{2, 3, …, n}, how many independent
parameters are needed to represent
i. P(X2)?
ii. P(Xn)?
iii. P(X2, X3, …, Xn)?
iv. P(X2 | X3, …, Xn)?
v. P(X2, X3, …, Xn-1| Xn)?