CS480 – Assignment 5 Solved

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 n2.  (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)?