We will return soon to describe one more function that takes truth
values as inputs, but it may be easier to understand its importance
after some introduction to the idea of mathematical functions that
have the value
true for all possible inputs, in other
words for all things in the universe. These sorts of functions
are mathematically true statements.
Mathematics is especially interested in statements that are true by mathematical reasoning – in other words theorems. If a mathematical statement has variables in it, the statement is a true one if it is true regardless of the values of the variables. To emphasize that is true for all possible values of the variables, these sorts of statements are sometimes described as universally true. We will sometimes refer to them as “true everywhere”.
As an example let’s consider the statement that every number is either
less than 100 or greater than 10. We could state this as
x < 100 | x > 10. In the picture for this
statement all shaded areas represent cases where the statement is
This picture shows everything in the world (all numbers) in one or both of the groups, and shows that some numbers are in both groups.
A more conventional and more informative picture might show a number line and the values having both of the properties, like this:
x < 100 | x > 10 is true regardless
of the value of
x. In mathematics, if the truth of a
statement does not depend on the values of variables in it, it
is considered simply a true or valid statement.
For a statement with “and” to be true, both of its parts must be true.
In the statement’s picture, both statements must be true at every spot
in the picutre. Here is a picture illustrating a statement
A & B that is true, where A and B are both
Let’s look at another typical kind of statement that has a logical
meaning, such as “all birds have wings”. We might also express this
as “if x is a bird then x has wings”. In our notation we can write
(bird x) implies (wings x) or alternatively
bird x => wings x.
The picture below illustrates a scenario where the statement is true. The area representing all things with wings contains the entire area that represents all birds. There are also areas of the picture to represent things with wings that are not birds, such as bats in the real world, and flying insects.
Any picture of this kind where one area encloses another (or occupies the same area) illustrates a true statement of this kind. But is there a system for shading pictures like this so they are completely shaded exactly when the statement is true? It turns out there is.
Let’s consider a picture where the statement is not always true, like this:
It is clear right away which part of the picture makes the statement not always true – the part of the “birds” circle outside the “wings” area.
Anything in the picture that is not a bird does not affect the truth of the statement. If something is not a bird, it does not affect whether this statement about birds is true. If every part of the picture is either in the “wings” circle or not in the “birds” circle, the statement is true.
Returning to functions with truth values as inputs and outputs, we can see how to define one more key function. This function enables us to express statements like “all birds have wings” mathematically. It takes two truth values as inputs and produces true or false as its value. The previous example and pictures above apply here once again.
We call the function
⇒), and it enables us to make statements that say
one thing implies another. Here are two picture as before, but with
shading to show the areas where the expression
(bird x) ⇒ (wings x) has
true as its value. First one where
it is true everywhere:
Its truth table being:
In this scenario all birds do indeed have wings so the function is behaving as intended. And now a picture where the statement is not true everywhere:
The birds without wings are represented by the small white area with
no shading. This is exactly the area where the value of the
implies function is false. In this picture not all
birds have wings, so the function is indeed behaving as intended.
Special situations can lead classical logic to peculiar conclusions. Can all birds larger than elephants fly to the moon? In ordinary life most of us would not say something like this because we know there are no birds larger than elephants. But nothing in our logic prohibits such a statement, and if there are no birds larger than elephants in our world, our logic takes this to be a true statement.
How can this be? Consider that there are no examples that break
the rule, no birds that are larger than elephants but
cannot fly to the moon! The truth table entries in the row where the
first input is
false both have the value
true, so the implies function has the value
true everywhere. If the there are no birds larger than
elephants, all of them can fly to the moon!
Mathematicians recognize that this is a strange situation and refer to such as statements as vacuously true, meaning true but useless because their conditions never apply. In standard logic things that do not exist can have any property, even contradictory properties. Taking our example a couple of steps further, all birds larger than elephants are blue, and all birds larger than elephants are also green. This is possible only because these statements are vacuous.
The logical functions can be combined into complex expressions. In
the lunch example, where D is an abbreviation for “delicious” and E is
an abbreviation for “easy”, the expression
(not ((D x) & (E x))) refers to things that are
not easy and delicious.
The value of this function at each point depends on the values of
(D x) and (E x) at the same point, and its
truth table can be computed by first looking up the value in the truth
table for and, then looking up the value of the result in
the table for not.
(not (D x) & not (E x)) refers to things
that are neither delicious nor easy; unfortunate for the eater, but
fortunate for things that do not wish to be eaten.
Once again we can build each entry in this truth table by looking up
the values of the subexpressions, first negating each input, then
looking up the results in the table for
expressions combine the same way arithmetic expressions do, but the
calculation is even easier because you only have to look up the
results of each part in a table.
Some statements are not just true everywhere, they are true everywhere
in every possible picture. Consider the statement
(blue x) | (not (blue x)), “either x is blue or x
is not blue”. It does not matter how many things are blue, or which
things are blue. It doesn’t even matter if any things at all are
blue. If we make a picture with one area for blue things and the rest
for things that are not blue, every part of the picture will be in one
of these two parts, either inside the “blue” area or not inside it.
This is an application of a tautology. Tautologies are true regardless of the truth of their parts. Statements of this sort occur constantly in normal mathematical reasoning, sometimes explicitly and even more often implicitly behind the scenes.
If a statement is a tautology, this can be verified just by building
its truth table. If all of the entries are
true, it is a
tautology. The statement
(blue x) | (not (blue x)) is
indeed a tautology, and its truth table has the value
true everywhere. Although the expression is complex
this table has only two entries because it has only one variable,
which is either true or false.
The inputs to some of the truth tables are labeled with expressions
(E x), or
(blue x). It doesn’t matter whether an
input is given by a variable or some expression. All that matters is
that different expressions are handled as different inputs. If an
expression (such as
(blue x)) appears more than once in the full
expression (such as
(blue x) | (not (blue x)), all of its
occurrences will have the same value when given the same value for
Tautologies properly are expressions with just variables and logical functions in them. More complex instances of a tautology can be constructed from it by substitution.