CALCULO DE PREDICADOS

ELEMENTOS BÁSICOS

El cálculo de predicados difiere del cálculo proposicional en que en él se habla de objetos o elementos en un dominio. Para predicar sobre elementos se introducirá variables. En otras palabras, aquí las fórmulas atómicas no son tan solo variables proposicionales, como lo eran en el cálculo de proposiciones, sino que ahora han de ser relaciones en un dominio fijo. Entremos en detalles técnicos un poco más adelante.

Un alfabeto  propio para una teoría de primer orden es la unión de los siguientes conjuntos de símbolos:

Símbolos especiales

SE= {(,)}

Conectivos lógicos

CL= { ⌐, v, Ʌ, →, ↔}

Cuantificadores

Q= {ӈ, ᴲ}. El símbolo ӈ se lee ``para todo'' y se dice ser el cuantificador universal y el símbolo ᴲ se lee ``existe'' y se dice ser el cuantificador existencial.

Variables

Var= {x₀, x1, x₂,…}

Símbolos constantes

Cte= {c₀, c1, c₂,…}

Símbolos de relaciones

Rel= {Rⁱ_j }^i>1 _j>0

.

Símbolos de funciones

Fun= {Fⁱ_j }^i>1 _j>0

.

.

Los conjuntos de constantes, de relaciones y de funciones han de ser finitos. La unión de ellos Sig=Cte U Rel U Fun  se dice ser la signatura de la teoría. Los superíndices  en los símbolos de relación o de función denotan a su respectiva aridad, es decir, al número de argumentos o de plazas que involucran.

Así, se tiene que todo alfabeto para una teoría de primer orden queda prácticamente determinado por su signatura. De hecho la unión de los otros conjuntos de símbolos, SL=SE U Q  U Var  es común a todos los alfabetos de teorías de primer orden. El alfabeto con signatura vacía, L₀= SL se dice ser el alfabeto del cálculo de predicados puro. Veamos algunos ejemplos de alfabetos.

OTRAS FUENTES: CALCULO DE PREDICADOS

REPRESENTACION

Sintaxis en el cálculo de predicados

 

Aquí se maneja la siguiente simbología.

- variables x, y, z

- funciones f, g, h

- constantes a, b, c

-Símbolo de predicado P, Q, R, S, T

-Símbolos de puntación "(", ")", ","

Aunado a estos símbolos se utilizan los siguientes conceptos.

-UNIVERSO: El cual identifica a la totalidad de los valores que puede tomar una variable.

-TERMINO: Una variable es un término, así como f(t) donde f es una función y T es una secuencia de uno o mas términos: Ejem. f(x), h(y), g( x,y,h(x) ), x, y,z, f( h(x,y), y(z,f(z) )

-FORMULA ATOMATICA: Una formula automática es un predicado p(x), donde P es el nombre del predicado y X es un término. Ejem. Es-verde (limón) mamífero (Pedro) mamífero (ballena, delfín, cobras)

-LITERAL: Los literales son predicados o negaciones de predicados. Ejemp. Mamífero (Pedro) ~ mamífero (vidrio)

- FORMULAS BIEN FORMADAS (WFF): Una WFF es una secuencias de formulas Atómicas ( o predicados) concatenados por medio de operadores lógicos. Ejem. P(x) v Q(y) ^ ~R(S) P(x) ^ Q(z) ==> ~R(s) mamífero(perro)=>tiene_sangre_caliente (perro).

-SENTECE: Las expresiones son wff donde el alcance de las variables esta perfectamente bien definido mediante cuantificadores o bien UNIVERSALES ó bien existenciales.

Símbolos Definición

·         V Para todo(cuantificador Universal)

·         E Existe(Cuantificadores Existencial)

·         E equivale a ~V No existe

Ejemplo:

·         Todo mamífero tiene sangre caliente

·         V mamífero(x) => tiene_sangre_caliente (x)

Todos los hijos tienen un padre y una Madre

V hijo(x) => E madre (y)^ padre(z)

-CLAUSULA: Es una disyunción de literales (una cláusula es una disyunción de predicados y/o predicados negados.

Ejemplos.

·         Conjunción equivale a And ( ^ )

·         Disyunción equivale o or (v)

El cálculo de predicado podemos entenderlo mejor en este mapa conceptual.

UNIFICACION

Por ejemplo en Lógica Proposicional la contradicción es evidente porque Estudia (Belén) ^¬ Estudia (Belén).

Pero en Cálculo de Predicados es diferente porque si tengo:
Estudia(x) ^ ¬Estudia (y). No hay contradicción [Belén/ x, Alberto/y]  Estudia (Belén) ^¬ Estudia (Belén).  

P(a) y P(x) no son comparables, para que lo sean, se debe encontrar una substitución para x que haga ambas fórmulas idénticas. Este proceso de encontrar una sustitución para hacer fórmulas idénticas  se conoce como unificación. Lo que se puede sustituir en una fbf para permitir el paramiento de dos fórmulas son las variables por términos.

Variable (Símbolos de constantes, Símbolos de variables, expresiones funcionales) 

 

Sustitución

• La sustitución de variables por términos generales se remite a variables libres. En las ocurrencias ligadas sólo podemos hacer un cambio de variables por variables y no sucede nada
• La sustitución se debe hacer para todas las ocurrencias libres o para ninguna
• Hay que cuidar que una variable libre no se convierta en ligada por la sustitución.

RESOLUCION

Resolución en Lógica Proposicional

Sea ф la conclusión,  Σ el conjunto de los argumentos:

1. Convertir todas las proposiciones en Σ a su forma de cláusulas 2. Negar ф y convertir el resultado en cláusula. Agregar la o las cláusulas resultantes al conjunto de cláusulas obtenidas en 1
3. Hasta encontrar una contradicción o no se pueda seguir avanzando:

• Seleccionar dos cláusulas que tienen como literales una L y la otra ¬L
• Resolverlas juntas. El resolvente será la disyunción de todos los literales que contienen los padres excepto L y ¬L
• Si el resolvente es la cláusula vacía, es que se ha encontrado una contradicción. Si no lo es agregarla al conjunto de cláusulas disponibles.

Resolución en Lógica de Predicados

1. Convertir todas las expresiones de Σ a Cláusulas 2. Negar ф y convertir el resultado en cláusula  y agregarlo al conjunto obtenido en 1
3. Repetir hasta encontrar una contradicción o no se pueda seguir:

a) Seleccionar cláusulas padres
b) Si existe un par de literales L1 y L2, uno en cada cláusula padre, tal que L1 y ¬L2 sean unificables, entonces obtener el resolvente mediante:

• La disyunción de los literales de ambas cláusulas padres excepto L1 y L2
• Usar la sustitución que unifica L1 y ¬L2 para crear el resolvente
• Si existe más de un par de literales complementarios, sólo se elimina uno

c) Si el resolvente es la cláusula vacía, se ha encontrado contradicción, sino agregarla al conjunto de cláusulas.