Estructuras de objetos discretos para la computación (página 2)

Diagrama de Venn que muestra y

Los elementos de un conjunto que no se encuentran en otro conjunto , forman otro conjunto llamado diferencia de y , representado por . Es decir:

.

O dicho de otra manera:

Algunas personas prefieren denotar la diferencia de y como .

Una propiedad interesante de la diferencia es que

Eso es porque

Ejemplos: Sin importar cual conjunto A elija usted, siempre se cumple

Complemento

El complemento de un conjunto A, es el conjunto de los elementos que pertenecen a algún conjunto U pero no pertenecen a A, que lo representaremos por . Es decir

El conjunto complemento siempre lo es respecto al conjunto universal que estamos tratando, esto es, si hablamos de números enteros, y definimos el conjunto de los números pares, el conjunto complemento de los números pares, es el formado por los números no pares. Si estamos hablando de personas, y definimos el conjunto de las personas rubias, el conjunto complementario es el de las personas no rubias.

En vista de que y , entonces

,

De manera que

Pero también

De modo que

II. Métodos para la representación de objetos.

    2.1 Conjunto de pares ordenados y particiones de objetos

            En la teoría de conjuntos pura, donde solamente existen conjuntos, pares ordenados (a, b) se pueden definir como el conjunto:

Esta definición tiene el nombre de par de Kuratowski, y es bien básica, porque requiere de apenas pocos axiomas para poder ser formulada (el axioma de extensión, el axioma de separación y el axioma del par).

La afirmación de que x sea el primer elemento de un par ordenado p puede ser entonces formulada como

Y que x sea el segundo elemento de p como

Nótese que esta definición también es válida para el par ordenado p = (x, x) = {{x}, {x, x}} = {{x}, {x}} = {{x}}.

En la formulación usual ZF de la teoría de conjuntos incluyendo el axioma de regularidad, un par ordenado (a,b) puede también ser definido como el conjunto {a,{a,b}}. De todas formas, el axioma de regularidad es necesario, dado que sin él, sería posible considerar conjuntos x y z tales que x = {z},z = {x}, y . Entonces se tendría que mientras que se quiere que

2.2 Trayectoria en las relaciones y en los dígrafos

          2.2.1 Relaciones y dígrafos

Informalmente, un grafo es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias entre elementos de un conjunto.

Típicamente, un grafo se representa gráficamente como un conjunto de puntos (vértices o nodos) unidos por líneas (aristas).

Desde un punto de vista práctico, los grafos permiten estudiar las interrelaciones entre unidades que interactúan unas con otras.

          2.2.2 Propiedades de las relaciones y dígrafos

·         Adyacencia: dos aristas son adyacentes si tienen un vértice en común, y dos vértices son adyacentes si una arista los une.

·         Incidencia: una arista es incidente a un vértice si ésta lo une a otro.

·         Ponderación: corresponde a una función que a cada arista le asocia un valor (costo, peso, longitud, etc.), para aumentar la expresividad del modelo. Esto se usa mucho para problemas de optimización, como el del vendedor viajero o del camino más corto.

·         Etiquetado: distinción que se hace a los vértices y/o aristas mediante una marca que los hace unívocamente distinguibles del resto.

          2.2.3 Relaciones de equivalencia

      2.2.4 Manipulación de relaciones

*****************************************

    2.3 Representación en las computadoras de las relaciones y los dígrafos

Una red de computadoras puede representarse y estudiarse mediante un grafo, en el cual los vértices representan terminales y las aristas representan conexiones (las cuales, a su vez, pueden ser cables o conexiones inalámbricas).

Prácticamente cualquier problema puede representarse mediante un grafo, y su estudio trasciende a las diversas áreas de las ciencias duras y las ciencias sociales.

III. Funciones empleadas en la aplicación de las ciencias de la computación.

    3.1 Definición de función

Una función o aplicación de X en Y es una correspondencia matemática denotada

 Que cumple con las siguientes dos condiciones:

1.       Todos los elementos de X están relacionado con elementos de Y, es decir,

2.       Cada elemento de X esta relacionado con un único elemento de Y, es decir, si

Una función es un caso particular de relación y de correspondencia matemática. Cada relación o correspondencia de un elemento con un (y sólo un) se denota , en lugar de

 3.2 Tipos de funciones especiales

          3.2.1 Función inyectiva

Aquellas en que a cada imagen le corresponde un único origen.

 Formalmente,

 O lo que es lo mismo,

          3.2.2 Función supreyectiva

Aquellas en que la aplicación es sobre todo el codominio, es decir, cuando el conjunto imagen . Formalmente,

          3.2.3 Función invertida

Dada una función , se denomina función inversa de , a la función que cumple la siguiente condición:

Si existe una función que cumpla esas dos condiciones, ser inversa por la izquierda y ser inversa por la derecha, se demuestra que esa función es única. Eso justifica la notación , que sería ambigua si pudiera haber dos inversas de la misma función.

Sólo algunas funciones tienen inversa. De hecho, la condición necesaria y suficiente para la existencia de es que sea biyectiva. Por tanto, las afirmaciones

·         Existe función inversa de y

·         es biyectiva

Son lógicamente equivalentes.

    3.3 Funciones idénticas

Dado un conjunto , la función que asigna a cada de el mismo de se denomina función identidad o función unitaria.

Dada cualquier función , es claro que es igual a y que es también igual a , puesto que para todo y también

    3.4 Composición de funciones

Dadas dos funciones y tales que la imagen de está contenida en el dominio de , se define la función composición como el conjunto de pares , para todos los elementos de .

Dado conocemos , puesto que conocemos la función , y dado cualquier elemento de conocemos también , puesto que conocemos la función . Por tanto, está definido para todo x. Luego cumple la condición de existencia que se exige a las funciones. También cumple la condición de unicidad, dado que para cada el valor de es único, y para cada también lo es el de , por ser y funciones. La composición de funciones es asociativa:

Sin embargo, en general, la composición de funciones no es conmutativa. Dadas y , puede no tener ni siquiera sentido, porque “devuelve” elementos de , en tanto que está definida en el dominio . Pero incluso en los casos en que dominios y codominios son compatibles (o son el mismo conjunto), nada garantiza que la composición de funciones sea conmutativa. Por ejemplo, con funciones numéricas y , , en tanto que

    3.5 Función de permutación y análisis combinatorio