Matediscretas

Notas de Matem´ ticas Discretas a
H´ ctor Fernando G´ mez Garc´a e o ı
Ingenier´a en Telem´ tica. ı a Universidad del Caribe. Canc´ n Q. Roo. u

1 Introducci´ n o
Los n´ meros reales est´ n caracterizados por ser cont´nuos, ya que, dados dos u a ı n´ meros reales diferentes, siempre es posible encontrar un tercero justo en la miu tad de los dos primeros sin importar qu´ tan cercanos est´ n.Las matem´ ticas e e a cont´nuas (como el c´ lculo integral y el diferencial) se enfocan siempre sobre ı a dominios reales (subconjuntos de la recta real). En contraste, las matem´ ticas a discretas tratan con objetos discretos, o lo que es lo mismo, objetos que pueden asumir valores ”separados”. Un ejemplo de ello es la l´ gica proposicional, un o tema que abordaremos durante el primer parcialdel curso y en el que analizaremos la validez de expresiones compuestas por proposiciones l´ gicas, dichas exo ´ presiones se consideran objetos que pueden asumir unicamente dos valores separados: verdadero o falso.

2 Conjuntos.
Un conjunto es una colecci´ n de objetos. Por ejemplo el conjunto o A = { a, e, i, o, u } , 1

se encuentra formado por las vocales del idioma espa˜ ol. Mientras queel n conjunto B= x | x2 − 1 = 0 ,

se construye con los n´ meros que resuelven la ecuaci´ n x2 − 1 = 0. u o Es una pr´ ctica ampliamente aceptada el representar a los conjuntos mediante a letras may´ sculas, mientras que sus elementos se describen con letras min´ sculas. u u Para afirmar que un objeto pertenece a un conjunto, escribimos 1∈B, mientras que lo contrario se escribe b∈A. /Representaci´ n de un conjunto. Existen dos opciones para denotar un cono junto, la primera de ellas es realizando un listado exhaustivo de sus elementos, por ejemplo

C = {1, 2} D = {3, a, }

sin embargo, esta estrategia es inadecuada cuando el n´ mero de elementos del u conjunto es muy grande, en tal caso, es preferible denotar el conjunto de forma descriptiva, por ejemplo

E = {x | x > 0}, D ={enteros impares} .

2

Cardinalidad y Conjunto Vac´o. La cardinalidad de un conjunto es igual al ı n´ mero de elementos que contiene. Por ejemplo, el conjunto A = {1, 5, 7} tiene u una cardinalidad de tres, lo cual se simboliza como |A| = 3. Algunos conjuntos pueden tener una cardinalidad infinita, por ejemplo, el conjunto de los enteros pares, mientras que otros tienen una cardinalidad de cero.Los conjuntos con cardinalidad igual a cero reciben el nombre de conjunto vac´o, un ı ejemplo est´ representado por el conjunto formado por todos los n´ meros reales a u 2 que resuelven la ecuaci´ n x + 1 = 0, esto es o C = {x | x ∈ R, x2 + 1 = 0} dado que no existe un n´ mero real que cumpla con la ecuaci´ n, este conjunto u o no contiene elementos. El s´mbolo ∅ se utiliza para representar unconjunto vac´o, ı ı por lo que podemos escribir que C = ∅ Subconjuntos. Dados dos conjuntos cualesquiera, A y B, si todos los elementos del conjunto A son tambi´ n elementos del conjunto B, se afirma que A es un e subconjunto de B, y se simboliza A⊂B. En caso de que se cumplan al mismo tiempo las condiciones A ⊂ B y B ⊂ A, se afirma que A = B. Finalmente, cuando A ⊂ B y A = B, se afirma que A es unsubconjunto propio de B y se escribe A ⊆ B. Un dato curioso lo constituye el hecho de que el conjunto vac´o es un suconı junto de cualquier conjunto, dado que no es posible encontrar elementos de ∅ que no est´ n en cualquier conjunto. e Conjunto Potencia. El conjunto potencia de un conjunto A contiene como elementos a todos los subconjuntos que es posible formar a partir de A, incluyendo 3

elconjunto vac´o. Por ejemplo, si A = {1, 2, 5} el conjunto potencia de A es ı

P (A) = {∅, {1}, {2}, {5}, {1, 2}, {1, 5}, {2, 5}, {1, 2, 5}} . Se puede demostrar que |P (A)| = 2|A| para cualquier conjunto A. En nuestro ejemplo puede verificarse que |P (A)| = 2|A| = 23 = 8. Conjuntos Num´ ricos. Existen diversos conjuntos num´ ricos que por su ime e portancia deben describirse de manera especial. El...