Monografias.com > Uncategorized
Descargar Imprimir Comentar Ver trabajos relacionados

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




Enviado por LEONEL PERALTA



Partes: 1, 2, 3

Diagrama de Venn que muestra A - B~~~y B - A~

Los
elementos de un conjunto ~Aque
no se encuentran en otro conjunto ~B,
forman otro conjunto llamado diferencia de ~Ay
~B
,
representado por ~Asetminus B. Es decir:

Asetminus B= {xin A:xnotin B}.

O
dicho de otra manera:

xin(Asetminus B)iff (xin A) wedge (xnotin B)

Algunas
personas prefieren denotar la diferencia de A~y
B~como
A-B~.

Una
propiedad interesante de la diferencia es que

Acap B=Asetminus(Asetminus B)

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

Asetminusemptyset = A

emptysetsetminus A = emptyset

{0,1,2,3}setminus{3,2}={0,1}

 

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  A^complement . Es decir

A^complement=Usetminus A

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 Asubseteq Uy Bsubseteq U, entonces

xin left (Asetminus Bright) iff xin left(Acap B^complementright),

Asetminus B=Acap B^complementDe
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

~Asetminus B = left (B^complementsetminus A^complementright)

 

 

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:

~(a,b)={{a},{a,b}}

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 xneq z.
Entonces se tendría que mientras que se quiere que(x,x)neq(z,z)

(x,x)={x,{x,x}}={x,{x}}={x,z}={z,x}={z,{z}}={z,{z,z}}=(z,z),

 

 

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

f colon X to Y , Que cumple con las siguientes dos condiciones:

 

1.      
Todos
los elementos de X están relacionado con elementos de Y, es
decir, forall xin X, exists yin Y backslash  (x,y)in f.

2.      
Cada
elemento de X esta relacionado con un único elemento de Y, es
decir, si (x,y_1)in f and (x,y_2)in f Rightarrow y_1 = y_2.

Una función es un caso particular de relación
y de correspondencia matemática. Cada relación o correspondencia de un elemento
xin Xcon
un (y sólo un) yin Yse
denota f(x)=y,, en lugar de (x,y)in f.

 

 3.2 Tipos de
funciones especiales

         
3.2.1
Función inyectiva

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

 Formalmente,

forall x_1,x_2 in X : f(x_1) = f(x_2) rarr x_1 = x_2, O lo que es lo mismo,

forall x_1,x_2 in X : x_1 neq x_2 rarr f(x_1)neq f(x_2)

 

         
3.2.2
Función supreyectiva

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

forall yin Y : exists xin X, f(x) = y

 

         
3.2.3
Función invertida

Dada una función f colon A to B ,;, se denomina
función inversa de f ;,
 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 f ;sea
biyectiva. Por tanto, las afirmaciones

·        
Existe
función inversa de f ;
y

·        
f ;es biyectiva

Son lógicamente equivalentes.

 

    3.3 Funciones
idénticas

Dado un conjunto , A ,,
la función ; e_A colon A to A ,que asigna a
cada x ,de
A ,el
mismo x ,de
A ,se
denomina función identidad o función unitaria.

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

Dada cualquier función g colon A to B ,, es claro que e_Bcirc f colon A to B ,es igual a
f,y
que fcirc e_A colon A to B ,es también
igual a f,,
puesto que para todo x  ;; f(e_A(x))=f(x) y también ;; e_B(f(x))=f(x)

; e_B circ f = f circ e_A = f ;

 

    3.4 Composición de
funciones

Dadas dos funciones f colon A to B ,;y g colon B to C ,;tales que la
imagen de f ,está
contenida en el dominio de g,,
se define la función composición ;;gcirc f colon A to C ,como el
conjunto de pares (,x, g(f(x),)), para todos los elementos x ,de
A ,.

A to ,,B;; to ;;,C

x mapsto f(x) mapsto g(f(x))

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

hcirc (g circ f) = (hcirc g) circ f

Sin embargo, en general, la composición de
funciones no es conmutativa
. Dadas f colon A to B ,y g colon B to C ,, fcirc g,puede no tener ni siquiera sentido, porque g ,“devuelve”
elementos de C ,,
en tanto que f ,está
definida en el dominio A ,.
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 f(x)=x+1 ,;y ,g(x)=x^2 ,;, ,f(g(x))=x^2+1 ,;, en tanto que ;g(f(x))=(x+1)^2 ,

 

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

 

Partes: 1, 2, 3
 Página anterior Volver al principio del trabajoPágina siguiente 

Nota al lector: es posible que esta página no contenga todos los componentes del trabajo original (pies de página, avanzadas formulas matemáticas, esquemas o tablas complejas, etc.). Recuerde que para ver el trabajo en su versión original completa, puede descargarlo desde el menú superior.

Todos los documentos disponibles en este sitio expresan los puntos de vista de sus respectivos autores y no de Monografias.com. El objetivo de Monografias.com es poner el conocimiento a disposición de toda su comunidad. Queda bajo la responsabilidad de cada lector el eventual uso que se le de a esta información. Asimismo, es obligatoria la cita del autor del contenido y de Monografias.com como fuentes de información.

Categorias
Newsletter