• Author / Uploaded
• Flavia Vanina Muñoz

Citation preview

Trabajo Práctico Nº 1

Conjuntos 1-Se consideran los conjuntos A ={2,4,6};B={6, 4,2,6 };C ={1,0,3} ;D={x  Z / x2 3 };E={6} 1.1. Indicar, justificando, cuáles de las siguientes proposiciones son verdaderas y cuáles son falsas: A=B 1D {4,6}  A D C {6}  E E  {{6}} 1.2 Hallar P(C) y P (P (E)) 1.3 Realizar las siguientes operaciones: (A  B) – C ;( C  B)  A; E  A ;( A  C)  E (A  E) – B; D C 2- Siendo A =  a, b, c, a, b, , indicar, justificando cuáles de las siguientes proposiciones son verdaderas y cuáles son falsas: 2.1 a, b A 2.2 a, b  A 2.3   a, b 2.4   A 2.5 , a, b   a, b 2.6 , a, b   A 2.7  a, , b, , c, , a, b,  = A 2.8  a, b   A 2.9  a, b, c  A 2.10  a, b, c, a, b  = A 2.11 a, b, c  A 3- Indicar el valor de verdad de cada una de las siguientes proposiciones con V = a, b a) V c)  V* b)  V d) V+ 4- Siendo A = , indicar, justificando cuáles de las siguientes proposiciones son verdaderas y cuáles son falsas: 4.1   A 4.2   A 4.3   P(A) 4.4   P(A) 4.5  = A 4.6   P(P(A)) 5-Siendo el alfabeto V = {2, 4}, determinar el valor de verdad de las siguientes expresiones. Matemática Discreta (1028)

Ingeniería - UNLaM

Justificar. 5.1. λ  V 5.2. {242, 22, 44}  V+

5.3. {2}  V 5.4. 22  V*

5.5. 5.6.

242  V* long (222) =1

6- Dado A = 5: 6.1 Hallar P (P(A)) 6.2 Determinar el valor de verdad de las siguientes expresiones: 6.2.1.  P (P (A)) 6.2.2.   P (A) 6.2.3. 5 P (P (A)) 6.2.4. 5  P (A) 6.2.5. P(A)  P (P(A)) 7- Determinar el valor de verdad de las siguientes expresiones:



i) 1  1, 1 ii) 1  1, 1 iii) 1  1, 1 iv) 1, 1  P 1, 1



8- Determinar el valor de verdad: Si A = {a, {b}} entonces: { b } P(A);{ a, {b} }  P (A) ; b  A; {{b }} P (A). 9- Demostrar las siguientes propiedades: 

9.1. A = (A  B )  (A  B) 



9.2. A  B = (A  B )  B = A  ( A  B) 







9.3. (A B )  ( A  B) = (A  B)  ( A  B ) 9.4. (A  B) - C = (A - C)  (B - C) 9.5. A - (B - C) = (A - B)  (A  C) 10-¿Qué podes decir de los conjuntos A y B si se sabe que 10.1 AB = A? 10.2 A - B = A? 10.3 A  B = A?

Producto Cartesiano 11-Sean los conjuntos A= {-2,-1}; B= {x  N / 1  x  3} y C= {a, b} Hallar AxC; CxA; AxBxC; A2 ; C3 12- Dado A = 3, 8: 12.1 Hallar P ( A2 ) 12.2 Determinar el valor de verdad de las expresiones: 12.2.1 (3,3)  A2 12.2.2 (3,8)  P (A) 12.2.3 (3,8), (8,3) P (A2 ) 12.2.4 8  P(A2 ) 2 Matemática Discreta (1028)

Ingeniería - UNLaM

12.2.5   A2 13- Dado el alfabeto V = a, b , hallar V, V0 V1, V0, V*, V+

Representación de un conjunto por un ordenador 14-Definida f: U  0, 1 de tal forma:  U y x  U

f A (x) =

1 0

si x  A si x  A

se denomina función característica restringida al conjunto A. Verificar: siendo A, B  U 14.1 A = B  f A = f B 14.2 f A  B = f A . f B 14.3 f A  B = f A + f B - f A . f B 14.4 f A  B = f A + f B - 2 f A . f B 15- Sea U = a, b, c, d, e, f, g; A = a, b; B = g; C = b, c, g, hallar: 15.1 f B (g) 15.2 f C (a) 15.3 Representar f A, f B , f C , f U , f  usando arreglos de ceros y unos. 15.4 Representar f A  B , f B  C , f A  C , f U - C usando arreglos de ceros y unos. 16- Usando la función característica verificar que la operación diferencia simétrica es asociativa.

Operaciones entre cadenas

17- Sea x = abb, calcular: a ) xR b ) x0

3

f)



xi

i 1

1

c)x d ) x2 e ) x3

3

g )  xi i=0

18- a) Dadas x = abb e y = acd calcular las siguientes hileras y dar sus longitudes: a1) xy a5) x23y2 a2) x a6) (xy)2 a3) y a7) yRxR a4 ) xy 19- Sea el vocabulario V = {a, b, c} y los lenguajes L1 =  , L2 = {ac, ba}, L3 = {aba, aca}: hallar: L3 2, L2 L3, L2 L3, L1 0, L2 R, L3 0, L3 R 3 Matemática Discreta (1028)

Ingeniería - UNLaM

20- Indicar el valor de verdad de cada una de las siguientes proposiciones a )  g )  b )  = 1 h ) * c ) L = L = L i ) L  L* d ) L = L =  j )  L* e ) 0 = 

3

k )  a, bk= 7 k=0

f ) * = 

l ) L = L = 

21- a) Sea V = a, b alfabeto, A = ab, ba y B = , b2 lenguajes a1) Hallar A2, AV a2) Describir B*, AB b) Dados los lenguajes A = a, ab, aa, B = cab, bac, cc y el alfabeto V = a, b, c y E = , calcular AB, VA, E96 22- Indicar ejemplos de hileras x  L a) L = akbp / k 0, p0 b) L = akbp / k 1, p1 c) L = akbp / k 0, p1 d) L = akbp / k 2, p1 e) L = akbp / k 1, p0 f) L = anbn / n 0 g) L = anbn / n 1

4 Matemática Discreta (1028)

Ingeniería - UNLaM

Trabajo Práctico Nº 2 Relaciones

1-Enumera los pares ordenados de la relación R de A={0,1,2,3,4} en B={0,1,2,3},donde (a,b)  R si y solo si: 1.1 a=b 1.2 a+b=4 1.3 a  b 1.4 a b 1.5 mcd (a, b)=1 1.6 mcm(a, b) = 2 2- Dado A = {1, 2, 3} y B = {a, b} 2.1 ¿Cuántas relaciones se pueden definir de A en B? 2.2 Para cada una de las relaciones de A en B indicar dominio e imagen: R = {(1, a), (2, b), (3, a), (3, b)} S = {(2, a), (3, b)} T = {(1, a), (2, a), (3, a)} V=  W=AxB 3- Sea R  N x N definida por: R = (x, y) / x + 2y = 12. Se pide: 3.1 Expresar R por extensión 3.2 Hallar DR e IR 3.3 Hallar DR -1 e IR -1 3.4 Representar en un diagrama cartesiano

4- Sea A = {a, b, c} y B = {1, 2, 3, 4} y las relaciones R y S definida de A en B: R = {(a, 1), (a, 2), (a, 4), (b, 4), (c, 1), (c, 2), (c, 3)} S = {(a, 2), (a, 3), (b, 1), (b, 4), (c, 1), (c, 2)}, Hallar:R, R-1 ,S, S-1 , S  R, (R  S)-1 , R-S, S-R 5- Sean R, S relaciones de A en A.¿ Cuáles de las siguientes proposiciones son válidas? 5.1 DR  S = DR  DS 5.2 I R  S = IR  IS 5.3 D R  S = DR  DS 5.4 I R  S = IR  IS 6-Sean A = {a, b, c}, B = {x, y, z}, C = {a, y, b}, R  A x B, S  B x C tal que R = {(a, y), (b, x), (b, z)}, S = {(x, a), (y, y), (z, b)}, hallar S o R 7- Para el conjunto A = 0, 1, 2, 3 y las relaciones definidas de A en A R1 = (0, 0), (1, 1) ; R2 = (0, 1), (2, 3) ; R3 = (0, 1), (1, 2), (2, 3); R4 = (0, 1) ; R5 = (0, 1), (0, 0), (1, 1), (1, 0); R6 = (2, 2) 5 Matemática Discreta (1028)

Ingeniería - UNLaM

Hallar: R3 º R5, R5 º R3, R2 º R4 , R4 º R2 , R4 º R4 , R1 2 , R6 3

Manejo Matricial de Relaciones 8- Calcular A B, A  B, A  B  1 1  0 1 8.1 A=  B=     1 0  0 1 8.2

 1 0 1   A =  0 1 0    0 0 1

 1 0 0   B =  0 1 0    1 0 1

9 -Si A = 1, 2, 3 y B =1, 4, 6, 9 Escribir por extensión R: A  B tal que a R b  a b Hallar la matriz de R; el dominio y la imagen de R;R por extensión y la matriz MR ; R-1 por extensión y la matriz MR-1 10- Dado A = {1, 2, 4}, B = {2, 4, 9} y R: AB definida por a R b  “b es múltiplo de a” indicar: 10.1 R por extensión y la matriz MR 10.2 R por extensión y la matriz MR 10.3 R-1 por extensión y la matriz MR-1 Calcular: __ 10.4 MR v M-R 10.5 ( MR )t  M R-1 11-Representa cada una de estas relaciones en el conjunto A= {1, 2,3} mediante una matriz (con los elementos de este conjunto listados en orden creciente) 16.1-{(1,1), (1,2), (1,3)} 16.2-{(1,2), (2,1), (2,2), (3,3)} 16.3-{(1,1), (1,2), (1,3), (2,3), (3,3)} Dibuja el dígrafo de cada una de las relaciones anteriores. 12- Si A = B = D6 =x / x es divisor positivo de 6 12.1 Escribir por extensión R definida por: a R b  a + b  5 12.2 Hallar el dígrafo de R 12.3 Hallar el dominio y la imagen de R 12.4 Hallar la matriz de R 1 0 13-Sea R la relación definida en A = a, b, c, d, representada por  1  0 Dar por extensión la relación R

1 0 1 0 0 1  1 1 0  1 0 1



Hallar la matriz y el dígrafo que representa a: R-1, R , R3 6 Matemática Discreta (1028)

Ingeniería - UNLaM





14-Calcular R  S, R  S, R-1 , R , S-1 , S para R y S definidas por los siguientes esquemas:

15- Dados A = 1, 2, 3, B = a, b, C = a, 4, 5, R: A  B, S: B  C con R = (1, a), (2, b), (3, a) S = (a, a), (a, 4), hallar: 15.1 S ° R 15.2 MR 15.3 MS 15.4 M S ° R = MR  MS 16- Para el conjunto A definido en el ejercicio 7, hallar: MR6 º R4 , MR6 º R6 , MR4 º R4 , MR6 º R4

7 Matemática Discreta (1028)

Ingeniería - UNLaM

Trabajo Práctico Nº 3 Relaciones Binarias – Propiedades 1- Sea A = 0,1.Utilizando el dígrafo, estudiar las propiedades de las siguientes relaciones: 1.1 R1 = (0,0), (1,1) 1.2 R2 = (0,1), (1,0) 1.3 R3 = (0,0), (0,1) 1.4 R4 = A x A 2- Sea A = 0, 1, 2, 3 Utilizando las definiciones, estudiar las propiedades de las siguientes relaciones: 2.1 R1 =  2.2 R2 = (0,0), (1,1) 2.3 R3 = (0,1), (2,3) 2.4 R4 = (0,1), (1,2), (2,3) 3-Sea A = 0, 1, 2, 3 Utilizando matrices, estudiar las propiedades de las siguientes relaciones: 3.1 R1 = (0,1) 3.2 R2 = (0,1), (0,0), (1,1), (1,0) 3.3 R3 = (2,2) 4-Dar un ejemplo de una relación en el conjunto A= {1, 2, 3,4} que: 4.1 Sea reflexiva y simétrica, pero no transitiva 4.2 Sea simétrica y transitiva, pero no reflexiva 4.3 Sea reflexiva, antisimétrica, pero no transitiva 4.4 Sea reflexiva, antisimétrica y transitiva 5- Dado A = a, b, c y cada una de las siguientes relaciones R: A  A, estudiar sus propiedades e indicar cuales son de equivalencia y de orden

8 Matemática Discreta (1028)

Ingeniería - UNLaM

6- Estudiar las propiedades de cada una de las relaciones R definidas en cada uno de los siguientes casos y clasificarlas: 6.1 x R y  x y en Z 6.2 x R y  x y en N 6.3 x R y  x = y2 en N 6.4 x R y  x = y2 en 0,1 6.5 x R y  n (x – y) en Z, n  N 6.6 x R y  x  y en Z 7-Si D12 = x / x es divisor positivo de 12, se define: a R b  2 (a-b), a S b  3 (a-b): 

calcular R , R S, RS, S-1 y estudiar sus propiedades (clasificar) 8- En el conjunto R de los números reales se definen: a R b  a < b, a S b  a > b: 

hallar R S, RS, R-1 , S y estudiar sus propiedades (clasificar ). 9- Sean R1 y R2 dos relaciones definidas sobre A. Probar: 9.1 Si R1 y R2 son antisimétricas, entonces R1  R2 es antisimétrica en A; 9.2 Si R1 y R2 son simétricas, entonces R1  R2 es simétrica en A. 10- Si R y S son relaciones de equivalencia en A ¿Es R ° S una relación de equivalencia en A? 11-Indique el valor de verdad de las siguientes afirmaciones, demostrando o justificando correctamente: 11.1. La relación vacío definida sobre un conjunto no vacío no tiene propiedades. 11.2. Ninguna relación de equivalencia es antisimétrica 11.3. Si R, S son reflexivas → R ° S es reflexiva

9 Matemática Discreta (1028)

Ingeniería - UNLaM

Trabajo Práctico Nº 4

Relaciones de equivalencia 1-Justificar cuáles de los siguientes conjuntos son una partición de A = 1, 2, 3, 4, 5 1.1 1,2, 3,4, 5 = P1 1.2 1,2, , 3, 4,5 = P2 1.3 1,2, 3,3, 4,5 = P3 1.4 1,2, 3,4 = P4 1.5 1, 2,3, 4, 5 = P5 2-Sean el conjunto A={1,2,3,4,5,6} y la relación R={(1,1),(1,2),(2,1),(2,2),(3,3), (4,4),(4,5),(5,4),(5,5),(6,6)}en A. ¿Es R una relación de equivalencia? Dar el conjunto cociente. 3-Sean A= {1, 2, 3, 4, 5, 6,7} y una relación R en el conjunto A definida por: xRy  -y es múltiplo de 3 Demostrar que R es de equivalencia y calcular las clases de equivalencia originadas por R. 4-Verificar que las siguientes relaciones son de equivalencia y hallar las clases de equivalencia y el conjunto cociente: 4.2 R  Z x Z a R b  (-1) a = (-1) b 4.3 x R y  x .y > 0 en Z - 0 6-Sea A={1,2,3,4,5}x{1,2,3,4,5} y sea la relación R en A definida por: (a; b) R (c, d) si y sólo si a+b=c+d. 6.1. Demostrar que R es de equivalencia. 6.2. Determinar las clases [(1,3)], [(2,4)] y [(1,1)]. 6.3. Determinar la partición de A originada por R. 7- En el conjunto A= {15, 22, 34, 45, 68, 54,125} se define la siguiente relación de equivalencia: a ≡ b (5) ↔ 5|(a-b) Hallar las clases de equivalencia y el conjunto cociente. 8-Dados los conjuntos cocientes Z1,Z2,Z3,Z4,Z5 ,hallar en cada caso la relación de equivalencia correspondiente y las clases de equivalencia. 9-9.1. Sea R1 la relación módulo 2 y R2 la relación módulo 3, definidas sobre Z; hallar R1  R2 y el conjunto cociente: Z  R1  R2. 9.2 Sea R1 la relación módulo 6 y R2 la relación módulo 10, definidas sobre Z; hallar R1  R2 y el conjunto cociente: Z / R1  R2. 10-Sea V un alfabeto, en V* se define la relación w1 R w2  long (w1) = long (w2). Probar que es una relación de equivalencia, hallar las clases de equivalencia y el conjunto cociente. 11-En el lenguaje L= {aaba, aaa,bab, ,ba,bbb} se define la siguiente partición P ={{aaba},{aaa,bab,ba},{ , bbb}}.Probar que P es partición de L y hallar la matriz de la relación de equivalencia inducida por P 10 Matemática Discreta (1028)

Ingeniería - UNLaM

12- Sea A = a, b, c, d, e, f, g  y P = a, b, c,d, e,f, g: hallar la matriz de la relación R: A  A que define la partición P. 13- Sea A = {1; 2; 3; 4; 5; 6; 7; 8; 9; 10}.3.1. Hallar y graficar la relación de equivalencia en A asociada a la partición {{1; 3} ;{2; 6; 7} ;{4; 8; 9; 10} ;{5}} 14- Si R es una relación de equivalencia definida en un conjunto A entonces R 1 también es de equivalencia en A. a) la afirmación es verdadera. b) la afirmación es falsa.

Relaciones clausuras 15- Sea A = {a, b, c, d, e} y la relación R  A x A tal que R = {(a, b); (a, c); (a, e); (e, d); (b, c); (c, c); (c, d); (d, a); (d, c) }, hallar: R A ; RR-1; R2 ; R3{c}. 16- Sea A = {1, 2, 3, 4} y las relaciones definidas sobre A: R1 = {(1, 2), (2, 2), (2, 4), (3, 2), (3, 4), (4, 1), (4, 3)} R2 = {(1, 1), (1, 2), (2, 3), (3, 4)} R3 = {(1, 2), (1, 3), (1, 4), (3, 2), (3, 3), (3, 4)} En cada caso indicar: 16.1 MR, el dígrafo de R 16.2 clausura reflexiva, clausura simétrica, clausura transitiva 16.3 MR*, el dígrafo de R* 17- Si A = a, b, c y R = (a, a), (a, b), (a, c), (c, a), (c, b), (b, c): 17.1 Hallar MR  usando: MR  = MR  (MR )2  (MR )3 17.2 Hallar R  usando el algoritmo de Warshall  1 0 0 1 0    0 1 0 0 0 17.3 Si MR =  0 0 0 1 1 = W0    1 0 0 0 0    0 1 0 0 1 Hallar W1, W2 y W3 usando Warshall 18-Hallar en forma analítica la relación más pequeña posible que contenga a R 1 = {(1; 2), (2; 4), (3; 3), (4; 1)} y a R2 ={(1;1),(3;4),(4;3)} definidas en A={1,2,3,4,5} y sea reflexiva ;simétrica y transitiva .¿Coincide R∞ con R*?

11 Matemática Discreta (1028)

Ingeniería - UNLaM

Trabajo Práctico Nº 5 Conjunto Ordenado 1-En el conjunto A= {0, 2, 5, 10, 11,15}, se define la relación  : x  y  x  y 1.1 Probar que (A,  ) está ordenado 1.2 Realizar el diagrama de Hasse 1.3 ¿Está totalmente ordenado? ¿Es un buen orden? 2-Sea A= {a, b} en P(A) se define  : X  Y  X Y 2.1 Probar que P(A) queda ordenado por  2.2 Realizar el diagrama de Hasse 2.3 ¿Está totalmente ordenado? ¿Es un buen orden? 3- En N se define la relación  en la siguiente forma: x  y  x y 3.1 Probar que es un orden en N. ¿Queda Z ordenado por ? 3.2 Dibujar el diagrama de Hasse de la relación de divisibilidad para los siguientes conjuntos A={1,2,3,4,6};B={3,5,7.13,16,17};C={2,3,5,10,11,15,25};D={1,3,9,27,81} 3.3 Indicar cuáles son órdenes totales y cuáles son buenos órdenes. 4-Sean ( D3,  ) y (P(A),  ) , A={ a,b },conjuntos ordenados, 4.1-Probar que  definida por (a, B)  (c, D)  a c  B  D ordena al conjunto D3 x P(A) 4.2- Dibujar el diagrama de Hasse para ( D3 x P(A),  ) 4.3-¿Está D3 x P(A) totalmente ordenado? 5-Si (A, 1 ) y ( B, 2 ) son conjuntos ordenados, 5.1 Probar que  definida por (a, b)  (c, d)  a 1 c  b 2 d ordena al conjunto A x B 5.2 ¿Cuáles son las condiciones para que (A x B, ) sea un orden total ? 6-Dadas las siguientes proposiciones probar las verdaderas y dar un contraejemplo para las falsas 6.1 Si  es un orden en A entonces  -1 es un orden en A 6.2 Si ( A,  ) es un orden parcial entonces ningún subconjunto no vacío de A está totalmente ordenado por  7-Para cada uno de los conjuntos ordenados del ejercicio 3.2 hallar los elementos maximales; los elementos minimales, ¿hay máximo?, ¿hay mínimo? y los átomos. 8-8.1 Sea D = 1, 2, 3, 4, 5, 6, 7, 8 ordenado como sigue

12 Matemática Discreta (1028)

Ingeniería - UNLaM

Hallar los elementos maximales y minimales; ¿Hay máximo? ¿Hay mínimo? Enumerar los subconjuntos de 3 elementos que estén bien ordenados Considerar el subconjunto B= {4, 5,6} y hallar cotas superiores e inferiores de B ¿Hay supremo para B? ¿Hay ínfimo para B? 8.2 En A = a, b, c, d, e, f, g ordenado como sigue:

Hallar maximales; minimales; primer elemento; último elemento; átomos y el subconjunto de mayor cardinal que esté bien ordenado de A Considerar B = c, d, e y hallar cotas superiores e inferiores, ínfimo, mínimo, supremo, máximo de B

9- Sea ( A,  ) y  , sea m maximal de ( A,  ) y k cota superior de B: Demostrar que si se ordena a A con el orden recíproco -1 resulta m minimal y k cota inferior de B. 10-Ordena de acuerdo con el orden lexicográfico de las cadenas de bits: 0, 01, 11,001, 010, 011, 0001 y 0101 basándose en el orden usual 0  1. 11- Sobre D44 definir una relación de orden amplio no lineal; b) para el subconjunto {4, 22} indicar las cotas inferiores, superiores, ínfimo, y supremo, de ser posible; c) para el subconjunto {2, 22, 44} determinar si es bien ordenado, justificar. 12- Sea el conjunto A = {(0,0),(1,0),(2,0),(3,0),(0,1),(1,1),(2,1),(3,1),(0,2),(1,2),(2,2),(3,2)} y sea la relación (a,b)  (c,d) si y sólo si a  c y b  d 12.1 Probar que  es una relación de orden. 12.2 Realizar el diagrama de Hasse 12.3 Determinar (si existen) las cotas inferiores, las cotas superiores, el supremo, el ínfimo, el máximo y el mínimo del subconjunto B = {(1,1), (1,2),(2,1)}.

13 Matemática Discreta (1028)

Ingeniería - UNLaM

Red 13- Determinar si el conjunto con la relación dada es retículo: 13.1 A = a, b, c, d, f

13.2 A = a, b, c, z, u 

14-Los siguientes diagramas de Hasse no representan retículos.¿Por qué? A={a,b,c,d,e,f}

B={1,2,3,4,5,6}

15- Obtener los diagramas de Hasse de todos los retículos, salvo isomorfismos, de uno, dos, tres, cuatro y cinco elementos.

16-En A =  se definen 1 y 2 órdenes de la siguiente forma: a 1 b  a.b = a



a 2 b  a + b = a con

. 0 1

0 0 0

1 0 1

+ 0 1

0 0 1

1 1 1 14

Matemática Discreta (1028)

Ingeniería - UNLaM

Probar que (A, 1) y (A, 2) son redes; 17-17.1 Sea D30 = x  N / x  30, probar ( D30,  ) con a  b  a b, es red, dibujar el diagrama de Hasse, 17.2 ¿( D12, | ) es red? 18-Sea B = {a, b}, probar ( P(B),  ) es red 19-¿Cuáles de los siguientes subconjuntos de N son retículo con el orden definido por a  b  a b ? ¿Por qué?

a) {5, 10, 15, 30};

b) {1, 3, 7, 15};

c) {2, 3, 5, 6, 10, 30};

15 Matemática Discreta (1028)

Ingeniería - UNLaM

Trabajo Práctico Nº 6 Álgebra de Boole – Funciones booleanas

8-Para cada uno de los siguientes conjuntos ordenados, definir, si es posible, dos operaciones binarias de modo de obtener un retículo algebraico 8.1 (P(A), ) ,A={1,2} 8.2 (D30 , ) 8.3 (, 1 ) siendo a 1 b  a.b = a . 0 1 0 0 0 1 0 1 9- 9.1 Dado (N, mcm, mcd) retículo algebraico: 9.1.1 Calcular: 18.35, (74.24) + 5 9.1.2 Resolver: 6.x = 2; 8 + x = 24 9.2 En el retículo (D30, mcm, mcd): 9.2.1 Resolver: 10 + x = 30; 10. x = 5 9.2.2 Calcular: 2 + 30, 6. 10, 6 + 15, 6. 30 10-Calcular los complementos de cada elemento de las siguientes redes: 10.1 (D30 , ) 10.2 (D 12, ) 10.3 A= {a, b, c, d, f}

11-¿Cuáles de las siguientes redes son distributivas? 11.1 (D30, mcm, mcd) 11.2 (P(A),,), A= {1,2} 11.3 A= {1, 2, 3, 4, 5, 6, 7,8}

11.4 A= {a,b,c,d,e,f ,g} 16 Matemática Discreta (1028)

Ingeniería - UNLaM

12-¿Cuáles de los retículos de los ejercicios 10 y 11 son Álgebras de Boole? 13- Sea (D182, mcm, mcd) álgebra de Boole: 13.1 Indicar los elementos neutros correspondientes a cada operación, 13.2 El complemento para cada elemento, 13.3 Los átomos 14-Sea (D40;|) conjunto ordenado. 14.1. Realizar el diagrama de Hasse.Hallar los elementos maximales, minimales, máximo, mínimo, cotas superiores, cotas inferiores, supremo , ínfimo del subconjunto S={2,4,8,20} 14.2. ¿Es red? En caso de ser red ¿es Álgebra de Boole? Justificar 15-Demostrar 15.1 Sea ( A, + , . ) el retículo distributivo y complementado si: x  a  y  a  x=y   x. a  y. a 15.2 Sea ( A, + , . ) el retículo distributivo y complementado. 



15.2.1 Si y . z = 0  y  z ( z complemento de z) 

15.2.2 Si x  y  y . z = 0  z  x 

16- Sea ( A, + , . ) álgebra de Boole con neutros 1A, 0A y a = “complemento de a”  a. Probar: 16.1 a  A  a + a = a 

16.2 a  A  a = a 

16.3 a, b  A  a . b + a . b = a 



16.4 a, b  A  a + b = a . b 



16.5 a, b  A  a . b = a + b 16.6 a  A  a + 1A = 1A 

16.7 a, b  A: a . b = a  a . b = 0A 16.8 a, b  A: a  b  a . b = a es una relación de orden amplio en A 16.9 a, b  A: a  b  a + b = b es una relación de orden amplio en A 



16.10 a, b  A si a  b  b  a 



16.11 a, b  A: a  b  a . b = 0A  a + b = 1A 17 Matemática Discreta (1028)

Ingeniería - UNLaM

17- Dado el conjunto A = {a, b, c, d, e} completar la tabla de : A2  A y definir la operación : A2  A para que (A, ,  ) sea una red, indicar justificando adecuadamente si es álgebra de Boole.



a

a

b

c

d

e

b

c

d

e

e

e

e

e

e

b c d

e

e

18-Rellenar la siguiente tabla con los términos o símbolos correspondientes a cada álgebra de Boole concreta Álgebra de Boole abstracta

Álgebra de subconjuntos de U

Circuito en Álgebra de las serie-paralelo proposiciones lógicas

Dn ( n libre de cuadrados)

+ . a 0 1 = 

19- Definir un isomorfismo entre: 19.1 ( D30 ,  ) y ( D42 ,  ) 19.2 ( D6 ,  ) y ( P(A),  ) con A = {a, b} 19.3 B = {e, f, g}; (P(B), , ) y ( D182 , ) 20- Simplificar f: B3  B para cada uno de los siguientes casos: 20.1 f (x1,x2,x3) = x1 x 2 x3  x1 x 2 x3 21.2 f (x1,x2,x3) = x3  x 2  x3  x1 ( x2 x3  x 2 x3 ) 22.3 f (x1,x2,x3) = x1 x3 x2 x2 x3  x1 x 2 x3 21- 21.1 Escribir en la forma normal disyuntiva 21.1.1 f (x1,x2,x3) = x1 + x1 x3 21.1.2 f (x1,x2,x3) = x1 + x3 18 Matemática Discreta (1028)

Ingeniería - UNLaM

21.1.3 f (x1,x2,x3) = x1 x2 21.2 Escribir en la forma normal conjuntiva 21.2.1 f (x1,x2,x3) = x1 x2 21.2.2 f (x1,x2,x3) = x1 + (x1 x2 ) 21.2.3 f (x1,x2,x3) = x1 (x2 + x3 ) 22- Construir el diagrama lógico para las funciones 22.1 f ( x, y, z ) = (x + y ) ( z + x ) 22.2 f ( x, y, z ) = x.( y + z ) 22.3 f (x, y, z ) = x y + ( y + x y ) 23- Dado el siguiente diagrama lógico determinar la función booleana correspondiente: 23.1

23.2

23.3

24-En el lenguaje L = {010, 110, 0100, 0001, 0000111, 1100011, 00000}, se define la siguiente relación de orden: w1  w2  w1 = w2  el número de ceros de w1 es menor al de w2 24.1. Hacer el diagrama de Hasse. Hallar los elementos maximales, minimales, máximo , mínimo, cotas superiores, cotas inferiores, supremo, ínfimo del subconjunto S= {010, 0001, 0100,0000111}. 24.2.¿Es (L,) un orden total ?Justificar. 19 Matemática Discreta (1028)

Ingeniería - UNLaM

24.3. ¿(L,) es red? En caso de no ser red, eliminar la menor cantidad de palabras para que sea red y Álgebra de Boole. Justificar 25-Considerar la red ( D132 , | ) 25.1. Hacer el diagrama de Hasse. Hallar los elementos maximales, minimales, máximo , mínimo, cotas superiores, cotas inferiores, supremo, ínfimo del subconjunto S= {2, 4, 6, 12,22} 25.2. ¿Es ( D132 , | ) un orden total ?Justificar.En el caso de no ser un orden total encontrar uno formado por cuatro elementos o más. 25.3. Indicar los complementos ¿La red ( D132 , | ) es Álgebra de Boole?Justificar 25.4. Resolver o calcular: 11  4; (3  12)  44 ; 4  x = 132

20 Matemática Discreta (1028)

Ingeniería - UNLaM

Trabajo Práctico Nº 7 Grafo – Dígrafo 1-Dibuja las gráficas, especificando el tipo de gráfica que utilizas, que representen las rutas aéreas diarias de Aerolíneas Argentinas sabiendo que ofrece los siguientes vuelos diarios: tres vuelos que unen Buenos Aires y Córdoba, dos entre Córdoba y Mendoza, uno entre Mendoza y Neuquén, cuatro entre Neuquén y La Pampa, uno entre La Pampa y Buenos Aires, uno entre Mendoza y Córdoba y uno entre La Pampa y Córdoba, de modo que: a) Hay una arista conectando cada par de vértices que representan ciudades para las que hay algún vuelo de la una a la otra (en cualquiera de los dos sentidos). b) Hay una arista conectando dos ciudades por cada vuelo que opere entre las dos ciudades ( en cualquiera de los dos sentidos) c) Hay una arista que sale de cada vértice asociado a una ciudad de la que despega algún vuelo y que llega al vértice correspondiente a la ciudad en que aterriza el vuelo. d) Hay una arista por cada vuelo, que sale del vértice que representa a la ciudad en que se inicia el vuelo y llega al vértice que representa a la ciudad en que aterriza. 2- Dibujar un grafo G = (V, A,) con A=a1, a2, a3, a4 , a5, a6, a7V=v1, v2, v3, v4y  dada por X (x)

a1 v1, v2

a2 v1, v2

a3 v4, v1

a4 v4, v2

a5 v2, v3

a6 v2, v4

a7 v3, v4

3-¿Cuáles de los siguientes grafos son simples? Para los grafos no simples, ¿cuál es el menor número de aristas que se deben quitar para hacerlos simples?

4- Hallar la matriz de adyacencia de los siguientes grafos y la función:

21 Matemática Discreta (1028)

Ingeniería - UNLaM

5- Hallar la matriz de adyacencia, la función  y la matriz de incidencia para el siguiente grafo:

6- Hallar el diagrama y la matriz de incidencia para cada uno de los grafos cuyas matrices de adyacencia son: a)

b)

v1 v2 v3 v4 v5 v1 v2 v3 v4 v5

0 1 0 0 1

1 0 1 0 0

0 1 1 1 0

0 0 1 0 1

1 0 0 1 0

v1 v2 v3 v4 v5 v1 v2 v3 v4 v5

0 1 0 0 0

1 0 0 0 0

0 0 0 1 1

0 0 1 0 1

0 0 1 1 1

7- Diagramar los grafos representados por las siguientes matrices de incidencia a)

v1 v2 v3 v4 v5

a

b

c

d

e

f

1 0 1 0 0

0 1 0 1 0

0 1 0 0 1

0 0 1 1 0

0 1 0 0 1

1 0 0 0 1

b)

a v1 1 v2 1 v3 0

b

c

1 0 1

0 1 1

22 Matemática Discreta (1028)

Ingeniería - UNLaM

8- Sea G un grafo a) ¿Qué particularidad tiene G si alguna fila de su matriz de incidencia sólo tiene ceros? b) ¿Cómo se manifiesta esa particularidad en la matriz de adyacencia? c) ¿Puede ocurrir que en una matriz de incidencia haya una columna de ceros?

9- Definir el dígrafo para cada uno de los siguientes diagramas:

10- Dibujar el dígrafo si G si A=a1, a2, a3, a4 , a5, a6, a7V=v1, v2, v3, v4 y  dada por

X (x)

a1 (v2, v4)

a2 (v1, v2)

a3 (v2, v2)

a4 (v1 ,v4)

a5 (v1 ,v3)

a6 (v4, v2)

a7 (v4, v3)

11- Hallar el dígrafo que corresponde a la matriz de incidencia para cada uno de los siguientes casos: A)

v1 v2 v3 v4 v5

a1

a2

a3

a4

a5

a6

1 0 0 0 0

0 1 0 0 0

0 0 -1 1 0

0 0 0 1 -1

0 0 -1 0 1

-1 1 0 0 0

b)

v1 v2 v3 v4

a1

a2

a3

a4

a5

a6

1 0 -1 0

-1 1 0 0

0 1 -1 0

0 -1 0 1

-1 0 0 1

0 0 1 -1

12-¿Cuántas aristas tiene un grafo simple que tiene la siguiente sucesión de grados: (4, 3, 3, 2, 2)? Dibújalo.

23 Matemática Discreta (1028)

Ingeniería - UNLaM

13-¿Existe algún grafo simple de cinco vértices con los grados siguientes?. Si es así, dibuja el grafo correspondiente.a)3, 3, 3, 3,4;b)1, 2, 3, 4,4;c)0, 1, 2, 2,3 14- Determinar el cardinal de V (V) para los siguientes grafos G: a) G tiene nueve aristas y todos los vértices tienen grado 3 b) G es regular con 15 aristas c) G tiene diez aristas con dos vértices de grado 4 y los restantes tienen grado 3 15- Hallar la matriz de adyacencia para el grafo completo de 5 vértices K5 y para el gráfico bipartito completo K2,3. 16-La secretaría Azul de gestión de carreteras se ocupa de la red vial entre 6 municipios, A, B, C, D, E y F, de Buenos Aires.Hay carretera entre A y C, A y E, B y C, B y D, B y F, C y D, C y E, y entre E y D. (a) Dibujar un grafo para modelar esta situación. (b) En una redistribución, la ciudad B junto con las carreteras que la unían con las ciudades de la secretaría Azul pasan a depender de la secretaría Blanca, ¿Qué grafo describiría la nueva situación de la secretaría Azul? (c) Si es C, en lugar de B, quien pasa a depender de la secretaría Blanca ¿qué grafo describiría entonces la nueva situación de la secretaría Azul? (d) Obtener la matriz M de adyacencia del grafo inicial y las matrices M1 y M2 de los subgrafos construidos en los apartados anteriores. 17- Para los grafos de los ejercicios 2) y 10) 







a) G v1 ; G v3 ; G a7 ; G a2 b) Indicar si hay istmos c) Indicar si hay puentes d) Hallar un conjunto desconectante e) Hallar un conjunto de conectividad 18-La matriz M representa las direcciones de circulación de las calles entre 6 plazas A, B, C, D, E y F . (a) El problema se modela usando un dígrafo. ¿Por qué? (b) ¿Hay calles de doble dirección? ¿Cuales? (c) Si se cierra la plaza B por obras, ¿habría que cambiar (o añadir) alguna dirección para poder seguir circulando por las demás calles?

0 1  1 M  0 0  0

0 0  0  1 0 1 0 0 1  0 0 1 0 0

0 0 0 1

1 0 0 0

0 1 1 0

0 1 1 0

19- Para el siguiente grafo G, determinar:

24 Matemática Discreta (1028)

Ingeniería - UNLaM

19-1 camino simple de b a d 19-2 camino no simple de b a d 19-3 ciclo simple de b a b 19-4 ciclo no simple de b a b 19-5 todos los caminos simples de b a f 19-6 Sabiendo que la distancia de x a y en un grafo no dirigido conexo G es la longitud del camino más corto de x a y, hallar la distancia desde d a los restantes vértices de G

20- Para cada uno de los siguientes grafos hallar, si es posible, caminos de Euler, circuitos de Euler, caminos de Hamilton y circuitos de Hamilton

21- a) Dibujar un grafo con un circuito de Euler y un circuito de Hamilton b) Dibujar un grafo que tenga un circuito de Euler y no un circuito de Hamilton c) Dibujar un grafo sin circuito de Euler y con circuito de Hamilton d) Dibujar un grafo sin circuito de Euler y sin circuito de Hamilton 25 Matemática Discreta (1028)

Ingeniería - UNLaM

22- Establecer si los siguientes pares de grafos son isomorfos

26 Matemática Discreta (1028)

Ingeniería - UNLaM