|
Symbolic Logic |
More review material regarding the topics we have covered that are not included in our text. (Note: this page will not display correctly if you don't have the Symbol and Lucida fonts installed, and even then it won't look right in Netscape. Let me know if you have problems reading the symbols.)
A yes-or-no question is decidable if there is a procedure that is guaranteed to give an answer to the question in a finite amount of time. A logical system such as a system of propositional logic or a system of first-order logic is decidable if, for every argument expressible in the language of the system, the question whether the argument is valid is decidable.
(Actually, given the way Barwise and Etchemendy use the term "valid," this formulation is not quite correct. Larger(a,b), therefore Smaller(b,a) is valid in B&E's sense, but a decidable system does not need to provide a method for determining whether any argument is valid in this ordinary-language sense. Rather, the issue of decidability concerns the more precise and restricted conceptions of validity developed for propositional logic and first-order logic. A system of propositional logic is decidable if the question whether an argument is tautologically valid is decidable; a system of first-order logic is decidable if the question whether an argument is FO-valid is decidable.)
[You can skip bracketed material if you wish, but it may help to make these ideas more precise and clear. Let us define a metalogical relation╞ as follows: P1, . . ., Pn ╞ C iff there is no interpretation on which P1, . . ., Pn are all true and C is false. This is a way of making the notion of validity more precise. Of course what it means depends on what exactly an interpretation is. That question will be answered differently for propositional logic than for first-order logic as a whole: see bracketed comments below.]
Propositional logic is clearly decidable: that is, for any argument from premises P1, . . ., Pn to conclusion C, we can determine in a finite amount of time whether the argument is valid or not. We can do this by constructing a truth table. If there is a row in which P1, . . ., Pn are all true and C is false, then the argument is not valid; otherwise, it is valid. Constructing a truth table is a computationally expensive procedure, since it requires exponential time, namely O(2n) where n is the number of distinct atomic sentences in the argument. Still, since every argument is finite, a truth table for a given argument is guaranteed to be finite, even though it may be very large.
[To be a little more precise, we can specify what we mean by an interpretation in propositional logic. An interpretation of a set of sentences is determined by an assignment of truth values to the atomic sentences out of which they are constructed. (The interpretations of the compound sentences are then determined by the truth tables for the propositional connectives.) Consider the argument P, P®Q, therefore Q. An interpretation for this argument is determined by an assignment of truth values to the atomic sentences P and Q. (We also have the sentence P®Q, but its truth value is determined by the truth values for P and Q together with the truth table for the conditional.) Now, P1, . . ., Pn ╞ C iff every interpretation that makes P1, . . . Pn all true also makes C true. How many distinct interpretations are there for the set of sentences {P1, . . ., Pn, C}? Well, an interpretation is completely determined by an assignment of truth values to atomic sentences. Every atomic sentence can be either true or false. So we have two possibilities for the first atomic sentence, times two possibilities for the second . . . times two possibilities for the nth. So if we have n atomic sentences, we have 2n distinct interpretations. In fact, this is exactly what a truth table enumerates: each of the 2n rows of a truth table represents a distinct interpretation.]
Predicate logic with only 1-place predicates is also decidable, although this is less obvious. The trouble with predicate logic is that its basic building blocks are not atomic sentences, but rather predicates and objects. For example, a sentence 'Pred(a,b)' is true iff the predicate Pred is true of the ordered pair <a,b> of objects denoted by the names 'a' and 'b'. A quantifier sentence such as "x"y Pred(x,y) is true iff every Pred(x,y) is true of every pair of objects <x, y>! So to determine whether a quantifier sentence is true, we need to specify a domain of objects; a universal sentence is true if every instance we can construct using objects in the domain makes it true, and an existential sentence is true if at least one instance using an object in the domain is true. Now, an argument is valid only if the conclusion follows from the premises for any domain we choose. And we cannot restrict ourselves to finite domains only; for instance, we may want to construct arguments involving the natural numbers or the real numbers, and these require domains that are infinitely large! (In fact nondenumerably large for the real numbers.)
So the basic problem with predicate logic is that, in order to determine whether there is a counterexample to an argument, we may need to consider an infinite number of distinct interpretations, and of course we can't exhaustively search an infinite number of cases, so the truth-table style investigation will not work.
[That was a little quick and dirty. To get slightly more precise, an interpretation for predicate logic includes a set of objects constituting the domain of quantification, and interpretation functions that assign to every name an object in the domain and to every n-ary predicate a set of n-tuples of objects in the domain. Suppose we have the argument "xPred(x), therefore Pred(a). One possible interpretation will have a domain of three objects: {o1, o2, o3}. The interpretation also must specify the set of objects of which Pred is true: if 'I('Pred')' represents the result of applying the interpretation function to the predicate 'Pred', then one example would be I('Pred') = {o1, o2}. Finally, our interpretation will also need to assign an object from the domain to the name 'a': for example, I('a') = o2. Obviously there are going to be a lot of interpretations even for an argument this simple and even if we only consider small domains! For our domain of size 3, we will have 3 distinct interpretations of the name 'a' and 8 distinct interpretations of 'Pred' (1 of size 0, three of size 1, three of size 2, 1 of size 3), for 3 * 8 = 24 distinct interpretations altogether. But matters are far worse even than this suggests, for validity requires a judgment about all possible interpretations, so we need to consider interpretations with domains of every possible size, and as we saw in the last paragraph there are an infinite number of these!]
Luckily, if we have one-place predicates only, there is a theorem showing that if there is a counterexample to an argument at all, then there will be a counterexample of size 2k, where k is the number of distinct predicates the argument contains. So in fact we can do an exhaustive search to determine whether an argument is valid, if we have only one-place (unary) predicates. This is a computational nightmare -- we will have 2 to the power 2k distinct interpretations of each one-place predicate, and since we must consider all possible combinations of these interpretations, we will have (2 to the power 2k)k distinct combinations of interpretations for the predicates. In practice, for large arguments, exhaustive search through all interpretations of size 2k will not be very practical. Nevertheless, it does at least give us a decision procedure.]
First-order logic in all its glory, including predicates with more than one argument place, is a different story. In this case, there is no guarantee that an invalid argument will have a finite counterexample.
In fact, there are examples of invalid arguments where there demonstrably are no counterexamples with a finite domain, but only counterexamples with infinite domains.
Here is an example:
"x$yR(x,y)
"x"y"z((R(x,y) Ù R(y,z)) ® R(x,z))
Therefore,
$xR(x,x)
As we discussed in class, as long as our domain is finite, the premises cannot be true unless the conclusion is also true (no matter what the predicate R means). However, in an infinite domain we can easily see that the argument is not valid. For example, if the domain is the natural numbers and the predicate R(x,y) means x > y, then clearly the premises are both true (for every natural number, there is another that is greater, and the > relation is transitive), but the conclusion is false (no natural number is greater than itself).
But the fact that there may be only counterexamples with infinite domains means that we cannot conclusively determine whether there is a counterexample by using exhaustive search.
Want to read more about this stuff? Our text gives a formal definition of interpretations (which our authors call "structures") in chapter 18.1. There is a good, brief, accessible discussion of decidability issues (on which I have drawn) in Graeme Forbes, Modern Logic (Oxford, 1994), pp. 207-211, 283-286.
|
Curtis Brown | Symbolic Logic | Philosophy Department | Trinity University cbrown@trinity.edu |