Matematicas discretas

INDICE LOGICA DE PREDICADOS CUANTIFICADORES REPRESENTACION Y EVALUACION DE PREDICADOS ALGEBRA DECLARATIVA INDUCCION MATEMATICA APLICACIONES DE LOGICA MATEMATICA EN LA COMPUTACION INTRODUCCION

Ejemplo 1

Todas las flores son rojas. Esta margarita es una flor. Luego esta margarita es roja. Ejemplo 2 Aldo sabe que el asesino de Juan huye herido. Pedro Fernandez es el asesino de Juan. Luego,Aldo sabe que Pedro Fernandez huye herido. Ejemplo 3 Todos los A son B. c es un A. Luego c es un B.

LOGICA DE PREDICADOS
La lógica de predicados es un lenguaje más de las matemáticas. Sin menospreciar otros sistemas de lógica que se han estudiado, algunos por razones filosóficas y otros por la importancia de sus aplicaciones, incluyendo las ciencias de la computación. En las ciencias de lacomputación, sabemos que muchas cosas pueden ser codificadas en bits y esto justifica la restricción de la lógica booleana (dos valores).En ocasiones es conveniente hacer referencia directamente a tres ó más valores discretos. Por ejemplo una compuerta lógica puede estar en un estado indeterminado antes de basarse en un nivel estable de voltaje. Esto puede ser formalizado en tres valores lógicos conun valor {$ X $} en la suma de de verdadero y falso. La definición de los operadores se extiende a los nuevos valores, por ejemplo, {$ X $} y verdadero = {$ X $}. EJEMPLO: Consideremos las 2 sentencias, “1 < 2″ y “Está lloviendo”. La primera sentencia siempre es verdadera mientras que la segunda es verdadera solo en algunas ocasiones. Esto puede ser expresado en el cálculo de predicados como: ‘Paratodas ocasiones de t, el valor “1 < 2″ en la ocasión t, es verdadero’ y ‘Para algunas ocasiones de t, el valor de “Esta lloviendo”, en la ocasión t es verdadero’.

CUANTIFICADORES
Cuantificador Universal. El cuantificador universal para todo asociado a una expresión de cálculo de predicados F se representa por la expresión (∀ x) F y es verdadera cuando todas las instancias de la fórmula sonverdaderas al sustituir la variable x en la fórmula por cada uno de los valores posibles del dominio. Así por ejemplo si tenemos que la fórmula es T(x) donde T representa “es alumno del ITT” y x representa un alumno de Tijuana, la fórmula (∀ x) T(x) es falsa pues sabemos que hay alumnos en Tijuana que no son del ITT. Cuantificador Existencial. El cuantificador existencial al menos uno o existe unoasociado a una expresión de cálculo de predicados F se representa por la expresión (∃ x) F y es verdadera cuando por lo menos una instancia de la fórmula es verdadera al sustituir por la variable x uno de los valores posibles del dominio. Así por ejemplo en el mismo caso del anterior la expresión (∃ x) T(x) es verdadera pues sabemos que sí es verdad que al menos un estudiante es alumno del ITT.Hay expresiones dentro del español que son muy utilizadas como por ejemplo, Todos los alumnos son estudiosos, Todos los hombres son mortales o Todos los alumnos de Computación estudian lógica. En este caso estamos tomando una parte del dominio para establecer un característica universal, esto se puede hacer mediante la combinación de dos predicados de una variable conectados mediante una condicionaly tomando el cuantificador universal. Así por ejemplo: Todos los alumnos son estudiosos se puede representar mediante (∀ X) (A(x) → E(x)) donde el predicado A significa alumno, E estudioso y x es un elemento de un dominio general que podría ser el de las personas o cualquier subconjunto deseado. Por ejemplo podrían ser todas las personas que viven en Tijuana. Aquí podemos ver claramente que eldominio juega un papel preponderante, ya que en un conjunto todos los alumnos podrían ser estudiosos y si cambiamos el conjunto puede ser que ya no sea verdad. Todos los hombres son mortales se puede representar por (∀ x) (H(x) → M(x)) donde H es hombre y M el predicado mortal.

Todos los pericos son verdes es: (∀ x) (P(x) → V(x)) con P, perico y V verde. A una expresión como las anteriores se...