Propositional Logic

Logical Expressions

We can define logical expressions using a recursive definition:

Propositional variables (whose value is TRUE or FALSE) and the propositional constants TRUE and FALSE are logical expressions.
If LE1 and LE2 are logical expressions, then LE1 AND LE2 is a logical expression, whose value is TRUE if both LE1 and LE2 have the value TRUE, and is FALSE otherwise.
If LE1 and LE2 are logical expressions, then LE1 OR LE2 is a logical expression, whose value is TRUE if either LE1 or LE2 have the value TRUE, and is FALSE otherwise.
If LE1 is a logical expression, then NOT LE1 is a logical expression, whose value is TRUE is LE1 has the value FALSE, and is FALSE otherwise.

The precedence levels of logical operators is:

By assigning values to the variables in a logical expression, we also assign a value to the expression itself.

Example: given the expression "(p AND q) OR r", if p=TRUE, q=TRUE, and r=FALSE, then the value of the expression is TRUE.

Boolean Functions and Truth Tables

The meaning (or value) of a logical expression is a Boolean function from the set of possible assignments of truth values for the variables in the expression to the values {TRUE,FALSE}.

Example: given the expression "(p AND q) OR r", we can describe the Boolean function that determines the value of the expression by considering all combinations of value assignments for p, q, and r.

      p	  q 	r   (p AND q) OR r
      ------------------------------
      T	  T	T     T
      T	  T	F     T
      T	  F	T     T
      T	  F	F     F
      F	  T	T     T
      F	  T	F     F
      F	  F	T     T
      F	  F	F     F

The above table describing the Boolean function "(p AND q) OR r" is called a truth table. In a truth table, there is a column for each variable in the expression, and each row in the table corresponds to an assignment of values to variables. The final column gives the value of the expression for the particular set of variable assignments given in the row.

We can define the basic operators in terms of a truth table as follows (where we use 1 and 0 instead of TRUE and FALSE):

     p    q    p AND q    p OR q    NOT p
     ------------------------------------
     0    0       0         0        1
     0    1       0         1        1
     1    0       0         1        0
     1    1       1         1        0

Note that a truth table for a function of N variables has 2^N rows.

Other Functions of Two Variables

We have seen a few functions of two variables, but there are many more. In fact, there are 16 different Boolean functions of two variables.

Why 16? Because each function corresponds to a different assignment of values to the last column of a truth table with four rows, and there are 16 different such assignments.

In general, there are 2^2^N different Boolean functions of N variables.

Here are some additional functions of two variables that are frequently used:

     p    q    p->q    p==q   p NAND q   p NOR q
     -------------------------------------------
     0    0     1        1        1         1
     0    1     1        0        1         0
     1    0     0        0        1         0
     1    1     1        1        0         0

Comments on these functions:

Implication: "p -> q" or "p implies q" means that whenever p is TRUE, so is q. The only way "p -> q" can be FALSE, is if p is TRUE, and q is FALSE.
Equivalence: "p == q" means that p and q have the same value.
NAND: "p NAND q" is the same as "NOT (p AND q)".
NOR: "p NOR q" is the same as "NOT (p OR q)".
Precedence is (from highest to lowest): NOT, NAND, NOR, AND, OR, ->, ==.

Computing Expressions with Truth Tables

We can compute the value of an expression using truth tables. We create a table for all possible values of the variables, and all subexpressions in the expression.

Compute the value of the following expression E for all possible truth assignments: (p -> q) -> (q -> r)

      p   q   r   p->q   q->r   E
      ---------------------------
      0   0   0    1      1     1
      0   0   1    1      1     1
      0   1   0    1      0     0
      0   1   1    1      1     1
      1   0   0    0      1     1
      1   0   1    0      1     1
      1   1   0    1      0     0
      1   1   1    1      1     1

Note that the column for the value of q->r is the same as the column for the value of the entire expression E. We've established the equivalence of those two columns, which means:

       (p -> q) -> (q -> r) == q->r.

Generating Expressions from Functions

We are often given a Boolean function in truth table form and must derive a corresponding logical expression.

For example, digital circuits are constructed from digital elements that compute the basic Boolean operations (such as NOT and NAND).

Given a specific function expressed as the results of variable assignment (such as a circuit that adds two bits together and produces a sum and a carry bit, all of which is expressed in truth table form), we'd like the corresponding logical expression so that we can construct a circuit for the function.

We can construct such a logical expression directly from the truth table for the function.

The resulting expression uses only AND, OR, and NOT as operators.

Exclusive Or: Expression from Truth Table

Exclusive or (XOR) is another well-known function of two variables. The truth table for XOR is:

      p     q     XOR
      ---------------
      0     0      0
      0     1      1
      1     0      1
      1     1      0

We can construct an expression for XOR in terms of AND, OR, and NOT, using the following reasoning:

The second row tells us that p XOR q is TRUE when p is FALSE and q is TRUE. In other words, p XOR q is TRUE if NOT p AND q is TRUE.
The third row tells us that p XOR q is TRUE when p is TRUE and q is FALSE. In other words, p XOR q is TRUE if p AND NOT q is TRUE.
The other rows tell us that p XOR q is FALSE in all other cases.
So p XOR q is TRUE if NOT p AND q is TRUE, or if p AND NOT q is true.

From the above, we determine that the following is a logical expression for the function p XOR q:

      (NOT p AND q) OR (p AND NOT q)

Conjunctive and Disjunctive Normal Forms

A Boolean expression is in disjunctive normal form if it is expressed as the sum (OR) of products (AND). That is, a Boolean expression B is in disjunctive normal form if it is written as:

      A1 OR A2 OR A3 OR ... An

where each Ai is expressed as

      T1 AND T2 AND ... AND Tm

where each Ti is either a simple variable, or the negation (NOT) of a simple variable. Each of the terms Ai is called a minterm.

A Boolean expression is in conjunctive normal form if it is expressed as the product (AND) of sums (OR). That is, a Boolean expression B is in conjunctive normal form if it is written as:

      O1 AND O2 AND O3 AND ... On

where each Oi is expressed as

      T1 OR T2 OR ... OR Tm

where each Ti is either a simple variable, or the negation (NOT) of a simple variable. Each of the terms Oi is called a maxterm.

Normal Forms in Truth Tables

Conjunctive and disjunctive normal forms are duals of each other; either one may be used to generate a logical expression from a truth table.

With these normal forms, we can be more precise about how to generate a logical expression from a truth table.

To construct a logical expression in disjunctive normal form from a truth table:

Build a minterm for each row of the table where the function is true.
For each variable whose value is 1 in that row, we include the variable in the minterm; if a variable is 0 in that row, we include the negation of the variable in the minterm.
The expression consists of the OR of all the minterms.

We could, of course, construct an expression in disjunctive normal form by using maxterms and AND.

A Logical Expression for an Adder

A binary integer adder can be constructed from a series of one-bit adders. A one-bit adder takes two one-bit operands (x and y) and a carry bit from the previous one-bit adder (ci), and produces the sum of those bits, and a carry-out bit (co).

We can define a Boolean function corresponding to the adder in the form of a truth table. We can then construct logical expressions for s and co, from which we could build a circuit.

  x    y   ci    co   s
  ---------------------
  0    0    0    0    0
  0    0    1    0    1    s : NOT x AND NOT y AND ci
  0    1    0    0    1    s : NOT x AND y AND NOT ci
  0    1    1    1    0    co: NOT x AND y AND ci
  1    0    0    0    1    s : x AND NOT y AND NOT ci
  1    0    1    1    0    co: x AND NOT y AND ci
  1    1    0    1    0    co: x AND y AND NOT ci
  1    1    1    1    1    co,s: x AND y AND ci

The logical expression for s is:

  (NOT x AND y AND ci) OR (x AND NOT y AND ci) OR
  (x AND y AND NOT ci) OR (x AND y AND ci)

The logical expression for co is:

  (NOT x AND NOT y AND ci) OR (NOT x AND y AND NOT ci)
  OR (x AND NOT y AND NOT ci) OR (x AND y AND ci)

Completeness of Boolean Operators

The previous construction of a logical expression from a truth table showed how to represent any Boolean function as a sum of products or product of sums.

Since we can represent any Boolean function using AND, OR, and NOT, these operators form a complete set for Boolean functions.

We can show that the NAND operator alone is sufficient to generate every Boolean function, by showing how to implement AND, OR, and NOT in terms of NAND.

      p   q  p NAND 1 q NAND 1 p NAND q  E1   E2
      --------------------------------------------
      0   0      1       1        1      0     0
      0   1      1       0        1      0     1
      1   0      0       1        1      0     1
      1   1      0       0        0      1     1
  
    E1: p AND q == ((p NAND q) NAND TRUE)
    E2: p OR q  == ((p NAND TRUE) NAND (q NAND TRUE))
    E3: (NOT p) == (p NAND TRUE)

A similar construction can be used to show that NOR is also sufficient to generate every Boolean function.

Thus, we can generate digital circuits for any Boolean function using just NAND or NOR operators (or components).

Tautologies

A tautology is a logical expression that is always TRUE, regardless of the assignment of truth values to the variables in the expressions.

Examples of tautologies:

TRUE
TRUE OR p
p OR NOT p
NOT (p AND NOT p)
p == p
(p OR q) == p OR (NOT p AND q)
(p == q) -> (p -> q)

If we can establish that "LE1 == LE2" is a tautology, then no matter what values we assign to the variables in LE1 and LE2, we know that "LE1 == LE2" has the value TRUE.

If "LE1 == LE2" is a tautology, then we can substitute LE2 for LE1 (or vice versa) in any expression, without changing the value of the expression.

The Tautology Problem

It is an interesting question to ask whether a given logical expression is a tautology. This question is known as the "tautology problem."

To solve the tautology problem, we need only construct the truth table for the logical expression. If the expression has the value TRUE for all possible assignment values for the variables in the expression (that is, if the entire column for the expression in the truth table is TRUE), then the expression is a tautology.

Note that the truth table will have 2^k rows and n columns, where the original expression has k variables and n operators. Thus, this algorithm requires O(2^kn) time, ie. exponential time.

There is no known algorithm for the tautology problem that takes less than exponential time. Such problems are called "intractable" because large instances of the these problems cannot be solved in a reasonable amount of time.

Another such intractable problem is the "satisfiability problem" which asks whether there is an assignment of truth values to variables in a logical expression that makes the expression TRUE. There is no known algorithm for this problem that is more efficient than cycling through all possible combinations of truth assignments for the variables.