30
Coordinación de Ciencias Computacionales - INAOE Matemáticas Discretas (Mini) Cursos Propedéuticos 2012 Ciencias Computacionales INAOE Dr. Hugo Jair Escalante [email protected] http://ccc.inaoep.mx/~hugojair Oficina 8319 Este material se basa en versiones previas del mismo por: Dr. Enrique Muñoz de Cote Dr. Enrique Sucar Dr. Luis Villaseñor

Matemáticas Discretas

Embed Size (px)

DESCRIPTION

Matemáticas Discretas. (Mini) Cursos Propedéuticos 2012 Ciencias Computacionales INAOE Dr. Hugo Jair Escalante [email protected] http://ccc.inaoep.mx/~hugojair O ficina 8319. Este material se basa en versiones previas del mismo por : Dr. Enrique Muñoz de Cote - PowerPoint PPT Presentation

Citation preview

Conjuntos

Matemticas Discretas(Mini) Cursos Propeduticos 2012Ciencias ComputacionalesINAOE

Dr. Hugo Jair [email protected]://ccc.inaoep.mx/~hugojair Oficina 8319

Este material se basa en versiones previas del mismo por: Dr. Enrique Muoz de CoteDr. Enrique SucarDr. Luis VillaseorCoordinacin de Ciencias Computacionales - INAOE1CUARTA PARTERelaciones y funciones RelacionesPropiedades de relacionesClases de equivalenciaConjuntos parciales y totalmente ordenadosFunciones2Producto cartesianoDados dos conjuntos A y B, el producto cartesiano AB se define por:AB = { (x, y) | xA, yB}

Ejemplo:{a,b}{1,2,3} = {(a,1),(b,1),(a,2),(b,2),(a,3),(b,3)}

Note que los elementos (x, y) son pares ordenados: hay una diferencia entre (a, 2) y (2, a)

En general: AB BACuntos pares ordenados se pueden generar si el nmero de elementos de A y B son |A| y |B|?3Teorema Para conjuntos arbitrarios A, B, C U.

a) b) c) d)

RelacionesEl producto cartesiano y las operaciones binarias de unin e interseccin estn interrelacionados con el siguiente teorema.4RelacionesDados dos conjuntos A y B, una relacin binaria R de A en B es determinada por cualquier subconjunto R AB

Se dice que aRb si y solo si (a, b)R

Si A=B, se dice que R es una relacin binaria en ACuntas relaciones se pueden generar si el nmero de elementos de A y B son |A| y |B|?5EJEMPLO Si A = U =Z+, se define una relacin binaria R en el conjunto A como . Se trata de la conocida relacin es menor o igual que para el conjunto de los enteros positivos,

Se observa que (7,7),(7,11)R, y (8,2)R, (7,11)R tambin se puede denotar como 7R 11; (8,2)R se transforma en 8R 2 son ejemplos de notacin infija en una relacin. Relaciones6En general, para conjuntos finitos A, B donde |A| = m y |B| = n, hay 2mn relaciones de A a B, incluyendo la relacin vaca y la propia relacin A B. Relaciones7EjemploSea U={1, 2, 3, ,7}, A={2, 3, 4} y B={4, 5}, las siguientes son ejemplos de relaciones de A a B:{(2, 4), (2, 5)}{(2, 4), (3, 4), (4, 5)}{(2, 4), (3, 4), (4, 4)}8EjemploLa relacin de menor que < en el conjunto de nmeros naturales N se describe por el conjunto:{(0,1),(0,2),(1,2),(0,3),} NN

La relacin de igualdad = en R se define por el conjunto:{(x, x) | xR} RR9Propiedades de las relacionesUna relacin R en A es reflexiva si:Si (a, a) R para toda a A

Una relacin R en A es antireflexiva si:Si (a, a) R para toda a A10EjemploSe A={1, 2, 3, 4}, considere las siguientes relaciones R sobre A y determine si son reflexivas:R={(1, 1), (2, 2), (3, 3)}No es reflexivaR={(x, y)| x, y A, x y}Es reflexiva

11Propiedades de las relacionesUna relacin R en A es simtrica si:Si (a,b)R entonces (b,a)R para todo a,bA

Una relacin R en A es antisimtrica si:Si (a,b)R y (b,a)R entonces a=b

Una relacin R en A es transitiva si:Si (a,b)R y (b,c)R entonces (a,c)R para todo a,bA

12EjemploSea A={1, 2, 3} y R una relacin en AR={(1,2),(2,1),(1,3),(3,1)}Simtrica y no reflexivaR={(1,1),(2,2),(3,3),(2,3)}Reflexiva y no simtricaR={(1,1),(2,3),(3,3)}No Simtrica y no reflexiva

13EjemploSea A={1, 2, 3, 4}R={(1,1),(2,3),(3,4),(2,4)}Es una relacin transitiva en AR={(1,3),(3,2)}No es transitiva14EjemploSea A={1, 2, 3}R={(1,2),(2,1),(2,3)}No simtrica y no antisimetricaR={(1,1),(2,2)}Simtrica y antisimetrica

15OrdenamientosRelaciones comunes tales como definen ordenamientos

Una relacin R en A es un ordenamiento parcial si y slo si es una relacin reflexiva, antisimtrica y transitiva

(A, R) es un conjunto ordenado parcialmente o poset si R es un ordenamiento parcial en A16Pg.353pg. 353EjemploSea A={1, 2, 3, 4, 6, 12} y sea R la relacin en A dada por (x, y) R si x divide exactamente a y

R es reflexiva?R es transitiva?R es antisimtrica?Por lo tanto R define un ordenamiento parcial en A17ParticionesUna particin de un conjunto A es un conjunto de subconjuntos {Aj} tal que:AiAj = para todo ijA = j Aj 18EjemploSea A={1, 2, 3, ,10}, las siguientes son ejemplos de particiones de A:A1={1, 2, 3, 4, 5}, A2={6, 7, 8, 9, 10} A1={1, 3, 5, 7, 9}, A2={2, 4, 6, 8, 10}A1={1, 2, 3}, A2={4, 6, 7, 9}, A3={5, 8, 10}Ai={i, i+5}, 1 i 519FuncionesUna funcin f:AB del conjunto A a B es la relacin fAB tal que cada aA est relacionada con un nico b tal que (a,b)f

Notacin f(a)=b, o f:a b

A es el dominio de f y B es el codominio

El valor f(a)=b es la imagen de aA bajo f

El conjunto { f(a) | aA } es el rango de f20EjemploSea A={1, 2, 3} y B={w, x, y, z}:Es f={(1, w), (2, x)} una funcin de A a B?NoEs f={(1, w), (2, w), (2, x), (3, z)} una funcin de A a B?NoEs f={(1, w), (2, x), (3, x)} una funcin de A a B?Si

21Composicin de funcionesSean f: A B y g: B C dos funciones. La composicin de las funciones f y g, denotada por (g o f) es la funcin: (g o f): A C tal que Para todo a A, (g o f)= g(f(a))22Tipos de funcionesUna funcin es inyectiva o uno a uno si para cada x A tiene una nica imagen f(a):Si f(x)=f(y) entonces x=y.Elementos distintos de A tienen siempre imgenes distintas

Sea f: R R donde f(x)= 3x + 7 para toda xEs una funcin uno a uno23EjemploSea A={1, 2, 3} y B={1, 2, 3, 4, 5}.

Es g={(1, 1),(2, 3),(3, 3)} una funcin uno a uno de A a B?No24Tipos de funcionesUna funcin es sobre o suprayectiva si para cada yB existe al menos una xA tal que f(x)=y:

Si yB entonces existe una xA tal que f(x)=y

Sea f: R R donde f(x)= x3 para toda xEs una funcin sobre o suprayectiva?Si

25Tipos de funcionesUna funcin es una biyeccin entre A y B si es una funcin uno a uno y suprayectica

Sea A={1, 2, 3 , 4} y B={w, x, y, z}. Es f={(1, w), (2, x), (3, y), (4, z)} de A a B una biyeccin?Si

26EjemplosLa funcin lineal f: ZZ, definida por f(x)=x+2Es inyectivaEs suprayectivaEs biyectiva

27Composicin de funcionesSi f: A->B y g:B->C, definimos la funcin compuesta que se denota g o f: A->C, como (g o f)(a)= g(f(a)), para cada a en A

Composicin de funcionesSea A={1,2,3,4}; B={a,b,c}; C={w,x,y,z}, con f: A->B; g: B->C, dadas por f={(1,a),(2,a), (3,b), (4,c)} y g={(a,x), (b,y), (c,z)}, calcule:g o f (1)g o f (2)g o f (3)g o f (4)