Proposiciones, vectores binarios y Conjuntos finitos Rafael F. Isaacs G.

*

Fecha: 24 de octubre de 2004 Trataremos de matar tres p´ajaros de un solo tiro. Nuestro objetivo no es descabellado, realmente el ´algebra que se trabaja en los vectores binarios, en los conjuntos finitos y la l´ogica de proposiciones es el ´ algebra booleana. La misma que tambi´en que se realiza en los circuitos electr´onicos.

1.

Nada depende de UNO, todo resulta de DOS

En principio tenemos el bien y el mal, el yin y el yang, dios y el diablo, la verdad y la falsedad, los pares y los impares. De esta divisi´on arbitraria y r´ıgida se genera toda la diversidad. Debemos trabajar entonces un conjunto con dos elementos que pueden ser Falso, Verdadero, o bien F , V , o lo que es lo mismo 0, 1. En principio identificaremos el 0 con la falsedad y el 1 con la verdad que son los valores de verdad que pueden tomar las proposiciones. Las letras p, q, r servir´an para referirnos a proposiciones que pueden ser falsas o verdaderas, el lector debe conocer las tablas de verdad para los conectivos l´ ogicos, que se refieren a c´omo las combinaciones de esas proposiciones producen nuevas proposiciones, por ejemplo la tabla de verdad del ´o exclusivo, corresponde a la suma m´odulo 2 que es la suma de los pares y los impares p q p∨q 1 1 0 1 1 0 0 1 1 0 0 0 mientras que la suma m´odulo 2 en el conjunto {0, 1} se da seg´ un la siguiente tabla + 0 1 0 0 1 1 1 0 El lector identificar´a las dos tablas como expresiones del mismo fen´omeno. Los conectivos l´ogicos usuales son la negaci´on que notaremos ¬(de un s´olo argumento) y los binarios: la disjunci´on, notada con el signo ∨, al conjunci´on (∧), la implicaci´on (⇒) la equivalencia (⇔), la cual se puede considerar como una igualdad. *

Profesor titular UIS

1

1.1.

F´ ormulas Proposicionales

Las f´ormulas proposicionales se obtienen combinando correctamente variables proposicionales con conectivos l´ogicos y s´ımbolos de agrupamiento. Tomando como variables p,q,r, se pueden definir recursivamente as´ı: Definici´ on 1. Las f´ormulas proposicionales sobre las variables p,q,r, se definen recursivamente as´ı: Base : p, q, r son f´ormulas proposicionales. Paso Recursivo : si α y β son f´ormulas proposicionales tambi´en lo son:(¬α), (α ∧ β), (α ∨ β), (α ⇒ β) y (α ⇔ β). Nuestro alfabeto en este caso ser´ıa {p, q, r, ¬, ∨, ∧, ⇒, ⇔, (, )}. Seguir estrictamente estas reglas para formar f´ormulas puede resultar engorroso y redundante en cuanto al exceso de par´entesis por lo cual en la pr´actica, ´estos se eliminan desde que no haya lugar a confusi´on. Todos los conectivos l´ogicos (¿cu´antos hay?) se pueden desarrollar a partir de unos pocos, por ejemplo de ¬ y ∧: p ∨ q : ¬(¬p ∧ ¬q) p ⇒ q : ¬(p ∧ ¬q) p ⇔ q : ¬(p ∧ ¬q) ∧ ¬(¬p ∧ q) p∨q : ¬(¬p ∧ ¬q) ∧ ¬(p ∧ q) Por esta raz´on el conjunto {¬, ∧} se dice que es un conjunto completo de conectivos. Los valores de verdad en la l´ogica cl´asica son exactamente los elementos de Z2 . Las f´ormulas proposicionales tiene valor de verdad seg´ un el valor de verdad de sus componentes. Este valor de verdad se halla recursivamente guiados por la construcci´on recursiva de la f´ormula. Esto es lo que se lleva a cabo con las tablas de verdad. Mostramos como ejemplo, la tabla de verdad de la implicaci´on “⇒”: p 0 0 1 1

q ¬q 0 1 1 0 0 1 1 0

(p ∧ ¬q) ¬(p ∧ ¬q) 0 1 0 1 1 0 0 1

Las tautolog´ıas se identifican porque en sus tablas de verdad siempre se obtiene la verdad, independiente del valor de verdad de las componentes (¡verdad!). Las tautolog´ıas son como los teoremas de la l´ogica de proposiciones, teor´ıa muy particular por cuanto sus teoremas se pueden establecer tanto por deducci´on axiom´atica , como por aplicaci´on de un algoritmo, que consiste exactamente en elaborar la tabla de verdad. Algunas tautolog´ıas son reconocidas como leyes del ´ algebra booleana:

2

Doble negaci´ on : ¬(¬p) ⇔ p Conmutativa : (p ∧ q) ⇔ (q ∧ p)

(p ∨ q) ⇔ (q ∨ p)

Asociativa : (p ∧ q) ∧ r ⇔ p ∧ (q ∧ r)

(p ∨ q) ∨ r ⇔ p ∨ (q ∨ r)

Distributiva : (p ∨ q) ∧ r ⇔ (p ∧ r) ∨ (q ∧ r) (p ∧ q) ∨ r ⇔ (p ∨ r) ∧ (q ∨ r) Morgan : ¬(p ∨ q) ⇔ (¬p ∧ ¬q) ¬(p ∧ q) ⇔ (¬p ∨ ¬q) Tercio excluido : (p ∨ ¬p) ⇔ V Absorci´ on : p ∧ (p ∨ q) ⇔ p

(p ∧ ¬p) ⇔ F.

p ∨ (p ∧ q) ⇔ p

Identidad : (p ∧ V) ⇔ p (p ∨ F) ⇔ p. Dominancia : (p ∨ V) ⇔ V (p ∧ F) ⇔ F. Idempotencia : (p ∨ p) ⇔ p (p ∧ p) ⇔ p.

En estas tablas V significa la verdad (absoluta) y F la falsedad o la contradicci´on. Hemos elaborado s´olo algunas de las equivalencias que se tienen involucrando a los conectivos ∨, ∧, ¬ en donde se cumple el principio de dualidad. N´otese que las tautolog´ıas de la derecha se obtienen intercambiando ∨ por ∧ y F por V en las de la izquierda. El principio de dualidad nos dice que si tenemos una tautolog´ıa donde interviene ∨, ∧, ¬ al hacer dichos intercambios lo que se obtiene tambi´en es tautolog´ıa. Para ello es necesario que la tautolog´ıa sea una equivalencia.

1.2.

Demostraciones

La mayor´ıa de las proposiciones de la matem´atica son de tipo “si p entonces se debe cumplir q”, abreviadamente p ⇒ q, en donde p juega el papel de hip´otesis y q el de tesis o conclusi´on. Se pueden dar diferentes versiones idiom´aticas de ´este conectivo l´ogico; en espa˜ nol se usa “si p entonces q”, “p implica q”, “q siempre que p”, ”para que suceda p es necesario que q”, “para que q es suficiente que p”, etc. Sea p, por ejemplo, la proposici´on “a y b son pares q la proposici´on “a + b es par”, p ⇒ q se puede leer: “Si a y b son pares entonces a + b tambi´en lo es”, como quien dice “la suma de dos pares es un par”, o, “condici´on suficiente para que a + b sea par es que a y b sean pares”. La rec´ıproca de la proposici´on p ⇒ q es la proposici´on q ⇒ p que en general tiene diferente valor de verdad. En el ejemplo anterior, mientras “la suma de pares es par”es una proposici´on cierta, su rec´ıproca “si la suma de dos n´ umeros es par entonces ambos n´ umeros son pares”es falsa, puesto que 5 + 3 es par siendo uno de los sumandos impar (realmente ambos ¡pero con unos es suficiente!). La contrarrec´ıproca de la proposici´on p ⇒ q es la proposici´on ¬q ⇒ ¬p que es equivalente a la original, por lo tanto, para demostrar una implicaci´on podemos demostrar su contrarrec´ıproca. 2

3

As´ı, para, mostrar que “todo par elevado al cuadrado es par”(n par implica n2 par) podemos mostrar que ”si el cuadrado de un n´ umero es impar, el n´ umero debe ser impar”(n2 no par implica n no par) que es equivalente. En el ejemplo inicial la contrarrec´ıproca de “la suma de dos pares es un par”es la proposici´on “si la suma de dos n´ umeros no es par entonces ambos n´ umeros no pueden ser pares.o lo que es lo mismo “si la suma de dos n´ umeros no es par entonces alguno de los n´ umeros es impar”. Muchas veces la hip´otesis o la tesis viene en forma de conjunci´on o disyunci´on. Por ejemplo la forma (p ∧ q) ⇒ r, que es la forma de la proposici´on que acabamos de analizar. En efecto, si convenimos en que p, r, q sean las proposiciones “a es par”, “b es par”, “a + b es parrespectivamente, se ve m´as claramente porqu´e la contrarec´ıproca tiene como conclusi´on que alguno de los n´ umeros es impar, ya que la negaci´on de p ∧ qes ¬p ∨ ¬q y la forma de la contrarec´ıproca ser´a r ⇒ (¬q ∨ ¬p). Probar la contrarec´ıproca es hacer la prueba por contradicci´on: Para demostrar p ⇒ q se supone que la conclusi´on no es cierta (pensemos lo peor) o sea ¬q y se deduce que la hip´otesis fallar´ıa o sea que ¬p; se est´a demostrando que ¬q ⇒ ¬p. Otra propiedad que nos interesa resaltar de la l´ogica de proposiciones es que la negaci´on de una implicaci´on p ⇒ q es equivalente a ¬(p ∧ ¬q). Esta es la raz´on para que negar la proposici´on “la suma de dos n´ umeros es impar implica que ambos son pares”, sea afirmar que “existen n´ umeros cuya suma es par sin que ambos sean pares”. La equivalencia entre p==¿q y (p q) nos ayuda tambi´en a explicar las demostraciones por contradicci´on: Se trata de ver que es imposible que se cumpla la hip´otesis sin que se cumpla tambi´en la tesis. Cuando tanto p ⇒ q como su rec´ıproca q ⇒ p, son ciertas se dice que p y q son equivalentes y se nota p ⇔ q. Por ejemplo, “n2 es par “n es par”son proposiciones equivalentes, pues tanto “si n2 es par entonces n es par” como “si n es par su cuadrado tambi´en lo es”son proposiciones ciertas. Otras versiones idiom´aticas para esta equivalencia son: “a es par s´ı y s´olo s´ı a2 lo es” o “condici´on necesaria y suficiente para que n2 sea par es que n lo sea. La equivalencia tambi´en se utiliza en las definiciones, por ejemplo para definir par podemos decir “n es par s´ı y s´olo s´ı existe un entero k tal que a = 2k”. Las equivalencias l´ogicas (tautol´ogicas) son v´alidas por su forma sin importar el contenido de las proposiciones ’internas’. As´ı, “k no es primo par s´ı y s´olo s´ı k no es primo o k es impar”, es una equivalencia v´alida por su forma pues ¬(p ∧ ¬q) ⇔ (¬p ∨ q) es cierta sin importar el valor de verdad de p y q. La tabla 1 muestra una lista de las principales equivalencias l´ogicas. Digamos para terminar esta secci´on, que siempre que p y q sean equivalentes la proposici´on p se puede reemplazar por q y el rev´es. Especial atenci´on merece el conectivo ⇒ es decir la implicaci´on, que no es conmutativo y que es el que da car´acter deductivo a la l´ogica simb´olica. Cuando una implicaci´on es una tautolog´ıa da lugar a que el antecedente se puede reemplazar por la concecuencia. Por ejemplo, p ⇒ (p ∨ q) entonces si tengo p como cierto, tambi´en ser´a cierto (p ∨ q), pero n´otese que teniendo p ∨ q no puedo deducir p. Cuando una equivalencia es tautolog´ıa se pueden reemplazar como queramos los extremos, tenemos entonces identidades l´ogicas. Enseguida presentamos algunas tautolog´ıas referentes a la implicaci´on: 2

4

Figura 1: George Boole

Figura 2: Caricatura de Auguste de Morgan, dibujada por un alumno 5

Contrarrec´ıproca : (p ⇒ q) ⇔ (¬q ⇒ ¬p) Implicaci´ on como disjunci´ on : (p ⇒ q) ⇔ (¬p ∨ q) Negaci´ on de la implicaci´ on : ¬(p ⇒ q) ⇔ (p ∧ ¬q). Equivalencia como implicaci´ on : p ⇔ q ⇔ (p ⇒ q) ∧ (q ⇒ p) Exportaci´ on : (p ∧ q) ⇒ r) ⇔ (p ⇒ (q ⇒ r). Modus Ponens : (p ∧ (p ⇒ q)) ⇒ q.

1.3.

Ejercicios

1. Seg´ un la definici´on 1 cu´ales de las siguientes expresiones no son f´ormulas proposicionales sobre p,q,r? a) (p ∧ (¬q)) b)(¬p ∧ (¬q)) c) p ∧ (¬q)) b)((¬p) ∧ (¬q)) 2. Construya las tablas de verdad de los conectivos: ¬, ∨, ∧, ⇒, ⇔, ⇐ 3. Sea p la proposici´on “Hay buen tiempo”, q : “Hay buenas cosechas”, r : “Los precios suben”. Exprese las siguientes afirmaciones con f´ormulas proposicionales en las variables p, q, r: a) Hay buen tiempo y buenas cosechas y sin embargo los precios suben. b) Si hay buen tiempo hay buenas cosechas y los precios bajan. c) Si hay buen tiempo y buenas cosechas entonces los precios bajan. d ) Si los precios bajan es porque hay buen tiempo y buenas cosechas. e) Si los precios bajan entonces hay buen tiempo y buenas cosechas. f ) Para que hayan buenas cosechas y los precios bajen es necesario que haya buen tiempo. 4. Demostrar que {¬, ∨} es un sistema completo de conectivos l´ogicos. 5. Escriba la negaci´on de las siguientes afirmaciones. a) Soy bueno y honesto. b) Es pobre pero de buena familia. c) Como nunca viene entonces no se dar´a cuenta. d ) Si es lunes es un d´ıa dif´ıcil. e) Juan sali´o a jugar y por lo tanto no est´a. f ) Si a divide a bc entonces a divide a b o bien a divide a c. g) El que asegura eso, no sabe lo que est´a diciendo o es un hip´ocrita. 6

6. La madre de Mafalda le dice: “Si te tomas la sopa te doy dulce”mientras que el padre dice: “si no te tomas la sopa no tomas dulce”. Explique por qu´e el padre es m´as riguroso.

2.

L´ ogica de predicados

La expresi´on “x + 1 = 5” no es una proposici´on ya que no podemos darle un valor de verdad. Cuando tenemos expresiones con variables para que tengan un valor de verdad tenemos dos caminos: o bien reemplazamos la variable por una constante apropiada (podr´ıamos decir “5 + 1 = 5”, aunque sea falso, pero no “Juan + 5 = 1”, que no tiene sentido), o bien podemos colocar cuantificadores a las variables y obtener por ejemplo “∃x(x + 1 = 5)”, que se lee: Existe un x tal que x + 1 = 5. Un predicado es una expresi´on p(x1 , . . . , xn ) donde los x1 , . . . , xn son variables. Los predicados pueden operarse como las proposiciones con conectivos l´ogicos, pero adem´as, permiten se modificados por cuantificadores. El uso de cuantificadores supone un universo donde puedan estar las variables. Si nuestro universo es finito por ejemplo sus elementos son a1 , a2 , . . . an entonces p(a1 ) ∨ p(a2 ) . . . ∨ p(an ) =

n _

p(ai ) = ∃x (p(x))

i=1

p(a1 ) ∧ p(a2 ) . . . ∧ p(an ) =

n ^

p(ai ) = ∀x (p(x))

i=1

Notar´a el lector, que los cuantificadores universal ∀ (para todo) y existencial ∃ (existe), se pueden entender como una generalizaci´on de los conectivos ∧ y ∨, a´ un en el caso infinito. Citamos algunas propiedades fundamentales de estos cuantificadores, no independientes, pues algunas se pueden demostrar de las otras. Negaci´ on del Universal : ¬(∀x(p(x)) ⇔ ∃x(¬p(x)) Negaci´ on del Existencial : ¬(∃x(p(x)) ⇔ ∀x(¬p(x)) Conjunci´ on del Universal : ∀x(p(x) ∧ q(x)) ⇔ (∀x(p(x)) ∧ ∀x(q(x))) Disjunci´ on del Existencial : ∃x(p(x) ∨ q(x)) ⇔ (∃x(p(x)) ∨ ∃x(q(x))) Conjunci´ on del Existencial : ∃x(p(x)∧q(x)) ⇒ (∃x(p(x))∧∃x(q(x))) Disjunci´ on del Universal : ∀x(p(x) ∨ q(x)) ⇐ (∀x(p(x)) ∨ ∀x(q(x))) Los cuantificadores pueden aparecer varias veces en un predicado desde que se refieran a variables no cuantificadas anteriormente. Dos cuantificadores del mismo tipo que aparecen seguidos se pueden intercambiar, no as´ı cuando son de diferente tipo. Adem´as de la existencia de un elemento que cumple una propiedad a veces es u ´til garantizar que tal elemento es u ´nico. Se usa el cuantificador ∃! que se lee “existe un u ´nico” y que se define as´ı: ∃!(p(x)) ⇔ ∃x(p(x)) ∧ ∀x∀y((p(x) ∧ p(y)) ⇒ x = y) 7

Esto no muestra c´omo demostrar que una soluci´on a un problema es u ´nica: se suponen dos soluciones y se concluye que son iguales. Demostrar la unicidad de una soluci´on es mucho m´as u ´til y necesario de lo que a primera vista aparece. Por otra parte, se acostumbra especificar el universo de la variable con el cuantificador, se usa por ejemplo ∀x ∈ A, pero estrictamente hablando esto s´olo es una abreviatura, as´ı: ∀x ∈ A(p(x)) ⇔ ∀x(x ∈ A ⇒ p(x))

2.1.

Ejercicios

1. Dar un ejemplo de un predicado de dos variables p(x, y) tal que ∀x∃y(p(x, y)) no sea equivalente a ∃y∀x(p(x, y)) 2. Escriba la negaci´on de los siguientes predicados: a) ∀x(p(x) ∧ ¬q(x)) b) ∀x(p(x) ⇒ q(x)) c) ∃x(p(x) ∧ ¬q(x)) d ) ∃x(p(x) ∨ ¬q(x)) e) ∀x(p(x) ∧ ¬q(x)) ∧ ∀y(¬p(y) ∨ q(y)) f ) ∀x∀y(p(x, y) ⇒ q(x, y)) g) ∀x∃y(p(x, y)) 3. Las siguientes proposiciones son falsas. D´e en cada caso un contra ejemplo: a) Si a2 no es par a3 s´ı lo es. b) n2 + 2n siempre es par. c) Si n es primo 2n − 1 tambi´en lo es. d ) Si n es positivo n3 − 6n2 + 11n − 6 = 0. 4. Analice la veracidad de los siguientes predicados de la aritm´etica sabiendo que el universo son los n´ umeros enteros. a) ∀n∃k(n2 = 4k + 1 ⇒ n = 4k + 1)) b) ∀n(∃k(n2 = 4k + 1) ⇒ ∃k(n = 4k + 1)) c) ∀n(∃k(n = 2k + 1 ∨ n = 2k) d ) ∀n((n|12 ∧ n|16) ⇒ n|2) e) ∃m(∀n(m|n)) f ) ∃n(∀m(m|n)) g) ∀n∀m∀r((n|m ∧ m|r) ⇒ (n|r)) h) ∀m∀n(2|(n + m) ⇒ 2|(n − m)) 5. Demuestre que las siguientes equivalencias son ciertas: 8

a) ¬(∀x(p(x) ∧ ¬q(x))) ⇔ ∃x(¬p(x)) ∨ ∃x(q(x)) b) ¬(∀x(p(x) ⇒ ¬q(x))) ⇔ ∃x(p(x) ∧ q(x)) c) ∃x¬(p(x) ∧ ¬q(x)) ⇔ ∃x(¬p(x)) ∨ ∃x(q(x)) 6. La negaci´on de “existen n´ umeros pares cuyo cuadrado es impar”es (escoja lo correcto): a) b) c) d)

3.

“existen n´ umeros pares cuyo cuadrado es par” “existen n´ umeros impares cuyo cuadrado es impar” “Todo n´ umero par tiene cuadrado par” “Todo n´ umero impar tiene cuadrado impar”

Algebra de conjuntos

Cuando se cuantifican todas las variables que aparecen en un predicado se obtiene una proposici´on que puede ser falsa o verdadera. Cuando una variable no se cuantifica el predicado p(x) da lugar al conjunto de los elementos que cumplen el predicado, este conjunto se nota as´ı: {x | p(x)} Esto nos permite definir much´ısimos conjuntos, por ejemplo el conjunto vac´ıo se podr´ıa definir as´ı: ∅ = {x | x 6= x} Hay que ser cuidadosos con tener bien claro el universo de d´onde se escogen los elementos para determinar el nuevo conjunto. Si definimos A = {x | p(x)} estamos diciendo que (x ∈ A) ⇔ (p(x)) pero ¡cuidado! Expresiones como {x | x ∈ / x} lleva a contradicciones por cierto muy interesantes, contradicciones y paradojas (por ejemplo la “paradoja del Barbero”) que han jugado un papel muy importante en el desarrollo de la Teor´ıa de Conjuntos. Los predicados fundamentales de conjuntos son del tipo x ∈ A que se lee “x es un elemento de A”. Aqu´ı trataremos de seguir la buena costumbre de notar siempre los elementos con letras min´ usculas y los conjuntos con may´ usculas. Pero la distinci´on entre elemento y conjunto no es esencial, podr´ıamos considerar que todos los entes de nuestro universo son conjuntos! Las definiciones del ´algebra de conjuntos se pueden dar en t´erminos de la l´ogica de proposiciones y de predicados como se indican en la siguiente tabla. A ∪ B =: {x | x ∈ A ∨ x ∈ B} A ∩ B =: {x | x ∈ A ∧ x ∈ B} Ac =: {x | x ∈ / A} A ⊆ B ⇔: ∀x(x ∈ A ⇒ x ∈ B} A = B ⇔: ∀x(x ∈ A ⇔ x ∈ B}

9

Ejemplo 1. Las propiedades del ´algebra de conjuntos est´an ´ıntimamente ligadas con las de la l´ogica. Por ejemplo las leyes de Morgan para conjuntos se traducen en (A ∩ B)c = Ac ∪ B c y (A ∪ B)c = Ac ∩ B c y ´esta u ´ltima se puede demostrar as´ı: (A ∪ B)c =: {x | x ∈ / (A ∪ B)} = {x | ¬(x ∈ A ∨ x ∈ B)} = {x | x ∈ / A∧x∈ / B} c = {x | x ∈ A ∧ x ∈ B c } = Ac ∩ B c La esencia de la demostraci´on yace en aplicar la tautolog´ıa: ¬(p ∨ q) ⇔ (¬p ∧ ¬q).

Figura 3: John Venn (1834-1923 Las leyes entonces del ´algebra de conjuntos son las mismas de la l´ogica de proposiciones, es decir las del ´algebra booleana. Enseguida traducimos las planteadas anteriormente.

10

(A ⊆ B) ⇔ (B c ⊆ Ac ) (A ⊆ B) ⇔ (Ac ∪ B) = U (A ⊆ B) ⇔ (A ∩ B c ) = ∅. A = B ⇔ (A ⊆ B) ∧ (B ⊆ A) ((A ∩ B) ⊆ C) ⇔ (A ⊆ C ∧ B ⊆ C) (U ⊆ A ⇒ A = U ) En lo anterior, y en lo que sigue, debe entenderse U como el conjunto universal, el cual hace el papel de V en l´ogica de proposiciones. El lector comprender´a que los enunciados ciertos en el ´algebra de conjuntos son infinitos y que conviene reducirlos a unos pocos axiomas de los cuales se deduzcan todos. Este es el m´etodo axiom´atico, una forma muy eficaz y antigua de comprimir informaci´on! Pues bien, hay varias formas de dar axiomas para el ´algebra booleana, sin embargo por ahora no es nuestro inter´es abordar esta tem´atica. Nuestro inter´es es investigar la veracidad de alguna afirmaci´on de manera intuitiva o reduci´endola a su forma l´ogica. Un tratamiento bastante pr´actico es utilizar diagramas de Venn que consiste en simular la situaci´on con conjuntos en un sector del plano. Ejemplo 2. Para analizar la veracidad de (A ∪ B)c ∩ C = Ac ∩ B c ∩ C por medio de diagramas de Venn mostramos la siguiente gr´afica: En la figura de la izquierda mostramos

Figura 4: (A ∪ B)c ∩ C = Ac ∩ B c ∩ C (A ∪ B)c en color amarillo. En la central representamos (A ∪ B)c ∩ C y a la derecha las l´ıneas amarillas verticales son el complemento de A y las de fondo rojo son el complemento de B, as´ı Ac ∩ B c aparece con l´ıneas verticales amarillas y fondo rojo. Se ve entonces que (A ∪ B)c ∩ C = Ac ∩ B c ∩ C. Esta afirmaci´on del ´algebra de conjuntos corresponde a la tautolog´ıa: (¬(p ∨ q) ∧ r) ⇔ (¬p ∧ ¬q ∧ r)

3.1.

Ejercicios

1. Representar con diagramas de Venn los siguientes conjuntos: 11

a) Ac ∩ B c b) Ac ∩ (B c ∩ C) c) Ac ∪ (B c ∩ C) 2. Si A, B, C son conjuntos entonces: a) A ∩ (B ∪ C) = (A ∪ B) ∩ (A ∪ C) b) (A ∪ B)c = Ac ∩ B c c) A ∩ (B ∩ C)c = A ∩ (B c ∩ C c ) d ) Todas las anteriores son ciertas. e) Todas las anteriores son falsas. 3. Si se tiene A ∩ (B ∩ C) = ∅ podemos asegurar: a) A ⊆ B b) A ⊂ (B ∩ C) c) A ∩ B = ∅, y adem´as A ∩ C = ∅ d ) Todas las anteriores son ciertas. e) Todas las anteriores son falsas. 4. Demostrar reduciendo a tautolog´ıas y comprobar con diagramas de Venn las siguientes afirmaciones del ´algebra de conjuntos: a) Ac ∩ B c = ∅ ⇔ (A ∪ B) = U b) A ⊆ (B c ∩ C) ⇔ (B ⊆ Ac ) ∧ (A ⊆ C) 5. la diferencia sim´etrica de A y B que se nota A 4 B se define como A 4 B = (A ∩ B c ) ∪ (Ac ∩ B) demostrar: a) (A 4 B)c = (A ∪ B c ) ∩ (Ac ∪ B) b) A 4 B = B 4 A c) (A 4 B) 4 C = A 4 (B 4 C) 6. i) 0 ∈ A ii) Si x ∈ A entonces (x + 2) ∈ A y (x − 2) ∈ A ¿Cu´al es el menor subconjunto A de los reales que cumple i) y ii)? 7. Sea Σ = {a, b} se define recursivamente el lenguaje L (un lenguaje es cualquier subconjunto de palabras) as´ı i) Base: a ∈ L ; bb ∈ L. ii) Paso inductivo: Si w ∈ L entonces ww ∈ L. iii) Clausura: Las palabras de L se forman u ´nicamente aplicando i) y ii).

12

¿Cu´ales de las siguientes palabras pertenecen a L? a. aaaa b. bbb c.abbabb d.λ

4.

Familias de Conjuntos

Un conjunto cuyos elementos son conjuntos lo denominamos una familia de conjuntos. Esta distinci´on entre conjuntos y familias no es te´orica sino m´as bien pedag´ogica. La teor´ıa de conjuntos se desarrolla considerando todos sus entes como conjuntos. Una familia de conjuntos es por ejemplo P (X) el conjunto de todos los subconjuntos de un conjunto X. En general utilizaremos letras caligr´aficas A, B, C, T para notar familias de conjuntos. Tambi´en se usa notaci´on subindizada A = {Ai | i ∈ I} = {Ai }i∈I aqu´ı I es un conjunto cualquiera de ´ındices y para cada i ∈ I se supone un conjunto Ai en la familia. Las operaciones que se han visto entre conjuntos, son solamente v´alidas para familias finitas de conjuntos, realmente para familias de dos conjuntos del tipo A = {A1 , A2 } = {Ai }i∈I cuando I = {1, 2}. Como estas definiciones est´an fundamentadas en los conectivos ∨ y ∧ y ´estos se generalizan a los cuantificadores ∃ y ∀, dicha generalizaci´on nos permite dar la definici´on general y muy natural. Definici´ on 2. Sea F = {Ai }i∈I una familia de conjuntos, definimos: [ [ Ai = {x | ∃i(i ∈ I ∧ x ∈ Ai )} F= i∈I

\

F=

\

Ai = {x | ∀i(i ∈ I ⇒ x ∈ Ai )}

i∈I

Definici´ on 3. Sea X un conjunto. Una familia F ⊆ P(X) es una partici´ on de X si se cumple: i) ∅ ∈ /F ii) Si A, B ∈ F y A 6= B entonces A ∩ B = ∅ (se dice que los conjuntos de F son disjuntos dos a dos). S iii) F = X Ejemplo 3. {{z ∈ Z | z ≡ n( mod m)}n∈N } es una partici´on de Z en m conjuntos, cada uno de ellos infinito.

13

4.1.

Ejercicios

1. Describir los elementos de los siguientes subconjuntos de R: T∞ 1 a) i=1 [i − 1, i + i ) T∞ 1 b) i=1 [0, 1 + i ) S∞ 1 c) i=1 [0, 1 − i ] T∞ 1 1 d) i=1 [− i , 1 − i ] 2. Demostrar las siguientes afirmaciones cuando {Ai }i∈I es una familia de conjuntos: T S a) ( i∈I Ai )c = i∈I (Ai )c S T b) ( i∈I Ai )c = i∈I (Ai )c T T c) i∈I (Ai ∪ B) = ( i∈I Ai ) ∪ B T T d ) Si ∀i ∈ I(Ai ⊆ Bi ) entonces i∈I Ai ⊆ i∈I Bi 3. Se particionan los enteros entre 0 y 11 seg´ un dejen el mismo residuo al ser divididos entre 3. Especifique los elementos de esta partici´on. 4. Las siguientes familias de conjuntos no forman una partici´on de Z. ¿Qu´e propiedad falla? a) {{nk ∈ Z | k ∈ N( mod m)}n∈N } b) {{z ∈ Z | |z − n| ≤ 2( mod m)}n∈N } c) {{z ∈ Z | |z − n| ≤ 2( mod m)}n∈Z } d ) {{z ∈ Z | |z − 3n| ≤ 2( mod m)}n∈N } 5. Determine de las siguientes familias de conjuntos cu´ales forman una partici´on de R. a) {{xk ∈ R | k ∈ N( mod m)}x∈R } b) {{x + k ∈ R | k ∈ Z( mod m)}x∈R } c) {(n − 12 , n + 12 ]}n∈Z } d ) {[n − 21 , n + 12 ]}n∈Z } T S 6. Si I = ∅ ¿ qu´e es i∈I Ai y i∈I Ai ? Justifique su respuesta.

5.

Algo de conteo: Conjuntos Finitos

En las ciencias de la computaci´on saber contar es algo muy importante, piense en la importancia de este arte, llamado tambi´en combinatoria, para comparar la eficiencia de dos algoritmos. Empezaremos contando los elementos de ciertos conjuntos, ´estos que se dejan contar con n´ umeros naturales son los conjuntos finitos. Definici´ on 4. El n´ umero de elementos de un conjunto finito A se llama el cardinal de A y se nota |A|. En este caso A se puede expresar as´ı: A = {a1 , a2 , . . . , an }. 14

5.1.

Vectores Booleanos

La manera natural de tratar los conjuntos finitos computacionalmente es por medio de vectores que en sus componentes siempre llevan 0’s o 1’s, o lo que lo mismo, palabras sobre el alfabeto Σ = {0, 1}. Si A es un conjunto dentro de un universo U con n ∈ N elementos, A queda determinado por un vector A[i] de n componentes donde el valor de A[i] es 0 o 1 si el i-´esimo elemento de U no est´a o est´a en A. Los vectores booleanos tambi´en se pueden entender como entradas a una m´aquina que debe devolver valores de 0 o 1 seg´ un las entradas. Ejemplo 4. Para mostrar los n´ umeros una calculadora se usan siete diales que forman un ocho. Supongamos que se quiere controlar el dial superior horizontal. Este se prende

Figura 5: Diales para expresar los n´ umeros en una calculadora con los n´ umeros 0, 2, 3, 5, 6, 7, 8, 9 es decir no se prende con 1 y 4 de los n´ umeros de la calculadora. Necesitamos hacer un mecanismo que responda con 0 cuando entran los vectores booleanos 0001 y 0100 y que responda 1 ante los est´ımulos 0000, 0010, 0011, 0101, 0111, 1000 y 1001. Para simplificar suponemos que los dem´as vectores booleanos de 4 componentes no se dan. Si representamos por (x1 , x2 , x3 , x4 ) el vector que entra, la salida que queremos es ¬((¬x1 ∧ ¬x2 ∧ ¬x3 ∧ x4 ) ∨ (¬x1 ∧ x2 ∧ ¬x3 ∧ x4 )). Ahora bien estas expresiones l´ogicas se pueden realizar en circuitos electr´onicos. ¡He aqu´ı la base te´orica del hardware!

5.2.

Otras Cuentas

Proposici´ on 1. El n´ umero de palabras de longitud n sobre una alfabeto de m elementos es mn . Si Σn = {w ∈ Σ∗ | |w| = n} |Σn | = |Σ|n . Demostraci´on. Si tenemos palabras mn de longitud n para formar palabras de longitud n + 1 podemos y debemos agregar una letra dentro de m posibles. Por tanto por cada una de las mn palabras sobre una alfabeto de m elementos formamos exactamente m palabras de longitud m + 1, en total obtenemos mn × m = mn+1 palabras de longitud n + 1. Demostraci´on. Procedemos por inducci´on sobre n la longitud de la palabra. Es claro para n = 0 pues Σ0 = {λ} (y para 1 tambi´en:Σ1 = Σ). 15

Proposici´ on 2. Sea X un conjunto finito y notemos P(X) al conjunto que consta de todos los subconjuntos de X. Entonces: |P(X)| = 2|X| Demostraci´on. Simplemente n´otese que hay tantos subconjuntos de X como vectores booleanos de |X| componentes. ¿Cu´al es el cardinal de Ai ∪ A2 , . . . ∪ An ? Empezaremos respondiendo para dos casos que son f´aciles de manipular. Proposici´ on 3. Siendo A, B, C conjuntos: |A ∪ B| = |A| + |B| − |A ∩ B| |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C| Demostraci´on. Probemos que |A ∪ B| = |A| + |B| − |A ∩ B| por inducci´on sobre el n´ umero de elementos de B. Si B = ∅, el resultado es obvio. Supongamos ahora que a B le agregamos un elemento x ∈ / B y hay dos posibilidades: Si x ∈ A entonces |A∪B∪{x}| = |A∪B| = |A|+|B|−|A∩B| pero |A∩(B∪{x})| = |A∩B|+1 mientras |B ∪ {x}| = |B| + 1 entonces |A ∪ B ∪ {x}| = |A| + |B ∪ {x}| − |A ∩ (B ∪ {x})| Si x ∈ / A entonces |A∪B ∪{x}| = |A∪B|+1 = |A|+|B|−|A∩B|+1 pero |A∩(B ∪{x})| = |A ∩ B| mientras |B ∪ {x}| = |B| + 1 entonces |A ∪ B ∪ {x}| = |A| + |B ∪ {x}| − |A ∩ (B ∪ {x})| y queda demostrado que |A ∪ B| = |A| + |B| − |A ∩ B|. Para ver que |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C| lo hacemos aplicando lo anterior: |(A ∪ B) ∪ C| = = |(A ∪ B)| + |C| − |(A ∪ B) ∩ C| = |A| + |B| − |A ∩ B| + |C| − |(A ∩ C) ∪ (B ∩ C| = |A| + |B| − |A ∩ B| + |C| − (|(A ∩ C)| + |B ∩ C| − |A ∩ B ∩ C|) = |A| + |B| − |A ∩ B| + |C| − |(A ∩ C)| − |B ∩ C| + |A ∩ B ∩ C|

Teorema 1 (Principio de Inclusi´ on-Exclusi´ on). Dados A1 , . . . , An ⊆ S then X \ |A1 ∪ · · · ∪ An | = (−1)|J|−1 |AJ | , donde AJ = Ai . i∈J

∅6=J⊆{1,...,n}

16

5.3.

Binomial n k




para n, k ∈ Z as´ı:

Base :Si n < 0 ∨ k < 0 ∨ k > n entonces nk = 0; 00 = 1


n n Paso Recursivo : n+1 = + k+1 k k+1 Definici´ on 5. Se define recursivamente

Proposici´ on.   n n! = k k!(n − k)! Demostraci´on. Pru´ebese que coeficiente binomial.

n! ! k!(n−k)

cumple la base y el paso recursivo de la definici´on del

Proposici´ on. Un conjunto con n elementos tiene exactamente mentos.

n k




subconjuntos con k ele-

Demostraci´on. Sea C(n, k) el n´ umero de conjuntos de k elementos de un conjunto con n elementos. Demostraremos que C(n, k) cumple la ley recursiva del coeficiente binomial. Veamos que C(n + 1, k + 1) = C(n, k) + C(n, k + 1) En efecto, los conjuntos de {a1 , . . . , an , an+1 } con k + 1 elementos los podemos dividir en dos: los que contienen a an+1 que son tantos como los subconjuntos de {a1 , . . . , an } con k elementos y son C(n, k) y por otra parte, los que no contienen a an+1 que son tantos como los subconjuntos de {a1 , . . . , an } con k + 1 elementos y son C(n, k + 1). Como en estas dos familias no hay conjuntos comunes se tiene el paso recursivo de la definici´on de binomial. Que C(n, k) tambi´en cumple la base es inmediato.
Ejemplo 5. El n´ umero de maneras de escoger 5 cartas de la baraja es 52 . De estas “manos” 5 ¿cu´antas son las que tienen al menos una carta de cada palo?. Contemos las que no contienen

52−13 39 un palo espec´ıfico, por ejemplo el diamante: = 5 . Sean A1 , A2 ,
A3 , A4 los conjuntos 5 de 5 cartas que no contiene un palo determinado, entonces |Ai | = 39 . Si i 6= j
entonces 5 Ai
∩ Aj es el conjunto de manos que no contienen los palos
i y j y |Ai ∩
Aj | = 26 y habr´ıa 5 4 13 4 maneras de escoger i, j. As´ı mismo, |Ai ∩ Aj ∩ Ak | = 5 y habr´ıa 3 maneras de escoger 2 i, j, k. Aplicando el principio de inclusi´on exclusi´on hay            52 39 4 26 4 13 4 − + − = 685,464 5 5 1 5 2 5 3 conjuntos de cinco cartas que contienen todos los palos.
Proposici´ on. Hay nk vectores binarios de n componentes que tienen exactamente k 1´s. Teorema 2 (Teorema del Binomio). Para a y b ∈ R, n ∈ N se tiene: X n  n (a + b) = ak bn−k . k k Hay muchas pruebas de esta afirmaci´on. Bosquejamos dos: 17

Demostraci´on. (a + b)n = (a + b)(a + b) . . . (a + b), y se tiene que el coeficiente ak bn−k es el
n n´ umero k-subconjuntos de un n-conjunto — por tanto el coeficiente es k . Demostraci´on. Procedemos por inducci´on sobre n, usando el hecho de que       n n−1 n−1 = + . k k−1 k

Proposici´ on. Si p es primo y 0 < m < p entonces

p m




≡0

(m´od p)
pa Demostraci´on. Haciendo a = (p − 1) . . . (m + 1) tenemos que mp = (p−m! ∈ N por tanto (p − m)! divide a pa pero p y (p − m)! son primos relativos y por
el lema de Euclides, (p − m)! p debe dividir a a, digamos que a = q(p − m)!, de donde = pq y por tanto p divide a m
p . m El teorema del binomio tiene much´ısimas aplicaciones. Como un ejemplo, veamos las siguiente demostraci´on de un teorema clave en la teor´ıa de n´ umeros. Teorema 3 (Teorema d´ ebil de Fermat). Si p es primo entonces ap ≡ a todo a ∈ N.

(m´od p) para

Demostraci´on. Procedemos por inducci´on sobre a. Es obvio cuando a = 0, tomemos a > 0 y supongamos que el teorema es cierto para a − 1. Entonces ap = ((a − 1) + 1)p   p ≡ (a − 1) + 1 mod p porque ≡0 k ≡ a − 1 + 1 mod p ≡ a mod p p

5.4.

(m´od p) salvo para k = 0 o k = p

Ejercicios

1. Para cada una de las siguientes expresiones booleanas p(x, y, z) especifique los elementos del conjunto de vectores booleanos A = {xyz | p(x, y, z) = 1}. a) ¬(x ∨ y) ∧ (z ∧ ¬x) b) ¬(x ∧ ¬y) ∨ ¬(z ∨ ¬x) c) ¬(x ∨ y) ∨ (¬z ∧ ¬x) d ) (x ∧ ¬y) ∨ (z ∧ ¬x) 2. Para cada uno de los siguientes conjuntos encuentre una expresi´on booleana p(x, y, z) en t´erminos de los conectivos ¬, ∨, ∧ (es decir A = {xyz | p(x, y, z) = 1}. a) {010} 18

b) {000,101,110,011} c) {000,001,100,010} d ) {101,110,011,111} 3. ¿Cu´antos n´ umeros hay de tres cifras con todos su d´ıgitos impares? 4. ¿Cu´antos n´ umeros hay de tres cifras con todos su d´ıgitos pares? (Ojo: ¡024 no es de ´estos, ya que es de dos cifras!) 5. Sea X un conjunto con n elementos y F una partici´on de X tal que si A ∈ F entonces |A| = m, determine |F| 6. ¿Cu´antas placas de autos se pueden hacer si deben tener tres letras seguidas con tres d´ıgitos? 7. Una clave para ingreso a una cuenta debe tener entre 4 y 8 letras del alfabeto ingl´es distinguiendo entre may´ usculas y min´ usculas (52 caracteres en total). ¿Cu´antas claves diferentes pueden existir? 8. ¿De cu´antas maneras se puede escoger 3 estudiantes de un grupo de 25? 9. Un equipo de voliball consta de 5 mujeres y 6 hombres, si en la alineaci´on siempre debe haber exactamente dos mujeres. ¿De cu´antas maneras diferentes se pueden escoger los seis jugadores ? 10. Encuentre el valor de cada uno de los siguientes coeficientes binomiales:


a) 10 ; b) 50 ; c) 20 . 0 1 3 11. Demostrar:

a) nn = n0 = 1;

b)

n k




=

n n−k




.

12. Use el teorema del binomio para encontrar todos los t´erminos en la expansi´on de las siguientes expresiones: a) (a + b)5 ;

b) (m − n)7 ;

c) (3x − 4y)7 .

13. ¿Cu´al es el coeficiente de x99 y 101 en la expansi´on de (2x + 3y)200 ?. 14. Demuestre que: n   X n i=0

i

= 2n

( Sugerencia: expanda (1 + 1)n ). 15. Expandiendo (1 + (−1))n , demuestre que: n X

  n (−1) =0 i i=0 i

. 19

16. Usando el ejercicio anterior compare los valores de
n + . . .. 5

n 0




+

n 2




+

n 4




+... y

n 1




+

n 3




+

17. Pruebe n,
r y k son enteros tales que 0 ≤ k ≤ r ≤ n entonces:

quen
sin−k n r = k r−k . r k



n n+1 18. Pruebe que rr + r+1 + . . . + = . r r r+1 19. Los coeficientes binomiales se pueden colocar formando el famoso Tri´ angulo de Pascal (tambi´en llamado de Tartaglia) como se muestra en el arreglo. 1 1 1

1 2

1

1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 a) ¿Cuales de las propiedades de los coeficientes binomiales enunciadas se observan en el Tri´angulo? b) Si desarrollamos un trinomio a la potencia n los coeficientes correspondientes se pueden ordenar en una pir´amide. ¿C´omo ser´ıa? 20. De los estudiantes de un grupo 2 no practican ning´ un deporte, 12 practican el f´ utbol y el basquet, 5 el f´ utbol y el volibol , 7 practican el f´ utbol u ´nicamente, 17 en total practican el b´asquet, 12 en total practican el volibol, no hay quien practique los tres deportes conjuntamente, y son 5 los que practican el b´asquet y el volibol. ¿Cu´antas personas componen el grupo? 21. 28 personas se encuentran en una monta˜ na del Per´ u. Entre ellos se hablan tres idiomas: quechua, espa˜ nol e ingl´es. El n´ umero de los que hablan exclusivamente un idioma siempre es impar, los grupos de personas que hablan dos de los tres idiomas es siempre par. Si los que hablan espa˜ nol son 18, cu´antos hablan ingl´es y quechua? 22. En t´erminos de la sucesi´on de Fibonacci determine cu´antas palabras sobre el alfabeto {0, 1} hay de longitud n que no tienen dos 1´s seguidos. Justifique su respuesta. 23. Elaborar una algoritmo que enumere todos los subconjuntos del conjunto {0, 1, . . . , n} 24. Dados los vectores booleanos de n componentes A[i], B[j], que representan los conjuntos A y B respectivamente desarrollar algoritmos para construir C[i] que representa: a) Ac ∩ B c b) A ∩ B c c) Ac ∪ B c

20

6.

Lenguajes Regulares

Recordamos que si Σ es un conjunto finito (alfabeto), cualquier subconjunto de Σ∗ es un lenguaje. Tambi´en recordemos que hemos definido una operaci´on muy natural entre palabras de Σ∗ que es la concatenaci´on y que consiste en “juntar” las palabras a operar. Dados dos lenguajes podemos hacer entre ellos operaciones como conjuntos y tambi´en hallar relaciones entre ellos. Ejemplo 6. {an cbn | n ∈ N} y {an cbm | n, m ∈ N} son lenguajes sobre Σ = {a, b, c}, se tiene que {an cbn | n ∈ N} es subconjunto propio de {an cbm | n, m ∈ N}. Definici´ on 6. Dados L1 y L2 lenguajes sobre un alfabeto Σ se define la concatenaci´on de L1 y L2 as´ı: L1 L2 = {w1 w2 | w1 ∈ L1 , w2 ∈ L2 } Ejemplo 7. {ab, aa, ba, bb}{ab} son todas las palabras sobre Σ = {a, b} de cuatro letras que terminan en ab. Podemos tambi´en ampliar el concepto de lenguaje generado por un alfabeto, tomando ahora como alfabeto cualquier conjunto de palabras. Definici´ on 7. Dados L lenguaje sobre el alfabeto Σ se define la estrella de Kleene L∗ recursivamente as´ı: i) BASE λ ∈ L∗ ii) PASO RECURSIVO Si v ∈ L y w ∈ L∗ entonces wv ∈ L∗ Notaci´ on. L+ = LL∗ Ejemplo 8. {ab, aa}∗ {ab, aa} = {ab, aa}+ son todas las palabras sobre Σ = {a, b} con un n´ umero par de letras que no contienen dos b’s seguidas y que empiezan por a. Finalmente definimos los lenguajes regulares que son una familia muy importante de lenguajes. Definici´ on 8. Dado el alfabeto Σ se define la familia de lenguajes regulares sobre Σ recursivamente as´ı: i) BASE ∅, {λ} y {x} para cada x ∈ Σ son lenguajes regulares. ii) PASO RECURSIVO Si L1 y L2 son lenguajes regulares entonces L1 ∪ L2 , L1 L2 y L∗1 son lenguajes regulares. Notaci´ on. L+ = LL∗ Ejemplo 9. Todo conjunto finito de palabras es un lenguaje regular. Para generarlos no es necesario utilizar la ∗ de Kleene. Por ejemplo, L = {abab, aaab, abaa, aaaa} es regular pues si N = {a}{b} ∪ {a}{a} entonces L = N N . Ejemplo 10. El conjunto de palabras sobre Σ = {a, b} que empiezan y terminan con a es un lenguaje regular ya que se puede expresar as´ı: {a}{a, b}∗ {a}. 21

No todos los lenguajes sobre un alfabeto son regulares. Demostrar que determinado lenguaje no es regular por ahora no est´a a nuestro alcance, sin embargo anotemos que los siguientes no lo son: 1. El conjunto de palabras sobre Σ = {a, b} que tiene igual n´ umero de a’s que b´s. 2. El conjunto de palabras sobre Σ = {a, b} de la forma an bn . 3. El conjunto de palabras pal´ındromes sobre un alfabeto Σ, es decir el conjunto {w ∈ Σ∗ | wR = w}.

6.1.

Ejercicios

1. Entre los siguientes conjuntos de palabras sobre Σ = {a, b} encuentre las relaciones de contenencia: a) ({a} ∪ {ab}∗ )∗ b) {a}∗ ∪ {ab}∗ c) {a, ab}∗ 2. Cu´ales de las siguientes palabras pertenecen al lenguaje {a}({ab, ba})∗ {b}: a. ababab b. ababbab c. aabbabab d. abbaabb d. aababaabb 3. La palabra aaabab a cu´ales de los siguientes lenguajes pertenece: a. {a}({ab, ba})∗ {b}: b. {a}∗ {ab, ba}{b}: c. {aa}{ab, ba}{b} d. {a}∗ {ba}{b} d. {a}∗ {ab}{b} 4. Def´ınase recursivamente el lenguaje L as´ı: i) Base: λ ∈ L ii) Paso recursivo: Si ω ∈ L ⇒ ωb ∈ L ∧ aaω ∈ L Entonces L es el lenguaje: a. {aa}∗ {b} ∗ b. {aa}∗ {b}+ c. {ab}∗ 22

d. {a2n bn | n ≥ 0} d. Ninguna de las anteriores 5. De las palabras del lenguaje {a, ba}∗ podemos decir (FALSO/VERDADERO): a. Todas tienen un n´ umero par de b’s. b. Que salvo λ, todas tienen al menos una b. c. Que salvo λ, todas terminan en a. d. Ninguna contiene a bb. e. Que salvo λ, todas contienen al menos una a. 6. De las cadenas del lenguaje a∗ b(a+ b)∗ podemos decir (FALSO/VERDADERO): a. Todas tienen un n´ umero impar de b’s. b. Que todas tienen al menos una b. c. Todas terminan en b. d. Ninguna contiene a bb. e. Que todas contienen al menos una a. 7. Demostrar que los siguientes conjuntos de palabras sobre Σ = {a, b} son regulares: a. Todas las que tienen un n´ umero impar de b’s. b. Las que tienen al menos una b. c. Las que terminan en b. d. Las que NO contienen contiene a bb. e. Las que contienen exactamente una a.

23