2017-03-08

Mar 8 In-Class Exercise.

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

-- Mar 8 In-Class Exercise
Resource Description for 17175935_1202740729838788_45298948_o.jpg
((resource:17175935_1202740729838788_45298948_o.jpg|Resource Description for 17175935_1202740729838788_45298948_o.jpg))

-- Mar 8 In-Class Exercise
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.
(Edited: 2017-03-08)
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.

-- Mar 8 In-Class Exercise
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
(Edited: 2017-03-08)
<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>

-- Mar 8 In-Class Exercise
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.
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.

-- Mar 8 In-Class Exercise
 
 
{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 
 
(Edited: 2017-03-08)
<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>

-- Mar 8 In-Class Exercise
`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
(Edited: 2017-03-08)
@BT@F = (@BT@ @BT@(x_3, x_2),@BT@ @BT@(\overline{x_1}, x_3),@BT@ @BT@(\overline{x_1}, \overline{x_3}, x_2),@BT@ @BT@(\overline{x_2}, x_1),@BT@ @BT@(\overline{x_3}, x_2),@BT@ @BT@(x_3)@BT@ @BT@)@BT@ @BT@F[0] = F@BT@ @BT@t:1@BT@ @BT@L = x_3@BT@ @BT@x_3 = 1@BT@ @BT@F[0] = (@BT@ @BT@(1, x_2),@BT@ @BT@(\overline{x_1}, 1),@BT@ @BT@(\overline{x_1}, 0, x_2),@BT@ @BT@(\overline{x_2}, x_1),@BT@ @BT@(0, x_2),@BT@ @BT@(1)@BT@ @BT@)@BT@ @BT@F[1] = F[0]@BT@ @BT@t:2@BT@ @BT@L = \overline{x_2}@BT@ @BT@\overline{x_2} = 1@BT@ @BT@F[1] = (@BT@ @BT@(1, 0),@BT@ @BT@(\overline{x_1}, 1),@BT@ @BT@(\overline{x_1}, 0, 0),@BT@ @BT@(1, x_1),@BT@ @BT@(0, 0),@BT@ @BT@(1)@BT@ @BT@)@BT@ @BT@F[2] = F[1]@BT@ @BT@t:3@BT@ @BT@L = \overline{x_1}@BT@ @BT@\overline{x_1} = 1@BT@ @BT@F[2] = (@BT@ @BT@(1, 0),@BT@ @BT@(1, 1),@BT@ @BT@(1, 0, 0),@BT@ @BT@(1, 0),@BT@ @BT@(0, 0),@BT@ @BT@(1)@BT@ @BT@)@BT@ This problem is not satisfiable by this assignment

-- Mar 8 In-Class Exercise
Resource Description for almost_surely_satisfiable.jpeg
((resource:almost_surely_satisfiable.jpeg|Resource Description for almost_surely_satisfiable.jpeg))
X