Cálculo de Predicados

El Cálculo de Predicados (Sistema SP), también conocido como Lógica de Primer Orden, es una extensión de la lógica proposicional que permite analizar la estructura interna de las proposiciones, al considerar individuos, propiedades de los individuos y relaciones entre ellos. Esto le otorga un poder expresivo mucho mayor. A continuación, se detalla cada uno de los aspectos solicitados:

Definiciones Clave

Predicados

Un predicado es una expresión lingüística que describe una propiedad de un individuo o una relación entre varios individuos. Se representa usualmente con una letra mayúscula seguida de argumentos entre paréntesis, que pueden ser constantes o variables.

● Ejemplo: P(x) (x es par), Ama(x, y) (x ama a y).

Constantes Individuales

Las constantes individuales (o nombres) son símbolos que representan individuos específicos del dominio de discurso. Se suelen usar letras minúsculas al comienzo del alfabeto

(ej., a, b, c).

● Ejemplo: s para "Sócrates", m para "Marte".

Variables Individuales

Las variables individuales son símbolos que representan individuos de manera genérica. Se suelen usar letras minúsculas al final del alfabeto (ej., x, y, z). Permiten expresar propiedades o relaciones que se cumplen para "cualquier" o "algún" individuo.

Cuantificadores

Los cuantificadores indican el alcance de las variables.

● Cuantificador Universal (\\forall): "Para todo", "Para cada". Se utiliza para afirmar que una propiedad se cumple para todos los individuos en el dominio.

○ Ejemplo: \\forall x P(x) ("Para todo x, x tiene la propiedad P").

● Cuantificador Existencial (\\exists): "Existe al menos uno", "Alguno". Se utiliza para afirmar que al menos un individuo en el dominio tiene una propiedad.

○ Ejemplo: \\exists x P(x) ("Existe al menos un x tal que x tiene la propiedad P").

Funciones (Functors)

Una función en el cálculo de predicados, similar a una función matemática, es una expresión que toma uno o más términos como argumentos y devuelve un individuo. Se representan con letras minúsculas como f, g, h.

● Ejemplo: padre(x) (el padre de x), suma(x, y) (la suma de x e y).

Diferencia entre Predicados y Funciones: Su Rango

La diferencia fundamental entre predicados y funciones radica en lo que "devuelven" o lo que su "rango" representa:

● Predicados: Cuando se les asignan argumentos, los predicados "devuelven" un valor de verdad (verdadero o falso). Es decir, el rango de un predicado es el conjunto {Verdadero, Falso}.

○ Ejemplo: Si P(x) es "x es un número par", P(4) es Verdadero, y P(3) es Falso.

● Funciones: Cuando se les asignan argumentos, las funciones "devuelven" un individuo del dominio de discurso. El rango de una función es el conjunto de individuos del dominio.

○ Ejemplo: Si f(x) es "el padre de x", f(\\text{Juan}) podría ser "Pedro". El resultado es otro individuo, no un valor de verdad.

Fórmulas: Gramática de los Términos y las Fórmulas de SP

La construcción de términos y fórmulas en SP sigue reglas gramaticales específicas:

Términos

Los términos representan individuos en el lenguaje. Un término puede ser:

1. Una constante individual (ej., a, b, c).

2. Una variable individual (ej., x, y, z).

3. Una función aplicada a términos (ej., f(t\_1, \\dots, t\_n), donde f es un símbolo de función y t\_1, \\dots, t\_n son términos).

○ Ejemplo: padre(x), suma(a, b), f(g(y), c).

Fórmulas Atómicas

Una fórmula atómica es la aplicación de un predicado a uno o más términos. Representan las proposiciones más básicas que pueden ser verdaderas o falsas.

● Ejemplo: P(a), Q(x, y), R(f(c), z).

● También se considera una fórmula atómica la igualdad: t\_1 = t\_2, donde t\_1 y t\_2 son términos.

Fórmulas Bien Formadas (FBF)

Las fórmulas bien formadas se construyen a partir de fórmulas atómicas y la aplicación de conectivas lógicas y cuantificadores:

1. Toda fórmula atómica es una FBF.

2. Si A es una FBF, entonces \\neg A (negación de A) es una FBF.

3. Si A y B son FBFs, entonces (A \\land B) (conjunción), (A \\lor B) (disyunción), (A \\rightarrow B) (implicación) y (A \\leftrightarrow B) (doble implicación) son FBFs.

4. Si A es una FBF y x es una variable, entonces \\forall x A (cuantificación universal) y \\exists x A (cuantificación existencial) son FBFs.

5. Nada más es una FBF.

Árboles Asociados a Fórmulas

Las fórmulas de SP pueden ser representadas gráficamente mediante árboles sintácticos (o árboles de análisis). Estos árboles muestran la estructura jerárquica de la fórmula, con los operadores (conectivas y cuantificadores) como nodos y los términos o fórmulas más simples como sus hijos.

● Ejemplo para \\forall x (P(x) \\rightarrow Q(x)):

∀x

/

→

/ \

P Q

| |

x x

Sustituciones

Una sustitución es el proceso de reemplazar una variable libre en una fórmula por un término. Se denota como A[t/x], lo que significa "la fórmula A con todas las ocurrencias libres de la variable x reemplazadas por el término t". Es crucial que el término t sea "libre para" x en A, lo que significa que ninguna ocurrencia de t en la fórmula resultante quede ligada por un cuantificador.

Instancias de Fórmulas

Una instancia de una fórmula cuantificada se obtiene eliminando el cuantificador y reemplazando la variable cuantificada por un término.

● Instanciación Universal (EU): De \\forall x A(x) se puede inferir A(t) para cualquier término t.

● Instanciación Existencial (EE): De \\exists x A(x) se puede inferir A(c) para una nueva constante c que no haya aparecido previamente en la derivación.

Semántica Formal: Traducción de Predicados y Proposiciones en Español a Fórmulas de SP

La semántica formal se ocupa de dar significado a las fórmulas del cálculo de predicados, estableciendo su valor de verdad. La traducción implica:

1. Identificar predicados: Convertir propiedades o relaciones en símbolos de predicado.

2. Identificar constantes y variables: Asignar símbolos a individuos específicos y variables para individuos genéricos.

3. Identificar conectivas y cuantificadores: Representar las relaciones lógicas y el alcance de las variables.

<!-- end list -->

● Ejemplos de Traducción:

○ "Sócrates es mortal." \\rightarrow M(s) (donde M es "es mortal" y s es "Sócrates").

○ "Todos los hombres son mortales." \\rightarrow \\forall x (H(x) \\rightarrow M(x)) (donde H es "es hombre" y M es "es mortal").

○ "Algunos estudiantes son inteligentes." \\rightarrow \\exists x (E(x) \\land I(x)) (donde E es "es estudiante" y I es "es inteligente").

○ "Nadie es perfecto." \\rightarrow \\neg \\exists x P(x) o \\forall x \\neg P(x) (donde P es "es perfecto").

○ "Todos los gatos maúllan." \\rightarrow \\forall x (G(x) \\rightarrow M(x)) (donde G es "es gato" y M es "maúlla").

○ "Hay alguien a quien todos aman." \\rightarrow \\exists x \\forall y Ama(y, x) (donde Ama(y, x) es "y ama a x").

Derivaciones: Nuevas Reglas de Inferencia

Las derivaciones son secuencias de fórmulas que demuestran la validez de un argumento, partiendo de premisas y aplicando reglas de inferencia. En el sistema SP, se añaden reglas específicas para manejar la identidad y los cuantificadores:

Regla de Copia

Permite repetir una línea anterior de la derivación. Es una regla básica para organizar los pasos.

Reglas para Introducción y Eliminación de la Identidad

● Introducción de la Identidad (I=): Permite introducir una identidad de la forma t = t en cualquier punto de la derivación.

○ Ejemplo: a = a.

● Eliminación de la Identidad (E=): Si tenemos una identidad t\_1 = t\_2 y una fórmula A que contiene una o más ocurrencias de t\_1, podemos reemplazar una o más de esas ocurrencias por t\_2 para obtener A'. Esta regla es también conocida como sustitución de idénticos.

○ Ejemplo: De P(a) y a = b, se puede inferir P(b).

Reglas para Introducción y Eliminación de los Cuantificadores

Estas reglas son fundamentales para trabajar con proposiciones cuantificadas:

● Eliminación del Cuantificador Universal (EU): Si se tiene una fórmula universalmente cuantificada \\forall x A(x), se puede inferir A(t) para cualquier término t.

○ Ejemplo: De \\forall x M(x) (Todos son mortales), se infiere M(s) (Sócrates es mortal).

● Introducción del Cuantificador Universal (IU): Si se ha derivado A(c) para una constante arbitraria c (que no aparece en las premisas ni en suposiciones de las que A(c) dependa), se puede inferir \\forall x A(x).

● Eliminación del Cuantificador Existencial (EE): Si se tiene una fórmula existencialmente cuantificada \\exists x A(x), se puede asumir A(c) para una nueva constante c que no aparezca en ninguna premisa ni en la conclusión final. Esta asunción  se utiliza dentro de una subderivación, y la conclusión de esta subderivación (que no debe depender de c) es lo que se infiere.

● Introducción del Cuantificador Existencial (IE): Si se tiene una fórmula A(t) donde t es un término, se puede inferir \\exists x A(x) para cualquier variable x, siempre que t se sustituya por x en A.

○ Ejemplo: De M(s) (Sócrates es mortal), se infiere \\exists x M(x) (Existe alguien que es mortal).

Nociones de Teorema, Consecuencia y Consistencia Teorema

Un teorema en el sistema SP es una fórmula que puede ser derivada sin ninguna premisa. Es una verdad lógica del sistema. Se denota por \\vdash A.

Consecuencia Lógica (Sintáctica)

Una fórmula A es consecuencia lógica de un conjunto de premisas \\Gamma (denotado \\Gamma \\vdash A) si existe una derivación de A a partir de las premisas en \\Gamma. Esto significa que A se puede deducir sintácticamente de \\Gamma.

Consistencia

Un conjunto de fórmulas \\Gamma es consistente si no es posible derivar una contradicción (ej., A \\land \\neg A) a partir de él. En otras palabras, no se puede deducir tanto una fórmula como su negación. Un sistema formal es consistente si no se puede derivar ninguna contradicción en él.

Semántica Informal: Traducción de Razonamientos con Predicados en Español a Derivaciones en SP

La semántica informal se refiere al proceso de tomar un argumento expresado en lenguaje natural y representarlo en el lenguaje formal del cálculo de predicados, para luego demostrar su validez mediante derivaciones.

● Pasos Típicos:

1. Identificar Premisas y Conclusión: Separar el argumento en sus componentes lógicos.

2. Formalizar Proposiciones Atómicas: Traducir cada proposición simple a una fórmula atómica usando predicados y constantes/variables.

3. Formalizar Conectivas y Cuantificadores: Representar las relaciones lógicas (y, o, si...entonces, no, todos, algunos) con los símbolos correspondientes.

4. Construir la Derivación: Aplicar las reglas de inferencia para llegar de las premisas a la conclusión.

● Ejemplo:

○ Razonamiento en Español:

■ "Todos los perros son mamíferos."

■ "Fido es un perro."

■ "Por lo tanto, Fido es un mamífero."

○ Traducción a SP:

■ Premisa 1: \\forall x (P(x) \\rightarrow M(x)) (donde P es "es perro", M es "es

mamífero")

■ Premisa 2: P(f) (donde f es "Fido")

■ Conclusión: M(f)

○ Derivación (esquema):

1. \\forall x (P(x) \\rightarrow M(x)) (Premisa)

2. P(f) (Premisa)

3. P(f) \\rightarrow M(f) (de 1, por EU)

4. M(f) (de 2 y 3, por Modus Ponens)

Metateoremas sobre Sintaxis: Deducción, Sustitución, Reemplazo

Los metateoremas son teoremas sobre el propio sistema lógico, no dentro del sistema. Se refieren a propiedades del sistema en sí.

Teorema de la Deducción

Establece que si una fórmula B es derivable de un conjunto de premisas \\Gamma junto con una premisa adicional A (es decir, \\Gamma, A \\vdash B), entonces la implicación (A \\rightarrow B) es derivable de solo \\Gamma (es decir, \\Gamma \\vdash (A \\rightarrow B)). Este teorema es fundamental para la construcción de demostraciones condicionales.

Teorema de Sustitución

En SP, este teorema se relaciona con la validez de reemplazar una subfórmula por otra equivalente. Si dos fórmulas son lógicamente equivalentes, una puede ser sustituida por la otra en cualquier contexto sin cambiar el valor de verdad de la fórmula completa.

Teorema de Reemplazo

Similar al teorema de sustitución, el teorema de reemplazo establece que si A \\leftrightarrow B es un teorema (o una tautología), y C es una fórmula que contiene una ocurrencia de A como subfórmula, entonces la fórmula C' obtenida al reemplazar esa ocurrencia de A por B es lógicamente equivalente a C.

Definición y Uso de Reglas Derivadas y de Reemplazo

● Reglas Derivadas: Son reglas de inferencia que no son básicas del sistema, pero pueden ser demostradas a partir de las reglas básicas. Se introducen para simplificar las derivaciones, haciendo los pasos más concisos.

○ Ejemplo: El Modus Tollens (A \\rightarrow B, \\neg B \\vdash \\neg A) puede ser una regla derivada si no es una regla primitiva.

● Reglas de Reemplazo: Son reglas que permiten reemplazar una subfórmula por otra lógicamente equivalente en cualquier parte de una fórmula. A diferencia de las reglas de inferencia que operan sobre fórmulas completas, las reglas de reemplazo operan dentro de una fórmula.

○ Ejemplo: Leyes de De Morgan (ej., \\neg(A \\land B) \\leftrightarrow (\\neg A \\lor \\neg B)), Doble Negación (\\neg \\neg A \\leftrightarrow A).

Semántica: Interpretaciones

La semántica del Cálculo de Predicados define el significado de las fórmulas. Una interpretación es una asignación de significado a los símbolos no lógicos (constantes, variables, funciones y predicados) de un lenguaje de primer orden.

Una interpretación I está compuesta por:

1. Un Dominio (D): Un conjunto no vacío de individuos sobre el cual se interpretan las variables y constantes.

2. Una Asignación para las Constantes: Cada constante individual se asigna a un individuo específico en D.

3. Una Asignación para las Variables Libres: Cada variable libre se asigna a un individuo específico en D.

4. Una Asignación para los Símbolos de Función: Cada símbolo de función f con aridad n se asigna a una función de D^n a D.

5. Una Asignación para los Símbolos de Predicado: Cada símbolo de predicado P con aridad n se asigna a un conjunto de n-tuplas de individuos del dominio D. Este conjunto representa los casos en que el predicado es verdadero.

Bajo una interpretación, cada fórmula bien formada toma un valor de verdad (verdadero o falso). Una fórmula es válida (o una tautología) si es verdadera bajo todas las posibles interpretaciones. Una fórmula es satisfacible si es verdadera bajo al menos una interpretación.