I have been reviewing Rosen’s Discrete Mathematics and Its Applications textbook for a course this fall, and I noticed an interesting potential pitfall for students in the first chapter on logic and proofs.
Many theorems in mathematics are of the form, “ if and only if ,” where and are logical propositions that may be true or false. For example:
Theorem 1: An integer is even if and only if is even.
where in this case is “ is even” and is “ is even.” The statement of the theorem may itself be viewed as a proposition , where the logical connective is read “if and only if,” and behaves like Boolean equality. Intuitively, states that “ and are (materially) equivalent; they have the same truth value, either both true or both false.”
(Think Boolean expressions in your favorite programming language; for example, the proposition , read “ and ,” looks like p && q
in C++, assuming that p
and q
are of type bool
. Similarly, the proposition looks like p == q
in C++.)
Now consider extending this idea to the equivalence of more than just two propositions. For example:
Theorem 2: Let be an integer. Then the following are equivalent:
- is even.
- is even.
- is even.
The idea is that the three propositions above (let’s call them ) always have the same truth value; either all three are true, or all three are false.
So far, so good. The problem arises when Rosen expresses this general idea of equivalence of multiple propositions as
Puzzle: What does this expression mean? A first concern might be that we need parentheses to eliminate any ambiguity. But almost unfortunately, it can be shown that the connective is associative, meaning that this is a perfectly well-formed propositional formula even without parentheses. The problem is that it doesn’t mean what it looks like it means.
Reference:
- Rosen, K. H. (2011). Discrete Mathematics and Its Applications (7th ed.). New York, NY: McGraw-Hill. ISBN-13: 978-0073383095