[Práctico 3] Ejercicio 1

[Práctico 3] Ejercicio 1

de Eliana Rosselli Orrico -
Número de respuestas: 3

Buenas,

Realizando el ejercicio 1 del práctico 3 me surgieron algunas dudas.

En la primera parte del ejercicio no me queda claro cómo saber si un elemento está en beta forma normal. Por ejemplo, para el tercer tipo (A -> B) -> (A -> B -> C) -> A -> C, se me ocurrieron dos "habitantes" distintos:

Definition term3_1 := fun (f: A -> B) (g: A -> B -> C) (a: A) => g a (f a).

Definition term3_2 := fun (f: A -> B) (g: A -> B -> C) => (fun (a: A) => g a (f a)).

Ambos tienen el tipo pedido (verificado usando Check), pero no sé darme cuenta de cuál(es) está(n) en beta forma normal. También me queda la duda de si es correcto usar "fun", vi que en otros ejercicios del práctico no se usa. 

En la parte 3 de este mismo ejercicio, me quedán 2 dudas. La primera es qué significa que un tipo sea una tautología (es decir, por ejemplo para el tipo mencionado previamente, pude demostrar Theorem tauto3: (A -> B) -> (A -> B -> C) -> A -> C., pero no entiendo qué significa esto). También me queda la duda de si en la parte de realizar la prueba utilizando exact, solo se puede usar esa táctica, o si además se pueden usar otras como intros. 

Gracias y saludos

Eliana

En respuesta a Eliana Rosselli Orrico

Re: [Práctico 3] Ejercicio 1

de Carlos Luna -

Hola.

Un término está en beta forma normal si no es posible aplicar sobre éste una reducción beta. Lo podés ver a mano o ayudarte con las tácticas de Coq vinculadas a reducciones que se vieron. Los términos que diste están en beta forma normal.

Por ejemplo, en:

fun (f: A->B) (g:A->B->C) (a:A) => (fun (x:C) => x) (g a (f a))

no está en beta forma normal.

Es correcto usar fun.

Respecto a tus consultas de la parte 3, que sea una tautología significa que se puede demostrar sin hipótesis adicionales; la fórmula correspondiente es un teorema. En este ejercicios podrías usar intro/s además de exact, pero fijate que no precisás usar intro/s.

Ver por ejemplo:

Lemma t1: (A->A->A)->A->A.

(*  tauto. *)

(* intros f a; exact a *) 

 exact (fun (f:A->A->A) (a:A) => a).

Qed.

Saludos, Carlos

En respuesta a Carlos Luna

Re: [Práctico 3] Ejercicio 1

de Eliana Rosselli Orrico -
Hola Carlos
Gracias por tu respuesta. Entiendo la definición de tautología, pero mi duda iba más por el lado de que no entiendo qué significa que un tipo sea una tautología, es decir que un tipo "se pueda demostrar".

Gracias y saludos
En respuesta a Eliana Rosselli Orrico

Re: [Práctico 3] Ejercicio 1

de Carlos Luna -

Hola.

El tipo de una función puede ser visto como una implicación. Si la fórmula es lógicamente válida, la prueba (constructiva) es un término lambda que es un habitante del tipo correspondiente.

En la teoría de tipos que estamos viendo/estudiando, cada enunciado lógico se corresponde con un tipo y cada prueba es un objeto del tipo correspondiente. La identificación de proposiciones con tipos y de pruebas con objetos (términos lambda) es esencialmente el Isomorfismo de Curry-Howard.

Saludos, Carlos