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

Is this related to the problem of expressions like “-3 < -2 < -1" resulting in false in most programming languages? I've had more than one mentee make this error.

Yes and no :). No, in the sense that your example is a problem in most languages (like C++) because of Boolean promotion, but in this case the values being compared are already Boolean.

Yes, in the sense that the corresponding C++ expression (p[1] == p[2] == p[3] == … == p[n]), where the p[k] are of type bool, has the same problem as Rosen’s notation; this “looks” like it might evaluate to true iff all of the p[k] are equal and false otherwise, but it doesn’t.

The *intended* meaning of this expression is essentially how Python treats chained comparisons, with an implicit AND stuck in between each consecutive binary comparison.

I thought was short hand for …

Right! The problem, IMO, is that this is never mentioned anywhere in the text, and to a student, it isn’t clear that this is “special” notation, since it’s well-formed as is. Rosen even follows up with the tautology justifying the usual “chain-of-implications” approach to proving equivalences like this, formatted as: