Matematica discreta

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

´
Indice general
1. L´gica Proposicional
o
1.1. Proposiciones, conectivos, f´rmulas proposicionales
o
1.1.1. Algunos conectivos . . . . . . . . . . . . . .
1.2. F´rmulas proposicionales . . . . . . . . . . . . . .
o
1.3. Algunos comentarios . . . . . . . . . . . . . . . . .
1.4. Valor de verdad deproposiciones compuestas . . . .
1.5. Asignaciones de verdad . . . . . . . . . . . . . . .
1.6. Tablas de Verdad . . . . . . . . . . . . . . . . . . .
1.7. Tautolog´ y contradicciones . . . . . . . . . . . .
ıas
1.8. Consecuencia l´gica . . . . . . . . . . . . . . . . .
o
1.9. Definici´n de consecuencia l´gica . . . . . . . . . .
o
o
1.10. Equivalencia l´gica . . . . . . . . . . . . . . . . ..
o
1.11. Las leyes de la l´gica . . . . . . . . . . . . . . . . .
o
1.12. Reglas de sustituci´n . . . . . . . . . . . . . . . . .
o
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´n . . . . . . . . . . . . . . . . . . . . . . .
o
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´gica de predicados
o
2.1. Definiciones b´sicas . . . . . . . . . . . . . . . . . . . . .
a
2.1.1. Predicados at´micos . . . . . . . . . . . . . . . .
o
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´gica, consecuencia l´gica y equivalencia l´gica
o
o
o
2.2.1. Interpretaciones y valores de verdad . . . . . . .
2.2.2. Proposiciones v´lidas (l´gicamente verdaderas) .
a
o2.2.3. Consecuencia l´gica . . . . . . . . . . . . . . . .
o
2.2.4. Equivalencia l´gica . . . . . . . . . . . . . . . . .
o
2.2.5. Resumen de definiciones . . . . . . . . . . . . . .
2.3. Negaci´n de proposiciones con cuantificadores . . . . . .
o
2.4. Reglas de inferencia usando predicados . . . . . . . . . .
2.5. Teor´ matem´ticas . . . . . . . . . . . . . . . . . . . .
ıas
a
2.6.Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . .

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

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

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

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

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

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

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