Eliminating the number of variables in an underdetermined system of Boolean equations

Question

As an example, in an underdetermined system of linear equations, we can eliminate the number of variables by substituting them.

As an example:

a+b+c+d+e=5

a+2b+3c+4d+5e=13

a+5b+4c+2d+9e=22

With five variables and three equations, we can reduce the number of variables to two:

a+b+c=5-d-e

a+2b+3c=13-4d-5e

a+5b+4c=22-2d-9e

Solve a, b, and c and representing them using d and e; essentially substituting a, b, and c with formulas containing d and e.

Now, consider a set of Boolean equations, with five variables and three equations. Can we perform a similar method (representing/substituting three of the variables with the other two) to reduce the number of variables? I'm still very new to Boolean algebra, and I am not very familiar with them - so please correct me if I have made any mistake.

Answer 1

This depends on the types of equations, i.e. the operators being used.

For XOR equations, Gaussian elimination is possible as explained here.

What happens, if the equations are restricted to disjunctions of variables?

Example:

$$a \lor b \lor c = 1$$ $$d \lor e \lor f = 0$$ $$a \lor f = 1$$

In this example, values for $d$, $e$ and $f$ must be $0$ due to the second equation. $a=1$ solves the other two equations, leaving $b$ and $c$ as don't care variables. This kind of inference or deduction is also called resolution.

Try to solve the following set of equations:

$$x\vee y\vee z=1$$ $$x\vee y\vee \neg z=1$$ $$x\vee \neg y\vee z=1$$ $$x\vee \neg y\vee \neg z=1$$ $$\neg x\vee y\vee z=1$$ $$\neg x\vee y\vee \neg z=1$$ $$\neg x\vee \neg y\vee z=1$$ $$\neg x\vee \neg y\vee \neg z=1$$

Source

Unlike in sets of linear equations, one cannot combine arbitrary Boolean equations to eliminate variables.

One common practical way to solve a set of Boolean equations is to translate the equations into Conjunctive Normal Form clauses and feed these into a SAT Solver.