Simultaneous Boolean equations

C

ChasW

New member
Joined
Nov 23, 2021
Messages
3
I have a set of Boolean equations:-

1 = b'c'd' + bcd' + a'bd + ac'd
1 = a'bc'd' + b'c'd + abc + a'b'c + b'cd'
0 = a'b'c'd + a'bc + abc' + a'cd' + ab'd'
0 = a'b'cd + a'bc' + b'c'd' + abc + a'bd'

Is there any automated way to solve sets of Boolean expressios such as this? I am not interested in a brute force approach.

There must be widespread applications for mathematics to solve these sorts of problems, but a search of the internet is not helpful. The only things I have found are written in totally non-understandable mathematical language.

(BTW The solution to the above equations is abcd = 1001)
 
ChasW said:
Is there any automated way to solve sets of Boolean expressios such as this? I am not interested in a brute force approach.
Click to expand...

I'm pretty sure that solving a general boolean equation is just "NP hard" and therefore it seems that some kind of brute force is inevitable (see * below). It might be possible that, with the specific types of equations you have, some kind of optimisation may be possible. But we'd need more information in order to think about that. Do you have few variables and many equations, or vice-versa? Are the supplied equations always in DNF (click). Do the supplied equations each have a length no more than 5 terms? Is only one solution expected? etc

* - You might be aware of this (sorry if you are) but sets of boolean equations, like the ones you supplied, can be reduced to a single equivalent equation. For your scenario...
0 = (b'c'd' + bcd' + a'bd + ac'd)' + (a'bc'd' + b'c'd + abc + a'b'c + b'cd')' + a'b'c'd + a'bc + abc' + a'cd' + ab'd' + a'b'cd + a'bc' + b'c'd' + abc + a'bd'
 
Cubist said:
I'm pretty sure that solving a general boolean equation is just "NP hard" and therefore it seems that some kind of brute force is inevitable (see * below). It might be possible that, with the specific types of equations you have, some kind of optimisation may be possible. But we'd need more information in order to think about that. Do you have few variables and many equations, or vice-versa? Are the supplied equations always in DNF (click). Do the supplied equations each have a length no more than 5 terms? Is only one solution expected? etc

* - You might be aware of this (sorry if you are) but sets of boolean equations, like the ones you supplied, can be reduced to a single equivalent equation. For your scenario...
0 = (b'c'd' + bcd' + a'bd + ac'd)' + (a'bc'd' + b'c'd + abc + a'b'c + b'cd')' + a'b'c'd + a'bc + abc' + a'cd' + ab'd' + a'b'cd + a'bc' + b'c'd' + abc + a'bd'
Click to expand...
You are 100% right about NP. In fact, Boolean Satisfiability Problem is the very first NP-complete problem (https://en.wikipedia.org/wiki/Boolean_satisfiability_problem).
 
Thank you for your responses.

I feared as much (that the solution was NP). I'm messing around with cryptographic algorithms (in particular DES), and realise that each encrypted bit can be represented as a function of the key bits and the plain text bits. Each function will be incredibly long but finite. For a given Plain Text message, there will be 56 unknown key bits and 64 equations. Note that the Substitution boxes can be represented as Boolean functions. Although DES (not DES3) has long since been cracked using a specific board with many CPUs, I don't think I have the patience to wait a few centuries with my modest laptop. I need a quantum computer!

Hence my question about solving simultaneous Boolean equations. If I found a way to do this, I might have solved one of the Millenium Puzzles (P vs NP)!!!!
 
You must log in or register to reply here.
Top