Discrete Mathematics An Open Introduction, 4th Edition

In order to do mathematics, we must be able to talk and write about mathematics. Perhaps your experience with mathematics so far has mostly involved finding numerical answers to problems. As we embark towards more advanced and abstract mathematics, writing will play a more prominent role in the mathematical process.

In fact, the primary goal of mathematics, as an academic discipline in its own right, is to establish general mathematical truths. How can we know whether these facts, perhaps called theorems or propositions, are true? We construct valid arguments, called proofs, which establish the truth of the statements. Here, an argument is not the sort of thing you have with your Mom when you disagree about what to have for dinner. Rather, we have a technical definition of the term.

To determine whether we have a proof of a statement, we must decide both whether every premise is true, and whether the argument is valid: whether the conclusion follows from the premises. How can we do this?

Since arguments are built up of statements, we must agree on what counts as a statement.

If the sentences in an argument could not be true or false, there would be no way to determine whether the argument was valid, since validity describes a relationship between the truth values of the premises and conclusions.

The goal of this section is to explore the different “shapes” a statement can take. We will see that more complicated statements can be built up from simpler ones, in ways that entirely determine their truth value based on the truth values of their parts.

A statement is any declarative sentence which is either true or false. A statement is atomic if it cannot be divided into smaller statements, otherwise it is called molecular.

The reason the sentence “$3+x=12$” is not a statement is that it contains a variable. Depending on what $x$ is, the sentence is either true or false, but right now it is neither. One way to make the sentence into a statement is to specify the value of the variable in some way. This could be done by setting a specific substitution, for example, “$3+x=12$ where $x=9\text{,}$” which is a true statement. Or you could capture the free variable by quantifying over it, as in, “For all values of $x\text{,}$ $3+x=12\text{,}$” which is false. We will discuss quantifiers in more detail in the subsection Quantifiers and Predicates below.

You can build more complicated (molecular) statements out of simpler (atomic or molecular) ones using logical connectives. For example, this is a molecular statement:

Note that we can break this down into two smaller statements. The two shorter statements are connected by an “and.” We will consider 5 connectives: “and” (Sam is a man, and Chris is a woman), “or” (Sam is a man, or Chris is a woman), “if…, then…” (if Sam is a man, then Chris is a woman), “if and only if” (Sam is a man if and only if Chris is a woman), and “not” (Sam is not a man). The first four are called binary connectives (because they connect two statements) while “not” is an example of a unary connective (since it applies to a single statement).

These molecular statements are, of course, still statements, so they must be either true or false. The crucial observation here is that which truth value the molecular statement achieves is completely determined by the type of connective and the truth values of the parts. We do not need to know what the parts actually say or whether they have some material connection to each other, only whether those parts are true or false.

To analyze logical connectives, it is enough to consider propositional variables (sometimes called sentential variables), usually capital letters in the middle of the alphabet: $P,Q,R,S,\dots \text{.}$ We think of these as standing in for (usually atomic) statements, but there are only two values the variables can achieve: true or false.

¹

In computer programming, we should call such variables Boolean variables.

We also have symbols for the logical connectives: $\wedge \text{,}$ $\vee \text{,}$ $\to \text{,}$ $\leftrightarrow \text{,}$ $\mathrm{\neg }\text{.}$

The truth value of a statement is determined by the truth value(s) of its part(s), depending on the connectives:

Each of the above definitions can be represented in a table, called a truth table. We simply list what the truth value of the statement is for each possible combination of truth values of the parts.

For example, we can use the truth table for $P\to Q$ to decide whether the statement, “If 5 is even, then 6 is even,” is true or false. Here $P$ is the statement “5 is even,” and $Q$ is the statement “6 is even.” Since 5 is not even, the statement $P$ is false. Since 6 is even, the statement $Q$ is true. The truth table tells us that the statement $P\to Q$ is true when $P$ is false and $Q$ is true (the 3rd row). So the statement, “If 5 is even, then 6 is even,” is true. (If you don’t like that the statement is true, hold on to that thought, and we will hopefully resolve it soon.)

Note that for us, or is the inclusive or (and not the sometimes used exclusive or) meaning that $P\vee Q$ is in fact true when both $P$ and $Q$ are true. As for the other connectives, “and” behaves as you would expect, as does negation. The biconditional (if and only if) might seem a little strange, but you should think of this as saying the two parts of the statements are equivalent in that they have the same truth value.

This leaves only the implication $P\to Q$ which has a slightly different meaning in mathematics than in ordinary usage. However, implications are so common and useful in mathematics that we must develop a level of fluency with their use which warrants a whole section (Section 1.2).

The way we define logical connectives and their truth value is very precise and technical. Often, language is not. Part of learning how to communicate mathematics is learning the cultural norms of mathematical language and how to translate statements in ordinary language into these technical statements. This will get easier with practice, so make sure you are talking to lots of people about the math you are studying.

Here are a few examples of how ordinary language might be difficult to translate.

Did you know that all mammals have hair? That every integer is even or odd? That some odd numbers are not prime?

Our goal is to explore how to write statements such as these in mathematical notation to highlight the logical structure of the statements.

This will require considering a new sort of basic sentence called a predicate, which is like a statement, but contains a free variable. When you replace that variable with a constant of some sort, then the sentence becomes a statement proper. Think of a predicate as making a claim about the values that are substituted for the “placeholder” variable(s).

A predicate can be made into a (true or false) statement by evaluating it at some constant(s), or we can claim that some or all possible constants would make the resulting statement true or false. This is done using quantifiers.

We usually write predicates similar to how you write a function, although with capital letters. For example, we might use the predicate $P(x)$ to represent “$x$ is prime”. We can then say that $P(7)$ is true (since 7 is prime) and that $P(8)$ is false. Or using quantifiers, we can (falsely) claim that all numbers are prime by writing $\mathrm{\forall }xP(x)$ or (truthfully) claim that there is at least one prime number, by writing $\mathrm{\exists }xP(x)\text{.}$

Just like we did for propositional logic and the logical connectives, we should decide what it means for a quantified predicate to be true or false. We say $\mathrm{\forall }xP(x)$ is true if $P(a)$ is true no matter what constant $a$ we substitute for $x\text{.}$ And similarly, $\mathrm{\exists }xP(x)$ is true if there is at least one value $a$ for which $P(a)$ is true.

Is this statement true? The answer depends on our domain of discourse. When we say “for all” $x\text{,}$ do we mean all positive integers or all real numbers or all elephants or...? Usually, this information is implied by the context of the statement. In discrete mathematics, we almost always quantify over the natural numbers, $0,1,2,\dots \text{,}$ so let’s take that for our domain of discourse here.

We will explore some rules for working with quantifiers and other connectives in Section 1.3. For now, we will focus on translating between informal statements in ordinary language and the more precise language of logic. There is no perfect algorithm for doing this translation, but here are a few useful rules of thumb.

To make sense of this, think about what we mean by statements like these in terms of sets. We claim that the set of mammals is contained in, or is a subset of, the set of hairy things. What we mean by “$A$ is a subset of $B$” is precisely that every element of $x$ is an element of $y\text{.}$ This can also be expressed by saying that “if $x$ is an element of $A\text{,}$ then $x$ is also an element of $B\text{.}$”

Again, it is helpful to think of how to express such statements in terms of sets. To say that some cats can swim is to say that there are things that belong both to the set of cats and to the set of swimming things. Such animals belong to the intersection of these two sets, which you can describe as belonging to the first set and the second set. Existential statements of this form claim that the intersection of the two sets is not empty.