L gica


MATERIAL DE APOYO PARA ELPRIMER CURSO DE MATEMATICASCOMPUTACIONALES.Ing. HUGO HUMBERTO MORALES PENAMAESTRIA EN ENSENANZA DE LAS MATEMATICAS
Linea de Matematicas Computacionales
UNIVERSIDAD TECNOLOGICA DE PEREIRAFACULTAD DE CIENCIAS BASICASDEPARTAMENTO DE MATEMATICASPereira, Risaralda28 de Julio de 2010
2
Indice general TOC \o "1-3" \h \z Introduction a la logicamatematica7Calculo proposicional7Conectivos proposicionales8Formulas bien formadas9Formulas logicamente equivalentes (FLE)11Tautologia11Leyes de la logica13Utilizando las leyes de la logica proposicional14Conectivo X-OR (0)15Conectivo NOR (^)17Conectivo NAND (^)20Ejercicios 22Reglas de inferencia25Tabla de reglas de inferencia25Utilization de las reglas de inferencia para demostrar la validez
de razonamientos 29Ejercicios 34Logica de predicados 37Cuantificador universal38Cuantificador existencial40Variables ligadas 42Alcance de un cuantificador 42Negaciones y cuantificadores 43Ejercicios 44Sucesiones y sumatorias49Funciones piso y techo492.1.1. Propiedades de las funciones piso y techo49Sucesiones50Sucesiones especiales de numeros 53Sumatorias 572.4.1. Formulas de sumatorias utiles:61Ejercicios 62Tecnicas de demostracion65Tecnica de demostracion directa65Tecnica de demostracion indirecta67Tecnica de demostracion por contra-reciproca67Tecnica de demostracion por contradiction69Tecnica de demostracion por disyuncion de casos 72Tecnica de demostracion por contraejemplo 78Tecnica de demostracion por induction matematica82Ejercicios 94Relaciones de recurrencia974.1. Metodo de Iteration 98Conjuntos115
El conjunto potencia118Producto cartesiano118Operaciones de conjuntos120Identidades en conjuntos123Uniones e intersecciones generalizadas125Ejercicios 125Funciones129
Conceptos fundamentales129Funciones inyectivas (o funciones uno a uno)131Funciones sobreyectivas131Funciones biyectivas 132Funciones inversas y composition de funciones132Grafica de una funcion135Ejercicios 136Relaciones139Relation binaria139Funciones como relaciones140Relaciones en un conjunto140Propiedades de las relaciones142Propiedad de reflexividad 142Propiedad de simetria 143Propiedad de antisimetria143Propiedad de transitividad143Combination de relaciones145Composition y potencia de relaciones145Representation de relaciones1467.7.1. Representation de relaciones utilizando matrices146Ejercicios 150
Relacionesde equivalencia153Clases de equivalencia 155Clases de equivalencia y particiones155Conjuntos parcialmente ordenados157Ejercicios 161Introduccion a la teoria de numeros163Los numeros enteros y la division163Introduccion163Division entre numeros enteros 163El algoritmo de la division entre numeros enteros165Los numeros primos 165Teorema fundamental de la aritmetica 166Procedimiento para generar lafactorization prima de un numeroentero170El maximo comun divisor (MCD)174El minimo comun multiplo(MCM)175El algoritmo de Euclides176Aritmetica modular177Aplicaciones de la aritmetica modular178Asignacion de localizaciones de memoria en el computador ...178Generation de numeros pseudoaleatorios179Criptosistemas basados en aritmetica modular180Representation de los enteros en elcomputador181Representation de numeros enteros en base hexadecimal ....183Cambio de base de un numero entero escrito en base 10183Algoritmo para construir la expansion de n en base b184Algoritmos para operaciones de numeros enteros en base 2 . . .186Ejercicios 191
6
INDICE GENERAL
Capitulo 1Introduction a la logica matematica1.1. Calculo proposicionalDefinition de proposition:Una proposition es un enunciadodeclarativocomo verdadero o falso. En este analisis norequieran una opinion individual y que por loque puede ser calificado sin ambiguedadse tendran en cuenta proposiciones quetanto, no pueden ser verdaderas o falsas.
Las siguientes declaraciones son ejemplos de proposiciones:
Matematicas Discretas es una materia que se evalua en el Examen de Calidadde la Education Superior (ECAES) en el programa...