Section 2.2 Propositional equivalence
It may have occurred to you in the prior section that there is no difference between the statements “It is raining and I brought my umbrella” and “I brought my umbrella and it is raining”. That is, a conjunction \(p \wedge q\) is the same regardless of which order we put the conjuncts. To formalize this idea, we say the two statements are equivalent. Even though \(p \wedge q\) and \(q \wedge p\) are different statements, they mean the same thing, and hence are “the same” in some sense of the word. (We will further torture the idea of “the same” in Part IV when we discuss equivalence relations in general.)
Subsection 2.2.1 Equivalence
Let's begin with some related definitions.
Definition 2.2.1.
Let \(\varphi\) be a statement. We say \(\varphi\) is a tautology if \(\varphi\) is true regardless of the truth values of its component atomic statements. If \(\varphi\) is always false we call it a contradiction. Finally, if the truth value of \(\varphi\) depends on the truth values of its component statements, we say \(\varphi\) is contingent.
Definition 2.2.2.
The statements \(\varphi\) and \(\psi\) are equivalent if \(\varphi \leftrightarrow \psi\) is a tautology. If so, we write \(\varphi \equiv \psi\text{.}\)
Recall that a biconditional statement is true if the two statements involved are both simultaneously true or simultaneously false. One way to tell if \(\varphi \leftrightarrow \psi\) is always true is to write down a truth table for \(\varphi\) and \(\psi\) with the rows in the same order. If the columns for \(\varphi\) and \(\psi\) are the same, then \(\varphi \equiv \psi\text{.}\)
Example 2.2.3.
Show that \(p \wedge q\) and \(q \wedge p\) are equivalent using a truth table. (This property is called \(\boldsymbol{\wedge}\)-commutativity.)
\(p\) | \(q\) | \(p \wedge q\) | \(q \wedge p\) |
\(T\) | \(T\) | \(T\) | \(T\) |
\(T\) | \(F\) | \(F\) | \(F\) |
\(F\) | \(T\) | \(F\) | \(F\) |
\(F\) | \(F\) | \(F\) | \(F\) |
Since \(p\wedge q\) and \(q \wedge p\) have the same columns with the rows in the same order (notice we just put both statements in the same table!), we can conclude \(p \wedge q \equiv q \wedge p\text{!}\)
If \(\varphi\) is a tautology we write \(\varphi \equiv T\text{.}\) If \(\varphi\) is a contradiction we write \(\varphi \equiv F\text{.}\)
Now, we will list many significant equivalences. We will go into detail on a few of them.
Name | Equivalence |
Double negation | \(\neg(\neg p) \equiv p\) |
\(\wedge\)-commutativity | \(p \wedge q \equiv q \wedge p\) |
\(\vee\)-commutativity | \(p \vee q \equiv q \vee p\) |
\(\wedge\)-associativity | \((p \wedge q) \wedge r \equiv p \wedge (q \wedge r) \equiv p \wedge q \wedge r\) |
\(\vee\)-associativity | \((p \vee q) \vee r \equiv p \vee (q \vee r) \equiv p \vee q \vee r\) |
\(\wedge\)-identity | \(p \wedge T \equiv p\) |
\(\wedge\)-absorption | \(p \wedge F \equiv F\) |
\(\wedge\)-cancellation | \(p \wedge \neg p \equiv F\) |
\(\vee\)-identity | \(p \vee F \equiv p\) |
\(\vee\)-absorption | \(p \vee T \equiv T\) |
\(\vee\)-cancellation | \(p \vee \neg p \equiv T\) |
Properties of conjunction, disjunction, and negation
That's a lot, and we're not even done! But let's stop for a minute to summarize this list.
Two negations cancel. This is what we would expect.
Conjunction and disjunction are commutative, which you may recall from the first chapter means that it does not matter what order the conjuncts or disjuncts are written. Addition and multiplication of integers have this property as well.
Conjunction and disjunction are also associative, meaning that the way the elements are grouped also doesn't matter. So if we only have conjunction or only have disjunction in our expression, we can lose parentheses altogether.
For conjunction, a tautology \(T\) is the identity element, meaning conjoining a statement with \(T\) will return the statement. Think about it: both statements must be true and \(T\) definitely is, so it resolves to whatever the other statement is. A contradiction \(F\) is the absorptive statement, because any false statement makes the whole conjunction false. Finally, since a statement and its negation can't both be true, they cancel out into \(F\text{.}\)
For disjunction, \(F\) is the identity, \(T\) is the absorptive element, and a statement and its negation cancel into \(T\text{.}\)
Be aware that some mathematicians, often called constructivists or intuitionists, reject a principle called the law of the exclused middle, another name for \(p \wedge \neg p \equiv F\text{.}\) These mathematicians must do their work without cancellation or double negation. In this book, we will take the law of the excluded middle to be true.
Let's do an example to prove one of the above equivalences.
Example 2.2.6.
Using a truth table, show that \(p \vee \neg p \equiv T\text{.}\)
\(p\) | \(\neg p\) | \(p \vee \neg p\) |
\(T\) | \(F\) | \(T\) |
\(F\) | \(T\) | \(T\) |
Since in every row \(p \vee \neg p\) is true, it is a tautology, so we write \(p \vee \neg p \equiv T\text{.}\)
Next, let's check out how negation, conjunction, and disjunction interact with one another.
Name | Equivalence |
DeMorgan's law \(\wedge\) | \(\neg (p \wedge q) \equiv \neg p \vee \neg q\) |
DeMorgan's law \(\vee\) | \(\neg (p \vee q) \equiv \neg p \wedge \neg q\) |
\(\wedge\) over \(\vee\) | \(p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r)\) |
\(\vee\) over \(\wedge\) | \(p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r)\) |
Distributive properties
The distribution laws of logic are similar to some laws you already know from algebra. DeMorgan's law is like the fact that you can distribute a negative sign over addition, i.e. \(-(a+b)=-a -b\text{,}\) with the additional wrinkle that the operation flips (conjunction to disjunction and vice-versa).
The distribution of conjunction over disjunction (or vice-versa) looks daunting at first, but consider the following example. When you use the distribution law \(a(b+c)=ab+ac\) in algebra, you tend to say “distribute the \(a\)”. However, you are really distributing the “\(a\) times”:
Writing the distribution law this way, it is easier to see where the distribution law comes from in logic (just replace \(\times\) with \(\vee\) or \(\wedge\) and \(+\) with the other one).
DeMorgan's law is extremely important, so let's prove one of them.
Example 2.2.9.
Prove that \(\neg(p \wedge q) \equiv \neg p \vee \neg q\) using a truth table.
\(p\) | \(q\) | \(p \wedge q\) | \(\neg(p \wedge q)\) | \(\neg p\) | \(\neg q\) | \(\neg p \vee \neg q\) |
\(T\) | \(T\) | \(T\) | \(F\) | \(F\) | \(F\) | \(F\) |
\(T\) | \(F\) | \(F\) | \(T\) | \(F\) | \(T\) | \(T\) |
\(F\) | \(T\) | \(F\) | \(T\) | \(T\) | \(F\) | \(T\) |
\(F\) | \(F\) | \(F\) | \(T\) | \(T\) | \(T\) | \(T\) |
There are many columns here, so keep your eye on the columns \(\neg(p \wedge q)\) and \(\neg p \vee \neg q\text{.}\) The columns are the same, so the statements are equivalent. As an exercise, prove the other DeMorgan's law to yourself.
Finally, let's examine the properties of the conditional.
Name | Equivalence |
Material implication | \(p \to q \equiv \neg p \vee q\) |
False conditional | \(\neg (p \to q) \equiv p \wedge \neg q\) |
Contraposition | \(p \to q \equiv \neg q \to \neg p\) |
Mutual implication | \(p \leftrightarrow q \equiv (p \to q) \wedge (q \to p)\) |
Properties of the conditional
The first of these, material implication, is important to internalize. It says the conditional is actually just a disjunction. (Notice that both the disjunction and the conditional were true three times out of four in their truth tables.) This helps us understand why the conditional is what it is: \(p \to q\) means \(q\) is true, or else \(p\) isn't. Let's prove it with a truth table.
Example 2.2.12.
Prove \(p \to q \equiv \neg p \vee q\text{.}\)
\(p\) | \(q\) | \(p \to q\) | \(\neg p\) | \(\neg p \vee q\) |
\(T\) | \(T\) | \(T\) | \(F\) | \(T\) |
\(T\) | \(F\) | \(F\) | \(F\) | \(F\) |
\(F\) | \(T\) | \(T\) | \(T\) | \(T\) |
\(F\) | \(F\) | \(T\) | \(T\) | \(T\) |
To prove the false conditional rule, we will take a different approach using algebraic substitution. To understand this, consider the following example. Suppose \(x\text{,}\) \(y\text{,}\) and \(z\) are numbers. Suppose you know that \(x=y-2\text{.}\) Then, the number \(x+z+3\) is equal to \(y+z+1\text{,}\) because you can substitute the \(x\) for \(y-2\) and combine like terms. We can do the same with logical equivalence.
Example 2.2.14.
Prove the false conditional rule, that \(\neg(p \to q) \equiv p \wedge \neg q\text{.}\)
First, use material implication to substitute \(p \to q\) for \(\neg p \vee q\text{.}\)
Next, use DeMorgan's law to distribute the outer negation.
We have proven the false conditional rule. Also, consider the fact that \(p \to q\) is only false when \(p\) is true and \(q\) is false. Therefore it makes sense that the negation of \(p \to q\) would be \(p \wedge \neg q\text{.}\)
We have already seen that \(p \to q\) and \(q \to p\) are not equivalent. Contraposition says that \(p \to q\) and \(\neg q \to \neg p\) are equivalent. In the exercises you will have an opportunity to explore which forms of the conditional are and aren't equivalent, but for now, let's make sure we can prove that two statements aren't equivalent.
Example 2.2.15.
Prove that \(p\to q\) and \(q \to p\) are not equivalent.
\(p\) | \(q\) | \(p \to q\) | \(q \to p\) |
\(T\) | \(T\) | \(T\) | \(T\) |
\(T\) | \(F\) | \(F\) | \(T\) |
\(F\) | \(T\) | \(T\) | \(F\) |
\(F\) | \(F\) | \(T\) | \(T\) |
Since the columns for \(p \to q\) and \(q \to p\) are not the same, the statements are not equivalent.
That's a lot, isn't it? With practice, the rules of logical equivalence will become second nature like the rules of real number algebra. Let's do one more example where we prove an equivalence using substitution.
Example 2.2.17.
Prove that \(\neg(q \to r) \wedge s\) and \(q \wedge \neg(s \to r)\) are equivalent.
First, use the false conditional rule:
Since we know conjunction is associative,
Conjunction is also commutative:
Finally, let's apply the false conditional rule one more time.
So, the statements are equivalent. As an exercise, do the \(8\)-row truth table to see they are equivalent another way.
Subsection 2.2.2 Rules of inference
Equivalences are tautological biconditional statements. But, maybe an equivalence only goes “one way”. In that case, we have a rule of inference.
Definition 2.2.18.
We say that the statement \(\varphi \to \psi\) is a rule of inference if it is a tautology, write \(\varphi \Rightarrow \psi\text{,}\) and say that \(\varphi\) implies \(\psi\text{.}\)
Every single equivalence amounts to two rules of inference (the forward and the backward direction). Let's look at two rules of inference that only go one way.
Theorem 2.2.19.
The statement \([(p \to q) \wedge p] \to q\text{,}\) called modus ponens, is a rule of inference.
To be clear, \(p\) and \(q\) can be any statement at all. It is probably more correct to write \(\varphi\) and \(\psi\) instead, but we write \(p\) and \(q\) to avoid an overuse of unfamiliar Greek letters.
When you want to prove something is a tautology via substitution, it is useful to create as many disjunctions as possible and then use the cancellation \(p \vee \neg p \equiv T\text{.}\)
Proof.
First, use contraposition to write the equivalent statement
Apply DeMorgan's law:
Next, use material implication to write this as a disjunction.
We can use double negation and also reorder the disjunction.
Finally, apply material implication (the other way) one last time.
Since this statement is the disjunction of a statement and its negation, like \(p \vee \neg p\text{,}\) it is a tautology.
Example 2.2.20.
Suppose a trustworthy speaker tells you “If you do your homework, you will pass your math class.” Furthermore, suppose you do your homework. Then, by modus ponens, you can believe that you will pass your math class.
Theorem 2.2.21.
The statement
which says that conditional statements are transitive, is a rule of inference.
We'll prove this one with the truth table.
Proof.
In the truth table below, there are no rows where \((p \to q) \wedge (q \to r)\) is true but \(p \to r\) is false. Therefore, \([(p \to q) \wedge (q \to r)] \to (p \to r)\) is always true.
\(p\) | \(q\) | \(r\) | \(p \to q\) | \(q \to r\) | \((p \to q) \wedge (q \to r)\) | \(p \to r\) |
\(T\) | \(T\) | \(T\) | \(T\) | \(T\) | \(T\) | \(T\) |
\(T\) | \(T\) | \(F\) | \(T\) | \(F\) | \(F\) | \(F\) |
\(T\) | \(F\) | \(T\) | \(F\) | \(T\) | \(F\) | \(T\) |
\(T\) | \(F\) | \(F\) | \(F\) | \(T\) | \(F\) | \(F\) |
\(F\) | \(T\) | \(T\) | \(T\) | \(T\) | \(T\) | \(T\) |
\(F\) | \(T\) | \(F\) | \(T\) | \(F\) | \(F\) | \(T\) |
\(F\) | \(F\) | \(T\) | \(T\) | \(T\) | \(T\) | \(T\) |
\(F\) | \(F\) | \(F\) | \(T\) | \(T\) | \(T\) | \(T\) |
There are many rules of inference, but these are two very important ones. In the next chapter, we will expand our system of logic to be able to express more complicated statements.