![]() | Section 1 Exercises | ![]() | 2. Logical Equivalence, Tautologies and Contradictions | ![]() | Main Logic Page | ![]() | "Real World" Page |
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.
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.
"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 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
to express this. We read this
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. |
Given p: "2+2 = 4" find ~p.
Solution
~p is the statement "it is not true that 2+2 = 4," or more simply,
Before We Go On ...
Note that ~p is false in this case, since p is true.
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...
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."
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.
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 p
q to be true, both p and q must be true. Thus, for example, if I am indeed clever, but you are not strong, then p
q is false.
The symbol is another logical operator. The statement p
q is called the conjunction of p and q.
Conjunction
The conjunction of p and q is the statement p
|
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 p
q. For example, reading across the third row tells us that, if p is false and q is true, then p
q is false. In fact, the only way we can get a T in the p
q 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.
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 p
q will be false.
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).
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.
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: (p
q)
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
(q
r), which again says: "This chapter is boring, this book is boring and life is boring." We shall soon see that
As we've just seen, there are many ways of expressing a conjunction in English. For example, if
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: p
q means p is true or q is true or both are true.
With p and q as above, p
q 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 p
|
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.
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.
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." .
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
(r
q). It is also equivalent to (p
q)
r and p
(q
r).
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)(q
r) 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)
(q
r), 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
|
not p | |||||||||||||||||
![]() |
| |||||||||||||||||
![]() |
|
![]() | 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) |