Please submit a digital copy of your solution on CCLE. Submitted files can be in either PDF or plain text. You may also submit a scanned PDF of a handwritten solution, but please ensure that the scanned file is clearly legible.
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, unsatisfiable, 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 ω in [0,1], the weight of a truth assignment is defined as the product of its literals weights. For example, ω(A, ¬B, C) = ω(A) ω(¬B) ω(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: ω(A)=0.1, ω(¬A)=0.9, ω(B)=0.3, ω(¬B)=0.7, ω(C)=0.5, ω(¬C)=0.5, ω(D)=0.7, ω(¬D)=0.3.
(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.
