How To Prove This Simple Theorem Using Fitch Natural Deduction System

77 Views Asked by At

Lemma. $ (p \land q) \iff (p \land q \land r) \lor (p\land q\land \lnot r)$

It is clear to me how this is true, but I don’t know how to prove it using only the rules of Fitch-style natural deduction. It is hard without distribution in my armament.

1

There are 1 best solutions below

7
On BEST ANSWER

Hint for the $\implies$ direction: derive $r \lor \neg r$. Try to eliminate this disjunction.

Hint for the $\impliedby$ direction: eliminate the disjunction in $(p \land q \land r) \lor (p \land q \land \neg r)$

Edit: full solution for $\implies$ direction

$\def\fitch#1#2{\quad\begin{array}{|l} #1\\[0ex]\hline #2\end{array}}$

$$ \fitch{p \land q}{ \fitch{\lnot(r \lor \neg r)}{\fitch{r}{r \lor \neg r\\\bot}\\\neg r\\r \lor \neg r\\\bot}\\ \neg \neg (r \lor \neg r) \\ r \lor \neg r \\ \fitch{r}{p \land q \land r \\ (p \land q \land r) \lor (p \land q \land \neg r)}\\ \fitch{\neg r}{p \land q \land \neg r \\ (p \land q \land r) \lor (p \land q \land \neg r)} \\ (p \land q \land r) \lor (p \land q \land \neg r)}$$