Logical Identities

  1. Logical And
  2. Logical Or
  3. Basic Laws of Boolean Algebra
  4. Advanced Laws of Boolean Algebra
The conditional clauses or predicates of programming's "if" and "while" statements are part of a system of mathematics called Boolean Algebra. This is an algebra over two values, True and False, with operators AND, OR and NOT. Knowning this algebra and its rules gives you important control over the way you construct your predicates for programming.

Logical And

Certain additional comments are necessary when talking Java rather than some abstract mathematics. For instance, there is an identity relating two programs:

      if ( a && b ) { S ; }
is the same as
      if ( a )
        if ( b ) { S ; }
where S represents any statement. This means that certain nested if's are equivalent to bringing together the conditional clauses by &&. In terms of pure mathematics, logical-and is commutative:
     a AND b = b AND a  // pure mathematics
however a && b is not the same as b && a in many programming languages, including Java.

Consider the program:

     if ( (i>0) && (f(i) ) { S ; }
where f is a function taking positive integers and returning boolean. By interpreting this as:
     if ( i>0 )
        if ( f(i) ) { S ; }
we see that f is never even called if i is out of its proper range. In general, for a complex logical-and such as:
   ( a && b && ... && z )
Java evaluates the expressions a, b, ... , z from left to right until some expression yeilds false. Since one false expression forces the complete logical-and to evaluate false, there is no reason to continue. This means that in certain instances, the order of the expressions is important, in contrast to the mathematical commutivity of logical-and. Here is an other example:
   if ( (x!=0.0) && (1.0/x) > 2.0 ) { S ; }
Reverse the order of the expressions in the logical-or and sometimes, when x==0.0, you will have a run-time error in the expression 1.0/x.

Logical Or

The logical-or can also be interpreted more closely:

    if ( a || b ) { S ; }
is the same as:
    if ( a ) { S ; }
       else if ( b ) { S ; }
Java evaluates the components of the logical-or, a then b and so on, until one yeilds true. That is, for a complex logical-or:
    ( a || b || ... || z )
Java evaluates the expressions a, b, ... , z from left to right until some expression yeilds true. Since one true result causes the entire logical-or to evaluate true, there is no reason to continue evaluation. Once again, while logical-or is commutative in pure mathematics, in many programming languages, including Java, the order of the expressions is important. Here is an example:
    if ( (x==0) || ( 1.0/x > 2.0 ) ) { S ; }
Reverse the order of the expressions in the logical-or and sometimes, when x==0.0, you will have a run-time error in the expression 1.0/x.

Basic Laws of Boolean Algebra

     ( a && (!a) ) == false
     ( a || (!a) ) == true
This means that the program:
     if ( (i==1) && (i!=1) { S ; }
is "wrong" in that S will never be run. The program:
    if ( (i==1) || (i!=1) { S ; }
is "wrong" in that S will always be run.
    (a && a ) == a
    (a || a ) == a
These laws have to be interpreted carefully for Java. Although
   if ( (i==1) && (i==1) ) { S ; }
is "wrong" in that the same condition is checked twice, a program such as:
   if ( (i++=1) && (i++=1) ) { S ; }
is "wrong" in that S will never be run and i might or might not be incremented twice.

Advanced Laws of Boolean Algebra

The absorption law

    a || ( a && b ) == a
    a && ( a || b ) == a

The distribution law

    a && ( b || c ) == ( a && b ) || ( a && c ) 
    a || ( b && c ) == ( a || b ) && ( a || c )

DeMorgan's theorem

    !( a && b ) == (!a) || (!b)
    !( a || b ) == (!a) && (!b)
Note again, that all of these are mathematical facts which must be carefully interpreted in Java. In particular, if the expressions have side-effects ( such as incrementing a variable), or if the order of expression evaluation is important, then the equivalence is not perfect.