prove P ∧ Q → P ⇔ R ∨ ¬R in natural deduction

Question

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.

Answer 1

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$.

Answer 2

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$$