Cálculo de predicados
| ||||||
Cálculo de predicados. En los cálculos de predicados se tienen elementos más simples para formar las expresiones atómicas, a diferencia de una proposición simple donde su valor es verdadero o falso de acuerdo a una interpretación.
Sumario
Definición
En el cálculo de predicados el valor de verdad depende de los componentes que forman el predicado. Por ejemplo: Pedro es padre de Idalia es una expresión en cálculo de predicados, que en general podría ser: x es padre de y, o simplemente p(x,y).
En otras palabras, se tiene aquí una proposición abierta que depende de dos variables, y que por supuesto el valor de verdad depende de los valores que se le dan a las variables, porque por ejemplo: Frank es padre de Lisbeth puede tener un valor de verdad diferente al anterior.
En general, se puede decir que un predicado puede tener una o más variables y que las variables pueden tomar valores de un conjunto específico llamado DOMINIO. Así por ejemplo las dos expresiones mencionadas anteriormente son de la forma p(x,y) donde el predicado p representa “es padre de” y el domino es el conjunto de las personas.
El Cálculo de Predicados permite ampliar el espectro del Cálculo_Proposicional, trabajando con fórmulas de diversos tipos además del booleano.
Mientras la lógica proposicional presenta limitaciones expresivas no permitiendo describir la estructura interna de las proposiciones, la lógica de predicados cuenta con un lenguaje mucho más expresivo que posibilita resolver esas limitaciones.
En la lógica proposicional la representación proposicional del juicio “Si Ana estudia, aprueba” se compone de dos átomos “Ana estudia”, representado como p y “Ana aprueba”, representado como q, pero las variables proposicionales p y q no reflejan el vínculo que existe entre las proposiciones que representan, (ambas hacen referencia a Ana).
En el lenguaje del cálculo de predicados los átomos tienen una representación relacional, pudiendo representarse “Ana estudia” como Est(ana), donde Est(x) es la relación untaria (de un argumento) que expresa que el individuo x estudia, de un modo similar “Ana aprueba” puede representarse como Apr(ana), siendo Apr(x) la relación que expresa que el individuo x aprueba, de este modo Est(ana) y Apr(ana) expresan explícitamente que ambas proposiciones hacen referencia a propiedades distintas (estudiar y aprobar) de un mismo objeto (Ana).
Por lo tanto se puede definir Cálculo de predicado como un sistema formal, estructurado para el estudio de la inferencia en los lenguajes formales con cuantificadores que alcanzan solo a variables de individuos, y con predicados y funciones cuyos argumentos son constantes o variables de individuos.
La construcción de fórmulas en este cálculo obliga a definir nuevas expresiones llamadas predicados.
Un predicado es una aplicación de una función booleana cuyos argumentos pueden ser de diferentes tipos, es decir un predicado puede ser una función de tipo Z → B.
Los nombres de las funciones (igual, menor) son llamados símbolos de predicados. También se utiliza la notación x < y para expresar el predicado menor(x, y). Por ejemplo, la siguiente expresión x < y ∧ x = z ⇒ q(x, z + x) contiene tres predicados, x < y, x = z y q(x, x + z).
Los argumentos de los predicados son en este caso, variables de tipo distinto de B o también expresiones de éstos tipos.
Los argumentos de un predicado son llamados términos, por ejemplo en la fórmula anterior los términos en los predicados son x, y, z y z + x.
El cuantificador universal
La conjunción ᴧ es asociativa, conmutativa y tiene elemento neutro verdadero. Por lo tanto puede considerarse una operación válida para definir la expresión cuantificada.
(ᴧ x : R : P )
El símbolo Ɐ, que se lee “para todo”, se conoce como cuantificador universal y la expresión anterior se denomina cuantificación universal y se lee “para todo x que satisfaga R se satisface P ”.
La sentencia “todos los cantantes hacen uso intensivo de la voz”, presenta una variable, pues “cantantes” no hace referencia a ningún elemento en particular por lo que sólo puede ser representado por una variable, sin embargo constituye una proposición porque se le puede asignar un valor veritativo.
Esto se debe a que la variable está cuantificada universalmente por “todos” con lo que se expresa que la propiedad “hacer uso intensivo de la voz” se cumple por todos los elementos del universo (conjunto de todos los cantantes).
El cuantificador universal (∀) es la operación que en el cálculo de predicados permite representar este tipo de proposiciones quedando el ejemplo anterior de la siguiente manera:
∀(x) UsoIntVoz(x)
>Puede apreciarse que x, de acuerdo con lo planteado en el epígrafe anterior, es libre en UsoIntVoz(x), pero no ocurre lo mismo en ∀(x) UsoIntVoz(x) pues al cuantificarse una variable, esta deja de ser libre.
Algunos ejemplos del uso de este cuantificador son los siguientes:
a)Todos los perros ladran.
b)Cada hombre debe pensar por su propia cabeza.
Es posible definir este nuevo operador a partir de otro ya conocido, la conjunción (ᴧ), pues si a1, a2, a3... son los elementos del universo en que toma valores la variable x, entonces:
∀(x) A(x) ⇔ A(a1) ᴧ A(a2) ᴧ A(a3) ᴧ ...
Esta equivalencia, evidencia que basta con que para un valor ai del universo, A(ai) sea falsa para que∀(x) A(x) sea falsa también.
Por último queda especificar que si el universo en que toma valores la variable x es vacío se establece que ∀(x) A(x) es verdadera.
El cuantificador existencial
La disyunción ⅴ es simétrica, asociativa y su elemento neutro es falso. Por lo tanto puede considerarse una operación válida para definir la expresión cuantificada
(ⅴ x : R : P )
Esta expresión se escribe usualmente así:
(∃x : R : P )
El símbolo ∃, que se lee “existe”, se conoce como cuantificador existencial y la expresión anterior se denomina cuantificación existencial y se lee “existe x en el rango R que satisface P ”.
La sentencia “alguien ha llegado”, es una proposición con una variable, pero esta no está cuantificada universalmente. Este tipo de proposiciones presentan cuantificación existencial, que se expresa mediante: “alguien”, “algún”, “un”, etc.
En este caso se plantea que la propiedad “haber llegado” se cumple por al menos uno de los elementos del universo (conjunto de todas las personas).
El cuantificador existencial (∃) es la operación que en el cálculo de predicados permite representar este tipo de proposiciones quedando el ejemplo anterior de la siguiente manera:
∃(x) HaLlegado(x)
Algunos ejemplos del uso de este cuantificador son los siguientes:
c)Hay hombres que han dado su vida por la libertad.
d)Un estudiante llegó tarde.
Este operador, al igual que ∀(), puede definirse a partir de otro ya conocido, en este caso la disyunción (v), pues si a1, a2, a3... son los elementos del universo en que toma valores la variable x, entonces:
∃(x) A(x) ⇔ A(a1) v A(a2) v A(a3) v ...
Esta equivalencia, evidencia que basta con que para un valor ai del universo, A(ai) sea verdadera para que ∃(x) A(x) sea verdadera también.
En caso de que el universo en que toma valores la variable x sea vacío se establece que ∃(x) A(x) es falsa.
Alfabeto del cálculo de predicados
Al igual que el cálculo proposicional, el cálculo de predicados cuenta con un alfabeto, algunos de cuyos símbolos ya se han analizado.
Este alfabeto cuenta, en primer lugar, con símbolos de constantes individuales, que se denotarán como combinaciones de letras y números comenzando siempre por una letra minúscula. En caso de utilizar solo una letra, esta será de las primeras del alfabeto latino (a, b, c, d, e,...).
También forman parte de este alfabeto los símbolos de variables individuales que se denotarán mediante las últimas letras del alfabeto latino (u, v, w, x, y, z).
Otros componentes del alfabeto son los símbolos de funciones que serán letras minúsculas del alfabeto latino, o combinaciones de letras y números (con inicial minúscula), preferentemente se emplearán f, g y h.
Integran el alfabeto también símbolos de relaciones, que serán combinaciones de letras y números comenzando siempre por una letra mayúscula.
Los símbolos del cuantificador universal ∀() y existencial ∃() vistos con anterioridad, evidentemente también componen este alfabeto.
Por último, los símbolos de constantes proposicionales, operaciones proposicionales y de agrupación, vistos en el alfabeto del cálculo proposicional integran este alfabeto también.
Términos y fórmulas del cálculo de predicados
Al igual que el cálculo proposicional, el cálculo de predicados define el concepto de fórmula, pero establece además, una expresión fundamental que se denomina término y se define según las reglas siguientes:
1. Toda constante y toda variable es un término.
2. Si t1,t2,...,tn son términos y f es un símbolo de función n-aria, entonces f(t1,t2,..., tn) es un término.
3. Todo término es el resultado de la aplicación un número finito de veces de las dos reglas anteriores.
Conociendo la definición de término, es posible establecer el concepto de fórmula del cálculo de predicados, que se sustenta en el de fórmula elemental o átomo:
definiciòn. Si t1, t2,..., tn son tèrminos y R un símbolo de relación n-aria, entonces R(t1, t2,..., tn) es una fórmula elemental o átomo.
Algunos ejemplos de fórmulas elementales o átomos son los siguientes:
a) R(a, x).
b) Amigo(luis, juan).
c) Hermano(x, y).
d) Grande(x).
e) Padre(x, y).
f) Madre(x, y).
g)Padres(x,y,z).
Evidentemente, un átomo representará una proposición elemental, pero para representar la proposiciones no elementales no basta con una fórmula atómica por lo que se define el concepto de fórmula de la siguiente manera:
1. Toda fórmula elemental es una fórmula.
2. Si A es una fórmula, entonces ¬A es una fórmula.
3. Si A y B son fórmulas, entonces [A v B], [A ᴧ B], [A ⇒ B] y [A ⇔ B] son fórmulas.
4. Si A es una fórmula donde x ocurre libre, entonces ∀(x)A y ∃(x)A son fórmulas.
5. Toda fórmula es el resultado solamente de la aplicación de un número finito de veces de las reglas1, 2, 3 y 4.
Algunos ejemplos de fórmulas son los siguientes:
a) Padres(x,y,z).
e) Padres(x,y,z) ⇔ Padre(x,z) ᴧ Madre(y,z).
b) Padres(luis,ana,jose).
f) Padre(luis,jose) ᴧ Madre(ana,jose).
g) ∀(x)∀(y)∀(z)[ Padres(x,y,z) ⇔ Padre(x,z) ᴧ Madre(y,z)].
Interpretación de fórmulas del cálculo de predicados
En el cálculo proposicional, una interpretación de una fórmula es una asignación de valores a las variables involucradas, determinar todas las interpretaciones de una fórmula no resulta difícil pues cada variable sólo tomas valores en {0, 1}.
En el cálculo de predicados esto se torna mucho más complejo, pues las variables toman valores en diversos universos y aparecen los cuantificadores que hacen necesario analizar desde otra perspectiva la interpretación de fórmulas, siendo preciso establecer:
1. Un conjunto U, que será el dominio de valores de cada variable libre y al que pertenecerán todas las constantes.
2. Una función con dominio en Un y codominio en U por cada símbolo de función n-aria.
3. Una relación definida en Un por cada símbolo de relación n-aria.
Quedando entonces determinado que una fórmula A tiene una interpretación en U si todos los símbolos de constantes, de funciones n-arias y de relaciones n-arias que ocurren en A se interpretan, respectivamente, en elementos, funciones n-arias y relaciones n-arias en U.
Establecido lo anterior, para determinar el valor veritativo de una fórmula, dada una interpretación, se procede de la siguiente manera:
1. Si A es una fórmula atómica de la forma R(a1,…, an), entonces A es verdadera en U si y solo si < a1,…, an > pertenece a R
2. Si A es la fórmula ¬B, entonces A es verdadera en U si y solo si B es falsa en U.
3. Si A es la fórmula B v C, entonces A verdadera en U si y solo si al menos una de las fórmulas B o C es verdadera en U.
4. Si A es la fórmula B ᴧ C, entonces A es verdadera en U si y solo si las fórmulas B y C son verdaderas en U.
5. Si A es la fórmula B ⇒ C, entonces A es verdadera en U si y solo si al menos B es falsa en U o C es verdadera en U.
6. Si A es la fórmula B ⇔ C, entonces A es verdadera en U si y solo si ambas fórmulas B ⇒ C y C ⇒ B son verdaderas en U.
7. Si A es la fórmula ∀(x)B(x), entonces A es verdadera en U si y solo si B(x) es verdadera en U para cualquier valor de x pertenece U.
8. Si A es la fórmula ∃(x)B(x), entonces A es verdadera en U si y solo si B(x) es verdadera en U para al menos un valor de x pertenece a U.
El siguiente ejemplo ilustra la interpretación de fórmulas del cálculo de predicados.
Sea la interpretación I definida por:
U = {1, 2, 3, 4},
R = {<1,1>,<1,2>,<1,3>,<1,4>,<2,3>},
f = {<1,2>,<2,3>,<3,4>,<4,1>}
a = 1, b = 2
Sean las fórmulas del cálculo de predicados:
a) ∀(x)R(x, f(x))
b) ∃(x)R(x, f(x))
c) ∀(x)R(a, x)
d) ∃(x)R(b, x)
e)∀(x)[∃(y)R(x, y) ⇒ R(x, 3)]
Determine el valor de las fórmulas anteriores:
a) ∀(x)R(x, f(x)).
En este caso la fórmula es falsa para I, pues R(3, f(3)), es R(3, 4) y <3,4> no pertenece a R.
b) ∃(x)R(x, f(x)). Esta fórmula es cierta para I, pues basta con que un valor de x haga R(x, f(x)) verdadera y esto ocurre con x = 1.
c) ∀(x)R(a, x). Como a = 1, la veracidad de esta fórmula depende de que R(1,x) sea cierta para todos los valores de x, lo que en efecto ocurre, siendo entonces verdadera.
d) ∃(x)R(b, x). Como b = 2 y para x = 3 se tiene R(2, 3), que es cierto, entonces la fórmula lo es también.
e) ∀∃(y)R(x, y) ⇒ R(x, 3)]. Esta fórmula es cierta pues lo son:
∃(y)R(1, y) ⇒ R(1, 3)
∃(y)R(2, y) ⇒ R(2, 3)
∃(y)R(3, y) ⇒ R(3, 3)
∃(y)R(4, y) ⇒ R(4, 3)
La primera lo es, pues la parte derecha de la implicación lo es. Lo mismo ocurre con la segunda. La tercera y la cuarta son ciertas pues sus implicantes son falsos (ningún par de R tiene como primer elemento al 3 o al 4).
Enlaces externos
Fuentes
- Fernández Laguna, Víctor (2004) (en español). Teoría de conjuntos elemental, Bachillerato (2 edición). Anaya. pp. 168. ISBN 978-84-667-2614-6.
- Climent Coloma, Joan Josep (2003) (en español). Álgebra: teoría de conjuntos y estructuras algebraicas (2 edición). Editorial Club Universitario. pp. 512. ISBN 978-84-8454-302-2.
- Setó, Jordi (2002) (en español). Teoría elemental de conjuntos (1 edición). Clag S.A. pp. 168. ISBN 978-84-921847-6-7.
- Arrieche Alvarado, Mario (2002) (en español). Iniciación de la teoría de conjuntos, en la formación de profesores de matemáticas (1 edición). Arrieche Alvarado, Mario Jose. pp. 169. ISBN 978-84-607-4774-1.
- González Carlomán, Antonio (2001) (en español). Retículo completo de Boole. Lógica matemática teoría de conjuntos (1 edición). Universidad de Oviedo. Servicio de Publicaciones. pp. 204. ISBN 978-84-8317-264-3.
