1
$\begingroup$

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

2 Answers 2

3

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 $(*)$).

1

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