Introduction to Logic

This on-line text is, for the most part, devoted to the study of 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 Propositions

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 a 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.

"There is no planet called Mars"	is a proposition with truth value T is a proposition with truth value F is not a proposition	.
"Ode to Spring"	is a proposition with truth value T is a proposition with truth value F is not a proposition	.
"60 = 1"	is a proposition with truth value T is a proposition with truth value F is not a proposition	.

Example 1B Self-Referential Sentences

"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.

"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 these are called self-referential sentences, since they refer to themselves.

Here are some rather amusing (and slightly disturbing) examples of self-referential senatences, the first two being taken from Douglas R. Hofstadter's Metamagical Themas:  

• "This sentence no verb."
• "This sentence was in the past tense."
• "This sentence asserts absolutely nothing."
• "While the last sentence had nothing to say, this sentence says a lot."
• "This sentence has more to say than the last two sentences combined, if you count the number of words."

E-mail us your own interesting self-referential sentences. If we like them, we will include them here with attribution.

Before we go on...

Self-referential sentences are not simply an idle indulgence; the famous logician Kurt Gödel used a mathematical formulation of the Liar's Paradox to draw very profound conclusions about the power of mathematics. (We shall be saying more about Gödel's results later.) However, we shall not be studying self-referential sentences here. 

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 as

p is the statment "the moon is round."

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.

Example 2 Negating Statements

Find the negations of the following propositions.

(a)	p: "2+2 = 4"
(b)	q: "1 = 0"
(c)	r: "Diamonds are a pearl's best friend."
(d)	s: "All the politicians in this town are crooks."

Solution

(a) ~p is the statement "it is not true that 2+2 = 4," or more simply,
~p: "2+2 4."

(b) ~q: "1 0."

(c) ~r: "Diamonds are not a pearl's best friend."

(d) ~s: " Not all the politicians in this town are crooks."

Before we go on...

Notice that ~p is false, because p is true. However, ~q is true, because q is false. A statement of the form ~q can very well be true; it is a common mistake to think it must be false.

To say that diamonds are not a pearl's best friend is not to say that diamonds are a pearl's worst enemy. The negation is not the polar opposite, but whatever would deny the truth of the original statement. Similarly, saying that not all politicians are crooks is not the same as saying that no politicians are crooks, but is the same as saying that some politicians are not crooks. Negations of statements involving the quantifiers "all" or "some" are tricky. We'll study quantifiers in more depth when we discuss the predicate calculus.

Here are some for you to try:

Example 2P Practice in Negating Statements

(a)	p: "There is life on Mars."		~p:	Select one "There is some life on Mars." "There may be life on Mars." "There may be no life on Mars." "There is no life on Mars." "There is probably no life on Mars."
(b)	p: "All lacrosse players are tall."		~p:	Select one "Some lacrosse players are not tall." "No lacrosse players are tall." "All lacrosse players are short." "Some lacrosse players are short." "Lacrosse players are not tall."
(c)	p: "My computer has some new software."		~p:	Select one "My computer has no software." "My computer has all new software." "My computer has no software at all." "My computer has some older software." "My computer has no new software."

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. The conjunction symbol "" is an example of a binary logical operator (the term "binary" indicates that the operator acts on a pair of propositions).

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 3 Conjunction

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 disappear into a black hole and 2+2=4," or the more astonishing statement: "Not only will this galaxy ultimately disappear into 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 4 Combining Conjunction with Negation

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

Solution

p(~q) says: "This galaxy will ultimately disappear into a black hole and 2+2 4," or "Contrary to your hopes and aspirations, this galaxy is doomed to eventually disappear into 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 4P Practice with Conjunction

(a)	p: "There is life on Mars." q: "There is no life on Europa."		pq:	"There is life on both Mars and Europa." "There is life on neither Mars nor Europa." "There is life on Mars but not on Europa." "There is either life on Mars or no life on Europa."
(b)	p: "We landed a man on the moon." q: "The manned lunar program is alive."		p~q:	"We never landed a man on the moon and in any case the manned lunar program is dead." "Even though we never landed a man on the moon, the manned lunar program is alive." "We landed a man on the moon and the manned lunar program is alive." "Even though we landed a man on the moon, the manned lunar program is dead."
(c)	p: "1 + 4 < 5" q: "1 + 4 = 5"		~p~q:	"1 + 4 > 5" "1 + 4 5" "1 + 4 5" "1 + 4 5"

Example 5 Words to Symbols

If p is the statement "This topic is boring" and q is the statement "Logic is a boring subject," then express the statement "This topic 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 6 Combining Three Statements

Let p: "This topic is boring," q: "This whole web site is boring" and r: "Life is boring." Express the statement "Not only is this topic boring, but this whole web site is boring, and 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 topic is boring and this web site is boring." We can then conjoin this with r to get: (pq)r. This says: "This topic is boring, this web site 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 web site is boring and life is boring." We then conjoin p to get p(qr), which again says: "This topic is boring, this web site 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 atrong, or both." We shall sometimes include the phrase "or both" for emphasis, but even if we do not that is what we mean. We call pq 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 This is the inclusive or, so pq is true when p is true or q is true or both are true. 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. The disjunctgion symbol "" is our second example of a binary logical operator.

Example 7 Disjunction

Let p: "The butler did it." let q: "The cook did it." and let r: "The lawyer did it."

(a)	What does pq say?
(b)	What does (pq)(~r) say?

Solution

(a) pq: "either the butler or the cook did it."

(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. )

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

Example 7P Practice with Disjunction

(a)	p: "There is life on Mars." q: "There is life on Titan."		pq:	"There is life Mars and also on Titan." "There is life on either Mars, Titan, or both." "There is life on either Mars or Titan, but not both." "There is either no life on Mars or no life on Titan."
(b)	p: "The US launched a manned Mars mission." q: " The USSR never launched a manned Mars mission."		p~q:	"Either the US or the USSR launched a manned Mars mission." "Neither the US nor the USSR launched a manned Mars mission." "The US or the USSR launched a manned Mars mission, but not both." "The US launched a manned Mars mission, and the USSR followed suit."
(c)	p: "1 = 4" q: "1 4"		p~q:	"1 < 4" "1 4" "1 4" "1 4"
(d)	p: "x = y" q: "x < y"		(pq)~p :	"x > y" "x y" "x < y" "x y"

Example 8 Words to Symbols

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.

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