B.

8) There do not exist natural numbers x, y, z, n,for which x - y - z ^ Q

and 1 <n and x" + >'" = z",

where it is natural to regard the propositional form

B.9) x-y 'Z^O and 2 <n and x" + >'" = z",

as a logically important part of B.8).

Let us therefore examine propositions and propositional forms

simultaneously. In the analysis of propositional forms we find, in addition to

the variables, two types of elements. First there are such frequently

repeated words (or groups of words) as "not," "and," "or," "for all,"

which in a certain sense are the logical framework of a proposition.

The most important of these are the propositional constants (§2.4) and

the quantifiers (§2.6). Secondly there are the words (or groups of words)

that are characteristic of the mathematical theory under examination at

the moment and do not occur, in general, in other theories. Examples are

," 7," "is a prime number," "lies on," "+." The most important

types here are subjects, predicates, and function signs (§2.5).

In the following sections we shall examine these elements more closely.

They should be compared with the operator of set formation in §7.7,

the notation for functions in §8.4, and the description operator in §2.7.

2.4. The Propositional Constants

These serve the purpose of combining propositional forms in order to

construct new propositional forms. A simple example is "and."

The two propositional forms

B.10) 2 divides X B.11) 3 divides x

are combined by "and" into the one propositional form

B.12) 2 divides x and 3 divides x.

The propositional form B.12) is called the conjunction of B.10) and B.11).

The conjunction of two propositions is again a proposition, which is true

(accepted) if and only if both the components united by the "and" are

true (accepted). This fact is expressed by the

TF
Truth table (logical matrix) _1

for conjunction t\ T F

F\F F

For example, the conjunction of a false proposition (the "/^" in the left

column of the above table) with a true proposition (the "T" of the top

2 Logical ^alysis of Propositions 13

row) is a false proposition (the "F" at the intersection of the given row

and column).

Another propositional constant is "not," as in

B.13) 8 is not a perfect square.

In a logical systematization of the language it is customary to put the

"not" at the beginning and to write:

B.13') Not 8 is a perfect square.

The proposition B.13') is called the negation of "8 is a perfect square."

In the nonclassical schools of logic, negation is either completely banned

or, if admitted, it is variously interpreted by the various schools. One

possibility consists of accepting the negation of a proposition a if from a

we can derive a contradiction (i.e., a proposition that is always rejected).

If negation is admitted at all, it is always subject to the condition that no

proposition is accepted together with its negative. In the classical two-

valued logic it follows that "not" reverses the truth value. Thus we have:

Truth table (logical matrix) T

for negation F

Another important propositional constant is "or." The word "or,"

which in everyday English has several different meanings, is almost always

used in mathematics in the nonexclusive sense of the Latin "vel," for

example:

B.14) Every natural number greater than two is a prime number or has

a prime factor.
The combination of two propositions by the nonexclusive "or" is called

an alternative (or also a disjunction, although it would be more correct to

reserve the word "disjunction" for the combination of propositions

expressed by "either-or"). An alternative is true (accepted) if and only

if at least one of its components is true (accepted):

Truth table (logical matrix)

for the alternative (disjunction)

The "either-or" is used like the Latin "aut," as indicated in the following

table:

Truth table (logical matrix) ! ^ ^

for the strict disjunction T\F T

f\t F

TF

TTT

FTF

14 PART A FOUNDATIONS OF MATHEMATICS

Among the other constants of the propositional calculus we shall

mention here only implication (and its consequence equivalence), which in

the English language is represented by the words "if—then" For the

"if—then" of ordinary spoken language, the logicians have distinguished,

in the course of the centuries, several essentially different meanings.

We shall restrict ourselves here to describing the one which appears most

often in classical logic and mathematics and can be traced back to the

Stoics (Philon, ca. 300 B.C.). If a reader feels that he cannot reconcile the

"if—then" of the following truth table with his everyday spoken language,

he is referred to §3.

Let us now take up the task of constructing a truth table for "if—then."

[The four entries will be determined as soon as we have fixed on the truth

value of the following four propositions:

B.15) If 1 + 1=2, then 1 + 1=2.

B.16) // 1 + 1=2, then 1 + 1=3.

B.18) // 1 + 1=3, then 1 + 1=3.]

We regard B.15) and B.18) as true, and B.16) as false. As for B.17),

we can argue as follows: The proposition

B.17') For arbitrary real numbers x,y it is true that, if x = y, then

x^ = y^

is true. A statement that holds for arbitrary real numbers x, y, holds in

particular for x = —2 and y = 2. Thus we recognize B.17) as a true

proposition. Consequently we have the

Truth table (logical matrix)

for implication

We establish the convention that in discussing the classical logic we shall

use "if—then" in the above sense. It should be noted that there is no

inherent connection between the two parts of an implication defined in

this way. For example, the following proposition is true: "ifl + 4 = 11,

then a triangle with three equal angles has three equal sides."

An equivalence ("if and only if") may be defined as a conjunction of

reciprocal implications (see below). Thus we have the

ITF

TF

TTF

FTT

Truth table (logical matrix)

for equivalence t\T F

f\f