Processing math: 100%

Saturday, October 26, 2013

Theorem of the alternative and logical equivalence

In the theory of linear equalities and inequalities, several fundamental results are formulated as a theorem of the alternative: two alternatives are given, and exactly one of the alternatives is satisfied at any one time. A well known example is Farkas' lemma (1894):

For a real matrix A and real vector b, exactly one of the following conditions is true:


  1. There exists a real nonnegative vector x such that Ax=b
  2. There exists a real row vector y such that yA is nonnegative and yb is negative. 

where we say a real vector is (non)negative if all its entries are (non)negative.  Consider a theorem of the alternative given in the following form: given two alternatives P or Q, only one of them is true at any time, no more and no less.  The truth table for this conclusion (denoted as Z) is then:

P Q Z
0 0 0
1 0 1
0 1 1
1 1 0

This means that Z is equal to PQ which is equivalent to P¬Q which is equivalent to ¬PQ.
Thus the theorem

Exactly one of the two statements P and Q is true

can also be restated as:

P is true if and only if Q is false

or as:

P is false if and only if Q is true

Setting the 2 statements in Farkas' Lemma above as P and Q, then
P¬Q is written as

Let A be a real matrix and let b be a real vector.  Then there exists a nonnegative real vector x such that Ax=b if and only if for each row vector y either yA is not a nonnegative vector or yb is nonnegative.

Given that PQ is logically equivalent to ¬PQ, this can be rewritten as

Let A be a real matrix and let b be a real vector.  Then there exists a nonnegative real vector x such that Ax=b if and only if yb is nonnegative for each row vector y such that yA is a nonnegative vector.

which is the form of Farkas' Lemma as stated in A. Schrijver, Theory of Linear and Integer Programming, Wiley, 1998.

No comments:

Post a Comment