﻿ ﻿Notation - From Mathematics to Generic Programming (2011)

# From Mathematics to Generic Programming (2011)

### Appendix A. Notation

The following are symbols used in the book that may not be familiar to a nonmathematical reader and that are not explained in the main text. (Other new symbols are explained when they are introduced.) We’ll list the symbols first, then give a few examples of their use.

¬p

Logical negation. Read “not p.” If p is true, then ¬p is false, and vice versa.

p q

Logical disjunction. Read “p or q.” The statement p q is true if either p is true, or q is true, or they are both true.

p q

Logical conjunction. Read “p and q.” The statement p q is true only when both p and q are true.

p q

Logical implication. Read “p implies q” or “if p, then q.” Note that the statement p q is false only when p is true and q is false. It may not be intuitive that the expression is true when p is false, but one way to think of it is “you can make an argument for anything if you get to start by assuming something that isn’t true.” For more about logical implication, see “Implication and the Contrapositive” at the end of this appendix.

p q

Logical equivalence. Read “p if and only if q” and sometimes written “p iff q.” The statement p q is true when both p and q are true, or when both p and q are false. This is exactly the same as saying (p q) ∧ (q p).

x S

Set membership. Read “x is an element of S” or “x is in S.”

x S

Negation of set membership. Read “x is not an element of S” or “x is not in S.”

x S

Universal quantifier. Read “for all x in S” or “for any x in S.” Sometimes membership in the set S is assumed from the context, so we just write ∀x.

x S

Existential quantifier. Read “there exists an x in S” or “there is an x in S.” Sometimes membership in the set S is assumed from the context, so we just write ∃x.

ST

Set union. Read “the union of S and T.” An element x is in the union of S and T if it is in either S or T or both.

ST

Set intersection. Read “the intersection of S and T.” An element x is in the intersection of S and T if it is in both S and T.

S = {x | . . . }

Set definition. Read “S is the set of all x such that ...” (where the “ ... ” could be any list of conditions about x). The set of natural numbers 0, 1, 2, 3, ...—numbers used for counting. (Some authors do not include 0 in the set of natural numbers.) The set of integers, which includes all the natural numbers and (for all except zero) their negations. The set {0, 1, 2, ..., n – 1} of remainders modulo n. The set of rational numbers (the ratio of two integers). The set of real numbers. The set of complex numbers a + bi, where a and b are real numbers and i2 = –1.

Examples

even(x) ¬odd(x)

x is even if and only if x is not odd.”

S = {x | x  ∧ even (x)}

“S is the set of all x’s such that x is in the set of integers and x is even” or, more concisely, “S is the set of all even integers.”

xy: y = x + 1

“For any x, there is a y such that y equals x plus 1.”

x {S ∩ T} x {S T}

“If x is in the intersection of S and T, then x is in the union of S and T.”

Implication and the Contrapositive

The implication p q (also known as a conditional) is logically equivalent to a variant called the contrapositive, which has the following form:

¬q ¬p

Consider this example:

If n = 2, then n is even.

Here our proposition p is “n = 2” and our proposition q is “n is even”; this conditional happens to be true. To form the contrapositive, we logically negate both sides and reverse the direction of the implication. So the contrapositive of the preceding statement is

If n is not even, then n ≠ 2

which is also true.

Since a conditional statement and its contrapositive are logically equivalent, we occasionally replace one with the other, in situations where the latter form is more convenient.

Don’t confuse the contrapositive of p q with its converse, which is q p. Just because an implication is true does not mean its converse is true; the two are independent. Continuing the earlier example, even though our original statement was true, its converse

If n is even, then n = 2

is clearly false.

﻿