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

Partes: 1, 2, 3

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

$begin{array}{rcl} xin Acap B & iff & (xin A) wedge (xin B)\ &iff& (xin A) wedge (xnotin Asetminus B)\ &iff& xin Asetminus (Asetminus B) end{array}$

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

$begin{array}{rcl} xin left (Acap B^complementright ) & iff & xin A wedge xin B^complement )\ &iff& xin B^complement wedge xin A\ &iff& xin B^complement wedge xnotin A^complement\ &iff& x inleft (B^complementsetminus A^complementright) end{array}$

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

$forall_{yin p}qquad xin y$

Y que x
sea el segundo elemento de p como

$(exist_{yin p}quad xin y)wedge(forall_{y_1in p}forall_{y_2in p}quad (x in y_1 wedge xin y_2) Rightarrow y_1=y_2)$

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 ,
$f^{-1} colon B to A ,$ a la función
que cumple la siguiente condición:

$; f^{-1} circ f = e_A ;$

$; f circ f^{-1} = e_B ;$

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 $f^{-1} ;$ , 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 $f^{-1} ;$ 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.

$e_A = left{(x, x)mid x in A right}$

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