Both sides previous revisionPrevious revisionNext revision | Previous revisionNext revisionBoth sides next revision |
teaching:cc4101:tareas:2015-2:tarea2 [2015/10/01 08:32] – [Tarea 2] racruz | teaching:cc4101:tareas:2015-2:tarea2 [2015/10/10 16:15] – [(3.0) Interpretación sobre conjuntos finitos] racruz |
---|
El siguiente listado muestra la grámatica BNF de nuestro lenguaje. | El siguiente listado muestra la grámatica BNF de nuestro lenguaje. |
<code> | <code> |
<prog> ::= <fun-def>* in <expr> | <prog> ::= (<fun-def>* in <expr>) |
| |
<fun-def> ::= (define (<id> <id>) <expr>) | <fun-def> ::= (define (<id> <id>) <expr>) |
| (=> <expr> <expr>) | | (=> <expr> <expr>) |
| (<=> <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>) |
| (= <expr> <expr>)) | | (= <expr> <expr>)) |
(set (1 3 5)) | (set (1 3 5)) |
(set (2 4)))))) | (set (2 4)))))) |
(list (num 2) (num 4)) | ;Edit: (list (num 2) (num 4)) por: |
| (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? 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> |
> (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> |
(my-and (id 'p) (id 'q)) | (my-and (id 'p) (id 'q)) |
> (simplify-negations (parse-expr '(¬ (¬ (¬ (or p q)))))) | > (simplify-negations (parse-expr '(¬ (¬ (¬ (or p q)))))) |
(my-and (id 'p) (id '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> |