[Skip Navigation]
2018-04-25
User Icon

Apr 25 In-Class Exercise Thread .

Posts your solutions to the Apr 25 In-Class Exercise to this thread.

Best,

Chris

Posts your solutions to the Apr 25 In-Class Exercise to this thread. Best, Chris
User Icon
-- Apr 25 In-Class Exercise Thread

Instance of Subset-Sum 1000 100 = v1 1000 010 = v1' 0100 100 = v2 0100 011 = v2' 0010 001 = v3 0010 010 = v3' 0001 001 = v4 0001 100 = v4' 0000 100 = s1 0000 200 = s1' 0000 010 = s2 0000 020 = s2' 0000 001 = s3 0000 002 = s3' 1111 444

v1+v2'+v3'+v4'+s1'+s2'+s3+s3' = 1111 444 corresponds to x1 true, x2 false, x3 false, x4 false

(Edited: 2018-04-25)
Instance of Subset-Sum 1000 100 = v1 1000 010 = v1' 0100 100 = v2 0100 011 = v2' 0010 001 = v3 0010 010 = v3' 0001 001 = v4 0001 100 = v4' 0000 100 = s1 0000 200 = s1' 0000 010 = s2 0000 020 = s2' 0000 001 = s3 0000 002 = s3' 1111 444 v1+v2'+v3'+v4'+s1'+s2'+s3+s3' = 1111 444 corresponds to x1 true, x2 false, x3 false, x4 false
User Icon
-- Apr 25 In-Class Exercise Thread
{

!! - !! x_1 !! x_2 !! x_3 !! x_4 !! C_1 !! C_2 !! C_3 |-

v_11000100
v_1'1000010
-
v_20100100
-
v_2'0100011
-
v_30010001
-
v_3'0010010
-
v_40001001
-
v_4'0001100
-
s_10000100
-
s_1'0000200
-
s_20000010
-
s_2'0000020
-
s_30000001
-
s_3'0000002
-
-1111444
}

let x1 = false, x2 = true, x3 = false, x4 = true Then we pick v1'+ v2 + v3' + v4 + s1' + s2 + s2' + s3' which will give 1111 444

(Edited: 2018-04-25)
{| |- !! - !! x_1 !! x_2 !! x_3 !! x_4 !! C_1 !! C_2 !! C_3 |- | v_1|| 1 || 0 || 0 || 0 || 1 || 0 || 0 |- | v_1'|| 1 || 0 || 0 || 0 || 0 || 1 || 0 |- | v_2|| 0 || 1 || 0 || 0 || 1 || 0 || 0 |- | v_2'|| 0 || 1 || 0 || 0 || 0 || 1 || 1 |- | v_3|| 0 || 0 || 1 || 0 || 0 || 0 || 1 |- | v_3'|| 0 || 0 || 1 || 0 || 0 || 1 || 0 |- | v_4 || 0 || 0 || 0 || 1 || 0|| 0 || 1 |- | v_4' || 0 || 0 || 0 || 1 || 1|| 0 || 0 |- | s_1 || 0 || 0|| 0|| 0|| 1|| 0|| 0 |- | s_1'|| 0|| 0|| 0|| 0|| 2|| 0|| 0 |- | s_2 || 0|| 0|| 0|| 0|| 0|| 1|| 0 |- | s_2' || 0|| 0|| 0|| 0|| 0|| 2||0 |- | s_3 || 0|| 0|| 0|| 0|| 0|| 0|| 1 |- | s_3' || 0|| 0|| 0|| 0|| 0|| 0||2 |- | - || 1|| 1|| 1|| 1|| 4|| 4 || 4 |} let x1 = false, x2 = true, x3 = false, x4 = true Then we pick v1'+ v2 + v3' + v4 + s1' + s2 + s2' + s3' which will give 1111 444
User Icon
-- Apr 25 In-Class Exercise Thread
  x1 x2 x3 x4 C1 C2 C3

v1 = 1 0 0 0 1 0 0 v1'= 1 0 0 0 0 1 0 v2 = 0 1 0 0 1 0 0 v2'= 0 1 0 0 0 1 1 v3 = 0 0 1 0 0 0 1 v3'= 0 0 1 0 0 1 0 v4 = 0 0 0 1 0 0 1 v4'= 0 0 0 1 1 0 0 s1 = 0 0 0 0 1 0 0 s1'= 0 0 0 0 2 0 0 s2 = 0 0 0 0 0 1 0 s2'= 0 0 0 0 0 2 0 s3 = 0 0 0 0 0 0 1 s3'= 0 0 0 0 0 0 2 1 1 1 1 4 4 4

x1 = false; x2 = false; x3 = false; x4 = false

variables = v1', v2', v3', v4', s1, s1', s2, s3, s3'

(Edited: 2018-04-25)
x1 x2 x3 x4 C1 C2 C3 v1 = 1 0 0 0 1 0 0 v1'= 1 0 0 0 0 1 0 v2 = 0 1 0 0 1 0 0 v2'= 0 1 0 0 0 1 1 v3 = 0 0 1 0 0 0 1 v3'= 0 0 1 0 0 1 0 v4 = 0 0 0 1 0 0 1 v4'= 0 0 0 1 1 0 0 s1 = 0 0 0 0 1 0 0 s1'= 0 0 0 0 2 0 0 s2 = 0 0 0 0 0 1 0 s2'= 0 0 0 0 0 2 0 s3 = 0 0 0 0 0 0 1 s3'= 0 0 0 0 0 0 2 1 1 1 1 4 4 4 x1 = false; x2 = false; x3 = false; x4 = false variables = v1', v2', v3', v4', s1, s1', s2, s3, s3'
User Icon
-- Apr 25 In-Class Exercise Thread

<nowiki> φ=C1∧C2∧C3 where, C1=(x1∨x2∨¬x4), C2=(¬x1∨¬x2∨¬x3), and C3=(¬x2∨x3∨x4). v_1 1 0 0 0 1 0 0 v_1' 1 0 0 0 0 1 0 v_2 0 1 0 0 1 0 0 v_2' 0 1 0 0 0 1 1 v_3 0 0 1 0 0 0 1 v_3' 0 0 1 0 0 1 0 v_4 0 0 0 1 0 0 1 v_4' 0 0 0 1 1 0 0 s_1 0 0 0 0 1 0 0 s_1' 0 0 0 0 2 0 0 s_2 0 0 0 0 0 1 0 s_2' 0 0 0 0 0 2 0 s_3 0 0 0 0 0 0 1 s_3' 0 0 0 0 0 0 2

If x1 = false, x2 = true, x3 = false, x4 = true Then we pick v1'+ v2 + v3' + v4 + s1' + s2 + s2' + s3' which will give 1111 444 </nowiki>

<nowiki> φ=C1∧C2∧C3 where, C1=(x1∨x2∨¬x4), C2=(¬x1∨¬x2∨¬x3), and C3=(¬x2∨x3∨x4). v_1 1 0 0 0 1 0 0 v_1' 1 0 0 0 0 1 0 v_2 0 1 0 0 1 0 0 v_2' 0 1 0 0 0 1 1 v_3 0 0 1 0 0 0 1 v_3' 0 0 1 0 0 1 0 v_4 0 0 0 1 0 0 1 v_4' 0 0 0 1 1 0 0 s_1 0 0 0 0 1 0 0 s_1' 0 0 0 0 2 0 0 s_2 0 0 0 0 0 1 0 s_2' 0 0 0 0 0 2 0 s_3 0 0 0 0 0 0 1 s_3' 0 0 0 0 0 0 2 If x1 = false, x2 = true, x3 = false, x4 = true Then we pick v1'+ v2 + v3' + v4 + s1' + s2 + s2' + s3' which will give 1111 444 </nowiki>
User Icon
-- Apr 25 In-Class Exercise Thread

&lt;nowiki&gt;

x1 x2 x3 x4 c1 c2 c3

v1 1 0 0 0 1 0 0 v1&#039; 1 0 0 0 0 1 0 v2 0 1 0 0 1 0 0 v2&#039; 0 1 0 0 0 1 1 v3 0 0 1 0 0 0 1 v3&#039; 0 0 1 0 0 1 0 v4 0 0 0 1 0 0 1 v4&#039; 0 0 0 1 1 0 0 s1 0 0 0 0 1 0 0 s1&#039; 0 0 0 0 2 0 0 s2 0 0 0 0 0 1 0 s2&#039; 0 0 0 0 0 2 0 s3 0 0 0 0 0 0 1 s3&#039; 0 0 0 0 0 0 2 t 1 1 1 1 4 4 4

let x1 = false, x2 = true, x3 = false, x4 = true and pick v1&#039;+ v2 + v3&#039; + v4 + s1&#039; + s2 + s2&#039; + s3&#039; = gives 1111 444

&lt;/nowiki&gt;

(Edited: 2018-04-25)
<nowiki> x1 x2 x3 x4 c1 c2 c3 v1 1 0 0 0 1 0 0 v1' 1 0 0 0 0 1 0 v2 0 1 0 0 1 0 0 v2' 0 1 0 0 0 1 1 v3 0 0 1 0 0 0 1 v3' 0 0 1 0 0 1 0 v4 0 0 0 1 0 0 1 v4' 0 0 0 1 1 0 0 s1 0 0 0 0 1 0 0 s1' 0 0 0 0 2 0 0 s2 0 0 0 0 0 1 0 s2' 0 0 0 0 0 2 0 s3 0 0 0 0 0 0 1 s3' 0 0 0 0 0 0 2 t 1 1 1 1 4 4 4 let x1 = false, x2 = true, x3 = false, x4 = true and pick v1'+ v2 + v3' + v4 + s1' + s2 + s2' + s3' = gives 1111 444 </nowiki>
2018-04-28
User Icon
-- Apr 25 In-Class Exercise Thread

Given : &phi;=C1&and;C2&and;C3 where C1=(x1 &or; x2 &or; &not;x4), C2=(&not;x1 &or; &not;x2 &or; &not;x3), and C3=(&not;x2 &or; x3 &or; x4)

x1 x2 x3 x4 C1 C2 C3

v1 = 1 0 0 0 1 0 0 v1&#039;= 1 0 0 0 0 1 0 v2 = 0 1 0 0 1 0 0 v2&#039;= 0 1 0 0 0 1 1 v3 = 0 0 1 0 0 0 1 v3&#039;= 0 0 1 0 0 1 0 v4 = 0 0 0 1 0 0 1 v4&#039;= 0 0 0 1 1 0 0 s1 = 0 0 0 0 1 0 0 s1&#039;= 0 0 0 0 2 0 0 s2 = 0 0 0 0 0 1 0 s2&#039;= 0 0 0 0 0 2 0 s3 = 0 0 0 0 0 0 1 s3&#039;= 0 0 0 0 0 0 2 1 1 1 1 4 4 4

Solution : v1+v2&#039;+v3&#039;+v4&#039;+s1&#039;+s2&#039;+s3+s3&#039; x1 = true x2 = false x3 = false x4 = false

Given : φ=C1∧C2∧C3 where C1=(x1 ∨ x2 ∨ ¬x4), C2=(¬x1 ∨ ¬x2 ∨ ¬x3), and C3=(¬x2 ∨ x3 ∨ x4) x1 x2 x3 x4 C1 C2 C3 v1 = 1 0 0 0 1 0 0 v1'= 1 0 0 0 0 1 0 v2 = 0 1 0 0 1 0 0 v2'= 0 1 0 0 0 1 1 v3 = 0 0 1 0 0 0 1 v3'= 0 0 1 0 0 1 0 v4 = 0 0 0 1 0 0 1 v4'= 0 0 0 1 1 0 0 s1 = 0 0 0 0 1 0 0 s1'= 0 0 0 0 2 0 0 s2 = 0 0 0 0 0 1 0 s2'= 0 0 0 0 0 2 0 s3 = 0 0 0 0 0 0 1 s3'= 0 0 0 0 0 0 2 1 1 1 1 4 4 4 Solution : v1+v2'+v3'+v4'+s1'+s2'+s3+s3' x1 = true x2 = false x3 = false x4 = false
2018-04-29
User Icon
-- Apr 25 In-Class Exercise Thread
  x1 x2 x3 x4 C1 C2 C3

v1 1 0 0 0 1 0 0 v1&#039; 1 0 0 0 0 1 0 v2 0 1 0 0 1 0 0 v2&#039; 0 1 0 0 0 1 1 v3 0 0 1 0 0 0 1 v3&#039; 0 0 1 0 0 1 0 v4 0 0 0 1 0 0 1 v4&#039; 0 0 0 1 1 0 0 s1 0 0 0 0 1 0 0 s1&#039; 0 0 0 0 2 0 0 s2 0 0 0 0 0 1 0 s2&#039; 0 0 0 0 0 2 0 s3 0 0 0 0 0 0 1 s3&#039; 0 0 0 0 0 0 2 1 1 1 1 4 4 4

Let x1 = T x2 = F x3 = T x4 = T Pick v1 + v2&#039; + v3 + v4 + s1&#039; + s2&#039;+ s3 + s3&#039; = 1111 444

x1 x2 x3 x4 C1 C2 C3 v1 1 0 0 0 1 0 0 v1' 1 0 0 0 0 1 0 v2 0 1 0 0 1 0 0 v2' 0 1 0 0 0 1 1 v3 0 0 1 0 0 0 1 v3' 0 0 1 0 0 1 0 v4 0 0 0 1 0 0 1 v4' 0 0 0 1 1 0 0 s1 0 0 0 0 1 0 0 s1' 0 0 0 0 2 0 0 s2 0 0 0 0 0 1 0 s2' 0 0 0 0 0 2 0 s3 0 0 0 0 0 0 1 s3' 0 0 0 0 0 0 2 1 1 1 1 4 4 4 Let x1 = T x2 = F x3 = T x4 = T Pick v1 + v2' + v3 + v4 + s1' + s2'+ s3 + s3' = 1111 444
User Icon
-- Apr 25 In-Class Exercise Thread

Given : &phi;=C1&and;C2&and;C3 

    where C1=(x1 ∨ x2 ∨ ¬x4), C2=(¬x1 ∨ ¬x2 ∨ ¬x3), C3=(¬x2 ∨ x3 ∨ x4)
x1 x2 x3 x4 C1 C2 C3

v1 1 0 0 0 1 0 0 v1&#039; 1 0 0 0 0 1 0 v2 0 1 0 0 1 0 0 v2&#039; 0 1 0 0 0 1 1 v3 0 0 1 0 0 0 1 v3&#039; 0 0 1 0 0 1 0 v4 0 0 0 1 0 0 1 v4&#039; 0 0 0 1 1 0 0 s1 0 0 0 0 1 0 0 s1&#039; 0 0 0 0 2 0 0 s2 0 0 0 0 0 1 0 s2&#039; 0 0 0 0 0 2 0 s3 0 0 0 0 0 0 1 s3&#039; 0 0 0 0 0 0 2 1 1 1 1 4 4 4

Solution : v1+v2&#039;+v3&#039;+v4&#039;+s1&#039;+s2&#039;+s3+s3&#039;

Hence x1 = true x2 = false x3 = false x4 = false

(Edited: 2018-04-29)
Given : φ=C1∧C2∧C3 where C1=(x1 ∨ x2 ∨ ¬x4), C2=(¬x1 ∨ ¬x2 ∨ ¬x3), C3=(¬x2 ∨ x3 ∨ x4) x1 x2 x3 x4 C1 C2 C3 v1 1 0 0 0 1 0 0 v1' 1 0 0 0 0 1 0 v2 0 1 0 0 1 0 0 v2' 0 1 0 0 0 1 1 v3 0 0 1 0 0 0 1 v3' 0 0 1 0 0 1 0 v4 0 0 0 1 0 0 1 v4' 0 0 0 1 1 0 0 s1 0 0 0 0 1 0 0 s1' 0 0 0 0 2 0 0 s2 0 0 0 0 0 1 0 s2' 0 0 0 0 0 2 0 s3 0 0 0 0 0 0 1 s3' 0 0 0 0 0 0 2 1 1 1 1 4 4 4 Solution : v1+v2'+v3'+v4'+s1'+s2'+s3+s3' Hence x1 = true x2 = false x3 = false x4 = false
User Icon
-- Apr 25 In-Class Exercise Thread
  x1 x2 x3 x4 C1 C2 C3

v1 = 1 0 0 0 1 0 0 v1&#039;= 1 0 0 0 0 1 0 v2 = 0 1 0 0 1 0 0 v2&#039;= 0 1 0 0 0 1 1 v3 = 0 0 1 0 0 0 1 v3&#039;= 0 0 1 0 0 1 0 v4 = 0 0 0 1 0 0 1 v4&#039;= 0 0 0 1 1 0 0 s1 = 0 0 0 0 1 0 0 s1&#039;= 0 0 0 0 2 0 0 s2 = 0 0 0 0 0 1 0 s2&#039;= 0 0 0 0 0 2 0 s3 = 0 0 0 0 0 0 1 s3&#039;= 0 0 0 0 0 0 2 1 1 1 1 4 4 4

Let x1 = false, x2 = true, x3 = false, x4 = true . Then we pick v1&#039;+ v2 + v3&#039; + v4 + s1&#039; + s2 + s2&#039; + s3&#039; = 1111 444

x1 x2 x3 x4 C1 C2 C3 v1 = 1 0 0 0 1 0 0 v1'= 1 0 0 0 0 1 0 v2 = 0 1 0 0 1 0 0 v2'= 0 1 0 0 0 1 1 v3 = 0 0 1 0 0 0 1 v3'= 0 0 1 0 0 1 0 v4 = 0 0 0 1 0 0 1 v4'= 0 0 0 1 1 0 0 s1 = 0 0 0 0 1 0 0 s1'= 0 0 0 0 2 0 0 s2 = 0 0 0 0 0 1 0 s2'= 0 0 0 0 0 2 0 s3 = 0 0 0 0 0 0 1 s3'= 0 0 0 0 0 0 2 1 1 1 1 4 4 4 Let x1 = false, x2 = true, x3 = false, x4 = true . Then we pick v1'+ v2 + v3' + v4 + s1' + s2 + s2' + s3' = 1111 444
[ Next ]
X

 

- Blog - Privacy - Terms - ThisSiteBot
- Developed at SeekQuarry -
(c) This Site - This Search Engine
We use cookies to implement this site's user functionality, social media features, and traffic analytics. Privacy Policy Details. Allow Cookies