Elementary Discrete Mathematics 2

Subsection 2.2.1 Equivalence

Let's begin with some related definitions.

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{.}\)

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.

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.

Next, let's check out how negation, conjunction, and disjunction interact with one another.

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.

Finally, let's examine the 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.

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.

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.

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.

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.

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.

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{.}\)

We'll prove this one with the truth table.

There are many rules of inference, but these are two very important ones. In the next section, we will expand our system of logic to be able to express more complicated statements.