15 Boolean Expressions (logic1)

Run LPL Code  ,  PDF Document

Problem

Study how the four following Boolean expressions A,B,C,D are translated into a mathematical 0-1-ILP formulation:

A :  x ∧ y ∨ z ˙∨  w
            ˙
B  : (∨x ∧ y∨ z) ∨ w
C  :    (qi ∧ pi)
     i∧∈I
D  :    (q ∨ p )
          i   i
     i∈I
     I = {1, ...,n} ,n > 0

Modeling Steps


Listing 8: The Complete Model implemented in LPL [13]
model Logic1 "Boolean Expressions"; 
  parameter c:=4 "choose constraint"; 
  set i:= [1..9]; 
  binary variable x; y; z; w; u; p{i}; q{i}; 
  constraint 
    A if c=1: (x and y or  z) xor w; 
    B if c=2: (x and y xor z)  or w; 
    C if c=3: or{i} (p and q); 
    D if c=4: and{i} (p or q); 
  solve 'nosolve'; 
  Write('EQU'); //write the EQU-file 
end

Expression A: ((x y) z) ˙∨w

  1. The first step is to apply a definition of the logical operator ∨˙ :

    (x ˙∨ y) ≡ ((x ∨ y) ∧ (x ∨ y ))

    this gives:

    ((x ∧ y ∨ z) ∨ w)  ∧   (( (x ∧ y ∨ z) ∨ w ))
  2. The first part gives ((x z) (y z) w) which is:

    (x ∨ z ∨ w ) ∧ (y ∨ z ∨ w)
  3. The second part gives (((x y) z) w which is:

    (x ∨ y  ∨ w ) ∧ (z ∨ w )
  4. Putting the two parts together gives four clauses for A:

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

    This is the CNF (conjunctive normal form) of the constraint A. Each single clause now can be formulated as a linear constraints as follows:

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

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

Expression B: ((x y) ˙∨z) w

  1. Again, we apply the definition of ∨˙ . Hence the expression becomes:

    (((x ∧ y) ∨ z) ∧ (( (x ∧ y ) ∨ z )) ∨ w
  2. Redistributing on the left and inverse moving gives:

    ((x ∨ z) ∧ (y ∨ z) ∧ (x ∨ y ∨ z )) ∨ w
  3. Redistribute an second time gives the following CNF:

    (x ∨ z ∨ w) ∧ (y ∨ z ∨ w ) ∧ (x ∨ y ∨ z ∨ w)
  4. Again each single clause can be reformulated as a linear constraint:

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

Expression C: iI(pi qi)

The operator is the indexed operator for “or”. The constraint is in fact (note that we have I = {1,,n} ,n > 0):

(p◟1-∧-q1) ∨-(p2-∧-q◝2◜) ∨-...∨-(pn-∧-qn)◞
               n times

  1. Introduce a new binary variable ri with i I and add the constraints

    ri → (pi ∧ qi) , forall i ∈ I
  2. Substitute pi qi by ri in constraint C. This gives the system of the two constraint types:

    ∨
   r
    i
i∈I
ri →  (pi ∧ qi)  , forall i ∈ I
  3. Replacing implication and distribute gives:

    ∨
   ri
i∈I
(r  ∧ p ) ∨ (r ∧ q )  , forall i ∈ I
   i   i       i   i
  4. This can be translated straight away into linear inequalities as:

    ∑
    r       ≥ 1
     i
i∈I
1 - ri + pi ≥ 1   forall i ∈ I
1 - ri + qi ≥ 1   forall i ∈ I

An alternative of constraint C is not to introduce a new variable ri, but to generate directly a CNF. However, the CNF would be exponential large in the size of set I. Hence, from a practical point of view, it is necessary to introduce a new binary variable ri.

Expression D: iI(pi qi)

The operator is the indexed operator for “and”. The constraint is in fact (note that we have I = {1,,n} ,n > 0):

(p1 ∨ q1) ∧ (p2 ∨ q2) ∧ ...∧ (pn ∨ qn)
◟---------------◝◜----------------◞
               n times

This constraint is already in the conjunctive normal form. Hence, the translation into linear inequalities is straightforward as:

pi + qi ≥ 1 , forall i ∈ I

Questions

  1. Start LPL and look what it generates by looking at the EQU-file and the LPY-file.

Answers

  1. the first constraint A generates the following linear constraints:

                +x +z +w >= 1;
                +w +z +y >= 1;
                -x -y -w >= -2;
                -w -z >= -1;
          

    The second constraint B produces the following linear constraints:
                 x >= 1-w -z
                 y >= 1-w -z
                 1-x + 1-y + 1-z >= 1-w
          

    The third constraint C produces the following linear constraints:
                                                                                           
                                                                                           
            C:  + X50[1] + X50[2] + X50[3] + X50[4] + X50[5]
                + X50[6] + X50[7] + X50[8] + X50[9] >= 1;
            X51[1]:  + q[1] - X50[1] >= 0;
            X51[2]:  + q[2] - X50[2] >= 0;
            X51[3]:  + q[3] - X50[3] >= 0;
            X51[4]:  + q[4] - X50[4] >= 0;
            X51[5]:  + q[5] - X50[5] >= 0;
            X51[6]:  + q[6] - X50[6] >= 0;
            X51[7]:  + q[7] - X50[7] >= 0;
            X51[8]:  + q[8] - X50[8] >= 0;
            X51[9]:  + q[9] - X50[9] >= 0;
            X52[1]:  + p[1] - X50[1] >= 0;
            X52[2]:  + p[2] - X50[2] >= 0;
            X52[3]:  + p[3] - X50[3] >= 0;
            X52[4]:  + p[4] - X50[4] >= 0;
            X52[5]:  + p[5] - X50[5] >= 0;
            X52[6]:  + p[6] - X50[6] >= 0;
            X52[7]:  + p[7] - X50[7] >= 0;
            X52[8]:  + p[8] - X50[8] >= 0;
            X52[9]:  + p[9] - X50[9] >= 0;
          

    where X50{i} are the new binary variables introduced.

    The fourth constraint D produces the following linear constraints:

            D[1]:  + p[1] + q[1] >= 1;
            D[2]:  + p[2] + q[2] >= 1;
            D[3]:  + p[3] + q[3] >= 1;
            D[4]:  + p[4] + q[4] >= 1;
            D[5]:  + p[5] + q[5] >= 1;
            D[6]:  + p[6] + q[6] >= 1;
            D[7]:  + p[7] + q[7] >= 1;
            D[8]:  + p[8] + q[8] >= 1;
            D[9]:  + p[9] + q[9] >= 1;