Tareas2011

Tarea #1

1.   Probar que ¬(PÙQ) es equivalente a (¬P) Ú(¬Q) y que ¬(PÚQ) es equivalente a (¬P)Ù(¬Q)

2. Probar que PÙ(QÚR) es equivalente a (PÙQ)(ÚPÙR) y que PÚ(QÙR) es equivalente a (PÚQ)Ù(PÚR)

3.   Mostrar que la siguiente proposición es una contradicción:  ((PÚQ)Ù¬P)Ù¬Q

4.   Mostrar que ¬$ x P(x) es equivalente a "x ¬ P(x).

5.   ¿Cuales de las siguientes proposiciones son tautologías?
a)¬(PÚQ) « (¬P)Ù(¬Q)
b) (PÙ¬P) ® Q
c) (PÚ¬P) Ù (QÚ¬Q)

6. Hacer la tabla de verdad de
a) (P Ù Q)Ú (ØP Ù Q) Ú (P Ù ØQ) Ú (ØP Ù ØQ)

7. Probar la equivalencia de las siguientes expresiones usando tablas de verdad.
a) (P « Q) º (P ® Q) Ù (Q ® P)
b) (P Ù Q)Ú (Q Ù R) º Q Ù (P Ú R)
c) Ø (ØP ØÚ (R Ú S)) º (P Ù R) Ú (P Ù S)
d) (P Ú R) Ù (Q Ú S) º (P Ù Q) Ú (P Ù S) Ú (R Ù Q) Ú (R Ù S)

8. En el dominio delos animales, ¿cómo traduciría las expresiones siguientes?
a) Todos los leones son predadores.
b) Algunos leones viven en África.
c) Sólo rugen los leones.
d) Algunos leones comen cebras.
e) Algunos leones solo comen cebras.

Tarea #2

1. Dados A = {1, 3, 4, 6, 8, 9} y B = {2, 3, 4, 5, 8, 11, 12} sobre el universo U = {1, 2, 3, ...20}, calcular
a) A È B
b) A Ç B
c) complemento de A
d) A - B
e) B -A

2. Dados los conjuntos del problema anterior, muestra que se cumplen las leyes de De Morgan.

3. Demostrar las siguientes igualdades
A - B = A - (B Ç A)

4. Calcule AxB y BxA para los conjuntos A = {1, 2, 5} y B = {a, c, d}.

5. Calcule 2A si A = {a, b, c, d}

6. ¿Son ciertos los siguientes resultados?
a. 2A Ç 2B = 2B Ç A
b. 2A È 2B = 2B È A

Tarea #3

1.   Determinar si cada una de lassiguientes es una relación de equivalencia sobre el conjunto A = {0, 1, 2, 3, 4, 5}
a) R1 = {(0,0),(1,1),(1,2),(2,2),(3,3),(4,4),(5,5)}
b) R2 = R1 È {(2,1)}
c) R3 = R1 – {(1,2)}
d) R4 = R2 È {(2,3),(1,3),(3,1),(3,2)}

2.   Sean A y B los conjuntos definidos de la siguiente manera
A = {0, 1, 2, 3}
B = {-1, 0, 1/2, 1, 3/2, 2, 3, 4}
¿Cuáles de las siguientes relaciones son funciones totales, cuálesparciales y cuales no son funciones?
a)      f = {(0, 1), (1,2), (2, 3), (3, 4)}
b)      f = {(0, 0), (1, 1/2), (2, 1), (3, 3/2)}
c)      f = {(0, 0), (1, 1), (1, -1), (2, 3)}
d)      f = {(0, 0), (1, 3), (2, 2)}
e)      f = {(0, 0)}

3. Sea f: A  B una biyección. Probar f-–1 que también es una biyección.

4. Probar que si A Í B y A es infinito, entonces B es infinito.

5. Sean f y g dos funcionesdefinidas como

f = {(x, y) | x  N y y  Z+ y y = |x| + 1}
g = {(x, y) | x  Z+ y y  N y y = 2|x|}

Observe que f  N  Z+ y g  Z+  N de modo que f  g y g  f están definidas. Describir f  g y g  f .


 
Tarea #4

1. Probar que para todo n  N
a)  20 + 21 + 22 + ...+ 2n-1 + 2n = 2n+1 - 1
b) 2(n + 2) <= (n + 2)2
c) n3 + 2n es  divisible por 3.

2. Dar, si es posible, un ejemplo decada apartado.
a) Un subconjunto infinito de un conjunto finito
b) Una familia {Ai | i  N} de conjuntos finitos cuya unión sea finita.
c) Una familia{Ai | i  N} de conjuntos finitos cuya unión no lo sea.
d) Unos conjuntos finitos tales que |A È B|  |A| + |B|

Tarea #5

1. Encuentre todas las cadenas prefijo, sufijo y subpalabras de la palabra w = “curso”

2. Sea el alfabeto  = {a, b, c},enliste todas las palabras del lenguaje L sobre este alfabeto que constan de cadenas de 3 caracteres y que son palíndromos (un palíndromo es una cadena que se lee igual en los sentidos, p. e. aba.

3. Sea L1 = {ac, ab, aab} y L2 = {ca, ba, cc}, encuentre L1L2 y L2L1.

4. Para  = {a, b, c} usando una representación ternaria con los dígitos 1, 2, 3. Supongamos que a esta asociado con 1, b con 2 y c con 3¿cuál será el entero decimal que corresponde a la palabra abbacca de *? Encontrar la palabra de * correspondiente a 20.

5. Sea  = {a, b}. Sea L el lenguaje formado por todas las palabras sobre  con igual número de a’s que de b’s y L’ = {ambn | m, n>= 0}. Defina L Ç L’.

6. Sean  y L’ como en el ejercicio anterior y L el lenguaje formado por todas las palabras sobre  que tienen un número...