My Math Forum Systems of Boolean Equations

 Complex Analysis Complex Analysis Math Forum

 February 12th, 2015, 02:48 AM #1 Newbie   Joined: Feb 2015 From: Armenia Posts: 2 Thanks: 0 Systems of Boolean Equations Hey guys -- , I need help to solve my problem). Here is the problem. Given a system of linear boolean equations . It looks like this c11*X1 + c12*X2 + ... + c1n*Xn = 1 c21*X1 + c22*X2 + ... + c2n*Xn = 1 . . . cn1*X1 + cn2*X2 + ... + cnn*Xn = 1 Cij = 0 or 1. The problem is how to find at least 1 solution with polynomial algorithm. I haven't found any topics about this problem.There are something about existence of solutions , but nothing about concrete solution. Do you have any ideas or known solutions ?
 February 12th, 2015, 01:36 PM #2 Senior Member   Joined: Dec 2013 From: Russia Posts: 327 Thanks: 108 You could solve it as an ordinary system of equations, but in $\Bbb Z_2$ instead of $\Bbb R$.
 March 3rd, 2015, 05:48 AM #3 Newbie   Joined: Feb 2015 From: Armenia Posts: 2 Thanks: 0 If someone is interested in , I've found some solution of this problem . In the first step algorithm represents X1 with other ones (X1 or Xi , which one exists) and replace it in other equations except the first . Lets assume in first equation c11 = 1. Then X1 = c12*X2 + ... + c1n*Xn + 1 . this equation marked as first.Then algorithm finds equation which contains X2 (or next variable with lowest index) , and so on . in the last equation we have 1 equation to solve , which is independent from others . After we solve that equation we are going up , solving next equation , and so on , finally we will reach the first equation. As we can see , algorithm has polynomial complexity. Here is the example x_1+ x_2+ x_5=1 x_2+ x_3+x_4 + x_5=1 x_1+ x_2+x_3=1 The first step is to find X1 from first equation and replace it in other ones (if it exists). x_1= x_2+ x_5+1 x_3+ x_2+x_4 + x_5=1 x_2+ x_5+1+ x_2+x_3=1 => x_1= x_2+ x_5+1 x_3+ x_2+x_4 + x_5=1 x_3+x_5=0 Now lets find X2 from the second equation . x_1= x_2+ x_5+1 x_3= x_2+x_4 + x_5+1 x_3+x_5=0 => x_1= x_2+ x_5+1 x_3= x_2+x_4 + x_5+1 x_2+x_4 + x_5+1+x_5=0 => x_1= x_2+ x_5+1 x_3= x_2+x_4 + x_5+1 x_2+x_4 =1 Now the second step of the algorithm. It starts with solving 3-th equation. It has 2 solutions (1,0) and (0,1) . Firstly , lets take (1,0) ; x_2=1 ,x_4=0 Then we have x_3= x_5 This equation has 2 solutions as well , lets take (1,1) x_3= 1 ,x_5=1 Finally , in first equation we have x_1= 1 One solution is x_1= 1,x_2=1 ,x_3= 1 ,x_4 =0,x_5=1 As we can it is suffices the equation . Lets find all solutions . Now Lets take x_3= 0 ,x_5=0 we will have x_1= 0 x_1= 0,x_2=1 ,x_3= 0 ,x_4 =0,x_5=0 Going down on 3-th equation. x_2=0 ,x_4 =1 Second equation will be the same x_3= x_5 Firstly , we will solve with (0,0) then (1,1) and we will have x_1=1 x_1=0 Finally x_1= 1,x_2=0 ,x_3= 0 ,x_(4 )=1,x_5=0 x_1= 0,x_2=0 ,x_3= 1 ,x_(4 )=1,x_5=1 x_1= 0,x_2=1 ,x_3= 0 ,x_(4 )=0,x_5=0 x_1= 1,x_2=1 ,x_3= 1 ,x_(4 )=0,x_5=1 Last edited by Karlen; March 3rd, 2015 at 05:53 AM.

 Tags boolean, equations, systems

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post Cloud Linear Algebra 2 October 13th, 2014 06:00 PM jojoluvsu2 Applied Math 1 August 7th, 2012 08:43 PM HellBunny Algebra 5 April 21st, 2012 09:41 PM boomer029 Algebra 2 December 27th, 2011 05:52 AM rawr-ree Linear Algebra 4 May 31st, 2010 03:54 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top