Formal logic

Formal logic is a set of rules for making deductions that seem self evident. Syllogisms like the following occur in every day conversation.

This is facilitated by representing objects and relationships symbolically. For example we might use

for the set of humans,

for the set of mortal creatures and

for Socrates. We use the symbolic expression ` $x \in y$ ' to indicate that object

is a member of set

. Thus we represent `Socrates is a human' with $s \in h$ . We 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$ . This reads that every

that has the property of being human must also have the property of being mortal. Then we restate the syllogism as follows. $\ \newline \forall x \hspace{.1in} x \in h \rightarrow x \in m\newline s \in h \newline $therefore$\newline s \in m \newline$

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 3.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}$ .

implies

requires that either both

and

are true or

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 3.2. If a logical expression contains quantifiers than we need to evaluate a logical relationship over a range of values to determine the truth of the expression. If the range is infinite then there is no general way to evaluate the expression. We can use induction^3.2to prove that some statements hold for all integers but for that we need to go beyond logic to mathematics.

Table 3.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 3.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 we can evaluate $\overline{B}$ and $D \wedge E$ . At subsequent levels the part of the expression evaluated at higher levels in in smaller type.