3.1.1 Relaciones y Predicados
Los axiomas y teoremas de matematicas son definidos en conjuntos arbitrarios tales como el conjunto de enteros Z. Para escribir y manipular las formulas lógicas que contienen relaciones sobre los valores de los conjuntos arbitrarios. El cálculo de predicados abarca el cálculo propósicional con letras de predicados que son interpretados como relaciones sobre un dominio.
Sea
la n-ésima relacion en un dominio
, dado que,
es subconjunto de
.
EJEMPLOS:
es el conjunto de los numeros primos: {2, 3, 5, 11…} .
es del conjunto de pares
dado que
: {(0,0,(1,1),(2,4),(3,9)…}.
Definición: Una relacion se represanta por una valor boleano en función de R:
→{ T,F }, por mapear el
-ésimo elemento de T si y solo si es uncluida en la relación:
EJEMPLO: Sq y Pr son representados por por la funciones Pr y Sq, respectivamente:
| Pr(0) = F | Pr(1) = F | Pr(2) = V | … |
| Sq(0,0)=F | Sq(0,1)=F | Sq(0,2)=F | … |
| Sq(1,0)=F | Sq(1,1)=F | Sq(1,2)=F | … |
| Sq(2,0)=F | Sq(2,1)=F | Sq(2,2)=F | … |
| … | … | … | … |
Esta correspondencia es trivial porque nos da el enlace para la formalizacion de matematicas lógicas. Toda la lógica de la mecanica de formulas, interpretaciones, ejemplos, etc. que manejamos ne le calculo proposicional puede ser manejado en la lógica de predicados. La presencia de un dominio sobre cualquier predicado es considerablemente complicado interpretar los detalles de su mecanica, pero no sus conceptos básicos.
El siguiente es un repaso de su desarrollo:
*Sintaxis: Las letras en predicados son usadas para representar relaciones( Funciones de un dominio para valores verdaderos). Los cuantificadores permiten una expresion puramente sintáctica de la sentencia dado que la recion representada por un predicado es verdadera para algunos o todos los elementos de el dominio.
*Semantica: Una interpretación consiste en un dominio y una asignacion de relaciones para las letras del predicado. La semantica de los operadores bolenos permanece igual, pero en la evaluación de valores verdaderos deben tomarse en cuenta los cuantificadores.
*Tableaux Semantico: La semantica buscada por un modelo es potencialmente infinita por que los dominios enteros son infinitos. La construcción de un Tableaux podria no terminar, este no es un procedimiento desicivo de satisfacibilidad en el calculo de predicados. Sin embargo, si un tableaux se cierra(termina)la formula no es satisfascible; Inversamente un tableaux semantico de una formula insatisfascible estara cerrada.
La sintaxis de el cálculo de predicados se extiende de la función que son interpretadas como funciones de un dominio. Con la funciones podemos razonas sobre la operaciones matematicas. por ejemplo, ( X > 0 ∧Y > 0) →( X.Y>0 ). El cálculo de predicados con las letras de la función es usado en el procedimiento de resolucion se usa en la Programación Lógica.
Las interpretaciones canónicas llamadas Interpretaciones de Herbrand. Si una formula tiene un modelo, ese modelo es una interpretación de Herbrand, de tal manera que para checar si es satisfascible, es suficiente con checar si es un modelo de herbrand para la formula.
