prove P ∧ Q → P ⇔ R ∨ ¬R in natural deduction I am a beginner in Natural Deduction currently reading the book "Logic in Computer Science" and got stuck at proving:
$$ P\land Q\to P\Leftrightarrow R\lor\lnot R$$
The latter formula is clearly a LEM, which I think $R$ should be obtained by getting a contradiction in the former formula.
Any help will be much appreciated.
 A: See :


*

*Michael Huth & Mark Ryan, Logic in Computer Science : Modelling and Reasoning about Systems (2nd ed 2004), page 27 for the table of natural deduction rules.


(A) LEM is a $0$-premise rule in the system; thus, we have a $1$-line proof of :

$\vdash r \lor \lnot r$.

(B) $p \land q \to p$ is a tautology, thus it must be provable :
1) $p \land q$ --- assumed [a]
2) $p$ --- from 1) by $\land$-e

3) $\vdash p \land q \to p$ --- from 1) and 3) by $\to$-i, discharging [a].

Now, we can use the (obvious) property of the derivability relation : $\vdash \ $ [not present in the book; we can see it in : Dirk van Dalen, Logic and Structure (5th ed - 2013), page 37] :

if $\Gamma \vdash \varphi$, then $\Gamma \cup \Delta \vdash \varphi$,

to add to the above proofs the "unnecessary" premises, getting from (A) :

$p \land q \to p \vdash r \lor \lnot r$

and from (B) :

$r \lor \lnot r \vdash p \land q \to p$.

Now we can conclude with :


$p \land q \to p \dashv \vdash r \lor \lnot r$.


A: Try this:
$$ p\wedge q\rightarrow p \leftrightarrow r \vee -r$$
$$ (-(p\wedge q)\vee p )\leftrightarrow V $$ 
If $ (-(p\wedge q)\vee p )$ is true or false, the result will be true or false respectivally, so
$$ (-p \vee -q \vee p)$$ 
$$(-q \vee -p\vee p)$$
$$(-q \vee V)=V$$
