Deducción en la Lógica de Predicados (página 2)

Partes: 1, 2

Lógica de predicados:Reglas de deducción, V
Limitación en la regla de deducción de implicaciones (?,? ? ? ? ? ? ???):
La deducción de partida (?,? ? ?) no puede incluir ninguna generalización sobre ninguna variable libre de ?.
Consecuencia: en una deducción auxiliar, no equivalen una fórmula ? y ?x,?. Se puede aplicar especificación a la última, pero no generalización a la primera.

Deducción de implicación a partir de inferencia
Si se permitieran generalizaciones en las deducciones que dan lugar a implicaciones, se podrían hacer deducciones falsas como la siguiente:
Deducción auxiliar:
a=0 ? ?a,a=0 [Generalización]
? Sa=0 [Especificación]
Fórmula deducida: a=0 ? Sa=0

Lógica de predicados:Reglas de deducción, VI
Regla de intercambio:
Ejemplo: ?a,~Sa=0 ?? ~?a,Sa=0
– A??,~B ?? A~??,B [?: variable]
Observaciones:
?x,~? ? ~?x,?

Lógica de predicados:Reglas de deducción, VII
Comentario a la regla de intercambio:
??,~ ? ? ~??,?
Se pueden añadir las reglas
A??,~B ?? A~??,B

Lógica de predicados:Reglas de deducción, VIII
Regla de existencia:
Ejemplos:
a) ?a,~Sa=0 ? ?b,?a,~Sa=b
b) ?a,~Sa=0 ^ ?a,~SSa=0 ?
?b, (?a,~Sa=b ^ ?a,~SSa=0)
– ? ? ??,??//? [?: Término en ?]

Lógica de predicados:Reglas de deducción, IX
Regla de ámbito:
Ejemplo:
?y,(SSy=Sy+S0 v?z,Sz=0) ??
(?y, SSy=Sy+S0) v ?z,~Sz=0
– ??,(?v?) ?? (??,?)v?
[? no libre en ?]
– ??,(?^?) ?? (??,?)^?
[? no libre en ?]

Lógica de predicados:Reglas de deducción, X
Comentario a la regla de ámbito: Las siguientes deducciones son correctas bajo la hipótesis de existencia de constantes:
– ??,(?^?) ?? (??,?)^?
– (??,?)v? ?? ??,(?v?)
[? no libre en ?]
(pero no en general: las partes derechas pueden ser falsas si el dominio es vacío aunque las partes izquierdas sean ciertas)

Lógica de predicados:Reglas de deducción, XI
Comentario a la regla de ámbito: Las siguientes deducciones son correctas en general:
– (??,?)^? ?? ??,(?^?)
– ??,(?v?) ?? (??,?)v?
[? no libre en ?]
La demostración se dará más adelante. Podemos aceptar cuatro reglas de deduc-ción correspondientes a estas deducciones.

Lógica de predicados:Reglas de deducción, XII
Reglas para la igualdad:
R. fundamental: ? ?=?
R. de simetría: ?=? ? ?=?
de Transitividad: ?=?, ?=? ? ?=?
R. de Sustitución: ?=?, ? ? ??//?
[?, ?, ?: Términos]

Lógica de predicados:Reglas de deducción, XIII
Las tres primeras reglas de la igualdad se pueden reescribir de manera natural como axiomas (son la idempotencia, simetría y transitividad de la igualdad).
En general, todo el sistema de reglas se puede sustituir por un conjunto de axiomas junto con una sola regla: el modus ponens.

Ejemplo de deducción, VI
Axiomas:
A todos los gatos les gusta el pescado
Todos los gatos comen todo lo que les gusta
Ziggy es un gato
Demostrar que Ziggy come pescado

Ejemplo de deducción, VII
Constantes:
Ziggy ? z
Pescado ? p
Predicados:
x es un gato ? g x
A y le gusta z ? t y z
u come w ? c u w

Ejemplo de deducción, VIII
?x, g x ? t x p [Axioma]
?x, ?y, g x ^ t x y ? c x y [Axioma]
g z [Axioma]
g z ? t z p [Espec. 1]
t z p [Modus pon.]
g z ^ t z p [3, 5]
?y, g z ^ t z y ? c z y [Espec. 2]
g z ^ t z p ? c z p [Espec.]
c z p [Modus pon.]

Ejercicio obligatorio
[PESC] Deducir que algún lenguado es un desgraciado a partir de los siguientes axiomas:
Todo tiburón se come un lenguado
Todo pez grande y blanco es un tiburón
Algunos peces grandes blancos viven en aguas profundas
Todo lenguado comido por un pez que vive en aguas profundas es desgraciado

Universalidad delCálculo de Predicados
La última demostración es válida independientemente del dominio. Podría ser, por ejemplo, una demostración acerca de números y funciones, alcachofas y caballos o puntos y rectas.
Esto es cierto en todas las deducciones formales basadas en el Cálculo de Predicados.
Las personas razonamos en base a unas reglas lógicas fijas, pero guiamos nuestro razonamiento en base a nuestro conocimiento del modelo que tenemos en mente.

Ejemplo de deducción, IX
?x,(F ? G) ?? (?x,F) ? (?x,G)

?x,(F ? G) (?x,F) ? Gy/x
F ? G ?y,((~?x,F)vGy/x)
[ ?x,F ?y,(Gy/xv(~?x,F))
F (?y,Gy/x)v(~?x,F)
G (~?x,F)v(?y,Gy/x)
Gy/x] (?x,F) ? (?y,Gy/x)

Ejemplo de deducción, X
?x,(F ? G) ?? (?x,F) ? (?x,G)

?x,(F ? G) ?x,~G?~Fy/x
F ? G (?x,G)v(~Fy/x)
~G ? ~F (~Fy/x)v(?x,G)
[ ?x,~G ?y,((~Fy/x)v(?x,G))
~G (?y,~Fy/x)v(?x,G)
~F (?y,Fy/x)?(?x,G)
~Fy/x]

Ejemplo de deducción, XI
?x, ? ; (? ? ?) ?? ?x,?
Demostración:
?x,? (?x,~?)?~?
? ?? ?x,((?x,~?)?~?)
[ ?x, ~? (?x,~?)??x,~?
~? (?x,?)? ?x,?
~??~? ?x,?
~?]

Ejemplo de deducción, XII
??,(FvG) ?? (??,F)vG [? no libre en G]
Demostración:
[ ~G
[ (FvG)^~G
FvG
~G
~G?F
F]

Ejemplo de deducción, XIII
…
((FvG)^~G) ?F
?x,((FvG)^~G) ??x,F [VISTO EN CLASE]
((?x,FvG)^~G)??x,((FvG)^~G) [REGLA DE AMBITO]
[ (?x,FvG)^~G
?x,((FvG)^~G) [MODUS PONENS]
?x,((FvG)^~G) ??x,F
?x,F] [MODUS PONENS]

Ejemplo de deducción, XIV
…
(?x,(FvG))^~G??x,F
(?x,(FvG))^~G
?x,F] [MODUS PONENS]
~G??x,F
(?x,F)vG
UFFFF!!!

Ejemplo de deducción, XV
?x,F, ?x,G ?? ?x,F
Demostración:
[ ?x,~F [[Reducción al absurdo]]
~F
F
F^~F]
(?x,~F) ? F^~F
(?x,~F) ? (?x, F^~F) [General. y ámbito]

Ejemplo de deducción, XVI
…
(?x,Fv~F) ? (?x,F)
Fv~F
G ? (Fv~F)
?x,G ? ?x,(Fv~F) [VISTO EN CLASE]
?x,G [AXIOMA]
?x,(Fv~F)
?x,F [MODUS PONENS]

Ejercicios obligatorios
[LOB] Se supone que en la lobera hay lobos, que son carnívoros, y hombres, que pueden ser carnívoros o hervíboros. También se supone que los carnívoros no comen lechuga y que Tom, que está en la lobera, la come. Demostrar que Tom es un hombre.
[ARD] Resolver el ejercicio anterior suponiendo que en la lobera también puede haber ardillas, que son hervíboras, y que los hombres también pueden ser omníboros, así como que los herví-boros no comen carne, que los omníboros comen carne y lechuga y que Tom come carne y lechuga. Es innecesaria alguna de las hipótesis?

Ejercicios opcionales
[TAUT] Demostrar que las siguientes fórmulas lógicas son tautologías:
(?x,?y,P x y) ? (?y,?z,(P 0 y ^ P y z)
(P ? (Q^R)) ? ((P ? Q) ^ (P ? R))
((P ? Q) ^ (P ? R)) ? (P ? (Q^R))
((?x, R x v Q x) ^ ?x,~R x) ? ?x,Q x

Interpretación: Definición formal
Recordatorio: En los sistemas formales que hemos estudiado una interpretación asigna objetos de un conjunto a partes de la palabra de partida.
En la Lógica de Predicados una interpretación asigna objetos de un conjunto a los términos y afirmaciones acerca de esos objetos a los predicados.
El conjunto de objetos asociado a una interpretación se llama su dominio (puede ser vacío).

Interpretación:Definición formal, II
Una interpretación I de un lenguaje lógico consiste en un conjunto D (su dominio) y:
Para cada variable ?, un elemento de D, ?I.
Para cada constante c, un elemento de D, cI.
Para cada símbolo de función n-aria f, una función
fI: DxDx…xD ? D.
Para cada símbolo de predicado n-ario P, un subconjunto PI ? DxDx…xD.

Interpretación:Definición formal, III
En la definición anterior las operaciones se consideran funciones binarias.
La interpretación de los símbolos de un lenguaje formal se extiende a todos los términos y todas las fórmulas del lenguaje:
Los términos se interpretan como elementos del dominio. Si un término tiene la forma
f(?1, …, ?n), su interpretación es fI(?1I, …, ?nI).
Las fórmulas se interpretan como booleanos.

Interpretación:Definición formal, IV
Las fórmulas se interpretan …
Si una fórmula tiene la forma P(?1, …, ?n), su interpretación es (?1I, …, ?nI) ? PI.
Las fórmulas compuestas se interpretan como en el cálculo de proposiciones. Por ejemplo, F^G se interpreta como FI^GI.
Las fórmulas con cuantificador se interpretan como sigue:
?x,F es cierta si ?x?D,FI.
?x,F es cierta si ? x?D,FI.

Teorema de coherencia delCálculo de Predicados
Si una fórmula F se deduce a partir de un conjunto de fórmulas A, es consecuencia de dicho conjunto de fórmulas.
Demostración:
Es consecuencia de que en cada regla de deducción, si todas fórmulas de su cabecera son ciertas en una interpretación, su cuerpo también es cierto.

Teorías lógicasDeducción como sistema formal
Una teoría lógica está formada por un lenguaje lógico, un cálculo lógico (sistema formal) y un conjunto de axiomas, que son fórmulas cerradas. Las fórmulas deducidas de los axiomas se denominan teoremas.
El conjunto de axiomas de una teoría lógica puede ser infinito, pero tiene que ser recursivo.

Deducción y consecuencia
En una teoría lógica basada en el Cálculo de Predicados, dada cualquier deducción que utilice los axiomas Ai para demostrar un teorema T, la fórmula A1^A2^…^AN ?T es una tautología.
Demostración:
Es consecuencia del teorema de coherencia para el Cálculo de Predicados.

Modelos
Un modelo es una interpretación de una teoría lógica en la que todos los axiomas son ciertos (y por lo tanto los teoremas también).
Ejemplo: En una lógica con un sólo símbolo de función f y un único axioma,
A = { ?x,?y,f x = f y ? x = y },
cualquier conjunto D con una aplicación inyectiva f:D?D es un modelo.

Ejercicios obligatorios
Dar modelos para los siguientes conjuntos de axiomas suponiendo que el lenguaje lógico que se considera no tiene constantes:
[MOD1] { ?x,?y,x=y }
[MOD2] { ?x,x=x }
[MOD3] { ? x,~x=x }
[MOD4] { ?x,~x=x }
[MOD5] { ?x,?y,x=y }
[MOD6] { ?y,?x,x=y }
[MOD7] { ?x,?y,(~x=y ^ ?z,(x=z v y=z)) }

Lógica de predicados con un modelo numérico: Axiomas
?x,~Sx=0
?x,0+x=x
?x,?y,Sx+y=S(x+y)
?x,x.0=0
?x,?y,x.Sy=(x.y)+x
?x,?y,(Sx=Sy ? x=y)
Nota: ?x,?y,(x=y ? Sx=Sy) es un teorema, consecuencia de la regla genérica de sustitución.

Lógica de predicados con modelo numérico: Axiomas, II
Inducción (conjunto infinito de axiomas)
Ejemplo:
0+0=0 ^ ?x,(x+0=x?Sx+0=Sx) ?
?x,(x+0=x)
– ?0/?, ??,(?? ?S?/?) ? ??,?
[F: Fórmula; V: Variable]
Es un conjunto infinito (recursivo) de axiomas, que se pueden utilizar como reglas de deducción.

Utilización de inducción para demostrar un teorema
Para demostrar en la lógica de predicados con modelo numérico un teorema de la forma ?x,F mediante inducción, hay que demostrar dos cosas:
A ?? F0/x
A ?? ?x,(F?FSx/x)
Una vez demostrado lo anterior, se tiene que A??F0/x^?x,(F?FSx/x), y por la regla del modus ponens y el axioma de elección para la fórmula F, A???x,F.

Ejemplo sencillo de demostración por inducción sobre números
Queremos demostrar por inducción que ?x,(x+0=x) . Tenemos que ver que:
0+0=0
?x,(x+0=x?Sx+0=Sx)
Lo primero es un axioma
Lo segundo se demuestra mediante la regla de deducción de implicaciones

Ejemplo sencillo de demostración por inducción sobre números, II
?x, (x+0=x?Sx+0=Sx)
0+0=0 0+0=0 ^
?x,?y,Sx+y=S(x+y) (?x, (x+0=x?Sx+0=Sx))
?y,Sx+y=S(x+y) (0+0=0 ^
Sx+0=S(x+0) ?x,(x+0=x?Sx+0=Sx))
[ x+0=x ??x,(x+0=x)
Sx+0=Sx] ?x,(x+0=x)
x+0=x?Sx+0=Sx

Modelo numérico
La interpretación
(D =??, 0?0, S?S, +?+, .?.)
es un modelo de la teoría lógica anterior.
Hay más modelos: D = ? x {0} ? Z x Q+, con
S(x, y) = (Sx, y)
(x, y) + (p, q) = (x+p, y+q)
(n, 0) . (x, p/q) = (x, p/q) . (n, 0) = (x.n, n.p/q)
(x, p/q) . (y, r/s) = (x.y, p.r/(q.s))

Lógica de predicados con modelo numérico: Ejemplo de deducción
Teorema: S0+S0=SS0
1 ?x,?y,Sx+y=S(x+y) [Ax. 3]
2 ?y,S0+y=S(0+y) [Espec. x ? 0]
3 S0+S0=S(0+S0) [Espec. y ? S0]
4 ?x,(0+x)=x [Ax. 2]
5 (0+S0)=S0 [Espec. a ? S0]
6 S(0+S0)=SS0 [Adición suces.]
7 (S0+S0)=SS0 [Transitiv (3, 6)]

Ejemplo de demostración numérica por inducción
?x,?y,?z,(~y=0^~z=0^y+z=SSx)
Caso x=0:
Partimos del teorema visto
S0+S0=SS0
?x,~Sx=0 [Axioma 1]
~S0=0 [Espec, x?0]
~S0=0 ^ S0+S0=SS0 [Agrup. Conj.]
~S0=0 ^ ~S0=0 ^ S0+S0=SS0 [Agrup. Conj.]
?z,(~S0=0 ^ ~z=0 ^ S0+z=SS0) [Existencia]
?y,?z,(~y=0 ^ ~z=0 ^ y+z=SS0) [Existencia]

Ejemplo de demostración numérica por inducción, II
Paso de inducción:
?y,?z,(~y=0^~z=0^y+z=SSx) ?
?u,?w,(~u=0^~w=0^u+w=SSSx)
[ ~y=0^~z=0^y+z=SSx
~y=0^~z=0
y+z=SSx
Sy+z=SSSx [Modus ponens]
~y=0^~z=0^Sy+z=SSSx]
(~y=0^~z=0^y+z=SSx)?(~y=0^~z=0^Sy+z=SSSx) [D.I.I.]
?z,(~y=0^~z=0^y+z=SSx)??z,(~y=0^~z=0^Sy+z=SSSx) [Ej.V]
?y,?z,(~y=0^~z=0^y+z=SSx)??y,?z,(~y=0^~z=0^Sy+z=SSSx)
?x,?y,?z,(~y=0^~z=0^y+z=SSx) [Inducción]

Ejemplo: Demostración más sencilla
?x,?y,Sx+y=S(x+y) ~Sx=0
?y,S0+y=S(0+y) ~S0=0 ^ ~Sx=0 ^
S0+Sx=S(0+Sx) S0+Sx=SSx
?x,0+x=x ?z,(~S0=0 ^ ~z=0 ^
0+Sx=Sx S0+z=SSx)
S0+Sx=SSx ?y,?z,(~y=0 ^ ~z=0 ^
?x,~Sx=0 y+z=SSx)
~S0=0 ?x, ?y,?z,(~y=0 ^ ~z=0 ^
y+z=SSX)