Show that $(P\land Q)\to(P\lor Q)$ is a tautology without the use of truth tables.


closed as off-topic by Dan Uznanski, user91500, Dominik, Claude Leibovici, астон вілла олоф мэллбэрг Nov 16 '16 at 10:07

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Dominik, Claude Leibovici, астон вілла олоф мэллбэрг
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Welcome to math.SE: since you are new, I wanted to let you know a few things about the site. In order to get the best possible answers, it is helpful if you say in what context you encountered the problem, and what your thoughts on it are; this will prevent people from telling you things you already know, and help them give their answers at the right level. Also, on this site we use MathJaX to format our maths. Here you can find a basic tutorial. $\endgroup$ – Nizar Nov 16 '16 at 8:28

Following the natural deduction system:

$$\begin{array}{cccl} p \wedge q & (1) & p \wedge q & \text{(premise)} \\ p \wedge q & (2) & p & \text{(conj elim (1))} \\ p \wedge q & (3) & p \vee q & \text{(disj intro (2))} \\ \varnothing & (4) & ( p \wedge q ) \rightarrow ( p \vee q ) & \text{(cond proof (3))} \end{array}$$


The following deduction is based on a truth table. T means true and F means false.

enter image description here

  • $\begingroup$ Nice illustration...+1 $\endgroup$ – Namaste Apr 23 '13 at 0:30

This was done using Fitch. Assume the statement you want to prove is false. Start a new subproof where you show that $P\wedge Q$ implies $P\lor Q$. This produces a contradiction which allows you to negate your original assumption, proving $(P\land Q)\to (P\lor Q)$. Since this can be can be proved from no premises, the statement is a tautology.

  • 1
    $\begingroup$ You should delete everything in this proof except lines 3 through 6. $\endgroup$ – DanielV Nov 16 '16 at 6:42

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