1
$\begingroup$

$ p \rightarrow q,s \rightarrow t \quad \vdash \quad (p \land s) \rightarrow (q \land t) $

We are not allowed to use truth tables, De-morgan's laws, or any other method except natural deduction. Laws allowed: Implication, And, Or, MT, PBC, Copy Rule, Negation, Double Negation, Contradictions.

Both introduction and elimination wherever applicable.

Here is a sample style we are supposed to use while writing the proof :

2: $ p \lor \neg p $ $\quad L.E.M. $

3: $ p $ $ \quad assumption $

4: $ q $ $\quad \rightarrow e \quad 1,3 $

5: $ \neg p \lor q $ $\quad \lor i_2 \quad 4 $

6: $ \neg p $ $\quad assumption $

$\endgroup$
  • $\begingroup$ Assume $p \land s$ and use $\land$-elim, followed by $\to$-elim twice, followed by $\land$-intro and conclude with $\to$-intro. $\endgroup$ – Mauro ALLEGRANZA Aug 29 '17 at 8:18
1
$\begingroup$

If you can use the deduction theorem you can assume $p\land s$ and from that follows $p$ and subsequently $q$. Also follows $s$ and subsequently $t$. And since you've proven both $q$ and $t$, $q\land t$ follows. Then you discharge the assumption resulting in the statement to be proved.

$$\begin{align} \tag{1}p\rightarrow q, s\rightarrow t, p\land s &\vdash p\land s&\text{ assumption} \\\tag{2}p\rightarrow q, s\rightarrow t, p\land s &\vdash p&\text{ CE(1)} \\\tag{3}p\rightarrow q, s\rightarrow t, p\land s &\vdash p\rightarrow q&\text{ assumption} \\\tag{4}p\rightarrow q, s\rightarrow t, p\land s &\vdash q&\text{ MP(2,3)} \\\tag{5}p\rightarrow q, s\rightarrow t, p\land s &\vdash s&\text{ CE(1)} \\\tag{6}p\rightarrow q, s\rightarrow t, p\land s &\vdash s\rightarrow t&\text{ assumption} \\\tag{7} p\rightarrow q, s\rightarrow t, p\land s &\vdash t&\text{ MP(5,6)} \\\tag{8} p\rightarrow q, s\rightarrow t, p\land s &\vdash s\land t&\text{ CI(5,7)} \\\tag{9}p\rightarrow q, s\rightarrow t &\vdash (p\land s) \rightarrow (s\land t)&\text{ DT(8)} \\ \end{align}$$

Where CE is conjuction elimination, MP is modus ponens, CI is conjuction introduction and DT is the deduction theorem. Assumption is of course using one of the assumptions to the left of the $\vdash$.

$\endgroup$
  • $\begingroup$ I wonder why this answer was downvoted... $\endgroup$ – skyking Aug 29 '17 at 8:11
0
$\begingroup$
01. (p→q)∧(s→t)  premise
  02. p∧s          assumption
  03. (p→q)∧(s→t)  restate 01
  04. p            ∧elim 02
  05. p→q          ∧elim 03
  06. q            MP 04 05
  07. s            ∧elim 02
  08. s→t          ∧elim 03
  09. t            MP 07 08
  10. q∧t          ∧intro 06 09
11. (p∧s)→(q∧t)  →intro 02 10

Therefore, ((p→q)∧(s→t))⊢((p∧s)→(q∧t)).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.