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);
                }
            }
        }
    }
}

1 comment:

https://forbrukeretaten.no/mobilabonnement/ said...

Forbrukeretaten fiber optic cables are the best internet connection offered today. It guarantees high speeds for shipment of large data volumes. In addition, the lines are symmetrical, which means that the upload speed is as high as the download speed, despite the technical advantages of fiber optic cables https://forbrukeretaten.no/mobilabonnement.