Solve logical problem

Question

Using any of the rules of inference and Rules of Replacement, prove

$$P \to A\tag{premise} $$

$$ Q \to B \tag{premise}$$

$$(P \land Q) \to (A\land B)\tag{conclusion)}$$

I was able to solve it to the conclusion of $(P\lor Q) \to (A\lor B)$, but I can't seem to figure out how to use the Rules of Replacement and Implication to get to the conclusion in the title.

Answer 1

We can start with: $(P \to A) \equiv (\lnot P \lor A)$ by Material Implication.

The same with: $(Q \to B) \equiv (\lnot Q \lor B)$.

By Addition we get:

$\lnot P \lor A \vdash \lnot P \lor \lnot Q \lor A$

and:

$\lnot Q \lor B \vdash \lnot P \lor \lnot Q \lor B$.

Now we apply Conjunction to get:

$(\lnot P \lor \lnot Q \lor A) \land (\lnot P \lor \lnot Q \lor B)$.

So far we have:

$(P \to A),(Q \to B) \vdash (\lnot P \lor \lnot Q \lor A) \land (\lnot P \lor \lnot Q \lor B)$.

The next step is to apply Distributivity to get:

$(P \to A),(Q \to B) \vdash (\lnot P \lor \lnot Q) \lor (A \land B)$.

Then use De Morgan's laws:

$(P \to A),(Q \to B) \vdash \lnot (P \land Q) \lor (A \land B)$

followed by Material Implication to conclude with:

$(P \to A),(Q \to B) \vdash (P \land Q) \to (A \land B)$.

Answer 2

We are given the two premises: $$(1)\; P \to A\tag{premise} $$

$$(2)\; Q \to B \tag{premise}$$

---

And we are to derive:

$$\therefore \;(P \land Q) \to (A\land B)\tag{conclusion)}$$

---

Proof:

$(1) \;P \to A \quad \text{premise}$

$(2)\; Q\to B \quad \text{premise}$

$(3) \;\qquad \text{Assume}\;\; P\land Q$

$(4)\qquad\qquad P\qquad \text{ (3), $\land$-elim}$

$(5)\qquad\qquad Q\qquad \text{ (3), $\land$-elim}$

$(6) \qquad \qquad A\qquad\text{ (4), (1), modus ponens}$

$(7) \qquad\qquad B\qquad\text{ (5), (2), modus ponens}$

$(8)\qquad\qquad A\land B\qquad\text{ (6), (7), $\land$-intro}$

$(9)\;\; (P \land Q) \to (A\land B)\qquad\text{(3)-(8), $\to$-intro}$ $$ $$

What we have proven is, given the first two premises, IF $P\land Q$, THEN $A\land B$, hence, we've proven $(P \land Q)\to (A\land B)$. $$ $$ Note: modus ponens is also known as $\to$-elimination.

And in the proof itself, "elim" is short for "elimination", and "intro" is short for "introduction."