Resolution: Computer programs have been developed to automate the task of reasoning and proving theorems. Many of these programs make use of a rule of inference known as resolution. This rule of inference is based on the tautology
((p ∨ q) ∧ (¬p ∨ r)) → (q ∨ r).
The final disjunction in the resolution rule, q ∨ r, is called the resolvent. When we let q = r in this tautology, we obtain (p ∨ q) ∧ (¬p ∨ q) → q. Furthermore, when we let r = F, we obtain (p ∨ q) ∧ (¬p) → q (because q ∨ F ≡ q), which is the tautology on which the rule of disjunctive syllogism is based.
EXAMPLE 1 Use resolution to show that the hypotheses “Jasmine is skiing or it is not snowing” and “It is snowing or Bart is playing hockey” imply that “Jasmine is skiing or Bart is playing hockey.”
Solution: Let p be the proposition “It is snowing,” q the proposition “Jasmine is skiing,” and r the proposition “Bart is playing hockey.”We can represent the hypotheses as ¬p ∨ q and p ∨ r, respectively. Using resolution, the proposition q ∨ r, “Jasmine is skiing or Bart is playing hockey,” follows.
Resolution plays an important role in programming languages based on the rules of logic, such as Prolog (where resolution rules for quantified statements are applied). Furthermore, it can be used to build automatic theorem proving systems. To construct proofs in propositional logic using resolution as the only rule of inference, the hypotheses and the conclusion must be expressed as clauses, where a clause is a disjunction of variables or negations of these variables.
We can replace a statement in propositional logic that is not a clause by one or more equivalent statements that are clauses. For example, suppose we have a statement of the form p ∨ (q ∧ r). Because p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r), we can replace the single statement p ∨ (q ∧ r) by two statements p ∨ q and p ∨ r, each of which is a clause. We can replace a statement of the form ¬(p ∨ q) by the two statements ¬p and ¬q because De Morgan’s law tells us that ¬(p ∨ q) ≡ ¬p ∧¬q.We can also replace a conditional statement p → q with the equivalent disjunction ¬p ∨ q.
EXAMPLE 2 Show that the premises (p ∧ q) ∨ r and r → s imply the conclusion p ∨ s.
Solution:We can rewrite the premises (p ∧ q) ∨ r as two clauses, p ∨ r and q ∨ r.We can also replace r → s by the equivalent clause ¬r ∨ s. Using the two clauses p ∨ r and ¬r ∨ s, we can use resolution to conclude p ∨ s.
Fallacies: Several common fallacies arise in incorrect arguments. These fallacies resemble rules of inference, but are based on contingencies rather than tautologies. These are discussed here to show the distinction between correct and incorrect reasoning.
The proposition ((p → q) ∧ q) → p is not a tautology, because it is false when p is false and q is true. However, there are many incorrect arguments that treat this as a tautology. In other words, they treat the argument with premises p → q and q and conclusion p as a valid argument form, which it is not. This type of incorrect reasoning is called the fallacy of affirming the conclusion.
EXAMPLE 3 Is the following argument valid? If you do every problem in any book, then you will learn discrete mathematics.You learned discrete mathematics. Therefore, you did every problem in any book.
Solution: Let p be the proposition “You did every problem in this book.” Let q be the proposition “You learned discrete mathematics.” Then this argument is of the form: if p → q and q, then p. This is an example of an incorrect argument using the fallacy of affirming the conclusion. Indeed, it is possible for you to learn discrete mathematics in someway other than by doing every problem in this book. (You may learn discrete mathematics by reading, listening to lectures, doing some, but not all, the problems in this book, and so on.)
The proposition ((p → q)∧¬p)→¬q is not a tautology, because it is false when p is false and q is true. Many incorrect arguments use this incorrectly as a rule of inference. This type of incorrect reasoning is called the fallacy of denying the hypothesis.
EXAMPLE 4 Let p and q be as in Example 10. If the conditional statement p → q is true, and ¬p is true, is it correct to conclude that ¬q is true? In other words, is it correct to assume that you did not learn discrete mathematics if you did not do every problem in the book, assuming that if you do every problem in this book, then you will learn discrete mathematics?
Solution: It is possible that you learned discrete mathematics even if you did not do every problem in this book. This incorrect argument is of the form p → q and ¬p imply ¬q, which is an example of the fallacy of denying the hypothesis.
