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.
