## Description

1. (10 pts) Use truth tables (worlds) to show that the following pairs of sentences are

equivalent:

• P Þ Q, ¬Q Þ ¬P

• P Û ¬Q, ((P Ù ¬Q) Ú (¬P Ù Q))

2. (20 pts) Consider the following sentences and decide for each whether it is valid,

satisfiable, or neither:

• (Smoke Þ Fire) Þ (¬Smoke Þ ¬Fire)

• (Smoke Þ Fire) Þ ((Smoke Ú Heat) Þ Fire)

• ((Smoke Ù Heat) Þ Fire) Û ((Smoke Þ Fire) Ú (Heat Þ Fire))

Justify your answer using truth tables (worlds).

3. (30 pts) Consider the following:

If the unicorn is mythical, then it is immortal, but if it is not mythical, then it is a mortal

mammal. If the unicorn is either immortal or a mammal, then it is horned. The unicorn is

magical if it is horned.

(a) Represent the above information using a propositional logic knowledge base (set

of sentences in propositional logic).

(b) Convert the knowledge base into CNF.

(c) Can you use the knowledge base to prove that the unicorn is mythical? How about

magical? Horned?

Justify your answers using resolution by providing corresponding resolution

derivations. Make sure to clearly define all propositional symbols (variables) first,

then define your knowledge base, and finally give your derivations.

4. (20 pts) Consider the two NNF circuits in Figure 1 and Figure 2. Identify whether they

are decomposable, deterministic, smooth and why.

5. (20 pts) Given a propositional formula, where each literal has a weight w in [0,1], the

weight of a truth assignment is defined as the product of its literals weights. For example,

w(A, ¬B, C) = w(A) w(¬B) w(C). The Weighted Model Count (WMC) of a propositional

formula is defined as the added weight of its satisfying assignments (i.e., models).

Suppose we have the following literal weights: w(A)=0.2, w(¬A)=0.8, w(B)=0.4,

w(¬B)=0.6, w(C)=0.6, w(¬C)=0.4 w(D)=0.8, w(¬D)=0.2.

(a) Compute the Weighted Model Count for formula (¬A Ù B) Ú (¬B Ù A) by

enumerating its models, computing their weights, then adding them up.

(b) Consider the decomposable, deterministic and smooth NNF circuit in Figure 3. If

we assign the weights of literals to all the leaf nodes, the count of each Ù node is

computed as the product of the counts of its children, and the count of each Ú

node is computed as the sum of the counts of its children. What is the relation

between the count on the root with the Weighted Model Count for the formula?

(c) Compute the Weighted Model Count for the formula associated with the

decomposable, deterministic and smooth NNF circuit in Figure 4.