2011

Tabla de contenidoDemostraciones por inducción.......................................................................................................5

Ejemplo 1..................................................................................................................................5

Ejemplo 2..................................................................................................................................6

Relaciones...............................................................................................................................14

Matrices de relaciones............................................................................................................16

Notación y nomenclatura..............................................................................................................19

Ejemplos..................................................................................................................................20

Igualdad de funciones...................................................................................................................21

Representación de funciones........................................................................................................21

Clasificación de las funciones......................................................................................................22

Homomorfismo................................................................................................................................22

Definición.....................................................................................................................................23

Tipos particulares de homomorfismos.........................................................................................23

Presentación.................................................................................................................................27

Ejemplos..................................................................................................................................27

Ejemplo....................................................................................................................................28

Relaciones de recurrencia lineales homogéneas..........................................................................28

Definición.................................................................................................................................28

Teorema 1................................................................................................................................28

Teorema 2................................................................................................................................29

Relaciones de recurrencia lineales no homogéneas.....................................................................29

Proposición...............................................................................................................................29

Pasos para resolver una relación de recurrencia lineal no homogénea...................................29

Observación.............................................................................................................................29

DEMOSTRACIONES

Un sistema matemático consta de axiomas, definiciones y términos no definidos. Se suponen verdaderos los axiomas. Las definiciones se utilizan para crear conceptos nuevos en términos de los existentes. Algunos términos no se definen en forma explícita, sino que se definen en forma implícita mediante axiomas. Dentro de un sistema matemático es posible deducir teoremas. Un teorema es una proposición cuya verdad se ha demostrado. Algunos tipos especiales de teoremas se conocen como lemas y corolarios. Un lema es un teorema que por lo general no es interesante en si mismo sino que es útil para demostrar otro teoremas. Un corolario es un teorema que se sigue rápidamente de otro teorema.

Un argumento que establece la verdad de un teorema es una demostración. La lógica es una herramienta para el análisis de las demostraciones.

Ejemplo:

La geometría euclidiana proporciona un ejemplo de sistema matemático. Entre los axiomas están:

Dados dos puntos distintos, existe exactamente una recta que los contiene. Dada una recta y punto que no está sobre la recta, existe exactamente una recta paralela a la

primera recta y que pasa por el punto.

Los términos punto y recta son términos no definidos que quedan definidos de manera implícita mediante los axiomas que describen sus propiedades. Entre las definiciones están:

Dos triángulos son congruentes si sus vértices pueden ponerse en correspondencia de modo que los lados correspondientes y los ángulos correspondientes sean iguales.

Dos ángulos son suplementarios si la suma de sus medidas es 180°.

Un argumento es una serie de proposiciones que se escriben

Las proposiciones son las hipótesis y la proposición q es la conclusión. El

argumento es válido si siempre que sean todas verdaderas, entonces q deberá también deberá ser verdadera; en caso contrario, el argumento no es válido.

En un argumento válido, a veces decimos que la conclusión se sigue de la hipótesis. Observe que no estamos diciendo que la conclusión sea verdadera; solo estamos diciendo que si se garantizan las hipótesis, entonces se tiene garantizada la conclusión. Un argumento es válido debido a su forma, no a su contenido.

Determine si el argumento

Es válido.

[Primera solución.] Construimos una tabla de verdad para todas las proposiciones que aparecen en el argumento:

Observamos que siempre que las hipótesis y p son verdaderas, la conclusión q también lo es; por tanto, el argumento es válido.

[Segunda solución.]Podemos dejar de lado la tabla de verdad, verificando directamente que siempre que las hipótesis sean verdaderas, la conclusión también es verdadera.

Supongamos q y p son verdaderas. Entonces q debe ser verdadera, ya que en caso

contrario sería falsa. Por tanto, el argumento es válido.

DEMOSTRACIONES POR RESOLUCIÓN.

En esta sección escribiremos como ab.

La resolución es una técnica de demostración propuesta por J.A. Robinson en 1965 que depende de una única regla:

Podemos verificar la regla mediante la tabla de verdad. Como la resolución depende solo de esta sencilla regla, es la base de muchos programas de computadora que realizan razonamientos y demostraciones de teoremas.

En una demostración por resolución, las hipótesis y la conclusión se escriben como clausulas. Una clausula consta de términos separados por o, donde cada termino es una variable o la negación de la variable.

INDUCCIÓN MATEMÁTICA

La inducción es un razonamiento que permite demostrar una infinidad de proposiciones, o una proposición que depende de un parámetro n que toma una infinidad de valores enteros. En términos simples, la inducción matemática consiste en el siguiente razonamiento:

Premisa mayor: El número entero a tiene la propiedad P.Premisa menor: El hecho de que cualquier número entero n tenga la propiedad P implica que n + 1 también la tiene.Conclusión: Todos los números enteros a partir de a tienen la propiedad P.Demostraciones por inducción

El razonamiento para demostrar una proposición cualquiera mediante el esquema del razonamiento es como sigue. Llamemos Pn a la proposición, donde n es el rango.

Se demuestra que P0, el primer valor que cumple la proposición (iniciación de la inducción), es cierta.

Se demuestra que si se asume Pn como cierta y como hipótesis inductiva, entonces Pn + 1 lo es también, y esto sin condición sobre el entero natural n (relación de inducción).

Luego, demostrado esto, concluimos por inducción, que Pn es cierto para todo natural n.

La inducción puede empezar por otro término que P0, digamos por Pno. Entonces Pn no será válido a partir del rango n0, es decir, para todo natural .

Ejemplo 1

Para todo , 6n es un número que acaba en 6.

Sea Pn la proposición: «6n acaba en 6».

Es claro que P1 es cierto, porque 61 = 6.

Supongamos que Pn es cierto para un valor de n natural, y probemos Pn + 1.Un entero acaba por 6 si se puede escribir así: 10a + 6, con a entero positivo o igual a cero. La hipótesis es, pues, 6n = 10a + 6.

Entonces 6n + 1 = 6(10a + 6) = 60a + 36 = 60a + 30 + 6 = 10(6a + 3) + 6 = 10c + 6, con c = 6a + 3, entero.Esta última escritura prueba que 6n + 1 acaba por 6, o sea que Pn + 1 es cierto.Luego Pn es cierto para todo .

La inducción es válida por la construcción misma del conjunto de los naturales mediante los axiomas de Peano. En este caso:

1 es un natural; si n lo es, entonces n + 1 (sucesor de n) lo es también.

Existen otras inducciones, para otros conjuntos elaborados de forma distinta, como por ejemplo la inducción transfinita, y la inducción sobre las fórmulas de la lógica proposicional.

Además de la demostración por inducción, existe la definición o construcción por inducción. Por ejemplo, una sucesión aritmética puede ser definida como función de n: un = a + rn, o por inducción:

u0 = a un + 1 = un + r.

Ejemplo 2

Se tratara de demostrar por inducción la siguiente proposición:

 1. Se comprueba para n=1

Se tiene por tanto que la proposición es verdadera para n=12. Hipótesis inductiva (n=k)

3. Tesis inductiva (n=k+1)

4. Demostración de la tesis en base a la hipótesis

Se aplica la hipótesis de inducción:

 (Sacando factor común)

Por lo tanto, por verificarse la proposición para n=1 y para n=k+1 siendo k cualquier número natural, la proposición se verifica 

CONJUNTOS Y RELACIONES

CONJUNTOS

Usualmente los conjuntos se representan con una letra mayúscula:

Llamaremos elemento, a cada uno de los objetos que forman parte de un conjunto, estos elementos tienen carácter individual, tienen cualidades que nos permiten diferenciarlos, y cada uno de ellos es único, no habiendo elementos duplicados o repetidos. Los representaremos con una letra minúscula:

De esta manera, si   es un conjunto, y   todos sus elementos, es común escribir:

Para definir a tal conjunto . Esta notación empleada para definir al conjunto   se llama notación por extensión.

Para representar que un elemento   pertenece a un conjunto , escribimos   (léase " en  ", "  pertenece a  " o bien "  es un elemento de  "). La negación de   se

escribe   (léase "  no pertenece a  ").

El conjunto universal, que representaremos como   (u mayúscula), es el conjunto de todas las cosas sobre las que estemos tratando. Así, si hablamos de números enteros entonces   es el conjunto de los números enteros; si hablamos de ciudades,   es el conjunto de todas las ciudades. Todos los elementos posibles están en este conjunto:

Este conjunto universal puede mencionarse explícitamente, o puede darse por supuesto según el contexto que estemos tratando.

Existe además, un único conjunto que no tiene elementos, al que se le llama conjunto

vacío y que se denota por , esto es:  . La característica importante de este conjunto es que todos los elementos posibles no están contenidos en él:

Por otro lado, si todos los elementos   de un conjunto   satisfacen alguna propiedad, misma que pueda ser expresada como una proposición p(x), con la indeterminada x, usamos la notación por comprensión, y se puede definir:

Lo anterior se lee "A es el conjunto de elementos x, que cumplen la propiedad p(x)". El símbolo ":" se lee "que cumplen la propiedad" o "tal que"; este símbolo puede ser

remplazado por una barra  .

Por ejemplo, el conjunto:

Puede definirse por:

Donde el símbolo   representa al conjunto de los números naturales.

SUCESIONES Y CADENAS

an = 3an-1 + 2an-2 +5

El orden de una sucesión tiene que ver con la cantidad de términos anteriores que se utilizan. En el ejemplo tenemos una sucesión de 2º orden. El gradose relaciona con el exponente al que están elevados an - i. Por último, la sucesión es homogénea si no hay ningún término independiente. En el caso anterior es no homogénea.

Ejemplificación:

Expresión Grado Orden Homogeneidad

       

an = 3an-1 - 2 1º 1º No homogénea

an = a²n-1 2º 1º Homogénea

an = 1-a³n-1 3º 1º No homogénea

an = 4an-1 – 2a²n-2 2º 2º Homogénea

an = a³n-2 + 1 3º 2º No homogénea

an = an-1 + an-2+ an-3 1º 3º Homogénea

an = 4an-5 + 2an-3 + an-1 1º 5º Homogénea

       

Resolución de ecuaciones homogéneas de primer grado, segundo orden:

a. Se pasan al primer miembro los términos an, an-1, an-2, los cuales también podrían figurar como an+2, an+1, an

n n

b. Se reemplaza an por r², an-1 por r y an-2 por 1, quedando una ecuación de segundo grado con raíces reales y distintas de r1 y r2.

c. Se plantea a = u · r1 + v · r2d. Debemos tener como dato los valores de los dos primeros términos de la sucesión:

A0 = k y A1 = k’. Utilizando estos datos ordenamos el sistema de 2x2: u + v = k y u·r1 + u·r2 = k’. La resolución de este sistema no da como resultado losvalores u0 y v0, que son números reales conocidos.

e) la solución general es:

 Para ver el gráfico seleccione la opción "Descargar" del menú superior

Ejemplificación:

an= 2/3an-1 +1/3an-2

a0 = 2 Esto es dato

a1= 5

 Primero efectuamos el cambio de variable de la manera indicada

1

r² - 2/3 r - 1/3 = 0

-1/3

Aplicamos la fórmula para resolver ecuaciones cuadráticas.

Luego reemplazamos los valores de las raíces en la fórmula general:

n n

a = u · 1 + v · (-1/3)

Ahora debemos usar los datos que nos dieron par resolver el problema: El polinomio especializado en 0 da como resultado 2, y especializado en 1 da 5 (Ver llave al inicio del problema donde se aclara cuales son los datos). Por lo tanto podemos elaborar el siguiente sistema de ecuaciones:

u + v =2

u - 1/3 = 5

Resolviéndolo, obtenemos que:

v = -9/4

u = 17/4

SISTEMA NUMÉRICO

Este tema lo encontramos en la página 84 del texto base, es conveniente que usted lo revise previamente para sustentar de mejor manera lo que la guía trata de complementar y explicar en forma práctica. Los sistemas de numeración son conjuntos de dígitos o símbolos usados para representar cantidades, así se tiene los sistemas de numeración Decimal, Binario, Octal, Hexadecimal, Romano, etc. Los cuatro primeros se caracterizan por tener una base (numero de dígitos o símbolos diferentes que se utilizan para representar cantidades y estas bases son: 10, 2, 8 y 16). El sistema de numeración binario es el mas importante en los sistemas digitales, mientras el sistema decimal la importancia radica en que se utiliza universalmente para representar cantidades fuera de un sistema digital. Esto significa que habrá situaciones en las cuales los valores decimales tengan que convertirse en valores binarios antes de que se introduzcan en el sistema digital.

 

Estos son los sistemas de numeración mas utilizados ya que permiten explicar las operaciones y funciones que se cumplen al operar, codificar o programar tareas con el computador. Una computadora utiliza números binarios para calcular respuestas a un

problema, luego los convierte a un valor decimal antes de mostrarlos en la pantalla. Además del Sistema Binario y decimal, otros dos sistemas de numeración encuentran amplias aplicaciones en los sistemas digitales. Los sistemas Octal (base 8) y Hexadecimal (base16) se usan con la misma finalidad, la de ofrecer un eficaz medio de representación de números binarios grandes.

Ejemplos en la manipulación de estos sistemas de numeración:

1. Sistema binario

Conversión de Binario a Octal y viceversa

a) Para la conversión de enteros binarios a octales, a los bits del número binario se los agrupa en conjuntos de tres comenzando por la derecha. Luego, cada grupo se convierte a su equivalente octal, utilizando la tabla siguiente:

Algunas veces el numero binario no tiene grupos de 3 bits completos. En estos casos, agregamos uno o dos ceros a la izquierda del número binario a fin de completar el último grupo. Esto se ilustra a continuación para el número binario 11010110_2.11 010 110 completamos: 011 010 110 remplazamos como indica la tabla:3 2 6luego el número buscado es: 326_8

b) Convertir el número octal 1235678 a binario, cada digito octal lo remplazamos por su correspondiente valor de la tabla anterior:

1 2 3 5 6 7001 010 011 101 110 111 luego el número buscado es:10100111011101112

Conversión de Binario a Hexadecimal y viceversa

a) Para la conversión de enteros binarios a hexadecimal, a los bits del número binario se los agrupa en conjuntos de cuatro comenzando por la derecha. Luego, cada grupo se convierte a su equivalente hexadecimal, utilizando la tabla siguiente:

Algunas veces el numero binario no tiene grupos de 4 bits completos. En estos casos, agregamos uno, dos o tres ceros a la izquierda del número binario a fin de completar el último grupo. Esto se ilustra a continuación para el número binario 1001001111_2.10 0100 1111 completamos: 0010 0100 1111remplazamos como indica la tabla: 2 4 Fluego el número buscado es: 24F_16

b) Convertir el número hexadecimal 127A8316 a binario, cada digito hexadecimal lo remplazamos por su correspondiente valor de la tabla anterior:

1 2 7 A 8 3

0001 0010 0111 1010 1000 0011 luego el número buscado es:

100100111101010000011_2

Conversión de un número de cualquier base a base 10

El método consiste en multiplicar los valores equivalentes de los dígitos por su base elevada a su valor posicional y luego sumar estos productos.

Ejemplos:

a) Convertir el número en base 2357_8 a decimal

posición: 3 2 1 0dígitos 2 3 5 7= (2 × 8^3) + (3 × 8^2) + (5 × 8^1) + (7 × 80)= 1024 + 192 + 40 + 7 = 1263_10

b) Convertir el número hexadecimal 3A1_16 a decimal

posición: 2 1 0dígitos 3 A 1= (3 × 16^2)+(10 × 16^1)+(1 × 16^0)= 768 + 160 + 1 = 929_10

Conversión de un número en base 10 a cualquier otra base

El método consiste en dividir el número sucesivamente para la nueva base y se escribirán los restos de las divisiones en orden inverso al obtenido.

Ejemplos:

a) Convertir el número decimal 273_10 a base octal u 8 

Ejercicios

Resuelva los ejercicios 6, 11, 23 de la página 90 del texto base, los mismos que le permitirán afianzar los conceptos y métodos de conversión.

EJEMPLOS DE OPERACIONES BINARIAS

Adicion

Para esta operación y mejor compresión tómese en cuenta el siguiente cuadro 

a) 

b) 

Obsérvese que en la operación de 1 + 1 = 10 en base binario (102), que es el equivalente del 2 en sistema decimal.

Sustracción

Para la sustracción tómese en cuenta el siguiente cuadro, para mejor comprensión en la resolución de los ejemplos que se muestran. 

a) 

Es necesario considerar que si el minuendo es negativo la operación se convierte en una adición con el resultado negativo.

Multiplicación

Se presenta la tabla de multiplicación binaria: 

a) 

Para multiplicar números que tiene parte entera y parte fraccionaria se opera como en el sistema decimal. Para colocar el número binario se cuenta la cantidad de cifras fraccionarias tanto en el multiplicando como en el multiplicador; y en esta cantidad se separa en el producto o resultado.

Relaciones

Este tema se encuentra en el capítulo 3 en los numérales 3.1 y 3.2 paginas 116 y 125 del texto básico, por lo tanto le sugerimos revisar con detenimiento las definiciones, teoremas y ejemplos desarrollados en base a la teoría expuesta, ya que lo que a continuación se desarrolle en la guía coadyuvara a ampliar los términos expuestos en el libro base.

Se define una relación como un conjunto de pares ordenados.

Una relación (binaria) R de un conjunto X a un conjunto Y es un subconjunto del producto cartesiano X × Y. si (x, y) ∈ R escribimos xRy y decimos que x esta relacionado con y.

Una relación que es reflexiva, simétrica y transitiva en un conjunto X se llama relación de equivalencia sobre X.

Ejemplos

a) Sean los conjuntos X = {a, b, c, d} y Y = {1, 2, 3, 4}, definir una relación R de X en Y y determinar el dominio de R y lel rango de R.

R = {(a, 1), (b, 2), (c, 3), (d, 4)}El dominio se define por el conjunto {x ∈ X/(x, y) ∈ R para algún y ∈ Y}

dominio de R es el conjunto {a, b, c, d}

b) La relación R sobre X = {1, 2, 3, 4} esta definida por “(x, y) ∈ R si x ≤ y“ es:

R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)}el dominio de R es el conjunto {1, 2, 3, 4}el rango de R es el conjunto {1, 2, 3, 4}se concluye que: el dominio y el rango son iguales porque la relación está definida sobre el mismo conjunto X.La digráfica de la relación R es la siguiente:

Ejemplos de las propiedades de las relaciones

a) Reflexiva

La relación R del ejemplo anterior dada por:R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)}se dice que es reflexiva por que cada elemento x ∈ X, (x, x) ∈ R; los pares ordenados (1, 1), (2, 2), (3, 3) y (4, 4) están en R. Si observamos la digráfica de la relación reflexiva, encontramos que tiene un lazo sobre cada vértice.

b) Simétrica

Tomando la relación R del ejemplo anterior dada por:R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)}“no es simétrica”, por cuanto no cumple la definición que dice: “si para cada x, y ∈ X, si (x, y) ∈ R, entonces (y, x) ∈ R”.

c) Transitiva

Tomando la relación R del ejemplo anterior dada por:R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)}“es una relación transitiva R sobre el cojunto X”, por cuanto cumple la definición que dice: “x, y, z ∈ X, si (x, y) y (y, z) ∈ R, entonces (x, z) ∈ R”.Específicamente tenemos (1, 2), (2, 3) se tiene (1, 3); (1, 3), (3, 4) se tiene (1, 4); (2, 3), (3, 4) se tiene (2, 4) todos pertenecen a R.

d) Antisimétrica

Tomando la relación R del ejemplo anterior dada por:

R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)}

“la relación R sobre el cojunto X es antisimétrica”, por cuanto cumple la definición que dice para toda: “x, y X, si (x, y) ∈ R y x ≠ y, entonces (x, y) ∉ R”. Específicamente tenemos (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4) pertenecen a R, pero (2, 1), (3, 1), (4, 1), (3, 2), (4, 2), (4, 3) no pertenecen a R.

e) Inversa

Tomando la relación R del ejemplo anterior dada por:R = {(1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,3),(3,4),(4,4)}

La relación inversa de R que se denota por R-1, esta dada por:R - 1 = {(1, 1), (2, 1), (3, 1), (4, 1), (2, 2), (3, 2), (4, 2), (3, 3), (4, 3), (4, 4)}Ejercicio 1

A partir del siguiente dígrafo, resuelva las siguientes instrucciones: 

1. Escriba R como un conjunto de pares ordenados

R ={(3, 5), (4, 4), (5, 5), (3, 5), (3, 4), (4, 5)}

2. Escriba una relación reflexiva sobre G1

R = {(3,3), (4,4), (5,5)}

3. Escriba una relación simétrica sobre G1

R = {(3,3), (4,4), (5,5)}

4. Escriba una relación antisimétrica sobre G1

R = {(3, 5), (3, 4), (4, 5)}

5. Escriba una relación transitiva sobre G1

R ={(3, 4), (4, 5), (3, 5)}

6. Escriba R-1 como un conjunto de pares ordenados

R-1 = {(3, 3), (4, 3), (4, 4), (5, 4), (5, 5), (5, 3)}

Ejercicio 2

Considere las siguientes relaciones en W = {1, 2, 3, 4} y determinar si son reflexivas, simétricas, antisimétricas o transitivas.

R1 = {(1, 1), (1, 2)}

R2 = {(1, 1), (2, 3), (4, 1)}

R3 = {(1, 3), (2, 4)}

R4 = {(1, 1), (2, 2), (3, 3)}

R5 = {W x W}

Respuestas: Reflexivas: R5

Simétricas: R4 y R5

Antisimétricas: R1, R2, R3, R4Transitiva: R1, R2, R3, R4, R5Matrices de relaciones

Este tema lo encontramos en la página 132, sección 3.3. Se describirá brevemente como formar una matriz de relación y se realizara ejemplos. Una matriz es una manera conveniente de representar una relación R de X a Y. Se etiquetan los renglones con elementos de X (en algún orden arbitrario), y se etiquetan las columnas con elementos de Y (orden arbitrario). Luego el elemento en el renglón x y la columna y se hace igual a 1 si xRy, y 0 de otra manera. Esta matriz se llama matriz de la relación R.

Ejemplos:

Formar la matriz de relación de los siguientes conjuntos:

a)

R = {(1, b), (1, d), (2, c), (3, c), (3, b), (4, a)}Donde X = {1, 2, 3,4} y Y = {a, b, c, d}Considerando los ordenes: 1, 2, 3,4 y a, b, c, d tenemos la matriz:

b)

X = {2, 3, 4} Y = {5, 6, 7, 8}Considerando las ordenes: 2, 3, 4 y 5, 6, 7,8; definida por xRy si x divide a y

Para los siguientes ejercicios vamos a determinar:

a) La matriz A_1 de la relación R_1 (con respecto de los órdenes dados)

b) La matriz A_2 de la relación R_2 (con respecto de los órdenes dados)

c) El producto matricial A_1 A_2.

d) Utilice el resultado de la parte c) para determinar la matriz de la relación R_2 o R_1.

e) Utilice el resultado de la parte d) para determinar la relación R_2 o R_1 (como un conjunto de pares ordenados).

Las relaciones dadas son:

R = {(1,x),(1,y),(2,x),(3,x)}

R_2 = {(x,b),(y,b),(y,a),(y,c)}

Órdenes: 1, 2, 3; x, y; a, b, c

Solución:

Las órdenes son los conjuntos que intervienen en las relaciones los mismos que los podemos escribir como:

X = {1, 2, 3} Y = {x, y} Z = {a, b, c}

Por tanto la matriz de una relación, es una representación de una relación cualesquiera R' de X a Y, para nuestro caso serían:

a) La matriz A_1 de la relación R_1, en este caso sería la relación R_1 de X a Y, la misma que esta dada por: 

b) La matriz A2 de la relación R2, en este caso sería la relación R2 de Y a Z, la misma que esta dada por: 

c) El producto de A1A2 es: 

d) Para obtener matriz de la relación , del punto c) tenemos que reemplazar cada término distinto de cero en el producto de matrices A1A2 obtenida en el punto anterior, conforme lo señala el Teorema 2.6.6 de la página 117 del texto básico, la misma que quedaría como a continuación se señala:

e) El conjunto de pares ordenados de la relación esta dado por: si la matriz A1 de la relación R1 que se expresa como la relación R1 de X a Y, intervienen los conjuntos X e Y; mientras la matriz A2 de la relación R2 que se expresa como la relación R2 de Y a Z, intervienen los conjuntos Y e Z. De donde podemos concluir que los conjuntos u órdenes que intervienen en la relación son: el conjunto X de R1 y el conjunto Z de R2; donde el conjunto de pares ordenados es:

R_2 o R_1 ={(1,a),(1,b),(1,c),(2,b),(3,b)} Respuesta

FUNCIONES

Una función puede considerarse como un caso particular de una relación o de correspondencia matemática. Cada relación o correspondencia de un elemento   

con un (y sólo un)   se denota  , en lugar de 

Formalmente, pedimos que se cumplan las siguientes dos condiciones:

Condición de existencia: Todos los elementos de X están relacionados con elementos de Y,

es decir, Condición de unicidad: Cada elemento de X está relacionado con un único elemento de Y,

es decir, si 

Notación y nomenclatura

Al dominio también se le llama conjunto de entrada o conjunto inicial. Se denota

por   o  . A los elementos del dominio se les llama habitualmente argumento de la función.

Al codominio, también llamado, conjunto de llegada, conjunto final o rango de f se le denota por

 o codomf

Cabe señalar que el término rango es ambiguo en la literatura, ya que puede hacer referencia tanto al codominio como al conjunto imagen. Por ello, es aconsejable usar el término codominio.

Si x es un elemento del dominio al elemento del codominio asignado por la función y denotado por f(x) se le llama valor o imagen de la función f de x. Al subconjunto del codominio formado por todos los valores o imágenes se le

llama imagen, alcance o recorrido de la función. Se denota por   o   o  .

Una preimagen de un   es algún   tal que  .

Note que puede haber algunos elementos del codominio que no sean imagen de un elemento del dominio, pero que cada elemento del dominio es preimagen de al menos un elemento del codominio.

Ejemplos

La función definida por  , tiene como dominio, codominio e imagen a todos

los números reales 

Función con Dominio X y Rango Y

Para la función   tal que  , en cambio, si bien su dominio y codominio son iguales a  , sólo tendrá como imagen los valores comprendidos entre 0 y +∞.

En la figura se puede apreciar una función  , con

Note que a cada elemento de X le corresponde un único elemento de Y. Además, el elemento a de Y no tiene origen, y el elemento b tiene dos (el1 y el 4). Finalmente,

Esta función representada como relación,

queda: Igualdad de funciones

Sean las funciones f: A → B y g: C → D, decimos que f es igual a g y escribimos f=g si y sólo si se cumple que ambas funciones:

1. tienen igual dominio, A=C,2. tienen igual codomino, B=D, y3. tiene la misma asignación, es decir que para cada x se cumple que f(x)=g(x).

Representación de funciones

Las funciones se pueden presentar de distintas maneras:

usando una relación matemática descrita mediante una expresión matemática: ecuaciones de la forma y = f(x). Cuando la relación es funcional, es decir satisface la segunda condición de la definición de función, se puede definir una función que

se dice definida por la relación, A menos que se indique lo contrario, se supone en tales casos que el dominio es el mayor posible (respecto a inclusión) y que el codominio son todos los Reales. El dominio seleccionado se llama el dominio natural, de la función.Ejemplo: y=x+2. Dominio natural es todos los reales.Ejemplo: "Para todo x, número entero, y vale x más dos unidades".

Como tabulación: tabla que permite representar algunos valores discretos de la función.Ejemplo:

X| -2 -1 0 1 2 3 Y| 0 1 2 3 4 5

Como pares ordenados: pares ordenados, muy usados en teoría de grafos.Ejemplo: A={(-2, 0),(-1, 1),(0, 2),(1, 3), ... (x, x+2)}

Como gráfica: gráfica que permite visualizar las tendencias en la función. Muy utilizada para las funciones continuas típicas del cálculo, aunque también las hay para funciones discretas.Ejemplo:

5 X

4 X

3 X

2 X

1 X

0 X

y / x -2 -1 0 1 2 3Clasificación de las funciones

Dados dos conjuntos X, Y, consideremos a todas las posibles aplicaciones (funciones) que pueden formarse entre estos dos conjuntos. Podemos diferenciar los siguientes casos:

Si a cada imagen le corresponde una única preimagen, inyectiva. Si la imagen de la función es igual al codominio, sobreyectiva o suprayectiva. Una función que sea inyectiva y sobreyectiva simultáneamente, se denomina biyectiva .

Puede haber funciones que sean biyectivas, inyectivas pero no suprayectivas, supreyectiva pero no inyectiva o que no se cumple ninguna de esas condiciones, en cuyo caso no tiene un nombre específico.

'Definiciones alternas: sea   dada y sea b un elemento cualquiera del codominio Y. Consideremos la ecuación

.

la función es suprayectiva o sobreyectiva si, y sólo si, la ecuación (*) siempre tiene al menos una solución.

la función es inyectiva si, y sólo si, la ecuación (*) tiene a lo más una solución. la función es biyectiva cuando, y sólo cuando, es inyectiva y suprayectiva a la vez.

Vamos a ilustrar esos diferentes tipos de funciones (aplicaciones) en un Diagrama de Venn, el conjunto universal U, representado por un rectángulo, es el conjunto de todas las posibles aplicaciones, el conjunto A es aquel de las aplicaciones inyectivas, y el conjunto B aquel de las sobreyectivas, esto nos permite ver los distintos tipos de aplicaciones de un modo gráfico.

Homomorfismo

En matemáticas, un homomorfismo, (o a veces simplemente morfismo) desde un objeto matemático a otro de la misma categoría, es una función que es compatible con toda la estructura relevante. La noción de homomorfismo se estudia abstractamente en el álgebra universal, y ése es el punto de vista tomado en este artículo. Una noción más general de morfismo se estudia abstractamente en la teoría de las categorías. Por ejemplo, si un objeto consiste en un conjunto X con un orden < y el otro objeto consiste en un

conjunto Y con orden u, entonces debe valer para la función   que, si

u < v   f( u ) < f( v ).

O, si en estos conjuntos hay definidas operaciones binarias + y *, respectivamente, entonces debe valer que: f(u + v) = f(u) * f(v). Ejemplos de morfismo son los homomorfismos de grupos, loshomomorfismos de anillo, los operadores lineales, las funciones continuas, etc.

Definición

Dado dos conjuntos no vacíos A y A', y las leyes de composición interna

La función   es un homomorfismo respecto de + y * si y sólo si la imagen de la composición en A es igual a la composición de las imágenes en A'. Es decir:

 es homomorfismo respecto de + y

* 

Cualquier homomorfismo f: X --> Y define una relación de equivalencia ~ en X como a ~ b si y solo si f(a) = f(b). En el caso general, este ~ se llama núcleo de f. Al conjunto cociente X/~ se le puede entonces dar una estructura de una manera natural, v.g., [x] * [y] = [x] * [y]. En ese caso la imagen de X en Y bajo el homomorfismo f es necesariamente isomorfa a X/~; este hecho es uno de los teoremas de isomorfía. Nótese que en algunos casos (v.g. grupos o anillos), una sola clase de equivalencia K es suficiente para especificar la estructura del cociente, así que escribimos X/K.

También en estos casos, es K, más bien que ~, el que es llamado el núcleo de f.

Tipos particulares de homomorfismos

Un homomorfismo suprayectivo se llama epimorfismo. Un homomorfismo inyectivo se llama monomorfismo. Un homomorfismo biyectivo cuya inversa es también un homomorfismo se

llama isomorfismo. Dos objetos isomorfos son totalmente indistinguibles por lo que a la estructura en cuestión se refiere.

Un homomorfismo de un conjunto a sí mismo se llama endomorfismo. Si es además un isomorfismo se llama automorfismo.

En topología, ciertos tipos de isomorfimos reciben nombres particulares:

Un homeomorfismo es un isomorfismo que preserva las características topológicas. Un difeomorfismo es un isomorfismo que preserva las características topológicas

y diferenciales.

ISOMORFISMO

El término 'isomorfismo' significa etimológicamente 'igual forma', y con ello se quiere destacar la idea según la cual existen semejanzas y correspondencias formales entre diversos tipos de sistemas en otras palabras Isomórfico (con una forma similar) se refiere a la construcción de modelos de sistemas similares al modelo original. Por ejemplo, un corazón artificial es isomórfico respecto al órgano real : este modelo puede servir como elemento de estudio para extraer conclusiones aplicables al corazón original.

El descubrimiento de un isomorfismo entre dos estructuras significa esencialmente que el estudio de cada una puede reducirse al de la otra, lo que nos da dos puntos de vista diferentes sobre cada cuestión y suele ser esencial en su adecuada comprensión.

Ejemplo de isomorfismo:

Por ejemplo, si X es un número real positivo con el producto e Y es un número real con la suma, el logaritmo ln:X→Y es un isomorfismo, porque ln(ab)=ln(a)+ln(b) y cada número real es el logaritmo de un único número real positivo. Esto significa que cada enunciado sobre el producto de números reales positivos tiene (sin más que sustituir cada número por su logaritmo) un enunciado equivalente en términos de la suma de números reales, que suele ser más simple.

Otro ejemplo: si en el espacio E elegimos una unidad de longitud y tres ejes mutuamente perpendiculares que concurren en un punto, entonces a cada punto del espacio podemos asociarles sus tres coordenadas cartesianas, obteniendo así una aplicación f:E→R³ en el conjunto de las sucesiones de tres números reales. Cuando en E consideramos la distancia que define la unidad de longitud fijada y en R³ consideramos la distancia que define la raíz cuadrada de la suma de los cuadrados de las diferencias, f es un isomorfismo. Este descubrimiento fundamental de Descartes permite enunciar cualquier problema de la geometría del espacio en términos de sucesiones de tres números reales, y este método de abordar los problemas geométricos es el corazón de la llamada geometría analítica.

Teoría analógica o modelo de isomorfismo sistémico:

Este modelo busca integrar las relaciones entre fenómenos de las distintas ciencias. La detección de estos fenómenos permite el armado de modelos de aplicación para distintas áreas de las ciencias.

Esto, que se repite en forma permanente, exige un análisis iterativo que responde a la idea de modularidad que la teoría de los sistemas desarrolla en sus contenidos.

Se pretende por comparaciones sucesivas, una aproximación metodológica, a la vez que facilitar la identificación de los elementos equivalentes o comunes, y permitir una correspondencia biunívoca entre las distintas ciencias.

Como evidencia de que existen propiedades generales entre distintos sistemas, se identifican y extraen sus similitudes estructurales.

Estos elementos son la esencia de la aplicación del modelo de isomorfismo, es decir, la correspondencia entre principios que rigen el comportamiento de objetos que, si bien intrínsecamente son diferentes, en algunos aspectos registran efectos que pueden necesitar un mismo procedimiento.

Un mapa puede ser isomórfico de la región que representa. También pueden serlo un objeto en movimiento y una ecuación, o el negativo de una fotografía con su ampliación. Otros isomorfismos incluyen una máquina de naturaleza mecánica, un aparato eléctrico y una cierta ecuación diferencial, todos los cuales pueden ser isornórficos. Por tanto, un aparato eléctrico puede ser un "modelo" de ecuación diferencial, una computadora analógica. "El propósito general más importante de la computadora digital es asombroso justamente porque puede programarse para resultar, isomórfico con cualquier sistema dinámico".'

Los aparatos isomórficos son valores en la ciencia. Una forma puede ser factible en un área en la que la otra es difícil de manipular. Puede demostrarse que el concepto de isomorfismo es susceptible de una, definición exacta y objetiva.. Las representaciones canónicas de dos

máquinas son isomórficas si una transformación de uno a uno de los estados de una máquina a la otra, puede convertir la representación de una en la otra. Pero la reclasificación puede tener varios niveles de complejidad; puede que las transformaciones no sean simples, sino complejas.

En administración tomaremos al isomorfismo como la presión que obliga a una empresa a parecerse a otra de la misma región, como una buena oportunidad de aumentar sus funciones comerciales.

Impacto del isomorfismo. El isomorfismo evalúa cómo las empresas toman la decisión de ingresar a los mercados internacionales, cuando ellos saben que las otras empresas se han desempeñado exitosamente.

Por ejemplo para determinar la entrada de las empresas colombianas a mercados internacionales se usa la teoría institucional, mientras el desempeño de estas es desconocido, el resultado es el isomorfismo.

Con el ejemplo de las empresas colombianas se evaluarán dos proposiciones de DiMaggio y Powell (1983), de la imitación de medianas y pequeñas empresas que están pensando en empezar a exportar y cómo el isomorfismo influye en el número de organizaciones que operan como exportadoras colombianas.

El mundo de los negocios que hoy se puede ver es aquel en el cual las organizaciones han empezado a ser más homogéneas; las imitaciones en prácticas y estructuras juegan un rol muy importante, ya que muchas organizaciones están copiando a sus competidores.

El proceso de imitación se hace a medida que una organización es más exitosa, ya que sus competidores tienden a imitarla.

Las siguientes dos proposiciones permiten obtener una real conclusión, acerca del objetivo propuesto.

Otro ejemplo podemos mencionar que durante casi todo este siglo las multinacionales americanas han difundido practicas de trabajo taylorianas a otros países, el solo hecho que estos países apliquen las practicas del trabajo tayloriano muestra un isomorfismo y así surgen las similaridades estructurales en distintos campos.

O también podríamos mencionar como ejemplo que en una organización las labores que realiza el factor humano son vitales, pero la tendencia obliga a disminuir ese esfuerzo humano y cambiarlo por esfuerzo robótico (isomorfismo), lo cual es una solución favorable para la empresa y para los mismos empleados, ya que las tareas rutinarias serán desarrolladas por estos y permitirá optimizar labores que requieran un mayor nivel de raciocinio a los empleados.

COMPLEJIDAD COMPUTACIONAL

La teoría de la complejidad computacional es la rama de la teoría de la computación que estudia, de manera teórica, la complejidad inherente a la resolución de un problema computable. Los recursos comúnmente estudiados son el tiempo (mediante una aproximación al número y tipo de pasos de ejecución de un algoritmo para resolver un problema) y el espacio (mediante una aproximación a la cantidad de memoria utilizada para resolver un problema). Se pueden estudiar igualmente otros parámetros, tales como el número de procesadores necesarios para resolver el problema en paralelo. La teoría de la complejidad difiere de la teoría de la computabilidad en que ésta se ocupa de la factibilidad de expresar problemas como algoritmos efectivos sin tomar en cuenta los recursos necesarios para ello.

Los problemas que tienen una solución con orden de complejidad lineal son los problemas que se resuelven en un tiempo que se relaciona linealmente con su tamaño.

Hoy en día las computadoras resuelven problemas mediante algoritmos que tienen como máximo una complejidad o coste computacional polinómico, es decir, la relación entre el tamaño del problema y su tiempo de ejecución es polinómica. Éstos son problemas agrupados en la clase P. Los problemas que no pueden ser resueltos por nuestras computadoras (las cuales son Máquinas Determinísticas), que en general poseen costes factorial o combinatorio pero que podrían ser procesados por una máquina no-determinista, están agrupados en la clase NP. Estos problemas no tienen una solución práctica, es decir, una máquina determinística (como una computadora actual) no puede resolverlos en un tiempo razonable.

Presentación

Un problema dado puede verse como un conjunto de preguntas relacionadas, donde cada pregunta se representa por una cadena de caracteres de tamaño finito. Por ejemplo, el problema factorización entera se describe como: Dado un entero escrito en notación binaria, retornar todos los factoresprimos de ese número. Una pregunta sobre un entero específico se llama una instancia. por ejemplo, "Encontrar los factores primos del número 15" es una instancia del problema factorización entera.

La complejidad temporal de un problema es el número de pasos que toma resolver una instancia de un problema, a partir del tamaño de la entradautilizando el algoritmo más eficiente a disposición. Intuitivamente, si se toma una instancia con entrada de longitud n que puede resolverse en n² pasos, se dice que ese problema tiene una complejidad en tiempo de n². Por supuesto, el número exacto de pasos depende de la máquina en la que se implementa, del lenguaje utilizado y de otros factores. Para no tener que hablar del costo exacto de un cálculo se utiliza la notación O. Cuando un problema tiene costo en tiempo O(n²) en una configuración de computador y lenguaje dado, este costo será el mismo en todos los computadores, de manera que esta notación generaliza la noción de coste independientemente del equipo utilizado.

Ejemplos

Extraer cualquier elemento de un vector. La indexación en un vector o array lleva el mismo tiempo sea cual fuere el índice que se quiera buscar, por tanto es una operación de complejidad constante O(1).

Buscar en un diccionario tiene complejidad logarítmica. Se puede iniciar la búsqueda de una palabra por la mitad del diccionario. Inmediatamente se sabe si se ha encontrado la palabra o, en el caso contrario, en cuál de las dos mitades hay que repetir el proceso (es un proceso recursivo) hasta llegar al resultado. En cada (sub)búsqueda el problema (las páginas en las que la palabra puede estar) se ha reducido a la mitad, lo que se corresponde con la función logarítmica. Este procedimiento de búsqueda (conocido como búsqueda binaria) en una estructura ordenada tiene complejidad logarítmica O(ln n).

El proceso más común para ordenar un conjunto de elementos tiene complejidad cuadrática. El procedimiento consiste en crear una colección vacía de elementos. A ella se añade, en orden, el menor elemento del conjunto original que aún no haya sido elegido, lo que implica hacer un recorrido completo del conjunto original (O(n), siendo n el número de elementos del conjunto). Este recorrido sobre el conjunto original se realiza hasta que todos sus elementos están en la secuencia de resultado. Se puede ver que hay que hacer n selecciones (se ordena todo el conjunto) cada una con un coste n de ejecución: el

procedimiento es de orden cuadrático O(n²). Hay que aclarar que hay diversos algoritmos de ordenación con mejores resultados.

RELACIONES DE RECURRENCIA

Una relación de recurrencia para una sucesión   es una fórmula que expresa cada término   a partir de cierto  , en función de uno o más de los términos que le preceden. Los valores de los términos necesarios para empezar a calcular se llaman condiciones iniciales. Se dice que una sucesión es una solución de la relación de recurrencia si su término general verifica dicha relación.

Ejemplo

Ejemplos particulares de relaciones de recurrencia son las de las formas:   (progresión aritmética),   (progresión geométrica). Sus soluciones son respectivamente,   y  . Por otra parte uno de los ejemplos más estudiados es la sucesión de Fibonacci que viene dada por:   y   para todo 

Relaciones de recurrencia lineales homogéneas

Si   para  , se dice que la relación de recurrencia es lineal homogénea de orden  .

Definición

Llamaremos ecuación característica de la relación de

recurrencia   a la ecuación  . A sus valores de solución se les llama raíces características.

Teorema 1

Dada la relación de recurrencia   con  , se verifica:

1- es raíz característica si y solo si es solución de la relación de recurrencia.2- Si es raíz doble de la ecuación característica, entonces es solución de la relación de recurrencia.3- Si y son soluciones de la relación de recurrencia, entonces y también lo son, para todo

Teorema 2

Dada la relación de recurrencia   con  :

1- Si la ecuación tiene dos soluciones reales distintas a y se

tiene que .

2- Si la ecuación tiene una solución real doble se tiene que

. y se determinan a partir de las condiciones iniciales y .

Relaciones de recurrencia lineales no homogéneas

Si   para  , se dice que la relación de recurencia es lineal no homogénea de orden  . A la

relación   resultante de eliminar   se le llama relación de recurrencia lineal homogénea asociada.

Proposición

Si   y   son soluciones de la relación de recurrencia lineal no homogénea, entonces   es solución de la relación de recurrencia lineal homogénea asociada.

Pasos para resolver una relación de recurrencia lineal no homogénea

- Se obtiene la solución general de la ecuación homogénea asociada. - Se obtiene una solución particular de la relación de recurrencia no homogénea. - La suma de la solución general de la ecuación lineal homogénea asociada y de una solución particular de la relación de recurrencia lineal no homogénea nos da la solución general de la relación de recurrencia lineal no homogénea. - La solución específica se obtiene a partir de las condiciones iniciales.

Observación

Una solución particular   de la relación de recurrencia lineal no homogénea se puede

encontrar en algunos casos especiales. - Si   (polinomio de grado  ,

entonces   (polinomio de grado  , excepto si 1 es raíz característica con

multiplicidad s, en cuyo caso  . - Si  ,

entonces  , excepto si a es raíz característica con multiplicidad s, en

cuyo caso   - Si  , entonces  , excepto

si a es raíz característica con multiplicidads, en cuyo caso 

Bibliografía:

Matemática Discreta y Lógica W.K Grassmann – J.P. Tremblay, Prentice Hall, 1997 Matemáticas Discretas Richard Johnsonbaugh, Prentice Hall, 1999