Informal introduction to formal logic

 In mathematics, we must prove (almost) everything and the proofs must be done logically and rigorously. Therefore, we need some understanding of basic logic. Here, I will informally explain some rudimentary formal logic.

Definitions

(Proposition): A proposition is a statement that is either true or false. "True" and "false" are called the truth values, and are often denoted $\mathrm{\top }$ and $\mathrm{\perp }$.

Here is an example. "Dr. Akira teaches at UBD." is a statement that is either true or false (we understand the existence of Dr. Akira and UBD), hence a proposition.

The following statement is also a proposition, although we don't know if it's true or false (yet):

Any even number greater than or equal to 4 is equal to a sum of two primes.

See also: Goldbach's conjecture 

Next, we define several operations on propositions. Note that propositions combined with these operations are again propositions. 

(Conjunction, logical "and"): Let $P$ and $Q$ be propositions. Their conjunction $P\wedge Q$ is defined by the following truth table: $$\underline{\begin{array}{ccc}P& Q& P\wedge Q\\ \mathrm{\top }& \mathrm{\top }& \mathrm{\top }\\ \mathrm{\top }& \mathrm{\perp }& \mathrm{\perp }\\ \mathrm{\perp }& \mathrm{\top }& \mathrm{\perp }\\ \mathrm{\perp }& \mathrm{\perp }& \mathrm{\perp }\end{array}}$$

We "interpret" the conjunction as logical "and," that is, if $P$ and $Q$ are both true, then $P\wedge Q$ is true. 

(Disjunction, logical "or"): Let $P$ and $Q$ be propositions. Their conjunction $P\wedge Q$ is defined by the following truth table: $$\underline{\begin{array}{ccc}P& Q& P\vee Q\\ \mathrm{\top }& \mathrm{\top }& \mathrm{\top }\\ \mathrm{\top }& \mathrm{\perp }& \mathrm{\top }\\ \mathrm{\perp }& \mathrm{\top }& \mathrm{\top }\\ \mathrm{\perp }& \mathrm{\perp }& \mathrm{\perp }\end{array}}$$

We "interpret" the conjunction as logical "or," that is, if $P$ or $Q$ is true, then $P\vee Q$ is true. 

(Negation, logical "not"): Let $P$ be a proposition. Its negation is defined by the following truth table: $$\underline{\begin{array}{cc}P& \mathrm{\neg }P\\ \mathrm{\top }& \mathrm{\perp }\\ \mathrm{\perp }& \mathrm{\top }\end{array}}$$

We interpret the negation as logical "not," that is, if $P$ is true (false), then $\mathrm{\neg }P$ is false (true).

(Implication, "if...then..."): Let $P$ and $Q$ be propositions. The implication $P⟹Q$ is defined by the following truth table: $$\underline{\begin{array}{ccc}P& Q& P⟹Q\\ \mathrm{\top }& \mathrm{\top }& \mathrm{\top }\\ \mathrm{\top }& \mathrm{\perp }& \mathrm{\perp }\\ \mathrm{\perp }& \mathrm{\top }& \mathrm{\top }\\ \mathrm{\perp }& \mathrm{\perp }& \mathrm{\top }\end{array}}$$

We interpret the implication $P⟹Q$ as "if $P$ then $Q$" or "$P$ implies "$Q$." Note in particular that an implication is true if the left-hand side of $⟹$ is false (by the way, the left- and right-hand sides of $⟹$ are called a premise and a conclusion, respectively).

Examples

We can connect propositions with the above operations to make new propositions.

Let us show that $\mathrm{\neg }(P\wedge Q)$ and $(\mathrm{\neg }P)\vee (\mathrm{\neg }Q)$ are equivalent. We say that two propositions are equivalent if their truth tables are identical. First, let's write down the truth table for $\mathrm{\neg }(P\wedge Q)$: $$\underline{\begin{array}{cccc}P& Q& P\wedge Q& \mathrm{\neg }(P\wedge Q)\\ \mathrm{\top }& \mathrm{\top }& \mathrm{\top }& \mathrm{\perp }\\ \mathrm{\top }& \mathrm{\perp }& \mathrm{\perp }& \mathrm{\top }\\ \mathrm{\perp }& \mathrm{\top }& \mathrm{\perp }& \mathrm{\top }\\ \mathrm{\perp }& \mathrm{\perp }& \mathrm{\perp }& \mathrm{\top }\end{array}}$$ It is often helpful to write down the smaller components of a complicated logical expression, such as $P\wedge Q$, which is a "smaller" component of $\mathrm{\neg }(P\wedge Q)$. Next, $(\mathrm{\neg }P)\vee (\mathrm{\neg }Q)$: $$\underline{\begin{array}{ccccc}P& Q& \mathrm{\neg }P& \mathrm{\neg }Q& (\mathrm{\neg }P)\vee (\mathrm{\neg }Q)\\ \mathrm{\top }& \mathrm{\top }& \mathrm{\perp }& \mathrm{\perp }& \mathrm{\perp }\\ \mathrm{\top }& \mathrm{\perp }& \mathrm{\perp }& \mathrm{\top }& \mathrm{\top }\\ \mathrm{\perp }& \mathrm{\top }& \mathrm{\top }& \mathrm{\perp }& \mathrm{\top }\\ \mathrm{\perp }& \mathrm{\perp }& \mathrm{\top }& \mathrm{\top }& \mathrm{\top }\end{array}}$$ By comparing the two tables, we can see that $\mathrm{\neg }(P\wedge Q)$ and $(\mathrm{\neg }P)\vee (\mathrm{\neg }Q)$ are indeed equivalent.

If two propositions $P$ and $Q$ are equivalent, we write

$$P\equiv Q$$

to denote their equivalence.

Theorem (De Morgan's laws)

Let $P$ and $Q$ be any propositions.

We have $$\begin{array}{rcl}\mathrm{\neg }(P\vee Q)& \equiv & (\mathrm{\neg }P)\wedge (\mathrm{\neg }Q),\\ \mathrm{\neg }(P\wedge Q)& \equiv & (\mathrm{\neg }P)\vee (\mathrm{\neg }Q).\end{array}$$

Proof. Exercise. (See above.) ■

Sometimes, we want propositions to depend on some inputs.

(Predicate) A proposition that depends on variables is called a predicate.

Example: Let $P(x)$ be the predicate that "$x$ is an even integer." Then, $P(2)=\mathrm{\top }$, $P(3.1415)=\mathrm{\perp }$, $P(\text{``elephant''})=\mathrm{\perp },$ etc.

Example: Let $P(x,y)$ be the predicate that "$x<y$" (i.e., $x$ is less than $y$). Then $P(1,2)=\mathrm{\top },P(5,-1)=\mathrm{\perp }$, etc.

Quantifiers

Next, consider the following "proposition":

For all $x\in \mathbb{Z}$, there exists $y\in \mathbb{Z}$ such that $x<y$.

(This statement means that, for any integer $x$, there is (always) another integer $y$ that is greater than $x$. This is clearly true!)

Here we have quantifiers such as "for all" or "there exists" that restrict the behavour of the variables $x$ and $y$ in the predicate "$x<y$." We introduce the symbols for these quantifiers. The above proposition can be expressed as 

$$\mathrm{\forall }x\in \mathbb{Z}\mathrm{\exists }y\in \mathbb{Z}(x<y).$$

The symbol "$\mathrm{\forall }$" is called the universal quantifier and is read as "for all..." or "for any..." or "for every...." 

The symbol "$\mathrm{\exists }$" is called the existential quantifier and is read as "there exist(s)..." or "for some..."

The order of appearance of quantifiers matters. That is, the above proposition is different from

$$\mathrm{\exists }y\in \mathbb{Z}\mathrm{\forall }x\in \mathbb{Z}(x<y).$$

The latter reads as "There exists an integer $y$ such that, for every integer $x$, $x<y$ holds." But this means that there exists the greatest integer $y$ (that is greater than any integers); this is clearly false.

Negation involving quantifiers

Note the following equivalence:

$$\mathrm{\neg }(x<y)\equiv x\ge y.$$

This means that "Not that $x$ is less than $y$" is equivalent to "$x$ is greater than or equal to $y$." This equivalence is based on the mathematical meaning of $<$ and $\ge$.

Next, note the following equivalence:

$$\mathrm{\neg }(\mathrm{\forall }x\in A(P(x)))\equiv \mathrm{\exists }x\in A(\mathrm{\neg }P(x)).$$

This means that, if "$P(x)$ holds for all $x\in A$" does not hold, then there exists an $x\in A$ such that $P(x)$ does not hold, and vice versa.

We also have the following equivalence:

$$\mathrm{\neg }(\mathrm{\exists }x\in A(P(x)))\equiv \mathrm{\forall }x\in A(\mathrm{\neg }P(x)).$$

In plain English, if "$P(x)$ holds for some $x\in A$" does not hold, it means that "for any $x\in A$, $P(x)$ does not hold."

Example: $$\begin{array}{rcl}\mathrm{\neg }(\mathrm{\exists }y\in \mathbb{Z}\mathrm{\forall }x\in \mathbb{Z}(x<y))& \equiv & \mathrm{\forall }y\in \mathbb{Z}\mathrm{\neg }(\mathrm{\forall }x\in \mathbb{Z}(x<y))\\ & \equiv & \mathrm{\forall }y\in \mathbb{Z}\mathrm{\exists }x\in \mathbb{Z}(\mathrm{\neg }(x<y))\\ & \equiv & \mathrm{\forall }y\in \mathbb{Z}\mathrm{\exists }x\in \mathbb{Z}(x\ge y).\end{array}$$

Note that the original proposition "$\mathrm{\exists }y\in \mathbb{Z}\mathrm{\forall }x\in \mathbb{Z}(x<y)$" is false, but its negation "$\mathrm{\forall }y\in \mathbb{Z}\mathrm{\exists }x\in \mathbb{Z}(x\ge y)$" is indeed true.

Propositions about members of the empty set.

Any propositions (predicates) about members of the empty set are true. For example,

$$\mathrm{\forall }x\in \mathrm{\varnothing }(x\text{ is a fish})$$

is true. So is

$$\mathrm{\forall }x\in \mathrm{\varnothing }(x\text{ is not a fish}).$$

This is because the proposition that $x\in \mathrm{\varnothing }$ is always false.