Guia de mate discreta

Universidad Central de Venezuela Facultad de Ciencias Escuela de Computaci´n o Centro de C´lculo Cient´ a ıfico y Tecnol´gico o

Nota de Docencia para Matem´ticas Discretas I a

Realizado por: Prof. Marlliny Monsalve L.

´ Ultima Actualizaci´n: Junio de 2008 o

Contenido
1 De qu´ trata la L´gica? e o 2 L´gica proposicional o 2.1 Conexiones l´gicas . . . . . . . o 2.1.1 Negaci´n . . . . .. . . o 2.1.2 Conjunci´n . . . . . . . o 2.1.3 Disyunci´n . . . . . . . o 2.1.4 Condicional . . . . . . . 2.1.5 Bicondicional . . . . . . 2.2 Reglas de formaci´n . . . . . . o 2.2.1 Agrupaci´n y par´ntesis o e 2.3 Traducci´n del lenguaje natural o 3 Equivalencia l´gica o 3.1 Tautolog´ y Contradicci´n . ıa o 3.2 Leyes de equivalencia l´gica . o 3.3 Equivalencia y simplificaci´n o 3.4 Circuitosl´gicos . . . . . . . o 3.4.1 Circuito negaci´n . . . o 3.4.2 Circuito conjunci´n . o 3.4.3 Circuito disjunci´n . . o 4 5 7 7 8 9 10 12 13 14 15 18 18 19 22 25 25 26 26 29 29 30 32 33 34 35 36 37

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . al lenguaje de la L´gica o

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . .. . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

4 Implicaci´n l´gica o o 4.1 Argumentaci´n l´gica . . . . . . . . . . . . . . . o o 4.1.1 Argumentos v´lidos . . . . . . . . . . . . a 4.1.2 Argumentos inv´lidos . . . . . . . . . . . a 4.2 Reglas de inferencia l´gica . . . . . . . . . . . . . o 4.3 M´todos para probarla validez de un argumento e 4.3.1 Prueba por tablas de verdad . . . . . . . 4.3.2 Prueba por equivalencias l´gicas . . . . . o 4.3.3 Prueba por argumentaci´n directa . . . . o

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

1

4.4

4.3.4 Pruebacondicional . . . . . . . . . . . . . . . . . . . . . . . 4.3.5 Prueba por reducci´n al absurdo . . . . . . . . . . . . . . . o Consistencia e inconsistencia de premisas . . . . . . . . . . . . . .

39 44 46 49 50 52 52 53 56 59 59 59 60 60 61 69 72 72 74 79 79 82 90 94

5 L´gica de predicados o 5.1 Predicados . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Cuantificadores . . . . . . . .. . . . . . . . . . . . . . . 5.2.1 Cuantificador universal . . . . . . . . . . . . . . 5.2.2 Cuantificador existencial . . . . . . . . . . . . . . 5.3 Simbolizaci´n . . . . . . . . . . . . . . . . . . . . . . . . o 5.4 Reglas de particularizaci´n y generalizaci´n . . . . . . . o o 5.4.1 Reglas para el cuantificador universal . . . . . . 5.4.2 Reglas para el cuantificador universal . . . . . . 5.5Equivalencias e implicaciones l´gicas con cuantificadores o 5.6 Argumentaci´n l´gica . . . . . . . . . . . . . . . . . . . o o 5.6.1 Argumentos v´lidos . . . . . . . . . . . . . . . . a 5.6.2 Argumentos inv´lidos . . . . . . . . . . . . . . . a 6 Teor´ de conjuntos ıa 6.1 Conceptos b´sicos . . . . . . . . . . . a 6.2 Inclusi´n e igualdad de conjuntos . . . o 6.3 Conjunto de partes . . . . . . . . . .. 6.4 Operaciones entre conjuntos . . . . . . 6.4.1 Leyes en la teor´ de conjuntos ıa 6.5 Conjunto de indices . . . . . . . . . . 6.6 Producto cartesiano . . . . . . . . . . 7 Herramientas para la 7.1 Potenciaci´n . . . o 7.2 Inecuaciones . . . . 7.3 Sumatoria . . . . . 7.4 Productoria . . . . inducci´n o . . . . . . . . . . . . . . . . . . . . . . . . . . . .

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

. ....