Steven Krantz - Discrete Mathematics DeMYSTiFied

Steven G. Krantz, Ph.D., is a professor of mathematics at Washington University in St. Louis, Missouri. He just finished a stint as deputy director at the American Institute of Mathematics. Dr. Krantz is an award-winning teacher, and the author of How to Teach Mathematics, Calculus Demystified, and Differential Equations Demystified, among other books.

Strictly speaking, our approach to logic is intuitive or nave. Whereas in ordinary conversation these emotion-charged words may be used to downgrade the value of that which is being described, our use of these words is more technical. What is meant is that we shall prescribe in this chapter certain rules of logic, which are to be followed in the rest of the book. They will be presented to you in such a way that their validity should be intuitively appealing and self-evident. We cannot prove these rules. The rules of logic are the point where our learning begins. A more advanced course in logic will explore other logical methods. The ones that we present here are universally accepted in mathematics and in most of science and analytical thought.

We shall begin with sentential logic and elementary connectives. This material is called the propositional calculus (to distinguish it from the predicate calculus, which will be treated later). In other words, we shall be discussing propositions which are built up from atomic statements and connectives. The elementary connectives include and, or, not, if-then, and if and only if. Each of these will have a precise meaning and will have exact relationships with the other connectives.

An elementary statement (or atomic statement) is a sentence with a subject and a verb (and sometimes an object) but no connectives (and, or, not, if then, if, and only if). For example,

John is good

Mary has bread

Ethel reads books

are all atomic statements. We build up sentences, or propositions, from atomic statements using connectives.

Next we shall consider the quantifiers for all and there exists and their relationships with the connectives from the last paragraph. The quantifiers will give rise to the so-called predicate calculus. Connectives and quantifiers will prove to be the building blocks of all future statements in this book, indeed in all of mathematics.

In everyday conversation, people sometimes argue about whether a statement is true or not. In mathematics there is nothing to argue about. In practice a sensible statement in mathematics is either true or false, and there is no room for opinion about this attribute. How do we determine which statements are true and which are false?

The modern methodology in mathematics works as follows:

We define certain terms.

We assume that these terms, or statements about them, have certain properties or truth attributes (these assumptions are called axioms).

We specify certain rules of logic.

Any statement that can be derived from the axioms, using the rules of logic, is understood to be true. It is not necessarily the case that every true statement can be derived in this fashion. However, in practice this is our method for verifying that a statement is true.

On the other hand, a statement is false if it is inconsistent with the axioms and the rules of logic. That is to say, a statement is false if the assumption that it is true leads to a contradiction. Alternatively, a statement P is false if the negation of P can be established or proved. While it is possible for a statement to be false without our being able to derive a contradiction in this fashion, in practice we establish falsity by the method of contradiction or by giving a counterexample (which is another aspect of the method of contradiction).