A Short History of Logic

Abstract

Logic is concerned with reasoning and with establishing the validity of arguments. It allows conclusions to be deduced from premises according to logical rules, and the logical argument establishes the truth of the conclusion provided that the premises are true.

14.1 Introduction

Logic is concerned with reasoning and with establishing the validity of arguments. It allows conclusions to be deduced from premises according to logical rules, and the logical argument establishes the truth of the conclusion provided that the premises are true.

The origins of logic are with the Greeks who were interested in the nature of truth. The sophists (e.g. Protagoras and Gorgias) were teachers of rhetoric, who taught their pupils techniques in winning an argument and convincing an audience. Plato explores the nature of truth in some of his dialogues, and he is critical of the position of the sophists who argue that there is no absolute truth, and that truth instead is always relative to some frame of reference. The classic sophist position is stated by Protagoras “Man is the measure of all things: of things which are, that they are, and of things which are not, that they are not.” In other words, what is true for you is true for you, and what is true for me is true for me.

Socrates had a reputation for demolishing an opponent's position, and the Socratean enquiry consisted of questions and answers in which the opponent would be led to a conclusion incompatible with his original position. The approach was similar to a reductio ad absurdum argument, although Socrates was a moral philosopher who did no theoretical work on logic.

Aristotle did important work on logic, and he developed a system of logic, syllogistic logic, that remained in use up to the nineteenth century. Syllogistic logic is a ‘term logic’, with letters used to stand for the individual terms. A syllogism consists of two premises and a conclusion, where the conclusion is a valid deduction from the two premises. Aristotle also did some early work on modal logic and was the founder of the field.

The Stoics developed an early form of propositional logic, where the assertibles (propositions) have a truth-value such that at any time they are either true or false. The assertibles may be simple or non-simple, and various connectives such as conjunctions, disjunctions and implications are used in forming more complex assertibles.

George Boole developed his symbolic logic in the mid-1800s, and it later formed the foundation for digital computing. Boole argued that logic should be considered as a separate branch of mathematics, rather than a part of philosophy. He argued that there are mathematical laws to express the operation of reasoning in the human mind, and he showed how Aristotle’s syllogistic logic could be reduced to a set of algebraic equations.

Logic plays a key role in reasoning and deduction in mathematics, but it is considered a separate discipline to mathematics. There were attempts in the early twentieth century to show that all mathematics can be derived from formal logic and that the formal system of mathematics would be complete, with all the truths of mathematics provable in the system (see Chap. 13). However, this program failed when the Austrian logician, Kurt Goedel, showed that there are truths in the formal system of arithmetic that cannot be proved within the system (i.e. first-order arithmetic is incomplete).

14.2 Syllogistic Logic

Early work on logic was done by Aristotle in the fourth century B.C. in the Organon [1]. Aristotle regarded logic as a useful tool of enquiry into any subject, and he developed syllogistic logic. This is a form of reasoning in which a conclusion is drawn from two premises, where each premise is in a subject-predicate form. A common or middle term is present in each of the two premises but not in the conclusion. For example

$$ \begin{gathered} {\text{All Greeks are mortal}}. \\ {\text{Socrates is a Greek}} \hfill \\ { - - - - - - - - - - - - - - - - - - - - - - - - - } \hfill \\ {\text{Therefore Socrates is mortal}} \hfill \\ \end{gathered} $$

The common (or middle) term in this example is ‘Greek’. It occurs in both premises but not in the conclusion. The above argument is valid, and Aristotle studied and classified the various types of syllogistic arguments to determine those that were valid or invalid. Each premise contains a subject and a predicate, and the middle term may act as a subject or a predicate. Each premise is a positive or negative affirmation, and an affirmation may be universal or particular. The universal and particular affirmations and negatives are described in the table below (Table 14.1)

Table 14.1 Types of syllogistic premises

This leads to four basic forms of syllogistic arguments (Table 14.2), where the middle is the subject of both premises; the predicate of both premises; and the subject of one premise and the predicate of the other premise.

Table 14.2 Forms of syllogistic premises

There are four types of premises (A, E, I and O), and therefore, sixteen sets of premise pairs for each of the forms above. However, only some of these premise pairs will yield a valid conclusion. Aristotle went through every possible premise pair to determine if a valid argument may be derived. The syllogistic argument above is of the form (iv) and is valid

$$ \begin{gathered} {\text{G}}{\mathbf{A}}{\text{M}} \hfill \\ {\text{S}} {\mathbf{I}}\,{\text{G}} \hfill \\ { - - - - - - - } \hfill \\ {\text{S}}\,{\mathbf{I}}\,{\text{M}} \hfill \\ \end{gathered} $$

Syllogistic logic is a ‘term logic’ with letters used to stand for the individual terms. Syllogistic logic was the first attempt at a science of logic and it remained in use up to the nineteenth century. There are many limitations to what it may express, and on its suitability as a representation of how the mind works.

14.3 Paradoxes and Fallacies

A paradox is a statement that apparently contradicts itself, and it presents a situation that appears to defy logic. Some logical paradoxes have a solution, whereas others are contradictions or invalid arguments. There are many examples of paradoxes, and they often arise due to self-reference in which one or more statements refer to each other. We discuss several paradoxes such as the liar paradox and the sorites paradox, which were invented by Eubulides of Miletus, and the barber paradox, which was introduced by Russell to explain the contradictions in naïve set theory.

An example of the liar paradox is the statement “Everything that I say is false”, which is made by the liar. This looks like a normal sentence but it is also saying something about itself as a sentence. If the statement is true, then the statement must be false, since the meaning of the sentence is that every statement (including the current statement) made by the liar is false. If the current statement is false, then the statement that everything that I say is false is false, and so this must be a true statement.

The Epimenides paradox is a variant of the liar paradox. Epimenides was a Cretan who allegedly stated “All Cretans are liars”. If the statement is true, then since Epimenides is Cretan, he must be a liar, and so the statement is false and we have a contradiction. However, if we assume that the statement is false and that Epimenides is lying about all Cretan being liars, then we may deduce (without contradiction) that there is at least one Cretan who is truthful. So in this case the paradox can be avoided.

The sorites paradox (paradox of the heap) involves a heap of sand in which grains are individually removed. It is assumed that removing a single grain of sand does not turn a heap into a non-heap, and the paradox is to consider what happens when the process is repeated often enough. Is a single remaining grain a heap? When does it change from being a heap to a non-heap? This paradox may be avoided by specifying a fixed boundary of the number of grains of sand required to form a heap, or to define a heap as a collection of multiple grains (≥2 grains). Then any collection of grains of sand less than this boundary is not a heap.

The barber paradox is a variant of Russell’s paradox (a contradiction in naïve set theory), which was discussed in chapter two. In a village, there is a barber who shaves everyone who does not shave himself, and no one else. Who shaves the barber? The answer to this question results in a contradiction, as the barber cannot shave himself, since he shaves only those who do not shave themselves. Further, as the barber does not shave himself, then he falls into the group of people who would be shaved by the barber (himself). Therefore, we conclude that there is no such barber (or that the barber has a beard).

The purpose of a debate is to convince an audience of the correctness of your position and to challenge and undermine your opponent’s position. Often, the arguments made are factual, but occasionally individuals skilled in rhetoric and persuasion introduce bad arguments as a way to persuade the audience. Aristotle studied and classified bad arguments (known as fallacies), and these include fallacies such as the ad hominem argument; the appeal to authority argument; and the straw man argument. The fallacies are described in more detail in Table 14.3.

Table 14.3 Table: fallacies in arguments

14.4 Stoic Logic

The Stoic school¹ was founded in the Hellenistic period by Zeno of Citium (in Cyprus) in the late fourth/early third century B.C. The school presented its philosophy as a way of life, and it emphasized ethics as the main focus of human knowledge. The Stoics stressed the importance of living a good life in harmony with nature. (Fig. 14.1)

Fig. 14.1

Zeno of citium

The Stoics recognized the importance of reason and logic, and Chrysippus, the head of the Stoics in the third century B.C., developed an early version of propositional logic. This was a system of deduction in which the smallest unanalyzed expressions are assertibles (Stoic equivalent of propositions). The assertibles have a truth-value such that at any moment of time they are either true or false. True assertibles are viewed as facts in the Stoic system of logic, and false assertibles are defined as the contradictories of true ones.

Truth is temporal and assertions may change their truth-value over time. The assertibles may be simple or non-simple (more than one assertible), and there may be present tense, past tense and future tense assertibles. Chrysippus distinguished between simple and compound propositions, and he introduced a set of logical connectives for conjunction, disjunction and implication that are used to form non-simple assertibles from existing assertibles.

The conjunction connective is of the form ‘both.. and..’, and it has two conjuncts. The disjunction connective is of the form ‘either.. or.. or..’, and it consists of two or more disjuncts. Conditionals are formed from the connective ‘if..,..’ and they consist of an antecedent and a consequence.

His deductive system included various logical argument forms such as modus ponens and modus tollens. His propositional logic differed from syllogistic logic, in that the Stoic logic was based on propositions (or statements) as distinct from Aristotle’s term logic. However, he could express the universal affirmation in syllogistic logic (e.g. All As are B) by rephrasing it as a conditional statement that if something is A then it is B.

Chrysippus’s propositional logic did not replace Aristotle’s syllogistic logic, and syllogistic logic remained in use up to the mid-nineteenth century. George Boole developed his symbolic logic in the mid-1800s, and his logic later formed the foundation for digital computing. Boole’s symbolic logic is discussed in the next section.

14.5 Boole’s Symbolic Logic

George Boole (Fig. 14.2) was born in Lincoln, England, in 1815. His father (a cobbler who was interested in mathematics and optical instruments) taught him mathematics and showed him how to make optical instruments. Boole inherited his father’s interest in knowledge, and he was self-taught in mathematics and Greek. He taught at various schools near Lincoln, and he developed his mathematical knowledge by working his way through Newton’s Principia, as well as applying himself to the work of mathematicians such as Laplace and Lagrange.

Fig. 14.2

George Boole

He published regular papers from his early twenties, and these included contributions to probability theory, differential equations and finite differences. He developed his symbolic algebra, which is the foundation for modern computing, and he is considered (along with Babbage) to be one of the grandfathers of computing. His work was theoretical, and he never actually built a computer or calculating machine. However, Boole’s symbolic logic was the perfect mathematical model for switching theory, and for the design of digital circuits.

Boole became interested in formulating a calculus of reasoning, and he published a pamphlet titled “Mathematical Analysis of Logic” in 1847 [2]. This short book developed novel ideas on a logical method, and he argued that logic should be considered as a separate branch of mathematics, rather than a part of philosophy. He argued that there are mathematical laws to express the operation of reasoning in the human mind, and he showed how Aristotle’s syllogistic logic could be reduced to a set of algebraic equations. He corresponded regularly on logic with Augustus De Morgan.²

He introduced two quantities ‘0’ and ‘1’ with the quantity 1 used to represent the universe of thinkable objects (i.e. the universal set), and the quantity 0 represents the absence of any objects (i.e. the empty set). He then employed symbols such as x, y, z, etc. to represent collections or classes of objects given by the meaning attached to adjectives and nouns. Next, he introduced three operators (+, − and × ) that combined classes of objects.

The expression x, y (i.e. x multiplied by y or x × y) combines the two classes x, y to form the new class x, y (i.e. the class whose objects satisfy the two meanings represented by the classes x and y). Similarly, the expression x + y combines the two classes x, y to form the new class x + y (that satisfies either the meaning represented by class x or class y). The expression x–y combines the two classes x, y to form the new class x–y. This represents the class (that satisfies the meaning represented by class x but not class y. The expression (1 – x) represents objects that do not have the attribute that represents class x.

Thus, if x = black and y = sheep, then xy represents the class of black sheep. Similarly, (1 − x) would represent the class obtained by the operation of selecting all things in the world except black things; x (1 − y) represents the class of all things that are black but not sheep; and (1 − x) (1 − y) would give us all things that are neither sheep nor black.

He showed that these symbols obeyed a rich collection of algebraic laws and could be added, multiplied, etc. in a manner that is similar to real numbers. These symbols may be used to reduce propositions to equations, and algebraic rules may be employed to solve the equations. The rules include:

• 1. $x + 0 = x\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \text{(Additive Identity)}$

• 2. $x + \left( {y + z} \right) = \left( {x + y} \right) + z\quad\quad\quad\quad\quad \text{(Associative)}$

• 3. $x + y = y + x\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \text{(Commutative)}$

• 4. $x + \left( {{1} - x} \right) = {1}$

• 5. $x{1} = x \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\text{(Multiplicative Identity)}$

• 6. $x0 = 0$

• 7. $x + {1} = {1}$

• 8. $xy = yx\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\text{(Commutative)}$

• 9. $x\left( {yz} \right) = \left( {xy} \right)z\quad\quad\quad\quad\quad\quad\text{(Associative)}$

• 10. $x\left( {y + z} \right) = xy + xz\quad\quad\quad\quad\quad\quad\text{(Distributive)}$

• 11. $x\left( {y - z} \right) = xy - xz\quad\quad\quad\quad\quad\quad\text{(Distributive)}$

• 12. $x^{2} = x\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\text{(Idempotent)}$

These operations are similar to the modern laws of set theory with the set union operation represented by ‘ + ’, and the set intersection operation is represented by multiplication. The universal set is represented by ‘1’ and the empty by ‘0’. The associative and distributive laws hold. Finally, the set complement operation is given by (1 − x).

Boole applied the symbols to encode Aristotle’s Syllogistic Logic, and he showed how the syllogisms could be reduced to equations. This allowed conclusions to be derived from premises by eliminating the middle term in the syllogism. He refined his ideas on logic further in his book “An Investigation of the Laws of Thought” [3]. This book aimed to identify the fundamental laws underlying reasoning in the human mind and to give expression to these laws in the symbolic language of calculus.

He considered the equation x² = x to be a fundamental law of thought. It allows the principle of contradiction to be expressed (i.e. for an entity to possess an attribute and at the same time not to possess it)

$$ \begin{gathered} x^{2} = x, \\ \Rightarrow x{-}x^{2} = 0, \\ \Rightarrow x\left( {{1}{-}x} \right) = 0. \\ \end{gathered} $$

For example, if x represents the class of horses then (1 – x) represents the class of ‘not-horses’. The product of two classes represents a class whose members are common to both classes. Hence, x (1 – x) represents the class whose members are at once both horses and ‘not-horses’, and the equation x (1 – x) = 0 expresses the fact that there is no such class. That is, it is the empty set.

Boole contributed to other areas in mathematics including differential equations, finite differences³ and to the development of probability theory. Des McHale has written an interesting biography of Boole [4]. Boole’s logic appeared to have no practical use, but this changed with Claude Shannon’s 1937 Master’s Thesis, which showed its applicability to switching theory and to the design of digital circuits.

14.5.1 Switching Circuits and Boolean Algebra

Claude Shannon showed in his famous Master’s Thesis that Boole’s symbolic algebra provided the perfect mathematical model for switching theory and for the design of digital circuits. It may be employed to optimize the design of systems of electromechanical relays, and circuits with relays solve Boolean algebra problems. The use of the properties of electrical switches to process logic is the basic concept that underlies all modern electronic digital computers. Digital computers use binary digits 0 and 1, and Boolean logical operations may be implemented by electronic AND, OR and NOT gates. More complex circuits (e.g. arithmetic) may be designed from these fundamental building blocks.

Modern electronic computers use billions of transistors that act as switches and can change states rapidly. The use of switches to represent binary values is the foundation of modern computing. A high voltage represents the binary value 1 with low voltage representing the binary value 0.

A silicon chip may contain billions of tiny electronic switches arranged into logical gates. The basic logic gates are AND, OR and NOT, and these gates may be combined in various ways to allow the computer to perform more complex tasks such as binary arithmetic. Each gate has binary value inputs and outputs.

The example in Fig. 14.3 is that of an ‘AND’ gate which produces the binary value 1 as output only if both inputs are 1. Otherwise, the result will be the binary value 0. Figure 14.4 is an ‘OR’ gate which produces the binary value 1 as output if any of its inputs is 1. Otherwise, it will produce the binary value 0.

Fig. 14.3

Binary AND operation

Fig. 14.4

Binary OR operation

Finally, a NOT gate (Fig. 14.5) accepts only a single input which it reverses. That is, if the input is ‘1’ the value ‘0’ is produced and vice versa.

Fig. 14.5

NOT operation

The logic gates may be combined to form more complex circuits. The example in Fig. 14.6 is that of a half adder of 1 + 0. The inputs to the top OR gate are 1 and 0 which yields the result of 1. The inputs to the bottom AND gate are 1 and 0 which yields the result 0, which is then inverted through the NOT gate to yield binary 1. Finally, the last AND gate receives two 1’s as input and the binary value 1 is the result of the addition.

Fig. 14.6

Half adder

The half adder computes the addition of two arbitrary binary digits, but it does not calculate the carry. It may be extended to a full adder that provides a carry for addition.

14.6 Application of Symbolic Logic to Digital Computing

Claude Shannon (Fig. 14.7) was an American mathematician and engineer who made fundamental contributions to computing. He was the first person⁴ to see the applicability of Boolean algebra to simplify the design of circuits and telephone routing switches. He showed that Boole’s symbolic logic developed in the nineteenth century provided the perfect mathematical model for switching theory and for the subsequent design of digital circuits and computers.

Fig. 14.7

Claude Shannon

His influential Master’s Thesis is a key milestone in computing, and it shows how to layout circuits according to Boolean principles. It provides the theoretical foundation of switching circuits, and his insight of using the properties of electrical switches to do Boolean logic is the basic concept that underlies all electronic digital computers.

Shannon realized that you could combine switches in circuits in such a manner as to carry out symbolic logic operations. This allowed binary arithmetic and more complex mathematical operations to be performed by relay circuits. He designed a circuit, which could add binary numbers, and he later designed circuits that could make comparisons, and thus is capable of performing a conditional statement. This was the birth of digital logic and the digital computing age.

Vannevar Bush [5] was Shannon’s supervisor at MIT, and Shannon’s initial work was to improve Bush’s mechanical computing device known as the Differential Analyser. This machine had a complicated control circuit that was composed of one hundred switches that could be automatically opened and closed by an electromagnet. Shannon’s insight was his realization that an electronic circuit is similar to Boole’s symbolic algebra, and he showed how Boolean algebra could be employed to optimize the design of systems of electromechanical relays used in the analog computer. He also realized that circuits with relays could solve Boolean algebra problems.

He showed in his Master’s thesis “A Symbolic Analysis of Relay and Switching Circuits” [6] that the binary digits (i.e. 0 and 1) can be represented by electrical switches. The implications of true and false being denoted by the binary digits one and zero were enormous since it allowed binary arithmetic and more complex mathematical operations to be performed by relay circuits. This provided electronics engineers with the mathematical tool they needed to design digital electronic circuits and provided the foundation of digital electronic design.

The design of circuits and telephone routing switches could be simplified with Boolean algebra. Shannon showed how to layout circuitry according to Boolean principles, and his Master’s thesis became the foundation for the practical design of digital circuits. These circuits are fundamental to the operation of modern computers and telecommunication systems, and his insight of using the properties of electrical switches to do Boolean logic is the basic concept that underlies all electronic digital computers.

14.7 Frege

Gottlob Frege (Fig. 14.8) was a German mathematician and logician who is considered (along with Boole) to be one of the founders of modern logic. He also made important contributions to the foundations of mathematics, and he attempted to show that all of the basic truths of mathematics (or at least of arithmetic) could be derived from a limited set of logical axioms (this approach is known as logicism).

Fig. 14.8

Gottlob Frege

He invented predicate logic and the universal and existential quantifiers, and predicate logic was a significant advance on Aristotle’s syllogistic logic. Predicate logic is described in more detail in Chap. 15.

Frege’s first logical system, the 1879 Begriffsschrift, contained nine axioms and one rule of inference. It was the first axiomatization of logic, and it was complete in its treatment of propositional logic and first-order predicate logic. He published several important books on logic, including Begriffsschrift, in 1879; Die Grundlagen der Arithmetik (The Foundations of Arithmetic) in 1884; and the two-volume work Grundgesetze der Arithmetik (Basic Laws of Arithmetic), which were published in 1893 and 1903. These books described his invention of axiomatic predicate logic; the use of quantified variables; and the application of his logic to the foundations of arithmetic.

Frege presented his predicate logic in his books, and he began to use it to define natural numbers and their properties. He had intended producing three volumes of the Basic Laws of Arithmetic, with the later volumes dealing with the real numbers and their properties. However, Bertrand Russell discovered a contradiction in Frege’s system (see Russell’s paradox in Chap. 2), which he communicated to Frege shortly before the publication of the second volume. Frege was astounded by the contradiction and he struggled to find a satisfactory solution, and Russell later introduced the theory of types in the Principia Mathematica as a solution.

14.8 Review Questions

• 1. What is logic?

• 2. What is a fallacy?

• 3. Give examples of fallacies in arguments in natural language (e.g. in politics, marketing, debates)

• 4. Investigate some of the early paradoxes (for example the Tortoise and Achilles paradox or the arrow in flight paradox) and give your interpretation of the paradox.

• 5. What is syllogistic logic and explain its relevance.

• 6. What is stoic logic and explain its relevance.

• 7. Explain the significance of the equation x² = x in Boole’s symbolic logic.

• 8. Describe how Boole’s symbolic logic provided the foundation for digital computing.

• 9. Describe Frege’s contributions to logic.

14.9 Summary

This chapter gave a short introduction to logic, which is concerned with reasoning and with establishing the validity of arguments. It allows conclusions to be deduced from premises according to logical rules, and the logical argument establishes the truth of the conclusion provided that the premises are true.

The origins of logic are with the Greeks who were interested in the nature of truth. Socrates had a reputation for demolishing an opponent's position (it meant that he did not win any friends in debate), and the Socratean enquiry consisted of questions and answers in which the opponent would be led to a conclusion incompatible with his original position. His approach showed that his opponent’s position was incoherent and untenable.

Aristotle did important work on logic, and he developed a system of logic, syllogistic logic, that remained in use up to the nineteenth century. Syllogistic logic is a ‘term logic’, with letters used to stand for the individual terms. A syllogism consists of two premises and a conclusion, where the conclusion is a valid deduction from the two premises. The Stoics developed an early form of propositional logic, where the assertibles (propositions) have a truth-value they are either true or false.

George Boole developed his symbolic logic in the mid-1800s, and it later formed the foundation for digital computing. Boole argued that logic should be considered as a separate branch of mathematics, rather than a part of philosophy. He argued that there are mathematical laws to express the operation of reasoning in the human mind, and he showed how Aristotle’s syllogistic logic could be reduced to a set of algebraic equations.

Gottlob Frege made important contributions to logic and to the foundations of mathematics. He attempted to show that all of the basic truths of mathematics (or at least of arithmetic) could be derived from a limited set of logical axioms (this approach is known as logicism). He invented predicate logic and the universal and existential quantifiers, and predicate logic was a significant advance on Aristotle’s syllogistic logic.