Mountain Math Software
home consulting videos book QM FAQ contact

PDF version of this book
next up previous contents
Next: Formal mathematics Up: Mathematical structure Previous: Logically determined unsolvable problems   Contents


Formal logic

Mathematics starts with formal logic. This is a set of rules for making deductions that seem self evident. Syllogisms like the following occur in every day conversation.

All humans are mortal.
Socrates is a human.
Therefore Socrates is mortal.
Mathematical logic formalizes such deductions with rules precise enough to program a computer to decide if an argument is valid.

This is facilitated by representing objects and relationships symbolically. For example Use $h$ for the set of humans, $m$ for the set of mortal creatures and $s$ for Socrates. Use the symbolic expression `$x \in y$' to indicate that object $x$ is a member of set $y$. Thus `Socrates is a human' is represented by $s \in h$. Use the symbol $\rightarrow$ in an expression ` $a \rightarrow b$' to indicate that if statement $a$ is true than statement $b$ must be true. Use the `quantifier' $\forall$ to indicate that all objects satisfy some condition. For example all men are mortal can be written as $\forall x \hspace{.1in} x \in h \rightarrow x \in m$. $\forall$ is called a universal quantifier.

The syllogism can be formalized as follows.

\begin{displaymath}\forall x \hspace{.1in} x \in h \rightarrow x \in m\end{displaymath}


\begin{displaymath}s \in h \end{displaymath}

therefore

\begin{displaymath}s \in m \end{displaymath}

Logic assumes something cannot be both true and not true. It looks only at the truth value of a proposition. It involves simple relationships between these truth values. These can be represented by truth tables as shown in Table 5.1. The only logical operations required are the three in this figure. Others such as implication represented by `$\rightarrow$' can be constructed from these three. $A\rightarrow B$ is the same as $A\wedge B \vee \overline{A}$. $A$ implies $B$ requires that either both $A$ and $B$ are true or $A$ is false.

Determining the truth of a logical expression that contains no quantifiers (like $\forall$) is a straightforward application of simple rules. One can use a truth table to evaluate each subexpression starting with those at the root of the expression tree as shown in Table 5.2. If a logical expression contains quantifiers, the logical relationship involved must be evaluated over a range of values to determine the truth of the expression. If the range is infinite, there is no general way to evaluate the expression. Induction on the integers can solve some problems of this type.

To use induction to prove a property is true for all integers requires two steps. First prove the property holds for 0. Then prove that if the property is true for any number $n$ it is also true for $n+1$. Having established these two results the principle of induction allows one to conclude the property is true for all integers. Figure 5.1 gives an example of such a proof. The principle of induction is an axiom of mathematics that seems self evident, but cannot be derived from more basic principles. It must be assumed.


Table 5.1: Truth tables for AND, OR and NOT
AND $\wedge$
A B A $\wedge$ B
false false false
false true false
true false false
true true true
OR $\vee$
A B A $\vee$ B
false false false
false true true
true false true
true true true
NOT -
A $\overline{A}$
false true
true false


Table 5.2: Evaluating a logical expression
symbol A B C D E F
truth value true true false true true false


expression evaluation
$A \wedge \overline{B} \vee C \vee \overline{D\wedge E\wedge F}$
$\overline{B}$ $D \wedge E$
false true
$A \wedge $$\overline{B}$ $D \wedge E$ $ \wedge F$
false false
$A \wedge \overline{B}$$ \vee C$ $\overline{ D \wedge E \wedge F}$
false true
$ A \wedge B \vee C $ $\vee$ $\overline{ D \wedge E \wedge F}$
true
The order in which the logical operations are done is important. The rules for this are called precedence. First do NOT then AND finally OR. If the NOT sign extends over a subexpression, the subexpression is evaluated and the NOT operation is applied to that result. In this example at the first level evaluate $\overline{B}$ and $D \wedge E$. At subsequent levels the part of the expression evaluated at higher levels in in smaller type.

Figure 5.1: Example of proof by induction on the integers
\begin{figure}\sf \par Proof that the sum of all integers less than or equal to ... ...$\ and that completes the proof by induction.} \end{enumerate}\par\end{figure}

PDF version of this book
next up previous contents
Next: Formal mathematics Up: Mathematical structure Previous: Logically determined unsolvable problems   Contents


Mountain Math Software
home consulting videos book QM FAQ contact
Email comments to: webmaster@mtnmath.com