Truth Tropic Language II
- The Propositional Calculus (from last time)
- PC Entailments and Theorems (pdf, from last time)
- PC Translations(pdf, from last time)
We began today by revisiting our definition of validity in terms of truth tables and working some more problems to see how the definition plays out in practice.
Recall the general definition of validity: An argument is valid iff it is impossible for the conclusion to be false when all the premises are true.
Since the rows of a standard truth table represent all the possibilities, this is equivalent to saying: A PC argument is valid iff on no row of a standard truth table are all the premises true but the conclusion false. Equivalently, a PC argument is valid iff on every row of standard truth table where the premises are all true, the conclusion is also true.
Note that the handout above, PC Entailments and Theorems, gives lots of practice examples of valid arguments (entailments) for you to practice. Note also that apart from correctly filling out the truth values for the individual sentence letters--the 'standard' in standard truth table--there is no one right way to proceed. You can use temporary columns to keep track of your work, as I do, or you can break expressions apart and put them side by side to be evaluated each in turn, as Gabby neatly showed you how to do. What does matter is that clearly indicate those rows on which all the premises are true so as to verify (display) that the conclusion is also true on those rows--therewith demonstrating that it is impossible for the conclusion to be false when all the premises are true, going back to the general definition of validity.
Truth tables are useful in another regard as well. It turns out there is a special class of PC WFFs that are true on every row. Since the rows represent all the possibilities, it is impossible for these PC WFFs to ever be false. They are necessarily true, and we call them 'theorems of PC'. They are also known as tautologies, necessary truths, or laws of logic.
As useful as truth tables are for defining (in a transparent way) validity (and theoremhood!), they quickly become unwieldy, perhaps even unworkable. After all, by the formula for filling out a standard truth table, the number of rows for formulas with four distinct sentence letters is 16--complicated, but not awfully so. The number of rows for formulas with 5 distinct sentence letters is 32, 6 gives you 64 rows, and a mere 7 distinct sentence letters requires a whooping 128 rows!
Surely there is a better, more economical approach. And, indeed, there is: the dauntingly named method of Analytic Tableaux.
Indeed, the method of Analytic Tableaux provides an elegant alternative.
To be sure, our definition of validity is a little more complicated when it comes to Analytic Tableaux, involving as it does the concept of a Semantic Tree (also called a Truth Tree.) It takes us three steps, thusly,
First, we say that a PC argument is valid iff a Semantic Tree which i) asserts all the premises while ii) denying the conclusion dies.
Second, we note that a Semantic Tree dies iff every branch of the Tree dies.
Third, and finally, we specify that a branch of a Semantic Tree dies iff it both asserts and denies the same PC-WFF--that is, iff a contradiction can be found on it, no matter how far back up the trunk we must track.
That is, if on any branch (and extending perhaps all the way back up the trunk, but never hopping over to a nearby branch!) we find a formula and its negation, we have shown that the branch dies.
Lastly, it bears pointing out that when we assert a PC-WFF on a Semantic Tree, we simply write it, but when we deny it, we write its negation. This should make sense: To deny a proposition is simply to assert its negation.
All of this boils down to both a definition of validity and a method for determing when we have valid arguments.
The Method of Analytic Tableaux
Suppose we have a PC argument and we wonder whether it is valid--whether, that is to say, the premises entail the conclusion. They do if, and only if, it is impossible for them to all be true and the conclusion false at the same time. Put another way, it is impossible to assert each of the premises on a tree while denying the conclusion--which, as we've seen, is just to assert its negation--without killing the tree. So we list the premises on the trunk along with the negation of the conclusion and see if all the resulting branches die upon determing what each of these assertions amounts to according to the following rules:
Rules of Analytic Tableaux
To implement the strategy of Analytic Tableaux, we need to understand what it comes to when we assert a given PC-WFF. Assertions, it turns out, can resolve either conjointly, which gives us our non-branching rules, or disjointly, which gives us our branching rules. Suppose X and Y are any PC-WFF's. Then,
Since '∼X' is true iff 'X' is false, '∼∼X' asserts 'X' on the same branch.
Since 'X ∧ Y' is true iff both 'X' is true and 'Y' is true, 'X ∧ Y' asserts both 'X' and 'Y' on the same branch.
Since '∼(X ∨ Y)' is true iff 'X ∨ Y' is false, and 'X ∨ Y' is false iff both 'X' is false and 'Y' is false, '∼(X ∨ Y)' asserts both '∼X' and '∼Y' on the same branch.
Since '∼(X → Y) is true iff 'X → Y' is false, and 'X → Y' is false iff both 'X' is true and 'Y' is false, '∼(X → Y)' asserts both 'X' and '∼Y'.
Since 'X ∨ Y' is true iff either 'X' is true, or 'Y' is true, or both 'X' and 'Y' are true, 'X ∨ Y' splits between asserting 'X' on a branch and 'Y' on another branch.
'∼(X ∧ Y)' is true iff 'X ∧ Y' is false, and 'X ∧ Y' is false iff either 'X' is false or 'Y' is false, '∼(X ∧ Y)' splits between asserting '∼X' on a branch and '∼Y' on another branch.
Since 'X → Y' is true iff either 'X' is false or 'Y' is true, 'X → Y' splits between asserting '∼X' on a branch and 'Y' on another branch.
Since 'X ↔ Y' is true iff either both 'X' is true and 'Y' is true or both 'X' is false and 'Y' is false, 'X ↔ Y' splits between asserting both 'X' and 'Y' together on one branch and '∼X' and '∼Y' together on another branch.
Since '∼(X ↔ Y)' is true iff 'X ↔ Y' is false, and 'X ↔ Y' is false iff either both 'X' is true and 'Y' is false or both 'X' is false and 'Y' is true, '∼(X ↔ Y)' splits between asserting both 'X' and '∼Y' together on one branch and '∼X' and 'Y' together on another branch.
In general we want to apply non-branching rules before branching rules to keep our trees tall and skinny. Remember also that assertions propagate (repeat themselves) across branches beneath them (our trees grow upside down!) Our goal on every branch is the same: We keep resolving assertions until we get to a PC-WFF and its negation on a branch, no matter how far back up the branch we have to trace to reach either the PC-WFF or its negation. The branch then 'dies', which we indicate by putting an 'x' under the dead branch.
Once all the branches have been shown to die, we have shown that the tree dies--that is, that it is impossible to assert all of the premises while denying the conclusion.
Next time we will apply these methods to natural language arguments and practice using the methods of truth tables and analytic tableaux.