Apuntes Disset

Apuntes de clase — Matem´atica Discreta
Luis Dissett
Segundo Semestre, 2004

´Indice general
1. L´
ogica Proposicional
1.1. Proposiciones, conectivos, f´ormulas proposicionales
1.1.1. Algunos conectivos . . . . . . . . . . . . . .
1.2. F´
ormulas proposicionales . . . . . . . . . . . . . .
1.3. Algunos comentarios . . . . . . . . . . . . . . . . .
1.4. Valor de verdad de proposicionescompuestas . . . .
1.5. Asignaciones de verdad . . . . . . . . . . . . . . .
1.6. Tablas de Verdad . . . . . . . . . . . . . . . . . . .
1.7. Tautolog´ıas y contradicciones . . . . . . . . . . . .
1.8. Consecuencia l´
ogica . . . . . . . . . . . . . . . . .
1.9. Definici´
on de consecuencia l´ogica . . . . . . . . . .
1.10. Equivalencia l´
ogica . . . . . . . . . . . . . . . . . .
1.11. Las leyes de lal´
ogica . . . . . . . . . . . . . . . . .
1.12. Reglas de sustituci´
on . . . . . . . . . . . . . . . . .
1.13. El principio de dualidad . . . . . . . . . . . . . . .
1.14. Formas Normales . . . . . . . . . . . . . . . . . . .
1.15. Reglas de inferencia . . . . . . . . . . . . . . . . .
1.16. Las reglas . . . . . . . . . . . . . . . . . . . . . . .
1.17. Sistemas deductivos . . . . . . . . . . . .. . . . .
1.18. Ejemplo de uso de las reglas . . . . . . . . . . . . .
1.19. Otro ejemplo . . . . . . . . . . . . . . . . . . . . .
1.20. Resoluci´
on . . . . . . . . . . . . . . . . . . . . . . .
1.21. Ejercicios . . . . . . . . . . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

..
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

1
1
1
1
2
2
2
3
3
3
4
4
5
6
6
6
7
7
9
9
10
10
11

2. L´
ogica de predicados
2.1. Definiciones b´
asicas . . . . . . . . . . . . . . . . . . . . .
2.1.1. Predicados at´
omicos . . . . . . . . . . . . . . . .
2.1.2. Variables, constantes, funciones y operaciones. .
2.1.3. Interpretaciones y dominios . . . . . . . . . . . .
2.1.4. Cuantificadores . . . . . . . . . . . . . . . . . . .
2.1.5. Variables libres y ligadas . . . . . . . . . . . . .
2.2. Verdad l´
ogica, consecuencia l´ogica y equivalencia l´ogica
2.2.1. Interpretaciones y valores de verdad . . . . . . .
2.2.2. Proposiciones v´alidas (l´ogicamente verdaderas) .
2.2.3. Consecuencia l´ogica . .. . . . . . . . . . . . . .
2.2.4. Equivalencia l´
ogica . . . . . . . . . . . . . . . . .
2.2.5. Resumen de definiciones . . . . . . . . . . . . . .
2.3. Negaci´
on de proposiciones con cuantificadores . . . . . .
2.4. Reglas de inferencia usando predicados . . . . . . . . . .
2.5. Teor´ıas matem´
aticas . . . . . . . . . . . . . . . . . . . .
2.6. Ejercicios . . . . . . . . . . . . . . . . . .. . . . . . . .

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
..
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

13
13
13
13
13
14
14
14
14
14
15
15
17
17
17
17
18

i

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

´INDICE GENERAL

´INDICE GENERAL

3. Teor´ıa de Conjuntos
3.1. Definiciones b´
asicas . . . . . . . . . . . . . . .
3.1.1. Nociones primitivas . . . . . . . . . .
3.1.2....