Tarea 2

Consulte las normas de entrega de tareas en http://pleiad.cl/teaching/cc4101.

En esta tarea se explorá el mundo de la lógica, a través de la implementación de un “evaluador de predicados”. Esto con el fin de evaluar expresiónes en notación prefija como:

; Todo elemento en S tiene una factorización en S
(with (S (set (2 3 4 5 6)))
         (all x in S
              (exists y in S
                      (exists z in S
                              (= x (* y z))))))

O bien consultar si la siguiente afirmación es satisfacible:

(<=> (=> p q) (or (not p) q))

Recordemos que la nocion de satisfacibilidad es distinta a la de equivalencia. En el predicado anterior se cumple que ambos costados de la ⇔ tienen los mismos valores de verdad para cualquier valor de p y q. Un ejemplo de un predicado que no es siempre cierto pero si es satisfacible es el siguiente:

(<=> (=> p q) (or p (not q)))

El cuál por reglas de reducción no es cierta para todos los casos, pero si es satisfacible pues cuando p y q son ambos falsos el predicado es verdadero.

El siguiente listado muestra la grámatica BNF de nuestro lenguaje.

<prop> ::= #t 
         | #f
         | (or <prop> <prop>)
         | (and <prop> <prop>)
         | (not <prop>)
         | (xor <prop> <prop>)
         | (=> <prop> <prop>)
         | (<=> <prop> <prop>)
         | (all <id> <Set> <prop>) 
         | (exist <id> <Set> <prop>)
         | (< <AE> <AE>)
         | (= <AE> <AE>)

<AE>   ::= <num>
         | (+ <AE> <AE>)
         | (- <AE> <AE>)
         | (* <AE> <AE>)
         | (/ <AE> <AE>)

<Expr> ::= <AE>
         | <prop>
         | <id>
         | (set <list[Expr]>)
         | (with (<id> <Expr>) <Expr>)

El AST que deberá usar para representar dicha gramática se encuentra adjunto en el fichero <link a fichero start.rkt con gramática>. Note que la gramática permite ⇒, ⇔ y xor como azucares sintácticos, su parser debe encargarse de reemplazarlas por expresiones equivalentes en el AST adjunto (sin necesidad de crear nuevos nodos, lo cual será verificado). Implemente la función parse para su lenguaje:

(define (parse s-expr) ...)

1. (0.5) Escriba los siguientes predicados usando la gramática definida. Estos predicados los podrá usar como tests. - (a) Sea un conjunto S = { … } de números enteros. Este conjunto tiene un mínimo - (b) Sea un conjunto P = { … } de números enteros. Existe un elemento en el conjunto que es primo - © Todos los elementos de un conjunto P = { … } de números enteros son primos - (d) Todos los elementos de un conjunto P = { … } son pares (e) Para todo par a, b en un conjunto N de naturales a2 + b2 < (a+b)2