Question

For the 3-CNF

f = (x’ +y’+z)& (x+y’+z’)&(x+y+z’)& (x’+y+z)&(x’+y+z’) &(x+y+z)

where “+” is or, “&” is and operations, “ ’ ” is negation.

a)give 0-1 assignment to variables such that

f=1    x= ______ y= ______ z= ____

f=0    x= ______ y= ______ z= ____

-

b) Draw the corresponding graph and mark the maximum independent set.

(you can draw on paper, scan and insert here)

Answer 1

A)

f = (x’ +y’+z)& (x+y’+z’)&(x+y+z’)& (x’+y+z)&(x’+y+z’) &(x+y+z)

a)give 0-1 assignment to variables such that

f=1 x= 1, y=1, z=1

When we Substitute these values in f, we will get f=1

f=0 x=0, y=0, z=0

When we Substitute these values in f, we will get f=0

------------------------------------

B) Draw the corresponding graph and mark the maximum independent set.

For each clause in f = (x’ +y’+z)& (x+y’+z’)&(x+y+z’)& (x’+y+z)&(x’+y+z’) &(x+y+z),

we have 3 vertices, all three vertices within a clause will be connected via edges.

For each literal L in Clause i, it will be connected to literal L' in Clause j via edge.

We obtain the below graph, the yellow nodes denoted the maximum independent set int the graph,

Observe those yellow nodes when set to 1(represent x=1, y=1, z=1) form a satisfiable assignment to formula f.

----------------------------

I hope this helps you,

Please rate this answer if it helped you,

Thanks for the opportunity