A crash course in logic

At the heart of every mathematical argument is a proposition, a statement that is unambiguously true or false. “The cat is black” is a proposition; “the cat is cute” is not.

Examples and non-examples:

Two propositions $p$ and $q$ are said to be logically equivalent if they have the same truth value: both must be true, or else both must be false. For example, “$x$ is a positive number” and “$x > 0$” are logically equivalent propositions. We write $p \Leftrightarrow q$ to denote that $p$ and $q$ are logically equivalent.

Now, the statement “$p$ and $q$ are logically equivalent” is also a proposition, as $p$ and $q$ are either logically equivalent, or not. Observing that $p \Leftrightarrow q$ is true precisely when $p$ and $q$ share the same truth value, we can draw up the following truth table:

$$\begin{array}{|c:c:c|} \hline p & q & p \Leftrightarrow q\\ \hline \hline \mathrm{True} & \mathrm{True} & \mathrm{True}\\ \hdashline \mathrm{True} & \mathrm{False} & \mathrm{False} \\ \hdashline \mathrm{False} & \mathrm{True} & \mathrm{False} \\ \hdashline \mathrm{False} & \mathrm{False} & \mathrm{True} \\ \hline \end{array}$$

We typically read $p \Leftrightarrow q$ as “$p$ if and only if $q$.” The relevance of if and only if will be discussed later in the post.

We will make use of the language of sets throughout the post. A set is an unambiguous collection of mathematical objects. In other words, we should always be able to tell if a mathematical object is in a set or not.

For example, all integers between 1 and 5 defines a set. We know that 4 is in the set, and that 16 is not. In contrast, all large numbers does not define a set, as we do not know what constitutes a “large number.”

We use curly brackets $\lbrace \rbrace $ to write out a set. For example, all integers between 1 and 5 is $\lbrace 1, 2, 3, 4, 5\rbrace $.

Given a set $X$ and a mathematical object $x$, we write $x \in X$ to indicate that $x$ belongs to $X$. Similarly, we write $x \notin X$ to indicate that $x$ does not belong to $X$. We say that $x$ is an element of $X$ in case $x \in X$.

In lieu of writing out all elements of a set, we can use the set-builder notation to specify a set. For example, all integers between 1 and 350 can be written as

$$\lbrace n \in \mathbb{Z}:1 \leq n \leq 350\rbrace ,$$

which we read as “the set of all $n$ in $\mathbb{Z}$ such that $1 \leq n \leq 350$.”

We note that every element of the above set is an element of $\mathbb{Z}$, which follows from the “all $n$ in $\mathbb{Z}$ such that” part of the definition. It then makes sense to consider the above set to be a subset of $\mathbb{Z}$.

In general, we say that a set $X$ is a subset of another set $Y$ in case every element of $X$ is an element of $Y$. We write $X \subseteq Y$ to denote the subset relation. Similarly, we write $X \supseteq Y$ to denote that $Y$ is a subset of $X$.

If $X \subseteq Y$ and $X \supseteq Y$, then $x$ is an element of $X$ if and only if it is an element of $Y$. In other words, $X$ and $Y$ share all of their elements. We can thus consider $X$ and $Y$ to be the same set with different labels and declare them equal.

Let us now consider the case $X = Y$, i.e., where the elements of $X$ are precisely those of $Y$. In this case, every element of $X$ is of course an element of $Y$, and so $X \subseteq Y$. Similarly, every element of $Y$ is an element of $X$, and we have the subset relation $X \supseteq Y$. We have thus derived our first theorem of set theory:

Theorem 1. Two sets $X$ and $Y$ are equal if and only if $X \subseteq Y$ and $X \supseteq Y$.

In the language of logical equivalence, Theorem 1 asserts $p \Leftrightarrow q$, where $p$ is the statement $X = Y$, and $q$ is the statement $X \subseteq Y$ and $X \supseteq Y$. Note that $q$ consists of two propositions

connected by the word and. The expectation here is that the composite proposition $q$ is considered true only when both (1) and (2) are true.

The notion of connecting two propositions with and can be formalized by the conjunction operator $\land$:

$$\begin{array}{|c:c:c|} \hline p & q & p \land q\\ \hline \hline \mathrm{True} & \mathrm{True} & \mathrm{True}\\ \hdashline \mathrm{True} & \mathrm{False} & \mathrm{False} \\ \hdashline \mathrm{False} & \mathrm{True} & \mathrm{False} \\ \hdashline \mathrm{False} & \mathrm{False} & \mathrm{False} \\ \hline \end{array}$$

We read $p \land q$ as “$p$ and $q$.”

With equivalence and conjunction at hand, we can write out Theorem 1 as $p \Leftrightarrow (q_1 \land q_2)$, where

We read $p \Leftrightarrow (q_1 \land q_2)$ as “$p$ if and only if $q_1$ and $q_2$.”

We combine the truth table of equivalence with that of conjunction to draw up the truth table of $p \Leftrightarrow (q_1 \land q_2)$:

$$\begin{array}{|c:c:c:c:c|} \hline p & q_1 & q_2 & q_1 \land q_2 & p \Leftrightarrow (q_1 \land q_2) \\ \hline \hline \mathrm{True} & \mathrm{True} & \mathrm{True} & \mathrm{True} & \mathbf{True} \\ \hdashline \mathrm{True} & \mathrm{True} & \mathrm{False} & \mathrm{False} & \mathrm{False} \\ \hdashline \mathrm{True} & \mathrm{False} & \mathrm{True} & \mathrm{False} & \mathrm{False} \\ \hdashline \mathrm{True} & \mathrm{False} & \mathrm{False} & \mathrm{False} & \mathrm{False} \\ \hdashline \mathrm{False} & \mathrm{True} & \mathrm{True} & \mathrm{True} & \mathrm{False} \\ \hdashline \mathrm{False} & \mathrm{True} & \mathrm{False} & \mathrm{False} & \mathbf{True} \\ \hdashline \mathrm{False} & \mathrm{False} & \mathrm{True} & \mathrm{False} & \mathbf{True} \\ \hdashline \mathrm{False} & \mathrm{False} & \mathrm{False} & \mathrm{False} & \mathbf{True} \\ \hline \end{array}$$

The truth table shows that we must check eight separate cases to establish the validity of $p \Leftrightarrow (q_1 \land q_2)$, but this is not what we have done in the proof of Theorem 1.

To tease apart the proof, we let

and observe that we have established the following statements:

The underlying assumption is that establishing the above amounts to proving $p_0 \Leftrightarrow q_0$. To verify this, we need to formalize the notion of implication, the task we take up now.

Given two propositions $p$ and $q$, we say that $p$ implies $q$ if $q$ is true whenever $p$ is true. We write $p \Rightarrow q$ to denote the implication.

$$\begin{array}{|c:c:c|} \hline p & q & p \Rightarrow q\\ \hline \hline \mathrm{True} & \mathrm{True} & \mathrm{True}\\ \hdashline \mathrm{True} & \mathrm{False} & \mathrm{False} \\ \hdashline \mathrm{False} & \mathrm{True} & \mathrm{True} \\ \hdashline \mathrm{False} & \mathrm{False} & \mathrm{False} \\ \hline \end{array}$$

Note that the proposition $p \Rightarrow q$ is true regardless of the outcome $q$ if the hypothesis $p$ is false, the phenomenon known as vacuous truth. For example, “if $2=3$, then pigs can fly” is a true statement — since $2 \neq 3$, it doesn’t matter what the rest of the statement says.

We now recall that the truth table corresponding to proposition $p \Leftrightarrow q$ is as follows:

$$\begin{array}{|c:c:c|} \hline p & q & p \Leftrightarrow q\\ \hline \hline \mathrm{True} & \mathrm{True} & \mathrm{True}\\ \hdashline \mathrm{True} & \mathrm{False} & \mathrm{False} \\ \hdashline \mathrm{False} & \mathrm{True} & \mathrm{False} \\ \hdashline \mathrm{False} & \mathrm{False} & \mathrm{True} \\ \hline \end{array}$$

Compare the truth value of $p \land q$ in each case with the truth value of $(p \Leftarrow q) \land (p \Rightarrow q)$, computed below:

$$\begin{array}{|c:c:c:c:c|} \hline p & q & p \Leftarrow q & p \Rightarrow q & (p \Leftarrow q) \land (p \Rightarrow q) \\ \hline \hline \mathrm{True} & \mathrm{True} & \mathrm{True} & \mathrm{True} & \mathrm{True} \\ \hdashline \mathrm{True} & \mathrm{False} & \mathrm{False} & \mathrm{True} & \mathrm{False} \\ \hdashline \mathrm{False} & \mathrm{True} & \mathrm{True} & \mathrm{False} & \mathrm{True} \\ \hdashline \mathrm{False} & \mathrm{False} & \mathrm{True} & \mathrm{True} & \mathrm{True} \\ \hline \end{array}$$

We have thus established the following theorem:

Theorem 2. Two propositions \(p\) and \(q\) are logically equivalent if and only if \(p\) implies \(q\) and \(q\) implies \(p\). In other words,

$$(p \Leftrightarrow q) \Leftrightarrow [(p \Leftarrow q) \land (p \Rightarrow q)].$$

We have implicitly assumed in Theorem 1 and Theorem 2 that the theorem holds for all objects in question. To formalize such arguments, we introduce the universal quantifier $\forall$. The statement

$$(\forall x \in X) p(x)$$

is to be read as “for each element $x$ of set $X$, the proposition $p(x)$ is true.” An example of a universally quantified statement is

$$(\forall n \in \mathbb{Z}) n \leq n+5,$$

i.e., “for each integer $n$, the inequality $n \leq n+5$ holds. This, of course, is a true statement.

The symbol $p(x)$ represents a collection of propositions indexed by a variable $x$. In other words, $p(x_0)$ is a proposition for each fixed value $x_0$ of $x$. In the example above, $p(n)$ is $n \leq n+5$, and so we have

Such collections of propositions are referred to as predicates.

Arguments involving predicates are called predicate logic, or first-order logic. Arguments that involve only propositions are called propositional logic, or zeroth-order logic.

We typically reason with predicates by binding the variables through quantifiers and then falling back on the techniques of propositional logic. For example, the statement

$$(\forall n \in \mathbb{Z}) (n+2)+1 = n+3$$

has its variable $n$ bound by the universal quantifier $\forall n \in \mathbb{Z}$, at which point the statement

$$(n+2)+1 = n+3$$

becomes a proposition. On the other hand, propositional logic cannot deal with statement

$$(n+2)+1 = n+3$$

by itself, as the variable $n$ has no meaning by itself.

With the language of predicate logic, we can write out the full content of Theorem 1 as follows:

Theorem 1'. $\forall X\forall Y[(X = Y) \Leftrightarrow (X \subseteq Y) \land (X \supseteq Y)]$

This concludes a brief tour of the basics of propositional logic. Below is a series of exercises that develops additional material on the topic. After all, there is no better way to learn mathematics than to build it ourselves:

“Mathematics, you see, is not a spectator sport. To understand mathematics means to be able to do mathematics.” —George Pólya, How To Solve It: A New Aspect of Mathematical Method

Exercise 2.1. In propositional logic, the negation operation $\lnot$ is defined by the following truth table:

$$\begin{array}{|c:c|} \hline p & \lnot p \\ \hline \hline \mathrm{True} & \mathrm{False} \\ \hdashline \mathrm{False} & \mathrm{True} \\ \hline \end{array}$$

Show that two negations cancel each other out, i.e.,

$$p \Leftrightarrow \lnot (\lnot p).$$

Exercise 2.2. Show that the contrapositive

$$\lnot p \Leftarrow \lnot q$$

of an implication relation $p \Rightarrow q$ is logically equivalent to the implication. In other words, show that

$$(p \Rightarrow q) \Leftrightarrow (\lnot p \Leftarrow \lnot q).$$

Exercise 2.3. Show that the converse

$$p \Leftarrow q$$

of an implication relation $p \Rightarrow q$ is logically equivalent to the inverse

$$\lnot p \Rightarrow \lnot q$$

of the relation. In other words, show that

$$(p \Leftarrow q) \Leftrightarrow (\lnot p \Rightarrow \lnot q).$$

Remark (The nonequivalence of a proposition and its converse ). An implication $p \Rightarrow q$ is not logically equivalent to its converse $q \Rightarrow p$ or its inverse $\lnot p \Rightarrow \lnot q$. Consider, for example,

For each fixed integer $x$, the proposition $p(x)$ implies $q(x)$. On the other hand, setting $x = 7$ renders $p(x)$ true but $q(x)$ false, which shows that neither the converse $p(7) \Leftarrow q(7) $ nor the inverse $\lnot p(7) \Rightarrow \lnot q(7)$ holds true.

The nonequivalence of a proposition and its converse shows that Theorem 2 is meaningful. There would be no point in distinguishing between an implication $p \Rightarrow q$ and a logical equivalence $p \Leftrightarrow q$ if they were always the same.

Theorem 2 is the standard way to establish logical equivalence in mathematics. For this reason, the word conversely appears quite frequently in the mathematics literature. $\square$.

Exercise 2.4. The formalization of the connective or is the disjunction operation $\lor$, which is defined by the following truth table:

$$\begin{array}{|c:c:c|} \hline p & q & p \lor q \\ \hline \hline \mathrm{True} & \mathrm{True} & \mathrm{True} \\ \hdashline \mathrm{True} & \mathrm{False} & \mathrm{True} \\ \hdashline \mathrm{False} & \mathrm{True} & \mathrm{True} \\ \hdashline \mathrm{False} & \mathrm{False} & \mathrm{False} \\ \hline \end{array}$$

Show that conjunction is the negation of disjunction. More specifically, show that

$$\lnot (p \land q) \Leftrightarrow (\lnot p \lor \lnot q).$$

Show also that disjunction is the negation of conjunction. More specifically, show that

$$\lnot (p \lor q) \Leftrightarrow (\lnot p \land \lnot q).$$

Exercise 2.5. Show that the implication relation $p \Rightarrow q$ is logically equivalent to

$$(\lnot p) \lor q.$$

Exercise 2.6. Show that

$$(p \land p) \Leftrightarrow p$$

and that

$$(p \lor p) \Leftrightarrow p.$$

This shows that every proposition is idempotent under conjunction and disjunction.

Exercise 2.7. Let $\operatorname{True}$ denote a proposition that is always true. Show that

$$(p \lor \lnot p) \Leftrightarrow \operatorname{True}.$$

Similarly, we let $\operatorname{False}$ denote a proposition that is always false. Show that

$$(p \land \lnot p) \Leftrightarrow \operatorname{False}.$$

Exercise 2.8. Let $\operatorname{True}$ and $\operatorname{False}$ be defined as in Exercise 2.7. Show that

$$(p \land \operatorname{True}) \Leftrightarrow p$$

and that

$$(p \lor \operatorname{False}) \Leftrightarrow p.$$

Exercise 2.9. Show that conjunction and disjunction satisfy the following commutative properties:

Exercise 2.10. Show that conjunction and disjunction satisfy the following associative properties:

Exercise 2.11. Show that conjunction and disjunction together satisfy the following distributive properties:

Remark (The Boolean Ring). Exercises 2.8 - 2.11 show that conjunction and disjunction possess properties analogous to the usual arithmetic operations: multiplication and addition.

To push this analogy further, we define a commutative ring to be a set $R$ equipped with an addition operation and a multiplication operation that satisfy the following properties:

  1. Addition is commutative: $a+b = b+a$ for all $a,b \in R$;
  2. Multiplication is commutative: $ab = ba$ for all $a,b \in R$;
  3. Addition is associative: $a+(b+c) = (a+b)+c$ for all $a,b,c \in R$;
  4. Multiplication is commutative: $a(bc) = (ab)c$
  5. There is an additive identity $\mathfrak{0}$ such that $a + \mathfrak{0} = a$ for all $a \in R$;
  6. There is a multiplicative identity $\mathfrak{1}$ such that $a\mathfrak{1} = a$ for all $a \in R$;
  7. Addition and multiplication satisfy the distributive properties $(a+b)c = ac + bc$ for all $a,b,c \in R$;
  8. Each $a \in R$ has an additive inverse $-a$, so that $a + (-a) = \mathfrak{0}$.

The standard example of a commutative ring is the set of integer $\mathbb{Z}$ with integer addition and integer multiplication. Similarly, the set of rational numbers $\mathbb{Q}$ with the usual addition and multiplication rules of fractions gives rise to the ring of rational numbers.

We can model conjunction and disjunction as a ring as well. To see this, we suppose that $R$ is a set of propositions with the following closure properties:

  1. If $p$ and $q$ are elements of $R$, then $p \land q$ and $p \lor q$ are elements of $R$.
  2. If $p$ is an element of $R$, then $\lnot p$ is an element of $R$.

Exercise 2.7 now shows that $\operatorname{True}$ and $\operatorname{False}$ are elements of $R$.

We define multiplication of two propositions to be their conjunction:

$$pq = p \land q.$$

We define addition of two propositions to be their exclusive disjunction:

$$p + q = (p \lor q) \land \lnot (p \land q).$$

Exercises 2.8 - 2.11 show that multiplication and addition are commutative, associative, and distributive. Moreover, by defining

$$\mathfrak{0} = \operatorname{True}$$

and

$$\mathfrak{1} = \operatorname{False},$$

we have that $p + \mathfrak{0} = p$ and $p\mathfrak{1} = p$ for all propositions $p \in R$. Finally, we observe that $\lnot p$ is the additive inverse of $p$; below, we use the equal symbol $=$ to denote logical equivalence:

$$\begin{align*} p + (\lnot p) &= (p \lor \lnot p) \land \lnot (p \land \lnot p) \\ &= \operatorname{True} \land \lnot (\operatorname{False}) \\ &= \operatorname{True} \land \operatorname{True} \\ &= \operatorname{True} \\ &= \mathfrak{0}. \end{align*}$$

It follows that the set of propositions $R$ with conjunction as multiplication and exclusive disjunction as addition forms a commutative ring, known as a Boolean ring.

Let us consider, for example, the Boolean ring $R = \lbrace \operatorname{True}, \operatorname{False}\rbrace $. $R$ is an adequate, simple representation of proposition logic, as every proposition is either true or false.

Recalling that $\mathfrak{0} = \operatorname{True}$ and $\mathfrak{1} = \operatorname{False}$, we have the following addition and multiplication tables:

$$\begin{array}{c:c:c} + & \mathfrak{0} & \mathfrak{1} \\ \hdashline \mathfrak{0} & \mathfrak{0} & \mathfrak{1} \\ \hdashline \mathfrak{1} & \mathfrak{1} & \mathfrak{0} \end{array}$$

$$\begin{array}{c:c:c} \cdot & \mathfrak{0} & \mathfrak{1} \\ \hdashline \mathfrak{0} & \mathfrak{0} & \mathfrak{0} \\ \hdashline \mathfrak{1} & \mathfrak{0} & \mathfrak{1} \end{array}$$

From the above computation, we see that exclusive disjunction and conjunction correspond precisely to addition and multiplication modulo 2. It would not be easy to see this correspondence without the Boolean ring concept!

The study of mathematical structures and their equivalences is called abstract algebra. We refer the interested readers to Michael Artin’s MIT OpenCourseWare on the subject. For starters, try proving that every commutative ring that consists solely of elemenets satisfying the idempotence relation

$$xx = x$$

is a Boolean ring. $\square$

Exercise 2.12. Show that the implication relation satisfies the following transitive property:

$$[(p \Rightarrow q) \land (q \Rightarrow r)] \Rightarrow (p \Rightarrow r).$$

Exercise 2.13. Show that the universal quantifier distributes over conjunction. In other words, show that

$$(\forall x \in X)[P(x) \land Q(x)] \Leftrightarrow [(\forall x \in X P(x)) \land (\forall x \in X Q(x))].$$

Exercise 2.14.The statement

$$(\exists x \in X) P(x)$$

is to be read as “there exists an element (x) of set (X) such that the proposition (p(x)) is true,” and the symbol (\exists) is called the existential quantifier. Show that the existential quantifier is the negation of the universal quantifier. More specifically, show that

$$(\forall x \in X)[\lnot P(x)] \Leftrightarrow \lnot (\exists x \in X) P(x).$$

Hint: To establish the implication

$$(\forall x \in X)[\lnot P(x)] \Rightarrow \lnot (\exists x \in X) P(x).$$

fix an arbitrary element (x_0) of (X), assume that (\lnot P(x)) is true, and show that (P(x)) is false. Argue that the proof holds for every element of (X), which means that no element of (X) renders (P(x)) true.

To complete the proof, show that the inverse

$$\lnot (\forall x \in X)[\lnot P(x)] \Rightarrow (\exists x \in X) P(x)$$

holds.

Exercise 2.15.Show that the existential quantifier distributes over disjunction. In other words, show that

$(\exists x \in X)[P(x) \lor Q(x)] \Leftrightarrow [(\exists x \in X P(x)) \lor (\exists x \in X Q(x))].$