Unidad 1 Lógica proposicional y razonamientos
1
Proposiciones
Conectivos
Operaciones
Conectivos
Se escribe
Se lee
Negación
¬ ( ∼ )
¬ p No p
Conjunción
p q p y q
Disyunción
p p p o q
Condicional
p q Si p entonces q
Bicondicional
p q p si y sólo si q
Disyunción
Excluyente
p q
O p o q
Tabla de verdad
p q
¬ p p q p q p q p q p q
V V F V V V V F
V F F F V F F V
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
Unidad 1 Lógica proposicional y razonamientos
2
Leyes lógicas
Doble negación
¬ ( ¬ p ) ≡ p
Idempotencia
p p ≡ p
p p ≡ p
Conmutativa
p q ≡ q p
p
q ≡ q
p
Asociativa
(p q) r ≡ p (q r )
(p
q)
r ≡ p
(q
r )
Distributiva
p ( q r ) ≡ ( p q ) ( p r)
p
( q
r ) ≡ ( p
q )
( p
r)
Complementación
p ¬ p ≡ V
p
¬ p
≡
F
Elemento neutro
p F ≡ p
p F ≡ p
Absorbente o dominante
p V ≡ V
p
F ≡ F
Identidad
p F ≡ p
p
V ≡ p
Leyes de De Morgan
¬ ( p q ) ≡ ¬ p ¬ q
¬ ( p
q ) ≡ ¬ p
¬ q
Ley de absorción
p ( p q ) ≡ p
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
Unidad 1 Lógica proposicional y razonamientos
3
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
Silogismo disyuntivo (S.D.)
A B ; ∼ A B
Ley de Combinación (L.C.)
A ; B A B
Particularización universal (P.U.)
x: p(x) p(a)
Generalización universal (G.U.)
p(a) x: p(x)
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)
Unidad 2 Conjuntos e inducción completa
4
Conjuntos
A = { a, e, i, o, u }
A = { x/x es una letra vocal }
Símbolos
Pertenencia aA bA
Vacío = { } = 0
Universal U
Cardinal A = n A = ∞
Inclusión A B x: [ x A x B ]
Propiedades
Básicas
Todo conjunto está incluido en sí mismo
A: A A
Conjunto vacío incluido en todo conj.
A: A
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
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 }
Diagrama de Venn
A
a e i
o u
U
Unidad 2 Conjuntos e inducción completa
5
Propiedades de las operaciones entre conjuntos
Involución
A̅
̅
= A
Conmutatividad
A B = B A
A ∩ B = B ∩ A
Asociatividad
A ( B C ) = ( A B ) C
A ∩ ( B ∩ C ) = ( A ∩ B ) ∩ C
Distributividad
A ( B ∩ C ) = ( A B ) ∩ ( A C )
A ∩ ( B C ) = ( A ∩ B ) ( A ∩ C )
Idempotencia
A A = A
A ∩ A = A
Leyes de De Morgan
A B = A̅ ∩ B
̅
A ∩ B = A̅ B
̅
Elemento neutro
A ∩ U = A
A = A
Absorbente
A U = U
A ∩ =
Absorción
A ∩ ( A B ) = A
A ( A ∩ B ) = A
Equivalencia de la
diferencia
A - B = A ∩ B
̅
Complementación
A ∩ A̅ =
A A̅ = U
Unidad 2 Conjuntos e inducción completa
6
Partición de un conjunto
P(A) = {x/x ⊆ A} Posibles combinaciones: P(A)= 2A
Ej. A = { 1, 2} P(A) = {{}, { 1 }, { 2 }, { A o 1, 2 }} P(2)= 22 = 4
Sea un conjunto A . Sea P = { A1 , A2 , ....., An }
P es una partición de A
1. Ai ≠ i
2. Ai ∩ Aj = i ≠ j
3. U Ai = A
Producto cartesiano
A X B = { (x;y) / x A y B }
Ej. A = { a, b, c } y B = { 1, 2 }
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) }
Principio de inducción
n ℕ: P(n)
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 + 2 + 3 + 4 …
Unidad 3 Métodos de Conteo
7
Principios del conteo
Producto
n
1
.
n
2
.
…
.
n
r
Suma
n
1
+
n
2
+
…
+
n
r
Inclusión-
exclusión
2 conjuntos
│
1
2
│ = │
1
│ + │
2
│ − │
1
∩
2
│
Inclusión-
exclusión
3 conjuntos
│
1
2
3
│=│
1
│+│
2
│+│
3
│−│
1
∩
2
│−│
1
∩
3
│−│
2
∩
3
│+│
1
∩
2
∩
3
│
Inclusión-
exclusión
n conjuntos
│
1
2
…
n
│=
i
−
i j+
i j k− … + (−1)
+1
│
1
∩
2
∩…∩
n
│
Variación, permutación y combinación
Repetición
Elementos
diferentes
Orden Fórmula
Variación
Sin k ≤ n Si
(, ) =
!
( )!
Con k ≤ n.k ≥ n Si
´(, ) =
k
Permutación
Sin k = n Si
() = !
Con k ≥ n Si
12 … =
!
1! 2! … !
Combinación
Sin k ≤ n.k ≥ n No
(
,
)
=
( + 1)!
! ( 1)!
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
8
números combinatorios
1
=
(hay n formas de tomar 1 elemento de un total de n)
0
= 1
(hay 1 sólo subconjunto de 0 elementos: el vacío)
= 1
(hay 1 sólo subconjunto de n elementos: el mismo)
=
(los números complementarios son iguales)
+
1
=
+ 1
(fórmula de adición)
Binomio de newton
(
+
)
=
(
+
)
=
0
+
1
+
2
+
=
!
!
(
)
!
Unidad 4 Divisibilidad en Enteros
9
Conjunto de los números enteros
ℤ = {…, -3,-2,-1,0,1,2,3,4, …}
ℤ = {-x/x ℕ} {0} ℕ
Algoritmo de la división
Divisibilidad
a,b∈ℤ : ab ⇔ ∃ k∈ℤ / b = k.a
Propiedades
Reflexiva
∀ a ∈ a
Transitiva
∀
a, b, c
∈
∧
b
∧
b
c a
c ]
∀ a, b, c ∈ b ∧ ac
a(b + c) ]
∀ a, b ∈ 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 n
1
y n
2
da 1.
Dividendo D
d Divisor
Resto r c Cociente
D = c . d + r
0 ≤ r < │d│
“a” divide a “b” “b” es divisible por “a”
“a” es divisor de “b” “b” es múltiplo de “a”
Unidad 4 Divisibilidad en Enteros
10
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 = p
1
k1
. p
2
k2
. … . p
r
k
r
Mínimo común múltiplo (m.c.m.)
m.c.m. (a;b)= [a;b] = m m∈ℤ
ab
bm
∃ m´∈ ℤ
+
: am´ ∧ bm’ ⇒ mm’
Máximo común divisor (m.c.d.)
m.c.d. (a;b)= (a;b) = d d∈ℤ
+
da
d
b
∃ d´∈ ℤ
+
: d´a ∧ d´b ⇒ d´d
Propiedades
m.c.d (a,b) ⇒ d = k
1
.a + k
2
.b
m.c.d (a,b)
. m.c.m. (a,b) = │a.b│
m.c.d. (a,b) = 1
⇔ Coprimos
Ej.
[64;48] = 2
6
.3=192
• No comunes
• Comunes con máx.
exponente
Ej.
[64;48] = 2
4
=16
• Solo comunes
• Menor exponente
Unidad 4 Divisibilidad en Enteros
11
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,r
1
) siendo b = r.q
1
+ r
1
m.c.d.(r, r
1
) = m.c.d.(r
1
,r
2
) siendo r = r
1
.q
2
+ r
2
m.c.d.(r
n-1
, r
n
) = m.c.d.(r
n
,0) siendo r
n-1
= r
n
.q
n+1
+ 0
m.c.d. (a,b) = r
n
Forma matricial del algoritmo de euclides
m.c.d (720;224) = 16
1
0
720
F
1
0
1
224
F
2
1
-3
48
F
3
= F
1
– 3.F
2
-4
13
32
F
4
= F
2
– 4.F
3
5
-16
16
F
5
= F
3
– F
4
0
F
6
= F
4
– 2.F
5
16 = 5
. 720 +
-16 . 224
Teorema de bezout
a,b ∈ ℤ: m.c.d.(a,b) = 1 ⇔ 1 = s . a + t . b s,t ∈ ℤ
Multiplicar por el resto
Unidad 5 Relaciones y equivalencia
12
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 : y
1
, y
2
∈B : (x;y
1
)∈F ∧(x;y
2
)∈F y
1
= y
2
Clasificación de funciones
• Inyectividad: x
1
,x
2
∈ A, y ∈ B: F(x
1
) = y ∧ F(x
2
) = y x
1
= x
2.
Para todos los x del dominio las imágenes deben ser distintas.
• Sobreyectividad: y ∈ B: ∃ x ∈ A ∧ F(x) = y ⇔Im(F) = B
Todos los elementos del segundo conjunto son imagen de por
lo menos alguno del primero.
•
Biyectividad: F es inyectiva y sobreyectiva.
Producto cartesiano
A, B Conjuntos (a,b) ≠ (b,a)
A x B { (a,b) / a ∈ A, b ∈ B}
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)}
Unidad 5 Relaciones y equivalencia
13
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
Dominio: primer elemento del par ordenado (x).
R: A → B Dom (R) = { x ∈ A / ∃ y ∈ B ∧ (x;y) ∈ R }
Imagen: segundo elemento del par ordenado (y).
R: A → B Im (R) = { y ∈ B / ∃ x ∈ A ∧ (x;y) ∈ R }
Matrices, Diagrama de Venn y Digrafos
Matrices booleanas
Es toda matriz cuyos elementos pertenecen al conjunto { 0, 1 }.
Algunas matrices especiales:
• Cuadrada: n=m.
• Nula: i, j: a
ij
= 0
• Identidad: i, j: i = j a
ij
= 1 yi, j: i ≠ j a
ij
= 0
=
1
2
3
1 1
2 2
3 3
El dígrafo solo se puede
hacer si se trata del
mismo conjunto es
decir R
A
→
A
1 2 3
=
1
2
3
1 0 0
1 0 0
0 1 0
1 2 1 3
3 2
1 2 a
3 b
1
2
3
Unidad 5 Relaciones y equivalencia
14
Relación inversa
R: A → B R
-1
= { (y;x) ∈ B x A / (x;y) ∈ R }
Ejemplo:
R
1
= {(1; a),(2;a),(3;b)} R
1
-1
= {(a; 1),(a;2),(b;3)}
Traspuesta → Mr
T
1 2 3
1 =
1
2
3
1 0
1 0
0 1
1
T
=
1 1 0
0 0 1
Relación complementada
R: A → B = R
c
=R R = { (x;y) ∈ A X B / (x;y) ∉ R } = A X B – R
Son los elementos que están en A x B pero no en la relación.
R
1
= {(1; a),(2;a),(3;b)} R
1
= {(1; b),(2;b),(3;a)}
1 =
1
2
3
1 0
1 0
0 1
1 =
1
2
3
0 1
0 1
1 0
Unión
R: A → B S: A → B
RS = { (x;y) ∈ A X B / (x;y) ∈ R (x;y) ∈ S }
R
1
= {(1; a),(2;a),(3;b)}
R
2
= {(1; a),(3;a)} R
1
R
2
= {(1; a),(2;a),(3;b),(3;a)}
( ó ó)
1
2
3
1 0
1 0
0 1
1
2
3
1 0
0 0
1 0
=
1
2
3
1 0
1 0
1 1
R
1
R
2
= R
1
R
2
0 1
0
1
0 1
1 1
Unidad 5 Relaciones y equivalencia
15
Intersección
R: A → B S: A → B
R
S = { (x;y) ∈ A X B / (x;y) ∈ R (x;y) ∈ S }
R
1
= {(1; a),(2;a),(3;b)}
R
2
= {(1; a),(3;a)} R
1
R
2
= {(1; a)}
( ó ó)
1
2
3
1 0
1 0
0 1
1
2
3
1 0
0 0
1 0
=
1
2
3
1 0
0 0
0 0
R
1
R
2
= R
1
2
Composición de Relaciones
R: A → B S: B → C
S
oR = S
R (X)
]
= { (x;z) ∈ A X C / ∃ y∈B (x;y)∈R (y;z)∈S }
A = {1; 2; 3} B = {a; b} C = {x; y; z}
R
A
→
B
= {(1;a),(1;b),(2;b)}
S
B
→
C
= {(a;y),(b;y),(b;z)} S oR = {(1;y),(1;z),(2;y),(2;z)}
(
)
=
(Producto Matricial Booleano)
0 1
0
1
0 0
0 1
0 1 0
0 1 1
1 1
0 1
0 0
0 1 1
0 1 1
0 0 0
(
)
A B C
R S
x y z
S
o
R
Este documento contiene más páginas...
Descargar Completo
Discreta - Primer Cuatrimestre - Primer año.pdf
Estamos procesando este archivo...
Lamentablemente la previsualización de este archivo no está disponible. De todas maneras puedes descargarlo y ver si te es útil.
Descargar
Estamos procesando este archivo...
Lamentablemente la previsualización de este archivo no está disponible. De todas maneras puedes descargarlo y ver si te es útil.