Lógica Matemática - LPred: Cuantificadores

Un cuantificador se utiliza para indicar cuántos elementos de un conjunto dado cumplen con cierta propiedad. Existen dos tipos de cuantificadores, cuyas características resumimos en la siguiente tabla:
Nombre Notación Se lee
cuantificador universal Para todo x...
cuantificador existencial Existe por lo menos un x...

² Los cuantificadores:
- Cuantificador universal (para todo). El cuantificador universal permite referirse a todos los individuos del universo del discurso.
- Cuantificador existencial (existe). El cuantificador existencial permite referirse a algunos de los individuos del universo del discurso.


Las variables, también pueden ser cuantificadas. Los cuantificadores que típicamente se utilizan en lógica de predicados son:

El cuantificador universal; " indica que la fórmula bien formada, dentro de su alcance, es verdadera para todos los valores posibles de la variable que es cuantificada. Por ejemplo:
" X . . . .

Establece que "para todo X, es verdad que . . . "

El cuantificador existencial;$ , indica que la fórmula bien formada, dentro de su alcance, es verdadera para algún valor o valores dentro del dominio. Por ejemplo:
$ X . . . .

Establece que "existe un X, tal que . . . "

A continuación se dan algunos ejemplos de predicados cuantificados:

" X, [niño (X) => le_gusta (X, helados)].

" Y, [mamífero (Y) => nace (Y, vivo)].

$ Z, [cartero(Z) ^ mordió (boby, Z)].

Desde el punto vista de representación, los cuantificadores son difíciles de usar. Por lo que es deseable reemplazarlos con alguna representación equivalente, más fácil de manipular. El caso del cuantificador universal es más simple ya que se asume a todas las variables como universalmente cuantificadas.

El cuantificador existencial es más difícil de reemplazar. El cuantificador existencial garantiza la existencia de uno o más valores particulares (instancias) de la variable cuantificada, que hace a la cláusula verdadera. Si se asume que existe una función capaz de determinar los valores de la variable que hace la cláusula verdadera, entonces simplemente se remueve el cuantificador existencial y se reemplaza las variables por la función que retorna dichos valores. Para la resolución de problemas reales, esta función, llamada función de Skolem, debe ser conocida y definida.


Las declaraciones cuantificadas se escriben en la forma que se leen "para todo x, es verdad que p" y "existe por lo menos un y tal que q es verdad".


El cuantificador universal, representado por . Este cuantificador se emplea para afirmar que todos los elementos de un conjunto cumplen con determinada propiedad. Se escribe
. (1)
La proposición (1) suele usarse como la equivalente de





El cuantificador existencial se usa para indicar que al menos un elemento de un conjunto cumple con una propiedad. Se escribe
. (2)
La proposición (2) suele interpretarse como la equivalente de la proposición

LÓGICA DE PREDICADOS

El lenguaje es el instrumento que se usa para la comunicación entre humanos. El lenguaje está formado por frases, entre ellas podemos distinguir: frases imperativas, frases interrogativas y frases declarativas.
La definición de lógica, disciplina que estudia métodos de formalización del conocimiento humano "de los métodos de formalización de frases declarativas".(Jose Emilio Labra Gayo, Daniel Fernández Lanvin, E.U.I.T.I.O.)
La lógica se clasifica:
•Lógica proposicional o lógica de enunciados:
Se parte de un elemento simple, las frases declarativas simples, las cuales tienen significado ellas mismas o la unión entre ellas,forman una frase. Esto inicia una unidad de comunicación de conocimientos, las cuales se les denomina proposiciones, y toman el valor verdadero o falso.

•Lógica de predicados: Estudia las frases declarativas,teniendo en cuenta la estructura interna de las proposiciones. Los objetos y las relaciones entre los objetos serán los elementos básicos. Podemos distinguir:
- "Qué se afirma: relación
- De quién se afirma: objeto" (Jose Emilio Labra Gayo, Daniel Fernández Lanvin, E.U.I.T.I.O.)

Lógica de Predicados (LP de Orden Cero).
Con la lógica de predicados intentamos conseguir sistemas de demostración automática de teoremas. Partimos de elementos básicos como las frases declarativas simples o proposiciones que son aquellos elementos de una frase que constituyen por sí solos una unidad de comunicación de conocimientos y pueden ser considerados Verdaderos y Falsos. La lógica de predicados estudia las frases declarativas con mayor grado de detalle, considerando la estructura interna de las proposiciones. Se tomarán como elemento básico los objetos y las relaciones entre dichos objetos. Se distingue:
• "Qué se afirma (predicado o relación)
• De quién se afirma (objeto)" (Jose Emilio Labra Gayo, Daniel Fernández Lanvin, E.U.I.T.I.O.)

Definimos a continuación las reglas sintácticas para construir fórmulas:

Definición 1:El alfabeto de la lógica de predicados estará formado por los siguientes conjuntos simbólicos:

•Conjunto de Símbolos de Variables(VAR): Es un conjunto de las últimas letras del alfabeto en minúsculas. Se utilizan subíndices, por ejemplo:
•Conjunto de símbolos de Constantes (CONS): Este conjunto lo forman las primeras letras del alfabeto en minúsculas,también utilizaremos subíndices:
•Conjunto de letras de función(FUNC): Representaremos a este conjunto por las letras f,g,h,L. Incluimos subíndices para poder diferenciar las funciones:
•Conjunto de letras de Predicado (PRED): Se representan mediante letras mayúsculas,

Símbolos de conectivas: ¬ = Negación
∨= Conectiva "o"
∧ = Conectiva "y"
→ = implicación
↔ = Doble implicación o equivalencia

Cuantificadores:
∃=existencial
∀=Universal

Signos de puntuación: Paréntesis ( ) y coma.

Definición 2: Término es una cadena de símbolos que representan a objetos y dependen de las siguientes reglas:
•"Toda variable o constante individual es un término." (Jose Emilio Labra Gayo, Daniel Fernández Lanvin, E.U.I.T.I.O.)

•"Si t1,t2,L,tn son términos y fn es una función de aridad n entonces fn(t1,t2,L,tn) es un término" (Jose Emilio Labra Gayo, Daniel Fernández Lanvin, E.U.I.T.I.O.)

•Todos los términos posibles se generan aplicando únicamente las dos reglas anteriores Cualquier término lo generamos a partir de las dos reglas dichas anteriormente.

Definición 3: Un átomo es una cadena de símbolos de la forma: donde Pn es un predicado de aridad n y sin términos

Definición 4: Definimos el conjunto de fórmulas bien formadas (fbf):
1. "Todo átomo (P,Q,R,S,...) es una fórmula bien formada. (Se denominará fórmula atómica)."
2. "Si es una fórmula bien formada, ¬ A también lo es.
3. Si y son fórmulas bien formadas, también lo son (A ∧ B), (A ∨ B) y (A ⇒ B).
4. No hay más fórmulas." (Jose Emilio Labra Gayo, Daniel Fernández Lanvin, E.U.I.T.I.O.)

Podemos hacer razonamientos con la deducción natural.
Ejemplo: Tenemos la frase “Todos los estudiantes de informática son listos” (Jose Emilio Labra Gayo, Daniel Fernández Lanvin, E.U.I.T.I.O.), lo podemos formalizar de la siguiente manera usando predicados:
I(x)=”x estudia informática” y L(x)=”x es listo” como:
"Existen estructuras deductivas que la lógica de proposiciones no puede formalizar de forma adecuada, por ejemplo, la deducción:
"Todos los informáticos son listos, Pedro es informático, luego Pedro es listo" (Jose Emilio Labra Gayo, Daniel Fernández Lanvin, E.U.I.T.I.O.)

En lógica de predicados de orden cero lo formalizamos con tres proposiciones p,q y r independientes y la fórmula resultante “p∧q→r” no sería válida.

Lógica de primer orden
En lógica de predicados de primer orden "se permite la cuantificación de variables" (Jose Emilio Labra Gayo, Daniel Fernández Lanvin, E.U.I.T.I.O.). Así de esta manera, se formaliza el razonamiento:
En la lógica de predicados de primer orden
(∀x (Informático(x)→Listo(x))∧ Informático (Pedro))→ Listo (Pedro)
La lógica de predicados de primer orden es la más básica, es una extensión de lógica de predicados de orden cero, sólo que admite los cuantificadores ( ∀ y ∃ ), y reglas de deducción natural.
Las variables en lógica de primer orden pertenecen a un dominio, tienen una asignación. Pueden existir constantes y las fórmulas en esta lógica se pueden unificar de formas nuevas que antes no teníamos o podíamos.
La LP1 es suficiente para formalizar la teoría de conjuntos, el problema es que, a diferencia de LP0, la lógica de primer orden no es predecible. No existe un procedimiento de decisión que nos permita decidir si para una fórmula,esta es válida o no.Church y Turing lo demostradon de forma independiente.

Ejemplo sobre lógica de predicados
Dada la siguiente expresión
-La variable x está ligada ya que aparece en el ámbito del cuantificador universal y además la tiene como variable de cuantificación.
-Se dice que la variable y es una variable libre ya que aunque está en el ámbito del cuantificador universal,esta no la tiene como variable de cuantificación.

---

Ámbito de los cuantificadores

Podemos definir ámbito de los cuantificadores aquella zona de una fórmula que se ve afectada por sus efectos. Las variables que se encuentran en su “radio de acción” se llaman variables ligadas y las no afectadas, variables libres. A su vez, las fórmulas sin variables libres se llaman fórmulas cerradas y las que sí tienen, fórmulas abiertas.

Ejemplo de variables libres y ligadas:

Cuando dos variables se muestran con la misma letra, podemos decir que:
1. Son la misma variable si están en el radio de acción del mismo cuantificador o si las dos son libres.
2. Son variables diferentes si no están en el radio de acción del mismo cuantificador o si una es libre y la otra no.

Según el ejemplo anterior, tendremos que:

Para evitar confusiones innecesarias, el ejemplo anterior también se podría haber escrito así:
∀u[P(u) Ù ∃tQ(t, z) → ∃yR(u, y)] Ú Q(z, x)