Logic

Section 0.2 Logic

When dealing with mathematical statements and arguments, we must pay close attention to logical structure. This section introduces both logical connectors and quantifiers, and carefully describes how to determine the truth values of propositions built from these operations.

Subsection Propositional logic

A proposition is a sentence that is either true or false. We build compound propositions from component propositions using logical operators (or logical connectors); the truth value of the compound proposition is defined as a function of the truth values of the component propositions.

Definition 0.2.1. Logical operators.

Negation.
Given a proposition \(\mathcal{P}\text{,}\) the negation of \(\mathcal{P}\) is the proposition “Not \(\mathcal{P}\)”, denoted \(\neg\mathcal{P}\) in logical notation, the truth value of which is defined as follows: \(\neg\mathcal{P}\) is true exactly when \(\mathcal{P}\) is false.
Conjunction (logical and).
Given propositions \(\mathcal{P}\) and \(\mathcal{Q}\text{,}\) their conjuction is the proposition “\(\mathcal{P}\) and \(\mathcal{Q}\)”, denoted \(\mathcal{P}\land \mathcal{Q}\) in logical notation, the truth value of which is defined as follows: \(\mathcal{P}\land\mathcal{Q}\) is true when both \(\mathcal{P}\) and \(\mathcal{Q}\) are true, and false otherwise.
Disjunction (logical or).
Given propositions \(\mathcal{P}\) and \(\mathcal{Q}\text{,}\) their disjunction is the proposition “\(\mathcal{P}\) or \(\mathcal{Q}\)”, denoted \(\mathcal{P}\lor \mathcal{Q}\) in logical notation, the truth value of which is defined as follows: \(\mathcal{P}\lor \mathcal{Q}\) is true when at least one of \(\mathcal{P}\) and \(\mathcal{Q}\) is true, and false otherwise.
Logical implication (if-then).
Given propositions \(\mathcal{P}\) and \(\mathcal{Q}\text{,}\) the proposition “If \(\mathcal{P}\text{,}\) then \(\mathcal{Q}\)”, denoted \(\mathcal{P}\implies\mathcal{Q}\) in logical notation, is called an implication, and its truth value is defined as follows: \(\mathcal{P}\implies\mathcal{Q}\) is false when \(\mathcal{P}\) is true and \(\mathcal{Q}\) is false, and true otherwise.
Logical equivalence (if and only if).
Given propositions \(\mathcal{P}\) and \(\mathcal{Q}\text{,}\) the proposition “\(\mathcal{P}\) if and only if \(\mathcal{Q}\)”, denoted \(\mathcal{P}\iff\mathcal{Q}\) in logical notation, is called an equivalence, and its truth value is defined as follows: \(\mathcal{P}\iff \mathcal{Q}\) is true when \(\mathcal{P}\) and \(\mathcal{Q}\) have the same truth value, and false otherwise. We say \(\mathcal{P}\) and \(\mathcal{Q}\) are logically equivalent when \(\mathcal{P}\iff \mathcal{Q}\) is true.

Remark 0.2.2.

A truth table of a compound proposition \(\mathcal{P}\) is a concise way of displaying how the truth value of \(\mathcal{P}\) depends on the truth values of its component propositions. It contains one row for each possible truth assignment of the component propositions. As illustration, we give the truth tables for the logical operators defined above:

\begin{align*} \amp\begin{array}{c||c}\mathcal{P}\amp\neg\mathcal{P} \\ \hline T\amp F\\F\amp T\end{array} \amp \amp \begin{array}{c|c||c}\mathcal{P}\amp\mathcal{Q}\amp\mathcal{P}\land\mathcal{Q} \\ \hline T\amp T\amp T\\T\amp F\amp F\\ F\amp T\amp F\\ F\amp F\amp F\end{array} \amp \amp \begin{array}{c|c||c}\mathcal{P}\amp\mathcal{Q}\amp\mathcal{P}\lor\mathcal{Q} \\ \hline T\amp T\amp T\\T\amp F\amp T\\ F\amp T\amp T\\ F\amp F\amp F\end{array}\\ \amp \begin{array}{c|c||c}\mathcal{P}\amp\mathcal{Q}\amp\mathcal{P}\implies\mathcal{Q} \\ \hline T\amp T\amp T\\T\amp F\amp F\\ F\amp T\amp T\\ F\amp F\amp T\end{array} \amp \amp \begin{array}{c|c||c}\mathcal{P}\amp\mathcal{Q}\amp\mathcal{P}\iff\mathcal{Q} \\ \hline T\amp T\amp T\\T\amp F\amp F\\ F\amp T\amp F\\ F\amp F\amp T\end{array} \end{align*}

Example 0.2.3.

Use a truth table to find all truth value assignments of \(\mathcal{P}\) and \(\mathcal{Q}\) making the compound proposition

\begin{equation*} \neg\mathcal{P}\implies (\mathcal{Q}\implies P) \end{equation*}

false.

Solution.

We construct a truth table with columns for \(\mathcal{P}\text{,}\) \(\mathcal{Q}\text{,}\) \(\neg\mathcal{P}\text{,}\) \(\mathcal{Q\implies P}\text{,}\) and \(\neg\mathcal{P}\implies (\mathcal{Q}\implies P)\text{:}\)

\begin{equation*} \begin{array}{c|c|c|c||c}\mathcal{P}\amp\mathcal{Q}\amp\neg\mathcal{P}\amp \mathcal{Q}\implies \mathcal{P}\amp \neg\mathcal{P}\implies(\mathcal{Q}\implies \mathcal{P}) \\ \hline T\amp T\amp F\amp T\amp T\\T\amp F\amp F\amp T\amp T\\ F\amp T\amp T\amp F\amp F\\ F\amp F\amp T\amp T\amp T\end{array}\text{.} \end{equation*}

We conclude that \(\neg\mathcal{P}\implies (\mathcal{Q}\implies P)\) is false exactly when \(\mathcal{P}\) is false and \(\mathcal{Q}\) is true. (It follows that \(\neg\mathcal{P}\implies (\mathcal{Q}\implies P)\) is equivalent to \(Q\implies P\text{.}\) )

Remark 0.2.4.

Our definitions of the logical operators above are chosen to agree with their usage in a very particular type of discourse: namely, mathematical discourse. They do not always agree with their use in natural language: hence the modifier “logical” in their titles.

For example, disjunctions in natural language of the form “\(\mathcal{P}\) or \(\mathcal{Q}\)” are often understood to be true when \(\mathcal{P}\) is true or \(\mathcal{Q}\) is true, but not both. This notion of disjunction is called the exclusive or in logic, in contrast to the standard logical or.

Similarly, according to our definition, the implication “If the President of the US is a dog, then the Vice President of the US is a cat” is true, since the proposition “The President of the US is a dog” is false. (In logic we say the implication is vacuously true in this case.) However, working outside of our logical definitions of truth value, we may have been inclined to treat this implication as false, since both “The President of the US is a dog” and “The Vice President of the US is a cat” are false.

Subsection Predicate logic

Propositions like “All humans are mortal” and “Every positive real number has a square-root” are modeled in logic in the form “For all \(x\text{,}\) \(P(x)\)” and “For all \(r\text{,}\) there exists an \(s\) such that \(Q(r,s)\)”, where \(P(x)\) stands for the phrase “\(x\) is mortal” and \(Q(r,s)\) stands for the phrase “\(s\) is a square-root of \(r\)”. Observe that \(P(x)\) and \(Q(r,s)\) on their own are not propositions; there is no truth value to “\(x\) is mortal” or “\(s\) is a square-root of \(r\)”. Instead, we think of \(P(x)\) and \(Q(r,s)\) as functions which return propositions when evaluated at a specific choice for \(x\text{,}\) or for \(r\) and \(s\text{.}\) For example, evaluating \(P(x)\) at \(x=\text{Aaron Greicius}\) yields the proposition “Aaron Greicius is mortal”, which happens to be true at the time of writing. Similarly evaluating \(Q(r,s)\) at \(r=2, s=11\) yields the proposition “\(11\) is a square-root of 2”, which happens to be false. In logic \(P(x)\) and \(Q(r,s)\) are called propositional functions (also called predicates): functions whose outputs are propositions.

The propositions “For all \(x\text{,}\) \(P(x)\)” and “For all \(r\text{,}\) there exists an \(s\) such that \(Q(r,s)\)” are obtained from \(P(x)\) and \(Q(r,s)\) by bounding them with a series of quantifiers (e.g., “for all \(x\)”, “there exists an \(s\)”). The definition below allows us to assign truth values to such propositions.

Definition 0.2.5.

Let \(D\) be a set, and let \(P\) be a propositional function that assigns to all elements \(d\in D\) the proposition \(P(d)\text{.}\) The set \(D\) is called the domain of discourse of \(P\text{.}\)

Universal quantifier.
The proposition “For all \(x\) in \(D\text{,}\) \(P(x)\)”, denoted \(\forall x P(x)\) in logical notation, is called a universal quantification, and its truth value is defined as follows: \(\forall x P(x)\) is true if for all elements \(d\) of \(D\text{,}\) the proposition \(P(d)\) is true; it is false if there is some \(d\in D\) such that \(P(d)\) is false.
Existential quantifier.
The proposition “There exists an \(x\) in \(D\) such that \(P(x)\)”, denoted \(\exists x P(x)\) in logical notation, is called an existential quantification, and its truth value is defined as follows: \(\exists x P(x)\) is true if there is some element \(d\) of \(D\) for which the proposition \(P(d)\) is true; it is false if \(P(d)\) is false for all \(d\in D\text{.}\)

Remark 0.2.6. Truth depends on domain of discourse.

Just as a function is not properly defined before its domain is specified, we do not have a well-defined propositional function, nor well-defined truth values of propositions built from this propositional function, until its domain of discourse is given.

For example, let \(P(x)\) be “x>0”. If we declare \(D=(0,\infty)\text{,}\) then the proposition \(\forall x P(x)\) is true, since by definition every \(d\in (0,\infty)\) is positive. On the other hand, if we declare \(D=\R\text{,}\) the proposition \(\forall x P(x)\) is false since not all elements of \(\R\) are positive: indeed, \(-1\) is negative, making \(P(-1)\) false.

Because of the important role played by the domain of discourse \(D\text{,}\) we sometimes include it in our quantifier expressions: e.g., \(\forall x\in D P(x)\text{,}\) \(\exists x\in D P(x)\text{.}\) Using this convention allows us to see more immediately that \(\forall\, x\in (0,\infty)\, P(x)\) is true and \(\forall\, x\in\mathbb{R}\, P(x)\) is false.

Example 0.2.7. Modeling “Every positive number has a square-root”.

Model the sentence “Every positive real number has a square-root” in the form \(\forall x P(x)\text{,}\) where \(P\) is a propositional function with domain of discourse \(D=\R\text{.}\) Determine the truth value of \(\forall x\, P(x)\) using Definition 0.2.5.

Solution.

Fix our domain of discourse to be \(D=\R\text{.}\) For any \(r,s\in \R\text{,}\) let \(Q(r,s)\) be the proposition that \(s\) is a square-root of \(r\text{.}\) Define \(P(x)\) to be the propositional function

\begin{equation*} x>0 \implies \exists y\, Q(x,y)\text{.} \end{equation*}

Thus for any \(r\in\R\text{,}\) \(P(r)\) is the proposition that if \(r\) is positive, then \(r\) has a square-root. It follows that \(\forall x\in\R\, P(x)\) is the proposition that for all real numbers \(x\text{,}\) if \(x\) is positive, then \(x\) has a square-root. This is clearly equivalent to the proposition that every positive real number has a square-root, as desired.

Lastly, we use Definition 0.2.5 to show \(\forall x\in \R\, P(x)\) is true. Take any \(r\in \R\text{.}\) The real number \(r\) is either positive or not positive. If \(r\) is not positive, then \(r>0\) is false and hence \(P(r)\text{,}\) which is the implication \(r>0\implies \exists y\, Q(r,y)\text{,}\) is true vacuously. If \(r\) is positive, then \(r>0\) is true, and \(\exists y\, Q(r,y)\) is true, since \(r\) has a square-root in this case: namely, \(\sqrt{r}\text{.}\) But if \(r>0\) is true and \(\exists y\, Q(r,y)\) is true, then the implication \(r>0\implies \exists y\, Q(r,y)\) is true. We have proved \(P(r)\) is true for all \(r\in \R\text{.}\) Thus \(\forall x\in\R\, P(x)\) is true.

Warning 0.2.8. Order of quantifiers matters.

As Example 0.2.7 illustrates, we can take a propositional function \(Q(x,y)\) in two variables and quantify one of the two variables to obtain a propositional function in one variable: e.g., \(P(x)=\exists y\, Q(x,y)\) or \(R(y)=\forall x\, Q(x,y)\text{.}\) Proceeding in this manner we engender propositions involving sequences of quantifiers. Mark well that the order of the quantifiers in such sequences is important!

For example, letting \(Q(x,y)\) be “\(y\) is a square-root of \(y\)” with domain of discourse \(D=(0,\infty)\text{.}\) The proposition \(\forall x\in\R\, \exists y\in\R\, Q(x,y)\) says that every positive real number has a positive square-root (true); the proposition \(\exists y\in\R\, \forall x\in\R\, Q(x,y)\) says that there is a positive real number that is the square-root of all real numbers (false).

In general to “unpack” a sequence of quantifiers we start from the leftmost quantifier and proceed to the right.

Remark 0.2.9. Negating quantifiers.

Let \(P(x)\) be a propositional function with domain of discourse \(D\text{.}\) According to Definition 0.2.5 a universal quantification \(\forall x\, P(x)\) is false if it is not the case that \(P(d)\) is true for all for all \(d\in D\text{;}\) that is, if there is some \(d\in D\) such that \(P(d)\) is false. Letting \(\neg P(x)\) be the propositional function defined as \(\neg P(d)\) for all \(d\in D\text{,}\) we see that \(\forall x\, P(x) \) is false if and only if \(\exists x\, \neg P(x)\) is true. This proves the equivalence

\begin{equation*} \neg\forall x\, P(x)\iff \exists x\, \neg P(x)\text{.} \end{equation*}

Similarly, we have

\begin{equation*} \neg\exists x\, P(x)\iff \forall x\, \neg P(x)\text{.} \end{equation*}

These equivalences can be understood as rules of negating quantifier statements. They can be summarized as follow: “swap quantifiers and negate the predicate.”

The example below taken from calculus nicely illustrates how to negate a proposition that involves a sequence of quantifiers.

Example 0.2.10. The limit does not exist.

Let \(f(x)\) be a function with domain \(\R\text{,}\) and let \(c\in \R\) be a point of this domain. By definition, the proposition that \(\lim\limits_{x\to c}f(x)\) exists is equivalent to the following proposition:

\begin{equation} \exists L\in\R\, \forall \epsilon \gt 0\, \exists \delta \gt0\, \forall x\in\mathbb{R}\ (\val{x-c}\lt\delta\implies \val{f(x)-L}\lt\epsilon)\text{.}\tag{0.2.1} \end{equation}

(We made a number of shortcuts in our logical notation above (e.g. \(\forall \epsilon\gt 0\text{,}\) \(\exists\delta\gt 0\)) in order to simplify the expression somewhat; the intended meaning should still be clear. )

Use the negation rules described in Negating quantifiers to derive a similar proposition equivalent to the statement that \(\lim\limits_{x\to c}f(x)\) do not exist.

Solution.

Let \(\mathcal{P}\) be the proposition in (0.2.1). Using the negation rules in series, we derive the chain of equivalences below. We’ve added parentheses to emphasize what is being negated at each step. Note how a quantifiers are “swapped” each time we pass the negation to the right.

\begin{align*} \neg\mathcal{P}\amp\iff \forall L\in\R\, \neg\left(\forall \epsilon \gt 0\, \exists \delta \gt0\, \forall x\in\mathbb{R}\ (\val{x-c}\lt\delta\implies \val{f(x)-L}\lt\epsilon) \right)\\ \amp\iff \forall L\in\R\, \exists \epsilon \gt 0\, \neg\left( \exists \delta \gt0\, \forall x\in\mathbb{R}\ (\val{x-c}\lt\delta\implies \val{f(x)-L}\lt\epsilon) \right)\\ \amp\iff \forall L\in\R\, \exists \epsilon \gt 0\, \forall \delta \gt0\, \neg\left( \forall x\in\mathbb{R}\ (\val{x-c}\lt\delta\implies \val{f(x)-L}\lt\epsilon) \right)\\ \amp\iff \forall L\in\R\, \exists \epsilon \gt 0\, \forall \delta \gt0\, \exists x\in\mathbb{R}\ \neg (\val{x-c}\lt\delta\implies \val{f(x)-L}\lt\epsilon)\\ \amp\iff \forall L\in\R\, \exists \epsilon \gt 0\, \forall \delta \gt0\, \exists x\in\mathbb{R}\ (\val{x-c}\lt\delta \text{ and } \val{f(x)-L}\not\lt\epsilon)\text{.} \end{align*}

(The last link in our chain uses the fact that \(\neg(\mathcal{Q}\implies\mathcal{R})\) is equivalent to \(\mathcal{Q}\land\neg\mathcal{R}\text{,}\) as a truth table easily shows.) Translating back into English, we conclude that the limit not existing (\(\neg\mathcal{P}\)) is equivalent to the following: for every \(L\in \mathbb{R}\) there is an \(\epsilon\gt 0\) such that for all \(\delta\gt 0\) there exists an \(x\in\mathbb{R}\) satisfying \(\val{x-c}\lt \delta\) and \(\val{f(x)-L}\not\gt\epsilon\text{.}\) Quite a mouthful!

Prev Top Next