Delftse Foundations of Computation

Chapter 2 – Logic

In a scene, we know a lot more than we realise, because everything that we know has consequences—logical consequences—that follow automatically. If you know that all humans are mortal, and you know that Socrates is human, then in a sense you know that Socrates is mortal, whether or not you have ever considered or wanted to consider that fact. This is an example of logical deduction: from the premises that “All humans are mortal” and “Socrates is human”, the conclusion that “Socrates is mortal” can be deduced by logic.

Logical deduction is a kind of computation. By applying rules of logic to a given set of premises, conclusions that follow from those premises can be generated automatically. This computational process could for instance be carried out by a computer. Once you know the premises, or are willing to accept them for the sake of argument, you are forced by logic to accept the conclusions. Still, to say that you ‘know’ those conclusions would be misleading. The problem is that there are too many of them (infinitely many), and, in general, most of them are not particularly interesting. Until you have actually made the deduction, you don’t really know the conclusion, and knowing which of the possible chains of deduction to follow is not easy. The art of logic is to find an interesting conclusion and a chain of logical deductions that leads from the premises to that conclusion. Checking that the deductions are valid is the mechanical, computational side of logic.

This chapter is mostly about the mechanics of logic. We will investigate logic as a branch of mathematics, with its own symbols, formulas and rules of computation. Your objective is to learn the rules of logic, to understand why they are valid, and to develop skill in applying them. As with any branch of mathematics, there is a certain beauty to the symbols and formulas themselves. But it is the applications that bring the subject to life for most people. We will, of course, cover some applications as we go along. In a sense, though, the real applications of logic include much of computer science and of mathematics itself.

Among the fundamental elements of thought, and therefore of logic, are propositions. A proposition is a statement that has a truth value: it is either true or false. “Delft is a city” and “2 + 2 = 42” are propositions. In the first part of this chapter, we will study propositional logic, which takes propositions and considers how they can be combined and manipulated. This branch of logic has surprising application to the design of the electronic circuits that make up computers. This ties closely to the digital and boolean logic you will study in your course Computer Organisation. Logic gets more interesting when we consider the internal structure of propositions. In English, a proposition is expressed as a sentence, and, as
you know from studying grammar, sentences have parts. A simple sentence like “Delft is a city” has a subject and a predicate. The sentence says something about its subject. The subject of “Delft is a city” is Delft. The sentence says something about Delft. The something that the sentence says about its subject is the predicate. In the example, the predicate is the phrase ‘is a city’. Once we start working with predicates, we can create propositions using quantifiers like ‘all’, ‘some’ and ‘no’. For example, working with the predicate ‘has a university’ we can move from simple propositions like “Delft has a university” to “All cities have a university” or to “No city has a university” or to the rather more realistic “Some cities have a university”.

Logical deduction usually deals with quantified statements, as shown by the basic example of human mortality with which we began this chapter. Logical deduction will be a major topic of this chapter; and under the name of proof , it will be the topic of the next chapter and a major tool for the rest of this book and indeed your computer science degree programme.