EF Tautologies and contradictions

🔗

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 \to p .$
🔗
$p \leftrightarrow p .$
🔗
Law of the Excluded Middle: $p \lor \neg p .$

🔗
Verification:

$p$ $\neg p$ $p \lor \neg p$

$T$ $F$ $T$

$F$ $T$ $T$

🔗
The table verifies that the statement is a tautology as the last column consists only of $T$ values.
🔗
Law of Contradiction: $\neg (p \land \neg p) .$

🔗
Verification:

$p$ $\neg p$ $p \land \neg p$ $\neg (p \land \neg p)$

$T$ $F$ $F$ $T$

$F$ $T$ $F$ $T$

🔗
The table verifies that the statement is a tautology as the last column consists only of $T$ values.

🔗

Example 1.4.2. Not a tautology.

🔗

p \lor 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 \lor \neg p) \to (q \land \neg q)$ is a contradiction:

$p$ $q$ $\neg p$ $\neg q$ $p \lor \neg p$ $q \land \neg q$ $(p \lor \neg p) \to (q \land \neg q)$

$T$ $T$ $F$ $F$ $T$ $F$ $F$

$T$ $F$ $F$ $T$ $T$ $F$ $F$

$F$ $T$ $T$ $F$ $T$ $F$ $F$

$F$ $F$ $T$ $T$ $T$ $F$ $F$

🔗
The table verifies that the statement is a contradiction as the last column consists only of $F$ values.

🔗

Example 1.4.4. Conditional versus contradiction.

🔗

Implication

A \to 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}, \dots, p_{m} .

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},

for every possible collection of logical statements

B_{1}, B_{2}, \dots, B_{m} .

🔗

Example 1.4.6. Using the Substitution Rule.

🔗

🔗
We know $p \lor \neg p$ is a tautology, therefore so is
$(q \to (r \land \neg s)) \lor \neg (q \to (r \land \neg s))$
using substitution $p = (q \to (r \land \neg s)) .$
🔗
We know $(p \lor \neg p) \to (q \land \neg q)$ is a contradiction, therefore so are
$\begin{matrix} (p \lor \neg p) \to (p \land \neg p) (by p = p, q = p), \\ ((r \lor s) \lor \neg (r \lor s)) \to (q \land \neg q) (by p = r \lor s, q = q), \\ (r \land (s \leftrightarrow t)) \lor \neg (r \land (s \leftrightarrow t)) \to (t \land \neg t) (by p = r \land (s \leftrightarrow t), q = t). \end{matrix}$

🔗

In mathematics, we often wish to prove that a condition

A \to B

is actually a tautology. (See Chapter 6.)

🔗

logically implies: 🔗
if the conditional $A \to B$ is a tautology, we say that $A$ logically implies $B$
$A \Rightarrow B$: 🔗
notation for logical implication

🔗

Example 1.4.7. Logical implication.

🔗

🔗
If $A = p$ and $B = p \lor q,$ then $A \Rightarrow B .$
🔗
If $A = p \land q$ and $B = p,$ then $A \Rightarrow B .$

🔗

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 \Rightarrow B,

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 \to B

where

A

is false help out — as the conditional

A \to B

is automatically true when

A

is false, regardless of the truth value of

B,

we really only need to consider what happens when

A

is true to verify

A \Rightarrow B .

Elementary Foundations: An introduction to topics in discrete mathematics

Search Results: