Section 1.4 Tautologies and contradictions

tautology: a logical statement that is always true for all possible truth values of its variable substatements
logically true statement: synonym for tautology

Example 1.4.1. Basic tautologies.

\(p \lgccond p \text{.}\)
\(p \lgcbicond p \text{.}\)
Law of the Excluded Middle: \(p \lgcor \lgcnot p \text{.}\)

Verification:

\(p \) \(\lgcnot p \) \(p \lgcor \lgcnot p \)

\(\lgctrue \) \(\lgcfalse \) \(\lgctrue \)

\(\lgcfalse \) \(\lgctrue \) \(\lgctrue \)

The table verifies that the statement is a tautology as the last column consists only of \(\lgctrue \) values.

Law of Contradiction: \(\lgcnot \bbrac{p \lgcand \lgcnot p} \text{.}\)

Verification:

\(p \)	\(\lgcnot p \)	\(p \lgcand \lgcnot p \)	\(\lgcnot \bbrac{p \lgcand \lgcnot p} \)
\(\lgctrue \)	\(\lgcfalse \)	\(\lgcfalse \)	\(\lgctrue \)
\(\lgcfalse \)	\(\lgctrue \)	\(\lgcfalse \)	\(\lgctrue \)

The table verifies that the statement is a tautology as the last column consists only of \(\lgctrue \) values.

Example 1.4.2. Not a tautology.

Is \(p \lgcor p \) a tautology? No, since it is false when \(p \) is false.

contradiction: a statement that must always be false, regardless of the truth values of its variable substatements
logically false statement: synonym for contradiction

Example 1.4.3. Contradictions.

Negation of a tautology is always a contradiction (and negation of a contradiction is always a tautology).

Statement \((p \lgcor \lgcnot p) \lgccond (q \lgcand \lgcnot q) \) is a contradiction:

\(p \)	\(q \)	\(\lgcnot p \)	\(\lgcnot q \)	\(p \lgcor \lgcnot p \)	\(q \lgcand \lgcnot q \)	\((p \lgcor \lgcnot p) \lgccond (q \lgcand \lgcnot q) \)
\(\lgctrue \)	\(\lgctrue \)	\(\lgcfalse \)	\(\lgcfalse \)	\(\lgctrue \)	\(\lgcfalse \)	\(\lgcfalse \)
\(\lgctrue \)	\(\lgcfalse \)	\(\lgcfalse \)	\(\lgctrue \)	\(\lgctrue \)	\(\lgcfalse \)	\(\lgcfalse \)
\(\lgcfalse \)	\(\lgctrue \)	\(\lgctrue \)	\(\lgcfalse \)	\(\lgctrue \)	\(\lgcfalse \)	\(\lgcfalse \)
\(\lgcfalse \)	\(\lgcfalse \)	\(\lgctrue \)	\(\lgctrue \)	\(\lgctrue \)	\(\lgcfalse \)	\(\lgcfalse \)

The table verifies that the statement is a contradiction as the last column consists only of \(\lgcfalse \) values.

Example 1.4.4. Conditional versus contradiction.

Implication \(A\lgccond B \) can only be a contradiction if \(A \) is a tautology and \(B \) is a contradiction.

Theorem 1.4.5. Substitution Rule.

Suppose \(A \) is a logical statement involving substatement variables \(p_1, p_2, \dotsc, p_m \text{.}\) If \(A \) is logically true or logically false, then so is every statement obtained from \(A \) by replacing each statement variable \(p_i \) by some logical statement \(B_i \text{,}\) for every possible collection of logical statements \(B_1, B_2, \dotsc, B_m \text{.}\)

Example 1.4.6. Using the Substitution Rule.

We know \(p \lgcor \lgcnot p \) is a tautology, therefore so is
\begin{equation*} \bbrac{q \lgccond (r \lgcand \lgcnot s)} \lgcor \lgcnot \bbrac{q \lgccond (r \lgcand \lgcnot s)} \end{equation*}
using substitution \(p = \bbrac{q \lgccond (r \lgcand \lgcnot s)} \text{.}\)
We know \((p \lgcor \lgcnot p) \lgccond (q \lgcand \lgcnot q) \) is a contradiction, therefore so are
\begin{gather*} (p \lgcor \lgcnot p) \lgccond (p \lgcand \lgcnot p) \qquad \text{(by } p = p \text{, } q = p \text{),}\\ \bbrac{(r \lgcor s) \lgcor \lgcnot (r \lgcor s)} \lgccond \bbrac{q \lgcand \lgcnot q} \qquad \text{(by } p = r \lgcor s \text{, } q = q \text{),}\\ \bbrac{r \lgcand (s \lgcbicond t)} \lgcor \lgcnot \bbrac{r \lgcand (s \lgcbicond t)} \lgccond \Bbrac{t \lgcand \lgcnot t} \qquad \text{(by } p = r \lgcand (s \lgcbicond t) \text{, } q = t \text{).} \end{gather*}

In mathematics, we often wish to prove that a condition \(A \lgccond B \) is actually a tautology. (See Chapter 6.)

logically implies: if the conditional \(A \lgccond B \) is a tautology, we say that \(A \) logically implies \(B \)
\(A \lgcimplies B \): notation for logical implication

Example 1.4.7. Logical implication.

If \(A = p \) and \(B = p \lgcor q \text{,}\) then \(A \lgcimplies B \text{.}\)
If \(A = p \lgcand q \) and \(B = p \text{,}\) then \(A \lgcimplies B \text{.}\)

Remark 1.4.8.

As we will see in Chapter 6, verifying logical implications in mathematical contexts is one of the main tasks of mathematical proof. And to verify a logical implication \(A \lgcimplies B \text{,}\) we want to focus on the idea of conditional as expressing “If \(A \) is true then \(B \) is true,” and we really don’t want to concern ourselves with what happens in the case that \(A \) is false. Here is where our “default” values in the rows of the truth table for the conditional \(A \lgccond B \) where \(A \) is false help out — as the conditional \(A \lgccond B \) is automatically true when \(A \) is false, regardless of the truth value of \(B \text{,}\) we really only need to consider what happens when \(A \) is true to verify \(A \lgcimplies B \text{.}\)

Prev Top Next