Still StrugglingLogic involves the study of arguments and their use in reasoning. An argument tries to establish the truth of a certain statement, the conclusion, based on other statements, the premises. For example, if you say, “Nobody is perfect; therefore I am not perfect,” the first part (“Nobody is perfect”) constitutes the premise, and it gives a reason to accept the conclusion (“I am not perfect”). Few reasonable people would object to this mode of thought, but many arguments are far less clear-cut. What if we don’t know that an argument actually proves a particular conclusion? What if one of the statements in an argument turns out false? Logic allows us to resolve most problems of this sort, and helps us to get an idea of how arguments “play out.” Logic can also help us to know when people hope to fool us into accepting “conclusions” based on insufficient, irrelevant, or contradictory “evidence”!
CHAPTER OBJECTIVES
In this chapter, you will
• Learn what logic can do, and why we need it.
• Understand sentence forms and rules.
• Symbolize basic logical operations and sentences.
• Break sentences down into tables.
• Use truth tables to prove simple logical statements.
• Construct simple derivations.
When an argument functions as it should, and we know that the conclusion holds true on the strength of the premises, we have sound or valid reasoning (as opposed to unsound or invalid reasoning). Valid reasoning involves the way in which one sentence leads to another, regardless of whether the individual sentences hold true or not in the “real world.” For example, we can construct a logically valid argument to the effect that if you are a sparrow, then you can fly (even though neither condition represents reality)! Logic provides us with mathematical certainty about a specific chain of reasoning. Pure logic, however, has nothing to do with the correctness or reality of any assumptions that we make.
Logicians use many different terms to talk about arguments, but don’t let them intimidate you! They’re all talking about the same thing. We can call an argument an inference or a deduction, because we infer or deduce the conclusion from the premises. We might also say that the premises entail or imply the conclusion, or that the conclusion follows from the premises.
All the statements in an argument constitute propositions. In everyday spoken languages, we express statements as sentences. Simple declarative sentences lend themselves ideally to logic, for example, “All dogs are mammals.” We have trouble assigning truth or falsity to questions, orders, or expressions of feeling, so such sentences do not lend themselves very well to use in logical arguments.
We can place verbal or “blogospheric” disputes—“arguments” in the everyday sense of the word—outside the bounds of formal logic. Such disputes rarely have much to do with deductive reasoning, and logic alone can rarely resolve them. We should also distinguish logical reasoning from the psychology that describes how people contemplate the nature of an argument. Logical validity constitutes an objective, not a subjective, measure of an argument’s strength. Logical argument also differs from making a persuasive speech in support of a statement or idea, which often takes advantage of appeals to emotion and eloquent language (or even suspicious reasoning) in addition to (or instead of) valid inferences. Logic addresses only those statements about which we can speak or write with absolute certainty.
Even when dealing with facts, in many everyday circumstances we can do little more than guess at our conclusions, and we ought not to expect certainty from such diluted “reasoning.” In a high-stakes criminal trial, the prosecutors must demonstrate the defendant’s guilt “beyond a reasonable doubt.” In logic, we demand total perfection; we must establish our conclusions “beyond all doubt.” By expressing an inference as simply and clearly as possible and checking it for validity, we can make an “airtight” argument where true premises absolutely guarantee a true conclusion.
TIP Most arguments aren’t as basic as deriving one conclusion from one premise. To deduce more complex, interesting things, we can string simple inferences together so that the conclusion of one step serves as a premise for the next step. As long as each link in the chain of inferences is valid, we can be sure that the whole argument is valid.
Even though logic may seem abstract and divorced from practical concerns, it deals with truth at a general level, so it has broad applications. Mathematical proofs rely on logical inferences to establish significant final results known as theorems. Similar deductions apply in all fields of science. Computers rely on logic at a fundamental level; digital 1s and 0s work like “truths” and “falsehoods.”
Traditionally, logic has constituted an important branch of philosophy, and logic remains central to philosophical analysis and argumentation. Logic can also apply to political science, debate, law, and rhetoric. Whenever we want to defend or critique an argument, we can use logic to classify the reasoning and test its validity.
Aside from all these uses, some logicians will tell you that logic has intrinsic value as a discipline in its own right, just as art has. Some people find beauty in the order and necessity of logical arguments. Others simply enjoy the “mental exercise” of working through a challenging logical proof.
Diverse arguments can share similar patterns of reasoning, so we don’t have to start from scratch on every argument. This principle constitutes one of the most important insights of logical thinking!
Two arguments about vastly different subjects may share a single logical form. Consider the following:
• The ocean is made of water, and water is wet. Therefore, the ocean is wet.
• Candy is made of sugar, and sugar is sweet. Therefore, candy is sweet.
These two inferences share something in common, but it has nothing to do with the similarity between the ocean and candy. The statements fit together in the same way. We can characterize them both with the following argument form:
• Thing A is made of substance S, and substance S has property P. Therefore, thing A has property P.
We could fill in anything for A, S, and P without affecting the validity of the argument in the slightest.
The form of an argument does not depend on the “real world” truth of the individual statements within it. The validity of the argument doesn’t change even if we fill in the blanks with ridiculous statements. For example, consider the following argument:
• My house is made of figs, and figs can exist only in outer space. Therefore, my house exists in outer space.
The premises are both false, but they still entail the conclusion, which in this case is also false! The converse situation can also occur; sometimes we may come across an invalid argument whose conclusion happens to be true.
The truth of the statements isn’t the only part of the argument that we can set aside to focus on the logical form; the meanings of the words may also lack relevance! That’s why, for example, we can swap out the ocean, or candy, or figs in the foregoing arguments without having to reconsider the inference. In fact, we don’t have to know what we’re talking about at all! We can use nonsense words and remain confident that our reasoning holds sound. For example:
• Blurgs are made of gludds, and gludds are plishy. Therefore, blurgs are plishy.
We need a few guidelines in order to keep our arguments clear and consistent. Sometimes we will see such logical restrictions as self-evident “laws of thought.” Even if you doubt this claim, it shouldn’t stop you from following along. Think of these as the rules of the “logic game.”
The principle of identity says that if a statement is true, then it is true (and if it’s false, then it’s false). Who can argue with that? In order for this rule to hold true all the time, however, we must use words consistently. The sentence “My father is tall” constitutes a true statement for some people and a false statement for others.
Still Struggling
The foregoing statement might seem confusing, but the confusion does not violate the principle of identity. The words “my father” can refer to a different man in each case, so the statements themselves differ! We must exercise caution whenever we work with words that depend on context (such as who speaks, or when they speak) and words with ambiguous meanings or multiple definitions.
The principle of contradiction tells us that no statement can hold true and false “at the same time.” If an argument concludes both “It is the case that Peter is alive” and “It is not the case that Peter is alive,” then something has gone wrong. If the argument uses words consistently as it should (so that “Peter” refers to the same man in both statements, and “alive” means the same thing), then the foregoing argument makes an incredible claim. Situations can arise in everyday discourse when we’ll want to answer “yes and no,” but in such cases, we’ll inevitably find that at least one of the words has a double meaning.
The law of excluded middle maintains that all statements are either true or false. Traditional logic constitutes a binary (two-state) system. No middle values or half-truths exist. Even if we have no clue as to whether a statement holds true or false, we can safely assume that things must go one way or the other.
This principle may seem obvious to you, but it constitutes nothing more than an agreed-on convention for the simplest sorts of arguments. A few imaginative mathematicians and computer scientists have devised (and even applied) specialized forms of logic that allow for states other than true and false.
In the English language (and most other languages), we can break simple declarative sentences into two parts: subject and predicate. The subject comprises the main or only noun in the sentence, and it names what the sentence is about. The predicate provides us with information about the subject, such as a description of its qualities or expression of an action it takes.
The simplest subject/predicate combination contains one noun and one verb. Consider the following sentences:
• Jack walks.
• Jill sneezes.
• The computer works.
• You shop.
These sentences all represent well-formed English propositions. They all have the subject/verb form in common, and they’re all clear, unambiguous sentences. You can write SV (where S stands for “subject” and V stands for “verb”) to symbolize each one of them. If their content seems spare (we aren’t told where Jack is going, for example, or how he walks), that’s because a subject/verb combination constitutes the most minimal structure that qualifies as a complete declarative sentence.
Consider the following sentences:
• Jack walks his dog.
• Jill kicks the ball.
• You plant a tree.
• The ball hits the pavement.
Each of these sentences contains a noun (the subject) followed by a verb, and then a second noun that is acted upon by the subject and verb. We call this third part the object. All four of the above sentences have the form subject/verb/object. Let’s abbreviate this form as SVO (where S stands for “subject,” V stands for “verb,” and O stands for “object”). Anything can serve as the subject or the object of a sentence: a person (Jack), an inanimate thing (ball), an abstract concept (fun), or whatever else we might imagine.
Now look at the following sentences:
• Jack is a person.
• Jill has a cold.
• You will be late.
• The dog was upset.
Once again, these sentences start with the main noun (subject). The final word of each sentence gives a description of the subject or another name for it; we call it the complement. The two words are joined by a verb, called the linking verb, usually a form of the verb “to be”: am, is, are, was, were, or will be. (Some formal texts refer to a linking verb as a copula.) This sentence structure is called subject/linking verb/complement, or SLVC for short.
In propositional logic, we will usually represent complete sentences by writing uppercase letters of the alphabet. You might say “It is raining outside,” and represent this statement as the letter R. Someone else might add, “It’s cold outside,” and represent it as C. A third person might say, “The weather forecast calls for snow tomorrow,” and represent it as S. Still another person might make the claim, “Tomorrow’s forecast calls for sunny weather,” and represent it as B (for “bright”; you’ve already used S).
When you write down a letter to stand for a sentence, you assert that the sentence holds true. So, for example, if Joanna writes down C in the above situation, she means to say “It is cold outside.” You might disagree if you grew up in Alaska and Joanna grew up in Hawaii. You might say, “It’s not cold outside.” You would symbolize this statement by writing the letter C with a negation symbol in front of it.
In propositional logic, the drooping minus sign (¬) can represent negation, also called the logical NOT operation. Let’s employ this symbol. Some texts use a tilde (~) to represent negation. Some use a minus sign (−). Some put a line over the letter representing the sentence; still others use an accent symbol. In our system, we would denote the sentence “It’s not cold outside” by writing a drooping minus sign followed by the letter C; that is, by writing ¬C.
Now imagine that someone declares, “You are correct to say ¬C. In fact, I’d say that it’s hot outside!” Let’s use H to stand for “It’s hot outside.” If you give the matter a little bit of thought, you’ll realize that H does not mean the same thing as ¬C. You’ve seen days that were neither cold nor hot. Our finicky atmosphere can produce in-between states such as “cool” (K), “mild” (M), and “warm” (W). There can exist no in-between condition, however, when it comes to the statements C and ¬C. In propositional logic, either it’s cold or it’s not cold. Either it’s hot or it’s not hot. Any given proposition is either true or it’s false (not true). Of course, the “decision line” for temperature opinions will vary from person to person—but you should get the general idea!
Mathematicians have invented logical systems in which in-between states can and do exist. These schemes go by names such as trinary logic or fuzzy logic. In trinary logic, three truth values exist: true, false, and “neutral.” In fuzzy logic, we get a continuum of values, a smooth transition from “totally false” through “neutral” to “totally true.” For now, let’s stick to binary logic, in which any given proposition is either “purely false” or “purely true.”
Propositional logic doesn’t bother with how words or phrases interact inside a sentence. However, propositional logic does involve the ways in which complete sentences interact with one another. We can combine sentences to make bigger ones, called compound sentences. The truth or falsity of a compound sentence depends on the truth or falsity of its component sentences, and on the ways in which we interconnect them.
Suppose someone says, “It’s cold outside, and it’s raining outside.” Using the symbols above, we can write this as
C AND R
In symbolic logic, mathematicians use a symbol in place of the word AND. Several symbols appear in common usage, including the ampersand (&), the inverted wedge [^], the asterisk (*), the period (.), the multiplication sign [×], and the raised dot (·}. Let’s use the inverted wedge. In that case, we write the above compound sentence as
C ^ R
The formal term for the AND operation is logical conjunction. A compound sentence containing one or more conjunctions holds true if (but only if) both or all of its components are true. If any one of the components happens to be false, then the whole compound sentence is false.
Now imagine that a friend comes along and says, “You are correct in your observations about the weather. It’s cold and raining. I have been listening to the radio, and I heard the weather forecast for tomorrow. It’s supposed to be colder tomorrow than it is today. But it’s going to stay wet. So it might snow tomorrow.”
You say, “It will rain or it will snow tomorrow, depending on the temperature.”
Your friend says, “It might be a mix of rain and snow together, if the temperature hovers near freezing.”
“So we might get rain, we might get snow, and we might get both,” you say.
“Of course. But the weather experts say we are certain to get precipitation of some sort,” your friend says. “Water will fall from the sky tomorrow—maybe liquid, maybe solid, and maybe both.”
Suppose that we let R represent the sentence “It will rain tomorrow,” and we let S represent the sentence “It will snow tomorrow.” Then we can say
S OR R
This statement constitutes an example of inclusive logical disjunction. Mathematicians use at least two different symbols to represent this operation: the plus sign (+) and the wedge (∨). Let’s use the wedge. We can now write
S ∨ R
A compound sentence in which both, or all, of the components are joined by inclusive disjunctions holds true if, but only if, at least one of the components is true. A compound sentence made up of inclusive disjunctions is false if, but only if, all the components are false.
In the foregoing example, we refer to the inclusive OR operation. If all the components are true, then the whole sentence holds true. However, that’s not the only way we can define disjunction. Once in awhile you’ll encounter another logical operation called exclusive OR in which, if both or all of the components are true, the compound sentence is false.
If you say “It will rain or snow tomorrow” using the inclusive OR, then your statement will turn out true if the weather gives you a mix of rain and snow. But if you use the exclusive OR, you can’t have a mix. The weather must produce either rain or snow, but not both, in order for the compound sentence to hold true.
TIP Some logicians call the exclusive OR operation the either-or operation. Engineers often abbreviate it as XOR; you’ll encounter it if you do any in-depth study of digital electronic or computer systems. From now on, if you see the symbol for the OR operation (or the word “or” in a problem), you should assume that it means the inclusive OR operation, not the exclusive OR operation.
Imagine that your conversation about the weather continues, getting more strange with each passing minute. You and your friend want to decide if you should prepare for a snowy day tomorrow, or conclude that you’ll have to contend with nothing worse than rain and gloom.
“Does the weather forecast say anything about snow?” you ask.
“Not exactly,” your friend says. “The radio newscaster said that there’s going to be precipitation through tomorrow night, and that it’s going to get colder tomorrow. I looked at my car thermometer as she said that, and the outdoor temperature was only a little bit above freezing.”
“If we have precipitation, and if it gets colder, then it will snow,” you say.
“Yes.”
“Unless we get an ice storm.”
“That won’t happen.”
“Okay,” you say. “If we get precipitation tomorrow, and if it’s colder tomorrow than it is today, then it will snow tomorrow.” (This is a weird way to talk, but you’re learning logic here, not the art of conversation. Logically rigorous conversation can sound bizarre, even in the “real world.” Have you ever sat in a courtroom during a civil lawsuit between corporations?)
Let P represent the sentence, “There will be precipitation tomorrow.” Let S represent the sentence “It will snow tomorrow,” and let C represent the sentence “It will be colder tomorrow.” In the above conversation, you made a compound proposition consisting of three sentences, as follows:
IF (P AND C), THEN S
Another way to write this is
(P AND C) IMPLIES S
In this context, “implies” means “always results in.” In formal propositional logic, “X IMPLIES Y” means “If X, then Y.” Symbolically, we write the above statement as
(P ^ C) → S
The arrow represents logical implication, also known as the IF/THEN operation. When we join two sentences with logical implication, we call the “implying” sentence (to the left of the arrow) the antecedent. In the above example, the antecedent is (P ^ C). We call the “implied” sentence (to the right of the arrow) the consequent. In the above example, the consequent is S.
Some texts use other symbols for logical implication, such as a “hook” or “lazy U opening to the left” (⊃} or a double-shafted arrow (⇒}. Let’s keep using the single-shafted arrow (→), making sure that it always points to the right.
Imagine that your friend declares, “If it snows tomorrow, then there will be precipitation and it will be colder.” For a moment you hesitate, because that strikes you as an exceedingly strange way to make a statement about the weather. But you conclude that it makes perfect logical sense. Your friend has composed the following implication:
S → (P ^ C)
Now you and your friend agree that both of the following implications are valid:
(P ^ C) → S
and
S → (P ^ C)
You can combine these two statements into a logical conjunction, because you assert them both together “at the same time”:
[(P ^ C) → S] ^ [S → (P ^ C)]
When implications between two sentences hold valid “in both directions,” we have an instance of logical equivalence. We can shorten the above statement to
(P ^ C) IF AND ONLY IF S
Mathematicians sometimes reduce the phrase “if and only if” to the single word “iff,” so we can also write
(P ^ C) IFF S
Logicians use a double-headed arrow (↔) to symbolize logical equivalence. As with all the other logical operations, alternative symbols exist. Sometimes you’ll see an equals sign (=), a three-barred equals sign (≡), or a double-shafted, double-headed arrow (⇔). Let’s use the single-shafted, double-headed arrow (↔). We can now write the foregoing statement as
(P ^ C) ↔ S
TIP When we want to establish logical equivalence, we must exercise care to ensure that the implication actually holds valid in both directions. Here’s a situation in which logical implication holds in one direction but not in the other, but that limitation can easily escape us if we’re careless. Consider this statement: “If it is overcast, then there are clouds in the sky.” This statement always holds true. Suppose that we let O represent the sentence “It is overcast” and we let K represent the sentence “There are clouds in the sky.” Then symbolically we have
O → K
If we reverse the sense of the implication, we obtain
K → O
This sentence translates to, “If there are clouds in the sky, then it’s overcast.” This does not always hold true. We have all seen days or nights in which there were clouds in the sky, but there were clear spots too, so it wasn’t overcast.
PROBLEM 1-1
Under what circumstances does the conjunction of several sentences have false truth value? Under what circumstances does the conjunction of several sentences hold true?
SOLUTION
The conjunction of several sentences is false if at least one of them is false. The conjunction of several sentences holds true if and only if every single one of them is true.
PROBLEM 1-2
Under what circumstances is the disjunction of several sentences false? Under what circumstances is the disjunction of several sentences true?
The disjunction of several sentences is false if and only if each and every one of them is false. The disjunction of several sentences holds true if at least one of them is true. In this context, the term disjunction refers to the inclusive OR operation.
A truth table denotes all possible combinations of truth values for the variables in a compound sentence. The values for the individual variables appear in vertical columns.
The negation operation has the simplest truth table, because it operates on only one variable. Table 1-1 shows how logical negation works for a variable called X.
TABLE 1-1 Truth table for logical negation (NOT).
Let X and Y represent two logical variables. Conjunction (X ^ Y) produces results as shown in Table 1-2. This operation produces the truth value T when, but only when, both variables have value T. Otherwise, the operation produces the truth value F.
TABLE 1-2 Truth table for logical conjunction (AND).
Inclusive logical disjunction for two variables (X v Y) breaks down as in Table 1-3A. We get T when either or both of the variables have truth value T. If both of the variables have truth value F, then we get F for the whole statement.
Table 1-3B shows the truth values for the exclusive logical disjunction operation (XOR). This operation gives us T if and only if both variables have opposite truth value (F-T or T-F); if the two variables agree (T-T or F-F), then the composite sentence has value F.
TABLE 1-3 Truth tables for both forms of logical disjunction. At A, inclusive (OR). At B, exclusive (XOR).
A logical implication holds valid (has truth value T) whenever the antecedent is false. A logical implication is also valid if the antecedent and the consequent are both true. But implication has truth value F when the antecedent is true and the consequent is false. Table 1-4 shows the truth-value breakdown for logical implication.
TABLE 1-4 Truth table for logical implication (IF/THEN).
Let’s look at a “word-problem” example of logical implication that fails the “validity test.” Let X represent the sentence, “The barometric pressure is falling fast.” Let Y represent the sentence, “A tropical hurricane is coming.” Consider the sentence
X → Y
Now imagine that the barometric pressure is dropping faster than you’ve ever seen it fall. Therefore, variable X has truth value T. But suppose that you live in North Dakota, where tropical hurricanes never stray. Sentence Y has truth value F. Therefore, the implication “If the barometric pressure is falling fast, then a tropical hurricane is coming” has truth value F overall. In other words, it’s invalid—in North Dakota, anyhow.
If X and Y represent logical variables, then X IFF Y has truth value T when both variables have value T, or when both variables have value F. If the truth values of X and Y differ, then X IFF Y has truth value F. Table 1-5 breaks the truth values down for logical equivalence.
TABLE 1-5 Truth table for logical equivalence (IFF).
TIP Note that the truth values for logical equivalence precisely oppose those for the exclusive OR operation (XOR). You can see this distinction when you compare the far right-hand columns of Tables 1-3B and 1-5.
TIP In logic, we can use an ordinary equals sign to indicate truth value. If we want to say that a particular sentence K holds true, for example, we can write K = T. If we want to say that a variable Xalways has false truth value, we can write X = F. But if we use the equals sign for this purpose, we must take care not to confuse its meaning with the meaning of the double-headed arrow that stands for logical equivalence. The equals sign tells us a characteristic of a particular sentence (truth or falsity); the double-headed arrow denotes an operation that we carry out between two sentences.
Logicians define the truth values shown in Tables 1-1 through 1-4 by convention, using common sense. Arguably, we can use the same simple reasoning to get Table 1-5 for logical equivalence.
We might suppose that two logically equivalent statements must have identical truth values. How, we might ask, could common sense dictate anything else? We can back up our intuition, no matter how strong, by proving this fact based on the truth tables for conjunction and implication. Let’s construct the proof in the form of a truth table.
Remember that X ↔ Y means the same thing as (X → Y) ^ (Y → X). We can build up X ↔ Y in steps, as shown in Table 1-6 as we proceed from left to right. The four possible combinations of truth values for sentences X and Y appear in the first (left-most) and second columns. The truth values for X → Y appear in the third column, and the truth values for Y → X appear in the fourth column.
TABLE 1-6 A truth-table proof that logically equivalent statements always have identical truth values.
In order to get the truth values for the fifth (right-most) column, we can apply conjunction to the truth values in the third and fourth columns. The complex logical operation (also called a compound logical operation because it comprises combinations of the basic ones) in the fifth column has the same truth values as X ↔ Y in every possible case. Therefore, that compound operation does, in fact, constitute logical equivalence.
You’ve just seen a mathematical proof of the fact that for any two logical sentences X and Y, (X ↔ Y) = T when X and Y have the same truth value, and (X ↔ Y) = F when X and Y have different truth values. Sometimes, when mathematicians finish proofs, they write “Q.E.D.” at the end. This sequence of letters constitutes an abbreviation of the Latin phrase Quod erat demonstradum. In English, it means “Which was to be demonstrated.”
When you read or construct logical statements, you should always do the operations within parentheses first. If you see multilayered combinations of sentences (called nesting of operations), then you should first use ordinary parentheses (), then brackets [], and then braces {}. Alternatively, you can use groups of plain parentheses inside each other, but if you do that, you had better ensure that you end up with the same number of left-hand parentheses and right-hand parentheses in the complete expression.
If you see an expression with no parentheses, brackets, or braces, you should go through the following steps in the order listed:
• Perform all the negations, going from left to right
• Perform all the conjunctions, going from left to right
• Perform all the disjunctions, going from left to right
• Perform all the implications, going from left to right
• Perform all the logical equivalences, going from left to right
We call this “operation hierarchy” precedence of operations, or simply precedence.
Consider the following compound sentence, which might easily confuse anyone not familiar with the rules of precedence:
A ^ ¬B ∨ C → D
Using parentheses, brackets, and braces to clarify this statement according to the rules of precedence, we can write
{[A ^ (¬B)] ∨ C} → D
Now consider the following compound sentence, which creates such a mess that we’ll run out of grouping symbols if we use the “parentheses/brackets/braces” or “PBB” scheme:
A ^ ¬B ∨ C → D ^ E ↔ F ∨ G
Using plain parentheses only, we can write it as
(((A ^ (¬B)) ∨ C) → (D ^ E)) ↔ (F ∨ G]
Still Struggling
Expressions such as the one shown above can confound even the most meticulous logician. When we count up the number of left-hand parentheses and the number of right-hand parentheses in the complete expression, we find six left-hand ones and six right-hand ones. Whenever we write, or read, a complicated logical sentence, we should always check to make sure that we have the proper balance of grouping symbols. It doesn’t hurt to check complicated expressions two or three times!
PROBLEM 1-3
How many possible combinations of truth values exist for a set of four sentences, each of which can attain either the value T or the value F independently of the other three?
For a group of four sentences, each of which can attain the value T or F independently of the other three, you can have 24 or 16 different combinations of truth values. If you think of F as the number 0 and T as the number 1, then you can find all the truth values of n independent sentences by counting up to 2n in the binary numbering system. In this case, with n = 4, you would count as follows:
If you claim that two compound sentences are logically equivalent, then you can prove that fact by showing that their truth tables produce identical results. Also, if you can show that two compound sentences have truth tables that produce identical results, then you can be sure that those two sentences are logically equivalent, as long as you account for all possible combinations of truth values. Following are several examples of simple proofs using truth tables.
TABLE 1-7 At A, statement of truth values for X ^ Y. At B, statement of truth values for Y ^ X. The outcomes are identical, demonstrating that they are logically equivalent.
Tables 1-7A and 1-7B show that, for any two variables X and Y, the statement
X ^ Y
is logically equivalent to the statement
Y ^ X
We can write the foregoing theorem entirely in symbols as
X ^ Y ↔ Y ^ X
Tables 1-8A and 1-8B show that for any three variables X, Y, and Z, the statement
(X ^ Y) ^ Z
is logically equivalent to the statement
X ^ (Y ^ Z)
TABLE 1-8A Derivation of truth values for (X ^ Y) ^ Z. Note that the last two columns of this proof make use of a theorem that we’ve already proved.
In Table 1-8A, the logic between the last two columns makes use of the theorem that we proved in Table 1-7. When a theorem plays the role of a “subtheorem” in this way, we call it a lemma. We can write the foregoing final theorem entirely in symbols as
(X ^ Y) ^ Z ↔ X ^(Y ^ Z)
TABLE 1-8B Derivation of truth values for X ^ (Y ^ Z). The far-right-hand column has values that coincide with those in the far-right-hand column of Table 1-8A, demonstrating that the far-right-hand expressions in the top rows of both tables are logically equivalent.
TABLE 1-9 At A, statement of truth values for X ∨ Y. At b, statement of truth values for Y ∨ X. The outcomes are identical, demonstrating that they are logically equivalent.
Tables 1-9A and 1-9B show that for any two variables X and Y, the statement
X ∨ Y
is logically equivalent to the statement
Y ∨ X
We can write the foregoing theorem entirely in symbols as
X ∨ Y ↔ Y ∨ X
Tables 1-10A and 1-10B show that for any three variables X, Y, and Z, the statement
(X ∨ Y) ∨ Z
TABLE 1-10A Derivation of truth values for (X ∨ Y) ∨ Z. Note that the last two columns of this proof make use of a lemma that we’ve already proved.
is logically equivalent to the statement
X ∨ (Y ∨ Z)
Our reasoning between the last two columns in Table 1-10A employs the theorem from Table 1-9 as a lemma. We can write the foregoing final theorem entirely in symbols as
(X ∨ Y) ∨ Z↔ X ∨ (Y ∨ Z]
TABLE 1-10B Derivation of truth values for X ∨ (Y ∨ Z). The far-right-hand column has values that coincide with those in the far-right-hand column of Table 1-10A, demonstrating that the far-right-hand expressions in the top rows of both tables are logically equivalent.
TABLE 1-11 At A, derivation of truth values for X → Y. At B, derivation of truth values for ¬Y → ¬X. the outcomes coincide, demonstrating that the two statements are logically equivalent.
Tables 1-11A and 1-11B show that for any two variables X and Y, the statement
X → Y
is logically equivalent to the statement
¬Y → ¬X
We can write the foregoing theorem entirely in symbols as
X → Y ↔ ¬Y → ¬X
Tables 1-12A and 1-12B show that for any two variables X and Y, the statement
¬(X ^ Y)
TABLE 1-12 At A, derivation of truth values for ¬(X ^ Y). At B, derivation of truth values for ¬X ∨ ¬Y. The outcomes coincide, demonstrating that the two statements are logically equivalent.
is logically equivalent to the statement
¬X ∨ ¬Y
We can write the foregoing theorem entirely in symbols as
¬(X ^ Y) ↔ ¬X ∨ ¬Y
Tables 1-13A and 1-13B show that for any two variables X and Y, the statement
¬(X ∨ Y)
is logically equivalent to the statement
¬X ^ ¬Y
We can write the foregoing theorem entirely in symbols as
¬(X ∨ Y) ↔ ¬X ^ ¬Y
TABLE 1-13 At A, derivation of truth values for ¬(X ∨ Y). At B, derivation of truth values for ¬X ∨ ¬Y. The outcomes coincide, demonstrating that the two statements are logically equivalent.
Tables 1-14A and 1-14B show that for any three variables X, Y, and Z, the statement
X ^ (Y ∨ Z)
is logically equivalent to the statement
(X ^ Y) ∨ (X ^ Z)
We can write the foregoing theorem entirely in symbols as
X ^ (Y ∨ Z) ↔ (X ∨ Y) ∨ (X ^ Z)
We can use truth tables to prove any statement in propositional logic, as long as it’s valid, of course! Consider the rather arcane theorem
[(X ^ Y) → Z] ↔ [¬Z → (¬X ∨ ¬Y]
TABLE 1-14A Derivation of truth values for X ^ (Y ∨ Z).
TABLE 1-14B Derivation of truth values for (X ^ Y) ∨ (X ^ Z). The far-right-hand column has values that coincide with those in the far-right-hand column of Table 1-14A, demonstrating that the far-right-hand expressions in the top rows of both tables are logically equivalent.
Tables 1-15A and 1-15B, taken together, prove that this theorem holds true for any three logical variables X, Y, and Z.
TABLE 1-15A Derivation of truth values for (X ^ Y) → Z.
TABLE 1-15B Derivation of truth values for ¬Z → (¬X ∨¬Y). The far-right-hand column has values that coincide with those in the far-right-hand column of Table 1-15A, demonstrating that the far-right-hand expressions in the top rows of both tables are logically equivalent.
PROBLEM 1-4
What, if anything, is wrong with the truth table shown in Table 1-16?
SOLUTION
Some of the entries in the far-right-hand column are incorrect.
TABLE 1-16 Truth table for Problems 1-4 and 1-5.
PROBLEM 1-5
What single symbol can we change to make Table 1-16 show a valid derivation?
SOLUTION
In the far-right-hand column header (top of the table), we can change the conjunction symbol (^) to an implication symbol (→) so that the header says (X ∨ Y) → Z.
You may refer to the text in this chapter while taking this quiz. A good score is at least 8 correct. Answers are in the back of the book.
1. Consider the following argument: “The stones in Wyoming all fell from the moon. This stone came from Wyoming. Therefore, this stone fell from the moon.” What purely logical flaws, if any, does this argument contain?
A. The first premise is ridiculous, so the argument must lack logical validity.
B. We have no way of knowing whether the particular stone in question really came from Wyoming.
C. We have no way of knowing how stones could fall from the moon.
D. This argument contains no purely logical flaws.
2. Imagine two propositions P and Q. Consider the compound statement A such that
A ↔ P XOR Q
Now consider the compound statement B such that
B ↔ (P ↔ Q)
Which of the following statements is logically valid?
A. A → B
B. A ↔ ¬B
C. B → A
D. ¬A ↔ ¬B
3. According to the principle of identity,
A. no statement can be both true and false “at the same time.”
B. a direct contradiction can imply anything.
C. if a statement is true, then it’s true.
D. every statement must identify a specific object or action.
4. Consider the two statements, “Stan scribbles. Stan is a scribbler.” Respectively, these sentences have the forms
A. SV and SLVC.
B. SV and SVO.
C. SLVC and SVO.
D. SVO and SLVC.
5. In a sound argument, we can have absolute confidence that
A. the conclusion leads to the premises beyond a reasonable doubt.
B. the conclusion leads to the premises beyond any doubt whatsoever.
C. the premises lead to the conclusion beyond a reasonable doubt.
D. the premises lead to the conclusion beyond any doubt whatsoever.
6. Based on the facts about logical conjunction between two variables that we’ve learned in this chapter, we can always do one of the following maneuvers and have confidence that the resulting statement is logically equivalent to the original statement. Which one?
A. We can switch the order of the variables.
B. We can negate the first variable.
C. We can negate the second variable.
D. We can negate both variables.
7. Based on the facts about inclusive logical disjunction between two variables that we’ve learned in this chapter, we can always do one of the following maneuvers and have confidence that the resulting statement is logically equivalent to the original statement. Which one?
A. We can switch the order of the variables.
B. We can negate the first variable.
C. We can negate the second variable.
D. We can negate both variables.
8. Consider the following compound sentence:
¬A ^ B ^ C → D ^ ¬E ↔ ¬F
Which of the following character sequences represents a correct way to rewrite this statement with grouping symbols?
A. [¬(A ^ B ^ C)] → [D ^ ¬(E ↔ ¬F)]
B. {[(¬A) ^ B] ^ C} → {[D ^ (¬E)] ↔ (¬F)}
C. {[(¬A) ^ B ^ C] → [D ^ (¬E)]} ↔ (¬F)
D. {[¬(A ^ B) ^ C] → [D ^ ¬E)]} ↔ (¬F)
9. A conjunction between the negations of two logical variables is always logically equivalent to
A. the negation of the exclusive disjunction between those two variables.
B. the negation of the inclusive disjunction between those two variables.
C. the negation of the implication from the second variable to the first.
D. None of the above.
10. An inclusive disjunction between the negations of two logical variables is always logically equivalent to
A. the negation of the exclusive disjunction between those two variables.
B. the negation of the inclusive disjunction between those two variables.
C. the negation of the implication from the second variable to the first.
D. None of the above.
