# A very brief introduction to logic

Imagine you are walking to a friend’s house. When you reach the right street, you realise you are not sure about the house number; you know that it is either 23 or 24, but can’t remember which one. You also remember that the house is on the left side of the road. Fortunately, you notice that the houses to the right of you all have even numbers, and the ones to the left correspondingly odd. Hence, provided that what you remember is correct, you have enough information to ring the right doorbell without having to guess. Let us break down the possible reasoning going on here:

(1) The friend’s house number is either 23 or 24.
(2) The friend’s house is on the left.
(3) All the houses on the left have an odd number.
(4) The friend’s house has an odd number. (By (3) and (2))
(5) 24 is not odd.
(6) The friend’s house is not 24. (By (4) and (5))
(7) The friend’s house is 23. (By (1) and (6))

What is remarkable about this reasoning is that if (1), (2), (3) and (5) are all true, then so must be (7), that is, the reasoning is truth-preserving. There is, of course, nothing special about houses and numbers, we could equally replace all the words by something which doesn’t even make much sense, for instance:

(1) My foot is either pink or ultramarine.
(2) My foot is stolen.
(3) All stolen feet are liked by the Holy Frog.
(4) My foot is liked by the Holy Frog. (By (3) and (2))
(5) No ultramarine foot is liked by the Holy Frog.
(6) My foot is not ultramarine. (By (4) and (5))
(7) My foot is pink. (By (1) and (6))

Formally, this is still a perfectly valid piece of reasoning. This, of course, by no means implies that the conclusion ‘My foot is pink’ is true; in this case at least (1) and (2) are certainly false, so the conclusion need not to be true. If we learn anything at all from this exercise, it is the following crucial observation; what makes the reasoning correct is its form rather that the content. This is the basic description of philosophical logic, it tries to capture the correct forms of reasoning, by correct we mean truth-preserving here. Formalisation of these rules for reasoning leads to the so called first-order logic.

While the field of mathematical logic is not limited to the first-order logic1, it is the most common one to consider in mathematics, philosophy and computer science. The reason for this is simple; first-order logic captures the reasoning we are familiar with in our everyday life. This kind of logic is intuitive and understandable for us; we are, in fact, as illustrated by the example above, constantly using this kind of inference rules without putting in much effort or paying attention to it. This is the reason why a person who starts learning programming doesn’t need to learn the ‘rules of logic’ first, they are more or less hard-wired in our interaction with the environment.

First-order logic consists of terms, sentential formulas, logical operators and quantifiers. In addition to these, one has to define a well-formed sentence and the inference rules2.  The terms can be thought of as elements of a set denoted by small letters $a, b, c, ...$; a term is made into a sentential formula by specifying a property it has, that is, the set it belongs to, these are denoted by capital letters. For example, $Hx$ means ‘$x$ has the property $H$‘. The logical operators are $\neg$ (not), $\land$ (and), $\lor$ (or) and $\Rightarrow$ (implication). Finally, the quantifiers of first-order logic are $\forall$ (for all) and $\exists$ (there is). Using this formal language, we can now express symbolically the argument given in the example above:

(1) $Ty \lor Fy$
(2) $Ly$
(3) $\forall x[Lx\Rightarrow Ox]$
(4) $Oy$
(5) $\forall x[Fx\Rightarrow \neg Ox]$
(6) $\neg Fy$
(7) $Ty$

Where we have denoted: $y$ = ‘the friend’s house’, $T$ = ‘has number 23’, $F$ = ‘has number 24’, $L$ = ‘house is on the left’, $O$ = ‘has an odd number’. Thus for example, (3) reads as ‘All houses on the left have an odd number’. To infer (4) from (3) and (2) we first use the inference rule $\forall x P(x) \rightarrow P(y)$ to get $Ly\Rightarrow Oy$, which together with (2) and the inference rule $A, A\Rightarrow B \rightarrow B$ gives (4). We can now explicitly see that it doesn’t matter what the letters above stand for, the given argument is true because we can justify each step by the inference rules of first-order logic.

The metaphysical status of first-order logic is an interesting question in philosophy, it can be summarised as ‘What makes logical truths true?’ The suggested answers to this include logical realism, asserting that logic is a property of the reality and the logical truths thus tell us something meaningful about the reality itself; and logical formalism, according to which logical truths do not as such provide any new information about how things are in the world, rather, it is their form which makes them necessarily true.3 While the latter view may sound appealing in the light of the previous example, as we are about to see, there is something about logic which seems to carry along some of our assumptions about the physical reality.

Since the inference rules of first-order logic are truth-preserving, if we start with a set of true statements about a physical system, everything we infer from this set of statements using those inference rules will also be true about the physical system in question. Or at least if this is not the case, we have a serious problem with either our physical understanding of the system, or with our logic. To illustrate this, consider the following example. We are told that a cyclist is somewhere on a road, and has a speed of 30 km/h. It is immediately obvious to us that this is equivalent to: ‘either the cyclist is on the first half of the road with the speed of 30 km/h, or the cyclist is on the second half of the road with the speed of 30 km/h’. This rephrasing is in fact so trivial that you could (rightfully) complain that this is pointless and I am just doing it to overcomplicate things. It does, however, illustrate a more general property of classical logic called distributivity. Using the formal notation defined above, distributivity can be expressed as:

$\displaystyle x \land (y \lor z) = (x \land y) \lor (x \land z)$

What makes this obvious property of classical logic extremely fascinating is that it no longer holds in general for quantum mechanical systems.

1One can indeed come up with an entire zoo of exotic logics in mathematics, the Wikipedia entry has a good overview of these, https://en.wikipedia.org/wiki/Mathematical_logic
2For a full list of properties defining first-order logic, see http://mathworld.wolfram.com/First-OrderLogic.html