Deductive proof - need help, explanation how to

Question

I am working on assignment for school where the task asks to give a deductive proof. However, I have never used this technique (nor that I am very good in proofs in general) thus it is quite complicated. Can anyone here give me a short "guide" on how to proof by deduction? (Couldn't find any good guide online). It would be really useful to see how to generate this kind of proofs if anyone could show how to solve this proof:

If $\forall x. (P(x) \to (Q(x) \wedge S(x)))$ and $\forall x. (P(x) \wedge R(x))$, then $\forall x. (R(x) \wedge S(x))$.

Thanks in advance!

Answer 1

A proof in natural deduction style is done with things called proof-trees. I don't know how to draw them on SE, so I'll use the other alternative known as Hilbert-style proof.

1. ∀ x . P x ⇒ Q x ∧ S x     premise
2. ∀ x . P x ∧ R x            premise
3. ∀ x . R x ∧ S x            goal
   3.1 P x ⇒ Q x ∧ S x       using (1) on x
   3.2 P x ∧ R x              using (2) on x
   3.3 P x                    ∧-elimination1 on 3.2
   3.4 R x                    ∧-elimination2 on 3.2
   3.5 Q x ∧ S x              modus-ponens using 3.1 and 3.3
   3.6 S x                    ∧-elimination2 on 3.5
   3.6 R x ∧ S x              ∧-introduction using 3.4 and 3.6

Natural deduction is treated in the early chapters of this nifty book called: Using Z. Best of luck!

Answer 2

There are many styles of natural deduction, and the one most suited for practical use is Fitch-style, which uses indentation just like programming languages to denote scoping. Basically, you ensure that every sentence you write is true in its context, where the context is captured by headers exactly as in a multi-level list. We can even throw away the lines at the side. See here and here and here for some examples.

Here is what such a proof of your example will look like: $\def\imp{\rightarrow}$

If $\forall x \ ( P(x) \imp Q(x) \land S(x) ) \land \forall x \ ( P(x) \land R(x) )$:

  $\forall x \ ( P(x) \imp Q(x) \land S(x) )$.

  $\forall x \ ( P(x) \land R(x) )$.

  Given any $x$:

    $P(x) \imp Q(x) \land S(x)$.

    $P(x) \land R(x)$.

    $P(x)$.

    $R(x)$.

    $Q(x) \land S(x)$.

    $S(x)$.

    $R(x) \land S(x)$.

  $\forall x \ ( R(x) \land S(x) )$.

$\forall x \ ( P(x) \imp Q(x) \land S(x) ) \land \forall x \ ( P(x) \land R(x) ) \imp \forall x \ ( R(x) \land S(x) )$.

I'm confident you can figure out how each line follows from the preceding ones. That ultimately is the goal of natural deduction, to make the logical reasoning clear.