Matematicas discretas

mate discretas3.1 Lógica de Predicados
La lógica de predicados es un lenguaje mas de la matematicas. Sin menospreciar otrs sistemas de lógica que se han estudiado, algunos por razones filosoficas y otros por la importancia de sus aplicaciones, incluyendo las ciencias de la computación.
En las ciencias de la computación, sabemos que muchas cosas pueden ser codificadas en bits y esto justificala restriccion de la lógica boleana(dos valores).En ocasiones es conveniente hacer referencia directamente a tres ó mas 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 con un valor {$ X $} en la suma de de verdadero y falso. La definición de losoperadores se extiende a los nuevos valores, por ejemplo, {$ X $} y verdadero = {$ X $}.
EJEMPLO: Consideremos las 2 sentencias, “1 < 2″ y “Esta 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: ‘Para todas ocasiones de t, el valor “1 < 2″ en la ocasion t, es verdadero’ y‘Para algunas ocasiones de t, el valor de “Esta lloviendo”, en la ocasion t es verdadero’.

Lógica de predicados
La lógica de predicados es un lenguaje formal donde las sentencias bien formadas son producidas por las reglas enunciadas a continuación.
Vocabulario
Un vocabulario es una tupla: que consta de:
* r símbolos relacionales Ri, cada uno de ellos con un número entero ai asociado, elcual se conoce como la aridad de Ri
* s símbolos funcionales fj, cada uno de aridad bj
* t símbolos constantes ck
Una fórmula de primer orden en el vocabulario τ, es una fórmula de primer orden donde los únicos predicados, funciones y constantes empleados son los especificados por τ.
Lenguajes y estructuras de primer orden
Un lenguaje de primer orden' es una colección de distintossímbolos clasificados como sigue:
1. El símbolo de igualdad' ; las conectivas , ; el cuantificador universal y el paréntesis , .
2. Un conjunto contable de símbolos de variable .
3. Un conjunto de símbolos de constante .
4. Un conjunto de símbolos de función .
5. Un conjunto de símbolos de relación .
Así, para especificar un orden, generalmente sólo hace falta especificar lacolección de símbolos constantes, símbolos de función y símbolos relacionales, dado que el primer conjunto de símbolos es estándar. Los paréntesis tienen como único propósito de agrupar símbolos y no forman parte de la estructura de las funciones y relaciones.
Los símbolos carecen de significado por sí solos. Sin embargo, a este lenguaje podemos dotarlo de una semántica apropiada.
Una -estructura sobreel lenguaje , es una tupla consistente en un conjunto no vacío , el universo del discurso, junto a:
1. Para cada símbolo constante de , tenemos un elemento .
2. Para cada símbolo de function -aria de , una function -aria .
3. Para cada símbolo de relación -aria de , una relación -aria sobre , esto es, un subconjunto .
A menudo, usaremos la palabra modelo para denotar esta estructura.Cuantificador
los cuantificadores son símbolos utilizados para indicar cuántos elementos de un conjunto dado cumplen con cierta propiedad. Existen muchos tipos de cuantificadores, pero quizás los más estudiados y utilizados sean:
* Cuantificador universal

Para todo x, y...
* Cuantificador existencial

Existe al menos un x, y...
* Cuantificador existencial único

Existeexactamente un x, y...
* Negación del cuantificador existencial

No existe ningún x, y...

Declaraciones cuantificadas
Las declaraciones cuantificadas se escriben en la forma:
*
Para todo x que pertenece a R, se cumple que 2x pertenece a R.
*
Para todo a que pertenece a R, existe x que pertenece a R, que esta comprendido entre a y a+1.
*
Para todo a que pertenece a R...