lógica i - diapositivas (um)

1

Lgica proposicional 9. Metateora

Juan Carlos Len Universidad de Murcia

Esquema del tema

9.1. Lgica y metalgica 9.2. Las nociones de consistencia, correccin

y completitud 9.3. La correccin del mtodo de rboles 9.4. La completitud del mtodo de rboles 9.5. La nocin de decidibilidad. Los rboles

como procedimiento decisorio 9.6. Potencia expresiva de conjuntos de

conectivas

2


9.1. Lgica y metalgica

Dos sentidos de lgica La lgica en sentido estricto se ocupa de

determinar qu argumentos son vlidos y qu proposiciones son lgicamente verdaderas

En un sentido amplio, la lgica incluye lo anterior (la lgica en sentido estricto), y el discurso acerca de ella

La metateora de la lgica (o metalgica) se considera por supuesto como parte de la ciencia de la lgica; y quiz como la parte ms importante

3

Lgica y metalgica En la prctica, decimos que nos ocupamos de

cuestiones lgicas cuando nos interesamos por un sistema deductivo con el fin de investigar cules son sus teoremas, cmo se desarrollan en l determinadas inferencias, etc.

En cambio, cuando nos preguntamos por el sistema deductivo en s mismo, y nos planteamos si no conduce a ninguna contradiccin, o si incluye entre sus teoremas todos aquellos que seran deseables, entonces podemos convenir en decir que estamos tratando cuestiones metalgicas

Teoremas y metateoremas Los teoremas son leyes lgicas: son verdaderos con

independencia de los hechos, y no cabe, por tanto, la posibilidad de que sean falsos

Un metateorema no es una ley lgica, sino una proposicin verdadera de hecho acerca de un sistema de lgica (pero que, como cualquier verdad de hecho, podra haber sido falsa)

Un metateorema no es formalmente demostrable sin partir de ningn supuesto previo

Podemos probar que es verdadero, pero partiendo de los hechos acerca de un sistema formal

4

Metalgica y filosofa de la lgica

La filosofa de la lgica tiene relacin con la metateora de la lgica, pero es bien distinta de ella

La metalgica estudia las propiedades de los sistemas lgico-formales

La filosofa de la lgica tambin puede tratar de tales sistemas lgicos, pero se ocupa de cuestiones filosficas ms que de cuestiones puramente formales

Ejemplo La filosofa de la lgica puede ocuparse de las

relaciones entre la lgica proposicional bivalente y la multivalente, y preguntarse si realmente unas son alternativas a las otras, o qu consecuencias tendra para el concepto de verdad la adopcin de un sistema multivalente, etc.

La metateora de la lgica puede ayudar mucho a resolver cuestiones de este tipo, pero no puede liquidarlas

Por ejemplo, parece relevante para una valoracin filosfica de las lgicas multivalentes el hecho de que la mayora de ellas estn contenidas en la lgica bivalente (es decir, que todos sus teoremas tambin lo son de la lgica bivalente, pero no a la inversa)

5


9.2. Las nociones de consistencia, correccin y completitud

Consistencia simple y absoluta

Un sistema formal es simplemente consistente sii para ninguna fbf A sucede que A y A. Tendramos una inconsistencia simple si

hubiera un par de teoremas contradictorios Un sistema es absolutamente consistente sii

no para toda fbf A sucede que A. Tendramos una inconsistencia absoluta

cuando todas las fbfs (o sea, cada fbf y su contradictoria) fueran teoremas

6

La consistencia del mtodo de rboles

Si en un sistema se cumple A A B entonces la inconsistencia simple implica la inconsistencia absoluta, y viceversa

En el mtodo de rboles se cumple el principio ex contradictione quodlibet

Adems, no sucede que p, por ejemplo Luego, es absoluta y simplemente

consistente

Correccin

Un sistema es correcto cuando todo argumento derivable es vlido (e incorrecto cuando permite derivar algn argumento invlido). Es decir, cuando Si A, entonces A

Para el caso particular en que fuera un conjunto vaco, tendramos que Si A, entonces A o sea, que todo teorema es vlido

7

Correccin y consistencia La correccin implica la consistencia, pues en un

sistema inconsistente para alguna fbf A sucedera que A y A y entonces, si fuera correcto, tendramos que A y A lo cual es imposible: dos fbfs vlidas no pueden ser contradictorias

Luego, basta demostrar la correccin para tener tambin probada la consistencia (pero no a la inversa)

Completitud La completitud es la inversa de la correccin Un sistema es completo cuando todo

argumento vlido es derivable (e incompleto cuando algn argumento vlido no es derivable). Es decir, cuando Si A, entonces A

Para el caso particular en que fuera un conjunto vaco, tendramos que Si A, entonces A o sea, que toda fbf vlida es un teorema

8

Adecuacin

Decimos que un sistema es adecuado con respecto a su interpretacin semntica cuando es correcto y completo: A sii A

Hay entonces una plena correspondencia entre sintaxis y semntica: y pueden intercambiarse libremente


9.3. La correccin del mtodo de rboles

9

El metateorema de correccin La correccin (si A, entonces A), para el

caso concreto de los rboles significa que Si {,A} tiene un rbol cerrado, entonces {,A} es

insatisfacible Por contraposicin, eso equivale a

Si {,A} es satisfacible, entonces {,A} tiene un rbol terminado y abierto

Ms generalmente, lo que probaremos como metateorema de correccin es que Si la lista inicial es satisfacible, el rbol terminado

estar abierto

Adecuacin de las reglas La prueba de correccin (y tambin despus la de

completitud) se basa en el siguiente Lema de adecuacin de las reglas: la premisa de una

regla es verdadera en las mismas interpretaciones en que lo son todas las lneas de alguna de sus listas de conclusiones

Las reglas que bifurcan la rama tienen dos listas de conclusiones; las que no, slo tienen una. Cada una de esas listas puede tener una o dos lneas

La prueba del lema, para cada una de las reglas, es obvia (A B, por ejemplo, es verdadera cuando A y B son veraderas o cuando lo son A y B)

10

Adecuacin descendente y ascendente

El lema de adecuacin tiene, en realidad dos partes: Adecuacin descendente: si la premisa de una regla

es verdadera para una interpretacin, entonces tambin lo son todas las lneas de alguna de sus listas de conclusiones

Adecuacin ascendente: Si todas las lneas de una de las listas de conclusiones de una regla son verdaderas para una interpretacin, entonces tambin lo es la premisa

Usaremos la primera parte para demostrar la correccin, y la segunda en la prueba de completitud

Hiptesis

Supongamos que la lista inicial de un rbol es simultneamente satisfacible

Eso significa que hay una interpretacin I que hace verdaderas a todas sus lneas

De ah se sigue que en el momento inicial el rbol est abierto Si estuviera cerrado la lista inicial contendra

como lneas una letra proposicional y la negacin de esa misma lnea. Y esas dos lneas no seran ambas verdaderas para I

11

Estrategia Para probar la correccin bastar demostrar que

cuando un rbol crece por la aplicacin de una regla, se conserva la propiedad de contener una rama satisfacible, y por tanto abierta Si la lista inicial est abierta y cada vez que

aplicamos una regla volvemos a tener una rama abierta, el rbol completo tendr una rama abierta

Suponemos entonces a) que en una rama R de un rbol sin terminar, todas las

lneas son verdaderas para una interpretacin I b) que hacemos crecer el rbol aplicando una regla a

una de sus lneas L (la cual puede pertenecer o no a R: lo que nos obliga a considerar dos casos)

Caso 1 Si L est en R, entonces, segn (a), L es verdadera

para I Apelando al lema (la adecuacin descendente de la

regla aplicada a L), sern verdaderas para I todas las lneas de al menos una de las listas de conclusiones aadidas a R

Luego, R junto con esa lista de conclusiones forma una rama del rbol extendido en la cual todas sus lneas son verdaderas para I

Luego, si L est en R, cuando el rbol se extiende por aplicacin de una regla, se conserva la propiedad de contener una rama en la que todas sus lneas son verdaderas para I

12

Caso 2 Si L no est en R, entonces al aplicar una regla a L,

no aadimos nada a R En este caso, la propia R es una rama del rbol

extendido en la cual todas las lneas son verdaderas para I

Luego tambin si L no est en R, cuando el rbol se extiende por aplicacin de una regla, se conserva la propiedad de contener una rama en la que todas sus lneas son verdaderas para I

Por tanto, sea cual sea el caso, ha de haber una rama tal (y por tanto abierta) en el rbol terminado, con lo que se completa la prueba de la correccin


9.4. La completitud del mtodo de rboles

13

El metateorema de completitud La completitud (si A, entonces A), para el

caso concreto de los rboles significa que Si {,A} es insatisfacible, entonces {,A} tiene un

rbol cerrado Por contraposicin, eso equivale a

Si {,A} tiene un rbol terminado y abierto, entonces {,A} es satisfacible

Ms generalmente, lo que probaremos como metateorema de completitud es que Si hay una rama abierta en un rbol terminado, la lista

inicial es satisfacible

Hiptesis

Supongamos que un rbol terminado contiene una rama abierta R

Puesto que est terminado, habrn sido marcadas todas las lneas de R que no sean letras proposicionales o letras proposicionales negadas. O sea, todas las lneas con una longitud de 3 smbolos o ms, si es que las hay

14

Estrategia Consideremos una interpretacin I que asigna V a

aquellas letras proposicionales que figuran como lneas independientes en R, y F a todas las dems

Consecuentemente, todas las lneas sin marcar de R (las lneas de longitud 1 y 2) sern verdaderas para I

Demostraremos entonces que todas las lneas de R son verdaderas para I, o sea que todas ellas son simultneamente satisfacibles

Con ello quedar probado que la lista inicial, que forma parte de R, es satisfacible

Prueba Si consideramos la adecuacin ascendente de

las reglas, la verdad para I de las lneas ms cortas implicar la de las premisas ms largas a partir de las cuales se obtuvieron como conclusiones

De este modo, en un nmero finito de pasos (uno para cada regla aplicada), partiendo de la verdad para I de las lneas de longitud 1 2, llegaramos hasta las fbfs iniciales de R

Luego todas las fbf de R son verdaderas para I, y por tanto las fbfs iniciales son satisfacibles

15


9.5. La nocin de decidibilidad. Los rboles como procedimiento decisorio

Decidibilidad Decimos que un sistema formal es decidible

cuando existe un algoritmo, un procedimiento mecnico o computacional, para establecer, en un nmero finito de pasos, si una conclusin se sigue o no de ciertas premisas (y si una proposicin es o no una ley lgica)

Para el caso del mtodo de rboles el metateorema a probar es ste: Decidibilidad: si la lista inicial es finita, la prueba

termina tras un nmero finito de pasos (Se da un paso cada vez que se aplica una regla)

16

Decidibilidad del mtodo de rboles

Los hechos en que se apoya la prueba son los siguientes: El mtodo comienza con nmero finito de fbfs, cada

una de las cuales tiene una longitud finita: un nmero finito de smbolos, contando letras proposicionales, conectivas y parntesis (sin omitir ninguno)

Cada vez que aplicamos una regla, marcando una premisa, introducimos un nmero finito de nuevas lneas, cada una de las cuales es ms corta (en nmero de smbolos) que la premisa

Por tanto, si el rbol no cierra (si cerrase terminara), llegar un momento en que todas las lneas sin marcar, en las ramas abiertas, sern de longitud 1 2 (letras proposicionales o negaciones de letras proposicionales), con lo que el rbol tambin termina

Censos de rboles Definamos el censo de un rbol como una secuencia

infinita de nmeros: el primero es el nmero de lneas sin marcar de longitud 1 que hay en el rbol, el segundo el nmero de lneas sin marcar de longitud 2, y as sucesivamente

Puesto que un rbol slo contiene un nmero finito de lneas, tarde o temprano en esa secuencia slo aparecern ceros hasta el infinito

Cada vez que apliquemos una regla, el censo se har ms pequeo en el sentido siguiente: el nuevo censo contendr un nmero menor que el censo anterior en la posicin ms a la derecha en la que ambos censos difieran

17

Ejemplo 1 rbol:

1. ((p q) r) (prem.) 2. r (prem.) 3. (p q) (con.)

4. (p q) 5. r (de 1) 6. p (de 7. q 4)

8. p 9. q (de 3)

Censos:

Inicio: 0 1 0 0 0 1 0 0 1 0 0

Paso 1: 1 1 0 0 0 2 0 0 0 0 0

Paso 2: 1 3 0 0 0 1 0 0 0 0 0

Paso 3: 1 5 0 0 0 0 0 0 0 0 0

Ejemplo 2

rbol:

1. (p (q r)) (prem.) 2. p (prem.) 3. (p q) (con.) 4. p (de 5. q 3)

Censos:

Inicio: 1 0 0 0 0 0 0 1 1 0 0

Paso 1: 1 1 1 0 0 0 0 0 1 0 0

18

Censos y decidibilidad Cualquier secuencia de censos ms y ms pequeos (en

el sentido indicado) ha de terminar tras un nmero finito de pasos, ya que que las cadenas descendentes siempre son finitas A partir de cualquier censo, es obvio que podemos hacerlo

crecer (ascender, en el sentido indicado) de forma indefinida Pero si en cada paso hacemos descender el censo,

obteniendo uno ms pequeo, tarde o temprano llegaramos al censo nulo (una cadena infinita de ceros)

(Obviamente, en el caso de censos de rboles, el descenso terminara antes, cuando slo sean positivos los dos primeros nmeros de la secuencia, o cuando el rbol se cierre; pero este hecho es irrelevante para la prueba)


9.6. Potencia expresiva de conjuntos de conectivas

19

Adecuacin de conectivas

Se dice que un conjunto de conectivas resulta adecuado cuando un lenguaje formal que cuenta con ellas, y no con otras, tiene la potencia suficiente para expresar todas las funciones de verdad existentes

Ello significa que, para cada funcin de verdad, existe en el lenguaje formal al menos una fbf cuya tabla de verdad coincide justamente con esa funcin

Tipos de funciones veritativas Las funciones de verdad pueden ser

funciones de un argumento, de dos, de tres, etc.

Las conectivas mondicas (como ) formalizan las funciones veritativas de un argumento

Las didicas (como , , y ), las de dos argumentos

Las tridicas (que podramos inventar) formalizaran las de tres argumentos, etc.

20

Funciones de un argumento

Hay exactamente 4 funciones de verdad de un argumento, algunas de las cuales tienen nombre familiar y otras no. Son stas:

Sin nombre Identidad Negacin Sin nombre

V V V F F

F V F V F

Funciones de dos argumentos (1) Hay exactamente 16 funciones de verdad de

dos argumentos, algunas de las cuales tienen nombre y otras no:

f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15 f16

V V V V V V V V V V F F F F F F F F

V F V V V V F F F F V V V V F F F F

F V V V F F V V F F V V F F V V F F

F F V F V F V F V F V F V F V F V F

21

Funciones de dos argumentos (2) De stas, las ms conocidas son:

f2: la disyuncin () f5: el condicional () f7: el bicondicional () f8: la conjuncin ()

Otras son menos conocidas, aunque tambin existen nombres para ellas: f3: el condicional converso f9: la barra de Sheffer () o negacin de la conjuncin f10: la disyuncin exclusiva o negacin del bicondicional () f12: la negacin del condicional f14: la negacin del condicional converso f15: la funcin de Peirce () o negacin de la disyuncin

Finalmente, carecen de nombre: f1, f4, f6, f11, f13 y f16

Infinitas funciones de verdad Hay exactamente 256 funciones de verdad de tres

argumentos, ninguna de las cuales tiene nombre familiar

En general, se cumple la regla de que existen 22n funciones de verdad de n argumentos

Hay, desde luego, una infinita cantidad de diferentes funciones de verdad

Pero formalizando slo unas pocas, e incluso una slo, pueden expresarse todas las dems

El conjunto de conectivas que hemos introducido en nuestro lenguaje formal es excesivo: podramos habrnoslas apaado con un menor nmero de conectivas, sin prdida alguna de potencia expresiva

22

El conjunto {, , } es adecuado Un lenguaje formal que tenga esas tres conectivas

contar entre sus fbfs con fbfs en forma normal disyuntiva (FND)

Una fbf est en forma normal disyuntiva sii es una disyuncin de n disyuntos (n 1), cada uno de los cuales es una conjuncin de m conyuntos (m 1), cada uno de los cuales es una letra proposicional o una letra proposicional precedida de negacin

Demostraremos que, para cualquier funcin de verdad, podemos construir una fbf en FND cuya tabla de verdad coincida con esa funcin, con lo cual quedar probada la adecuacin del conjunto {, , }

Peculiaridades de las fbfs en FND Podemos hablar de disyunciones y conjunciones de

un solo miembro (a las que llamamos degeneradas) ya que ambas conectivas son idempotentes: A A A A A A

Adems, en las FND hacemos uso del hecho de que ambas conectivas cumplen la propiedad asociativa

De la definicin de FND se sigue que Una negacin no puede tener mayor alcance que una

conjuncin ni que una disyuncin Una conjuncin no puede tener mayor alcance que

una disyuncin

23

Ejemplos Fbfs en FND:

(p q) (p r s) (q r) p (q r) p q r p q p

Fbfs que no estn en FND: (p q) r (p q) (p r) p (q r)

Estrategia de la prueba Tomemos una funcin de verdad cualquiera, con un

nmero cualquiera n de argumentos. La tabla correspondiente tendr 2n filas. Consideremos la ltima columna de la tabla; podemos encontrarnos con tres posibilidades: caso 1: que en la ltima columna slo aparezca F caso 2: que haya nicamente una V y el resto sea F caso 3: que haya ms de una V (posiblemente todas)

Mostraremos, para cada uno de estos tres casos, cmo se construye una fbf en FND con n letras proposicionales, y cuya tabla de verdad coincide con la funcin en cuestin

24

Caso 1 (todo F) Entonces

p1 p1 p2 pn es una fbf en FND cuya tabla de verdad coincide con la de la funcin en cuestin

En efecto, p1 p1 siempre tiene el valor F, y por tanto hace que en ninguna valoracin la fbf resulte V

Ejemplo

La fbf

p p q r

est en FND y tiene justamente esa tabla de verdad

V V V F V V F F V F V F V F F F F V V F F V F F F F V F F F F F

25

Caso 2 (slo una V) Sigamos la fila de la tabla que termina en V

Si el primer trmino de esa fila es V, escribamos p1; si es F, escribamos p1

Si el segundo trmino de la fila es V, escribamos p2; si es F, escribamos p2

As sucesivamente hasta llegar al nsimo trmino: si es V, escribamos pn; si es F, escribamos pn

Finalmente formemos la conjuncin de todo lo que hemos escrito

La fbf resultante estar en FND y tendr la misma tabla de verdad que la funcin en cuestin

Ejemplo

La fbf

p q r

est en FND y tiene justamente esa tabla de verdad

V V V F V V F F V F V F V F F F F V V F F V F V F F V F F F F F

26

Caso 3 (ms de una V) Procedamos, igual que en el caso 2, a

construir del mismo modo una fbf para cada fila que adopte el valor V

Formemos luego la disyuncin de todas esas fbfs

La fbf resultante estar en FND y tendr la misma tabla de verdad que la funcin en cuestin

Esto completa la prueba de la adecuacin del conjunto {, , }

Ejemplo 1

La fbf que buscamos es

(p q r) (p q r) (p q r)

V V V F V V F V V F V F V F F F F V V F F V F V F F V F F F F V

27

Ejemplo 2

La fbf que buscamos es

(p q) (p q) (p q) (p q)

V V V V F V F V V F F V

El conjunto {, } es adecuado Partimos de la adecuacin de {, , } Tomemos una funcin de verdad cualquiera, y

construyamos una fbf en FND que tenga la misma tabla de verdad que esa funcin

Eliminemos de esa fbf cada una de las apariciones de y , sustituyndolas por y , de acuerdo con los siguientes esquemas tautolgicos: 1) A B (A B) 2) A B (A B)

El resultado ser una fbf cuyas nicas conectivas sern y y cuya tabla de verdad coincidir con la de la funcin en cuestin. Luego, {, } es adecuado

28

Ejemplo

La fbf en FND que buscamos es (p q) (p q)

Aplicando el esquema (1), obtenemos (p q) (p q)

Y aplicando el esquema (2), resulta finalmente (p q) (p q)

V V V V F F F V V F F F

Los conjuntos {, } y {, } son adecuados Nos apoyamos en ambos casos en la adecuacin de

{, , } {, } es adecuado: basta usar el esquema

tautolgico (A B) (A B)

para eliminar las conjunciones de las fbfs en FND {, } es adecuado: es suficiente usar el esquema

(A B) (A B) para eliminar las disyunciones de las fbfs en FND

(No todos los conjuntos adecuados incluyen la negacin, como veremos a continuacin)

29

Los conjuntos {, }, {} y {} son adecuados {, } es adecuado: partimos ahora de la

adecuacin de {, }, y usamos el esquema A (A (A A))

{} es adecuado: nos apoyamos en la adecuacin de {, }, y usamos los esquemas A (A A) A B ((A A) (B B))

{} es adecuado: se prueba a partir de la adecuacin de {, }, usando los esquemas A (AA) A B ((AA)(BB))

Los dos ltimos metateoremas muestran cmo una sola conectiva puede ser adecuada

Conjuntos no adecuados Los siguientes resultados se basan en que los conjuntos de

conectivas que se citan son incapaces de expresar la funcin veritativa de la negacin: {, } no es adecuado {, } no es adecuado {,} no es adecuado {, } no es adecuado

El resultado siguiente se justifica considerando que el condicional no puede expresarse mediante ninguna combinacin de y : {, } no es adecuado

Finalmente, como de las otras tres funciones de verdad de un argumento, slo la de la identidad puede expresarse en trminos de la negacin (mediante una doble negacin), tenemos que {} no es adecuado

30

Las conectivas de Sheffer y Peirce Especial inters tiene este ltimo metateorema:

Las nicas conectivas didicas que resultan adecuadas por s solas son y

La prueba procede por reduccin al absurdo Supongamos que existiera otra conectiva didica que

fuera adecuada por s sola, y llammosla * Si * ha de ser capaz de expresar la negacin,

entonces debe cumplirse A (A * A)

Esto nos permite afirmar que su tabla de verdad ha de arrojar F como resultado de la primera fila, y V como resultado de la cuarta

La (supuesta) conectiva *

Con respecto a las filas segunda y tercera, tenemos cuatro casos a considerar:

Caso 1: que ambas den V Caso 2: que ambas den F Caso 3: que la segunda d V y la tercera F Caso 4: que la segunda d F y la tercera V

A B A * B V V F V F ? F V ? F F V

lógica i - diapositivas (um)

Documents