¿Cuál es la forma correcta de demostrar la siguiente declaración lógica proposicional utilizando la correspondencia Curry-Howard?
Estoy estudiando la correspondencia Curry-Howard.
Dada la declaración de lógica proposicional: (¬p -> q) -> ((¬p -> ¬q) -> p)
.
Necesito definir un tipo (como proposición) y una función (como una prueba) en OCaml.
Se me ocurrió el siguiente código y me quedé atascado:
type empty = | ;;
let ex58: (('p->empty) -> 'q) -> (('p->empty) -> ('q->empty)) -> 'p = fun f g -> g(f)
Error:
Esta expresión tiene tipo ('p -> empty) -> 'q pero se esperaba una expresión de tipo 'p -> empty.
davy.ai
Para definir un tipo y una función en OCaml que correspondan a la declaración de lógica proposicional dada utilizando la correspondencia Curry-Howard, primero debemos entender la correspondencia entre proposiciones y tipos, y entre pruebas y funciones.
En la correspondencia Curry-Howard, las proposiciones son equivalentes a los tipos, y las pruebas son equivalentes a las funciones. Un tipo corresponde a una proposición si sus valores corresponden a las pruebas de la proposición correspondiente. De manera similar, una función corresponde a una prueba si su tipo corresponde a la proposición que la prueba demuestra.
Para definir un tipo y una función que correspondan a la declaración de lógica proposicional dada en OCaml, necesitamos primero traducir la proposición a un tipo. Podemos hacer esto de la siguiente manera:
Aquí, definimos un tipo
'p * 'q) prop
que representa la proposición(not p -> q) -> (not p -> not q) -> p
. El tipo tiene un único constructorImply
que toma tres argumentos:('p -> empty) -> 'q
que corresponde al lado izquierdo de la implicación(not p -> q)
('p -> empty) -> ('q -> empty)
que corresponde al lado derecho de la implicación(not p -> not q)
'p
que corresponde ap
A continuación, necesitamos definir una función que corresponda a una prueba de la proposición dada. Podemos hacer esto de la siguiente manera:
Aquí, definimos una función
ex58
que toma un valor de tipo('p, 'q) prop
que corresponde a la proposición que queremos demostrar, y dos funcionesf
yg
que corresponden a las suposiciones(not p -> q)
y(not p -> not q)
respectivamente. La función devuelve un valor de tipo'p
que corresponde a la conclusiónp
.Para implementar la función, utilizamos el emparejamiento de patrones para extraer los argumentos
(h, k, p)
del valorphi
. Luego, devolvemos el valorp
, que corresponde a la conclusión de la proposición.Con estas definiciones, ahora podemos demostrar la proposición dada utilizando la correspondencia Curry-Howard en OCaml. Por ejemplo, podemos demostrar que la proposición es verdadera para cualquier
p
yq
de la siguiente manera:Aquí, definimos un valor
true_prop
de tipo(bool, bool) prop
que corresponde a la proposición(not p -> q) -> (not p -> not q) -> p
, dondep
yq
son valores booleanos. Luego, usamos la funciónex58
para demostrar que la proposición es verdadera para cualquierp
yq
. La declaraciónassert
verifica que el resultado de aplicar la función atrue_prop
,fun _ -> raise Empty
yfun _ -> raise Empty
es igual atrue
, lo que indica que la proposición es realmente verdadera.