Friday, March 11, 2005

Tautologies

Introduction

A boolean expression that always evaluates to true, is called a tautology.

Using tautologies, it's often possible to simplify complex boolean expressions into simpler ones. This is important because programs may run faster and could be easier to understand. For instance, p & (p | q) could be simplified to p. Similarly, (p | q) & !(p & q) could be simplified to p ^ q, using the Java conditional operator ^ (xor). The boolean variables p and q could also represent complex boolean expressions, but in these examples we use simple expressions like false and true.

Program

Let's take a closer look at one of De Morgan's Laws.

!(p | q)        == (!p & !q);           // De Morgan's Laws

We can easily check if De Morgan's Law is a tautology, just by testing each combinations of p and q with a Java application.

public class Tautologies {
    public static void main(String[] args) {
        System.out.println("De Morgan's Laws");
        boolean p, q, r, A;
        p = false; q = false; A = !(p | q) == (!p & !q); System.out.println(A);
        p = false; q = true;  A = !(p | q) == (!p & !q); System.out.println(A);
        p = true;  q = false; A = !(p | q) == (!p & !q); System.out.println(A);
        p = true;  q = true;  A = !(p | q) == (!p & !q); System.out.println(A);
    }
}

Output

This application produces the following output.

De Morgan's Laws
true
true
true
true

Similarly you may check if (p & (q & r)) == ((p & q) & r) is a tautology. It is, because each test will print true.

        System.out.println("Associative Laws");
        p = false; q = false; r = false; A = (p & (q & r)) == ((p & q) & r); System.out.println(A);
        p = false; q = false; r = true;  A = (p & (q & r)) == ((p & q) & r); System.out.println(A);
        p = false; q = true;  r = false; A = (p & (q & r)) == ((p & q) & r); System.out.println(A);
        p = false; q = true;  r = true;  A = (p & (q & r)) == ((p & q) & r); System.out.println(A);
        p = true;  q = false; r = false; A = (p & (q & r)) == ((p & q) & r); System.out.println(A);
        p = true;  q = false; r = true;  A = (p & (q & r)) == ((p & q) & r); System.out.println(A);
        p = true;  q = true;  r = false; A = (p & (q & r)) == ((p & q) & r); System.out.println(A);
        p = true;  q = true;  r = true;  A = (p & (q & r)) == ((p & q) & r); System.out.println(A);
        System.out.println();

The Laws of Logic

!!p             == p                    // Law of Double Negation
!(p | q)        == (!p & !q);           // De Morgan's Laws
!(p & q)        == (!p | !q)            // De Morgan's Laws
(p | q)         == (q | p)              // Commutative Laws)
(p & q)         == (q & p)              // Commutative Laws)
(p | (q | r))   == ((p | q) | r)        // Associative Laws
(p & (q & r))   == ((p & q) & r)        // Associative Laws
(p | (q & r))   == ((p | q) & (p | r))  // Distributive Laws
(p & (q | r))   == ((p & q) | (p & r))  // Distributive Laws
(p | p)         == p                    // Idempotent Laws
(p & p)         == p                    // Idempotent Laws
(p | false)     == p                    // Identity Laws
(p & true)      == p                    // Identity Laws
(p | !p)        == true                 // Inverse Laws, Law of Excluded Middle
(p & !p)        == false                // Inverse Laws, Law of Contradiction
(p | true)      == true                 // Domination Laws
(p & false)     == false                // Domination Laws
(p | (p & q))   == p                    // Absorption Laws
(p & (p | q))   == p                    // Absorption Laws

More Tautologies

((p | q) & !(p & q)) == (p ^ q)
(p != q) == (p ^ q)

Discussion

Boolean expressions may be simplified using tautologies. Tautologies like (p | (p & q)) == p always evaluates to true. So, both sides of the equality operator always have to give the same result. A complicated boolean expression like p | (p & q) can be replaced by a simpler expression like p.

The program testing for tautologies could perhaps be "simplified" using loops. The program also demonstrates how to convert between boolean and int.

public class Main {
    
    public static void main(String[] args) {
        boolean p, q, r, A;
        
        for (int i = 0; i <= 1; i++) {
            p = i == 0 ? false : true;
            for (int j = 0; j <= 1; j++) {
                q = j == 0 ? false : true;
                for (int k = 0; k <= 1; k++) {
                    r = k == 0 ? false : true;
                    
                    A = ((p | q) & !(p & q)) == (p ^ q); 
                    System.out.println(p + " " + q + " " + r + " = " + A);
                }
            }
        }
    }
}

No comments: