0.3 Boolean Logic

0.3.1 Definition

Here is an alternative, recursive, definition of Boolean Logic:

  1. The two Boolean constants are MATH or MATH .

  2. Boolean variables MATH etc,can take on the values $\QTR{Large}{1}$or $\QTR{Large}{0}$ .

  3. Boolean constants and Boolean variables are Boolean expressions.

  4. If $\QTR{Large}{p}$ and $\QTR{Large}{q}$ are Boolean expressions, then $\QTR{Large}{p}$ MATH $\QTR{Large}{q}$ is a Boolean expression, whose truth table is

    .

  5. If $\QTR{Large}{p}$ and $\QTR{Large}{q}$ are Boolean expressions, then $\QTR{Large}{p}$ $\QTR{Large}{\vee }$ $\QTR{Large}{q}$ is a Boolean expression, whose truth table is

    .

  6. If $\QTR{Large}{p}$ is a Boolean expressions, then $\lnot $ $\QTR{Large}{p}$ is a Boolean expression, whose truth table is

    .

In forming complex Boolean expressions, the precedence levels of logical operators is:

  1. $\lnot $

  2. MATH

  3. MATH

0.3.2 The Truth Table of Complex Boolean Expressions:

Using 4-6 above, we itteratively compute the Truth Tables of any Boolean expression. As an example, consider MATH MATH



We call two Boolean expressions , $\QTR{Large}{P}$ and $\QTR{Large}{Q}$ "equal" , written $\QTR{Large}{P=Q}$, if they have the sameTruth Tables.

One should check that if $\QTR{Large}{R\ }$is a Boolean expression containing $\QTR{Large}{P}$ and is MATH the Boolean expression that is the result of substituting $\QTR{Large}{Q}$ for every occurrence of $\QTR{Large}{P}$ then MATH.

0.3.3 The Completeness of Boolean Operations

The example in 1.3.2 be though of a special case of the following:

0.3.4 Theorem

Any truth table is the truth table of a Boolean expression that is the sum of products or product of sums of Boolean variables and their negations.

Indeed we make do with negation and sum, or negation and product. (See1.3.5 below)

Here is an example that easily generalizes



0.3.5 Derived Boolean Operations

There are a number of important Boolean expressions that are representated by their own operation symbol. We will particularly want the following three:

MATH



MATH



MATH



Note that, amongst others:

MATH

MATH

MATH

Finally, as promised in 2.4

MATH

and

MATH

In point of fact, we can make do with the single Boolean operator MATH, the "Sheffer stroke."

Here is its truth table:



Check that:

MATH

MATH

0.3.6 Tautologies

A tautology is a Boolean expression that is always $\QTR{Large}{true}$, that is its truth table contains only in the result column.

Examples of tautologies:

Tautologies and proofs are closely related concepts in Boolean logic.

0.3.7 The Tautology Problem

The question as to whether or not a given logical expression is a tautology known as the "tautology problem."

Formally, the tautology problem is solvable in that we need only construct the truth table for a given Boolean expression. If the result column is all $\QTR{Large}{1}$'s then the expression is a tautology.

The more interesting question is how hard (in the computational work sense ) it is to solve the problem. If a Boolean expression has $\QTR{Large}{n}$ propositional variables then the corresponding truth table has MATHrows. Hence, roughly, a Boolean expression with $\QTR{Large}{n}$ propositional variables requires MATHcomputations to determine whether or not it is tautology.

The associate arithmetic work is as follows:

Since MATH , the work associated with the $\QTR{Large}{2n}$ variable tautology problem is MATH times the work associated with the $\QTR{Large}{n}$ variable tautology problem. Thus, assuming that the $\QTR{Large}{n}$ variable tautology problem is the present "practical" limit of computers, it would require $\QTR{Large}{n}$ Moore Cycles to develop a computer capable of solving the $\QTR{Large}{2n}$ variable tautology problem.