In the algebra of sets we found that it was necessary to start with certain primitive concepts in the form of undefined terms. This is typical of any formal system and is true of the algebra of propositions as well. The terms true, false, and proposition will be taken here as undefined. Without any attempt to investigate the philosophical meaning of truth and falsehood, we will assume that the words true and false are attributes which apply to propositions. By a proposition, we will infer the content of meaning of any declarative sentence which is free of ambiguity and which has the property that it is either true or false, but not both.

The discussion in the preceding paragraph helps our intuition in selecting suitable applications for the concept of a proposition, but it is not a definition. It may not even be apparent that propositions exist, since to be completely free of ambiguity is a requirement that would be difficult to justify for any given statement. The requirement is no more idealistic than the requirement in geometry that a line have no width. Certainly no such line can be drawn with a pencil or can even be proved to exist in the physical world. We will be somewhat tolerant, then, in our selection of statements which are suitable to be called propositions. The following examples are typical propositions:

3 is a prime number;

when 5 is added to 4, the sum is 7;

living creatures exist on the planet Venus.

Note that of these propositions, the first is known to be true, the secondis known to be false, and the third is either true or false (not both), although our knowledge is not sufficient to decide at present which is the case. Contrast this with the following sentence, which is not a proposition:

this statement you are reading is false.

If we assume that the statement is true, then from its content we infer that it is false. On the other hand, if the statement is assumed to be false, then from its content we infer that it is true. Therefore this statement fails to satisfy our requirements and is not a proposition.  We shall use lower case italic letters p, q, r.... to represent propositions.  Where no specific proposition is given, these will be called propositional variables and used to represent arbitrary propositions.

From any proposition, or set of propositions, other propositions may be formed. The simplest example is that of forming from the proposition p the negation of p, denoted by p'. For any proposition p, we define p' to be the proposition "it is false that p." For example, suppose that p is the proposition

sleeping is pleasant.

The negation of this proposition would be the proposition

it is false that sleeping is pleasant.

Since this statement is somewhat awkward, it is convenient to reword it to conform more closely with common usage. Other wordings that are equally acceptable are the following:

sleeping is not pleasant;

sleeping is unpleasant.

Regardless of the wording, it is essential that the negation be worded in such a way that it has the opposite truth value to that of the original proposition. When p is true, p' is false and when p is false, p' is true.

       Any two propositions p and q may be combined in various ways to form new propositions. To illustrate, let p be the proposition

ice is cold,

and let q be the proposition

blood is green.

These propositions may be combined by the connective and to form the proposition

ice is cold and blood is green.

This proposition is referred to as the conjunction of p and q. In general,  we define the conjunction of p and q for arbitrary propositions p and q to be the proposition "both p and q." In wording this proposition, the word both is often omitted. We will denote the conjunction of p and q by pq, and we will require that the proposition be true in those cases in which both p and q are true, and false in cases in which either one or both of p and q are false.

Another way in which the propositions in the preceding paragraph may be combined is indicated in the proposition

either ice is cold or blood is green.

This proposition is referred to as the disjunction of p and q. The use of "either ... or..." in English is ambiguous in that some usages imply "either . . . or ... or both," but other usages imply "either ... or ... , but not both." Consider, for example:

this creature is either a dog or an animal;

the baby is either a boy or a girl.

The first of these is called inclusive disjunction, and allows the possibility that both may be the case. This is the sense in which we will use disjunction throughout this text. The second proposition reflects the usage "either ... or .... but not both." When we intend this interpretation,  the phrase but not both will always be added.

For arbitrary propositions p and q, we will define the disjunction of p and q, denoted by p + q, to be the proposition "either p or q or both."

The words or both are usually omitted, and the word either may be omitted in cases where no ambiguity results. We will require that this proposition be true whenever either one of p and q or both are true, and false only when both p and q are false.

In connection with any of these propositions, it is customary to apply the terminology introduced in (BOOLEAN ALGEBRA). That is, we may speak of variables and functions in exactly the same way as before. The only change in terminology is that whenever the letters involved represent propositions, we speak of propositional variables and propositional functions rather than the more general, but equally correct, terms Boolean variables and Boolean functions.

It follows from our definitions that the negation of "p or q" is the proposition "not p and not q," which can also be stated "neither p nor q."  Likewise, the negation of "p and q" is "either not p or not q. " That is,  the laws of De Morgan hold for propositions just as they do for sets.

In symbolic form we have the following laws for propositions:

(p + q)' = p'q',

(pq)' = p' + q'.

EXAMPLE 1. Let p be the proposition "missiles are costly," and let q be the proposition "Grandma chews gum." Write in English the propositions represented by the symbols (a) p + q', (b) p'q', (c) pq' + p'q.

Solution. (a) Either missiles are costly or Grandma does not chew gum.

(b) Missiles are not costly and Grandma does not chew gum.

(c) Either missiles are costly and Grandma does not chew gum, or missiles are not costly and Grandma chews gum.

This last statement is not very clear, but it is difficult to avoid ambiguity in complicated sentences of this type. This difficulty is one of the primary reasons why the symbolic notations we have introduced are of value. In symbols, the proposition cannot be misunderstood.