Here is an alternative, recursive, definition of Boolean Logic:
The two Boolean constants are
or
.
Boolean variables
etc,can take on the values
or
.
Boolean constants and Boolean variables are Boolean expressions.
If
and
are Boolean expressions, then
is a Boolean expression, whose truth table is
.
If
and
are Boolean expressions, then
is a Boolean expression, whose truth table is
.
If
is a Boolean expressions, then
is a Boolean expression, whose truth table is
.
In forming complex Boolean expressions, the precedence levels of logical operators is:
Using
4-6 above, we itteratively compute the Truth Tables of
any Boolean expression. As an example, consider
We call two Boolean
expressions ,
and
"equal"
, written
,
if they have the sameTruth Tables.
One should check that if
is
a Boolean expression containing
and
is
the
Boolean expression that is the result of substituting
for every occurrence of
then
.
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
There are a number of important Boolean expressions that are representated by their own operation symbol. We will particularly want the following three:
Note that, amongst others:
Finally, as promised in 2.4
and
In point of fact, we can make do with the single Boolean operator
,
the "Sheffer stroke."
Here is its truth table:
Check that:
A tautology is a Boolean expression that is always
,
that is its truth table contains only in the result column.
Examples of tautologies:
(
Tautologies and proofs are closely related concepts in Boolean logic.
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
'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
propositional variables then the corresponding truth table has
rows.
Hence, roughly, a Boolean expression with
propositional variables requires
computations
to determine whether or not it is tautology.
The associate arithmetic work is as follows:
Since
, the work associated with the
variable tautology problem is
times
the work associated with the
variable tautology problem. Thus, assuming that the
variable tautology problem is the present "practical" limit of computers, it
would require
Moore Cycles to develop a computer capable of solving the
variable tautology problem.