Skip to main content

Section 1.3 Tautologies, Contradictions, & Quantifiers

By definition, a simple statement is either true or false. In mathematics/logic, statements which are always true or always false are of great value, but the greatest benefit occurs when dealing with compound statements fitting this description. We give the formal definitions below.

Definition 1.3.1.

A compound statement which is always true is called a tautology, while a compound statement which is always false is called a contradiction.

The statement \(p \leftrightarrow \negate p\) is a contradiction since its truth table indicates this statement is always false (Table 1.3.3). That is, a statement and its negation can never have the same truth value.

\(p\) \(\negate p\) \(p \leftrightarrow \negate p\)
T F F
F T F
Table 1.3.3. Truth table for \(p \leftrightarrow \negate p\)

The statement \(p \leftrightarrow \negate(\negate p)\) is a tautology since its truth table indicates this statement is always true (Table 1.3.5). Thus, the double negation of a statement is equivalent to the original statement.

\(p\) \(\negate p\) \(\negate( \negate p)\) \(p \leftrightarrow \negate(\negate p)\)
T F T T
F T F T
Table 1.3.5. Truth table for \(p \leftrightarrow \negate(\negate p)\)

The following theorem enumerates a list of tautologies which will be useful to us. The proofs will be left as exercises.

Subsection 1.3.1 Historical Note

Augustus De Morgan (27 June 1806–18 March 1871) was a British mathematician and logician. Use internet and/or library resources to research his major contributions to the fields of mathematics and logic, specifically De Morgan's Laws.

The following theorem lists some useful contradictions, and again, the proof requires construction of the appropriate truth tables and is left to the exercises.

You should be aware that the list of possible tautologies and contradictions we could have chosen is virtually endless. We have simply chosen those which will be of most benefit to us later.

As a final example we will provide the following example of a truth table involving three statements.

The following truth table (Table 1.3.9) can be used to verify the statement

\begin{equation*} [( p \rightarrow q ) \vee r] \leftrightarrow [(p \; \wedge \negate q) \rightarrow r]. \end{equation*}

Since the columns for \(( p \rightarrow q ) \vee r\) and \((p \; \wedge \negate q) \rightarrow r\) match, we have a tautology.

\(p\) \(q\) \(r\) \(p \rightarrow q\) \(( p \rightarrow q ) \vee r\) \(\negate q\) \(p \; \wedge \negate q\) \((p \; \wedge \negate q) \rightarrow r\)
T T T T T F F T
T T F T T F F T
T F T F T T T T
T F F F F T T F
F T T T T F F T
F T F T T F F T
F F T T T T F T
F F F T T T F T
Table 1.3.9. Truth table for \([( p \rightarrow q ) \vee r] \leftrightarrow [(p \; \wedge \negate q) \rightarrow r]\)

Exercises 1.3.2 Exercises

3.

Using the appropriate tautologies from Theorem 1.3.6, negate the following statements.

  1. A foot has 12 inches and a yard has three feet.
  2. Either I will get a job or I will not be able to pay my bills.
  3. If you study logic one hour per day, then you will make an A in the course.
  4. If \(x^2 - 5x + 6 = 0\text{,}\) then \(x - 3 = 0\) or \(x - 2 = 0\text{.}\)
  5. An integer \(m\) is odd if and only if \(m^2\) is odd.
  6. If \(m\) is an even integer, then \(m + 1\) is odd and \(m^2\) is even.
  7. I will call home if I win the game.
5.

Justify why each of the following are true by way of a truth table and a brief paragraph explaining what the statement means.

  1. \(\displaystyle [\negate p \wedge (p \vee q)] \rightarrow q\)
  2. \(\displaystyle [(p \rightarrow q) \wedge \negate q] \rightarrow \negate p\)
  3. \(\displaystyle [\negate p \rightarrow (q \wedge \negate q)] \rightarrow p\)