Question

Consider a formula of propositional logic consisting of a conjunction of clauses of the form (±p⊕±q), where p and q are propositional variables (not necessarily distinct) and ±p stands for either p or ¬p. Consider the graph in which the vertices include p and ¬p for all propositional variables p appearing in the formula, and in which there is an edge (1) connecting p and ¬p for each variable p, and (2) connecting two literals if their exclusive-or is a clause of the formula. Prove that the formula is satisfiable if and only if the graph is 2-colorable.

Answer 1

Consider a formula of propositional logic consisting of a conjunction of clauses of the form.

It contains a path from to then it also contains a path from to .

That is the path from to be ->p1->p2->.......->pk-> now by construction of G if there is an edge (p,q) then there is also an edge ( q, p).

Therefore the edges ( , pk),(pk,pk-1) .........(p2,p),(p,) hence there is a path from to .

2-colorable formula P ia a satisfable if there exists a variable p

There exist path from p to p in the graph.

There exist path from p to p in the graph by cotradiction.

If there are paths p to p and p to p for some variable p in G,but there also exists a unsatisfiable assignment p(p1,p2.......pn) be such that X=False.

Now the path  p to p be p->.............->->p->.......->p

p->->->p

f f t t

Here by constuction there is an edge between A to B in G .if and only if there is a clause (A v B) in the edge from A to B represents that if A is True then B must be True now since P is True.

This results an edge between and with = False and  =True consequency the clause ( v ) becomes False.

Contradicting our a assumption is wrong that there exist a satisfying assignment p(p1,p2,.....pn)for  .