

Introduction to Logic

Tools for Thought


The connections described in the preceding section are useful in solving logical problems because they allow us to transform problems of one type into problems of another type. For example, if we needed to determine the validity of a sentence of the form (φ => ψ), the deduction theorem tells us that we could instead solve the equivalent problem of determining whether φ logically entails ψ. In making this determination, we need to consider only those interpretations that make φ true and we can ignore all of the other interpretations. The upshot is that solving the equivalent problem can be easier than solving the original.

The idea of problem transformation can also be used to transform problems of one type into equivalent problems of the same type. The trick is to rewrite the sentences involved in the problem into logically equivalent sentences. Suppose we wanted to know whether a complex sentence like ((¬p ∨ q) ⇒ (p ⇒ q)) ∧ q is valid, contingent, or unsatisfiable. Since (¬p ∨ q) is logically equivalent to (p ⇒ q), we can rewrite the given sentence as ((p ⇒ q) ⇒ (p ⇒ q)) ∧ q. The first conjunct is clearly valid; the second is contingent; and so the sentence as whole must be contingent.

The following is a list of logical equivalences that can be used in rewriting sentences as logically equivalent sentences.
¬¬φ ⇔ φ 
¬(φ ∧ ψ) ⇔ (¬φ ∨ ¬ψ) 
¬(φ ∨ ψ) ⇔ (¬φ ∧ ¬ψ) 
(φ ⇒ ψ) ⇔ (¬φ ∨ ψ) 
(φ ⇔ ψ) ⇔ (φ ⇒ ψ) ∧ (ψ ⇒ φ) 
Of course, there are many more such equivalences. In fact, there are infinitely many. The ones listed here are the most common and the simplest to apply. Moreover, as we shall see in Chapter 5, they are also the basis for the conversion of sentences to clausal form.

The idea of rewriting sentences as logically equivalent sentences can also be applied to sets. We can transform the individual sentences in the sets; and, in some cases, we can add or delete sentences. For example, we can replace the set {p, p ⇒ q} with the set {p, q}, since they are logically equivalent.

As we shall see in the next two chapters, proofs are, in a way, a special case of this idea (one where we add sentences but do not delete sentences). For example, to prove a conclusion in the Fitch system (described in the next chapter), we start with our set of premises and incrementally add logical consequences until we produce a set containing the desired conclusion. The resolution method (described in Chapter 5) is analogous; to show that a set of sentences is unsatisfiable, we start with a set of premises and add conclusions until we obtain a direct contradiction.

Use the arrow keys to navigate.
Press the escape key to toggle all / one.

