For the 3CNF
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 01 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)
A)
f = (x’ +y’+z)& (x+y’+z’)&(x+y+z’)& (x’+y+z)&(x’+y+z’) &(x+y+z)
a)give 01 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
Get Answers For Free
Most questions answered within 1 hours.