This page is about fundamental building blocks of classical logic -- true, false, and functions that have these values as inputs and outputs. We will focus on the functions and, or, not, and implication.
Though the system described here is modern in style, it supports the kinds of reasoning used in mathematics ever since the ancient Greek mathematicians and philosophers. In the last 100 years or so non-classical varieties of logic have been created, but classical logic is by far the best known and widely used kind in textbooks and by working mathematicians. This particular logic is also functional, having functions as a fundamental concept.
This page uses pictures of mathematical worlds or universes that have things in them. The things can have properties. A property is something like being red, being new, or being a member of some group. Numbers can have properties such as being even, odd, positive, or prime. In classical logic, a thing either has a particular property or it does not, and there is no middle ground.
Our logic expresses precisely concepts such as having at least one of two properties, having both of two properties, or not having a property at all. It also lets us express statements that are true about everything in a mathematical world and to conclude that if one statement is true, some different statement must also be true.
The logic concepts described here are enough to make precise virtually all of the reasoning needed by students of high school algebra and trigonometry (though calculus needs a bit more). Adding suitable rules of inference and axioms for logic and numbers gives a precise system that can be used to solve a great many math problems at this level.
This is also the kind of logic used in the Prooftoys automated proof assistant, and the use of truth tables here is in the same spirit as the reasoning about boolean functions and tautologies in Prooftoys.
The basic logical concepts of and, or, not, and implies can all be expressed as functions from boolean values to boolean values, and truth tables capture their essence as functions.
Implication in particular is more familiar in statements that also include predicates, such as "all multiples of 10 are multiples of 5", or "if it rains the street will be wet". Pictures may help demonstrate how all of this works.
In classical mathematical logic, a statement is considered true if it is true in all possible cases. Imagine assigning all possible combinations of values to the variables in the statement and checking the truth of the statement in each of these cases. The statement is considered true if it is true in every case.
Tautologies are true statements involving only boolean values and boolean functions. Substitution is a fundamental idea in math, and substitution instances of tautologies are basic building blocks of mathematical reasoning.
If you are satisfied with this summary and don't like looking at pictures about abstract mathematics you might prefer to skip reading the rest of the page.
In the pictures a mathematical world is shown as a circle. The world has various things in it, each of those things having a particular spot in the picture.
Mathematical writing, instead of saying a point of a picture is blue,
or has the property of being blue, often says it is a member of the
set of points that are blue. In mathematics, properties are also
often referred to as predicates. These are all just different
ways of describing the same situation. (Note: a predicate can also
express a relationship between two or more things, as in
x < y. In this case <
is a predicate.)
Sets of things with some common property are shown as a circle, part of a circle, or other region of this world, shaded with a particular color or pattern. Each set is labeled with a name. Each contains the things inside its shaded circle or part circle, but nothing ouside of that. In the diagrams below, areas where some statement is true are generally colored. Areas where a statement is not true are usually white or gray.
In our version of mathematical notation we are going to write
(green x) to mean that x is green,
(blue x) to mean that x is blue, and so on.
Some of the pictures are near tables that define key functions. Moving the mouse over one of these pictures or touching it on a touch screen will cause the relevant table entries to highlight themselves.
In mathematics a function named
f is often defined
with a statement like this:
In our notation we write:
f(x) = x + 1
or omit the parentheses around the function call, like this:
(f x) = x + 1
f x = x + 1
and so on. A function produces a result value given an input value or values. The addition function (
f 0 = 1
f 1 = 2
f 2 = 3
A function can have the same result regardless of the input, for
example the function defined by
(f x) = 1. A function of
this sort is a constant function because its result does not
vary with different inputs. But no function can give different
results given the same inputs twice.
In our logic there are values
false, known as truth values. These are often
referred to as boolean values in honor of
a pioneer in the development of these ideas.
When we write something like
(blue x), or (yellow x), the words
green, blue, and yellow
represent functions that produce a value of true
or false. The function blue for example
produces a value of true or false depending
on whether its input is blue or not.
In other words, predicates are functions that produce values that
true or false.
Our introduction to basic logic focuses on mathematical functions that have truth values as their inputs and a truth value as their result. These can be referred to as truth functions or logical functions.
The simplest of these functions is called
not, also known
as negation. Negation provides a way to talk about things that do not
have a certain property, ones that are not in a certain set, or where
the value of a predicate is false. In our logic, these
are all just different ways of expressing the same idea.
The next group of pictures illustrate negation. The parts of the pictures in the first group that were green, or blue, or yellow are white in this group. The areas that were white in the first group of pictures are marked here with stripes, indicating that in the original picture they had the property of being not green, not blue, or not yellow.
So every point that was colored (true) in the first set of pictures is
white (false) here and each point that was white (false) in the first
set is shaded (true) here. we can treat
not as a
function that takes true or false as its
input and produces a value of true or false.
This behavior can be defined with a table. You can look up the value
of not x by going to the row labeled with the value of
x, either true or false.
To use the table, look up the row labeled with the value of the input
"X". The value of the function is in that row under "not X". So
(not false) = true and (not true) = false.
Moving the mouse over one of these pictures or touching it on a touch
screen will cause the truth table entries to highlight.
This kind of table that shows the truth value produced by true or false inputs to a function is called a truth table. The entries where the value is true are shaded with blue lines to highlight the difference between true and false. We will use this color scheme in other truth tables as well.
In our notation we write the property of not being blue as
not (blue x) or (not (blue x)).
Of course we can also read this as saying that the predicate blue is
not true for x, or that x is not in the set of things that are blue.
In mathematics a statement like (not (A x)) is
commonly called the negation of a statement
(A x). The negated statement is true of
all the things where theoriginal statement (A x) is false.
Other notations for negation include "
" ˜" (tilde).
As an example of our next function, suppose you are thinking what to
have for lunch, and decide it must either be delicious or easy. In
the first picture let circle D represent things that are delicious and
circle E represent things that are easy. The combined area then
represents things that are delicious or easy. We can write that a
thing x is "delicious or easy" as
(D x) | (E x).
Everything in the parts of the picture that are shaded have this
The shaded part of the second picture also represents things that are delicious or easy, this time using the same shading for all of them instead of separate shadings for D and E.
All areas of the first picture that are shaded yellow or green are
shaded blue in the second picture. Once again we can use a function
to model this relationship. This function has two inputs. Each input
value is boolean (true or false) and so is the result. Again,
hover the mouse over either of the pictures to highlight the
appropriate parts of the truth table for the function named
or ( |).
This truth table is organized with a row for each value of the first
input and a column for each value of the second input. The value of
the function is in the row for the value of the first input and the
column for the value of the second input. So for example
(false | true) = true.
A common notation for disjunction is "
∨", for example
p ∨ q.
Suppose you are feeling more picky about your lunch, and decide it
must be both delicious and easy. Only things in both of the circles
fit this description -- the small shaded area in the next picture. In
Prooftoys we write
((D x) & (E x)).
Once again, at each point "x" in the picture,
((D x) & (E x)) is true exactly when (D x)
is true and (E x) is also true. We can define a
function with this truth table:
What if there is nothing that is both easy and delicious? A picture for that situation could like this:
The picture has no shaded area because region D and region E do not
overlap; there is no part of the picture where
(D x) and
(E x) are both true. If that really is your
requirement, in this scenario there is no possible lunch for you!
A common notation for conjunction is "
∧", for example
p ∧ q.
A simple yet important property of truth values is equality. In this case we will give the truth table immediately:
It shows that
true is equal to true, false
is equal to false, and neither one is equal to the other,
all as you would expect. For boolean values it is sometimes written
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