Basic Logic through Pictures

Contents

Introduction

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.

Summary for the impatient

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.

About the pictures

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.

Functions and truth values

Functions

In mathematics a function named f is often defined with a statement like this:

f(x) = x + 1
In our notation we write:
(f x) = x + 1
or omit the parentheses around the function call, like this:
f x = x + 1
So:
f 0 = 1
f 1 = 2
f 2 = 3
and so on. A function produces a result value given an input value or values. The addition function (+) for example takes two numbers as input and gives a number as its result, as in 3 + 5 = 8. The function f above takes a number as input and produces a number as its result. The value of a function can depend only on its inputs, nothing else. And given the same inputs on different occasions any mathematical function must have the same result each time.

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.

True and false as values

In our logic there are values true and false, known as truth values. These are often referred to as boolean values in honor of George Boole, a pioneer in the development of these ideas.

When we write something like (green x), (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 are 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.

Untrue: "not"

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.

x true
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 "¬" and "˜" (tilde).

At least one true: "or" (|)

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 property.

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 (|).

(E x)
true false
(D x) true
false

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.

Both true: "and" (&)

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:

(E x)
true false
(D x) true
false

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.

Equality: (=, ==)

A simple yet important property of truth values is equality. In this case we will give the truth table immediately:

true false
true
false

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 as .

Statements that are always true

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".

Statements with "or"

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 true.

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:

The statement 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.

Statements with "and"

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 true statements.

Statements like "all A are B"

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.

Implication: "implies" ()

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 implies (alternatively ), 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:

wings
true false
bird true
false

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.

About vacuous statements

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, that is no birds that are larger than elephants and 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.

Combining logical functions

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.

(E x)
true false
(D x) true
false

The expression (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 and. Logical 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.

(E x)
true false
(D x) true
false

Tautologies

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.

(blue x) true
false

The inputs to some of the truth tables are labeled with expressions such as (D x), (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 x. It is not possible for one occurrence to have the value true and another one the value false. They count as one input.

Tautologies properly are expressions with just variables and logical functions in them. This is the simplest way to write down the principle of a tautology, and more complex instances of tautologies can be built from them by substitution.

Just a few examples of commonly-encountered tautologies are:

  • a => a
  • (a & a) == a
  • (a => b) == ((not b) => (not a))
  • (not (a | b)) == ((not a) & (not b))

Assigning all combinations of true and false to the variables in these expressions and checking that the value of the expression is true will verify that these all really are tautologies.

Substitution

Substitution for variables is one of the fundamental operations in virtually all forms of mathematical proofs and mathematical problem solving.

If a mathematical statement has a variable in it, we say the statement is true if it is true for all possible values of the variable; otherwise we say it is not true. If the variable is a boolean variable, we say the statement is true if it is true regardless of whether the variable is true or false.

So if a variable appears more than once in a true statement, we know the statement will be true as long as each occurrence is assigned the same value. Since an expression with the same inputs always gives the same result, substituting an expression for every occurrence of a variable in a true statement gives another true statement.

In a true statement, if we systematically replace every occurrence of a variable with an expression (the same expression everywhere), the result of this substitution is another true statement, because the expression has the same value everywhere it appears.

The simple tautology a ⇒ a is a true statement, since true ⇒ true and false ⇒ false. A statement like (shining sun) ⇒ (shining sun) is also true whether the sun is actually shining or not. The substituted expression itself can have variables, as in x < y ⇒ x < y. No matter what values x and y have, the value of x < y is going to be the same in both spots, so the whole statement is still true.

The result of substituting an expression for all instances of a variable in a statement is called an instance of the original statement, so we say that substituting one or more expressions for variables in a tautology gives an instance of the tautology.

Note: If a mathematical statement has parts that use "quantifiers" ("for all", "there exists", etc.), substitution has to be done a bit more carefully, but the idea remains the same.