1. In transforming a formula into an equivalent CNF, you can use the absorption laws to eliminate conjunctions within disjuntions, i.e. expressions such as p ˅ (q ˄ r) and (p ˄ q) ˅ r.   True False                                                                                                                                                                                                                                                                                        2. Let p, q, and r be propositional variables. Which of the following expressions would NOT be formulas in conjunctive normal form?   (p ˄ ¬q) ˅ (¬r ˄ q ˄ p) ¬q p ˅ q ˅ ¬p p ˄ ¬p   3. Consider the propositional logic formula (p ˄ q) ˅ (r ˅ ¬s) From the options below, which one is the equivalent CNF? To determine the correct answer, transform the formula above into CNF using the steps learnt in this module.   (p ˅ r ˅ s) ˄ (q ˅ r ˅ ¬s) (¬p ∨ r ∨ s) ∧ (¬q ∨ ¬r ∨ ¬s) (p ˅ r ˅ ¬s) ˄ (q ˅ r ˅ s) (p ˅ r ˅ ¬s) ˄ (q ˅ r ˅ ¬s)

1. In transforming a formula into an equivalent CNF, you can use the absorption laws to eliminate conjunctions within disjuntions, i.e. expressions such as p ˅ (q ˄ r) and (p ˄ q) ˅ r.

True

False                                                                                                                                                                                                                                                                                       

2. Let p, q, and r be propositional variables. Which of the following expressions would NOT be formulas in conjunctive normal form?

(p ˄ ¬q) ˅ (¬r ˄ q ˄ p)

¬q

p ˅ q ˅ ¬p

p ˄ ¬p

3. Consider the propositional logic formula

(p ˄ q) ˅ (r ˅ ¬s)

From the options below, which one is the equivalent CNF? To determine the correct answer, transform the formula above into CNF using the steps learnt in this module.

(p ˅ r ˅ s) ˄ (q ˅ r ˅ ¬s)

(¬p ∨ r ∨ s) ∧ (¬q ∨ ¬r ∨ ¬s)

(p ˅ r ˅ ¬s) ˄ (q ˅ r ˅ s)

(p ˅ r ˅ ¬s) ˄ (q ˅ r ˅ ¬s)

4. Consider the propositional logic formula
 
r → ¬(¬p → s)
 
From the options below, which one is the equivalent CNF? To determine the correct answer, transform the formula above into CNF using the steps learnt in this module.

(¬r ˅ ¬p) ˄ (¬r ˅ ¬s)

(r ˅ p) ˄ (r ˅ s)

¬r ˅ ¬(p ˅ s)

r ˅ (¬p ˄ ¬s)

5. Which of the following are correct statements? Select all that apply.

The resolvent of p and ¬p is ∅.

Let C₁, C₂ be clauses. The set of clauses {C₁, C₂, T} and {C₁, C₂} are logically equivalent.

The empty set of clauses is unsatisfiable.

A set of clauses is valid if and only if every clause in the set is true in every interpretation      

6. Which formulas are in 3CNF? Select all that apply.

p

(¬p ˅ q ˅ ¬r) ˄ (p ˅ ¬q ˅ r)

p ˄ q ˄ r

(¬p) ˄ (¬q ˅ r)

7. Let p, q, r, and s be propositional variables. Consider the formula
 
(p ˅ q) ˄ (r ˅ s)
 
If you applied the algorithm discussed in this module to transform a CNF formula into 3CNF, the result would be ___.

(p ˅ q ˅ r) ˄ (q ˅ r ˅ s)

p ˅ q ˅ s

(p ˅ q ˅ t) ˄ (r ˅ s ˅ u)

(p ˅ q ˅ t) ˄ (p ˅ q ˅ ¬t) ˄ (r ˅ s ˅ u) ˄ (r ˅ s ˅ ¬u)                                                                                                                                                                                                                                                                                                                           

8. Let p, q, r, and s be propositional variables. What is the resolvent of clauses C₁ and C₂?
 
C₁ = pq̄r
C₂ = q̄r̄s

pqs

q̄

pq̄s

F                                                                                                                                                                                             

9. Which sets of clauses are satisfiable? Select all that apply.

{pq̄, p, p̄q}

{pqr}

{p̄q̄, p, p̄q}

{p, p̄}

10. The proof that the set of clauses

is unsatisfiable is given below. Clauses in Steps 7 through 11 were obtained using the resolution rule. For each clause in Steps 7 through 11, please select the number of the clause that was used to obtain it.

   (7):  (1) and       
   (8):  (3) and       
   (9):  (4) and      
 (10):  (5) and       
 (11):  (9) and