6.045J/18.400J: Autmatas, computabilidad y complejidad Prof. Ron Rivest

Fotocopias 2: problemas de repaso Mircoles 7 de 2002 Jonathan Herzog Problema 1: construya tablas de verdad para las siguientes frmulas. Para cada par de frmulas, indique qu afirmaciones se sostienen de las que se citan a continuacin:

Son equivalentes. No son equivalentes, pero una supone la otra (asegrese de indicar cul es cul). Ninguna de las anteriores: 1. 2. 3. 4. 5. ( )

p qp qp q

p qp q

Problema 2: una frmula booleana est en forma normal disyuntiva cuando se encuentra en la forma 1 2 3 1 2 3( ...) ( ...) ...x x x x x x

1. Halle una frmula booleana en forma normal disyuntiva que sea equivalente a: (a) ( )(b) ( )

p q rp q r

2. Realice un esquema que demuestre que cualquier frmula booleana tiene una frmula

equivalente en forma normal disyuntiva. Problema 3: suponga que R es una relacin en un conjunto A no vaco. Defina Rt para que sea la interseccin de todas las relaciones transitivas en A que contengan R. Demuestre que Rt es transitivo y que es la menor relacin transitiva en A que contiene R.

Problema 4: sea {def= ^( , ) : .(u })R R x y z xRz zRy . Es Ru = Rt anterior? Demuestre que es cierto o encuentre un contraejemplo. Problema 5: en un rbol binario, cul es la relacin entre el nmero de nodos internos y el nmero de hojas? Demuestre su respuesta. Problema 6: cree un autmata, como los vistos en clase, que acepte el lenguaje Li = {x : x como nmero binario mltiplo de i}, donde: 1. 22. 43. 6

iii

===

1

Fotocopias 2: problemas de repaso