Post your solutions to the Mar 8 in class exercise here.

Best, Chris

F = (x1) ^ (x2 ) ^ (x3) ^ (x1 V -x2) ^ (-x2 V x3) ^ (x3 V -x1)

x2 = true

F[0] = (x1) ^ (1 ) ^ (x3) ^ (x1 V 0) ^ (0 V x3) ^ (x3 V -x1)

x3 = true

F[1] = (x1) ^ (1 ) ^ (1) ^ (1 V 0) ^ (0 V 1) ^ (1 V -x1)

x1 = true

F[2] = (1) ^ (1 ) ^ (1) ^ (1 V 0) ^ (0 V 1) ^ (1 V 0)

1 ^ 1 ^ 1 ^ 1 ^ 1 ^ 1

Therefore it is satisfiable.

<pre> variables: {x, y ,z} >> (!z,!y,x) ^ (!y,z,z) ^ (y,x,!z) ^ (y,y,y) ^ (x,!z,x) ^ (!y,!y,x)

Random process: Assign variable y = 0; >> (x,!z) ^ (0,0,0) ^ (x,!z,x) ^ (x)

>> not satisfiable by random assignment, satisfiable by all 1 assignment </pre>

m = 6 and n = 3

Generating Formula, C = (a, b, c),(a, b, c),(a, b, c),(a, b, c),(a, b, c),(a, b, c) C = (a, -c, a),(-c, a, -b), (-a, -c, -b),(-b, c, -c), (-b, a, b), (-b, -c, b) C = {a, -c},{-c, a, -b},{-a, -c, -b},{T}, {T}, {T}

Assignments, F[0] = {a, -c},{-c, a, -b},{-a, -c, -b},{T}, {T}, {T} F[1] = {1, -c},{-c, 1, -b},{0, -c, -b},{T}, {T}, {T} F[2] = {1, 0},{0, 1, -b},{0, 0, -b},{T}, {T}, {T} F[3] = {1, 0},{0, 1, 1},{0, 0, 1},{T}, {T}, {T}

This formula is satisfiable since all clauses has atleast one value as 1.

<pre>

{v1,~v2,v3}, {v2,~v1,v3},{v3,~v3,v1},{v1,v2,v3},{~v2,v1,~v2},{v1,v2,~v1}

{v1,~v2,v3}, {v2,~v1,v3},{T},{v1,v2,v3},{v1,~v2},{T}

F[0] = {v1,~v2,v3}, {v2,~v1,v3},{T},{v1,v2,v3},{v1,~v2},{T} F[1] = {1,~v2,v3}, {v2,0,v3},{T},{1,v2,v3},{1,~v2},{T} F[2] = {1,0,v3}, {1,0,v3},{T},{1,1,v3},{1,0},{T} F[3] = {1,0,1}, {1,0,1},{T},{1,1,1},{1,0},{T}

the problem is satisfiable as value of the clauses equals 1

</pre>

F = ( (x_3, x_2), (\overline{x_1}, x_3), (\overline{x_1}, \overline{x_3}, x_2), (\overline{x_2}, x_1), (\overline{x_3}, x_2), (x_3) )

F[0] = F

t:1

L = x_3

x_3 = 1

F[0] = ( (1, x_2), (\overline{x_1}, 1), (\overline{x_1}, 0, x_2), (\overline{x_2}, x_1), (0, x_2), (1) )

F[1] = F[0]

t:2

L = \overline{x_2}

\overline{x_2} = 1

F[1] = ( (1, 0), (\overline{x_1}, 1), (\overline{x_1}, 0, 0), (1, x_1), (0, 0), (1) )

F[2] = F[1]

t:3

L = \overline{x_1}

\overline{x_1} = 1

F[2] = ( (1, 0), (1, 1), (1, 0, 0), (1, 0), (0, 0), (1) )

This problem is not satisfiable by this assignment