TRUTH TABLES
Up till now we have been concerned mainly with the validity of arguments. If a given argument whose validity depends on relationships between statements is valid, then we can prove it so (assuming the completeness of SL, statement logic).
If an argument is an instance of one of the forms we have identified as fallacious, such as the Fallacy of Denying the Antecedent (FDA), then, assuming it is not an instance of a more specific valid form, we know it is invalid. But beyond that, we are stuck. We can prove arguments and their forms (and their corresponding sequents and forms) valid, if we have enough ingenuity; but if we can’t prove them valid, we cannot conclude that they are invalid: it may be our lack of ingenuity. In this chapter we are going to examine techniques (originating with Gottlob Frege in 1879) that enable us to prove the validity or invalidity of any sequent (or sequent form). Given the sequent, we apply the technique and this itself will always yield the result: either valid, or invalid. Such a technique is known in the lingo as a decision procedure, a procedure that will always give you a yes-or-no answer for any choice of values of some input parameters.We begin where we left off in chapter 3 where we introduced the five statement operators as truth-functional. Recall that this means that the truth value (T or F) of any compound statement formed using these operators depends only on the truth values of the component statements. We already exploited the particular ways each of these operators combine statements in formulating our rules of inference, so (with the exception, perhaps, of the pattern belonging to the conditional, which we will come to shortly) the particular patterns of truth values associated with each operator should come as no surprise. We may lay out these patterns in tables called truth tables, one for each operator.
The first is the truth table for negation:This says that if a statement has one truth value, its negation will have the opposite one. Now in our truth tables for & and v we need four rows, because the statement p stands for could be true or false, and for each of these values, the statement q stands for could be true or false. Their truth tables are just what you would expect:
Finally there are the tables for conditionals and biconditionals
The first of these is something you should find a little perplexing. We’ll come back to that later. The second is what we would expect intuitively. Now we may express the truth tables for all the operators together as follows:
The truth table for a truth-functional compound statement of a given form, involving component statements p, q, r,..., is a complete listing of the truth values of that compound corresponding to each possible combination of truth values for the component statements represented by p, q, r,..., written in a column under the governing operator.
For the first component statement there will be 2 possibilities, and for each of these a second component can be true or false, giving four combinations; and for each of these a third component can be true or false, giving (2 ? 2 ? 2 = ) eight combinations; and so on. Writing 2 ? 2 ? 2 as 23, we can see that in general,
A truth table involving n component statements will have 2n rows.
13.1.2 MATERIAL IMPLICATION
What you may have found puzzling about the truth table is this. It says that a conditional is false only if the antecedent is true and the consequent false. From this it follows that (a) the conditional is true if the consequent is true, and (b) the conditional is true if the antecedent is false. This can also be seen by inspecting rows 1 and 2 for (a), and 2 and 4 for (b). Thus by either of these criteria, “If all philosophers are immortal, Socrates is dead” would count as a true conditional! But (a) corresponds to the argument form q.,. p → q, and (b) to the argument form
which we proved valid in exercise 23 of
chapter 11, and 12 of chapter 12. As noted there, these highly counter-intuitive results are known as the Paradoxes OfMaterial Implication. Other examples can easily be created: (a) makes true any conditional with a true consequent, such as “If your underwear is blue then Elvis sold a lot of records,” while (b) makes true any conditional with a false antecedent, such as “If Brazil is in Europe then pigs can fly.” These paradoxical results derive from the fact that when we symbolize a conditional, we do not take into account any relationship of meaning or other connection between the antecedent and consequent, save for the truth-functional one: a conditional is false if the antecedent is true and the consequent false; otherwise it is true. Almost all the conditionals occurring in ordinary language, on the other hand, are considered true because of some non-truth-functional relationship between the antecedent and consequent, such as the meaning connection in the above example between being immortal and being dead, or the causal connection between falling out of a window and breaking a leg.
If such a connection is relevant to the validity of an inference, it needs to be made explicit as an extra implicit premise: here, something like “Someone who is dead cannot be immortal.” This will then relieve the air of paradox. All this is discussed more fully in Appendix 1.13.1.3 TAUTOLOGIES, CONTRADICTIONS, AND CONTINGENT STATEMENTS
The truth table of any given compound statement consists in a column of T’s and F’s written under the main operator. Some statements will have a column consisting only in T’s: that is, the truth value of such compound statements will be T no matter what values the components have. Here is an example: P → (Q → P):
Such a statement with a row of T’s below the governing operator is called a tautology, or logical truth:
A tautology or logical truth is a truth-functional compound statement whose form is such that its truth value is T for each possible combination of truth values of its components: its truth table consists only in T’s.
It is logically true because it is true whatever the truth values of its components are; any compound of this form will be true, no matter what its components. Thus
A tautologous form is a statement form every instance of which is a tautology.
We saw examples of tautologous forms in the previous chapter, where they appeared as statement forms that could be proven true from no premises. For example, a 3-line reductio proves the theorem
(by supposing its negation and applying DM). So
we expect this to be tautologous. A truth table test demonstrates that it is:
Similarly, if the column under the main operator of a compound is all F’s, the statement is Iogicallyfalse, or, a contradiction.
A contradiction or logical falsehood is a truth-functional compound statement whose form is such that its truth value is F for each possible combination of truth values of its components: its truth table consists only in F’s.
It is logically false because it is false whatever the truth values of its components are; any compound of this form will be false, no matter what its components. Thus
A self-contradictory form is a statement form every instance of which is a contradiction.
In setting out this truth table, I have not repeated the columns under p and q on the right side of the table; instead, I have read them directly from the left to compile the columns under p → q and so on. You may always do this, for the sake of the clarity it achieves. I have also put a ’ under the penultimate columns as an aid to calculation, as well as the * under the column for the main operator.
Now most propositions will not be either logically true or logically false. Instead, like the compound statement
above, they will have a column of truth values
underneath the governing operator that is a mix of T’s and F’s. Such statements are called contingent statements.
A contingent statement is a truth-functional compound statement that is neither a tautology nor a contradiction. Its truth table contains at least one F and at least one T.
13.1.4 LOGICAL EQUIVALENCE
In discussing material implication above, we saw that p → q and its equivalent
have the same truth table: that is, one is T in exactly the same rows the other is T, and F wherever the other is F. This is true also of the other equivalence rules of inference. Indeed, any two statements that mutually entail one another, and may therefore be substituted one for the other, will have the same truth table.
Two statements p and q having the same truth table column under their governing operators are logically equivalent.
Alternatively, we may define it in terms of mutual entailment. Introducing some obvious 
In the first case we could have Conditionalized the conclusion on the premise, getting:
SUMMARY ________________________________________________________________
• A truth table for a truth-functional compound statement of a given form is a complete listing of the truth values (T or F) of that compound corresponding to each possible combination of truth values for the component statements, written in a column under the governing operator.
• The truth tables for the various truth-functional operators may be summarized thus:
• A truth table involving n simple statements will have 2n rows.
• A tautology or logical truth is a truth-functional compound statement whose form is such that its truth value is T for each possible combination of truth values of its components: its truth table consists only in T’s.
• A contradiction or logical falsehood is a truth-functional compound statement whose form is such that its truth value is F for each possible combination of truth values of its components: its truth table consists only in F’s.
• A contingent statement is a truth-functional compound statement that is neither a tautology nor a contradiction. Its truth table contains at least one F and at least one T.
• A tautologous form is a statement form every instance of which is a tautology.
• Likewise, a self-contradictory form is a statement form every instance of which is a contradiction.
• Two statements p and q are logically equivalent iff each entails the other, p -W- q. Logically equivalent statements will have identical truth table columns under their governing operators.
EXERCISES 13.1
1. For each of the following abstract statements, determine using a truth table whether it is a tautology, a contradiction, or a contingent statement: 
13.2 TRUTH TABLES AND VALIDITY 201
Symbolize each of statements 2-5, and determine using a truth table whether it is a tautology, a contradiction, or a contingent statement;
2. A television reporter describing a dilemma facing government officials said: “They’re DAMNED if they do [take a certain ACTION], or damned if they don’t.”
3. The reporter perhaps meant to say:
“They’re DAMNED if they do [take a certain ACTION], and damned if they don’t.”
4. The head of the Longshoreman’s Union, when asked if his union should boycott shipments to England if that country did not give autonomy to Northern Ireland, said: “I don’t think we’ll HAVE to go that far unless we have to.”
5. The famous English philosopher G.E. Moore regarded this statement as a contradiction—was he correct?:
“If A had not HAD P, it would not have been true that A did not have P.”
6. For each of the following abstract statements, determine using a truth table whether it is contingent, tautologous, or self-contradictory:
7. Using truth tables, prove the following logical equivalences: 
13.2