
Complex Analysis Complex Analysis Math Forum 
 LinkBack  Thread Tools  Display Modes 
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 3th 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 3th 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  

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