DEPARTAMENTO DE ELÉCTRICA Y ELECTRÓNICA

CARRERA DE INGENIERÍA EN SOFTWARE

Pertenece a:
Fernando Daír Sánchez Gómez

Área de Conocimiento:
Matemáticas Discretas

Docente:
Ing. Luis Guerra MsC
UNIDAD I: Razonamiento y lógica
1.1 Inferencia lógica
1.2 Lógica experimental
1.3 Teorema de incompletes de Kurt Godel
1.4 Algebra de conjuntos
1.5 Sucesiones
1.6 Principio de inducción matemática
1.7 Ejercicios de aplicación
Unidad II: Análisis de algoritmos y recurrencia
2.1 Relaciones binarias
2.2 Base de datos relacionales
2.3 Análisis de algoritmos
2.4 Algoritmos recursivos
2.5 Aplicaciones y ejercicios
UNIDAD III: Teorema de grafos y arboles
3.1 Definición de grafos
3.2 Algoritmos de la ruta mas corta
3.3 Redes de flujo en grafos
3.4 Redes de petri
3.5 Definición de arboles
3.6 Arboles n-arios
3.7Arboles binarios
3.8 Recorridos a través de árbol
3.9 Árboles de juego (Aplicaciones varias)
3.10 jercicios de aplicación
 Concepto de Inferencia lógica

Inferencia.
Es la acción, el acto o proceso de deducir, conclusiones.
Definición de Inferencia.
Proceso por el cual se infiere una conclusión de varias observaciones.
¿De dónde nace la Inferencia?
Nace a partir de una evaluación mental entre distintas expresiones.
Ejemplo:
Inferencia: Justificación de inasistencia.

 Nombre del alumno

 Carrera
 Fecha de solicitud
 Fecha de justificación
 Deberes, trabajos, evaluaciones
 Docente

Condición.- Justificación de una inasistencia.

NACE A PARTIR de una EVALUACIÓN MENTAL entre distintas expresiones, que al ser
relacionadas como abstracciones permiten tatar una IMPLICACIÓN LÓGICA.
Ejemplo.
Expresiones:
1 Autos impactados
2 Daño material
3 Choque de prueba
4 Heridos
5 Muertos IMPLICACIÓN LÓGICA
6 Fugitivos
7 Conductores irresponsables
8 Uno estático otro en movimiento
9 Tipo de colisión

La conclusión. Se suscita como la implicación lógica.

Puede ser Correcto o Incorrecto
Correcto. Dentro de un cierto grado de precisión.
Correcto. En determinadas situaciones.

Colisiones. - Accidente de trafico violento que se produce entre vehículos que se encuentren en
movimiento, o el uno estático y el otro en movimiento.
Distintas Expresiones. (Tipos de Colisiones)
1.- Punto de impacto entre vehículos
2.- La dirección de los vehículos.

EVALUACIÓN MENTAL
Tipos de Puntos de impacto Dirección de los Implicación
Conclusiones
Colisiones de los vehículos vehículos Lógica
Ambos vehículos
Circulando en sentid Accidente de tránsito
Frontales colisionan con su parte
contrario violento.
V
delantera entre si

Fronto- Circulan en la misma

Un vehículo golpea en su Accidente de tránsito
laterales o parte latera a otro
dirección, en sentido
violento.
V
embestidas contrario

Lo vehículos colisionan Circulan en la misma

Accidente de tránsito
Reflejadas entre si dos o más veces dirección, en sentido
violento.
V
sucesivamente contrario

Se producen cuando un
vehículo circula a mayor
Por velocidad que el que le Circulan en la misma Accidente de tránsito
V
alcance procede y golpea con su dirección. violento.
parte frontal con la parte
trasera del otro
 Se producen cuando
Circulan en la misma
existen roces entre los Accidente de tránsito
Por raspón laterales de ambos
dirección, en sentido
violento.
V
contrario
vehículos.

Ejemplos sobre inferencia

Caso 1: Un argumento válido con premisas verdaderas puede llevar a una conclusión verdadera.

 Premisa 1: Por lo general la fruta son dulces.

 Premisa 2: Una manzana es una fruta.
P1 ˄ P2 P1˅P2
V˅V V ˅ V
Caso 2: Un argumento válido con premisas falsas pueden llevar a una conclusión falsa.

 Premisa 1: Las manzanas son frutas

 Premisa 2: Los plátanos son frutas.

POR TANTO, LOS PLATANOS SON FRUTAS

Caso 3: Premisas falsas pueden llevar a una conclusión verdadera.

 Premisa 1: Todas las personas inteligentes son inteligentes.

 Premisa 2: Einstein era inteligente.

POR TANTO, EINSTEIN FUE UN INVESTIGADOR

Caso 4: Premisas falsas pueden llevar a una conclusión falsa.

 Premisa 1: Todas las personas son alemanes.

 Premisa 2: Juan León Mera era alto.

POR TANTO, JUAN LEON MERA ERA ALEMAN

Lógica Proposicional
 En la lógica estudia la formación de proposiciones simples.
 Una lógica proporcional es un sistema formal cuyos elementos más simples
representan proposiciones.

Conectivas Lógicas
Las conectivas lógicas ocupan a la lógica proporcional, incluyen su uso en el lenguaje
natural y los símbolos para representarlos.
 Expresión En
Conectiva Lenguaje Símbolo Ejemplo
Natural
Está lloviendo y
Conjunción y ∧ está nublado.
Está lloviendo o
Disyunción o ∨
está soleado.
Si esta soleado
Condicional Si…entonces →
entonces es de día.
Está nublado si y
Bicondicional Si y solo si ↔ solo si hay nubes
visibles
Negación no ⌐ No está lloviendo
Ni está soleado ni
Negación conjunto Ni…ni ↓
está nublado
Disyunción O bien está soleado
O bien…o bien /
excluyente o bien está nublado

Ejemplos.
P: está lloviendo P: está lloviendo P: está soleado P: está nublado
Q: está nublado Q: está soleado Q: es de día Q: hay nubes
visibles

P∧Q P∨Q P→Q P

↔Q
P∪Q P∩Q

P: está lloviendo P: está soleado P: está soleado

⌐P: no está nublado Q: está nublado Q: está nublado

⌐P P↓Q P / Q

Leyes de la lógica proposicional

Comportamiento de las conectivas lógicas con funciones de verdad.
Conjunción

P Q PQ

V V V
V F F
F V F

F F F

Disyunción

P Q PvQ

V V V
V F V
F V V
F F F

Condicional

P Q P => Q

V V V
V F F
F V V
F F V

Bi-condicional

P Q P <=> Q

V V V
V F F
F V F
F F V
Negación
P -P

V F

F V

Equivalencia lógica y sus leyes

Las leyes del algebra de proposiciones son equivalentes lógicamente que se pueden
desarrollar con el desarrollo de las tablas de verdad.
Equivalencia
pp

Idempotencia
p ∧ p p
p∨pp

Asociativa
p ∨ q ∨ r  (p ∨ q) ∨ r  p ∨ (q V r)
p ∧ q ∧ r  (p ∧ q) ∧ r  p ∧ (q ∧ r)

Conmutativa
p∧q q∧p
p∨qq∨p

Distributiva
p ∧ (q ∨ r)  (p ∧ q) ∨ (p ∧ r)
p ∨ (q ∧ r)  (p ∨ q) ∧ (p ∨ r)

Identidad
p∧FF
p∧Vp
p∨Fp
p ∨ V V

Complemento
p ∧ ¬p  F
P ∨ ¬p  V
¬F  V
¬V  F

Morgan
¬(𝑝 ∧ 𝑞) ≡ ¬𝑝 ∨ ¬𝑞
¬(𝑝 ∨ 𝑞) ≡ ¬𝑝 ∧ ¬𝑞
Absorción
𝑝 ∧ (𝑝 ∨ 𝑞) ≡ 𝑝
𝑝 ∨ (𝑝 ∧ 𝑞) ≡ 𝑝
Condicional simple
𝑝 → 𝑞 ≡ ¬𝑝 ∨ 𝑞
𝑝 → 𝑞 ≡ ¬𝑞 → ¬𝑝
Bicondicional
𝑝 ↔ 𝑞 ≡ (𝑝 → 𝑞) ∧ 𝑞 → 𝑝
Conjunción negativa
𝑝 ↓ 𝑞 ≡ ¬𝑝 ∧ ¬𝑞

Ejemplos:

¬𝒒 → ¬𝒑 ≡ ¬𝒑 ∨ 𝒒
¬(¬𝑞) ∨ (¬𝑝 ) 𝑐𝑜𝑛𝑑𝑖𝑐𝑖𝑜𝑛𝑎𝑙 𝑠𝑖𝑚𝑝𝑙𝑒
(𝑞) ∨ (¬𝑝 ) morgan
¬𝑝 ∨ 𝑞 𝑐𝑜𝑛𝑚𝑢𝑡𝑎𝑡𝑖𝑣𝑎

¬𝒑 ∧ ¬𝒒 ≡ 𝒑 ↓ 𝒒
¬(𝑝 ∧ 𝑞) ≡ 𝑝 ↓ 𝑞 𝑀𝑜𝑟𝑔𝑎𝑛
𝑝↓𝑞≡𝑝↓𝑞 𝑐𝑜𝑛𝑗𝑢𝑛𝑐𝑖𝑜𝑛 𝑛𝑒𝑔𝑎𝑡𝑖𝑣𝑎

¬{(¬𝒑) ∨ (¬𝒒) ∨ ¬𝒒} ≡ 𝒑 ∧ 𝒒

¬{(¬𝑝) ∨ (¬𝑞 ∨ ¬𝑞)} ≡ 𝑝 ∧ 𝑞 𝑎𝑠𝑜𝑐𝑖𝑎𝑡𝑖𝑣𝑎
¬{¬𝑝 ∨ ¬𝑞} ≡ 𝑝 ∧ 𝑞 𝑖𝑑𝑒𝑚𝑝𝑜𝑡𝑒𝑛𝑐𝑖𝑎
𝑝∧𝑞 ≡𝑝∧𝑞 𝑚𝑜𝑟𝑔𝑎𝑛
[¬𝒑 ∨ 𝒒] ∨ [¬𝒒 ∨ ¬𝒑] ≡ 𝑽
¬𝑝 ∨ (𝑞 ∨ ¬𝑞) ∨ ¬𝑝 ≡ 𝑉 𝑎𝑠𝑜𝑐𝑖𝑎𝑡𝑖𝑣𝑎
[¬𝑝 ∨ 𝑉] ∨ ¬𝑝 ≡ 𝑉 𝑐𝑜𝑚𝑝𝑙𝑒𝑚𝑒𝑛𝑡𝑜
[¬𝑝 ∨ ¬𝑝] ∨ (𝑉) ≡ 𝑉 𝑎𝑠𝑜𝑐𝑖𝑎𝑡𝑖𝑣𝑎
¬𝑝 ∨ (𝑉) ≡ 𝑉 𝑖𝑑𝑒𝑚𝑝𝑜𝑡𝑒𝑛𝑐𝑖𝑎
𝑉≡𝑉 𝑖𝑑𝑒𝑛𝑡𝑖𝑑𝑎𝑑

(𝒑 ∨ 𝒒) ∧ ¬𝒑 ≡ ¬𝒑 ∧ 𝒒
(𝑝 ∧ ¬𝑝) ∨ (𝑞 ∧ ¬𝑝) ≡ ¬𝑝 ∧ 𝑞 𝑑𝑖𝑠𝑡𝑟𝑖𝑏𝑢𝑡𝑖𝑣𝑎
𝐹 ∨ (𝑞 ∧ ¬𝑝) ≡ ¬𝑝 ∧ 𝑞 𝑐𝑜𝑚𝑝𝑙𝑒𝑚𝑒𝑛𝑡𝑜
(𝑞 ∧ ¬𝑝) ≡ ¬𝑝 ∧ 𝑞 𝑖𝑑𝑒𝑛𝑡𝑖𝑑𝑎𝑑
(¬𝑝 ∧ 𝑞) ≡ ¬𝑝 ∧ 𝑞 𝑐𝑜𝑛𝑚𝑢𝑡𝑎𝑡𝑖𝑣𝑎

[(~𝒑 ∧ 𝒒) → (𝒓 ∧ ~𝒓)] ∧ ~ ↔ ~𝒒
[(𝑝 ∨ ~𝑞) ∨ (𝑟 ∧ ~𝑟)] ∧ ~𝑞 Condicional Simple
[(𝑝 ∨ ~𝑞) ∨ (𝐹)] ∧ ~𝑞 Complemento
(𝑉) ∧ ~𝑞 Identidad
~𝑞

[(𝒑 ∧ 𝒒) ∨ (𝒑 ∧ ~𝒒) ∨ (~𝒑 ∧ ~𝒒)] ↔ 𝒒 → 𝒑

[𝑝 ∧ (𝑞 ∨ ~𝑞)] ∨ [~𝑝 ∧ ~𝑞] Distributiva
[𝑝 ∧ 𝑉] ∨ [~𝑝 ∧ ~𝑞] Complemento
(𝑝) ∨ (~𝑝 ∧ ~𝑞) Identidad
(𝑝 ∨ ~𝑝) ∧ (𝑝 ∨ ~𝑞) Distributiva
𝑉 ∧ (𝑝 ∨ ~𝑞) Complemento
(𝑝 ∨ ~𝑞) Conmutativa
~𝑞 ∨ 𝑝 Condicional Simple
𝑞→𝑝
(𝒑 ∧ ~𝒑) ∧ [𝒑 ∧ (𝒒 ∨ 𝒑)] ↔ 𝒑
𝑉 ∧ [(𝑝 ∧ 𝑝) ∨ (𝑝 ∧ 𝑞)] Complemento
𝑉 ∧ [𝑝 ∨ (𝑝 ∧ 𝑞)] Idempotencia
𝑝 ∨ (𝑝 ∧ 𝑞) Identidad
𝑝 Absorción

𝒑 → (𝒒 ∧ 𝒓) ↔ (𝒑 → 𝒒) ∧ (𝒑 → 𝒓)
𝑝 ∨ (𝑞 ∨ 𝑟) Condicional Simple
(𝑝 ∨ 𝑞) ∧ (𝑝 ∨ 𝑟) Distributiva
(𝑝 → 𝑞) ∧ (𝑝 → 𝑟) Condicional Simple

~[(𝒑 ∨ 𝒑) ↔ 𝒑] ↔ 𝑭
~[𝑝 ↔ 𝑝] ↔ 𝐹 Idempotencia
~[(𝑝 → 𝑝) ∧ (𝑝 → 𝑝)] Condicional Simple
~[(~𝑝 ∨ 𝑝) ∧ (~𝑝 ∨ 𝑝)] Condicional Simple
~(𝑉 ∧ 𝑉) Complemento
𝐹

[(𝒑 ∨ ~𝒒) ∧ 𝒒] → 𝒑 ↔ 𝑽
[(𝑝 ∧ 𝑞) ∨ (~𝑞 ∧ 𝑞)] → 𝑝 Distributiva
[(𝑝 ∧ 𝑞) ∨ 𝐹] → 𝑝 Complemento
(𝑝 ∧ 𝑞) → 𝑝 Identidad
(~𝑝 ∨ ~𝑞) ∨ 𝑝 Condicional Simple
(~𝑝 ∨ 𝑝) ∨ ~𝑞 Asociativa
𝑉 ∨ ~𝑞 Complemento
𝑉 Identidad
¬[¬(𝒑⋀𝒒) ⟷ ¬𝒒] ∨ 𝒒 ≡ 𝒒
¬[(¬𝑝 ⋁ ¬𝑞) → ¬𝑞] ∨ 𝑞 Condicional Simple
¬[(𝑝⋀𝑞) ⋁ ¬𝑞] ∨ 𝑞 Distributiva
¬[(𝑝 ⋁ 𝑞)⋀(𝑞 ⋁ ¬𝑞)] ∨ 𝑞 Complemento
¬[(𝑝 ⋁ ¬𝑞)⋀(𝑉)] ∨ 𝑞 Identidad
¬[(𝑝 ⋁ ¬𝑞)] ∨ 𝑞 Morgan
(¬𝑝⋀𝑞) ∨ 𝑞 Distributiva
𝑞 Absorción

[(¬𝒑⋀𝒒) ⟷ (𝒓⋀¬𝒓)]⋀¬𝒒 ≡ ¬𝒒
[(¬𝑝⋀𝑞) ⟷ 𝐹]⋀¬𝑞 Complemento
[(¬𝑝⋀𝑞) → 𝐹]⋀[𝐹 → (¬𝑝⋀𝑞)]⋀¬𝑞 Bicondicional
[¬(¬𝑝⋀𝑞) ∨ 𝐹]⋀[¬𝐹 ∨ (¬𝑝⋀𝑞)]⋀¬𝑞 Condicional Simple
[(𝑝 ∨ ¬𝑞) ∨ 𝐹] ∨ [¬𝐹 ∨ (¬𝑝⋀𝑞)]⋀¬𝑞 Morgan
(𝑝 ∨ ¬𝑞) ∨ [¬𝐹 ∨ (¬𝑝⋀𝑞)]⋀¬𝑞 Identidad
(𝑝 ∨ ¬𝑞) ∨ [𝑉 ∨ (¬𝑝⋀𝑞)]⋀¬𝑞 Complemento
(𝑝 ∨ ¬𝑞) ∨ 𝑉⋀¬𝑞 Identidad
𝑉⋀¬𝑞 Identidad
𝑞 Identidad

Reglas de inferencia.
Denominadas también reglas de transformación y su principal característica es que nos
permiten dar conclusiones muy bien formadas y validadas a partir de otras premisas.
Dentro de la injerencia encontraremos reglas en donde las utilizaremos conjuntamente
con las preposiciones. Las reglas de inferencia son argumentos válidos breves que se
utilizan dentro de n argumento más largo como una demostración.
 A → B
A MODUS PONENS
B

A → B
¬A MODUS TOLLENS
¬B

A ˅ B
SILOGISMO
¬A
DISYUNTIVO
B

p → q
SIGOLISMO
q → r
HIPOTETICO
→ r
p

Ejemplos

A: Si estudio apruebo examenes → B: Me va bien en el promedio

A: Si estudio apruebo examenes
B: Me va bien en el promedio

A: Si trabajo cumpliendo un horario → B: Obtengo un salario completo

A: Si trabajo cumpliendo un horario
B: Obtengo un salario completo

A: Si saco malas calificaciones → B: Pierdo el Nivel

¬B: No pierdo el nivel

∴ ¬A: No saque malas calificaciones

A: Si estudio apruebo los examenes → B: Me va bien en el promedio
¬B: No me va bien en el promedio

∴ ¬A: No estudio no apruebo los examenes

A: Es Abril ó B: Es Mayo
¬A: No es Abril
∴ B ∶ Es Mayo

A: Me voy de paseo ó B: Estudio

¬A: No me voy de paseo
∴ B ∶ Estudio

p: Si Luis estudio → q: Aprueba los exámenes

q: Aprueba los exámenes → r: actualiza sus conocimientos
∴ p: Si Luis estudio → r: actualiza sus conocimientos

Modus Ponens
A: Si duermo temprano → B: Me levanto con energía
A: Si duermo temprano
∴ B: Me levanto con energía

A: Si ahorro → B: Me compro lo que quiera

A: Si ahorro
∴ B: Me compro lo que quiera

A: Si hago ejercicio → B: Mi cuerpo se encuentra saludable

A: Si hago ejercicio
∴ B: Mi cuerpo se encuentra saludable
 A: Si utilizo lentes → B: Mejoro mi vista
A: Si utilizo lentes
∴ B: Mejoro mi vista
Modus Tollens
A: Si aprendo las reglas de inferencia → B: Me va bien en el exámen
¬B: No me va bien en el exámen
∴ ¬A: No aprendi las reglas de inferencia

A: Si me porto bien → B: Me premian

¬B: No me premian
¬A: No me porte bien

A: Ella te quiere → B: Es tu novia

¬B: No es tu novia
¬A: Ella no te quiere

A: Si voy de compras → B: Tengo comida

¬B: No tengo comida
¬A: No fui de compras
Silogismo Disyuntivo
A: Hago deberes ⋁ B: Estudio
¬A: No hago deberes
∴ B: Estudio
A: Voy al curso de nivelación ⋁ B: Doy el examen exonera
¬A: No voy al curso de niverlación
∴ B: Doy el examen exonera

A: Se llama Dayane ⋁ B: Se llama Dayana

¬A: No se llama Dayane
∴ B: Se llama Dayana
 A: Es un Landborgini ⋁ B: Es un Ferrary
¬A: No es un Lanfborgini
∴ B: Es un Ferrary
Silogismo Hipotético
p: Si realiza su Tesís → q: Se gradua
q: Se gradua → r: Recibe su título
∴ p: Si realiza sus tesís → r: Recibe su título

p: Si se Java → q: Saco buenas notas

q: Saco buenas notas → r: Apruebo programación II
∴ p: Si se Java → r: Apruebo programación II

p: Si me pongo buso → q: No tengo frío

q: No tengo Frío → r: No me enfermo
∴ p: Si me pongo buso → r: No me enfermo

Cuantificadores

Operadores lógicos y cuantificadores

Predicado: Es una afirmación que expresa una propiedad de un objeto o una relación
entre objetos, estas afirmaciones se hacen verdaderas o falsas cuando se reemplazan las
variables (objetos) por valores específicos.
Ejemplo:
P(x): x es un país de Sudamérica en donde hablan español
Si, x:= Ecuador
.:. Ecuador es un país de Sudamérica en donde hablan español (T)
Si, x:= México
.:. México es un país de Sudamérica en donde hablan español (F)
P(x): x es una asignatura y es consecuente a inteligencia artificial
Si, x:= Matemática discreta
Matemática discreta es una asignatura y es consecuente a inteligencia artificial (T)
Si, x:= Programación
Programación es una asignatura y es consecuente a inteligencia artificial (F)

Predicados y proposiciones
Si p(x1, x2, x3… xn) es un predicado constante con n variables y asignamos los valores
c1, c2, c3… cn a cada una de ellas, el resultado es la proposición p(c1, c2, c3… cn)
Ejemplo:
Si el predicado; p(x,y) : x+y = 5
U es el conjunto de los números enteros

Caso 1:
1) x:= 2
y:= 3
2) p(2,3): 2+3 = 5
3) p(2,3): 5 (T)

Caso 2:
1) x:= 1
y:= 2
2) p(1,2): 1+2 = 3
3) p(1,2): 3 <> 5 (F)

Cuantificadores
1. Universal (∀)
Si p(x) es un predicado cuya variable es x, entonces la afirmación “para todo p(x)”, es
una proposición en la cual se dice que la variable x, está universalmente cuantificada.
La frase: “para todo” se simboliza con ∀, símbolo que recibe el nombre de “cuantificador
universal”, además este cuantificador se lo interpreta también como: “para todo X”, “para
cualquier X”, “para X arbitrario”.
Conclusión: Así pues, para todo x de p(x) se escribe “∀x, p(x)”
Para todo z de p(z) se escribe “∀z, p(z)”.
Cuantificador existencial ∃
Si p(x) es un predicado cuya variable es x, entonces la afirmación “Existe un x tal que
p(x)” es una proposición en la que diremos que la variable x está Existencialmente
cuantificada.
La frase “Existe al menos” : ∃ símbolo que recibe el nombre de cuantificador
existencial, además puede leerse como: “Para algún x, p(x)“, “Existe al menos un x, tal
que p(x)”
Conclusión.
Por lo tanto “existe un x talque p(x)” se escribe “x : p(x)“
Ejercicios con Cuantificador Universal y Existencial
Para todo x, p(x) → " ∀ x, p(x)”
↓
Para cada x
Para cualquier x
Para x arbitrario
Existe un x, tal que p(x) → “∃: p(x)”

Escriba en lógica matemática la siguiente propuesta:

“Todo número es estricto menor que el siguiente”
∀𝑥, 𝑥 < 𝑥 + 1

- Sean p(x, y, z) : xy=z, q(x, y) : x=y , r(x, y) : x>y y sea el Universo del
discurso el conjunto de los números enteros. Transcribir las siguientes
proposiciones a notación lógica.

a. Si y=1, entonces xy=x para cualquier x

∀𝑦, 𝑦 = 1 → 𝑥𝑦 = 𝑥

b. Si xy≠0, entonces x≠0 e y≠0

∀𝑥, 𝑥 ≠ 0 ∧ ∀𝑥, 𝑦 ≠ 0 → ∀𝑥𝑦, 𝑥𝑦 ≠ 0

c. Si xy=0, entonces x=0 o y=0

∀𝑥, 𝑥 = 0 ∨ ∀𝑦, 𝑦 = 0 → ∀𝑥∀𝑦, 𝑥𝑦 = 0

d. 3x=6 Si, y solo si x=2

∀𝑥, 3𝑥 = 6 ↔ 𝑥 = 2
 - Analice en el conjunto de los números enteros el valor de verdad de las
afirmaciones siguientes.

1. ∃𝑥 ∶ 𝑥 < 𝑥 + 1 V
Existe al menos un entero que es menor que el siguiente.

2. ∃𝑥 ∶ 𝑥 = 5 V
Existe un número que es igual a cinco

3. ∃𝑥 ∶ 𝑥 = 𝑥 + 1 F
Existe un entero que es igual al siguiente entero.

Teorema de Conjuntos
Conjunto: Conjunto de elementos con características similares e iguales.
Notación
U= {meses del año}
M= {meses del año}  Notación por tabulación
M={enero, febrero, marzo, abril, mayo, junio, julio, agosto, septiembre, noviembre, diciembre}
 Notación por extensión
M= {m/m ∈ Meses del calendario}  Notación por comprensión / formula

U= {Superhéroes de marvel}
S= {Superhéroes de marvel}  Notación por tabulación
S={sentry, antman, visión, spiderman, wolverin, Stan loor, gamura, drax, iron man} 
Notación por extensión
S= {s/s ∈ Universo cinematográfico de marvel }  Notación por comprensión / formula
U= {números pares de una cifra positiva}
P= {números pares de una cifra positiva}  Notación por tabulación
P= {0, 2, 4, 6, 8}  Notación por extensión
P= {x/x ∈ numero par de una cifra}  Notación por comprensión / formula

Por descripción el conjunto A esta dado por:

A= {x/x ∈ N, x es un digito del número 2014}  Notación por comprensión / formula
A= {números naturales}  Notación por tabulación
A= {0, 1, 2, 4}  Notación por extensión
U= {números impares de una cifra positiva}
A= {1, 3, 5, 7, 9}  Notación por extensión
A= {x/x ∈ N, x es un número impar de una cifra}  Notación por comprensión / formula
A= {números impares de una cifra}  Notación por tabulación

Ejercicios en clase

Universo U {0,1,2,3,4,5,6,7,8,9}
A {0,2,4,5,6}
B {3,4,5,6,7}
C {0,1,7,8,9}

1. A`

A`={1,3,7,8,9}
2. B`

B` = {1,2,8,9}

3. C`
C` ={12,3,4,5,6}

4. A∪B
A∪B= {0,2,3,4,5,6,7}
5. B∪C
B∪C ={0,1,3,4,5,6,7,8,9}

6. 𝐂 ∪ 𝐀
𝐂 ∪ 𝐀 = {𝟎, 𝟏, 𝟐, 𝟒, 𝟓, 𝟔, 𝟕, 𝟖, 𝟗}

7. 𝐀 ∪ U
𝐀 ∪ 𝐔 = {𝟎, 𝟏, 𝟐, 𝟑, 𝟒, 𝟓, 𝟔, 𝟕, 𝟖, 𝟗}
8. 𝐁 ∪ 𝐔
𝐁 ∪ 𝐔 = {𝟎, 𝟏, 𝟐, 𝟑, 𝟒, 𝟓, 𝟔, 𝟕, 𝟖, 𝟗}

9. 𝐁′ ∪ 𝐀
𝐁′ ∪ 𝐀 = {𝟎, 𝟏, 𝟐, 𝟒, 𝟓, 𝟔, 𝟖, 𝟗}

10. 𝐁 ′ ∪ 𝐀
𝐁′ ∪ 𝐀 = {𝟎, 𝟏, 𝟐, 𝟑, 𝟒, 𝟓, 𝟔, 𝟕, 𝟖, 𝟗}
Leyes del Algebra de Conjuntos
1. Idempotencia
A∪A=A
A∩A=A

2. Asociativa
A∪(B∪C) = (A∪B) ∪C
A∩(B∩C) = (A∩B) ∩C

3. Conmutativa
A∪B=B∪A
A∩B=B∩A

4. Distributiva
A∪(B∩C) = (A∪B) ∩(A∪C)
A∩(B∪C) = (A∩B) ∪(A∩C)

5. Identidad
A∪U=U
A∪∅=A

A∩U=A
A∩∅=∅

6. Complemento
A ∪ A’ = U
(A’)’ = A
A ∩ A’ = ∅
U’ = ∅
∅’ = U

7. Leyes de Morgan
(A∪B)’ = A’ ∩ B’
(A∩B)’ = A’ ∪ B’

8. Inversa Distributiva
(A∩C) ∪ (A∩B) = A∩(B∪C)

9. Diferencia
A – B = A ∩ B’
B – A = B ∩ A’

EJERCICIOS:

1. Demostrar que 𝑨 − (𝑩 ∪ 𝑪) = (𝑨 − 𝑩) ∩ (𝑨 − 𝑪)

𝐴 − (𝐵 ∪ 𝐶) = (𝐴 ∩ 𝐵′) ∩ (𝐴 ∩ 𝐶′) *Diferencia

 𝐴 − (𝐵 ∪ 𝐶) = (𝐵′ ∩ 𝐴) ∩ (𝐴 ∩ 𝐶′) *Conmutativa

𝐴 − (𝐵 ∪ 𝐶) = [𝐵′ ∩ (𝐴 ∩ 𝐴) ∩ 𝐶 ′ )] *Asociativa

𝐴 − (𝐵 ∪ 𝐶) = [𝐵′ ∩ 𝐴 ∩ 𝐶′] *Ídem Potencia

𝐴 − (𝐵 ∪ 𝐶) = [𝐴 ∩ 𝐵′ ∩ 𝐶′] *Conmutativa

𝐴 − (𝐵 ∪ 𝐶) = [𝐴 ∩ (𝐵′ ∩ 𝐶 ′ )] *Asociativa

𝐴 − (𝐵 ∪ 𝐶) = [𝐴 ∩ (𝐵 ∪ 𝐶)′] *Morgan

𝐴 − (𝐵 ∪ 𝐶) = [𝐴 − (𝐵 ∪ 𝐶)] l.q.q.d *Diferencia

2. Demostrar que 𝑨 − (𝑩 ∩ 𝑪) = (𝑨 − 𝑩) ∪ (𝑨 − 𝑪)

𝐴 ∩ (𝐵 ∩ 𝐶)′ = (𝐴 − 𝐵) ∪ (𝐴 − 𝐶) *Diferencia

𝐴 ∩ (𝐵′ ∪ 𝐶′) = (𝐴 − 𝐵) ∪ (𝐴 − 𝐶) *Morgan

(𝐴 ∩ 𝐵′) ∪ (𝐴 ∩ 𝐶′) = (𝐴 − 𝐵) ∪ (𝐴 − 𝐶) *Distributiva
(𝐴 − 𝐵) ∪ (𝐴 − 𝐶) = (𝐴 − 𝐵) ∪ (𝐴 − 𝐶) *Distributiva l.q.q.d

3. (𝑨 ∪ 𝑩) − 𝑨 = 𝑩 − 𝑨
(𝐴 ∪ 𝐵) ∩ 𝐴′ = 𝐵 − 𝐴 *Diferencia
(𝐴 ∩ 𝐴′) ∪ (𝐵 ∩ 𝐴′) = 𝐵 − 𝐴 *Distributiva
(∅) ∪ (𝐵 ∩ 𝐴′) = 𝐵 − 𝐴 *Complemento
(𝐵 ∩ 𝐴′) = 𝐵 − 𝐴 *Identidad

𝐵−𝐴=𝐵−𝐴 l.q.q.d *Identidad

4. (𝑨 ∩ 𝑩 ∩ 𝑪) = (𝑨 ∩ 𝑩) − [(𝑨 − 𝑪) ∪ (𝑩 − 𝑪)]
(𝐴 ∩ 𝐵 ∩ 𝐶) = (𝐴 ∩ 𝐵) ∩ [(𝐴 ∩ 𝐶 ′ ) ∪ (𝐵 ∩ 𝐶 ′ )]′ *Diferencia
(𝐴 ∩ 𝐵 ∩ 𝐶) = (𝐴 ∩ 𝐵) ∩ [(𝐴 ∪ 𝐵) ∩ 𝐶 ′ ]′ *Inversa Distributiva
(𝐴 ∩ 𝐵 ∩ 𝐶) = (𝐴 ∩ 𝐵) ∩ [(𝐴 ∪ 𝐵)′ ∪ 𝐶] *Morgan
(𝐴 ∩ 𝐵 ∩ 𝐶) = (𝐴 ∩ 𝐵) ∩ [(𝐴′ ∩ 𝐵′) ∪ 𝐶] *Morgan
(𝐴 ∩ 𝐵 ∩ 𝐶) = [(𝐴 ∩ 𝐵) ∩ (𝐴′ ∩ 𝐵′)] ∪ [(𝐴 ∩ 𝐵) ∩ 𝐶] *Distributiva
(𝐴 ∩ 𝐵 ∩ 𝐶) = [(𝐴 ∩ 𝐴′) ∩ (𝐵 ∩ 𝐵′)] ∪ [(𝐴 ∩ 𝐵) ∩ 𝐶] *Asociativa
(𝐴 ∩ 𝐵 ∩ 𝐶) = [∅ ∩ ∅] ∪ [(𝐴 ∩ 𝐵) ∩ 𝐶] *Complemento
(𝐴 ∩ 𝐵 ∩ 𝐶) = ∅ ∪ [(𝐴 ∩ 𝐵) ∩ 𝐶] *Complemento
(𝐴 ∩ 𝐵 ∩ 𝐶) = 𝐴 ∩ 𝐵 ∩ 𝐶 l.q.q.d *Complemento

5. 𝑯𝟏 = 𝑨 − 𝑩 = 𝑨
𝑯𝟐 = 𝑨 ∩ 𝑩 = ∅
𝐴−𝐵 =𝐴
𝐴 ∩ 𝐵′ = 𝐴 *Diferencia
𝐴 ∩ (𝐵′ ∪ ∅) = 𝐴 *Identidad
(𝐴 ∩ 𝐵′) ∪ (𝐴 ∩ ∅) = 𝐴 *Diferencia

(𝐴 ∩ 𝐵′) ∪ (𝐴 ∩ (𝐴 ∩ 𝐵)) = 𝐴 *Sustitución H1

(𝐴 ∩ 𝐵′) ∪ ((𝐴 ∩ 𝐴) ∩ 𝐵) = 𝐴 *Asociativa

(𝐴 ∩ 𝐵′) ∪ (𝐴 ∩ 𝐵) = 𝐴 *Ídem Potencia

𝐴 ∩ (𝐵′ ∪ 𝐵) = 𝐴 *Inversa Distributiva

𝐴∩𝕌=𝐴 *Complemento

𝐴=𝐴 l.q.q.d *Identidad

PRINCIPIOS DE INCLUSION Y EXCLUSION

Demuestre que la suma de los primeros números n enteros impares positivos en
𝑛2
Hipótesis de Inducción:
Sea:
𝑆𝐾 = 1,3,5,7 … ,2𝑘 − 1
𝑆𝐾 = 1 + 5 + 7 + ⋯ + (2𝑘 − 1) = 𝑘 2
Demostración
𝑆1 → 𝑇𝑟𝑢𝑒
𝑆1 → 𝑆𝑘+1 → 𝑇𝑟𝑢𝑒

𝑆1 = 1 = 12 (𝑇𝑟𝑢𝑒)
𝑆𝐾+1 = 1 + 5 + 7 + ⋯ + (2𝑘 − 1) + (2𝑘 + 1)
𝑆𝐾+1 = 𝑆𝐾 + (2𝑘 + 1)
𝑆𝐾+1 = 𝑘 2 + (2𝑘 + 1)
𝑆𝐾+1 = 𝑘 2 + 2𝑘 + 1
𝑆𝐾+1 = (𝑘 + 1)2
∴ 𝑆𝐾+1 = 𝑛2
𝒏(𝒏+𝟏)(𝟐𝒏+𝟏)
Pruebe por inducción que 𝟏𝟐 + 𝟐𝟐 + ⋯ + 𝒏𝟐 = 𝟔
Hipótesis de Inducción:
 𝑘(𝑘 + 1)(2𝑛 + 1)
𝑆𝐾 = 12 + 22 + ⋯ + 𝑘 2 =
6
Tesis:
𝑆1 → 𝑇𝑟𝑢𝑒

𝑆1 → 𝑆𝑘+1 → 𝑇𝑟𝑢𝑒

Demostración
1(1 + 1)(2 ∗ 1 + 1) 1(2)(3)
𝑆𝐾=1 = 12 = 1 = = = 1 → 𝑇𝑟𝑢𝑒
6 6
𝑆𝐾+1 = 12 + 22 + ⋯ + 𝑘 2 + (𝑘 + 1)2
𝑘(𝑘 + 1)(2𝑘 + 1)
𝑆𝐾+1 = 𝑆𝑘 + (𝑘 + 1)2 = + (𝑘 + 1)2
6
𝑘(𝑘 + 1)(2𝑘 + 1) + 6(𝑘 + 1)2
𝑆𝐾+1 =
6
(𝑘 + 1)[𝑘(2𝑘 + 1) + (𝑘 + 1)]
𝑆𝐾+1 =
6
(𝑘 + 1)(2𝑘 2 + 𝑘 + 6𝑘 + 6)
𝑆𝐾+1 =
6
(𝑘 + 1)(𝑘 + 2)(2𝑘 + 3)
𝑆𝐾+1 =
6
(𝑘 + 1)(𝑘 + 2)(2𝑘 + 2 + 1)
𝑆𝐾+1 =
6
(𝑘 + 1)(𝑘 + 2)[(2𝑘 + 1) + 1]
𝑆𝐾+1 =
6
(𝑘 + 1)(𝑘 + 2)[2(𝑘 + 1) + 1]
𝑆𝐾+1 =
6
(𝑘 + 1)[(𝑘 + 1) + 1][2(𝑘 + 1) + 1]
𝑆𝐾+1 =
6
𝒏(𝒏 + 𝟏)(𝟐𝒏 + 𝟏)
𝑺𝒏 =
𝟔
𝒏(𝒏 + 𝟏)(𝟐𝒏 + 𝟏)
𝟏𝟐 + 𝟐𝟐 + ⋯ + 𝒏 𝟐 =
𝟔

𝒏(𝒏+𝟏)
Pruebe por inducción que 𝟏 + 𝟐 + ⋯ + 𝒏 = 𝟐

Hipótesis de inducción
Sea 𝑆𝑘 = 1 + 2 + ⋯ + 𝑘
𝑛(𝑛 + 1)
𝑆𝑘+1 = 1 + 2 + ⋯ + 𝑘 =
2
Tesis
 𝑆1 = 12 → 𝑇𝑟𝑢𝑒
{
𝑆𝑘 = 𝑆𝑘+1
Demostración
𝑆1 = 12 = 1
1(1 + 1)
𝑆1 =
2
𝑆1 = 12 = 1 → 𝑇𝑟𝑢𝑒

𝑆𝑘+1 = 1 + 2 + ⋯ + 𝑘 + (𝑘 + 1)
𝑆𝑘+1 = 𝑆𝑘 + (𝑘 + 1)
𝑘(𝑘 + 1)
𝑆𝑘+1 = +𝑘+1
2
𝑘(𝑘 + 1) + 2(𝑘 + 1)
𝑆𝑘+1 =
2
𝑘 2 + 𝑘 + 2𝑘 + 2
𝑆𝑘+1 =
2
𝑘 2 + 3𝑘 + 2
𝑆𝑘+1 =
2
(𝑘 + 1)(𝑘 + 2)
𝑆𝑘+1 =
2
(𝑘 + 1)[(𝑘 + 1) + 1]
𝑆𝑘+1 =
2
𝑛(𝑛 + 1)
𝑆𝑛=
2
2. Conteo y relaciones de Recurrencia.
2.1.Métodos de conteo o Técnicas de conteo.

Cuando el número de posibles resultados de un experimento es finito