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 \(\top\) and \(\bot\).

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 \land Q\) is defined by the following truth table: \begin{equation} \begin{array}{cc|c} P & Q & P \land Q\\\hline \top & \top & \top\\ \top & \bot & \bot\\ \bot & \top & \bot\\ \bot & \bot & \bot\\ \hline \end{array} \end{equation}

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

(Disjunction, logical "or"): Let \(P\) and \(Q\) be propositions. Their conjunction \(P \land Q\) is defined by the following truth table: \begin{equation} \begin{array}{cc|c} P & Q & P \lor Q\\\hline \top & \top & \top\\ \top & \bot & \top\\ \bot & \top & \top\\ \bot & \bot & \bot\\ \hline \end{array} \end{equation}

We "interpret" the conjunction as logical "or," that is, if \(P\) or \(Q\) is true, then \(P\lor Q\) is true. 

(Negation, logical "not"): Let \(P\) be a proposition. Its negation is defined by the following truth table: \begin{equation} \begin{array}{c|c} P & \lnot P\\\hline \top & \bot \\ \bot & \top \\\hline \end{array} \end{equation}

We interpret the negation as logical "not," that is, if \(P\) is true (false), then \(\lnot P\) is false (true).

(Implication, "if...then..."): Let \(P\) and \(Q\) be propositions. The implication \(P \implies Q\) is defined by the following truth table: \begin{equation} \begin{array}{cc|c} P & Q & P \implies Q\\\hline \top & \top & \top \\ \top & \bot & \bot \\ \bot & \top & \top\\ \bot & \bot & \top \\\hline \end{array} \end{equation}

We interpret the implication \(P\implies Q\) as "if \(P\) then \(Q\)" or "\(P\) implies "\(Q\)." Note in particular that an implication is true if the left-hand side of \(\implies\) is false (by the way, the left- and right-hand sides of \(\implies\) 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 \(\lnot (P \land Q)\) and \((\lnot P)\lor (\lnot 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 \(\lnot(P \land Q)\): \begin{equation} \begin{array}{cc|c|c} P & Q & P \land Q & \lnot (P\land Q)\\\hline \top & \top & \top & \bot\\ \top & \bot & \bot & \top\\ \bot & \top & \bot & \top\\ \bot & \bot & \bot & \top\\\hline \end{array} \end{equation} It is often helpful to write down the smaller components of a complicated logical expression, such as \(P \land Q\), which is a "smaller" component of \(\lnot (P \land Q)\). Next, \((\lnot P)\lor (\lnot Q)\): \begin{equation} \begin{array}{cc|cc|c} P & Q & \lnot P & \lnot Q & (\lnot P) \lor (\lnot Q)\\\hline \top & \top & \bot & \bot & \bot\\ \top & \bot & \bot & \top & \top\\ \bot & \top & \top & \bot & \top\\ \bot & \bot & \top & \top & \top\\\hline \end{array} \end{equation} By comparing the two tables, we can see that \(\lnot (P \land Q)\) and \((\lnot P)\lor (\lnot 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{eqnarray} \lnot(P \lor Q) &\equiv & (\lnot P) \land (\lnot Q),\\ \lnot(P \land Q) &\equiv & (\lnot P) \lor (\lnot Q). \end{eqnarray}\]
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) = \top \), \( P(3.1415) = \bot \), \( P(\text{``elephant''}) = \bot, \) etc.

Example: Let \(P(x,y)\) be the predicate that "\(x < y\)" (i.e., \(x\) is less than \(y\)). Then \(P(1, 2)=\top, P(5, -1) = \bot\), 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 

\[\forall x\in \mathbb{Z} ~ \exists y \in \mathbb{Z} (x < y).\]

The symbol "\(\forall\)" is called the universal quantifier and is read as "for all..." or "for any..." or "for every...." 

The symbol "\(\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

\[\exists y \in \mathbb{Z} ~ \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:
\[\lnot (x < y) \equiv x \geq 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 \(\geq\).

Next, note the following equivalence:

\[\lnot (\forall x \in A (P(x))) \equiv \exists x\in A (\lnot 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:

\[\lnot (\exists x\in A (P(x))) \equiv \forall x\in A (\lnot 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{eqnarray} \lnot(\exists y\in \mathbb{Z} ~ \forall x\in\mathbb{Z} ~ (x < y)) &\equiv & \forall y \in\mathbb{Z}\lnot(\forall x\in\mathbb{Z} ~ (x < y))\\ &\equiv&\forall y \in\mathbb{Z} ~\exists x\in\mathbb{Z} ~ (\lnot(x < y))\\ &\equiv&\forall y \in\mathbb{Z} ~\exists x\in\mathbb{Z} ~ (x \geq y). \end{eqnarray}\]

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

Propositions about members of the empty set.

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

\[\forall x \in \emptyset ~ (\text{$x$ is a fish})\]

is true. So is

\[\forall x \in \emptyset ~ (\text{$x$ is not a fish}).\]

This is because the proposition that \(x \in \emptyset\) is always false.


Comments

Post a Comment

Popular posts from this blog

Open sets and closed sets in \(\mathbb{R}^n\)

-
Image
Open sets In \(\mathbb{R}\), we have the notion of an open interval such as \((a, b) = \{x \in \mathbb{R} | a < x < b\}\). We want to extend this idea to apply to \(\mathbb{R}^n\). We also introduce the notions of bounded sets and closed sets in \(\mathbb{R}^n\). Recall that the \(\varepsilon\)-neighbor of a point \(x\in\mathbb{R}^n\) is defined as \(N_{\varepsilon}(x) = \{y \in \mathbb{R}^n | d(x, y) < \varepsilon \}\) where \(d(x,y)\) is the distance between \(x\) and \(y\). Definition (Open set) A subset \(U\) of \(\mathbb{R}^n\) is said to be an  open set  if the following holds: \[\forall x \in U ~ \exists \delta > 0 ~ (N_{\delta}(x) \subset U).\tag{Eq:OpenSet}\] That is, for every point in an open set \(U\), we can always find an open ball centered at that point, that is included in \(U\). See the following figure. Perhaps, it is instructive to see what is  not  an open set. Negating (Eq:OpenSet), we have \[\exists x \in U ~ \forall \delta > 0 ~ (N_{\delta}(x) \not
Read more

Euclidean spaces

-
Image
We would like to study multivariate functions (i.e., functions of many variables), continuous multivariate functions in particular. To define continuity, we need a measure of "closeness" between points. One measure of closeness is the Euclidean distance. The set \(\mathbb{R}^n\) (with \(n \in \mathbb{N}\)) with the Euclidean distance function is called a Euclidean space. This is the space where our functions of interest live. The real line is a geometric representation of \(\mathbb{R}\), the set of all real numbers. That is, each \(a \in \mathbb{R}\) is represented as the point \(a\) on the real line. The coordinate plane , or the \(x\)-\(y\) plane , is a geometric representation of \(\mathbb{R}^2\), the set of all pairs of real numbers. Each pair of real numbers \((a, b)\) is visualized as the point \((a, b)\) in the plane. Remark . Recall that \(\mathbb{R}^2 = \mathbb{R}\times\mathbb{R} = \{(x, y) | x, y \in \mathbb{R}\}\) is the Cartesian product of \(\mathbb{R}\) with i
Read more

Newton's method

-
Image
Newton's method (the Newton-Raphson method) is a very powerful numerical method for solving nonlinear equations.  Suppose we'd like to solve a non-linear equation \(f(x) = 0\), where \(f(x)\) is a (twice) differentiable non-linear function. Newton's method generates a sequence of numbers \(c_1, c_2, c_3, \cdots\) that converges to a solution of the equation. That is, if \(\alpha\) is a solution (i.e., \(f(\alpha) = 0\)) then,  \[\lim_{n\to\infty}c_n = \alpha,\] and this sequence \(\{c_n\}\) is generated by a series of linear approximations of the function \(f(x)\). Theorem (Newton's method) Let \(f(x)\) be a function that is twice differentiable on an open interval \(I\) that contains the closed interval \([a, b]\) (i.e., \([a,b]\subset I\)) and satisfy the following conditions: \(f(a) < 0\) and \(f(b) > 0\); For all \(x\in [a, b]\), \(f'(x) > 0\) and \(f''(x) > 0\). Let us define the sequence \(\{c_n\}\) by \[ \begin{eqnarray} c_1 &
Read more