Propositional Logic – A Primer

To prove that an argument is valid, one must show that the conclusion necessarily follows from the premises using the logical rules of inference given in the previous section or other such additional rules of inference. If an argument is valid, then it is impossible for the premises to be true and the conclusion to be false at the same time. For a valid argument, to assert the premises while denying the conclusion is to assert a contradiction. We say that the premises logically entail the conclusion.

As a simple example, suppose we have the following premises:

Using the rule of inference called Modus Ponens (MP), we can derive the conclusion:

The proof can be written as follows:

Example 1 – Natural deduction proof

This proof demonstrates that if the conditional, if it is raining, then the streets are wet, is true and it is also true that it is raining, we can validly conclude that the streets are wet.

The letters and numbers that appear to the right of each proposition are the abbreviation of the inference rules applied and the premise numbers to which the rule applies.

In this example, the [P] rule is the Premise Introduction rule. This rule states that a given premise may be introduced at any stage in the proof. The [MP] rule is Modus Ponens and here it is applied to Premises 1 and 2.

For a more complex example, suppose we want to prove the three premises 'P → ¬Q' and 'R → Q' and 'R' entail '¬P'.

The proof proceeds as follows.

Example 2 – Natural deduction proof

Line (1) is the second premise in our original list of premises. Line (2) is the third premise in our original list of premises. Line (3) is derived from lines (1) and (2) using the rule Modus Ponens. Line (4) is the first premise in our original list of premises. Line (5) is the proved conclusion, reached by deriving it from lines (3) and (4) using the rule Modus Tollens.

Note how the validity of an argument is a function of the syntactical structure of the argument and the truth of each of the premises. We can replace the letters representing each proposition with any interpretation (such as replacing 'P' with 'It is raining') and our argument will remain valid. The only proviso is that we remain consistent with our interpretation of each letter. For example, if we make 'P' stand for 'It is raining', 'It is raining' must be the interpretation of 'P' in all places where 'P' occurs in the argument.

Here is a third example using the natural deduction method of proof. The task is to prove '¬P → (R ∧ S)' and 'P → Q' and '¬Q' entail 'R'. The proof is as follows.

Example 3 – Natural deduction proof

An important learning to note here is that the conditional proposition constructed from the conjunction of the initial premises forming the antecedent of the conditional and the proved proposition constituting the consequent form a tautology. This is true for all valid arguments. For the preceding proof, the tautology constructed is:

((¬P → (R ∧ S)) ∧ (P → Q) ∧ ¬Q) → R

This proposition is true for all interpretations of the component propositions. It must be true for all possible truth values we assign to 'P', 'Q', 'R' and 'S'. To indicate this logical entailment from the conjunction of the premises to the conclusion, we use a special symbol: ⊨

We can then express the entailment thus:

((¬P → (R ∧ S)) ∧ (P → Q) ∧ ¬Q) ⊨ R

Using the entailment symbol, we indicate that the conditional is not only true for some interpretations of the component propositions, but for all interpretations. Some beginners in logic get confused between implication '→' (sometimes called 'material implication') and logical entailment '⊨'. Remember, if 'P' implies 'Q' is true, all this means is that 'P' is false or 'Q' is true. If 'P' entails 'Q', on the other hand, then there is no interpretation of 'P' and 'Q' in which 'P' is true and 'Q' is false. If 'P' is true, then there is no possibility that 'Q' is false in virtue of the components of 'P'.

Let us look at one more proof using the natural deduction method. Let's prove 'P ∧ Q' and 'P → ¬(Q ∧ R)' and 'S → R' entail '¬S'. The proof is as follows.

Example 4 – Natural deduction proof

A proof is a sequence of propositions that follow from a given set of premises using rules of inference. A valid argument is one in which the conclusion necessarily follows from the premises. There are several rules of inference that can be used to determine the validity of an argument, such as Modus Ponens, Modus Tollens, Simplification and Disjunctive Syllogism. In this section, we have seen how the natural deduction method is used to prove the validity of arguments. In the next section, we will examine a more graphical method for conducting formal proofs in propositional logic.

Copyright © 2023 Leslie Allan