Class Notes (811,705)
United States (314,697)
Philosophy (46)
2250 (23)

N05TFCompleteness - Truth Functional Completeness.pdf

14 Pages
Unlock Document

James Hildebrand

The truth functional completeness of SL The question of the truth functional completeness of SL is the question of whether SL is an adequate language for sentential logic. Can it be used to symbolize all the forms that truth-functionally compound sentences can have? Recall that a truth functional connective is a connective that builds a compound sentence that is always exactly one of true or false depending on the truth values of the component sentence(s) it connects. At first sight it seems that SL could not possibly be truth-functionally complete, because it contains only one unary and four binary connectives, and there are many more. For example, speaking in English, I can say “It is neither raining nor snowing.” This is a compound sentence of English. It is compounded from two simple sentences, “It is raining,” and “It is snowing,” using the English connective, “[It is] neither [the case that] … nor [the case that] …” Moreover, this connective is a truth-functional connective. For each combination of truth values that might be assigned to the component sentences, the connective determines a unique truth value for the compound. The sentence, “It is neither raining nor snowing” is true if and only if both the sentence “It is raining” and the sentence, “It is snowing” are false. In all other cases — if one or the other is true or both are (which sometimes happens) — the compound sentence is false. This rule does not correspond to any of the rules for the five connectives of SL. So it looks like SL comes up short at giving us symbols for one of the truth functional connectives of English — “neither … nor …,” which assigns truth values in accord with a rule we do not have a connective to represent. Nor is this the only such case. In English the connective “Either … or …” is often used in what is called a “strong” or “exclusive sense.” If I say, “I will either take early retirement or accept the promotion,” someone could accuse me of lying if I did both (as well, of course, as if I did not do either). So, when used in this sense, “either … or …” builds a compound sentence that is true if and only if exactly one of its component sentences is true, but that is false when either both are true or when both are false. Again, a survey of the rules for the connectives of SL shows that we have no connective that assigns truth values to compound sentences in this way. Once again, SL comes up short at providing us with symbols for truth-functional connectives that exist in English. Just how bad is this problem? How many connectives has SL failed to symbolize? To help us grasp the magnitude of this problem, I here introduce the notion of a “characteristic truth table.” The textbook introduces this notion early in chapter 2 and again in chapter 3.1, but I have avoided using it up until now because the connectives of SL are better understood by understanding their semantic rules and truth tables are constructed with fewer mistakes when constructed in accord with the semantic rules. There has therefore been no call to speak of characteristic truth tables. Now, the proper occasion has arisen to introduce them. 2 A characteristic truth table is a truth table that represents what assignments a truth function makes under each of the possible circumstances. For example, a unary truth function makes an assignment under two possible circumstances: when a sentence is true, and when it is false. The negation truth function does this, and we represent the assignments it makes under these circumstances on a characteristic table as follows: ~ T F F T The table tells us that when a sentence (be it atomic or compound) is true, the negation function assigns an F, and when it is false the function assigns a T. Similarly, a binary truth function makes an assignment under four possible circumstances: when two sentences are true, when one is true and the other is false, when the one is false and the other is true, and when both are false. The characteristic tables for &, v, ⊃, and ≡ specify what assignments the conjunction, disjunction, conditional, and biconditional truth functions make under each of these possible circumstances. They look like this: & v ⊃ ≡ T T T T T T T T T T T T T F F T F T T F F T F F F T F F T T F T T F T F F F F F F F F F T F F T If we want, we can add characteristic tables for the two English connectives I mentioned earlier, for purposes of comparison. To make the comparison easier, I here collect all the separate tables together onto one and use “↓” to symbolize the “neither … nor …” truth function and “/” to symbolize “either … or … but not both.” & v ⊃ ≡ ↓ / T T T T T T F F T F F T F F F T F T F T T F F T F F F F T T T F Here you see exactly how the different rules for the English connectives dictate different characteristic truth tables. Looking at these tables, you might be struck by something. “Neither … nor …” is the contradictory of “v.” All we need to do is consider the truth tab efor ~(… v …) and w arrive at the truth table for “Neither … nor …” Similarly, “Either … or … but not both” is 3 the contradictory of “≡.” All we need to do is consider the truth table for ~(… ≡ …) and we arrive at the truth table for “Either … or … but not both.” v ~( v ) ↓ ≡ ~( ≡ ) / T T T F F T F F T F T F F F T T F T T F F F T T F F F T T T F F In light of this discovery you might start to think that perhaps we don’t need to worry that SL does not have enough connectives to represent all the truth functions. Granted, we have no special symbol in SL for either a “neither … nor …” or a “strong or” truth functional connective. But it looks like we can construct sentences of SL that are truth functionally equivalent to sentences made using these missing connectives. So we don’t need the missing connectives. When we run into English sentences that use these truth functions we can “translate” them into slightly more compound sentences of SL that use only the connectives we have available, but that mean exactly the same thing (that is, that receive the same truth values on all possible truth value assignments). We can translate “neither … nor …” as ~( … v …), and we can translate the “strong or” as ~( … ≡ …). The former is not surprising if you think of “Neither” as a slurring of “Not (either … or …).” But we are not quite out of the woods yet. We have only considered two English truth functional connectives that are not symbolized in SL. There may be others. How do we know that we can handle all of them in the way we have just handled “neither … nor …” and the “strong or?” Let me make the question I am asking a bit more precise by introducing a notion that the textbook brings up in Ch. 6.2: that of a sentence that “expresses” a truth function. We will say that a sentence of SL expresses a truth function if and only if it has the same column of T’s and F’s under its main connective that appears on the characteristic truth table for that truth function. So, trivially, the sentence “A v B” expresses the “v” truth function and, non-trivially, the sentence “~(A ≡ B)” expresses the “strong or” truth function. The question we are asking is whether, for any compound sentence of English or any other natural language, compounded using any truth functional connective of that language, there is a sentence of SL that expresses that truth function: that has the same column of T’s and F’s under its main connective as appears on the characteristic truth table for the truth function. This question begs a prior one: just how many truth functions are there anyway? Considering things in terms of characteristic truth tables gives us a way to begin to answer this question. Let’s begin by asking just how many unary truth functions there could be. If we consider just unary truth functions, we can see that only four are 4 possible. There is the truth function that assigns a T to the compound sentence, regardless of the truth value of its immediate component; the truth function that assigns the same truth value to the compound sentence that its immediate component has; the truth function that assigns the opposite truth value to the compound sentence that its immediate component has; and the truth function that assigns an F to the compound sentence, regardless of the truth value of the immediate component. The four possible truth functions are listed on the following table. Obviously, there can be no others. P U1 U2 U3 U4 T T T F F F T F T F (The characteristic truth tables for the 4 truth functions are here amalgamated on one table, but you should think of the left hand column and one of each of the other columns as making up 4 separate characteristic tables.) As it turns out, both English and SL use only one of these truth functions, #3. Perhaps that is because there is not much point to using the others. We have no use for a unary connective that does not change the truth value of its immediate component — it is redundant — and no interest in ones that draw no distinctions and just make everything true and everything false. Nonetheless, there are sentences of SL that express the U1, U2, and U4 truth functions, and that therefore can be substituted for them wherever we might have a need to do so; namely, the sentences (P v ~P), P, and (P & ~P). And, of course, ~P does the job for U3. Each of these sentences has the same column of T’s and F’s under its main connective as appears on the characteristic truth table for that truth function. (P v ~P) is true on any tva, P always has the same truth value as itself wherever it occurs, ~P has the opposite truth value of P on any tva, and (P & ~P) is always false on any tva. Now what about binary truth functions? There are 16 different ways of mapping four pairs of truth values onto a single column of truth values, and hence 16 different binary truth functions. Beginning with the one that assigns a T in all circumstances and ending with the one that assigns an F in all circumstances they are: B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 B11 B12 B13 B14 B15 B16 T T T T T T F T T F T F F T F F F F T F T T T F T T F T F T F F T F F F F T T T F T T F T T F F T F F T F F F F T F T T T F F F T T T F F F T F It is an entertaining exercise to run through this list and try to think up sentences of SL that express each of these truth functions. And we might think that if we can do this, then we are out of the woods and can consider SL to have the resources to represent any truth function and so to be a complete language for doing truth functional logic. 5 But we aren’t out of the woods, because there is no reason to limit connectives to unary and binary truth functions. There can be trinary or three place connectives that connect three sentences into a compound sentence, four-place connectives, five-place connectives, and so on without end. And these connectives can be truth-functional — they can have their own rules for determining truth values for the compound sentence in all possible circumstances. So we need to worry about three-place truth functions, four- place truth functions, and so on without end. Since there are 8 possib8e ways for two truth values to be distributed over three sentences, there are 2 or 256 different possible three-place truth functions. There are 65,536 different possible 4-place truth functions. And, to repeat, there is no limit to how many places a connective can have. (The formula for hownmany different truth functions there are for n sentences is 2 raised to the power of 2 .) We are not going to be able to satisfy ourselves by brute force that SL is adequate to express all of these truth functions, that is, by running through each of the possible truth functions in turn and finding a sentence of SL that expresses it. There are too many for that — infinitely many. Neither can we dismiss this problem by saying that we don’t have names for any higher place connectives in English and so can safely ignore them. Even if that were true (and English is surprisingly more resourceful than you might think at first, as we will see in a moment), we don’t want SL to be a language that is adequate just for the truth- functional logic of speakers of English. We want SL to be adequate for speakers of any language whatsoever, even super-intelligent speakers of massively complex languages that don’t exist. So how can we be assured that SL is truth functionally complete —that there is a sentence of SL that will express any truth function? We can get that assurance if we can come up with an algorithm for constructing a sentence of SL that will express any truth function anyone chooses to be worried about. An algorithm is a mechanical procedure — a routine sequence of steps — that is guaranteed to produce the right result. If we can come up with such an algorithm for constructing sentences of SL that express truth functions, then we won’t need to run through all the infinitely many truth functions to check if SL can handle each of them. We will be able to be assured that given any one of them, we can simply apply the algorithm and be assured of getting the sentence we are looking for. To satisfy your curiosity, here is that algorithm. WARNING: there are some concepts that will have to be further explained. I will also need to explain why the algorithm is guaranteed never to fail. 6 The sentence of SL that expresses any arbitrarily given truth function is the disjunction of the characteristic sentences for each line of the characteristic table on which the truth function assigns a T. If there are no such lines it is the conjunction of the characteristic sentence for the first line and its negation. Now for the explanations. Remember that each truth function has its own characteristic truth table. Here, by way of example, is a characteristic truth table for an arbitrarily selected three-place truth function, “T?,” — one of 256 others. ?T T T T T T T F F T F T F T F F T F T T F F T F F F F T F F F F T This table tells us that this mystery truth function assigns a T to a compound of three immediate components if and only if either each of the components is true, or the first is true and the others are false, or all are false; otherwise it assigns an F to the compound. We don’t care whether there is an English name for this truth function. — Though there is: “All or none or just the first of A, B, and C.” Some might quibble that this is not a single English name for a three-place truth function but a des ing English names for a number of simpler truth functions. They are party-poopers (though they would have a fine time trying to incorporate “all,” “none,” and “just the first of” into SL). Regardless, the point is that there is such a truth function, whether it has its own name in English or not, and we want to know if SL can express it. Let’s proceed with showing how there is an effective procedure for constructing a sentence of SL that will express this (or any other) truth-function. To begin with, we will use our stock of atomic sentences of SL to name the columns on the left side of a characteristic table, taking them in alphabetical order and going from left to right. So the left side of the characteristic table given above will look like this: 7 A B C T T T T T F T F T T F F F T T F T F F F T F F F Now note that for each (horizontal) row on this partial truth table below the first, there is a sentence of SL (one using just the atomic sentence letters listed on the top row of the characteristic table, and the connectives “~” and “&”) that is true if and only if its atomic components get the truth value assignments specified on that row and that is otherwise false. We call this the characteristic sentence for that line. The characteristic sentence for a line on a truth table is, firstly, the iterated conjunction of each of the atomic sentence letters on the top row of the table. An iterated conjunction is created by taking the first two sentence letters from the left and making a conjunction using them, then taking that conjunction and making a conjunction with the next atomic sentence letter over
More Less

Related notes for 2250

Log In


Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.