Differences

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

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
teaching:cc4101:tareas:2015-2:tarea2 [2015/10/10 10:38] – [(3.0) Interpretación sobre conjuntos finitos] racruzteaching: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> <code scheme>
-(<=> (=> p q) (or (¬ p) q))+(<=> (=> p q) (or (not p) q))
 </code> </code>
  
Line 30: Line 30:
  
 <code scheme> <code scheme>
-(<=> (=> p q) (or p (¬ q)))+(<=> (=> p q) (or p (not q)))
 </code> </code>
  
Line 143: Line 143:
 ;Edit: (list (num 2) (num 4)) por: ;Edit: (list (num 2) (num 4)) por:
 (list 2 4) (list 2 4)
-</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".  +</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? 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>+  - (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))) > (satisfiable? (parse-expr '(or p q)))
 #t #t
-> (satisfiable? (parse-expr '(and p (: p))))+> (satisfiable? (parse-expr '(and p (not p))))
 #f #f
 > (satisfiable? (parse-expr '(<=> (=> p q) (or p q)))) > (satisfiable? (parse-expr '(<=> (=> p q) (or p q))))
 #t #t
-> (satisfiable? (parse-expr '(<=> (=> p q) (and p (: q)))))+> (satisfiable? (parse-expr '(<=> (=> p q) (and p (not q)))))
 #f #f
 </code> </code>
Line 166: Line 166:
     * ¬¬p <=> p     * ¬¬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>   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)) (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>     </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>   -(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 183: Line 183:
 (my-or (my-and (id 'p) (id 'q)) (my-and (id 'q) (id 'p)))                     (my-or (my-and (id 'p) (id 'q)) (my-and (id 'q) (id 'p)))                    
 </code> </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 ===== ===== (0.7) Sistema de Tipos =====