Logic Lecture 2: Implications, Biconditionals, Tautologies and Contradictions
Implications
Definition: For two statements P and Q, the implication P ⇒ Q is written as "If P then Q" (a conditional).
P is the hypothesis; Q is the conclusion.
Truth table (P, Q) → P ⇒ Q:
(T, T) → T
(T, F) → F
(F, T) → T
(F, F) → T
Important observation (IO):
(1) If P is false, then P ⇒ Q is true regardless of Q.
(2) If Q is true, then P ⇒ Q is true regardless of P.
Examples of IO:
If $2+3=5$ then $4+6=10$ (true ⇒ true → True)
If $4+6=10$ then $5+7=14$ (true ⇒ true → True)
If $5+3=7$ then $4+6=10$ (true ⇒ true → True)
If $5+7=13$ then $4+6=11$ (true ⇒ false would be False, but note: $5+7=13$ is actually false, so antecedent is false; by IO the implication is true.)
Answers: T, T, T, T in the last case due to the false antecedent.
Implications can be applied to open sentences as well.
Example: If $x-2=0$ then $x^2 - x - 2 = 0$.
For $x=2$, both open sentences are true, so the implication is true.
For $x
eq 2$, the open sentence $x-2=0$ is false. By IO, the implication is true regardless of $x^2 - x - 2 = 0$.Conclusion: the implication "If $x-2=0$ then $x^2 - x - 2 = 0$" is true for every real number $x$.
Different ways to state the implication P ⇒ Q in words:
If P then Q
Q if P
P implies Q
P is sufficient for Q
Q is necessary for P
Note: the fourth row can look surprising (depending on which value you think is the antecedent).
Example with open sentences: P = (x = 5), Q = (x^2 = 25).
P ⇒ Q: If $x=5$ then $x^2=25$.
Q if P: If $x=5$ then $x^2=25$ (same as above).
$x^2=25$ is true whenever $x = \pm5$, but statement P is only true when $x=5$.
$x=5$ implies $x^2=25$; $x=5$ only if $x^2=25$; $x=5$ is sufficient for $x^2=25$; $x^2=25$ is necessary for $x=5$.
Converse of an implication
Definition 2: For statements/open sentences P and Q, the implication Q ⇒ P is called the converse of P ⇒ Q.
IO: Not always Q ⇒ P and P ⇒ Q have the same truth value.
Example (open statements): P(x): (x − 1)(x − 2) = 0, Q(x): (x − 2)(x − 3) = 0.
Observations:
P(1) ⇒ Q(1) is false;
Q(1) ⇒ P(1) is true;
P(3) ⇒ Q(3) is true;
Q(3) ⇒ P(3) is false;
P(2) ⇒ Q(2) is true;
Q(2) ⇒ P(2) is true as well.
Takeaway: The truth value of a converse can differ from the original implication.
Contrapositive of an implication
Definition 3: For statements/open sentences P and Q, the implication ∼Q ⇒ ∼P is the contrapositive of P ⇒ Q.
Theorem 1: For every two statements P and Q,
Proof: See the truth tables (the contrapositive has the same truth value as the original implication).
Intuition: Replacing the conclusion with its negation and the hypothesis with its negation preserves truth value of the implication.
Equivalences and logical forms
Theorem 2: For every two statements P and Q,
Theorem 3: For every two statements P and Q,
Both theorems can be shown via truth tables; also can be derived using De Morgan's laws.
Biconditionals, if and only if
Definition 4: For two statements P and Q, the biconditional is the conjunction of the implications:
Notation: , in words: "P if and only if Q".
Truth table notes:
P and Q have the same truth value ⇔ the biconditional is true.
If P and Q differ, the biconditional is false.
Example: P = (P ⇒ Q) and Q ⇒ P truth values align to yield the biconditional truth value.
Biconditionals: examples and intuition
Example 1: P(n) : $n^2-4=0$, Q(n) : $2n+1=0$ with $n$ an integer.
P(n) true only if $n=2$ or $n=-2$.
Q(2) and Q(-2) are both false, so P(2) ⇐⇒ Q(2) and P(-2) ⇐⇒ Q(-2) are false.
For any integer $n$ with $n \neq \pm 2$, both P(n) and Q(n) are false; thus P(n) ⇐⇒ Q(n) is true for such $n$ (false ⇔ false).
Example 2: A triangle is equilateral ⇐⇒ it is equiangular.
Exercise: Construct a biconditional for a rectangle. For a square?
Tautologies and contradictions
Definition (Tautology): A compound statement is a tautology if it is true for all possible truth values of its components.
Definition (Contradiction): A compound statement is a contradiction if it is false for all possible truth values of its components.
Corollary: A compound statement is a tautology if and only if its negation is a contradiction.
Simple examples:
P ∨ ¬P is a tautology (law of excluded middle).
P ∧ ¬P is a contradiction (law of non-contradiction).
Examples to prove:
Prove that is a tautology.
Prove that is a tautology.
// End of notes