Introduction to Logic
by
Stefan Waner and Steven R. Costenoble

This Section: 1. Statements and Logical Operators

Section 1 Exercises

2. Logical Equivalence, Tautologies and Contradictions

Main Logic Page

"Real World" Page

1. Statements and Logical Operators

As we mentioned in the introduction, this chapter is devoted to the so-called Propositional Calculus. Contrary to what the name suggests, this has nothing to do with the subject most people associate with the word "calculus." Actually, the term "calculus" is a generic name for any area of mathematics that concerns itself with calculating. For example, arithmetic could be called the calculus of numbers. Propositional Calculus is then the calculus of propositions. A proposition, or statement, is any declarative sentence which is either true (T) or false (F). We refer to T or F as the truth value of the statement.

Example 1

The sentence "2+2 = 4" is a statement, since it can be either true or false.Since it happens to be a true statement, its truth value is T.

The sentence "1 = 0" is also a statement, but its truth value is F.

"It will rain tomorrow" is a proposition. For its truth value we shall have to wait for tomorrow.

The following statement might well be uttered by a Zen Master to his puzzled disciple: "If I am Buddha, then I am not Buddha." This is a statement which, we shall see later on, really amounts to the simpler statement "I am not Buddha." As long as the speaker is not Buddha, this is true.

"Solve the following equation for x" is not a statement, as it cannot be assigned any truth value whatsoever. (It is an imperative, or command, rather than a declarative sentence.)

"The number 5" is not a proposition, since it is not even a complete sentence.

Example 2 The Liar's Paradox

"This statement is false" gets us into a bind: If it were true, then, since it is declaring itself to be false, it must be false. On the other hand, if it were false, then its declaring itself false is a lie, so it is true! In other words, if it is true, then it is false, and if it is false, then it is true, and we go around in circles. We get out of this bind by refusing to accord it the privileges of statementhood. In other words, it is not a statement. An equivalent pseudo-statement is: "I am lying," so we call this the liar's paradox.

Example 3

"This statement is true" may seem like a statement, but there is no way that its truth value can ever be determined: is it true, or is it false? We thus disqualify it as well. (In fact, it is the negation of the liar's paradox; see below for a discussion of negation.)

Sentences such as those in Examples 2 and 3 are called self-referential sentences, since they refer to themselves. Self-referential sentences are henceforth disqualified from statementhood, so this is the last time you will see them in this chapter.

We shall use the letters p, q, r, s and so on to stand for propositions. Thus, for example, we might decide that p should stand for the proposition "the moon is round." We shall write

p: "the moon is round"

to express this. We read this

p is the statment "the moon is round."

p	~p
T	F
F	T

On the left are the two possible truth values of p, with the corresponding truth values of ~p on the right. The symbol ~ is our first example of a logical operator.

Following is a more formal definition.

Negation The negation of p is the statement ~p, which we read "not p." Its truth value is defined by the following truth table. p ~p T F F T

Example 4

Given p: "2+2 = 4" find ~p.

Solution

~p is the statement "it is not true that 2+2 = 4," or more simply,

~p: "2+2 4."

Before We Go On ...

Note that ~p is false in this case, since p is true.

Example 5

If p: "1 = 0" find ~p.

Solution

~p: "1 0."

Before We Go On ...

~p is true in this case, since p is false. Notice that a statement of the form ~p can easily be a true statement. It is a common mistake to assume that ~p is always false. You have been warned...

Example 6

If p: "I am Julius Caesar" find ~p.

Solution

~p is the statement "It is not the case that I am Julius Caesar" or "I am not Julius Caesar."

Example 7

If p: "Diamonds are a pearl's best friend," find ~p.

Solution

~p: "Diamonds are not a pearl's best friend"

Before We Go On ...

Note that "Diamonds are a pearl's worst enemy" is not the negation of p. To say that it is false that diamonds are a pearl's best friend does not necessarily mean that they are a pearl's worst enemy; it might simply be the case that they are a pearl's second best friend.

Example 8

If p: "All the politicians in this town are crooks," find ~p.

Solution

~p: "It is not the case that all the politicians in this town are crooks," or "Not all the politicians in this town are crooks," or "At least one politician in this town is not a crook."

Before We Go On ...

Notice that ~p is not the statement "No politician in this town is a crook." You must be very careful negating a statement involving the words "all" or "some." The use of these quantifiers is the subject of the predicate calculus, and so we shall have little more to say about them here.

Here is another way we can form a new proposition from old ones. Starting with p: "I am clever," and q: "You are strong," we can form the statement "I am clever and you are strong." We denote this new statement by pq, read "p and q." In order for pq to be true, both p and q must be true. Thus, for example, if I am indeed clever, but you are not strong, then pq is false.

The symbol is another logical operator. The statement pq is called the conjunction of p and q.

Conjunction The conjunction of p and q is the statement pq, which we read "p and q." Its truth value is defined by the following truth table. p q pq T T T T F F F T F F F F

In the p and q columns are listed all four possible combinations of truth values for p and q, and in the pq column we find the associated truth value for pq. For example, reading across the third row tells us that, if p is false and q is true, then pq is false. In fact, the only way we can get a T in the pq column is if both p and q are true, as the table shows.

In the following examples, we begin to see the way in which the rich color and innuendo of language is stripped to the bare essentials by logical symbolism.

Example 9

If p: "This galaxy will ultimately wind up in a black hole" and q: "2+2 = 4," what is pq?

Solution

pq: "This galaxy will ultimately wind up in a black hole and 2+2=4," or the more astonishing statement: "Not only will this galaxy ultimately wind up in a black hole, but 2+2 = 4!"

Before We Go On ...

q is true, so if p is true then the whole statement pq will be true. On the other hand, if p is false, then the whole statement pq will be false.

Example 10

With p and q as in Example 9, what does the statement p(~q) say?

Solution

p(~q) says: "This galaxy will ultimately wind up in a black hole and 2+2 4," or "Contrary to your hopes and aspirations, this galaxy is doomed to eventually wind up in a black hole; moreover, two plus two is decidedly different from four!"

Before We Go On ...

Since ~q is false, the whole statement p(~q) is false (regardless of whether p is true or not).

Example 11

If p is the statement "This chapter is boring" and q is the statement "Logic is a boring subject," then express the statement "This chapter is definitely not boring even though logic is a boring subject" in logical form.

Solution

The first clause is the negation of p, so is ~p. The second clause is simply stating the (false) claim that logic is a boring subject, and thus amounts to q. The phrase "even though" is a colorful way of saying that both clauses are true, and so the whole statement is just (~p)q.

Example 12

Let p: "This chapter is boring," q: "This whole book is boring" and r: "Life is boring." Express the statement "Not only is this chapter boring, but this whole book is boring, an in fact life is boring (so there!)" in logical form.

Solution

The statement is asserting that all three statements p, q and r are true. (Note that "but" is simply an emphatic form of "and.") Now we can combine them all in two steps: Firstly, we can combine p and q to get pq, meaning "This chapter is boring and this book is boring." We can then conjoin this with r to get: (pq)r. This says: "This chapter is boring, this book is boring and life is boring." On the other hand, we could equally well have done it the other way around: conjoining q and r gives "This book is boring and life is boring." We then conjoin p to get p(qr), which again says: "This chapter is boring, this book is boring and life is boring." We shall soon see that

(pq)r
is logically the same as
p(qr),
a fact called the associative law for conjunction. Thus both answers (pq)r and p(qr) are equally valid. This is like saying that (1+2)+3 is the same as 1+(2+3). As with addition, we sometimes drop the parentheses and write
pqr.

As we've just seen, there are many ways of expressing a conjunction in English. For example, if

p: "Waner drives a fast car"

q: "Costenoble drives a slow car,"

Waner drives a fast car and Costenoble drives a slow car.
Waner drives a fast car but Costenoble drives a slow car.
Waner drives a fast car yet Costenoble drives a slow car.
Although Waner drives a fast car, Costenoble drives a slow car.
Waner drives a fast car even though Costenoble drives a slow car.
While Waner drives a fast car, Costenoble drives a slow car.

Any sentence that suggests that two things are both true is a conjunction. The use of symbolic logic strips away the elements of surprise or judgement that can also be expressed in an English sentence.

We now introduce a third logical operator. Starting once again with p: "I am clever," and q: "You are strong," we can form the statement "I am clever or you are strong," which we write symbolically as pq, read "p or q." Now in English the word "or" has several possible meanings, so we have to agree on which one we want here. Mathematicians have settled on the inclusive or: pq means p is true or q is true or both are true.With p and q as above, pq stands for "I am clever or you are a fool, or both." We shall sometimes include the phrase "or both" for emphasis, but even if we do not that is what we mean.

Another way of saying all this is that pq, called the disjunction of p and q.

Disjunction The disjunction of p and q is the statement pq, which we read "p or q." Its truth value is defined by the following truth table. p q pq T T T T F T F T T F F F

Notice that the only way for the whole statement to be false is for both p and q to be false. For this reason we can say that pq also means "p and q are not both false." We'll say more about this in the next section.

Example 13

Let p: "the butler did it" and let q: "the cook did it." What does pq say?

Solution

pq: "either the butler or the cook did it." !"

Before We Go On ...

Remember that this does not exclude the possibility that the butler and cook both did it-or that they were in fact the same person! The only way that pq could be false is if neither the butler nor the cook did it.

Example 14

Let p: "the butler did it," let q: "the cook did it," and let r: "the lawyer did it." What does (pq)(~r) say?

Solution

(pq)(~r) says "either the butler or the cook did it, but not the lawyer." .

Example 15

Let p: "55 is divisible by 5," q: "676 is divisible by 11" and r: "55 is divisible by 11." Express the following statements in symbolic form:

(a) "Either 55 is not divisible by 11 or 676 is not divisible by 11."

(b) "Either 55 is divisible by either 5 or 11, or 676 is divisible by 11."

Solution

(a)This is the disjunction of the negations of r and q, and is thus (~r)(~q).

(b) This is the disjunction of all three statements, and is thus (pr)q, or, equivalently, p(rq). It is also equivalent to (pq)r and p(qr).

Before We Go On ...

(a) is true because ~q is true. (b) is true because p is true. Notice that r is also true. If at least one of p, q, or r is true, the whole statement (pq)r will be true.

We end this section with a little terminology: A compound statement is a statement formed from simpler statements via the use of logical operators. Examples are ~p, (~p)(qr) and p(~p). A statement that cannot be expressed as a compound statement is called an atomic statement.For example, "I am clever" is an atomic statement. In a compound statement such as (~p)(qr), we shall refer to p, q and r as the variables of the statement. Thus, for example, ~p is a compound statement in the single variable p.

The following table summarizes the three logical operators we have encountered so far.

Summary: Negation, Conjunction and Disjunction

	Symbolic Form	Truth Table	In Words
Negation	~p	p ~p T F F T	not p
Conjunction	pq	p q pq T T T T F F F T F F F F	p and q
Disjunction	pq	p q pq T T T T F T F T T F F F	p or q

Section 1 Exercises

2. Logical Equivalence, Tautologies and Contradictions

Main Logic Page

"Real World" Page

Stefan Waner (matszw@hofstra.edu)

Steven R. Costenoble (matsrc@hofstra.edu)

Last Updated: July, 1996 Copyright © 1996 StefanWaner and Steven R. Costenoble