Mathematicians normally use a * two-valued
logic*: Every statement is either * True* or
* False*. This is called the *
Law of the Excluded Middle*.

A statement in sentential logic is built from simple statements using the logical connectives , , , , and . The truth or falsity of a statement built with these connective depends on the truth or falsity of its components.

For example, the compound statement is built using the logical connectives , , and . The truth or falsity of depends on the truth or falsity of P, Q, and R.

A * truth table* shows how the truth or falsity
of a compound statement depends on the truth or falsity of the simple
statements from which it's constructed. So we'll start by looking at
truth tables for the five logical connectives.

Here's the table for negation:

This table is easy to understand. If P is *true*, its negation
is *false*. If P is *false*, then is *true*.

should be *true* when both P and Q are
*true*, and *false* otherwise:

is *true* if either P is *true* or Q is
*true* (or both --- remember that we're using "or"
in the inclusive sense). It's only *false* if both P and Q are
*false*.

Here's the table for logical implication:

To understand why this table is the way it is, consider the following example:

"If you get an A, then I'll give you a dollar."

The statement will be *true* if I keep my promise and
*false* if I don't.

Suppose it's *true* that you get an A and it's *true*
that I give you a dollar. Since I kept my promise, the implication is
*true*. This corresponds to the first line in the table.

Suppose it's *true* that you get an A but it's *false*
that I give you a dollar. Since I *didn't* keep my promise,
the implication is *false*. This corresponds to the second
line in the table.

What if it's false that you get an A? Whether or not I give you a dollar, I haven't broken my promise. Thus, the implication can't be false, so (since this is a two-valued logic) it must be true. This explains the last two lines of the table.

means that P and Q are *
equivalent*. So the double implication is *true* if P and
Q are both *true* or if P and Q are both *false*;
otherwise, the double implication is false.

You should remember --- or be able to construct --- the truth tables for the logical connectives. You'll use these tables to construct tables for more complicated sentences. It's easier to demonstrate what to do than to describe it in words, so you'll see the procedure worked out in the examples.

* Remark.* (a) When you're constructing a truth
table, you have to consider all possible assignments of True (T) and
False (F) to the component statements. For example, suppose the
component statements are P, Q, and R. Each of these statements can be
either true or false, so there are possibilities.

When you're listing the possibilities, you should assign truth values
to the component statements in a systematic way to avoid duplication
or omission. The easiest approach is to use *
lexicographic ordering*. Thus, for a compound statement with
three components P, Q, and R, I would list the possibilities this
way:

(b) There are different ways of setting up truth tables. You can, for instance, write the truth values "under" the logical connectives of the compound statement, gradually building up to the column for the "primary" connective.

I'll write things out the long way, by constructing columns for each "piece" of the compound statement and gradually building up to the compound statement. Any style is fine as long as you show enough work to justify your results.

* Example.* Construct a truth table for the
formula .

First, I list all the alternatives for P and Q.

Next, in the third column, I list the values of based on the values of P. I use the truth table for negation: When P is true is false, and when P is false, is true.

In the fourth column, I list the values for . Check for yourself that it is only false ("F") if P is true ("T") and Q is false ("F").

The fifth column gives the values for my compound expression . It is an "and" of (the third column) and (the fourth column). An "and" is true only if both parts of the "and" are true; otherwise, it is false. So I look at the third and fourth columns; if both are true ("T"), I put T in the fifth column, otherwise I put F.

A * tautology* is a formula which is "always
true" --- that is, it is true for every assignment of truth
values to its simple components. You can think of a tautology as a
*rule of logic*.

The opposite of a tautology is a *
contradiction*, a formula which is "always false". In
other words, a contradiction is false for every assignment of truth
values to its simple components.

* Example.* Show that is a tautology.

I construct the truth table for and show that the formula is always true.

The last column contains only T's. Therefore, the formula is a tautology.

* Example.* Construct a truth table for .

You can see that constructing truth tables for statements with lots of connectives or lots of simple statements is pretty tedious and error-prone. While there might be some applications of this (e.g. to digital circuits), at some point the best thing would be to write a program to construct truth tables (and this has surely been done).

The point here is to understand how the truth value of a complex statement depends on the truth values of its simple statements and its logical connectives. In most work, mathematicians don't normally use statements which are very complicated from a logical point of view.

* Example.* (a) Suppose that P is false and is true. Tell whether Q is true, false, or its truth
value can't be determined.

(c) Suppose that is false. Tell whether Q is true, false, or its truth value can't be determined.

(a) Since is true, either P is true or is true. Since P is false, must be true. Hence, Q must be false.

(b) An if-then statement is false when the "if" part is true and the "then" part is false. Since is false, is true. An "and" statement is true only when both parts are true. In particular, must be true, so Q is false.

* Example.* Suppose

" " is true.

" " is false.

"Calvin Butterball has purple socks" is true.

Determine the truth value of the statement

For simplicity, let

P = " ".

Q = " ".

R = "Calvin Butterball has purple socks".

I want to determine the truth value of . Since I was given specific truth values for P, Q, and R, I set up a truth table with a single row using the given values for P, Q, and R:

Therefore, the statement is * true*.

* Example.* Determine the truth value of the
statement

The statement " " is false. You can't tell whether the statement "Ichabod Xerxes eats chocolate cupcakes" is true or false --- but it doesn't matter. If the "if" part of an "if-then" statement is false, then the "if-then" statement is true. (Check the truth table for if you're not sure about this!) So the given statement must be true.

Two statements X and Y are * logically
equivalent* if is a tautology. Another way to say
this is: For each assignment of truth values to the *simple
statements* which make up X and Y, the statements X and Y have
identical truth values.

From a practical point of view, you can replace a statement in a proof by any logically equivalent statement.

To test whether X and Y are logically equivalent, you could set up a truth table to test whether is a tautology --- that is, whether "has all T's in its column". However, it's easier to set up a table containing X and Y and then check whether the columns for X and for Y are the same.

* Example.* Show that and are logically equivalent.

Since the columns for and are identical, the two statements are logically
equivalent. This tautology is called * Conditional
Disjunction*. You can use this equivalence to replace a
conditional by a disjunction.

There are an infinite number of tautologies and logical equivalences; I've listed a few below; a more extensive list is given at the end of this section.

When a tautology has the form of a biconditional, the two statements which make up the biconditional are logically equivalent. Hence, you can replace one side with the other without changing the logical meaning.

You will often need to *negate* a mathematical statement. To
see how to do this, we'll begin by showing how to negate symbolic
statements.

* Example.* Write down the negation of the
following statements, simplifying so that only simple statements are
negated.

(a)

(b)

(a) I negate the given statement, then simplify using logical equivalences. I've given the names of the logical equivalences on the right so you can see which ones I used.

(b)

I showed that and are logically equivalent in an earlier example.

In the following examples, we'll negate statements written in words. This is more typical of what you'll need to do in mathematics. The idea is to convert the word-statement to a symbolic statement, then use logical equivalences as we did in the last example.

* Example.* Use DeMorgan's Law to write the
*negation* of the following statement, simplifying so that
only simple statements are negated:

"Calvin is not home or Bonzo is at the movies."

Let C be the statement "Calvin is home" and let B be the statement "Bonzo is at the moves". The given statement is . I'm supposed to negate the statement, then simplify:

The result is "Calvin is home and Bonzo is not at the movies".

* Example.* Use DeMorgan's Law to write the
*negation* of the following statement, simplifying so that
only simple statements are negated:

"If Phoebe buys a pizza, then Calvin buys popcorn."

Let P be the statement "Phoebe buys a pizza" and let C be
the statement "Calvin buys popcorn". The given statement is
. To simplify the negation, I'll use the * Conditional Disjunction* tautology which says

That is, I can replace with (or vice versa).

Here, then, is the negation and simplification:

The result is "Phoebe buys the pizza and Calvin doesn't buy popcorn".

Next, we'll apply our work on truth tables and negating statements to problems involving constructing the converse, inverse, and contrapositive of an "if-then" statement.

* Example.* Replace the following statement with
its contrapositive:

"If x and y are rational, then is rational."

By the contrapositive equivalence, this statement is the same as "If is not rational, then it is not the case that both x and y are rational".

This answer is correct as it stands, but we can express it in a slightly better way which removes some of the explicit negations. Most people find a positive statement easier to comprehend than a negative statement.

By definition, a real number is * irrational* if
it is not rational. So I could replace the "if" part of the
contrapositive with " is irrational".

The "then" part of the contrapositive is the negation of an "and" statement. You could restate it as "It's not the case that both x is rational and y is rational". (The word "both" ensures that the negation applies to the whole "and" statement, not just to "x is rational".)

By DeMorgan's Law, this is equivalent to: "x is not rational or y is not rational". Alternatively, I could say: "x is irrational or y is irrational".

Putting everything together, I could express the contrapositive as: "If is irrational, then either x is irrational or y is irrational".

(As usual, I added the word "either" to make it clear that the "then" part is the whole "or" statement.)

* Example.* Show that the inverse and the
converse of a conditional are logically equivalent.

Let be the conditional. The inverse is . The converse is .

I could show that the inverse and converse are equivalent by constructing a truth table for . I'll use some known tautologies instead.

Start with :

Remember that I can replace a statement with one that is logically equivalent. For example, in the last step I replaced with Q, because the two statements are equivalent by Double negation.

* Example.* Suppose x is a real number. Consider
the statement

"If , then ."

Construct the converse, the inverse, and the contrapositive. Determine the truth or falsity of the four statements --- the original statement, the converse, the inverse, and the contrapositive --- using your knowledge of algebra.

The converse is "If , then ".

The inverse is "If , then ".

The contrapositive is "If , then ".

The original statement is false: , but . Since the original statement is eqiuivalent to the contrapositive, the contrapositive must be false as well.

The converse is true. The inverse is logically equivalent to the converse, so the inverse is true as well.

\newpage

\centerline{\bigssbold List of Tautologies}

Copyright 2019 by Bruce Ikenaga