In this problem we will see how to solve a class of Boolean formulas. A Boolean formula

is a logical expression composed of Boolean variables $($which can take the values True or

False $),$ logical operators, and parentheses.

For example, $\backslash$Phi $1($x$1,$ x$2)=($x$1$ x$2)($x$1$ x$2)$ is a Boolean formula with $2$ variables $$ x$1$

and x$2.($note: x$1$ denotes the negation of x$1,$ denotes the logical OR$,$ and $$ denotes the

logical AND of two Boolean variables.$)$ The formula $\backslash$Phi $1$ evaluates to False for x$1=$ True

and x$2=$ False $.$

The Boolean Satisfiability Problem $($SAT$)$ asks the following question: Given a Boolean

formula $\backslash$Phi $,$ is there an assignment of True or False to its variables such that the formula

evaluates to True $?$ For instance, in the above example, the Boolean formula $\backslash$Phi $1($x$1,$ x$2)$

evaluates to True for x$1=$ x$2=$ True $.$ Therefore, $\backslash$Phi is satisfiable. Whereas, the following

Boolean formula is not satisfiable $\backslash$Phi $2($x$1,$ x$2,$ x$3)=($x$1$x$2)($x$1$x$3)($x$2$x$3)($x$1$x$3)$

is not satisfiable $($convince yourself$).$

Solving such Boolean formulas plays a pivotal role in logic, and circuit design, and of course

computer science. A specific class of SAT formulas, known as $2-$SAT, consists of Boolean

formulas of the form C$1$ C$2...$ Ck$,$ where each Ci

is a clause with exactly two variables

$($or their negations$)$ connected by an OR operation. The Boolean formulas in examples

above are both $2-$SAT formulas.

$$Bool Software Inc.$$ is a startup that prides itself in designing efficient algorithms to solve

various classes of SAT problems. Having taken CIS $675$ during your grad school, the interviewer at $$Bool Software Inc.$$ has promised you a permanent job with benefits if you can

design an algorithm that solves the $2-$SAT problem efficiently.

Since you have learnt only graph search primitives so far, your goal for this HW assignment

is to propose an efficient algorithm that takes in a $2-$SAT formula as input, and outputs

True if there is a satisfying assignment for the Boolean formula, and False if there is

no satisfying assignment for it$.$ You can use the following directed graph to develop your

algorithms:

Given a Boolean $2-$SAT formula $\backslash$Phi $($x$1,...,$ xn$)$ on n$-$variables, let G $=($V$,$ E$)$ be a directed

graph on $2$n vertices, where each vertex denotes a variable xi and its negation xi

$.$ For each

clause $($xi $$ yi$)$ add arcs xi $->$ yi and yi $->$ xi

$.$ Use an appropriate graph search algorithm

on G to solve the $2-$SAT problem. Prove the correctness and run$-$time of your algorithm.