Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

$$x:X.\; (P \land Q) \;\dashv\; \vdash \; \lnot \exists x: X.\; \lnot (\lnot P \lor \lnot Q)$$

I want to prove that the left hand side entails the right hand side using propositional and predicate logic. $P$ and $Q$ are of type $x$ and I can use natural deduction and axioms.

Thank you.

share|cite|improve this question

It's not altogether clear which axioms you are using, as there are different axiomatic systems. I will assume you can use DeMorgan's.

Note, as it seems that the left-hand side is universally quantified ($\forall$), and the right-hand side is the denial of an existential statement ($\lnot \exists$), you need to keep in mind that $$\forall a:X(\text{blah})\iff \lnot \exists a:X(\lnot\text{blah}).\tag{$*$}$$

$\text{Premise:}\quad \forall x:X\; \lnot (P \land Q)\tag{p}.$ $$\forall x:X \;\lnot (P \land Q) \iff \forall x:X\;(\lnot P \lor \lnot Q)\tag{1.1}$$ $$\iff \lnot \lnot \left(\forall x:X \;(\lnot P \lor \lnot Q)\right)\tag{1.2}$$ $$\iff \lnot \exists x:X \;\lnot( \lnot P \lor \lnot Q))\tag{1.3}$$

Step $(\text{p})\to (1.1)$ makes use of the equivalence $\lnot (P \land Q) \equiv (\lnot P \lor \lnot Q)$, by DeMorgan's;
Step $(1.1)\to (1.2)$ assumes $\lnot \lnot A \equiv A$ for any statement $A$;
Step $(1.2)\to (1.3)$ makes use of what I discuss at the start of this answer (see $(*)$).

share|cite|improve this answer
+1 Hmm. blah, blah, blah – Babak S. Aug 18 '13 at 6:09

An easy / straightforward way to prove such things is to compute each side of your equations truth tables and to show that they are identical.

for instance on the left

$P | Q | (P\wedge Q)| ¬(P\wedge Q) \\t | t | t | f \\t | f | f | t \\f | t | f | t \\f | f | f | t$

now show that the last column of this table is equal to the last colum in the table corresponding to the right hand side

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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