Discreta - Primer Cuatrimestre - Primer Ano

Unidad 1 Lógica proposicional y razonamientos
Proposiciones
Conectivos
Operaciones Conectivos Se escribe Se lee
Negación ¬(∼) ¬p No p
Conjunción ∧ p∧q pyq
OM
Disyunción ∨ p∨p poq
Condicional ⇒ p⇒q Si p entonces q
Bicondicional ⇔ p⇔q p si y sólo si q
Disyunción
Excluyente
.C ∨̲ p ∨̲ q Opoq
DD
Tabla de verdad
p q ¬p p∧q p∨q p⇒q p⇔q p ∨̲ q
LA
V V F V V V V F
V F F F V F F V
FI
F V V F V V F V
F F V F F V V F

Fortaleza de conectivos
¬ es el más débil
∧∨ Son igualmente fuertes
⇒ y ⇔ Son más fuertes que ∧∨
Clasificación
Contingencia → Resultado mixto
Tautología → Todo verdadero
Falacia o contradicción → Todo falso
Este archivo fue descargado de https://filadd.com

Leyes lógicas
Doble negación ¬(¬p)≡p
p∧p≡p
Idempotencia
p∨p≡p
p∧q≡q∧p
Conmutativa
p∨q≡q∨p
OM
(p ∧ q) ∧ r ≡ p ∧ (q ∧ r )
Asociativa
(p ∨ q) ∨ r ≡ p ∨ (q ∨ r )
p ∨ ( q ∧ r ) ≡ ( p ∨ q ) ∧ ( p ∨ r)
Distributiva
p ∧ ( q ∨ r ) ≡ ( p ∧ q ) ∨ ( p ∧ r)
.C
Complementación
p∨¬p≡V
p∧¬p≡F
DD
p∨F≡p
Elemento neutro
p∧F≡p
p∨V≡V
Absorbente o dominante
p∧F≡F
LA
p∨F≡p
Identidad
p∧V≡p
¬(p∨q)≡¬p∧¬q
FI
Leyes de De Morgan
¬(p∧q)≡¬p∨¬q
p∨(p∧q)≡p
Ley de absorción
p∧(p∨q)≡p

Bicondicional p⇔q≡(p⇒q)∧(q⇒p)
Condicional p⇒q≡(¬p)∨q
Simplificación p∧q⇒p≡V
Adición p⇒p∨q≡V

Reglas de Inferencia
Modus Ponens (M.P.) A⇒B;A∴B
Modus Tollens (M.T.) A⇒B;∼B∴∼A
Silogismo hipotético (S.H.) A⇒B;B⇒C∴A⇒C
OM
Silogismo disyuntivo (S.D.) A∨B;∼A∴B
Ley de Combinación (L.C.) A;B∴A∧B
.C
Particularización universal (P.U.)
Generalización universal (G.U.)

∀ x: p(x) ∴ p(a)
p(a) ∴ ∀ x: p(x)
DD
Nota: si a es genérico
Particularización existencial (P.E.) ∃ x: p(x) ∴ p(a)
Generalización existencial (G.E.) p(a) ∴ ∃ x: p(x)

LA
FI


Unidad 2 Conjuntos e inducción completa
Diagrama de Venn
Conjuntos A
a e i
A = { a, e, i, o, u } o u
A = { x/x es una letra vocal }
Símbolos
Pertenencia a∈A b∉A
OM
Vacío ∅={} ⎪∅⎪ = 0
U
Universal U
Cardinal ⎪A⎪ = n ⎪A⎪ = ∞
Inclusión A ⊆ B ⇔ ∀x: [ x ∈ A ⇒ x ∈ B ]
Propiedades
.C
DD
Básicas
Todo conjunto está incluido en sí mismo ∀ A: A ⊆ A
Conjunto vacío incluido en todo conj. ∀ A: ∅ ⊆ A

LA
Todo conjunto incluido en el Universal ∀ A: A ⊆ U
Propiedad Transitiva ∀ A, B, C: A ⊆ B ∧ B ⊆ C ⇒ A ⊆ C
∀ A, B: A ⊆ B ∧ B ⊆ C ⇒ A = B
FI
De igualdad
Reflexiva ∀ A: A = A

Simétrica ∀ A, B: A = B ⇒ B = C
Transitiva ∀ A, B, C: A = B ∧ B = C ⇒ A = C
Unión A∪B={x/x∈A∨x∈B}
Intersección A∩B={x/x∈A∧x∈B}
Diferencia A-B={x/x∈A∧x∉B}
Diferencia ∆ A ∆ B = { x / x ∈ A ∨ x ∈ B} = (A ∪ B) - (A ∩ B) = (A - B) ∪ (B - A)
Complemento A̅ = U - A = { x / x ∈ U ∧ x ∉ A } = { x ∉ A }

Propiedades de las operaciones entre conjuntos
Involución A̅̅ = A
A∪B=B∪A
Conmutatividad
A∩B=B∩A
OM
A∪(B∪C)=(A∪B)∪C
Asociatividad
A∩(B∩C)=(A∩B)∩C
A∪(B∩C)=(A∪B)∩(A∪C)
Distributividad
A∩(B∪C)=(A∩B)∪(A∩C)
.C
Idempotencia
A∪A=A
A∩A=A
DD
A ∪ B = A̅ ∩ B̅
Leyes de De Morgan
A ∩ B = A̅ ∪ B̅
LA
A∩U=A
Elemento neutro
A∪∅=A
A∪U=U
Absorbente
FI
A∩∅=∅
A∩(A∪B)=A
Absorción
A∪(A∩B)=A

Equivalencia de la
A - B = A ∩ B̅
diferencia
A ∩ A̅ = ∅
Complementación
A ∪ A̅ = U

Partición de un conjunto
P(A) = {x/x ⊆ A} Posibles combinaciones: ⎪P(A)⎪= 2⎪A⎪
Ej. A = { 1, 2} P(A) = {{∅}, { 1 }, { 2 }, { A o 1, 2 }} ⎪P(2)⎪= 2⎪2⎪ = 4
Sea un conjunto A . Sea P = { A1 , A2 , ....., An }
P es una partición de A
1. Ai ≠ ∅ ∀i
OM
2. Ai ∩ Aj = ∅ ∀i≠j
3. U Ai = A
Producto cartesiano
Ej. .C A X B = { (x;y) / x A y B }
A = { a, b, c } y B = { 1, 2 }
DD
A X B = {(a;1), (a;2), (b;1), (b;2), (c;1), (c;2) }
B X A = {(1;a), (2;a), (1;b), (2;b), (1;c), (2;c) }

LA
Principio de inducción
∀ n ∈ ℕ: P(n)
FI
Paso inductivo: PI) v [ P( 1 ) ] = V
Hipótesis inductiva: HI) v [ P( h ) ] = V

Tesis inductiva: TI) v [ P( h + 1 ) ] = V
Sumatoria
∑𝑛𝑛𝑖𝑖=1 𝑖𝑖 1 + 2 + 3 + 4 …

Unidad 3 Métodos de Conteo
Principios del conteo

Producto n1 . n2 . … . nr
Suma n1 + n2 + … + nr
Inclusión-
exclusión │𝐴𝐴1 ∪ 𝐴𝐴2│ = │𝐴𝐴1│ + │𝐴𝐴2│ − │𝐴𝐴1 ∩ 𝐴𝐴2│
2 conjuntos
Inclusión-
OM
exclusión │𝐴𝐴1∪𝐴𝐴2∪𝐴𝐴3│=│𝐴𝐴1│+│𝐴𝐴2│+│𝐴𝐴3│−│𝐴𝐴1∩𝐴𝐴2│−│𝐴𝐴1∩𝐴𝐴3│−│𝐴𝐴2∩𝐴𝐴3│+│𝐴𝐴1∩𝐴𝐴2∩𝐴𝐴3│
3 conjuntos
Inclusión-
exclusión │𝐴𝐴1∪𝐴𝐴2∪…∪𝐴𝐴n│= ∑ni=1 │Ai│−∑ │Ai ∩ Aj│+∑ │Ai ∩ Aj ∩ Ak│− … + (−1) 𝑛𝑛+1│𝐴𝐴1∩𝐴𝐴2∩…∩𝐴𝐴n│
n conjuntos
.C
Variación, permutación y combinación
Elementos
DD
Repetición Orden Fórmula
diferentes
𝑛𝑛!
Sin k≤n Si 𝑉𝑉(𝑛𝑛, 𝑘𝑘) =
(𝑛𝑛 − 𝑘𝑘)!
Variación
Con k ≤ n.k ≥ n Si 𝑉𝑉´(𝑛𝑛, 𝑘𝑘) = 𝑛𝑛k
LA
Sin k=n Si 𝑃𝑃(𝑛𝑛) = 𝑛𝑛!

Permutación 𝑛𝑛!
Con k≥n Si 𝑃𝑃𝑘𝑘1𝑘𝑘2 … 𝑘𝑘𝑛𝑛 =
FI
𝑘𝑘1! 𝑘𝑘2! … 𝑘𝑘𝑛𝑛!

(𝑛𝑛 + ℎ − 1)!
Sin k ≤ n.k ≥ n No 𝐶𝐶 (𝑛𝑛, 𝑘𝑘 ) =
𝑘𝑘! (𝑛𝑛 − 1)!
Combinación

𝑛𝑛!
Con k≤n No 𝐶𝐶´(𝑛𝑛, 𝑘𝑘) =
𝑘𝑘! (𝑛𝑛 − 𝑘𝑘)!
Diferencia entre permutaciones, variaciones y combinaciones

● Cuando los elementos son los mismos y lo único que cambia es el
ORDEN de ellos, estamos ante PERMUTACIONES.
● Cuando lo que diferencia una muestra de otra son los elementos que la
forman o el orden de los mismos, estamos ante VARIACIONES.
● Cuando lo que diferencia una muestra de otra son únicamente los
elementos que la forman (el orden de los mismos no importa), estamos
antes COMBINACIONES.

Unidad 3 Métodos de Conteo
números combinatorios
𝑛𝑛
� � = 𝑛𝑛 (hay n formas de tomar 1 elemento de un total de n)
1
�
𝑛𝑛 � = 1 (hay 1 sólo subconjunto de 0 elementos: el vacío)
0
𝑛𝑛 � = 1
� (hay 1 sólo subconjunto de n elementos: el mismo)
𝑛𝑛
𝑛𝑛 𝑛𝑛
OM
� �=�
𝑛𝑛 − ℎ �
(los números complementarios son iguales)
ℎ
𝑛𝑛
� �+�
𝑛𝑛 � = �𝑛𝑛 + 1� (fórmula de adición)
ℎ ℎ−1 ℎ
Binomio de newton
.C 𝑛𝑛
𝑛𝑛
(𝑎𝑎 + 𝑏𝑏)𝑛𝑛 = � � � 𝑎𝑎𝑛𝑛−𝑘𝑘 𝑏𝑏 𝑘𝑘
𝑘𝑘
DD
𝑘𝑘=0
𝑛𝑛 𝑛𝑛 𝑛𝑛 𝑛𝑛
(𝑎𝑎 + 𝑏𝑏 )𝑛𝑛 = � � 𝑎𝑎𝑛𝑛−0 𝑏𝑏 0 + � � 𝑎𝑎𝑛𝑛−1 𝑏𝑏 1 + � � 𝑎𝑎𝑛𝑛−2 𝑏𝑏 2 + � � 𝑎𝑎𝑛𝑛−𝑛𝑛 𝑏𝑏 𝑛𝑛
0 1 2 𝑛𝑛
LA
𝑛𝑛 𝑛𝑛!
� �=
ℎ ℎ! (𝑛𝑛 − ℎ)!
FI


Unidad 4 Divisibilidad en Enteros
Conjunto de los números enteros

ℤ = {…, -3,-2,-1,0,1,2,3,4, …}
ℤ = {-x/x ∈ ℕ} ∪ {0} ∪ ℕ
Algoritmo de la división
OM
Dividendo D d Divisor D=c.d+r
Resto r c Cociente 0 ≤ r < │d│
Divisibilidad
.C a,b∈ℤ : ab ⇔ ∃ k∈ℤ / b = k.a

DD
“a” divide a “b” “b” es divisible por “a”
“a” es divisor de “b” “b” es múltiplo de “a”
Propiedades
LA
Reflexiva ∀ a ∈ ℤ, a ≠ 0: aa
Transitiva ∀ a, b, c ∈ ℤ , a ≠ 0 ∧ b ≠ 0: [ ab ∧ bc ⇒ ac ]

FI
∀ a, b, c ∈ ℤ, a ≠ 0: [ ab ∧ ac ⇒ a(b + c) ]
∀ a, b ∈ ℤ, a ≠ 0 : [ ab ∧ c ∈ ℤ ⇒ a( b . c ) ]

Números primos y coprimos

Primos
• 1 < n.
• Sólo son divisibles por 1 y n.
• p | a . b ∧ p: primo ⇒ p | a ∨ p | b
coprimos
El m.c.d. entre n1 y n2 da 1.

Teorema fundamental de la aritmética

Todo número entero mayor que 1 es o bien primo o se puede escribir
como producto de factores primos de manera única salvo el orden.
N = p1k1 . p2k2. … . prkr
Mínimo común múltiplo (m.c.m.)
OM
m.c.m. (a;b)= [a;b] = m m∈ℤ Ej.
[64;48] = 26.3=192
 ab
• No comunes
 bm • Comunes con máx.
 ∃ m´∈ ℤ+ : am´ ∧ bm’ ⇒ mm’
.C
exponente
DD
Máximo común divisor (m.c.d.)
m.c.d. (a;b)= (a;b) = d d∈ℤ+ Ej.
[64;48] = 24=16
 da • Solo comunes
LA
 db • Menor exponente

 ∃ d´∈ ℤ+ : d´a ∧ d´b ⇒ d´d
Propiedades
FI
 m.c.d (a,b) ⇒ d = k1.a + k2.b

 m.c.d (a,b) . m.c.m. (a,b) = │a.b│
 m.c.d. (a,b) = 1 ⇔ Coprimos

10

Algoritmo de Euclides
Propiedad: a,b ∈ ℤ/m.c.d.(a,b) = m.c.d.(b,r)
m.c.d.(a,b) = m.c.d.(b,r) siendo a = b.q + r
m.c.d.(b,r) = m.c.d.(r,r1 ) siendo b = r.q1 + r1
m.c.d.(r, r1 ) = m.c.d.(r1 ,r2 ) siendo r = r1.q2 + r2
OM
m.c.d.(rn-1 , rn ) = m.c.d.(rn ,0) siendo rn-1 = rn.qn+1 + 0
m.c.d. (a,b) = rn
Forma matricial del algoritmo de euclides
.C m.c.d (720;224) = 16
DD
1 0 720 F1
0 1 224 F2
1 -3 48 F3 = F1 – 3.F2
-4 13 32 F4 = F2 – 4.F3
LA
5 -16 16 F5 = F3 – F4
0 F6 = F4 – 2.F5
16 = 5 . 720 + -16 . 224 Multiplicar por el resto

FI
Teorema de bezout

a,b ∈ ℤ: m.c.d.(a,b) = 1 ⇔ 1 = s . a + t . b s,t ∈ ℤ
11

Unidad 5 Relaciones y equivalencia
Función
F: A → B. (x;y) ∈ F se puede denotar como y = F(x).
F es función si cumple con:
 Existencia: ∀x∈A : ∃ y∈B : (x;y)∈F

 Unicidad: ∀x∈A : ∀y1, y2∈B : (x;y1)∈F ∧฀(x;y2)∈F ⇒฀y1 = y2
Clasificación de funciones
OM
• Inyectividad: ∀ x1,x2 ∈ A, ∀ y ∈ B: F(x1) = y ∧ F(x2) = y ⇒ x1= x2.
Para todos los x del dominio las imágenes deben ser distintas.
• Sobreyectividad: ∀ y ∈ B: ∃ x ∈ A ∧ F(x) = y ⇔฀Im(F) = B
.C
Todos los elementos del segundo conjunto son imagen de por
lo menos alguno del primero.
DD
• Biyectividad: F es inyectiva y sobreyectiva.
Producto cartesiano
LA
A, B Conjuntos (a,b) ≠ (b,a)
A x B { (a,b) / a ∈ A, b ∈ B}
FI
Ej.
A ={x, y, z} B = {1, 2}
A x B = {(x;1),(x;2),(y;1),(y;2),(z;1),(z;2)}

B x A = {(1;x),(1;y),(1;z),(2;x),(2;y),(2;z)}
12

Relaciones
Para indicar que R es una relación de A en B (o sea si R ⊆ A X B ) se
escribe:
R:A→B
Siendo A el conjunto de partida y B el conjunto de llegada.
Dominio e imagen
OM
Dominio: primer elemento del par ordenado (x).
R: A → B Dom (R) = { x ∈ A / ∃ y ∈ B ∧ (x;y) ∈ R }
.C
Imagen: segundo elemento del par ordenado (y).
R: A → B Im (R) = { y ∈ B / ∃ x ∈ A ∧ (x;y) ∈ R }
DD
Matrices, Diagrama de Venn y Digrafos
𝑎𝑎 𝑏𝑏 El dígrafo solo se puede
⬚
1 𝑎𝑎1 𝑏𝑏1 1 2 a hacer si se trata del
LA
𝑀𝑀𝑀𝑀 = 2 �𝑎𝑎2 𝑏𝑏2� mismo conjunto es

3 b
3 𝑎𝑎3 𝑏𝑏3
decir R A → A
1 2 3
1 1 0 0 ⬚
FI
1 2 1 3
𝑀𝑀𝑀𝑀 = 2 �1 0 0� 1 2
3 2
3 0 1 0 3

Matrices booleanas
Es toda matriz cuyos elementos pertenecen al conjunto { 0, 1 }.
Algunas matrices especiales:

• Cuadrada: n=m.
• Nula: ∀i, ∀j: aij= 0
• Identidad: ∀i, ∀j: i = j aij= 1 y฀∀i, ∀j: i ≠ j aij= 0
13

Relación inversa
R: A → B R-1 = { (y;x) ∈ B x A / (x;y) ∈ R }
Ejemplo:
R1 = {(1; a),(2;a),(3;b)} ⇒ R1-1 = {(a; 1),(a;2),(b;3)}
Traspuesta → MrT
𝑎𝑎 𝑏𝑏
OM
1 2 3
1 1 0 𝑎𝑎
𝑀𝑀𝑀𝑀1 = 2 �1 0� ⇒ 𝑀𝑀𝑀𝑀1T =
𝑏𝑏
�
1 1 0
0 0 1
�
3 0 1
.C
Relación complementada
R: A → B = Rc =R R = { (x;y) ∈ A X B / (x;y) ∉ R } = A X B – R
DD
Son los elementos que están en A x B pero no en la relación.
R1 = {(1; a),(2;a),(3;b)} ⇒ R1 = {(1; b),(2;b),(3;a)}
𝑎𝑎 𝑏𝑏 𝑎𝑎 𝑏𝑏
1 1 0 1 0 1
LA
𝑀𝑀𝑀𝑀1 = 2 �1 0� ⇒ 𝑀𝑀𝑀𝑀𝑀1 = 2 �0 1�
3 0 1 3 1 0
Unión
FI
R: A → B S: A → B
R∪S = { (x;y) ∈ A X B / (x;y) ∈ R ∨ (x;y) ∈ S }

R1 = {(1; a),(2;a),(3;b)}
R2 = {(1; a),(3;a)} ⇒ R1∪R2 = {(1; a),(2;a),(3;b),(3;a)}
(𝑆𝑆𝑆𝑆𝑆𝑆𝑎𝑎 𝑙𝑙ó𝑔𝑔𝑖𝑖𝑔𝑔𝑎𝑎 𝑜𝑜 𝑑𝑑𝑖𝑖𝑑𝑑𝑑𝑑𝑆𝑆𝑛𝑛𝑔𝑔𝑖𝑖ó𝑛𝑛)

𝑎𝑎 𝑏𝑏 𝑎𝑎 𝑏𝑏 𝑎𝑎 𝑏𝑏
1 1 0 1 1 0 1 1 0 ∨ 0 1
2 � 1 0� ∨ 2 �0 0� = 2 �1 0� 0 0 1
3 0 1 3 1 0 3 1 1 1 1 1
𝑀𝑀R1 ∨ 𝑀𝑀R2 = 𝑀𝑀R1∪R2
14

Intersección
R: A → B S: A → B
R∩S = { (x;y) ∈ A X B / (x;y) ∈ R ∧ (x;y) ∈ S }
R1 = {(1; a),(2;a),(3;b)}
R2 = {(1; a),(3;a)} ⇒ R1∩R2 = {(1; a)}
(𝑃𝑃𝑀𝑀𝑜𝑜𝑑𝑑𝑆𝑆𝑔𝑔𝑃𝑃𝑜𝑜 𝑙𝑙ó𝑔𝑔𝑖𝑖𝑔𝑔𝑜𝑜 𝑜𝑜 𝑔𝑔𝑜𝑜𝑛𝑛𝑐𝑐𝑆𝑆𝑛𝑛𝑔𝑔𝑖𝑖ó𝑛𝑛)
OM
𝑎𝑎 𝑏𝑏 𝑎𝑎 𝑏𝑏 𝑎𝑎 𝑏𝑏
1 1 0 1 1 0 1 1 0 ∧ 0 1
2 �1 0� ∧ 2 �0 0� = 2 � 0 0� 0 0 0
3 0 1 3 1 0 3 0 0 1 0 1
𝑀𝑀R1 ∧ 𝑀𝑀R2 = 𝑀𝑀R1∩R2
.C
Composición de Relaciones
R: A → B S: B → C
DD
SoR = S[R (X)] = { (x;z) ∈ A X C / ∃ y∈B ∧ (x;y)∈R ∧ (y;z)∈S }
A R B S C
LA
x y z
SoR
FI
A = {1; 2; 3} B = {a; b} C = {x; y; z}

RA → B = {(1;a),(1;b),(2;b)}
SB → C = {(a;y),(b;y),(b;z)} ⇒ SoR = {(1;y),(1;z),(2;y),(2;z)}

𝑀𝑀(𝑆𝑆𝑜𝑜𝑆𝑆) = 𝑀𝑀𝑀𝑀 ʘ 𝑀𝑀𝑑𝑑 (Producto Matricial Booleano)

0 1 0
𝑀𝑀𝑑𝑑
0 1 1
1 1 0 1 1
𝑀𝑀𝑀𝑀 0 1 0 1 1 𝑀𝑀(𝑆𝑆𝑜𝑜𝑆𝑆)
0 0 0 0 0
15

PROPIEDADES DE LAS MATRICES BOOLEANAS

Igualdad A,B ∈ {0,1}nxm: A < B ⇔ aij < bij ∀i, ∀j
Relación de menor o igual A,B ∈ {0,1}nxm: A ≤ B ⇔ aij ≤ bij ∀i, ∀j
A∨A=A
Idempotencia
A∧A=A
A∨B=B∨A
Conmutatividad
OM
A∧B=B∨A
A∨( B ∨ C)= (A∨ B) ∨ C
Asociatividad A∧( B ∧ C)= (A∧ B) ∧ C
A.(B.C)=(A.B).C
A∨ ( B∧C )= (A∨B )∧ ( A∨C )
Distributividad
A∧( B ∨ C)= (A∧ B) ∨( A∧C )
.C
PROPIEDADES DE LAS RELACIONES BINARIAS. RA→A
DD
Relaciones Matrices
Reflexiva ∀ a ∈ A: (a;a) ∈ R I ≤ M(R)

LA
A-Reflexiva ∀ a ∈ A: (a;a) ∉ R I ∧ M(R) = N
Simétrica ∀ a,b ∈ A: (a;b) ∈ R ⇒ (b;a) ∈ R M(R) = M(R)t

FI
Antisimétrica ∀ a,b ∈ A: (a;b) ∈ R ∧ (b;a) ∈ R ⇒ a=b M(R) ∧ M(R) t ≤ I
A-simétrica ∀ a,b ∈ A: (a;b) ∈ R ⇒ (b;a) ∉ R M(R) ∧ M(R) t = N

Transitiva ∀ a,b,c ∈ A: (a;b)∈R ∧ (b;c)∈R ⇒ (a;c)∈R M(R) . M(R) ≤ M(R)
A-transitiva ∀ a,b,c ∈ A: (a;b)∈R ∧ (b;c)∈R ⇒ (a;c)∉R
16

Relación de conectividad
X Rn y ⇔ existe un camino de longitud n entre x e y.
Conectividad: x R∞ y ⇔ existe un camino de cualquier longitud entre x e y.
R∞= R ∪ R2 ∪ R3 ∪ R4 ∪ ... ∪ Rn ∪ ...
Relación de equivalencia
OM
Se representa con el
R : A → A es de equivalencia si es Reflexiva
Simétrica símbolo “∼”
Transitiva
Clase de equivalencia
.C
Sea (A ; ∼)
Propiedades:
a = [ a ] = Cl(a) = { x ∈ A / x ∼ a }
DD
→ ∀ a ∈ A: cl(a) ≠ ∅
→ a ∈ cl(b) ⇒ b ∈ cl(a)
→ ∀ a,b ∈ A: cl(a) = cl(b) ∨ cl(a) ∩ cl(b) = ∅.
Conjunto cociente
LA
Formado por un
Se lee “Conjunto A partido Sea (A ; ∼) representante de cada
por la relación ∼ “. Porque clase, se denomina
A/∼ = { Cl(a) / a ∈ I }
el conjunto queda CONJUNTO DE INDICES.
FI
particionado en las clases.
Teorema fundamental de las relaciones de equivalencia

Podemos decir que en cualquier conjunto A, hay tantas relaciones de

equivalencia como particiones posibles. Son dos conceptos equivalentes.
Relación de equivalencia ⇔ Partición del conjunto (Visto U2)
Congruencia módulo n
a R b se denota a ≡ b(n) n∈ℕ Se lee “a es congruente con b módulo x”
ℤ: a ≡ b(n) ⇔ na – b ⇔ a – b = k.n ∧ k∈ ℕ

Conjunto cociente: ℤn= {0, 1̅, 2, … , n−̅1 }
Clases: x = { y ∈ ℤ/ y = n.k + x con k ∈ ℤ}
17

Discreta - Primer Cuatrimestre - Primer Ano

Cargado por

Copyright:

Formatos disponibles

Discreta - Primer Cuatrimestre - Primer Ano

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Discreta - Primer Cuatrimestre - Primer Ano

Cargado por

Copyright:

Formatos disponibles

Unidad 1 Lógica proposicional y razonamientos

Conjunción ∧ p∧q pyq

Condicional ⇒ p⇒q Si p entonces q

Bicondicional ⇔ p⇔q p si y sólo si q

Este archivo fue descargado de https://filadd.com

Este archivo fue descargado de https://filadd.com

Modus Tollens (M.T.) A⇒B;∼B∴∼A

Silogismo hipotético (S.H.) A⇒B;B⇒C∴A⇒C

Ley de Combinación (L.C.) A;B∴A∧B

Generalización universal (G.U.)

Particularización existencial (P.E.) ∃ x: p(x) ∴ p(a)

Generalización existencial (G.E.) p(a) ∴ ∃ x: p(x)

Este archivo fue descargado de https://filadd.com

A = { x/x es una letra vocal }

Conjunto vacío incluido en todo conj. ∀ A: ∅ ⊆ A

Todo conjunto incluido en el Universal ∀ A: A ⊆ U

Este archivo fue descargado de https://filadd.com

Propiedades de las operaciones entre conjuntos

Este archivo fue descargado de https://filadd.com

Ej. A = { 1, 2} P(A) = {{∅}, { 1 }, { 2 }, { A o 1, 2 }} ⎪P(2)⎪= 2⎪2⎪ = 4

Sea un conjunto A . Sea P = { A1 , A2 , ....., An }

B X A = {(1;a), (2;a), (1;b), (2;b), (1;c), (2;c) }

Paso inductivo: PI) v [ P( 1 ) ] = V

Hipótesis inductiva: HI) v [ P( h ) ] = V

Tesis inductiva: TI) v [ P( h + 1 ) ] = V

Este archivo fue descargado de https://filadd.com

Principios del conteo

Sin k=n Si 𝑃𝑃(𝑛𝑛) = 𝑛𝑛!

𝑘𝑘1! 𝑘𝑘2! … 𝑘𝑘𝑛𝑛!

Diferencia entre permutaciones, variaciones y combinaciones

Este archivo fue descargado de https://filadd.com

Este archivo fue descargado de https://filadd.com

Conjunto de los números enteros

.C a,b∈ℤ : ab ⇔ ∃ k∈ℤ / b = k.a

Transitiva ∀ a, b, c ∈ ℤ , a ≠ 0 ∧ b ≠ 0: [ ab ∧ bc ⇒ ac ]

∀ a, b, c ∈ ℤ, a ≠ 0: [ ab ∧ ac ⇒ a(b + c) ]

Números primos y coprimos

Este archivo fue descargado de https://filadd.com

Teorema fundamental de la aritmética

N = p1k1 . p2k2. … . prkr

Mínimo común múltiplo (m.c.m.)

 db • Menor exponente

 m.c.d (a,b) ⇒ d = k1.a + k2.b

Este archivo fue descargado de https://filadd.com

m.c.d.(a,b) = m.c.d.(b,r) siendo a = b.q + r

m.c.d.(b,r) = m.c.d.(r,r1 ) siendo b = r.q1 + r1

m.c.d.(r, r1 ) = m.c.d.(r1 ,r2 ) siendo r = r1.q2 + r2

Forma matricial del algoritmo de euclides

16 = 5 . 720 + -16 . 224 Multiplicar por el resto

a,b ∈ ℤ: m.c.d.(a,b) = 1 ⇔ 1 = s . a + t . b s,t ∈ ℤ

Este archivo fue descargado de https://filadd.com

F es función si cumple con:

 Existencia: ∀x∈A : ∃ y∈B : (x;y)∈F

• Sobreyectividad: ∀ y ∈ B: ∃ x ∈ A ∧ F(x) = y ⇔฀Im(F) = B

A, B Conjuntos (a,b) ≠ (b,a)

Este archivo fue descargado de https://filadd.com

Siendo A el conjunto de partida y B el conjunto de llegada.

R: A → B Dom (R) = { x ∈ A / ∃ y ∈ B ∧ (x;y) ∈ R }

𝑀𝑀𝑀𝑀 = 2 �𝑎𝑎2 𝑏𝑏2� mismo conjunto es