Autor Tema: Deducciones formales

0 Usuarios y 1 Visitante están viendo este tema.

23 Mayo, 2013, 03:45 am
Leído 2227 veces

Tanius

  • Lathi
  • Mensajes: 4,649
  • Karma: +0/-0
  • Sexo: Masculino
El sistema forma \( L \), es el que cuenta con tres axiomas, si \( \alpha , \beta , \gamma \) son fórmulas bien formadas:

A1: \( \alpha\rightarrow{(\beta\rightarrow{\alpha})} \)
A2: \( (\alpha\rightarrow{(\beta\rightarrow{\gamma})})\rightarrow{((\alpha\rightarrow{\beta}) \rightarrow{(\alpha\rightarrow{\gamma})})} \)
A3: \( (\lnot{\beta}\rightarrow{\lnot{\alpha}})\rightarrow{(\lnot{\beta}\rightarrow{\alpha})\rightarrow{}\beta} \)

Y la única regla de inferencia es Modus Ponens.

Estoy atorado en las siguientes tres deducciones formales:

(a) \( \vdash \lnot (\beta\rightarrow{\lnot\gamma})\rightarrow{\gamma} \)
(b) \( \vdash \beta\rightarrow{(\lnot\beta\rightarrow{\gamma})} \)
(c) \( \vdash (\lnot\alpha\rightarrow{\beta})\rightarrow{(\lnot\beta\rightarrow{\alpha})} \)

¿Alguna idea?

Ya puedo usar el teorema de la deducción por si es de utilidad. Lo que no puedo usar es corrección-completud.

23 Mayo, 2013, 04:03 am
Respuesta #1

numbsoul

  • Nahuel Albarracín
  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,849
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
¿Pueden usarse los símbolos de conjunción y disjunción y equivalencias semánticas?

23 Mayo, 2013, 04:09 am
Respuesta #2

Tanius

  • Lathi
  • Mensajes: 4,649
  • Karma: +0/-0
  • Sexo: Masculino
¿Pueden usarse los símbolos de conjunción y disjunción y equivalencias semánticas?

Creo que no. La razón es que, por ejemplo, el símbolo \( \beta\wedge\gamma \) es, por definición, una abreviación de \( \lnot (\beta\rightarrow{\lnot\gamma}) \). Claro, (a) podría reformularse como \( \vdash \beta\wedge\gamma \rightarrow{\gamma} \), pero no es de mucha ayuda ya que para probarla habría que recurrir a la definición del símbolo \( \beta\wedge\gamma \).

No sé a qué te refieres con equivalencia semántica.

23 Mayo, 2013, 04:15 am
Respuesta #3

numbsoul

  • Nahuel Albarracín
  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,849
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
¿Y qué sería probar una de esas implicaciones?.¿Estamos en el lenguaje de la lógica proposicional?

23 Mayo, 2013, 04:24 am
Respuesta #4

Tanius

  • Lathi
  • Mensajes: 4,649
  • Karma: +0/-0
  • Sexo: Masculino
Si \( \Gamma \) es un conjunto de fórmulas bien formadas, escribimos \( \Gamma\vdash \gamma \) si existe una sucesión (ordenada) de fórmulas bien formadas \( \beta _1,...,\beta _n \) tales que \( \beta _n = \gamma \), y para cada \( i\in{\left\{{1,...n}\right\}} \) tenemos que \( \beta _i\in{\Gamma} \), o bien \( \beta _i \) es axioma o bien \( \beta _i \) se obtiene de Modus Ponens de anteriores.

Si \( \Gamma = \emptyset \) escribimos simplemente \( \vdash \gamma \).

Comentaba que puedo usar el teorema de la deducción, el cual se formula básicamente como \( \Gamma \cup{\left\{{\alpha}\right\}}\vdash \gamma \) implica \( \Gamma \vdash \alpha \rightarrow{\gamma} \).

.¿Estamos en el lenguaje de la lógica proposicional?

Sí.

23 Mayo, 2013, 04:55 am
Respuesta #5

luis

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 303
  • Karma: +1/-0
  • Sexo: Masculino

acerca de la parte (c).

usando el teorema de deducción, intentarías probar \( \lnot\alpha\to\beta, \lnot\beta \vdash \alpha \). podés
resolverlo con el esquema A3 y A1. cuidado que al usar A3 los \( \alpha \) y \( \beta \) quedan intercambiados.

las otras partes no las he visualizado de inmediato.

saludos

luis

23 Mayo, 2013, 05:02 am
Respuesta #6

luis

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 303
  • Karma: +1/-0
  • Sexo: Masculino
acerca de la parte (b).

usando el teorema de deducción, intentarías probar \( \beta, \lnot\beta \vdash \gamma \) . podés
resolverlo con el esquema A3 y A1. al usar el esquema A1 (dos veces) hay que colocar como \( \beta \) a \( \gamma \).

la otra parte aún no la he visualizado.

saludos

luis

23 Mayo, 2013, 04:29 pm
Respuesta #7

Tanius

  • Lathi
  • Mensajes: 4,649
  • Karma: +0/-0
  • Sexo: Masculino
Ya entiendo.

Para probar (c), es decir, \( \lnot\alpha\to\beta, \lnot\beta \vdash \alpha \) se puede hacer como sigue:

Por axioma 3: \( (\lnot\alpha\rightarrow{\lnot\beta})\rightarrow{(\lnot\alpha\rightarrow{\beta})}\rightarrow{\alpha} \)
Por axioma 1: \( \lnot\beta\rightarrow{(\lnot\alpha\rightarrow{\lnot\beta})} \)
Por hipótesis: \( \lnot\beta \)
Modus Ponens: \( \lnot\alpha\rightarrow{\lnot\beta} \)
Modus Ponens: \( (\lnot\alpha\rightarrow{\beta})}\rightarrow{\alpha} \)
Hipótesis: \( \lnot\alpha\rightarrow{\beta} \)
Modus Ponens: \( \alpha \)

El (b), como dices, sale de forma parecida.

Muchas gracias, luis :)