Question

Consider the following instance of 2SAT: (\neg Q \vee P) \wedge(\neg P \vee \neg S) \wedge(\neg P \vee \neg R) \wedge(S \vee R) \wedge(Q \vee R) Draw the implication graph

and identify the strongly connected components. Which of the following subsets are strongly connected components of the implication graph? \{\neg S\} \{\neg P, \neg Q, R\} \{P, Q, \neg R, S\} \{\neg P, \neg R, \neg S\} \{\neg P, \neg R, \neg S\} \{\neg P, Q, S\}

Fig: 1

Fig: 2

Fig: 3

Fig: 4

Fig: 5

Fig: 6

Fig: 7

Fig: 8

Fig: 9