Differences

This shows you the differences between two versions of the page.

--- teaching:cc4101:tareas:2015-2:tarea2 [2015/10/01 08:32] – [Tarea 2] racruz
+++ teaching:cc4101:tareas:2015-2:tarea2 [2015/10/13 11:07] (current) – [(3.0) Interpretación sobre conjuntos finitos] racruz
@@ Line 21: / Line 21: @@
 <code scheme>
-(<=> (=> p q) (or (¬ p) q))
+(<=> (=> p q) (or (not p) q))
 </code>
@@ Line 30: / Line 30: @@
 <code scheme>
-(<=> (=> p q) (or p (¬ q)))
+(<=> (=> p q) (or p (not q)))
 </code>
@@ Line 47: / Line 47: @@
 El siguiente listado muestra la grámatica BNF de nuestro lenguaje.
 <code>
-<prog> ::= <fun-def>* in <expr>
+<prog> ::= (<fun-def>* in <expr>)
 <fun-def> ::= (define (<id> <id>) <expr>)
@@ Line 59: / Line 59: @@
          | (=> <expr> <expr>)
          | (<=> <expr> <expr>)
-         | (all <id> <Set> <expr>)
+         | (all <id> in <expr> <expr>)
-         | (exist <id> <Set> <expr>)
+         | (exists <id> in <expr> <expr>)
          | (< <expr> <expr>)
          | (= <expr> <expr>))
@@ Line 141: / Line 141: @@
                                   (set (1 3 5))
                                   (set (2 4))))))
-(list (num 2) (num 4))
+;Edit: (list (num 2) (num 4)) por:
-</code> En caso de evaluar un programa que aplique una función no definida deberá lanzar un error "function not defined". Note que ''%%(eval-expr expr)%%'' se debe comportar como ''%%(eval-prog (program expr '()))%%''. En caso de evaluar un programa que use una variable no definida deberá lanzar un error "unbound identifier".
+(list 2 4)
-  - (0.5) Defina la función ''%%(satisfiable? s-expr)%%'' para determinar si un predicado booleano es satisfacible para algún valor de verdad de sus variables libres. Hint: use el cuantificador de existencialidad sobre las variables libres y el conjunto predefinido ''%%{#t ,#f}%%''. <code scheme>
+</code> En caso de evaluar un programa que aplique una función no definida deberá lanzar un error "function not defined". Note que ''%%(eval-expr expr)%%'' se debe comportar como ''%%(eval-prog (program '() expr))%%''. En caso de evaluar un programa que use una variable no definida deberá lanzar un error "unbound identifier".
+  - (0.5) Defina la función ''%%(satisfiable? expr)%%'' para determinar si un predicado booleano es satisfacible para algún valor de verdad de sus variables libres. Hint: use el cuantificador de existencialidad sobre las variables libres y el conjunto predefinido ''%%{#t ,#f}%%''. <code scheme>
 > (satisfiable? (parse-expr '(or p q)))
 #t
-> (satisfiable? (parse-expr '(and p (: p))))
+> (satisfiable? (parse-expr '(and p (not p))))
 #f
 > (satisfiable? (parse-expr '(<=> (=> p q) (or p q))))
 #t
-> (satisfiable? (parse-expr '(<=> (=> p q) (and p (: q)))))
+> (satisfiable? (parse-expr '(<=> (=> p q) (and p (not q)))))
 #f
 </code>
@@ Line 165: / Line 166: @@
     * ¬¬p <=> p
   Con esto se puede asegurar que en un programa válido, después de las negaciones ¬ no aparecen las expresiones: v, ^, ∀, ∃, ¬. Entiéndase programa válido (a este nivel), aquellos programas que no contienen operaciones invalidas como ''%%(+ #f 1)%%''. Ejemplos: <code scheme>
-> (simplify-negations (parse-expr '(¬ (or (¬ p) (¬ q)))))
+> (simplify-negations (parse-expr '(not (or (not p) (not q)))))
-(my-and (id 'p) (id 'q))
-> (simplify-negations (parse-expr '(¬ (¬ (¬ (or p q))))))
 (my-and (id 'p) (id 'q))
+> (simplify-negations (parse-expr '(not (not (not (or p q))))))
+(my-and (my-not (id 'p)) (my-not (id 'q)))
     </code>
   -(0.5) Defina la función ''%%(simplify expr)%%'' que se encargue de remplazar las siguientes expresiones: ''%%(and #f p)%%'', ''%%(or #t p)%%'', ''%%(¬ #t)%%'', ''%%(¬ #f)%%'', ''%%(or p p)%%'' y ''%%(and p p)%%'' por versiones más simples en el predicado representado por ''%%expr%%''. Asegúrese de utilizar la función ''%%simplify-negations%%'' definida anteriormente para uniformar las expresiones pues el predicado p puede ser arbitrariamente complejo. Hint: use la función ''%%equal?%%'' para verificar igualdad de predicados arbitrariamente complejos. No es necesario verificar permutaciones. <code scheme>
@@ Line 182: / Line 183: @@
 (my-or (my-and (id 'p) (id 'q)) (my-and (id 'q) (id 'p)))
 </code>
-  -(0.3) Defina la función ''%%(o-satisfiable? s-expr)%%'' que realiza optmización (usando ''%%simplify%%'') antes de evaluar. De un ejemplo de un predicado que toma mucho más tiempo de evaluar con la función ''%%satisfiable?%%'' que con ''%%o-satisfiable?%%''
+  -(0.3) Defina la función ''%%(o-satisfiable? expr)%%'' que realiza optmización (usando ''%%simplify%%'') antes de evaluar. De un ejemplo de un predicado que toma mucho más tiempo de evaluar con la función ''%%satisfiable?%%'' que con ''%%o-satisfiable?%%''
 ===== (0.7) Sistema de Tipos =====