3
$\begingroup$

How to use natural deduction to show $\lnot (P \land Q) \vdash \lnot P \lor \lnot Q$? I think I need to first assume $\neg(\neg P \lor \neg Q)$ and then find a contradiction but I cannot see how to do it. Can anyone help?

$\endgroup$
  • $\begingroup$ Do you know De Morgan's laws? $\endgroup$ – lightxbulb Jan 21 at 17:41
  • $\begingroup$ @lightxbulb yes, it is what the sequent shows. $\endgroup$ – S0rin Jan 21 at 17:47
  • $\begingroup$ What rules do you have? What proof system are you using? There are many different proof systems ..... $\endgroup$ – Bram28 Jan 21 at 19:45
  • $\begingroup$ The statement isn't constructively true, so it is using LEM, so you may as well just learn how to do truth tables in whatever logic you are using. $\endgroup$ – DanielV Jan 21 at 21:34
1
$\begingroup$

How to use natural deduction to show $¬(P∧Q)⊢¬P∨¬Q$? I think I need to first assume $¬(¬P∨¬Q)$ and then find a contradiction but I cannot see how to do it.

To show that assuming $\lnot(\lnot P\lor\lnot Q)$ contradicts the premise of $\lnot(P\land Q)$, you clearly need to show that that assumption entails $P\land Q$.

You can show $\lnot(\lnot P\lor\lnot Q)$ entails $P$ by reduction to absurdity.   Assume $\lnot P$, then use disjunction introduction, negation elimination, negation introduction (to discharge the assumption), and double negation elimination.

The rest should be obvious.   Here's the fitch style skeleton.

$$\def\fitch#1#2{\quad\begin{array}{|l} #1\\ \hline #2\end{array}}\fitch{\lnot(P\land Q)\hspace{10ex}\textsf{Premise}}{\fitch{\lnot(\lnot P\lor\lnot Q)\hspace{3ex}\textsf{Assumption}}{\fitch{\lnot P\hspace{9ex}\textsf{Assumption}}{\lnot P\lor\lnot Q\hspace{3ex}\textsf{Disjunction Introduction}\\\bot\hspace{10.5ex}\textsf{Negation Elimination}}\\\lnot\lnot P\hspace{11ex}\textsf{Negation Introduction}\\P\hspace{14ex}\textsf{Double Negation Elimination}\\\vdots }\\ \vdots\\\lnot P\lor\lnot Q}$$

$\endgroup$
4
$\begingroup$

The following is a derivation in natural deduction proving that $\lnot(P \land Q) \vdash \lnot P \lor \lnot Q$. The notation $[A]^*$ marks an assumption discharged by the inference rule $*$. \begin{align} \dfrac{\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\dfrac{[\lnot(\lnot P \lor \lnot Q)]^* \quad \dfrac{\dfrac{\dfrac{\lnot(P \land Q) \quad \dfrac{[P]^+ \quad \dfrac{\dfrac{[\lnot(\lnot P \lor \lnot Q)]^* \quad \dfrac{[\lnot Q]^{**}}{\lnot P \lor \lnot Q}\lor_{i_2}}{\bot}\lnot_e\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!}{Q}\text{raa}^{**}\!\!\!\!\!\!\!\!\!\!\!\!\!\!}{P \land Q}\land_i\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!}{\bot}\lnot_e}{\lnot P}\lnot_i^+}{\lnot P \lor \lnot Q}\lor_{i_1}\!\!\!\!\!\!\!\!}{\bot}\lnot_e\!\!\!\!\!\!\!\!\!\!\!}{\lnot P \lor \lnot Q}\text{raa}^* \end{align}

The idea is a reasoning by contradiction: in addition to the hypothesis $\lnot (P \land Q)$, we suppose $\lnot (\lnot P \lor \lnot Q)$ (the negation of what we want to prove) and we show that this leads to a contradiction. More precisely, we show that $P \land Q$ follows from $\lnot (\lnot P \lor \lnot Q)$, which contradicts our hypothesis $\lnot (P \land Q)$. To show this, we need some additional assumptions ($\lnot Q$ and $P$), which we can discharge at the right moment: this complicates a bit the reasoning.

Note the application of the inference rule raa (reductio ad absurdum), used twice. Actually, $\lnot(P \land Q) \vdash \lnot P \lor \lnot Q$ cannot be proved without this rule (or another inference rule equivalent to it).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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