Ayuda a la lógica de predicados y proposiciones

Question

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

Quiero demostrar que el lado izquierdo implica el lado derecho utilizando la lógica proposicional y de predicados. $P$ y $Q$ son del tipo $x$ y puedo usar la deducción natural y los axiomas.

Gracias.

Answer 1

No está del todo claro qué axiomas estás utilizando, ya que hay diferentes sistemas axiomáticos. Asumiré que puedes usar el de DeMorgan.

Obsérvese, como parece que el lado izquierdo está cuantificado universalmente ( $\forall$ ), y el lado derecho es la negación de un enunciado existencial ( $\lnot \exists$ ), hay que tener en cuenta que $$\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}$$

Paso $(\text{p})\to (1.1)$ hace uso de la equivalencia $\lnot (P \land Q) \equiv (\lnot P \lor \lnot Q)$ por DeMorgan's;
Paso $(1.1)\to (1.2)$ se supone que $\lnot \lnot A \equiv A$ para cualquier declaración $A$ ;
Paso $(1.2)\to (1.3)$ hace uso de lo que comento al principio de esta respuesta (ver $(*)$ ).

Answer 2

Una forma fácil / directa de demostrar estas cosas es calcular cada lado de las tablas de verdad de tus ecuaciones y demostrar que son idénticas.

por ejemplo, a la izquierda

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

demuestre ahora que la última columna de esta tabla es igual a la última columna de la tabla correspondiente al lado derecho