Skip to main content
Humanities LibreTexts

2.8.3: Proving Invalidity with Truth Trees

  • Page ID
    1706
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    Let us now look at an example of an invalid argument:

    AvB
    A&B

    Keep in mind that this argument is invalid just in case there is a counterexample to it, and that the truth tree method works by searching for such counterexamples.
    We begin by listing the premise and the negation of the conclusion.

    1 AvB P
    2 ~(A&B) ~C

    An assignment of truth values which makes both of these sentences true will constitute a counterexample, demonstrating the invalidity of the original argument.

    We already know what to do with line 1. But when we get to line 2 we will have a new kind of sentence to work on, a negated conjunction. To make the negated conjunction '~(A&B)' true, I must make the conjunction '(A&B)' false. Making 'A' false is minimally sufficient for making '(A&B)' false, and so for making '~(A&B)' true. So for line 2 I must produce one branch which makes 'A' false, which I do by writing a branch which makes '~A' true. Making 'B' false is likewise minimally sufficient for making 'A&B' false. So for line 2 I also need a second, separate branch with '~B' on it. Altogether, the result of working on line 2 will look like this:

    8-7.png

    I will write this at the bottom of every open path on which line 2 appears. Note that this rule is very different from the rule for the negated disjunction '~(AvB)'. In working on the negated disjunction, '~(AvB)', I had to write a stack of the negated disjuncts ('~A' followed by '~B') at the bottom of every open branch. This is because only the stack, '~A' followed by '-B', is minimally sufficient for making the negated disjunction true. In working on the negated conjunction, '~(A&B)', I must write a branch with '~A' on one leg and '-B' on the other leg. This is because each of the negated conjuncts ('-A' or '-B') is by itself minimally sufficient for making the negated conjunction true.

    We now know everything we need to test our new argument for validity:

    8-8.png

    I first worked on line 1, producing a branch with 'A' on one leg and 'B' on the other, representing the two minimally sufficient ways of making line 1 true. I checked line 1 to remind myself that I have done everything needed to make it true. I then worked on line 2. At the bottom of each open path I put a new branch, one leg representing one minimally sufficient way of making line 2 true, and the second leg representing the second minimally sufficient way of making line 2 true. The annotation on the right of line 4 indicates that I got line 4 by applying my rule for a negated conjunction to line 2. And I checked line 2 to remind myself that I have done all that is needed to make it true. Next I inspected each path to see if it contained both a sentence and the negation of the same sentence. The first path has both 'A' and '~A'. The fourth path has both 'B' and '~B'. So I marked both these paths closed. At this point I observed that there are no unchecked compound sentences which I could make true by making some simpler sentences true.

    How does this tree show the argument to be invalid? You see that this completed tree has two open paths. What do they mean? Look, for example, at the first open path. Reading up from the bottom, suppose we make '~B' hue and make 'A' true. This constitutes an assignment of truth values to sentence letters ('B' false and 'A' true) which will make the original sentences 1 and 2 true. This is because we made '~F true as one way of making line 2 true. And we made 'A' true as one way of making line 1 true. So by assigning truth values f to 'B' and t to 'A', we make all sentences along the first open path true.

    This sort of thinking works generally for open paths. Keep in mind how we constructed the paths. Each time we found a sentence with an '&' or a 'v' in it, we wrote a shorter sentence farther down the path. We did this in a way which guaranteed that if we made the shorter sentence true, the longer sentence from which it came would be true also. So if we start at the bottom of a path and work up, making each sentence letter and each negated sentence letter true, that will be enough to make all sentences along the path true. Any sentence longer than a sentence letter or negated sentence letter will be made true by one or more sentences farther down the path.

    Even if we start with very complicated sentences at the top, each sentence is made true by shorter sentences below, and the shorter sentences are made true by still shorter sentences farther down, until we finally get to the shortest sentences possible, sentence letters and negated sentence letters. Then we can work backward. Making the sentence letters and negated sentence letters along the path true will, step by step, also make true all longer sentences higher up on the path.

    We have seen that the assignment of f to 'B' and t to 'A' makes all sentences along the first open path true. In particular, it makes the original first two sentences true. These sentences were our argument's premise and the negation of our argument's conclusion. So making the initial two sentences true makes our argument's premise true and its conclusion false. In short, 'B' false and 'A' true constitutes a counterexample to our argument. Thus the argument is invalid. One counterexample is enough to show an argument to be invalid, but you should note that the second open path gives us a second counterexample. Reasoning in exactly the same way as we did for the first open path, we see that making '~A' true and 'B' true makes every sentence along the second open path true. So making 'A' false and 'B' true constitutes a second counterexample to the argument.

    Our last step is to record all this information next to the completed tree. We write 'invalid' next to the tree and write the counterexamples which show the argument to be invalid. We can do this most easily with the sentences of sentence logic which describe the counterexamples. The sentence '~B&A' describes the counterexample given by the first open path and the sentence '~A&B' describes the counterexample given by the second open path.

    A last detail will conclude this section: The order of the cases in the description of the counterexample obviously does not matter. I described the first counterexample with the sentence '~B&A' because I read the counterexample off the path by reading from the bottom up. As a matter of practice, I recommend that you do the same. But in principle the equivalent description 'A&~B' describes the same counterexample just as well.

    Exercise \(\PageIndex{1}\)

    8-3. Use the truth tree method to show that the following arguments are invalid. Show your trees, being careful to show which branches are closed. In each problem give any counterexamples which show the argument being tested to be invalid.

    a) F b) ~(~S&T) C) KvH d) ~(I&P)
    F&K S ~K PvF
    H&D IvF


    2.8.3: Proving Invalidity with Truth Trees is shared under a not declared license and was authored, remixed, and/or curated by LibreTexts.

    • Was this article helpful?