Proofs – By Cases

Proofs by cases breaks a problem into smaller easier to manage sub problems.

Take a couple of  java logical expressions:

if (( x > 0 ) || ( x <= 0 && y > 100 ))

and

if ( x > 0 || y > 100 )

The question is, How can we prove these two different expressions in fact behave the same way.

Theorem: The two preceding java expressions behave in the same manner.

Proof. The proof is a by case analysis, there are two cases:

1. x > 0 and the exclusive OR evaluates true immediately.
2. x <= 0 and the exclusive OR moves to it’s second operand

Case 1: When x > 0 both expressions immediate evaluate to true and the following code executes. The expressions behave the same in this case.

Case2: When x <= 0 things get a little more interesting.  This time the first operand to the OR evaluates to false and now the second operand is evaluated.  In the case the x > 0 evaluates to false implies that x <= 0 it in fact has to be true for us to even be asking the question.

Lets fill in our statements with true instead of x conditions

if (( true || ( true && y > 100 ))

and

if ( true || y > 100 )

Now it’s clear to see that when we remove the true,

if ((        || (        && y > 100 ))

and

if (          || y > 100 )

It is now  clear to see that how y > 100 evaluates is the only part of this expression of any consequence and therefore the two expressions behave the same in this case as well.