链接：https://pan.baidu.com/s/1fCU9Bejy4M3GUetTt28eLw 

提取码：899u 

 

Propositions

Definition. A proposition is a statement that is either true or false.

For example, both of the following statements are propositions. The first is true

and the second is false.

Proposition 1.0.1. 2 + 3 = 5.

Proposition 1.0.2. 1 + 1 = 3.

Being true or false doesn’t sound like much of a limitation, but it does exclude

statements such as, “Wherefore art thou Romeo?” and “Give me an A!”.

Unfortunately, it is not always easy to decide if a proposition is true or false, or

even what the proposition means. In part, this is because the English language is

riddled with ambiguities. For example, consider the following statements:

1. “You may have cake, or you may have ice cream.”

2. “If pigs can fly, then you can understand the Chebyshev bound.”

3. “If you can solve any problem we come up with, then you get an A for the

course.”

4. “Every American has a dream.”

What precisely do these sentences mean? Can you have both cake and ice cream

or must you choose just one dessert? If the second sentence is true, then is the

Chebyshev bound incomprehensible? If you can solve some problems we come up

with but not all, then do you get an A for the course? And can you still get an A

even if you can’t solve any of the problems? Does the last sentence imply that all

Americans have the same dream or might some of them have different dreams?

Some uncertainty is tolerable in normal conversation. But when we need to

formulate ideas precisely—as in mathematics and programming—the ambiguities

inherent in everyday language can be a real problem. We can’t hope to make an

exact argument if we’re not sure exactly what the statements mean. So before we

start into mathematics, we need to investigate the problem of how to talk about

mathematics.

To get around the ambiguity of English, mathematicians have devised a special

mini-language for talking about logical relationships. This language mostly uses

ordinary English words and phrases such as “or”, “implies”, and “for all”. But

“mcs-ftl” — 2010/9/8 — 0:40 — page 6 — #12

Chapter 1 Propositions6

mathematicians endow these words with definitions more precise than those found

in an ordinary dictionary. Without knowing these definitions, you might sometimes

get the gist of statements in this language, but you would regularly get misled about

what they really meant.

Surprisingly, in the midst of learning the language of mathematics, we’ll come

across the most important open problem in computer science—a problem whose

solution could change the world.

1.1 Compound Propositions

In English, we can modify, combine, and relate propositions with words such as

“not”, “and”, “or”, “implies”, and “if-then”. For example, we can combine three

propositions into one like this:

If all humans are mortal and all Greeks are human, then all Greeks are mortal.

For the next while, we won’t be much concerned with the internals of propositions—

whether they involve mathematics or Greek mortality—but rather with how propositions are combined and related. So we’ll frequently use variables such as P and

Q in place of specific propositions such as “All humans are mortal” and “2 C 3 D 5”. The understanding is that these variables, like propositions, can take on only

the values T (true) and F (false). Such true/false variables are sometimes called

Boolean variables after their inventor, George—you guessed it—Boole.

1.1.1 NOT, AND, and OR

We can precisely define these special words using truth tables. For example, if

P denotes an arbitrary proposition, then the truth of the proposition “NOT.P /” is

defined by the following truth table:

P NOT.P /

T F F T

The first row of the table indicates that when proposition P is true, the proposition

“NOT.P /” is false. The second line indicates that when P is false, “NOT.P /” is

true. This is probably what you would expect.

In general, a truth table indicates the true/false value of a proposition for each

possible setting of the variables. For example, the truth table for the proposition