Chapter 1: Formal Logic
Section 1.1 Statements, Sybmolic Representation and Tautologies
Tautology
A tautology in formal logic is a statement or proposition that is always true, regardless of the truth values of its constituent parts. Tautologies are important in logic because they are considered logically valid; they hold true under any possible interpretation.Importance in Logic
Proofs: Tautologies are often used in logical proofs because they are universally true.
Logical Equivalence: They help in determining if two propositions are logically equivalent.
Redundancy: In some cases, tautologies can be used to identify redundancy in logical statements.
Tautology
A tautology is a statement that is always true. Once a tautology has been proven, we can use that tautology anywhere. A tautology is "intrinsically true" by its very structure; it is true no matter what truth values are assigned to its statement letters.A simple example of a tautoloy is \(A ∨ A' \) ; consider, for example, the statement:
"Today the sun will shine or today will not shine." which must always be true because one or the other of these must happen.
| A | A' | A ∨ A' |
|---|---|---|
| T | F | T |
| F | T | T |
Suppose that \(P\) and \(Q\) represent two wffs, and it happends that the wff \(P ↔ Q\) is a tautology. If we did a truth table using the statement letters in \(P\) and \(Q\), then the truth values of the wffs \( P\) and \(Q\) would agree for every row of the truth table. In this case, \(P\) and \(Q\) are said to be equivalent wffs , denoted by \(P ⇔ Q \). Thus \(P ⇔ Q\) states a fact, namely, that the particular wff \(P ↔ Q\) is a tautology.
Contradiction
A wff whose truth values are always false, is called contradiction. A contradiction is "intrinsically false" by its very structure.A simple example of a contradiction is \( A ∧ A'\); consider
"Today is Tuesday and today is not Tuesday." which is false no matter what day of the week it is."
| A | A' | A ∧ A' |
|---|---|---|
| T | F | F |
| F | T | F |
Contingency
A contingency is a statement that is neither always true nor always false. A contingency can be true in some cases and false in others, depending on the values of its variables.A simple example of a contingency is \( A ∨ B \) ; consider, for example, the statement:
"Today is sunny or it is raining." which could be either true or false depending on the actual weather conditions.
| A | B | A ∨ B |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
Tautological Equivalences
We will list some basic equivalences. We represent any contradiction by 0 and any tautology by 1.| Some Tautological Equivalences | ||
|---|---|---|
| 1a. A ∨ B ⇔ B ∨ A | 1b. A ∧ B ⇔ B ∧ A | Commutative Properties |
| 2a. (A ∨ B) ∨ C ⇔ A ∨ (B ∨ C) | 2b. (A ∧ B) ∧ C ⇔ A ∧ (B ∧ C) | Associative Properties |
| 3a. A ∨ (B ∧ C) ⇔ (A ∨ B) ∧ (A ∨ C) | 3b. A ∧ (B ∨ C) ⇔ (A ∧ B) ∨ (A ∧ C) | Distributive Properties |
| 4a. A ∨ 0 ⇔ A | 4b. A ∧ 1 ⇔ A | identity Properties |
| 5a. A ∨ A' ⇔ 1 | 5b. A ∧ A' ⇔ 0 | complement Properties |
Note that 2a allows us to write \(A ∨ B ∨ C\) with no need for parentheses because the grouping doesn't matter; similarly, 2b allows us to write \( A ∧ B ∧ C\).
Example
The turth Table 1 verifies equivalence 1a, the commutative property for disjunction, and that Table 2 verifies 4b, the identity property for conjunction. Note that only two rows are needed for Table 2 because 1 (a tautology) cannot take on false values.| Table 1 verifies \(A ∨ B ⇔ B ∨ A\) | ||||
|---|---|---|---|---|
| A | B | A ∨ B | B ∨ A | A ∨ B ↔ B ∨ A |
| T | T | T | T | T |
| T | F | T | T | T |
| F | T | T | T | T |
| F | F | F | F | T |
| Table 2 verifies \(A ∧ 1 ⇔ A\) | |||
|---|---|---|---|
| A | 1 | A ∧ 1 | A ∧ 1 ↔ A |
| T | T | T | T |
| F | T | F | T |
Practice
Please verify equivalence 1b, 2a, 3a.De Morgan's laws
Two additional equivalences are very useful are De Morgan's laws, named for the nineteenth-century British mathematician Augustus De Morgan, who first stated them. This theorem is easy to prove.and
| Verify \( (A ∨ B)' ⇔ A' ∧ B' \) | |||||||
|---|---|---|---|---|---|---|---|
| A | B | A ∨ B | (A ∨ B)' | A' | B' | A' ∧ B' | (A ∨ B)' ↔ A' ∧ B' |
| T | T | T | F | F | F | F | T |
| T | F | T | F | F | T | F | T |
| F | T | T | F | T | F | F | T |
| F | F | F | T | T | T | T | T |
\( P ↔ Q \) vs. \( P ⇔ Q \)
| Symbol | Name | Meaning | Type | Truth Table Behavior |
|---|---|---|---|---|
| \( P ↔ Q \) | Biconditional | “P if and only if Q” — true when P and Q have the same truth value in a specific row | Wff (logical expression) | May be true or false, depending on the truth values of P and Q |
| \( P ⇔ Q \) | Logical Equivalence | “P is logically equivalent to Q” — means \( P ↔ Q \) is a tautology Note: A meta-logical statement is a statement about logical expressions rather than a logical expression itself. For example, “P ⇔ Q” is a claim that the wff “P ↔ Q” is a tautology. It expresses something about the truth behavior of P and Q across all cases, rather than being part of the truth table itself. |
Meta-logical statement (not a wff) | Always true; asserts P and Q agree in every row of the truth table |