Page 22 - Discrete Mathematics and Its Applications

CH A P TER

1 The Foundations:

Logic and Proofs

1.1 Propositional he rules of logic specify the meaning of mathematical statements. For instance, these rules
Logic Thelp us understand and reason with statements such as “There exists an integer that is
not the sum of two squares” and “For every positive integer n, the sum of the positive integers
1.2 Applications of
Propositional not exceeding n is n(n + 1)/2.” Logic is the basis of all mathematical reasoning, and of all
Logic automated reasoning. It has practical applications to the design of computing machines, to the
specification of systems, to artificial intelligence, to computer programming, to programming
1.3 Propositional languages, and to other areas of computer science, as well as to many other fields of study.
Equivalences To understand mathematics, we must understand what makes up a correct mathematical

1.4 Predicates and argument, that is, a proof. Once we prove a mathematical statement is true, we call it a theorem.A
Quantifiers collectionoftheoremsonatopicorganizewhatweknowaboutthistopic.Tolearnamathematical
topic, a person needs to actively construct mathematical arguments on this topic, and not just
1.5 Nested read exposition. Moreover, knowing the proof of a theorem often makes it possible to modify
Quantifiers the result to fit new situations.
1.6 Rules of Everyone knows that proofs are important throughout mathematics, but many people find
Inference it surprising how important proofs are in computer science. In fact, proofs are used to verify
that computer programs produce the correct output for all possible input values, to show that
1.7 Introduction to
algorithms always produce the correct result, to establish the security of a system, and to create
Proofs
artificial intelligence. Furthermore, automated reasoning systems have been created to allow
1.8 Proof Methods computers to construct their own proofs.
and Strategy In this chapter, we will explain what makes up a correct mathematical argument and intro-
duce tools to construct these arguments. We will develop an arsenal of different proof methods
that will enable us to prove many different types of results. After introducing many different
methods of proof, we will introduce several strategies for constructing proofs. We will intro-
duce the notion of a conjecture and explain the process of developing mathematics by studying
conjectures.

1.1 Propositional Logic

Introduction

The rules of logic give precise meaning to mathematical statements. These rules are used to
distinguish between valid and invalid mathematical arguments. Because a major goal of this book
is to teach the reader how to understand and how to construct correct mathematical arguments,
we begin our study of discrete mathematics with an introduction to logic.
Besides the importance of logic in understanding mathematical reasoning, logic has numer-
ous applications to computer science. These rules are used in the design of computer circuits,
the construction of computer programs, the verification of the correctness of programs, and in
many other ways. Furthermore, software systems have been developed for constructing some,
but not all, types of proofs automatically. We will discuss these applications of logic in this and
later chapters.

1