Hola,
Más allá de entender las reglas de deducción natural, en lógica II sólo hace falta entender cómo funcionan los cuantificadores y la ampliación del alcance expresivo respecto a la lógica proposicional.
Es decir, que La teoría de la lógica proposicional y la de primer orden, tanto en la deducción natural, las reglas de deducción natural básicas o derivadas, como para la formación de contraejemplos, en los árboles semánticos, etc., sólo variará en el manejo de los cuantificadores.
Algunas de las adiciones a la parte teórica:
A diferencia de la lógica proposicional, que opera con
proposiciones enteras como unidades indivisibles, la lógica de primer orden
descompone proposiciones en sujetos y predicados, y permite el uso de cuantificadores. Esto permite la cuantificación sobre individuos en un dominio específico y la expresión de relaciones entre estos individuos mediante los predicados.
[Edición: para ilustrar esto, veamos 2 ejemplos:
una proposición de lógica proposicional como podría ser "llueve y hace frío"
(P∧Q), cada parte de la conjunción (
∧) es indivisible en cuanto a su contenido semántico.
En lógica de primer orden, podríamos tener 'Todos los humanos son mortales' (∀x(H(x)→M(x))) donde respectivamente:
- H(x) = 'x es humano"
- M(x) = 'x es mortal'
y la estructura de la sentencia se analiza en más detalle.
Algunas notas respecto a la sintaxis:
Las conectivas son las mismas:
¬ (negación),
∧ (y, o conjunción),
∨ (o, o disyunción),
→ (implicación),
↔ (si y solo si).
Los cuantificadores son: ∀ (el cuantificador
universal, se lee: para todo) y
∃ (el cuantificador
existencial se lee: existe).
Variables: representan objetos generales dentro del dominio (por convención: ...x,y,z).
Constantes: denotan objetos específicos (por convención: a,b,c...).
Funciones: mapean objetos a otros objetos (por ejemplo
f(x) podría representar el padre de (x).
- *[Edición: a modo de aclaración, es muy raro ver (o no se ven) ejercicios en los exámenes o en los libros de Deaño o de Formas Lógicas(tengo los libros en alguna parte pero no recurro a ellos hace mucho aunque estoy cursando la asignatura, supongo que el estudio de la lógica es independiente de la bibliografía) que utilicen funciones y no recuerdo en ellos dónde se explica cómo una función y un predicado pueden interactuar en una fórmula como P(f(a)), donde f(a) podría ser interpretado como "el padre de a" y P(x) podría interpretarse como "x es alto". Es probable que Deaño lo explique y en Formas Lógicas no se explique. O que se haga o no se haga en ambos; en cualquier caso, es altamente probable que no haya funciones en los exámenes mayo-junio o septiembre.]
Predicados: son las propiedades o relaciones entre objetos (por ejempl: P(x) podría ser "x es azul", R(x,y) podría ser "x es más alto que y").
Formulas bien formadas (FBF):
Por aquí un desglose de las reglas fundamentales que deben cumplirse para tener FBFs:
Para las atómicas:
Predicado con términos: Si P es un predicado
n-ario y t
1 ,…,t
n son términos, entonces P(t
1 ,…,t
n ) es una FBF.
De igualdad:
Si t
1 y t
2 son términos, entonces t
1 = t
2 es una FBF.
En las conectivas:
Negación: Si ϕ es una FBF, entonces ¬ϕ también lo es.
Para la
conjunción, la
disyunción, la
implicación y el
bicondicional: Si ϕ y ψ son FBFs, entonces ϕ∧ψ, ϕ∨ψ, ϕ→ψ, y ϕ↔ψ también son FBFs.
En
cuantificadores:
Universal: Si ϕ es una FBF y x es una variable, entonces ∀xϕ es una FBF.
Existencial: Si ϕ es una FBF y x es una variable, entonces ∃xϕ es una FBF.
Transcripción de la tabla de
reglas de deducción natural:
Eliminación de la conjunción (∧E)
Si tenemos P∧Q, entonces podemos inferir P y también Q.
Introducción de la conjunción (∧I)
Si tenemos P y Q como premisas separadas, podemos inferir P∧Q.
Introducción de la disyunción (∨I)
Si tenemos P, podemos inferir P∨Q para cualquier Q.
Eliminación de la disyunción (∨E)
Si tenemos P∨Q y, suponiendo P deducimos R, y suponiendo Q deducimos también R, entonces podemos concluir R.
Eliminación del condicional ( →E, el famoso Modus Ponens)
Si tenemos P→Q y P, entonces podemos inferir Q.
Introducción del condicional ( →I)
Si, asumiendo P como hipótesis, podemos deducir Q, entonces podemos concluir P→Q sin esa hipótesis.
Eliminación de la negación (¬E, Reducción al Absurdo)
Si la suposición de P lleva a una contradicción, podemos inferir ¬P.
Introducción de la negación (¬I)
Si deducir P lleva a una contradicción, podemos concluir¬P.
Eliminación de la bicondicional (↔E)
Si tenemos P↔Q, podemos inferir P→Q y Q→P.
Introducción de la bicondicional (↔I)
Si podemos demostrar P→Q y Q→P, entonces podemos concluir P↔Q.
Reglas derivadas:
Modus Tollendo Ponens (MTP)
Si tenemos P∨Q y ¬P, podemos inferir Q.
Modus Tollens
Si tenemos P→Q y ¬Q, podemos inferir ¬P.
Introducción de la Igualdad (RI=)
Cualquier objeto es igual a sí mismo, a=a.
Eliminación de la Igualdad (RE=)
Si x=y y ϕ(x) es verdadero, entonces ϕ(y) también lo es.
Introducción del Único (RI∃!)
Si ∀x∀y((ϕ(x)∧ϕ(y))→x=y) y ϕ(t) para algún t, entonces ιxϕ(x)=t.
Eliminación del Único (RE∃!)
Si t=ιxϕ(x) y ϕ(t) es verdadero, entonces podemos usar t en lugar de ιxϕ(x) en cualquier fórmula.
Reflexividad (RflI)
Cualquier objeto es igual a sí mismo.
Simetría (SimI)
Si a=b, entonces b=a.
Transitividad (TrI)
Si a=b y b=c, entonces a=c.
Eliminación de Igualdad en Predicados (EI2)
RSi a=b y P(a), entonces P(b).
Sustitución por Igualdad (R sust=)
Si a=b, entonces cualquier fórmula que contenga a puede ser transformada en una fórmula válida sustituyendo a por b.
Interdefiniciones: [Edición: los predicados se suponen '[i]verdaderos[/i]'.]
Implicación a Conjunción(Interdef. →, ∧)
P→Q puede ser reescrito como ¬(P∧¬Q).
[Edición: estamos negando la única situación en la que la implicación falla, cuando P es verdadero y Q falso.]
Implicación a Disyunción (Interdef. →, ∨)
P→Q puede ser reescrito como ¬P∨Q.
[Edición: esto es así porque la unica situación donde no se cumple P→Q es cuando P es verdadero y Q falso; de modo que la implicación se sostiene si P es falso (¬P).]
Conjunción a Implicación (Interdef. ∧, →)
P∧Q puede ser reescrito como ¬(P→¬Q).
[Edición: negar que la implicación de que P implique ¬Q afirmamos que tanto P como Q deben ser verdaderos.]
Disyunción a Implicación (Interdef. ∨, →)
P∨Q puede ser reescrito como ¬P→Q.
[Edición: en esta implicación la falsedad (¬) de P implica la verdad de Q de la disyunción.
Conjunción y Disyunción (Interdef. ∧, ∨)
P∧Q puede ser reescrito como ¬(¬P∨¬Q).
[Edición: negar lo diametralmente opuesto a decir (1)P es verdadero y Q es verdadero es decir: (2)P es falso y Q es falso. Negar a (2) es equivalente a afirmar (1).
Disyunción y Conjunción (Interdef. ∨, ∧)
P∨Q puede ser reescrito como ¬(¬P∧¬Q).
[Edición: si estamos señalando que o P o Q son verdaderos, al negar que sea cierto que ambos sean falsos estamos señalando que uno de ellos es verdadero.
[Edito: en un sentido más amplio se pueden interpretar las transformaciones entre cuantificadores como interdefiniciones, por ejemplo si en:
¬∀xP(x)≡∃x¬P(x)
- ¬∀xP(x) = "no es cierto que P(x) sea verdadero para todo x"
- ∃x¬P(x) = "existe al menos un x tal que P(x) no es verdadero"
la equivalencia se sostiene afirmando que si bien no es verdad que algo sea el caso para todos los elementos debe haber al menos un elemento para el que no sea el caso, al igual que en:
¬∃xP(x)≡∀x¬P(x)
- ∃xP(x) = "no existe ningún x para el cual P(x) sea verdadero"
- ∀x¬P(x)
donde se dice que si no hay un elemento que cumpla P, entonces todos cumplen ¬P.
* Entender esta transformación o 'interdefinición' de los cuantificadores es una ayuda en la búsqueda de contraejemplos o en la verificación de propiedades.
Reglas para cuantificadores:
Introducción del Universal (RI∀)
Si ϕ(x) ha sido demostrado bajo la suposición deque x es arbitrario, entonces podemos generalizar a∀xϕ(x), siempre y cuando x no aparezca en supuestos no descartados o en premisas.
Eliminación del Universal (RE∀)
Si tenemos ∀xϕ(x), podemos sustituir x por cualquier término específico t, resultando en ϕ(t).
Introducción del Existencial (RI∃)
Si ϕ(t) es verdadero para algún término específico t, entonces podemos inferir ∃xϕ(x).
Eliminación del Existencial (RE∃)
Si tenemos ∃xϕ(x) y podemos demostrar ψ bajo la suposición de ϕ(x) para un x nuevo, entonces podemos inferir ψ, siempre y cuando x no aparezca en ψ ni en premisas no canceladas.
[Reglas avanzadas de Cuantificadores]
Fórmula Barcan (FB): □∀xϕ(x)→∀x□ϕ(x)
Se afirma que si es necesariamente que todos los individuos cumplen ϕ, entonces para cada individuo en particular, ϕ es necesariamente cierto.
Conversa de Barcan (CFB): ∀x□ϕ(x)→□∀xϕ(x)
Se afirma que si para cada individuo, ϕ es necesariamente cierto, entonces es necesariamente cierto que todos los individuos cumplen con ϕ.
Reglas de Skolemización: la
skolemización es un proceso empleado para eliminar ∃ mediante introdución de funciones Skolem en teoría de la demostración y en la simplificación de fórmulas para resolución automática en lógica, veamos:
Dada una fórmula ∃xϕ(x,y), donde
y es libre, la skolemización reemplaza
x con una función f(y), resultando en ϕ(f(y),y). Así se elimina el cuantificador, bajo la suposición de que f es una función que 'elige' un
x apropiado para cada
y.
ECQ
Si P y ¬P son ambas verdaderas, entonces cualquier Q puede ser inferida, simbolizado como P,¬P⊢Q.
Cambio de cuantificadores (cambio de ariable)
Si tenemos ∀xP(x) o ∃xP(x), podemos reemplazar x por otra variable y que no esté en uso en P para obtener ∀yP(y) o ∃yP(y), respectivamente.
Notas para hacer árboles semánticos:
Respecto a los árboles semánticos de lógica I a efectos prácticos la única diferencia es también el tratamiento de los cuantificadores.
Por supuesto hay detalles un poco más técnicos, como el
dominio de interpretación pero no son relevantes para la preparación de los exámenes, ya que en los exámenes los ejercicios
no son complejos, sino
eficientes.
Reglas para descomponer los cuantificadores en los árboles:
Para descomponer ∀ en ∀xP(x) se reemplaza x por un término constante y arbitrario [
importante: que no haya aparecido antes en la rama.]
Y para descomponer ∃ en ∃xP(x) se introduce un término constante concreto, mostrando que "existe al menos un elemento tal que P es verdadero".
El procedimiento es el mismo que en lógica I:
negamos la fórmula de la que probamos su validez,
descomponemos aplicando las reglas para conectivas y cuantificadores hasta que ya no se pueda descomponer más
y evaluamos que, si bien todas las ramas terminan en contradicción se trata que la fórmula original (no su negación) es válida o si bien, alguna rama es consistente (no contiene contradicciones) el conjunto de fórmulas es satisfacible, es decir, tanto la fórmula original como su negación.
[Edición: en una fórmula cuantificada como ∀xP(x) reemplaza x por un término constante albitrario que no se encuentre en la rama del árbol (usualmente: a, b, c...). Por ejemplo: ∀xP(x) = Pa o también: ∀x(x>0) se transforma en a>0 al introducir la constante a.
Para el existencial ∃xP(x) donde al menos existe un elemento para el que P es verdadero se introduce una nueva constante específica no usado anteriormente en la misma rama: ∃x(x<0) pasa a: b<0.
Ejemplos (sencillos) de: un árbol semántico para casos donde
todas las ramas conducen a contracciones y de otro árbol semántico donde
al menos una rama permanecerá abierta.
Probemos mediante el método de árbol semántico: ∀x(P(x)→Q(x))→(∃xP(x)→∃xQ(x))
- Negamos la fórmula y queda: ¬(∀x(P(x)→Q(x))→(∃xP(x)→∃xQ(x))); empleamos Interdef. →, ∨: (A→B≡¬A∨B ) y su negación (¬(A→B )≡A∧¬B ), transformando la implicación en ¬A∨B y acto seguido la negación en A∧¬B.
- Descomponemos (la negación): esto nos da ∀x(P(x)→Q(x))∧¬(∃xP(x)→∃xQ(x)); y volvemos a plicar Interdef. →, ∨ para descomponer ¬(∃xP(x)→∃xQ(x)) en ∃xP(x)∧¬∃xQ(x).
- Introducimos constantes para descomponer los cuantificadores: para ∀x(P(x)→Q(x)), consideramos un término constante 'a' tal que si P(a) es verdadero entonces Q(a) debe ser verdadero. Para ∃xP(x), elegimos el mismo término 'a' demostrando P(a).
- Para ¬∃xQ(x), aplicamos ∀x¬Q(x) y especificamos que ¬Q(a) debe ser verdadero, usando la constante 'a' ya introducida.
- Evaluamos las contradicciones: P(a) implica Q(a) por la universalidad de ∀x(P(x)→Q(x)), pero al mismo tiempo, ¬Q(a) debe ser verdadero por ∀x¬Q(x), lo que resulta en una contradicción directa (Q(a) y ¬Q(a) no pueden ser ambos verdaderos).
- Como que encontramos una contradicción bajo la suposición inicial (la negación de la fórmula original), esto indica que la fórmula original es válida en todos los modelos posibles. Todas las ramas del árbol semántico llevan a contradicciones, confirmando la validez de la fórmula.
Saludos y ánimo, la lógica es una gran compañera.