0
$\begingroup$

I need to find the deduction from the set $\{\neg S \lor R,R \rightarrow P,S\}$ such that the last component is $P$.

The textbook gives the long rigorous definition of deduction but no examples to follow. Can someone give an alternative example of a deduction?

Edit: The definition of deduction from a set M is a finite sequence $(A_1,\ldots,A_n)$ of wffs such that each $k≤n, A_k$ is either 1) a tautology, 2) in M, or 3) $A_i$ is $(A_j \to A_k)$ for some $i,j<k$.

$\endgroup$
3
  • $\begingroup$ Please see here for a tutorial on how to format your math. $\endgroup$
    – mrp
    Sep 26, 2015 at 18:25
  • $\begingroup$ I have no idea how you are supposed to write this out, but: (1) S is true, so ~S is false; (2) but ~S or R is true, so R must be true; (3) R implies P, so P must be true. $\endgroup$
    – almagest
    Sep 26, 2015 at 18:48
  • 1
    $\begingroup$ What deductive system are you using? There are many, and nobody can give an example in yours unless you say what it is. $\endgroup$ Sep 26, 2015 at 19:13

2 Answers 2

1
$\begingroup$

Let $M = \{ ¬S∨R,R→P,S \}$

1) $¬S∨R$ --- in $M$

2) $(¬S∨R) \to (S \to R)$ --- tautology

3) $S \to R$ --- from 1) and 2) by modus ponens

4) $R \to P$ --- in $M$

5) $(S \to R) \to ((R \to P) \to (S \to P))$ --- tautology

6) $(R \to P) \to (S \to P)$ --- from 3) and 5) by mp

7) $S \to P$ --- from 4) and 6) by mp

8) $S$ --- in $M$

9) $P$ --- from 8) and 7) by mp.

Thus :

$\{ ¬S∨R,R→P,S \} \vdash P.$

$\endgroup$
0
$\begingroup$

What might be useful is a closer analysis of what a deduction is.

Basically, it is a formalisation of the notion of proof: a fully specified means to discover logical implications.

Now, one important note is that this formalisation is simply a game: it has a starting position $M$, a fixed set of allowed moves (described in your post), and an ending position $(A_1\ldots A_n)$, or more usually, $A_n$. Only we humans can decide that this game agrees sufficiently with what we intuitively understand as a "proof" -- in this case, a "proof of $A_n$ from $M$".


So let us analyse in this specific case what the rules are, and that they're sensible. Presume that we have an interesting set-up of assumptions $M$. Now:

  • According to rule 1, we can prove any tautology $A$ from $M$. This makes sense, because we didn't have to make use of any assumption from $M$ to derive $A$. For, $A$ is a tautology and as such it's always true.
  • According to rule 2, if we assume $A \in M$, then we may derive $A$. This is also intuitively obvious if we phrase it as: "If you assume something is true, then it is true."

And now there is the mysterious rule 3. It is a particular formulation of what is called modus ponens, the logical construct that:

Given $A$ is true, and given that $A$ implies $B$, one infers that $B$ is true.

To convert this logical principle to symbols, we represent "$A$ implies $B$" as "$A \to B$ is true". Then we can say:

Given $A$ and $A \to B$ are true, infer $B$ is true.

Finally, now, rule 3 (together with the whole sequence machinery) is nothing but a means to include this principle in our "game". For, consider $M = \{A, A \to B\}$ and begin a sequence: \begin{align}A_1 &:=\quad A\\ A_2 &:=\quad (A \to B)\end{align}

Now applying rule 3 requires some pattern recognition: If it is to be used, we need $i,j$ such that $A_i = (A_j \to X)$. Then we can pick $A_3 = X$ and rule 3 will be satisfied. In the above scenario, we see that $j = 1$ and $i = 2$. Consequently, we may specify: $$A_3 :=\quad B$$ and our desired interpretation of the game we defined leads us to say that:

$(A_1,A_2,A_3)$ is a proof of $B$ from $\{A, A \to B\}$.

which, as one sees, is nothing but an interpretation of modus ponens.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .