# Thread: Proving rule of inference

1. ## Proving rule of inference

Prove or disprove that the following rule of inference is sound:
Hint: You can use a truth table, but a careful logical
argument will also do it.

(p \/ q \/ r)
(~p \/ s)
---------------
(q \/ r \/ s)

2. This inference rule is called resolution. The programming language Prolog has it; in fact, Prolog programs run by doing resolution.

So what it is the difficulty with this problem? To show that the rule is sound one has to show that: for any interpretation, or model, M, if all premise formulas are true in M, then the conclusion is also true in M. An interpretation is a function from propositional letters to the set {True, False}. By considering different interpretations and computing the truth value of each formula, you can say whether this is correct.

Well, it's not wise to consider all possible interpretations, because there are 2^(2^4) = 2^16 of them. Hint: when dealing with formulas that have a lot of disjunctions, it is often easier to find interpretations where formulas are false. So here, assume that the conclusion is false, and...

3. Can you elaborate your answer in an easy way so that I can understand, because I am new to this and I don't want my teacher to think that I have cheated.

4. There are two ways to approach this problem, as the hint says: a formal proof and a common-sense argument.

If you want to solve this problem in a precise mathematical way, you need to know and be able to use the following concepts:

(1) Propositional variables, connectives and formulas;

(2) Interpretation, or model: a function from prop. variables to {T, F};

(3) Boolean functions of one or two arguments and using truth tables to specify them, e.g.:
Code:
f(F, F) = F
f(F, T) = F
f(T, F) = F
F(T, T) = T
(4) Boolean functions and their truth tables corresponding to propositional connectives: /\, \/, etc.;

(5) Truth value of a propositional formula in a given interpretation;

(6) Rule of inference; when it is sound;

(7) Probably the most important: how to make mathematical argument. E.g., how to prove statements of the form "For all such-and-such objects, the following holds: ...", "If ..., then ..."; what are proofs by contradiction, counterexamples, etc.

If you know these concepts and how to apply them, it should not be too difficult to solve the problem. If you still can't figure it out, post here the description of where exactly you are stuck. E.g.: I assumed that the premises are true in M, but there are too many such M's, so I can't go over all of them and verify if the conclusion is true in M.

There is no easier way to come up with a formal proof; you need to know the concepts and have some experience in using them.

If you can't spare the efforts to learn all this, you can give a less precise explanation that any reasonable person would understand. You are asked to show that if the first two formulas are true, then the third one is true as well. Another way to say this is: If the third formula is false, then at least one of the first two is false as well.

Assume that the third formula is false. Then all of q, r, and s are ... . We play the devil's advocate: let's assume that both formulas on top are true. Since s is ... and the second formula is true, this implies that p is ... . But then how can the first formula be true? So we showed the last sentence of the previous paragraph is correct.