2

Unfortunately I don't get the intuition behind the proofs by rules of inference.

I do understand example, however I don't see the broad picture, I simply don't understand how to reason about the solution.

Following I will show few example with my notes, which are might be incorrect, please show me what I don't get right.

Exercise 1. Prove ¬p from (p → q), (q → r) and ¬r.

We are given few assumption, (p → q) is true, (q → r) is true and ¬r is true. The question is whether ¬p is true.

If (q → r) is true and ¬r is true, then q should be false, therefore ¬q is true.

If (p → q) is true and ¬q is true that ¬p is true.

Whether the reasoning is true?

user16168
  • 697
  • better give an example where you go wrong :) – Willemien Sep 09 '13 at 08:35
  • 2
    Just to observe, it's "inference", not "interference". – Renny Barrett Sep 09 '13 at 08:53
  • I'm not sure if you want to look into the soundness (everything derivable qualifies as logically valid with respect to the semantics of the system) and semantic completeness (everything valid with respect to the semantics of the system, qualifies as derivable) of your logical system. I'd characterize that as a key part of the broad picture here. Reasoning about "the solution" can depend on the particular system and the rules of inference you have. Sometimes there exists different ways to reason about the solution, but recognizing the form of the solution probably will help. – Doug Spoonwood Sep 09 '13 at 16:48

5 Answers5

3

The reasoning is valid if modus tollens $$ A\to B, \neg B\;\vdash\; \neg A$$ is among your repository of inference rules

2

Valid rules of inference work such that if their premise(s) hold as true, then their conclusion will also hold as true. A solution to such an exercise consists of a deduction that given the premises and the rules of inference of the system (and it's axioms if any... I'd guess your system doesn't have an axioms), the conclusion can get deduced. To reason about the solution I suggest keeping the following in mind as much as possible:

  1. Know the major rules of inference by heart or have them ready to look at on a separate sheet of paper.
  2. Know the axioms (if any) by heart. Or have them ready to look at constantly.
  3. Know the form of the desired conclusion and try to reason about what the form of the desired conclusion suggests.
  4. Know the form(s) of the premise(s) involved.

With your example you have a wff that qualifies as a negation. So, you have to use some rule of inference which gives you a negation of a letter somehow. What rules in your logical system enable you to do this? It also has only one letter or variable. Your premises have one variable, and two variables, for a total of three distinct variables or letters. One consists of a negation, and the other two consist of conditionals. What rules do you have that enable you to change negations or conditionals into something else? What rules do you have that have conditionals or negations in their set of premises?

For this particular example, if you use all the premises in your solution (the solution is a deduction), consequently, we can deduce that to get the conclusion we have to use some rule which has fewer variables in the conclusion than it does in the set of premises. We can only outline rules of inference, but even such outlines can end up very instructive. For instance, consider the outline of the following rule

Hypothetical Syllogism:

{($\alpha$ $\rightarrow$ $\beta$), ($\beta$ $\rightarrow$ $\gamma$)} $\vdash$ ($\alpha$ $\rightarrow$ $\gamma$)

It has two variables in its conclusion and three variables in its set of premises. Its premises and its conclusion all come as conditionals. So, it enables us to take two conditionals, where the conditionals have a total of three letters, and infer another conditional which has two letters.

As another example consider the following rule, which your system probably doesn't have at its basis:

($\alpha$ $\rightarrow$ $\beta$) $\vdash$ [($\gamma$ $\rightarrow$ $\alpha$) $\rightarrow$ ($\gamma$ $\rightarrow$ $\beta$)]

It has two variables in its premise, and three variables in its conclusion. Its premise comes as a conditional, and so does its conclusion. Consequently, if we want to increase the number of variables or deduce something with conditionals, this rule of inference might help.

With what you did you engaged in semantic reasoning. It isn't invalid. However, it does NOT use any rules of inference of a formal system. That said, it probably does come close to rules of inference in your system.

1

By transitivity of implication (p → q) and (q → r) implies (p → r). By logical rule saying that if ((a → b) and ¬b) then ¬b (modus tollens) and already prooven fact that (p → r) and assumption ¬r you can infer ¬p.

Trismegistos
  • 2,410
1

You can transform $A \to B = \neg A \vee B$. So you have the following premises:

  • $p \to q = \neg p \vee q$ (1)
  • $q \to r = \neg q \vee r$ (2)
  • $\neg r$ (3)

By resolution on (2) and (3): you have $\neg q$ (4)
By resolution on (1) and (4): you have $\neg p$.

sean
  • 200
  • The language might not have any definitions or replacement rules which allows you to transform a conditional into a disjunction. So, this doesn't necessarily work. – Doug Spoonwood Sep 09 '13 at 16:41
1

Your reasoning is valid.

If $r$ is false and we know that $q\implies r$, then $q$ is false too because otherwise the truth of $q$ would immediately imply the truth of $r$. Similarly, knowing $\neg q$ and $p\implies q$, we deduce that $p$ is false.

Note that the contrapositives of your two assumptions are $\neg r \implies \neg q$ and $\neg q\implies \neg p$. So knowing $\neg r$, we can easily deduce $\neg p$.

Alraxite
  • 5,647