problemas de deberes de lógica proposicional

Question

Tengo problemas con un par de problemas en mi tarea de metalogía. Estamos utilizando un sistema axiomático con los siguientes axiomas:

$\vdash B\rightarrow(A\rightarrow B)$

$\vdash (\neg A\rightarrow B)\rightarrow((\neg A\rightarrow \neg B)\rightarrow A$

$\vdash (A\rightarrow(B\rightarrow C))\rightarrow((A\rightarrow B)\rightarrow (A\rightarrow C))$

También se nos permite utilizar el Modus Ponens en nuestras derivaciones.

Tengo problemas para mostrar lo siguiente (nótese que los únicos símbolos que forman parte de nuestro lenguaje son los paréntesis, las negaciones, las flechas y las letras):

1. $\{x, \neg y\}\vdash \neg(x\rightarrow y)$
2. $\vdash x\leftrightarrow x$ que es lo mismo que $\vdash \neg((x\rightarrow x)\rightarrow \neg(x\rightarrow x))$
3. $\{x, y\} \vdash x\wedge y $ que es lo mismo que $\{x, y\} \vdash \neg(x\rightarrow \neg y)$

También he probado muchos de los ejercicios, cuyas respuestas puedo utilizar en todas mis derivaciones:

Todavía no me siento completamente cómodo con el teorema de la deducción y estoy seguro de que podría abusar de él para resolver (2) y (3). Gracias por cualquier ayuda.

Answer 1

Asumimos como único conectivo el condicional ( $\rightarrow$ ).

Asumimos también la constante propositiva $\bot$ ( falsum o absurdo podemos pensar en ello también como un $0$ -), y definimos el negación de $p$ de esta manera : $\lnot p$ es $p \rightarrow \bot$ .

Las demás conectivas se definen como de costumbre: $p \land q$ es $\lnot (p \rightarrow \lnot q)$ , $p \lor q$ es $\lnot p \rightarrow q$ y $p \leftrightarrow q$ es $(p \rightarrow q) \land (q \rightarrow p)$ .

1) Utilizaremos el Teorema de la deducción es decir

si $\Gamma \cup \{ A \} \vdash B$ entonces $\Gamma \vdash A \rightarrow B$ .

Tenemos que :

$\{ x, x \rightarrow y \} \vdash y$ --- por modus ponens

De modo que :

$\vdash x \rightarrow ((x \rightarrow y ) \rightarrow y)$ --- por DT dos veces.

Ahora utilizaremos Transitividad y lo aplicamos:

$\vdash x \rightarrow [(x \rightarrow y) \rightarrow y]$ --- es $A \rightarrow B$

$\vdash [(x \rightarrow y) \rightarrow y] \rightarrow [\lnot y \rightarrow \lnot (x \rightarrow y)]$ --- por el lema 2.3(b), con DT --- es $B \rightarrow C$

Así que tenemos :

$\vdash x \rightarrow [\lnot y \rightarrow \lnot (x \rightarrow y)]$ --- es $A \rightarrow C$ .

Ahora aplicamos modus ponens dos veces :

$\{ x, \lnot y \} \vdash \lnot (x \rightarrow y)$ .

3) Utilizando la definición de $x \land y$ como $\lnot(x \rightarrow \lnot y)$ , de 1) con $\lnot y$ en lugar de $y$ y utilizando Doble negación tenemos :

$\{ x, y \} \vdash \lnot (x \rightarrow \lnot y)$ .

2) Utilizando la definición de

$x \leftrightarrow x$ como $(x \rightarrow x) \land (x \rightarrow x)$ ,

y utilizando la definición de

$x \land y$ como $\lnot(x \rightarrow \lnot y)$

tenemos que :

$x \leftrightarrow x$ es $\lnot [(x \rightarrow x) \rightarrow \lnot (x \rightarrow x)]$ .

Ahora la derivación :

utilizando Axioma 2 (1a) y Transitividad tenemos :

$\vdash (A \rightarrow B) \rightarrow ((A \rightarrow \lnot B) \rightarrow \lnot A)$

poniendo $A$ en lugar de $B$ tenemos :

$\vdash (A \rightarrow A) \rightarrow ((A \rightarrow \lnot A) \rightarrow \lnot A)$ .

Utilizando el ejemplo 2 (es decir $\vdash A \rightarrow A$ ) tenemos finalmente, por modus ponens :

$\vdash ((A \rightarrow \lnot A) \rightarrow \lnot A)$ .

Esto, a su vez, nos da :

$\vdash [(x \rightarrow x) \rightarrow \lnot (x \rightarrow x)] \rightarrow \lnot (x \rightarrow x)$

Utilizando el Lemma 2.3(b) tenemos :

$\vdash \lnot \lnot (x \rightarrow x) \rightarrow \lnot [(x \rightarrow x) \rightarrow \lnot (x \rightarrow x)]$

Utilizando 1(a) y Transitividad tenemos :

$\vdash (x \rightarrow x) \rightarrow \lnot [(x \rightarrow x) \rightarrow \lnot (x \rightarrow x)]$

Aplicar ahora modus ponens utilizando el ejemplo 2 (es decir $\vdash x \rightarrow x$ ) para obtener :

$\vdash \lnot [(x \rightarrow x) \rightarrow \lnot (x \rightarrow x)]$ es decir $x \leftrightarrow x$ .