So far, we have learned the formal syntax of the language of sentential logic, but as yet, we have talked only informally about how to interpret and evaluate the formulae of sentential logic. In this chapter, we learn the SEMANTICS of sentential logic, which will provide us with the tools, techniques, and vocabulary we need to interpret and evaluate not only individual formulae, but also inferences as they are represented in sentential logic.
GOALS FOR THIS CHAPTER:
As we have already mentioned, our primary interest in sentential logic has to do with the TRUTHVALUES of the formulae of sentential logic. We have already learned how the basic expressions of sentential logic combine, in accordance with the syntactic rules, to form compound formulae. The syntactic rules thus allow us to determine, for any particular expression, whether or not that expression constitutes a grammatical formula of sentential logic. Similarly, the semantic rules for sentential logic will allow us to determine the truthvalue of any formula, given that we know the truthvalues of all the atomic formulae involved.
Great, but what if we don't know the truthvalues of all the atomic formulae? Well, we can still determine what the truthvalue of the formula will be for any possible assignment of truthvalues to atomic formulae. Such an assignment of truthvalues to atomic formulae is, appropriately enough, known as a TRUTHVALUE ASSIGNMENT.
A TRUTHVALUE ASSIGNMENT consists of an assignment of a truthvalue (either true or false) to every atomic sentence of sentential logic, not just those atomic formulae that appear in some particular formula.
Okay, so this means that we can determine the truthvalue of any formula of sentential logic, relative to a given truthvalue assignment. Obviously, if our formula is an atomic sentence, all we need to do is to see what truthvalue it has been assigned in order to determine what its truthvalue is on that assignment. What about compound formulae? You may recall that we've mentioned that the logical connectives are all TRUTHFUNCTIONAL.
This means that the truthvalue of a compound formula is a FUNCTION of the truthvalues of its components.
In order to see how this works, we should go on to take a look at the semantics of the connectives.
We have already discussed, though informally, the truthfunctions we take to correspond to our logical connectives. So far, we have relied only on an intuitive understanding of the truthfunctions our connectives represent, but it is now time to make explicit the truthfunctions at work, as well as to provide a formal means, known as TRUTHTABLES, for representing them.
Recall our first example of a conjunction from the previous chapter:
Now, this sentence would be considered to be true just in case it was true both that John ran, and that Mary laughed. If John didn't run, the conjunction would be false, and similarly if Mary didn't laugh. This intuitive and informal understanding of the TRUTHCONDITIONS of the conjunction, that a conjunction is true just in case both of its conjuncts are true, and false otherwise, is precisely what we want to capture formally. We can do this in a tabular form, by specifying the truthvalue of a conjunction for each possible combination of truthvalues that the two conjuncts can take on. Here's the truthtable for this particular conjunction:
J  M  J & M 

T  T  T 
T  F  F 
F  T  F 
F  F  F 
After looking only briefly at the above truthtable, it should be pretty clear what is going on, but it can't hurt to go through it explicitly in any case.
In our truthtable, we have three columns: One for the conjunction itself, plus one for each of the two atomic formulae appearing in the conjunction. As for rows, this truthtable has four (not including the header row, where we specify the atomic formulae and the compound formula), just enough to include every possible combination of the truthvalues T (for true) and F (for false) that the two atomic formulae can have. The entries in the conjunction's column specify the truthvalue of the conjunction given that the conjuncts have the truthvalues indicated in the same row.
Each of the rows in the truthtable thus represents a set of truthvalue assignments—the set of truthvalue assignments where the atomic formulae listed in the truthtable are assigned the truthvalues specified on that row. The first row of the truthtable thus represents all truthvalue assignments where the atomic formulae J and M are both assigned the truthvalue T. This includes the truthvalue assignment where J, M, and, say, R are all assigned the truthvalue T as well as the truthvalue assignment where J and M are assigned T, but R is assigned F, and so on for every atomic formula not mentioned in the truthtable.
Now, in the truthtable above, we listed some specific atomic formulae. The truthtable thus tells us what the truthvalue of the conjunction of those two particular atomic formulae will be on any truthvalue assignment. We would like, however, to have a way to represent the relationship between the truthvalue of a conjunction and the truthvalues of its conjuncts in a general way, rather than just specific instances of the relationship, like in the example above. We can do this with a truthtable by using variables in place of specific formulae for the conjuncts, as follows:
P  Q  P & Q 

T  T  T 
T  F  F 
F  T  F 
F  F  F 
This truthtable, since it doesn't mention any specific formulae, we call the CHARACTERISTIC truthtable for conjunction.
So far, we have only seen the characteristic truthtable for conjunction. We should go on and take a look at the truthtables for the other connectives, then we will be able to see how to construct a truthtable for any formula of sentential logic.
Here's the truthtable for disjunction:
P  Q  P v Q 

T  T  T 
T  F  T 
F  T  T 
F  F  F 
The truthtable specifies that a disjunction is true on any truthvalue assignment where either one or both of the disjuncts is true, and false just in case both of the disjuncts are false. Recall our example disjunction from the last chapter:
EXAMPLE:
 Either John ran, or Mary laughed.
The truthtable tells us that this sentence will be false only if it is both false that John ran, and false that Mary laughed. If either of the two disjuncts is true (including the case where both disjuncts are true), on the other hand, then the sentence as a whole will be true as well.
Moving on to the last of our binary connectives, here is the truthtable for the conditional:
P  Q  P → Q 

T  T  T 
T  F  F 
F  T  T 
F  F  T 
As you can see, a conditional is false just in case its antecedent is true, and its consequent false. If either the antecedent is false or the consequent true, then the conditional as a whole will be true.
Our final connective is negation. Since negation is a unary connective, we only have one component formula to worry about in the truthtable. The characteristic truthtable for negation will thus have only two rows, since the single formula can be either true or false. Here's the truthtable itself:
P  ¬P 

T  F 
F  T 
Now that we've seen the truthtables for each of the connectives, we can go on to learn how to use truthtables to semantically evaluate any formula of sentential logic.
The first thing we need to know with respect to using truthtables is just how the characteristic truthtables for the connectives allow us to determine the truthvalue of a particular formula on a given truthvalue assignment. There's actually a rather handy way to do that using parse trees, which we did promise in the last chapter would have semantic, as well as syntactic applications, after all. Let's take a look and see how:
Now that we know how to use the characteristic truthtables for the connectives in combination with the parse tree for a formula to determine that formula's truthvalue on a given assignment, let's continue on to see how we can construct a truthtable for the formula that specifies its truthvalue on any truthvalue assignment.
In order to construct a truthtable for an arbitrary formula of sentential logic, the first thing you need to do is to count the number of different sentential letters that occur as subformulae of the formula as a whole. This will tell you how many rows you are going to need in your truthtable. As we have seen, if there's only a single atomic formula, you'll need two rows, and with two atomic formulae, you'll need four rows. See if you can determine how many rows you'd need for larger numbers of atomic formulae, then read on.
Now that you've thought about it, you've likely realised that every additional atomic formula involved is going to double the number of rows you'll need in your truthtable. Thus, for a formula containing three atomic formulae, you need a truthtable with eight rows, for four you'd need sixteen rows, five atomic formulae would require thirty two rows, and so on. Actually, you need 2 to the power of n rows in a truthtable for a formula containing n different atomic formulae as subformulae.
Once you know how many rows you need, you can begin to construct your truthtable by setting out the rows and columns.
EXAMPLE:
(P & Q) → ¬R
Pretty simple, actually. We have now determined the truthvalue of our formula (P & Q) → ¬R on every possible truthvalue assignment. We just have to find the row where the truthvalues assigned to P, Q, and R match the assignment we're interested in, and the above truthtable will tell us whether our formula is true or false on that assignment.
Let's take a look at one more example, just to make sure we have the hang of it all. Consider the following:
That's all there is to it. Now that we know how to construct a truthtable for any formula, why don't we head on to the next section, where we will take a look at the formal version of what we have learned so far about the semantics of sentential logic.
So far, we've had a good look at truthtables and how to use them, but we haven't yet done anything in the way of formally stating the semantics of sentential logic. We should take a moment at this point to present a formal definition of truth with respect to a truthvalue assignment, much as we formally stated the syntactic rules in the last chapter.
Without further ado, here it is:
There you have it. You'll note that the truthconditions specified in the above formal definition match those provided informally by the characteristic truthtables for the connectives precisely.
Believe it or not, this one little definition gives us everything we need to determine the truthvalue of any formula on a given truthvalue assignment. We have yet to consider the situation with respect to all truthvalue assignments, however, so we really should proceed to the next section in order to do just that.
So far, all the formulae for which we have constructed truthtables have turned out to be true on some truthvalue assignments, and false on others. Such formulae are called CONTINGENT, since their truthvalues depend on the particular truthvalue assignment under consideration.
A CONTINGENT FORMULA is true on some truthvalue assignments and false on others.
There are also formulae, however, that turn out to be true on every possible truthvalue assignment, and similarly, some that turn out to be false on every possible truthvalue assignment. As an example of the former, here's the truthtable for the formula: P v ¬P
P  P  v  ¬P 

T  T  F  
F  T  T 
As you can see, this formula turns out to be true on every possible truthvalue assignment, i.e., on every row of its truthtable.
Formulae that are true on all truthvalue assignments are called TAUTOLOGIES.
You've probably already realised that the negation of any tautology is going to be false on every truthvalue assignment, but here's the truthtable for the negation of our tautology P v ¬P to demonstrate this:
P  ¬  ( P  v  ¬P 

T  F  T  F  
F  F  T  T 
Formulae that are false on every truthvalue assignment are known as CONTRADICTORIES.
Of course, not all contradictories are negations of tautologies, as the following example demonstrates:
P  P  &  ¬P 

T  F  F  
F  F  T 
The negation of this formula, on the other hand, is a tautology, since it will be true on every possible truthvalue assignment.
Now that we've learned how to semantically classify individual formulae of sentential logic, and how to use truthtables to determine the classification of a particular formula, it's time to move ahead and take a look at inference from a semantic perspective.
As you will recall from the introduction, we consider an inference to be a good argument just in case its premises are all true, and those premises furthermore support the conclusion. The kind of support we are most interested in is, of course, deductive validity, which we can now characterise in terms of truthvalue assignments to the inferences involved.
An inference is DEDUCTIVELY VALID (or SOUND) just in case any truthvalue assignment that makes all the premises of the argument true also makes the conclusion true. An inference will thus be INVALID just in case it is not valid, i.e., if there is some truthvalue assignment that makes the premises of the argument true, but the conclusion false.
Now that we know how to use truthtables to determine the truthvalue of a formula on any truthvalue assignment, we can apply this technique to the premises and conclusion of an argument, symbolised as formulae of sentential logic, in order to determine with certainty whether or not an argument is valid. We just need to be careful to ensure that we take into consideration all the right truthvalue assignments.
Consider the following conversation:
EXAMPLE:
Hilbert: It's raining outside. Godel: If it's raining outside, then Kant won't stop at the grocery store to buy ice cream. Socrates: If Kant doesn't stop at the grocery store to buy ice cream, then we will have to settle for cookies for dessert. Hilbert: Alas, we will thus have to settle for cookies for dessert.
Interpreting this as an argument, we can symbolise it as follows:
R 
R → ¬K 
¬K → S 

∴ S 
We can make a truthtable for all the premises plus the conclusion by first noting the atomic formulae that occur as subformulae of any premise or of the conclusion, then setting up the truthtable for all such atomic formulae. We include a column for each of the premises and also the conclusion. Here's what the resulting table looks like:
R  K  S  R  ( R  →  ¬K )  ( ¬K  →  S )  S 

T  T  T  T  F  F  F  T  T  
T  T  F  T  F  F  F  T  F  
T  F  T  T  T  T  T  T  T  
T  F  F  T  T  T  T  F  F  
F  T  T  F  T  F  F  T  T  
F  T  F  F  T  F  F  T  F  
F  F  T  F  T  T  T  T  T  
F  F  F  F  T  T  T  F  F 
In order to determine whether the argument is valid or not, we now look for any rows in this truthtable where all the premises are true. In this case, there is only one such row—the third one—and the conclusion is true on this row, so the argument is shown to be valid.
Put text here
Construct truthtables for each of the following formulae:
Construct truthtables for each of the following formulae:
Construct truthtables for each of the following formulae:
For each of the above formulae, indicate whether it is a tautology, contigent, or contradictory.
Determine whether each of the following arguments is valid or invalid. If it is invalid, specify a truthvalue assignment that provides a counterexample:
i  

ii  

iii  

iv  

v  

vi  

vii  

viii  

ix  

x  

xi  

xii  
