4 Translating Boolean Expressions

First of all, It is easy to verify that all Boolean operators in Table 3 can also be formulated as mathematical linear expressions if x and y are binary variables with x,y ∈{0, 1} as shown in Table 4. The true (1) and false (0) values of a proposition x in Table 3 is interpreted as numerical 1 and 0 values in Table 4. The negation x (or x) can be substituted by 1 - x.












x y x y = 0 x + y 1 x = 1 - y x y x = y x y x y = 0 x + y = 0










1 1 1 1 0 1 1 1 0 0
1 0 0 1 1 0 0 1 1 0
0 1 0 1 1 1 0 0 1 0
0 0 0 0 0 1 1 1 1 1











Table 4: The Boolean Operators as Mathematical inequalities

Table 5 displays a collection of further equivalences and it is easy to check their identity by applying the true/false (0,1) values to each proposition (binary) and compare the result.




Propositions: P,X,Y, 0-1 binary variables p,x,y,


X x 1
X (or x) x 0
X Y x + y 1
X Y Z x + y + + z 1
X Y x 1, y 1 (or x + y 2
X Y Z x 1, y 1, , z 1
(or: x + y + + z n)
X Y x y
X ˙∨Y x + y = 1
X ˙∨Y ˙∨∨˙Z x + y + + z = 1
X Y x = y
X Y Z x = y = = z
X nor Y (or: X Y x 0, y 0
X Y Z x + y + + z 0
X nand Y (or: X Y x + y 1
X Y Z x + y + + z n - 1
X Y x + y 1
P X Y Z x p, y p, , z p
(or: x + y + + z np)
P X Y Z x + y + + z p
X Y Z P x + y + + z - p n - 1
X Y Z P x p, y p, , z p
(or: x + y + + z np)
X (Y Z) x = 1, y + z 1
X (Y Z) x + y 1, x + z 1
(or: 2x + y + z 2)
X1 Xn Y 1 Y n x1 + x2 + + xn-
(y1 + y2 + + yn) n - 1
P X Y Z x + y + + z - np n - 1,
x p, y p, , z p
P X Y Z x + y + + z p,
x p, y p, , z p



Table 5: Logic-mathematical Equivalences

However, translating logical constraints into mathematical linear inequalities in a systematical way requires a precise procedure. The general idea is to transform the Boolean expression into a conjunctive normal form eventually by introducing additional (binary) variables, then it is easy to get the linear inequalities from the resulting clauses using the given identities. Before presenting a systematical procedure, let us try to translate a concrete Boolean expression into purely mathematical linear inequalities (the example is implemented in model logic1) :

              ˙
((x ∧ y) ∨ z) ∨ w

Step 1: replace  a ˙
∨b  with  (a b) (a b). This gives:

                     -----------  --
((x ∧ y ) ∨ z ∨ w) ∧ ((x ∧ y) ∨ z ∨ w )

Step 2: Move the negation inwards (using the Morgan’s law). This gives:

((x ∧ y) ∨ z ∨ w) ∧ (((x-∨ y) ∧ z-) ∨ w-)

Step 3: Move the or-operators inwards over the and-operators. This gives the following conjunctive normal form (CNF) :

(x ∨ z ∨ w) ∧  (y ∨ z ∨ w) ∧  (x-∨ y ∨ w-) ∧ (z-∨ w)

Step 4: Translate the 4 clauses into 4 linear inequalities as follows:

x + z + w              ≥  1
y + z + w              ≥  1
1 - x + 1 - y + 1 - w  ≥  1
1 - z + 1 - w          ≥  1