Logic and Modelling – Polarity

No, this a not a post about the North and South pole ;)

Polarity and Position

Polarity defines the monotocity of the arguments of a given sub-formula at a given position. In order to do this we need to define position and polarity.

• Position – is any sequence of positive integers “a1,…,an” where n>=0. This can be written as “a1.a2. … .an”.
  When n=0, for example the sequence is empty; we call this the empty position and denote it by ε. This is normally just the entire formula A.
  
• Polarity – polarity is one of the following values given to the arguments of a given sub-formula. Either –1,0,1.

Now all we have to do is define the following notions:

1. position that we are in a given formula
2. the sub-formula of a given formula A at a position π , denoted by A|π
3. the polarity of the sub-formula at position π, denoted pol(A, π)

With these, we now have some very quick and basic definitions:

1. For EVERY formula A, ε is a position in A. such that A|ε = A and pol(A,ε)=1
   
2. Now we need to do this for the rest of the formula at all other given positions. So now we need to let A|π = B.
   
   1. If B has the form “B1 /\ … /\ Bn” or “B1 \/ … \/ Bn” then for all i Є {1, … ,n} the position π.i is a position in A. Such that:
      
      A|π.i = Bi and pol(A, π.i) = pol(A, π)
      
      In other words, the polarity stays exactly the same and doesn’t change from the polarity of the previous formula :)
      
   2. If B has the form “¬B1” then π.1 is a position in A. Such that:
      
      A|π.1 = B1 and pol(A, π.1) = –pol(A, π)
      
      So the negation of the previous polarity. If it was a 1, its now a –1 and vice versa.
      
   3. If B has the form “B1 –> B2” then π.1 and π.2 are positions in A. Such that:
      
      A|π.1 = B1 and A|π.2 = B2
      pol(A, π.1) = –pol(A.π) and pol(A, π.2) = pol(A, π)
      
      So the polarity of the left argument (B1) negates the previous polarity, where as the right argument (B2) remains the same polarity.
      
   4. If B has the form “B1 <-> B2” then for all i Є {1,2} then position π.i is a position in A. such that:
      
      A|π.i = Bi and  pol(A, π.i) = 0
      
      So it doesn’t matter what the previous polarity was, both arguments neutralise it to 0.

Example

Lets now consider the following quick example. Consider the following formula:

• ¬(((p /\ q) –> r) –> (p <-> q))

Denote this formula as A, the positions in A, sub-formulas at these positions, and the corresponding polarities are given in the following table.

To better visualise this, here is the tree for it. With this tree the red boxes are the positions and the blue boxes are the polarities.

Now lets follow through one of the branches of this tree. Say all the way down to A|1.1.2 (you do remember what that means… right?)

Well, we start off at A|ε which is the formula itself, so that has a polarity of 1. Now we go through each of the positions stated:

1. A|1 – this has a polarity of –1. Since we have just removed a “¬”, then from the rules of polarity for a “¬” we must negate the previous polarity. So –(1) = –1.
   
2. A|1.1 – Next we have the polarity of 1 again. Because of priorities we now have an implication. From the rules of polarities above, the argument on the left side (or position 1) of the implication must negate the polarity of the previous sub-formula. Since A|1 has pol=-1, then A|1.1 has pol=1.
   
3. A|1.1.2  - Finally we get a polarity of 1. Since the sub-formula at A|1.1 is another implication, then using the rules of polarities above, the argument on the right side (or position 2) of the implication must remain the same as the previous polarity. Since the polarity of A|1.1 has pol=1, then the polarity of A|1.1.2 has pol=1 (ie, unchanged).
   
4. Since we have reached the end of the tree, then we can say that this sub-formula has a position occurrence in A, and that the Boolean variable ‘r’ is positive.