How do I Prove De Morgan's Law with Inference?

Question

I'm trying to get from ~(q -> p) to (q ^ ~p), which is a version of De Morgan's Law with the conditional, in Fitch using only basic logic rules (e.g. ^ intro, ^ elim, etc. No laws or shortcuts).

(Actually specifically I'm trying to get from ~(~q -> p) to (~q ^ ~p), but that's the same idea, right?)

Any help?

Answer 1

$\def\fitch#1#2{\begin{array}{|l}#1\\\hline#2\end{array}}$

You seek to derive $\neg q\wedge\neg p$ from the premise $\neg(\neg q\to p)$.   Well, derive each conjunct separately then introduce the conjunction.

First show that you can derive $\neg q\to p$ from an assumption of $p$.   Therefore you can infer that $\neg p$ may be derived from $\neg(\neg q\to p)$.

Next show that you can derive $\neg q\to p$ from an assumption of $q$.   Therefore you can infer that $\neg q$ may be derived from $\neg(\neg q\to p)$.

Here's a quick Fitch style skeleton of the proof.   Fill in the missing details and you are done.

$$\fitch{\neg(\neg q\to p)}{\fitch{p}{~\vdots\\\neg q\to p\\\bot}\\\neg p\\\fitch{q}{~\vdots\\\neg q\to p\\\bot}\\\neg q\\\neg q\wedge\neg p}$$

Answer 2

DeMorgan's Laws are pretty much your only means of distributing a negation by inference; you can't prove them by the same.

Fortunately, they're both intuitive and can be proven by other means, such as truth tables.

As far as your expression, $!(!q -> p) = !q!p$, that's easily proven if DeMorgan's laws are allowed. $x -> y = !x + y$, so your expression is actually $!(q + p) = !q!p$, which is DeMorgan's law verbatim.