3. a. Consider the following instance of 2SAT: (PVR) A(-QVP) A(-SVR) ^ (RVQ) ^ (PVS) i....

 

Transcribed Image Text:

3. a. Consider the following instance of 2SAT: (PVR) A(-QVP) A(-SVR) ^ (RVQ) ^ (PVS) i. Draw the implication graph for this instance of 2SAT. [5 marks] ii. Identify all the strongly connected components of the implication graph associated with the above instance of 2SAT. [5 marks] iii. Decide whether the above instance of 2SAT is satisfiable. Justify your answer. [3 marks] b. Consider the following set of clauses (numbered for reference): (PVQ) (QVRVS) (PVQ) (PVRVS) (PVQ VR) (QVR) (2) (3) (4) (5) (6) Use the Davis-Putnam-Logemann-Loveland (DPLL) algorithm to de- cide if the above set of clauses is satisfiable. [10 marks] 3. a. Consider the following instance of 2SAT: (PVR) A(-QVP) A(-SVR) ^ (RVQ) ^ (PVS) i. Draw the implication graph for this instance of 2SAT. [5 marks] ii. Identify all the strongly connected components of the implication graph associated with the above instance of 2SAT. [5 marks] iii. Decide whether the above instance of 2SAT is satisfiable. Justify your answer. [3 marks] b. Consider the following set of clauses (numbered for reference): (PVQ) (QVRVS) (PVQ) (PVRVS) (PVQ VR) (QVR) (2) (3) (4) (5) (6) Use the Davis-Putnam-Logemann-Loveland (DPLL) algorithm to de- cide if the above set of clauses is satisfiable. [10 marks]