7.1 Introduction and Terminology

Logic, the systematic study of reasoning, is one of the oldest branches of mathematics. For example, the notion of a syllogism was important to the ancient Greeks, and the phrase Aristotelian logic is still commonly used. But the flowering of logic in modern mathematics did not begin until the mid-nineteenth century, particularly with the work of George Boole (1815 1864). In the twentieth century, particularly with the growing importance of computers, logic became one of the most important and useful branches of modern mathematics.

In Section 0.6 we introduced various terminology and notation of mathematical logic. In particular in that section, we discussed at some length implication and quantification, two topics that will also play a major role in this chapter. (You might want to review the relevant portions of Section 0.6 now, particularly if Chapter 0 seems like something from the distant past.) In Section 0.6 we also introduced various ideas related to theorems and their proofs. One purpose of this chapter is to recapitulate somewhat more formally what we ve said earlier about proofs in order to stress the importance of logical thinking in mathematics. Another purpose is to introduce you to a variety of areas of mathematical logic which are finding increasing application in various disciplines, especially computer science. In particular, since the study of algorithms has been an important theme throughout this book, we want to show you how to use logic in the formal study of algorithms as mathematical objects.