My Math Forum  

Go Back   My Math Forum > College Math Forum > Complex Analysis

Complex Analysis Complex Analysis Math Forum


Reply
 
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 ?
Karlen is offline  
 
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$.
Evgeny.Makarov is offline  
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.
Karlen is offline  
Reply

  My Math Forum > College Math Forum > Complex Analysis

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 rawr-ree Linear Algebra 4 May 31st, 2010 03:54 PM





Copyright © 2019 My Math Forum. All rights reserved.