Propositional Logic – A Primer

For proving the validity of arguments and demonstrating tautologies, the truth table method is effective up to a point. Beyond around three letters representing atomic propositions, the truth table becomes unwieldy with so many possible truth values to map. The natural deduction method is a powerful alternative, but for the more complex proofs it requires a lot of practice and ingenuity. The truth tree method has the advantage of handling the more complex proofs while providing a mechanical method for proving validity and tautologousness. For these two reasons, the truth tree method is my preferred method.

This method tests for whether it is possible for all of the premises to be true while the conclusion be false. We do that by assuming the premises true, negating the conclusion and testing for consistency for the set of propositions. If it is possible for the premises to be true and the conclusion false, then we can conclude that the argument is not valid according to the inference rules of propositional logic. We do this graphically, drawing a truth tree to map the components of composite propositions, and by applying a small number of fixed rules using a set procedure.

With this method, there are nine rules for decomposing propositions. These are as shown below, with the name for each rule shown in parentheses to the right of the rule. The letters 'P' and 'Q' stand for any proposition.

Truth tree decomposition rules

Note how each of these decomposition rules mirror a truth table and a rule of inference. Take the Double Negation (DN) rule of inference: If 'P' is true, then the negation of the negation of 'P' is true. The first decomposition rule (¬¬) represents that equivalence graphically with a line from '¬¬P' to 'P'.

Similarly, the second decomposition rule (∧) represents the inference rule Simplification (SIMP) and the truth table for (∧). The single line in the decomposition rule indicates that 'P' and 'Q' are true together.

The third decomposition rule (¬∧) is an example of branching. This rule represents the inference rule De Morgan's Law (DM): If 'P and Q' is false, then 'P' is false or 'Q' is false. The branching indicates that at least one of the branches is true; in this case, '¬P' or '¬Q'. The same is true for the remaining decomposition rules.

The procedure for applying the above decomposition rules in building the tree and testing for validity is as follows.

STEP 1:

List each of the initial premises of the argument on a separate line.

STEP 2:

Write under the list of initial premises the negation of the conclusion.

STEP 3:

Select a proposition from the list and apply the correct decomposition rule, adding the decomposition to every open path that can be reached from the decomposed proposition.

Add a check mark (✓) to the left of the decomposed proposition to indicate that it has been decomposed.

STEP 4:

Close any path that has a component proposition and its negation appearing in it.

Mark the path as closed by drawing a cross 'X' under it.

STEP 5:

Inspect to see if all paths are closed. If YES, stop. The argument is valid.

If NOT, have all propositions been decomposed?

If NOT, return to STEP 3. If YES, the argument is invalid.

If there are any paths left open after you have decomposed all of the propositions, it means there is a way for the premises to be true and the conclusion false. Each open path shows which of the component propositions are true in those scenarios in which the premises are true and the conclusion false. The open paths show you how the argument is invalid.

If all the paths end up closed, that means there is no possible way in which the premises are true and the negation of the conclusion is also true. In other words, there is no way for the premises to be true and the conclusion false. Hence, the argument is demonstrated to be valid.

Here are a couple of tips for keeping the branching simple:

1. When selecting a complex proposition for decomposing, prefer one that gives a trunk and not branches.
2. If branching is unavoidable, choose a complex proposition that you know will result in a closed branch.

Let's start with a simple example of a proof using the truth tree method. The task is to test whether 'P ∧ Q' and '¬P' entail 'Q'. Our test looks as follows.

Example 1 – Truth tree proof

The numbers to the left of the tree are the line numbers of the proof. The bracketed comments to the right of the tree indicate the source of the line and the decomposition rule applied. Lines (1) and (2) are the application of STEP 1. Line (3) is the application of STEP 2. We now apply the decomposition rule (∨) to line (1) (STEP 3) to create the branch resulting in line (4). We also add a check mark to line (1) to show that we have dealt with it.

Inspecting each path for a contradiction (STEP 4), we can see that every path contains a proposition and its exact negation. Hence, we mark both paths as closed with an 'X'. As all paths are closed (STEP 5), we have proved that the argument is valid. It's impossible for the premises to be true and the conclusion false.

Note that if all paths had not been closed, the propositions in lines (2) and (3) do not require further decomposition as the negation of an atomic proposition cannot be broken down into simpler components.

Let us now try a second example. In this example, we want to find out whether the single premise '(P ∨ Q) → R' entails 'R ∨ P'. The final truth tree appears as follows.

Example 2 – Truth tree proof

Line (1) is the initial premise, with line (2) listing the negation of the conclusion (STEPS 1 and 2). Applying the decomposition rule (¬∨) to line (2), we write in lines (3) and (4) (STEP 3). We also check off line (2) to show that we have decomposed it. So far, no proposition and its negation appear in any path in the tree. So, we continue from STEP 5 to decompose the next proposition. Applying the decomposition rule (→) to the proposition in line (1) gives us line (5). We check off line (1). Inspecting for contradictions in each path (STEP 4), we close of the right path as 'R' and its negation appear in the path.

The left path remains open, so we must decompose a proposition (STEP 5). There is only one proposition left to decompose; that appearing in line (5) as '¬(P ∨ Q)'. We apply the decomposition rule (¬∨) to it to write in lines (6) and (7). Inspecting that remaining path, we see that it remains open with no contradictions showing in the path. We conclude that the argument is not valid according to the rules of propositional logic.

From the open path, we can see the truth values of the atomic sentences in the case where the premises are true and the conclusion is false. We see that occurs when 'P', 'Q' and 'R' are all false. Importantly, note that because we have proved that the argument is invalid according to the rules of propositional logic, we cannot conclude that the original argument prior to translation to symbolic logic is necessarily invalid. It may be that a further decomposition of the internal structure of the atomic sentences using a more advanced logic shows the argument to be valid after all.

For our final example, let's prove whether or not the three premises 'P ∨ Q', 'P → R' and '¬Q ∨ R' entail 'R'.

Example 3 – Truth tree proof

Lines (1), (2) and (3) list the premises while line (4) is the negation of the conclusion. Decomposition rule (∨) is first applied to line (1) to give the first branch and then checked off. With no paths to close, decomposition rule (→) is applied to line (2) and checked off. Note how the application of the (→) rule appears in both open branches in line (5). This is because the proposition in line (2) appears at the head of each path. Following decomposition in line (6), we can now close three of the four paths. One open path remains, so we must decompose the proposition in line (3) that has so far not been decomposed. Applying the (∨) rule gives us the final branch in the tree. On inspection, we close each of the final two paths. With all paths closed, we determine the argument is valid.

The truth tree method can also be used to prove tautologies. In this case, we negate the tautology and then proceed to decompose the negated proposition using the standard decomposition rules. Once the single premise is fully decomposed, if all paths are closed, we have proved that the proposition is a tautology. We have proved that there is no possible interpretation of the atomic propositions that makes the composite proposition false.

The truth tree method is a simple but effective way of proving the validity of arguments and tautologies. By applying a small set of decomposition rules and following some procedural steps, we have available a mechanical method for demonstrating the logical entailment of a conclusion from a set of premises.

Copyright © 2023 Leslie Allan