logica modal

Logica modal

Ramon Jansana

Universitat de Barcelona

Indice general

Capıtulo 1. Introduccion 5

Capıtulo 2. El lenguaje de la logica modal 91. Vocabulario 92. Definicion de formula 93. Instancias de sustitucion 104. El principio de induccion 105. Definicion por induccion (o recursion) 106. Ejercicios 11

Capıtulo 3. La Semantica relacional 131. Modelos y marcos 132. Formulas validas 153. Formulas equivalentes 174. Relaciones de consecuencia 185. Secuentes validos 196. Ejercicios 20

Capıtulo 4. La logica clasica proposicional 231. Lenguaje formal 232. Semantica 233. Calculo de secuentes 24

Capıtulo 5. Calculo de secuentes para la logica modal 351. El calculo 352. Relaciones de deducibilidad 373. Propiedades basicas de ` 374. Conjuntos consistentes de formulas 385. El modelo canonico 39

Capıtulo 6. Algunos resultados de correspondencia 43

Capıtulo 7. Logicas modales normales 451. Extensiones axiomaticas del calculo LKK 462. Axiomatizaciones tipo Hilbert de las logicas modales normales 473. Relaciones de consecuencia 494. Relaciones de deducibilidad 49

Capıtulo 8. Algunos resultados de correspondencia 51

3

4 Indice general

Capıtulo 9. Teoremas de completud 531. L-teorıas, conjuntos L-consistentes, L-teorias primas,

relativamente maximales y L-consistente maximales 542. El modelo canonico 573. Los teoremas de completud 59

Capıtulo 10. Logica modal cuantificacional 631. Sintaxis 632. Las interpretaciones del lenguaje 643. Semantica de modelos con dominio constante: cuantificacion

sobre posibles 684. Semantica de modelos con dominio variable: cuantificacion sobre

actuales y designacion rıgida 71

Capıtulo 1

Introduccion

El inicio de la logica modal se puede retrotraer al analisis de Aristotelesde los enunciados que contienen los terminos “necesario” y “posible”. Loslogicos medievales continuaron el analisis de estos terminos pero estudiarontambien otras modalidades como por ejemplo las epistemicas. La logica mo-dal moderna se ocupo en sus comienzos (C.I. Lewis, Hugh McColl...) de lasmodalidades “necesario” y “posible” tratadas por Aristoteles, pero prontose ocupo de otras modalidades.

Hoy en dıa lo que se conoce, en sentido amplio, como logica modal tratade una variedad de modalidades que incluye, ademas de las tradicionalmen-te consideradas, otras modalidades que han surgido en las ciencias de lacomputacion y en el estudio de los fundamentos de las matematicas.

Brevemente podemos decir queuna modalidad es una expresion que aplicada a una oracionS proporciona una nueva oracion sobre el modo en que S esverdadera o sobre el modo en que es aceptada.

Por ejemplo, sobre cuando es verdadera, donde es verdadera, como es verda-dera, en que circunstancias es verdadera; o sobre el modo en que un sujetoo colectividad la acepta, por ejemplo, como conocida, creıda, demostrada,etc.

Las modalidades usualmente se dan en pares de modalidades duales(“necesario” / “posible”, “siempre” / “alguna vez”): “necesario” equivale a“no es posible que no”, “siempre” equivale a “no es el caso que alguna vezno”.

La logica clasica es extensional. Esto significa que vale el principio desustitucion de equivalentes materiales, o sustitucion salva veritate, conocidotambien como principio de extensionalidad:

si dos enunciados β y γ tienen el mismo valor de verdad,entonces en todo enunciado α(p/β) en el que aparezca β, siβ se sustituye por γ entonces se obtiene un nuevo enunciado,α(p/γ), con el mismo valor de verdad que el inicial (α(p/β)).

Las modalidades infringen el principio de extensionalidad. Veamos algunosejemplos.

1. La oracion (3) no se sigue de (1) y (2):(1) 3 + 2 = 5 si y solo si Juan Carlos I es rey de Espana(2) Es necesario que 3 + 2 = 5

5

6 1. INTRODUCCIoN

(3) Es necesario que Juan Carlos I es rey de Espana.2. La oracion (6) no se sigue de (4) y (5):

(4) Felipe de Borbon es rey de Espana si y solo si Parıs esta enAustralia

(5) En el futuro Felipe de Borbon sera rey de Espana(6) En el futuro Parıs estara en Australia

3. Del mismo modo, la oracion (9) no se sigue de (7) y (8):(7) El autor de El Quijote es el autor de El Quijote si y solo si

el autor de El Quijote es Cervantes(8) Juan cree que el autor de El Quijote es el autor de El Quijote(9) Juan cree que el autor de El Quijote es Cervantes.

4. La oracion (12) no se sigue de (10) y (11)(10) 3 + 2 = 5 si y solo si no hay un numero primo mayor que

todos los demas numeros primos(11) Juan sabe que 3 + 2 = 5(12) Juan sabe que no hay un numero primo mayor que todos

los demas numeros primos.La razon de que el principio de extensionalidad falle en los ejemplos 1

y 2 se explica por el hecho de que el valor de verdad de las oraciones (2),(3), (5), (6) no depende, a diferencia de lo que ocurre con las oraciones (1) y(4), unicamente de lo que ocurre en la situacion en que se evalua la oracion,sino que depende tambien de lo que ocurre en las situaciones alternativaspertinentes en cada caso. Por ejemplo, el valor de verdad de (3) no dependesolo de si Juan Carlos I es o no rey de Espana, depende de si lo es en todaslas situaciones alternativas a la actual. Que (3) sea verdadero significa queen cualquier situacion posible (no solo en la actual) Juan Carlos I es rey deEspana. Puesto que esto no es ası, (3) es falsa. Analogamente, el valor deverdad de (6) no depende de si ahora Parıs esta o no en Australia, dependede si en algun momento futuro sera el caso que Parıs esta en Australia.Puesto que esto no es ası, (6) es falsa.

Un listado de modalidades.Modalidades aleticas: necesario, posible, imposibleModalidades temporales: siempre, nunca, siempre en el pasado, siem-pre en el futuro, en algun momento futuro, en algun momento pasa-do, a partir de ahora, etc.Modalidades deonticas: es obligatorio, esta permitido, esta prohibi-do, es legal, etc.Modalidades doxasticas: j cree que, se cree que.Modalidades epistemicas: j sabe que, se sabe que, todos saben que,etc.Modalidades de la logica dinamica: despues de que la computacionse acabe, durante la computacion, el programa permite que, etc.Modalidades de la metalogica: es valido, es satisfacible, es demostra-ble, es consistente, es demostrable en la teorıa T .

1. INTRODUCCIoN 7

Modalidades espaciales: en todas partes, en alguna parte, etc.

La semantica relacional. La semantica relacional para las logicas delas diferentes modalidades considera seriamente el analisis que hemos ex-puesto brevemente de porque no vale el principio de sustitucion de equiva-lentes materiales para enunciados con modalidades. Toma en serio desde unpunto de vista matematico la idea de situacion alternativa y la idea de que elvalor de verdad de un enunciado con modalidades en la situacion actual de-pende del valor de verdad de alguno o todos sus componentes es situacionesalternativas.

Dada una modalidad 2 y un enunciado ϕ (interpretado en la situacionactual), el valor de verdad del enunciado 2ϕ en la situacion actual w, o en elestado actual w, depende de lo que ocurre en situaciones (o estados) alter-nativas(os) a w. Las situaciones alternativas, o posibles, se representan ensemantica relacional por puntos; en contextos filosoficos estos puntos se lla-man a menudo mundos posibles y en contextos de ciencias de la computacionestados. La relacion de ser una alternativa se representa por una relacionentre puntos. Por esta razon se conoce a esta semantica como semanticarelacional. En los cırculos de filosofıa analıtica se la conoce tambien comosemantica de mundos posibles.

La semantica de mundos posibles para las modalidades aleticas la intro-dujo Carnap, y para las modalidades temporales Prior. La semantica relacio-nal tal como la formulamos hoy en dıa la introdujeron, independientementeuno de otro, Kripke, Hintikka y Kanger, aunque el tratamiento de Kripkees el mas general. Implıcitamente se halla en un artıculo mucho anterior deJonsson y Tarski.

La semantica relacional tal como la presento Kripke es completamentegeneral, en el sentido de que es aplicable a multitud de modalidades. En estecaso los modelos constan de:

1. Un conjunto no vacıo de puntos que representan las situaciones per-tinentes. Cada una de ellas puede ser la actual.

2. Una relacion R entre puntos que indica que situaciones son alternati-vas a cuales.

3. Una interpretacion que en cada situacion establece que enunciados sonverdaderos y cuales falsos, de modo que 2ϕ es verdadero en una situacionw sii ϕ es verdadero en toda situacion w′ tal que wRw′.

A pesar de que hemos usado la palabra ‘situacion’ mas a menudo que laexpresion ‘mundo posible’, ambas expresiones se han usado metaforicamente,como por otra parte es muy comun. Tambien es frecuente utilizar con elmismo proposito la expresion ‘estado de cosas’ (state of affairs). Con el usode estas expresiones no se pretende sugerir ni mucho menos que se disponede una concepcion de lo que es una situacion o lo que es un mundo posible, nique disponer de una tal concepcion sea necesario para elaborar la semanticarelacional. De hecho, la semantica relacional es compatible con diferentesconcepciones de lo que puede ser desde un punto de vista metafısico un

8 1. INTRODUCCIoN

mundo posible, incluso es compatible con concepciones que niegan, desdeeste punto de vista metafısico, los mundos posibles.

Conviene observar una caracterıstica importante de la semantica rela-cional. En cada punto, bajo cada interpretacion, cada formula tiene un valorde verdad (es verdadera o falsa). Debido a esta caracterıstica a veces pue-de parecer mas apropiada la metafora de los mundos posibles que la de lassituaciones puesto que, segun una actitud realista, en el mundo esta deter-minado de cada enunciado si es verdadero o falso, pero en una situacion notiene porque ser ası.

Capıtulo 2

El lenguaje de la logica modal

El lenguaje de la logica modal proposicional es una extension del len-guaje de la logica proposicional clasica. Se obtiene anadiendo a este dosoperadores modales. Las conectivas ∧,∨,→ de la logica clasica y las cons-tantes proposicionales ⊥,> se siguen interpretando intuitivamente del modoen que se hace en logica proposicional, es decir como funciones de valoresde verdad. Los operadores modales pueden interpretarse intuitivamente demuchas maneras, segun la modalidad que se pretenda tratar. Uno de losoperadores se interpreta como una de las modalidades y el otro como lamodalidad dual. Convencionalmente se utiliza el cuadrado 2 para la mo-dalidad universal y el diamante 3 para la existencial. Ası, si nos importanlas modalidades aleticas, 2 se interpretara como “es necesario” y 3 se in-terpretara como “es posible”; si nos importan las modalidades temporales2 se interpretara por ejemplo como “siempre en el futuro” y entonces 3 seinterpretara como “en algun momento futuro”.

1. Vocabulario

El lenguaje formal de la logica modal proposicional consta pues del si-guiente vocabulario:

1. Variables proposicionales: p, q, r, p1, q1, r1, . . .2. Constantes proposicionales: ⊥,>3. Conectivas: ∧,∨,→4. Operadores modales: 2, 3

5. Parentesis

Asumimos una enumeracion fijada p0, p1, p2, . . . de la s variables propo-sicionales.

2. Definicion de formula

Las expresiones son las sucesiones finitas de elementos del vocabulario.Las formulas atomicas son las variables proposicionales y las constantesproposicionales. Las formulas se definen de acuerdo con las siguientes reglas:

1. Toda formula atomica es una formula,2. Si α es una formula, lo son 2α, y 3α3. Si α y β son formulas, tambien lo son (α ∧ β), (α ∨ β) y (α→ β).

9

10 2. EL LENGUAJE DE LA LoGICA MODAL

El sımbolo ↔ se define del modo usual en logica clasica como

ϕ↔ ψ := (ϕ→ ψ) ∧ (ψ → ϕ)

La negacion de una formula α es la formula α→ ⊥ que abreviamos con¬α.

El arbol genealogico de una formula se define de modo analogo a como sehace en logica proposicional (no modal), ası como el concepto de subformula.

Una formula de la forma 2ϕ se lee “cuadrado ϕ” y a veces “es necesarioque ϕ” aunque no consideremos ninguna interpretacion intuitiva del mismo.Nosotros optaremos por la primera lectura. Analogamente una formula dela forma 3ϕ se lee “rombo ϕ”, “diamante ϕ” y tambien, a veces, “es posibleque ϕ”. Como en el caso del cuadrado optaremos por la primera lectura.

3. Instancias de sustitucion

Dada una formula α, una instancia de sustitucion de α es cualquierformula que se obtiene reemplazando simultaneamente alguna o todas lasletras proposicionales que aparecen en α por formulas. Ası (r ∧ p) → ¬res una instancia de sustitucion de p → q. Tambien es una instancia desustitucion de las formulas (r ∧ q)→ p y de (p ∧ q)→ r, entre otras.

Si β es una formula, con β(p0/α0, . . . , pn/αn) nos referiremos a la ins-tancia de sustitucion de β que se obtiene reemplazando en β las letras pro-posicionales p0, . . . , pn por α0, . . . , αn respectivamente.

4. El principio de induccion

Proposicion 1 (Principio de induccion). Si P es una propiedad tal que1. toda variable proposicional tiene P ,2. ⊥ y > tienen P ,3. si ϕ y ψ tienen P , entonces (ϕ ∨ ψ) , (ϕ ∧ ψ) y (ϕ→ ψ) tienen P ,4. si ϕ tiene P , entonces 3ϕ y 2ϕ tienen P ,

entonces toda formula tiene P .

5. Definicion por induccion (o recursion)

Proposicion 2. Sea D un conjunto no vacıo, F2 y F3 funciones de Den D, G∨, G∧, G→ funciones de D×D en D y a, b ∈ D. Para cada funcion hdel conjunto de las variables proposicionales en D, existe una unica funcionh : Fm→ D tal que

1. h(p) = h(p), para cada letra proposicional p,2. h(⊥) = a3. h(>) = b4. h((ϕ ∨ ψ)) = G∨(〈h(ϕ), h(ψ)〉)5. h((ϕ ∧ ψ)) = G∧(〈h(ϕ), h(ψ)〉)6. h((ϕ→ ψ)) = G→(〈h(ϕ), h(ψ)〉)7. h(2ϕ) = F2(h(ϕ)),8. h(3ϕ) = F3(h(ϕ)).

6. EJERCICIOS 11

6. Ejercicios

1. Interpretando 2 como “es necesario” y su dual 3 como “es posible”,formalice:

1. Es posible que el Barca gane La Liga, pero no es necesario.2. Es posible que si el Barca gana La Liga, pierda la “Champions”.3. Si es posible que el Barca gane La Liga, es necesario que la pierda

el Valencia.4. Si el Barca pierde La Liga, es necesario que la gane el Valencia.5. No es posible que el Barca gane La Liga, pero es posible que gane

la copa de la UEFA.6. Es posible que el Valencia gane La Liga y posiblemente es necesario

que sea ası.7. Es imposible que que el Barca y el Valencia ganen La Liga.

2. Interpretando 2 como “siempre en el futuro” y su dual 3 como “algunavez en el futuro”, formalice:

1. El Barca ganara siempre La Liga.2. Si el Barca gana alguna vez La Liga, siempre perdera la “Cham-

pions”.3. Siempre ocurrira que si el Barca gana La Liga, la perdera el Valencia.4. Si el Barca pierde alguna vez La Liga, siempre la ganara el Valencia.5. No siempre ocurrira que el Barca gane La Liga, pero alguna vez

ganara la copa de la UEFA.6. No siempre ocurrira que el Barca o el Valencia ganen La Liga.

Capıtulo 3

La Semantica relacional

Presentamos la semantica relacional para el lenguaje de la logica modalproposicional. Primero definiremos los conceptos de marco y de modelo;despues, para cada modelo, definiremos la relacion de verdad de una formulaen un punto del modelo.

1. Modelos y marcos

Definicion 3. Un marco (de Kripke) es una estructura F = 〈W,R〉donde

1. W es un conjunto no vacıo y2. R es una relacion binaria en W .

Los elementos de W se llaman puntos, ındices, mundos o estados del marco.Utilizaremos indistintamente todos estos terminos.

Definicion 4. Un modelo (de Kripke) es una estructuraM = 〈W,R, V 〉,donde

1. 〈W,R〉 es un marco y2. V es una funcion que asigna a cada letra proposicional un subconjunto

de W .

Se dice que la funcion V es una asignacion o una valoracion en el marco〈W,R〉, y que el modelo 〈W,R, V 〉 es un modelo sobre 〈W,R〉.

Dado un modelo M = 〈W,R, V 〉, la definicion inductiva de formulaverdadera en un punto w ∈W es la siguiente:

M, w |= p sii w ∈ V (p), para cada letra proposicional p,M, w |= > ,M, w 6|= ⊥ ,M, w |= (ϕ1 ∧ ϕ2) sii M, w |= ϕ1 y M, w |= ϕ2,M, w |= (ϕ1 ∨ ϕ2) sii M, w |= ϕ1 o M, w |= ϕ2,M, w |= (ϕ1 → ϕ2) sii M, w 6|= ϕ1 o M, w |= ϕ2,M, w |= 2ϕ sii para cada v ∈W tal que wRv, M, v |= ϕ,M, w |= 3ϕ sii existe v ∈W tal que wRv y M, v |= ϕ.

De la definicion se sigue que

M, w |= ¬ϕ sii M, w 6|= ϕ

13

14 3. LA SEMaNTICA RELACIONAL

Si ϕ es verdadera en un punto se dice que el punto satisface la formulao que la formula es satisfecha en el punto. Con V (ϕ) se denota el conjuntode puntos en que ϕ es verdadera, es decir

V (ϕ) := {w ∈W :M, w |= ϕ}.

Ejemplos.1. Consideremos el modelo de diagrama

p, q1 ll

p, q 2

<<yyyyyyyyy// 3 q

aaBBBBBBBB

La formula 2p es verdadera en los puntos 1 y 3.La formula 3p es verdadera en los puntos 1, 2 y 3.La formula 2q es verdadera en los puntos 1, 2 y 3.La formula 3q es verdadera en los puntos 1, 2 y 3.La formula 23p es verdadera en los puntos 1, 2 y 3.La formula 32p es verdadera en los puntos 1, 2 y 3.La formula 2(p→ q) es verdadera en los puntos 1, 2 y 3.La formula 2(p→ 2q) es verdadera en los puntos 1, 2 y 3.

2. Consideremos el modelo de diagramap1 ee

p, q 2

==||||||||||// 3 q

La formula 2p es verdadera en los puntos 1 y 3.La formula 3p es verdadera en los puntos 1 y 2.La formula 2q es verdadera en el punto 3.La formula 3q es verdadera en el punto 2.La formula 23p es verdadera en los puntos 1 y 3.La formula 32p es verdadera en los puntos 1 y 2.La formula 2(p→ q) es verdadera en el punto 3.La formula 2(p→ 2q) es verdadera en el punto 3.

3. En el modelo de diagramap1 ee

��???

????

??

p, q 2

==||||||||||// 3 q oo

la formula 2p→ 32q es verdadera en todos los puntos.4. En el modelo de diagrama

p199 // 2 eeoo

2. FoRMULAS VaLIDAS 15

la formula 3p→ 2p es falsa en todos los puntos.

2. Formulas validas

Si ϕ es verdadera en todo punto de un modeloM, es decir si V (ϕ) = W ,se dice que es valida en M.

Con Val(M) denotaremos el conjunto de formulas validas en M.Dado un marco F , se dice que una formula ϕ es valida en F si ϕ es

valida en todo modelo 〈F , V 〉 sobre F .Con Val(F) denotaremos el conjunto de formulas validas en F .Una formula es valida en una clase de modelos M si es valida en cada

uno de sus elementos. Analogamente se dice que una formula es valida enuna clase F de marcos. Denotaremos con Val(M) el conjunto de las formulasvalidas en todos los modelos pertenecientes a M y con Val(F) la clase detodas las formulas validas en todos los marcos elemento de F.

La semantica relacional obliga a que ciertas formulas sean validas entodo modelo y que los conjuntos de formulas validas en un modelo y deformulas validas en un marco tengan ciertas propiedades de clausura.

Lema 5. Sea 〈W,R, V 〉 un modelo, sean β0, . . . , βn formulas cualesquieray consideremos la asignacion V ∗ en 〈W,R〉 definida por

V ∗(pi) = V (βi)

para cada i ≤ n y si i 6≤ n, V ∗(pi) = V (pi). Entonces, para toda formula α,

V (α(p0/β0, . . . , pn/βn)) = V ∗(α).

Demostracion. Por induccion.a) Si α es una variable proposicional q y q es diferente de p0, . . . , pn,

entonces α(p0/β0, . . . , pn/βn) = q y V ∗(q) = V (q). Por tanto tenemos lodeseado. Si q = pi para algun i ≤ n, entonces α(p0/β0, . . . , pn/βn) = βi yV ∗(q) = V ∗(pi) = V (βi), con lo cual obtenemos tambien lo deseado.

b) Si α es ⊥ o >, entonces α(p0/β0, . . . , pn/βn) = α y obtenemos lodeseado.

c) Supongamos como hipotesis inductiva que V (α(p0/β0, . . . , pn/βn)) =V ∗(α) y V (β(p0/β0, . . . , pn/βn)) = V ∗(β). Veamos que

V ((α ∧ β)(p0/β0, . . . , pn/βn)) = V ∗(α ∧ β).

Puesto que

(α ∧ β)(p0/β0, . . . , pn/βn) = α(p0/β0, . . . , pn/βn) ∧ β(p0/β0, . . . , pn/βn)

y ademas

V (α(p0/β0, . . . , pn/βn) ∧ β(p0/β0, . . . , pn/βn)) =

V (α(p0/β0, . . . , pn/βn)) ∩ V (β(p0/β0, . . . , pn/βn)),utilizando la hipotesis inductiva obtenemos

V (α(p0/β0, . . . , pn/βn)∧β(p0/β0, . . . , pn/βn)) = V ∗(α)∩V ∗(β) = V ∗(α∧β).

Por tanto, V ((α ∧ β)(p0/β0, . . . , pn/βn)) = V ∗(α ∧ β).


De modo analogo se tratan los casos de (α ∨ β) y de (α→ β).d) Supongamos como hipotesis inductiva que V (α(p0/β0, . . . , pn/βn)) =

V ∗(α). Veamos que V ((2α)(p0/β0, . . . , pn/βn)) = V ∗(2α). Por un lado

(2α)(p0/β0, . . . , pn/βn) = 2α(p0/β0, . . . , pn/βn).

Por otro,V (2α(p0/β0, . . . , pn/βn)) =

{w ∈W : (∀v ∈W )(wRv ⇒ v ∈ V (α(p0/β0, . . . , pn/βn))}.Aplicando la hipotesis inductiva,

V (2α(p0/β0, . . . , pn/βn)) = {w ∈W : (∀v ∈W )(wRv ⇒ v ∈ V ∗(α)}.

Ası,V (2α(p0/β0, . . . , pn/βn)) = V ∗(2α).

Por tanto, V ((2α)(p0/β0, . . . , pn/βn)) = V ∗(2α).De modo analogo se trata el caso de 3α, es decir se demuestra que

V ((3α)(p0/β0, . . . , pn/βn)) = V ∗(3α). QED

Lema 6. Si α es una formula en la que no ocurren los sımbolos 2 y 3,entonces α es una tautologıa si y solo si es valida en todo modelo.

Demostracion. Supongamos que α es una tautologıa. SeaM = 〈W,R, V 〉un modelo y sea w ∈W . Consideremos la asignacion de valores de verdad vdefinida mediante

v(p) = 1 sii w ∈ V (p)

para cada letra proposicional p. Es inmediato ver que una formula cualquieraβ en la que no ocurren ni 2 ni 3 es verdadera con la asignacion de valoresde verdad v si y solo si w ∈ V (β). Puesto que α es verdadera con cualquierasignacion, lo es con v, Por tanto w ∈ V (α). Puesto que w es un elementoarbitrario de W , concluimos que V (α) = W , Ası, α es valida en M.

Supongamos ahora que α es valida en todo modelo. Sea v una asignacionde valores de verdad. Consideremos el modelo M = 〈{a}, ∅, V 〉 donde V sedefine mediante V (p) = {a} si y solo si v(p) = 1, para cada letra proposi-cional p. Es facil ver que en toda formula β en la que ni 2 ni 3 ocurren,V (β) = {a} si y solo si β es verdadera con la asignacion de valores de verdadv. Por tanto, puesto que α es valida en todo modelo, α es valida enM. Ası,V (α) = {a}. Por tanto α es verdadera con la asignacion v. Concluimos queα es una tautologıa. QED

Proposicion 7.1. Las formulas de la forma 2(ϕ→ ψ)→ (2ϕ→ 2ψ) son verdaderas

en todo punto de todo modelo, por tanto son validas en todo modelo.2. Las formulas de la forma de una tautologıa (las instancias de susti-

tucion de tautologıas) son validas en todo modelo.3. Si ϕ es valida en un modelo, lo es 2ϕ. Ası, para cada modelo M, siϕ ∈ Val(M), entonces 2ϕ ∈ Val(M).

3. FoRMULAS EQUIVALENTES 17

4. Si ϕ es valida en un marco F , entonces toda instancia de sustitucionσϕ de ϕ es valida tambien en F . Ası, si ϕ ∈ Val(F) y σϕ es unainstancia de sustitucion de ϕ cualquiera, entonces σϕ ∈ Val(F)

5. Las formulas de la forma 2α ↔ ¬3¬α, y las de la forma 3α ↔¬2¬α son verdaderas en todo punto de todo modelo, por tanto sonvalidas.

Demostracion. 1. Fijemos un modelo M = 〈W,R, V 〉. Consideremosun punto w ∈ W . Para demostrar que 2(ϕ → ψ) → (2ϕ → 2ψ) es verda-dera en w, basta demostrar que en caso de que el antecedente 2(ϕ→ ψ) seaverdadero en w, lo es tambien el consecuente (2ϕ→ 2ψ). Supongamos puesque M, w |= 2(ϕ→ ψ). Para ver que M, w |= 2ϕ→ 2ψ, supongamos queM, w |= 2ϕ. Bajo esta suposicion debemos ver que M, w |= 2ψ, es decirque para todo v ∈ W tal que wRv ocurre que M, v |= ψ. Para demostrarlosea v ∈W tal que wRv. Puesto queM, w |= 2(ϕ→ ψ), (i)M, v |= (ϕ→ ψ)y puesto queM, w |= 2ϕ, (ii)M, v |= ϕ. Por tanto, por (i) y (ii) obtenemosque M, v |= ψ, que es lo que deseabamos. Ası, M, w |= 2ψ.

2. Supongamos que α es una instancia de sustitucion de una tautologıa.Supongamos que α es β(p0/β0, . . . , pn/βn) donde β es un tautologıa. Consi-deremos un modelo M = 〈W,R, V 〉 arbitrario. Consideremos la asignacionV ∗ en 〈W,R〉 definida por V ∗(pi) = V (βi) para cada i ≤ n y tal que i 6≤ n,V ∗(pi) = V (pi). Por el lema 5,

V (β(p0/β0, . . . , pn/βn)) = V ∗(β).

Puesto que β es una tautologıa, V ∗(β) = W . Por tanto,

V (β(p0/β0, . . . , pn/βn)) = W.

Ası, α es valida en M.3. Supongamos que ϕ es valida en un modelo M = 〈W,R, V 〉. Esto

significa que para todo w ∈ W , M, w |= ϕ. Por tanto, trivialmente, dadow ∈ W , para todo v ∈ W tal que wRv ocurre que M, v |= ϕ. Ası, M, w |=2ϕ.

4. Debe utilizarse el lema 5. Se deja como ejercicio.5. Se deja como ejercicio. QED

3. Formulas equivalentes

Diremos que dos formulas son equivalentes si en todo modelo ambasson verdaderas en exactamente los mismos puntos.

Proposicion 8. Para toda formula ϕ,

1. 2ϕ es equivalente a ¬3¬ϕ,2. 3ϕ es equivalente a ¬2¬ϕ.

Demostracion. Se deja como ejercicio. QED


Proposicion 9. Si α y β son formulas en las que no ocurren ni 2

ni 3 y son logicamente equivalentes en el sentido de la logica proposi-cional clasica, entonces para cualesquiera letras proposicionales p0, . . . , pn

y cualesquiera formulas modales β0, . . . , βn, las instancias de sustitucionα(p0/β0, . . . , pn/βn) y β(p0/β0, . . . , pn/βn) son formulas equivalentes.

Demostracion. Supongamos que α y β son formulas en las que noocurren ni 2 ni 3 y son logicamente equivalentes en el sentido de la logi-ca proposicional clasica. Ası, α ↔ β es una tautologıa. Por tanto todainstancia de sustitucion de α ↔ β es valida en todo modelo M. Ası,α(p0/β0, . . . , pn/βn) ↔ β(p0/β0, . . . , pn/βn) es valida en todo modelo M.Se sigue que en todo modelo M las formulas

α(p0/β0, . . . , pn/βn) y β(p0/β0, . . . , pn/βn)

son verdaderas en los mismos puntos, por lo que son equivalentes. QED

Proposicion 10 (Sustitucion de equivalentes). Para cualesquiera formu-las α, β y γ, si β es equivalente a γ, entonces para toda variable p, α(p/β)es equivalente a α(p/γ)

Demostracion. Se demuestra por induccion. Se deja como ejercicio.QED

4. Relaciones de consecuencia

La relacion de consecuencia local se define como sigue. Sean ϕ unaformula modal y Σ un conjunto de formulas modales. Se dice que ϕ es con-secuencia local de Σ, y escribimos Σ |=l ϕ, si para todo modelo 〈W,R, V 〉)y para todo w ∈W tal que para cada ψ ∈ Σ, w sat. ψ ocurre que w sat. ϕ.

La relacion de consecuencia global se define como sigue. Sean ϕ unaformula modal y Σ un conjunto de formulas modales. Se dice que ϕ esuna consecuencia global de Σ, y escribimos Σ |=g ϕ, si para todo modelo〈W,R, V 〉 tal que para cada ψ ∈ Σ, 〈W,R, V 〉 |= ψ ocurre que 〈W,R, V 〉 |= ϕ.

Las dos relaciones de consecuencia tienen las mismas consecuencias apartir del conjunto vacıo.

Proposicion 11. Para toda formula ϕ,

|=l ϕ sii |=g ϕ.

Demostracion. Observemos que por una parte, |=l ϕ si y solo si paratodo modelo M y todo w ∈ W , M.w |= ϕ, y que por otra parte, |=g ϕ si ysolo si para todo modelo M ϕ es valida en M. Por tanto, es evidente que|=l ϕ si y solo si |=g ϕ. QED

Sin embargo ambas relaciones de consecuencia son diferentes. Por ejem-plo

p |=g 2p pero p 6|=l 2p.

5. SECUENTES VaLIDOS 19

5. Secuentes validos

Como en logica proposicional clasica, un secuente esta formado por unpar de conjuntos finitos Γ, ∆, que escribimos Γ � ∆.

Un secuente Σ�∆ es valido en un modelo M si para cada punto w ∈Wen el que todas las formulas en Σ son verdaderas, ocurre que alguna formulaen ∆ es verdadera. Un secuente es valido, si es valido en todo modelo.

Una regla entre secuentes es valida si para todo modelo en el que sonvalidos los secuentes a los que se aplica la regla, es valido el secuente que seobtiene por la aplicacion de la regla.

Dada un conjunto Σ de formulas consideraremos los conjuntos de formu-las

2Σ := {2ϕ : ϕ ∈ Σ} y 3Σ := {3ϕ : ϕ ∈ Σ}.

Proposicion 12. Los secuentes1. 2(ϕ→ ψ) � 2ϕ→ 2ψ2. 2(ϕ ∨ ψ) � 2ϕ ∨3ψ3. 2ϕ ∧3ψ � 3(ϕ ∧ ψ)

son validos


Proposicion 13. La reglaΣ, ϕ� ∆

2Σ,3ϕ� 3∆es valida. En particular lo es

ϕ� ψ

3ϕ� 3ψ.

Demostracion. Supongamos que M = 〈W,R, V 〉 es un modelo en elque es valido el secuente Σ, ϕ � ∆, esto significa que para cada w ∈ W enel que las formulas de Σ y ϕ sean verdaderas, alguna de las formulas en ∆es verdadera. Veamos que 2Σ,3ϕ� 3∆ es valido enM. Supongamos paraello que w ∈ W es tal que para cada α ∈ Σ, 2α es verdadera en w y 3ϕes verdadera en w. Esto ultimo implica que hay v ∈ W tal que wRv y ϕes verdadera en v. Puesto que wRv, las formulas de Σ son verdaderas env. Por tanto, puesto que Σ, ϕ � ∆ es valido en M, alguna formula β ∈ ∆debe ser verdadera en v. Ası, 3β es verdadera en w. Concluimos pues que2Σ,3ϕ� 3∆ es valido en M. QED

Proposicion 14. La reglaΣ � ∆, ϕ

2Σ � 3∆,2ψes valida. En particular lo es

ϕ� ψ

2ϕ� 2ψ.



Proposicion 15. Sea Σ � ϕ un secuente. Σ � ϕ es valido sii Σ |=l ϕ.

Demostracion. Se sigue inmediatamente de las definiciones. QED

6. Ejercicios

1. Consideremos el modelo de diagramap199 //

q2oo

Decida para cada una de las formulas siguientes si es verdadera en1 y si es verdadera en 2.

(a) 2p→ 22p(b) ¬2p(c) p→ 32p(d) ¬2q → 2¬p(d) 3q → ¬3q

2. Consideremos el modelo 〈W,R, V 〉 dondeW = {1, 2, 3, 4},R = {〈1, 2〉, 〈2, 3〉, 〈3, 1〉, 〈4, 2〉}V (p) = {1, 3}, V (q) = {1, 2}(a) Dibuje el modelo.(b) De cada una de las siguientes formulas diga en que puntos

es verdadera:a) 2q,b) 2¬(p→ ¬q),c) 2(p ∨ q) ∨3(p ∧ q),d) 32(p ∨ q),e) 2p ∧3q.

(c) Decida para cada una de las formulas siguientes si es validaen el modelo:a) 32p ∨332p,b) 2p→ ¬p,c) (p→ 3p) ∧ (q → 3q),d) 3(p ∨ ¬p)→ 2(p ∨ ¬q).

(d) Decida si las formulas 2p→ 3p y 332p→ p son validas enel marco del modelo.

3. Es valido el secuente p� 2p? Y el secuente p� 3p?4. Demuestre que 2α es equivalente a ¬3¬α.5. Demuestre el apartado 4 de la proposicion 7.6. Demuestre el apartado 4 de la proposicion 7.7. Demuestre la proposicion 8, el principio de sustitucion de equivalen-

tes.8. Demuestre la proposicion 10.9. Demuestre la proposicion 12.

6. EJERCICIOS 21

10. Demuestre que las formulas 2(3p→ q) y 2(2¬p∨ q) son equivalen-tes.

Capıtulo 4

La logica clasica proposicional

Dedicamos este capıtulo a presentar la logica proposicional clasica. Pri-mero introduciremos el lenguaje. Hemos optado por tener en el lenguaje dosconstantes proposicionales, una se interpreta siempre como verdadera y laotra siempre como falsa. Este recurso permite introducir la negacion comouna conectiva definida y comparar mejor la logica proposicional clasica conla logica intuicionista a traves de los calculos de secuentes para cada una deellas introducidos por Gentzen.

La semantica que presentamos es la habitual: la de asignaciones de valo-res de verdad. El calculo es el calculo de secuentes de Gentzen. El capıtulofinaliza con la demostracion del teorema de completud.

1. Lenguaje formal

El lenguaje formal que hemos escogido para presentar la logica proposi-cional consta del siguiente vocabulario:

1. Variables proposicionales: p, q, r, p1, q1, r1, . . .2. Conectivas: ∧,∨,→3. Constantes proposicionales: ⊥,>4. Parentesis

Las expresiones son las sucesiones finitas de elementos del vocabulario.Las formulas atomicas son las variables proposicionales y las constantesproposicionales. Las formulas se definen de acuerdo con las siguientes reglas:

1. Toda formula atomica es una formula,2. Si ϕ y ψ son formulas, tambien lo son (ϕ ∧ ψ), (ϕ ∨ ψ) y (ϕ→ ψ).

La negacion se introduce del siguiente modo. Si ϕ es una formula

¬ϕ := (ϕ→ ⊥)

donde := significa que la expresion de la izquierda se define como una abre-viacion de la expresion de la derecha.

2. Semantica

Una asignacion de valores de verdad es una funcion v que asigna a cadaletra proposicional un elemento de {V, F}. V representa el valor de verdadverdadero y F el valor de verdad falso. Para abreviar hablaremos simple-mente de asignaciones.

23

24 4. LA LoGICA CLaSICA PROPOSICIONAL

Definimos inductivamente la relacion de satisfaccion entre asignacionesy formulas, sat., como sigue. Dada una asignacion v,

v sat. p sii v(p) = Vv sat. >v sat. ⊥v sat. (ϕ ∧ ψ) sii v sat. ϕ y v sat. ψv sat. (ϕ ∨ ψ) sii v sat. ϕ o v sat. ψv sat. (ϕ→ ψ) sii v no sat. ϕ o v sat. ψ

De la definicion se sigue inmediatamente que

v sat. ¬ϕ sii v no sat. ϕ.

Cuando parezca conveniente escribitremos v |= ϕ para indicar que v sat. ϕ.Diremos que v satisface ϕ, si v sat. ϕ. Analogamente, si Σ es un conjunto

de formulas, decimos que v satisface Σ si para cada ϕ ∈ Σ, v sat. ϕ. Si existeuna asignacion v tal que v satisface Σ, decimos que Σ es satisfacible

Una formula ϕ es una tautologıa si toda asignacion satisface ϕ. Es unacontradiccion si ninguna asignacion la satisface.

Si Σ es un conjunto de formulas y ϕ es una formula, decimos que ϕ esconsecuencia de Σ, y escribimos Σ |= ϕ, si toda asignacion que satisface Σsatisface ϕ.

3. Calculo de secuentes

Vamos a considerar el calculo para la logica clasica proposicional queintrodujo Gentzen en “Untersuchungen uber das logische Schliessen” (Mat-hematische Zeitschrift 39 (1935) pp. 176-210, 405-431)1, con la diferenciade que nuestros secuentes son pares de conjuntos finitos de formulas en lu-gar de pares de sucesiones finitas de formulas. El calculo que damos es unaadaptacion del de Gentzen al lenguaje L = {∧,∨,→,⊥,>}.

Un secuente es un par 〈Γ,∆〉 donde Γ y ∆ son conjuntos finitos, posi-blemente vacıos, de formulas. Las letras griegas mayusculas Γ,∆,Π varianen lo sucesivo sobre este tipo de conjuntos. La union de conjuntos finitos eneste contexto se indicara con la coma. Ası, Γ,∆ es el conjunto finito Γ ∪∆.En este contexo, Γ, ϕ,∆ es el conjunto Γ∪ {ϕ} ∪∆. Debe tenerse en cuentaque ∅� ∅ es un secuente.

Un secuente tıpico es de la forma

{ϕ1, . . . , ϕn}� {ψ1, . . . , ψn}que escribiremos simplemente ası

ϕ1, . . . , ϕn � ψ1, . . . , ψn,

pero tenemos secuentes de las formas

ϕ1, . . . , ϕn � ∅ ∅� ψ1, . . . , ψn

1Hay traducciom inglesa en M.E. Szabo (ed.) Collected papers of Gerhard Gentzen,North-Holland, Amsterdam 1969.

3. CaLCULO DE SECUENTES 25

A menudo abreviaremos las expresiones ∅ � ∆ y Γ � ∅ con �∆ y Γ�, res-pectivamente.

3.1. El calculo LK para la logica clasica.

Reglas estructuralesIdentidad

ϕ� ϕDebilitacion

Γ � ∆Γ, ϕ� ∆

(DI)Γ � ∆

Γ � ϕ,∆(DD)

Corte

Γ � ϕ,∆ Π, ϕ� ΣΓ,Π � ∆,Σ

(Corte)

Reglas operacionales

Γ,⊥� ∆(Bot)

Γ �>,∆(Top)

Γ, ϕ� ∆Γ, ϕ ∧ ψ � ∆

Γ, ψ � ∆Γ, ϕ ∧ ψ � ∆

(∧ I)Γ � ϕ,∆ Γ � ψ,∆

Γ � ϕ ∧ ψ,∆(∧ D)

Γ, ϕ� ∆ Γ, ψ � ∆Γ � ∆, ϕ ∨ ψ

(∨ I)Γ � ϕ,∆

Γ � ϕ ∨ ψ,∆Γ � ψ,∆

Γ � ϕ ∨ ψ,∆(∨ D)

Γ � ϕ,Σ Π, ψ � ∆Γ,Π, ϕ→ ψ � Σ,∆

(→ I)Γ, ϕ� ψ,∆

Γ � ϕ→ ψ,∆(→ D)

Una derivacion en LK es una sucesion finita y no vacıa de secuentestal que cada uno de sus elementos es un axioma o se obtiene de elementosanteriores en la sucesion mediante la aplicacion de una de las reglas estruc-turales o una de las reglas operacionales. Una derivacion lo es de su ultimosecuente. Un secuente es derivable en LK si tiene una derivacion en LK.

A continuacion prersentamos algunas reglas estructurales derivadas.Una regla derivada importante es la del Corte Generalizado

Σ � ϕ1,∆ . . . Σ � ϕn,∆ Π, ϕ1 . . . , ϕn � ∆′

Σ,Π � ∆,∆′(Corte G.)

Aunque la negacion no sea un sımbolo primitivo de nuestro lenguajeconviene tener las reglas derivadas fundamentales que la gobiernan, la reglade introduccion a la derecha y la regla de introduccion a la izquierda.


Reglas para la negacion

Γ, ϕ� ∆Γ � ¬ϕ,∆

Γ � ϕ,∆Γ,¬ϕ� ∆

Estas reglas se justifican mediante las derivaciones:

Γ, ϕ� ∆(DD)

Γ, ϕ�⊥,∆(→D)

Γ � ϕ→ ⊥,∆Γ � ¬ϕ,∆

y

Γ � ϕ,∆ ⊥� ∅(→I)

Γ, ϕ→ ⊥� ∆Γ,¬ϕ� ∆

Proposicion 16. Las reglas

Γ � ϕ,ψ,∆Γ � ϕ ∨ ψ,∆

Γ � ϕ ∨ ψ,∆Γ � ϕ,ψ,∆

Γ, ϕ, ψ � ∆Γ, ϕ ∧ ψ � ∆

Γ, ϕ ∧ ψ � ∆Γ, ϕ, ψ � ∆

son derivadas.

Demostracion. Justificamos las de la disyuncion. Las de la conjuncionse dejan como ejercicio.

Γ � ϕ,ψ,∆Γ � ϕ ∨ ψ,ψ,∆

ψ � ψ

ψ � ϕ ∨ ψΓ � ϕ ∨ ψ,ϕ ∨ ψ,∆

Γ � ϕ ∨ ψ,∆

Γ � ϕ ∨ ψ,∆

ϕ� ϕ

ϕ� ϕ,ψ

ψ � ψ

ϕ� ϕ,ψ

ϕ ∨ ψ � ϕ,ψ

Γ � ∆, ϕ, ψΓ � ϕ,ψ,∆

QED

Proposicion 17. Los secuentes1. ϕ ∧ ψ � ϕ, ϕ ∧ ψ � ψ2. ϕ ∧ ψ � ψ ∧ ϕ3. ϕ ∧ (ψ ∧ δ) � ϕ ∧ (ψ ∧ δ)4. ϕ ∧ ϕ� ϕ5. ϕ� ϕ ∨ ψ, ψ � ϕ ∨ ψ6. ϕ ∨ ψ � ψ ∨ ϕ7. ϕ ∨ (ψ ∨ δ) � ϕ ∨ (ψ ∨ δ)


8. ϕ ∨ ϕ� ϕ

son derivables sin utilizar las reglas estructurales.

Demostracion. Demostraremos 1, 2, 3, y 4. El resto de demostracionesse dejan como ejercicio.

1.

ϕ� ϕ

ϕ ∧ ψ � ϕ

ψ � ψ

ϕ ∧ ψ � ψ

2.

ψ � ψ

ϕ ∧ ψ � ψ

ϕ� ϕ

ϕ ∧ ψ � ϕ

ϕ ∧ ψ � ψ ∧ ϕ3.

ϕ� ϕ

ϕ ∧ (ψ ∧ δ) � ϕ

ψ � ψ

ψ ∧ δ � ψ

ϕ ∧ (ψ ∧ δ) � ψ

ϕ ∧ (ψ ∧ δ) � ϕ ∧ ψ

δ � δψ ∧ δ � δ

ϕ ∧ (ψ ∧ δ) � δ

ϕ ∧ (ψ ∧ δ) � (ϕ ∧ ψ) ∧ δ4. Es un caso particular de 1. QED

Utilizando las dos ultimas proposiciones es facil demostrar que las reglas

ϕ1, . . . , ϕn � ψ1, . . . , ψk

ϕ1 ∧ . . . ∧ ϕn � ψ1 ∨ . . . ∨ ψk

ϕ1 ∧ . . . ∧ ϕn � ψ1 ∨ . . . ∨ ψk

ϕ1, . . . , ϕn � ψ1, . . . , ψk

son derivadas. Estas reglas junto con los secuentes derivables de la propo-sicion anterior muestran que la conjuncion simula el comportamiento de lacoma a la izquierda de los secuentes y la disyuncion lo simula a la derecha.

Proposicion 18. Los secuentes1. ϕ,ϕ→ ψ � ψ2. ϕ� ¬¬ϕ3. ∅� ϕ ∨ ¬ϕ4. ¬¬ϕ� ϕ

son derivables

Demostracion. 1.

ϕ� ϕ ψ � ψ

ϕ,ϕ→ ψ � ψ


2.

ϕ� ϕ ⊥�⊥ϕ,ϕ→ ⊥�⊥

ϕ� (ϕ→ ⊥)→ ⊥ϕ� ¬¬ϕ

3.

ϕ� ϕ�¬ϕ,ϕ�ϕ,¬ϕ

�ϕ ∨ ¬ϕ4.

ϕ� ϕ�¬ϕ,ϕ¬¬ϕ� ϕ

QED

Proposicion 19. Las siguientes reglasΣ, ϕ� ψ

Σ � ϕ→ ψ

Σ � ϕ→ ψ

Σ, ϕ� ψ

son reglas derivadas para el condicional.


3.2. Correccion de LK. A continuacion demostraremos que el calcu-lo LK es correcto. Diremos que un secuente Γ�∆ es correcto si toda asigna-cion v que satisface todas las formulas de Γ satisface al menos una formulade ∆. En particular, si ∆ no es vacio, ∅ � ∆ es correcto si toda asignacionsatisface alguna formula de ∆, y si Γ no es vacıo, Γ�∅ es correcto si ningunaasignacion satisface todas las formulas de Γ. El secuente ∅�∅ no es correcto.

Teorema 20 (Correccion de LK). Todo secuente derivable de LK escorrecto.

Demostracion. Los secuentes que permiten derivar los axiomas de LKson correctos. Las reglas de inferencia aplicadas a secuentes correctos nospermiten derivar secuentes correctos. QED

3.3. La relacion de deducibilidad. Dado un conjunto de formulasΣ y una formula ϕ, diremos que ϕ es deducible de Σ, y escribiremos Σ ` ϕ,si el secuente ∅ � ϕ es derivable o hay ϕ1, . . . , ϕn ∈ Σ tales que el secuenteϕ1, . . . , ϕn � ϕ es derivable.

Un conjunto Σ de formulas es consistente si Σ 6` ⊥. En caso contrario sedice que es inconsistente.

De la definicion se sigue inmediatamente que Σ es inconsistente si y solosi alguno de sus subconjuntos finitos lo es.


Proposicion 21. La relacion de deducibilidad tiene las siguientes pro-piedades:

1. Si ϕ ∈ ∆, entonces ∆ ` ϕ,2. Si para toda ϕ ∈ ∆, Σ ` ϕ, y ∆ ` ψ, entonces Σ ` ψ.3. Si Σ ` ϕ, entonces Σ ∪∆ ` ϕ.

Demostracion. 1. Se sigue de que el secuente ϕ� ϕ es derivable.2. Se sigue del Corte Generalizado. Supongamos que ∆ ` ψ y que pa-

ra toda ϕ ∈ ∆, Σ ` ϕ. Si el secuente ∅ � ψ es derivable, es claro queΣ ` ψ. En caso contrario hay elementos ψ0, . . . , ψn de ∆ tales que el secuen-te ψ0, . . . , ψn�ψ es derivable. Consideremos para cada i ≤ n un subconjuntofinito Σi de Σ tal que el secuente Σi �ψi es derivable. Estos conjuntos exis-ten puesto que, por suposicion, Σ ` ψi. Utilizando la regla de Debilitaciontenemos que para cada i ≤ n el secuente

Σ0, . . . ,Σn � ψi

es derivable. Utilizando el Corte Generalizado obtenemos que

Σ0, . . . ,Σn � ψ

es derivable. Puesto que Σ0, . . . ,Σn es un subconjunto finito de Σ obtenemosque Σ ` ψ.

3. Se sigue inmediatamente de la definicion de la relacion de deducibili-dad. QED

Observese que las propiedades de ` de la proposicion dependen exclusi-vamente de las reglas estructurales del calculo.

Proposicion 22. La relacion de deducibilidad tiene ademas las propie-dades:

1. Si Σ ` ϕ→ ψ y Σ ` ϕ, entonces Σ ` ψ.2. Σ ` ϕ ∧ ψ sii Σ ` ϕ y Σ ` ψ.3. Si Σ ` ϕ o Σ ` ψ, entonces Σ ` ϕ ∨ ψ.4. Σ ∪ {ϕ} ` δ y Σ ∪ {ψ} ` δ sii Σ ∪ {ϕ ∨ ψ} ` δ.5. Σ, ϕ ` ψ sii Σ ` ϕ→ ψ.6. Para toda formula ϕ, ⊥ ` ϕ.

Demostracion. 1. Supongamos que Σ ` ϕ → ψ y Σ ` ϕ. Sean Σ′ yΣ′′ subconjuntos finitos de Σ tales que los secuentes Σ′ � ϕ → ψ y Σ′′ � ϕson derivables. Por la regla de debilitacion los secuentes Σ′,Σ′′ � ϕ → ψy Σ′,Σ′′ � ϕ resultan derivables. Sabemos que el secuente ϕ → ψ,ϕ � ψ esderivable. Utilizando la regla de Corte Generalizado obtenemos que Σ,Σ′�ψes derivable. Esto implica que Σ ` ψ.

2. Parecida a la demostracion de 1, utilizando que los secuentes ϕ∧ψ�ϕ,ϕ ∧ ψ � ψ y ϕ,ψ � ϕ ∧ ψ son derivables.

3. Parecida a la demostracion de 1, utilizando que los secuentes ϕ�ϕ∨ψy ψ � ϕ ∨ ψ son derivables.


4. Supongamos que Σ ∪ {ϕ} ` δ y Σ ∪ {ψ} ` δ. Existen pues secuentesderivables ∆, ϕ � δ y ∆′, ψ � δ tales que ∆ ⊆ Σ y ∆′ ⊆ σ. Entonces,gracias a la regla (∨D), el secuente ∆,∆′, ϕ ∨ ψ � δ es derivable. Por tanto,Σ∪ {ϕ∨ψ} ` δ. Por otra parte, si Σ∪ {ϕ∨ψ} ` δ. Puesto que ϕ ` ϕ∨ψ yψ ` ϕ∨ψ, utilizando 2 y 3 de la proposicion 21 obtenemos que Σ∪ {ϕ} ` δy Σ ∪ {ψ} ` δ.

5. Deben utilizarse las reglas derivadas para el condicional que se handado anteriormente.

6. El secuente ⊥� ϕ es claramente derivable. QED

Corolario 23. Si Σ ` ϕ, entonces Σ |= ϕ.

Demostracion. Supongamos que Σ ` ϕ. Sea Σ′ un subconjunto finitod de Σ tal que Σ′�ϕ es derivable. Por el teorema de correccion de LK, estesecuente es correcto. Ası toda asignacion que satisface a toda formula de Σ′

satisface ϕ. Por tanto, toda asignacion que satisface Σ satisface ϕ, es decirΣ |= ϕ. QED

3.4. El teorema de completud. Demostremos que LK es completo,es decir que todo secuente correcto es derivable en LK. Ademas demostra-remos el teorema de completud, a saber: si Σ |= ϕ entonces Σ ` ϕ. Para ellonecesitamos introducir algunos conceptos y demostrar varios resultados.

Lema 24. Σ ` ϕ si y solo si Σ ∪ {¬ϕ} es inconsistente.

Demostracion. Si Σ ` ϕ, puesto que Σ ∪ {¬ϕ} ` ϕ → ⊥, obtenemosque Σ ∪ {¬ϕ} ` ⊥, es decir que Σ ∪ {¬ϕ} es inconsistente. Por otra parte,si Σ ∪ {¬ϕ} es inconsistente, Σ ∪ {¬ϕ} ` ⊥. Por tanto Σ ` ¬ϕ→ ⊥. Ahorabien, ¬ϕ→ ⊥ ` ϕ. Por tanto Σ ` ϕ. QED

Lema 25. Σ es inconsistente sii para toda formula ϕ, Σ ` ϕ.

Demostracion. Si para toda formula ϕ, Σ ` ϕ, en particular Σ ` ⊥,por lo que es inconsistente. Si Σ es inconsistente, Σ ` ⊥. Por tanto puesto quepara toda formula ϕ, ⊥ ` ϕ, tenemos que para toda formula ϕ, Σ ` ϕ. QED

Un conjunto de formulas Σ es una teorıa si para cada formula ϕ tal queΣ ` ϕ ocurre que ϕ ∈ Σ.

Una teorıa Σ es ϕ-relativamente maximal si Σ 6` ϕ y para toda formulaψ 6∈ Σ, Σ ∪ {ψ} ` ϕ.

Una teorıa Σ es prima si es consistente y para cualesquiera formulasϕ,ψ, si Σ ` ϕ ∨ ψ, entonces ϕ ∈ Σ o ψ ∈ Σ.

Una teorıa Σ es consistente maximal si es consistente y para cada formulaϕ 6∈ Σ, Σ ∪ {ϕ} es inconsistente.

Lema 26. Si Γ es un conjunto de formulas y ϕ es una formula tal queΓ 6` ϕ, entonces existe una teorıa ϕ-relativamente maximal Σ tal que Γ ⊆ Σ.

Demostracion. Consideremos una enumeracion ψ0, ψ1, ψ2, . . . , ψn, . . .de las formulas del lenguaje. Vamos a definir en pasos sucesivos una sucesionde conjuntos de formulas Σ0,Σ1, . . . , Σn, . . . tal que


1. Σ0 = Γ2. Para cada n, Σn 6` ϕ3. Para cada n, Σn ⊆ Σn+1

La definicion de la sucesion es:

Σ0 = Γ

Σn+1 ={

Σn si Σn ∪ {ψn} ` ϕΣn ∪ {ψn} si Σn ∪ {ψn} 6` ϕ

Claramente se cumplen las condiciones 1, 2 y 3 deseadas. Sea

Σ =⋃n

Σn

Es decir, para cada formula ψ, ψ ∈ Σ si y solo si hay n tal que ψ ∈ Σn.Veamos que Σ es ϕ-relativamente maximal.

1. Σ 6` ϕ. En efecto, si Σ ` ϕ, hay ∆ ⊆ Σ finito tal que ∆�ϕ es derivable.De la condicion 3 anterior y de que ∆ es finito se sigue que hay n tal que∆ ⊆ Σn. Por tanto, Σn ` ϕ. Pero esto contracide la condicion 2 anterior.

2. Si ψ 6∈ Σ, entonces Σ ∪ {ψ} ` ϕ. En efecto, supongamos que ψ 6∈ Σ yque Σ ∪ {ψ} 6` ϕ Sea n tal que ψ es ψn. Entonces Σn ∪ {ψn} 6` ϕ. Por tantoψn ∈ Σn+1 ⊆ Σ. Pero esto es absurdo. Por tanto Σ ∪ {ψ} ` ϕ. QED

Proposicion 27. Sea Σ una teorıa. Son equivalentes

1. Σ es ϕ-relativamente maximal para alguna formula ϕ.2. Σ es prima3. Σ es consistente y para toda formula ϕ, ϕ ∈ Σ o ¬ϕ ∈ Σ.4. Σ es consistente maximal.

Demostracion. 1 implica 2. Supongamos que Σ es ϕ-relativamentemaximal. Supongamos que ψ ∨ δ ∈ Σ. Puesto que Σ es ϕ-relativamentemaximal, si ψ, δ 6∈ Σ, Σ∪{ψ} ` ϕ y Σ∪{δ} ` ϕ. Por tanto Σ∪{ψ ∨ δ} ` ϕ.Es decir, Σ ` ϕ, pero esto no es posible al ser Σ es ϕ-relativamente maximal.Ası ψ ∈ Σ o δ ∈ Σ. Por tanto Σ es una teorıa prima.

2 implica 3. Supongamos que Σ es prima. Por tanto es consistente.Ademas, para cada ϕ, ϕ∨¬ϕ ∈ Σ. Por tanto, al ser prima, ϕ ∈ Σ o ¬ϕ ∈ Σ.

3 implica 4. Σ es consistente y para toda formula ϕ, ϕ ∈ Σ o ¬ϕ ∈ Σ.Supongamos que ϕ 6∈ Σ. Por tanto, ¬ϕ ∈ Σ. Asi, Σ ∪ {ϕ} es inconsistente.Por tanto Σ es consistente maximal.

4 implica 1. Si Σ es consistente maximal, para cada ϕ 6∈ Σ, Σ es ϕ-relativamente maximal. QED

3.4.1. Teorıas consistentes maximales y asignaciones. Vamos a demos-trar que hay una correspondencia biunıvoca entre las asignaciones de valoresde verdad y las teorıas consistentes maximales.

1. Consideremos una asignacion v. Sea

Σ(v) = {ϕ : v sat. ϕ}


Este conjunto de formulas es una teorıa, gracias al teorema de correccion.En efecto, supongamos que Σ(v) ` ϕ. Entonces Σ(v) |= ϕ. Puesto queclaramente v satisface Σ(v), tenemos que v sartisface ϕ. Por tanto ϕ ∈Σ(v). Por otra parte, es claro que ⊥ 6∈ Σ(v). Por tanto Σ(v) es consistente.Finalmente Σ(v) es prima pues si ϕ ∨ ψ ∈ Σ(v), entonces v satisface ϕ ∨ ψ,con lo que v satisface ϕ o v satisface ψ; es decir, ϕ ∈ Σ(v) o ψ ∈ Σ(v).Conluimos pues que Σ(v) es una teorıa consistente maximal.

Si dos asignaciones v y v′ son diferentes, hay una letra proposicional almenos, digamos p, tal que v(p) 6= v′(p). Por tanto Σ(v) 6= Σ(v′).

2. Observemos que si Γ es una teorıa consistentes maximal

1. > ∈ Γ2. ⊥ 6∈ Γ3. ϕ ∧ ψ ∈ Γ sii ϕ ∈ Γ y ψ ∈ Γ;4. ϕ ∨ ψ ∈ Γ sii ϕ ∈ Γ o ψ ∈ Γ5. ϕ→ ψ ∈ Γ sii ϕ 6∈ Γ o ψ ∈ Γ6. ϕ ∈ Γ sii ¬ϕ 6∈ Γ

Sea Γ una teorıa consistente maximal. Definamos la asignacion vΓ comosigue: para cada letra proposicional p,

vΓ(p) = V sii p ∈ Γ

Gracias a la observacion anterior tenemos que para toda formula ϕ

vΓ sat. ϕ sii ϕ ∈ Γ.

Ademas, para cada teorıa maximal consistente Γ y cada asignacion v,

Σ(vΓ) = Γ y vΣ(v) = v.

Teorema 28 (Completud de LK). Todo secuente correcto es derivable.

Demostracion. Supongamos que Γ � ∆ es un secuente correcto. Su-pongamos que no es derivable. Entonces no es derivable el secuente Γ �⊥.Por tanto el conjunto de formulas Γ es consistente. Si la disyuncion de lasformulas de ∆ fuese deducible de Γ, el secuente Γ � ∆ serıa derivable. Portanto la disyuncion, digamos α, de las formulas de ∆ no es deducible de Γ.Sea Σ una teorıa prima tal que Γ ⊆ Σ y α 6∈ Σ. Puesto que Σ es maximalconsistente, consideremos la asignacion vΣ. Esta asignacion satisface todaslas formulas de Γ, por tanto, puesto que el secuente Γ � ∆ es correcto, sa-tisface alguna formula de ∆, por tanto la disyuncion de todas ellas, es decirα. Ası, α ∈ Σ, pero esto es absurdo. QED

Corolario 29. Si Σ |= ϕ, entonces Σ ` ϕ.

Demostracion. Supongamos que Σ |= ϕ y que Σ 6` ϕ. Sea Γ una teorıamaximal consistente tal que Σ ⊆ Γ y ϕ 6∈ Γ. Entonces vΓ satisface Σ. Portanto vΓ satisface ϕ, con lo que ϕ ∈ Γ y ello es absurdo. QED

Teorema 30 (Correccion y completud de LK).


1. Un secuente ϕ0, . . . , ϕn � ψ0, . . . , ψm es derivable en LK si y solo sila formula (ϕ0 ∧ . . . ∧ ϕn)→ (ψ0 ∨ . . . ∨ ψm) es una tautologıa.

2. Un secuente ϕ0, . . . , ϕn �∅ es derivable en LK si y solo si la formulaϕ0 ∧ . . . ∧ ϕn es una contradiccion en logica clasica.

3. Un secuente ∅�ψ0, . . . , ψm es derivable en LK si y solo si la formulaψ0 ∨ . . . ∨ ψm es una tautologıa.

Demostracion. 1. Tenemos que ϕ0, . . . , ϕn � ψ0, . . . , ψm es derivableen LK si y solo si ϕ0 ∧ . . . ∧ϕn �ψ0 ∨ . . .∨ψm es derivable en LK si y solosi ϕ0 ∧ . . . ∧ ϕn |= ψ0 ∨ . . . ∨ ψm si y solo si ϕ0 ∧ . . . ∧ ϕn → ψ0 ∨ . . . ∨ ψm

es una tautologıa.2. ϕ0, . . . , ϕn�∅ es derivable en LK si y solo si ϕ0, . . . , ϕn�⊥ es derivable

en LK si y solo si ϕ0∧ . . .∧ϕn → ⊥ es una tautologıa si y solo si ϕ0∧ . . .∧ϕn

es una contradiccion.3. ∅�ψ0, . . . , ψm es derivable en LK si y solo >�ψ0, . . . , ψm es derivable

en LK si y solo si > → ψ0 ∨ . . .∨ψm es tautologıa si y solo si ψ0 ∨ . . .∨ψm.QED

Capıtulo 5

Calculo de secuentes para la logica modal

1. El calculo

El calculo de secuentes que introducimos se obtiene a partir del calculode la logica clasica introducido en el capıtulo anterior anadiendo las reglasoperacionales

Σ, ϕ� ∆2Σ,3ϕ� 3∆

(M1)Σ � ∆, ϕ

2Σ � 3∆,2ϕ(M2)

Lo llamaremos LKK .Las siguientes reglas son casos particulares:

ϕ� ∆3ϕ� 3∆

Σ � ϕ

2Σ � 2ϕ

ϕ,ψ � ∆2ϕ,3ψ � 3∆

Σ � ϕ,ψ

2Σ � 2ϕ,3ψ

y tambien lo son:

ϕ� ∅3ϕ� ∅

∅� ϕ

∅� 2ϕ

Una derivacion en LKK es una sucesion finita y no vacıa de secuentestal que cada uno de sus elementos es un axioma o se obtiene de elementosanteriores en la sucesion mediante la aplicacion de una de las reglas estruc-turales o una de las reglas operacionales. Una derivacion lo es de su ultimosecuente. Un secuente es derivable en LKK si tiene una derivacion en LKK .

Una derivacion en LKK a partir de un conjunto de secuentes S es unasucesion finita y no vacıa de secuentes tal que cada uno de sus elementos esun axioma o un elemento de S o se obtiene de elementos anteriores en lasucesion mediante la aplicacion de una de las reglas estructurales o una de lasreglas operacionales. Un secuente s es derivable a partir de un conjunto desecuentes S si hay una derivacion en LKK a partir del conjunto de secuentesS cuyo ultimo elemento es el secuente s.

35

36 5. CaLCULO DE SECUENTES PARA LA LoGICA MODAL

Observese que un secuente s es derivable si y solo si es derivable a partirdel conjunto vacıo de secuentes.

Proposicion 31. Si S es un conjunto de secuentes validos en un modeloM y s es un secuente derivable a partir de S, entonces s es valido en M.

Demostracion. Sea M un modelo. Basta con ver primero que cadaregla si la aplicamos a secuentes validos en M nos proporciona un secuen-te valido en M. Despues por induccion en la longitud de las derivacionesobtenemos lo deseado. QED

Corolario 32. Todo secuente derivable en LKK es un secuente valido.

Demostracion. Un secuente derivable los es del conjunto vacıo de se-cuentes. Ası, puesto que los secuentes del conjunto vacıo son validos en todomodelo, todo secuente derivable es valido en todo modelo, por tanto vali-do. QED

Algunos secuentes derivables:

Proposicion 33. El secuente ∅� 2ϕ es derivable a partir del secuente∅� ϕ.

Demostracion. La siguiente derivacion

∅� ϕ(M2)

∅� 2ϕ

justifica que � 2ϕ es derivable a partir del secuente � ϕ. La derivacion seobtiene aplicando la regla la regla (M2); observese que el primer secuentees de la forma ∅ � ∅, ϕ y la regla (M2) nos permite obtener el secuente2∅� 3∅,2ϕ, que es el secuente � 2ϕ, puesto que 2∅ = 3∅ = ∅. QED

Proposicion 34. El secuente p� 2p no es derivable

Demostracion. No puede ser derivable puesto que no es valido. QED

Lema 35. Si Σ �α es un secuente derivable, entonces el secuente ∅�αes derivable a partir del conjunto de secuentes {∅� β : β ∈ Σ}.

Demostracion. Dada una derivacionD del secuente Σ�α, extendamosla sucesion con los secuentes ∅ � β con β ∈ Σ. Entonces la regla del Cortegeneralizada nos permite obtener el secuente ∅� α. QED

Lema 36. Los secuentes1. 2¬α� ¬3α2. ¬3α� 2¬α

son derivables.

Demostracion. 1. El secuente ¬α, α�∅ es derivable. Aplicando la regla(M1) obtenemos que el secuente 2¬α,3α�∅ es derivable (al aplicar la reglaconsideramos Σ = {¬α} y ∆ = ∅). Por tanto, aplicando las reglas derivadaspara la negacion (con ∆ = ∅), obtenemso que 2¬α� ¬3α es derivable.

3. PROPIEDADES BaSICAS DE ` 37

2. El secuente �α,¬α es derivable. Aplicanco la regla (M2) (con Σ = ∅ y∆ = {α}) obtenemos que el secuente �3α,2¬α es derivable. Por las reglasderivadas de la negacion obtenemos que ¬3α� 2¬α es derivable. QED

2. Relaciones de deducibilidad

Dado un conjunto de formulas Σ y una formula ϕ, diremos que ϕ esdeducible de Σ, y escribiremos Σ ` ϕ, si el secuente ∅�ϕ es derivable o hayϕ1, . . . , ϕn ∈ Σ tales que el secuente ϕ1, . . . , ϕn � ϕ es derivable.

Sea Σ un conjunto de formulas y sea α una formula. Decimos que αes fuertemente deducible de Σ si el secuente �α es derivable a partir delconjunto de secuentes {�β : β ∈ Σ}. Para indicar que α es fuertementededucible de Σ escribiremos Σ `f α.

Lema 37. Si Σ ` α, entonces Σ `f α.

Demostracion. Supongamos que Σ ` α. Sea Σ′ ⊆ Σ finito tal que elsecuente Σ � α es derivable. Por el lema anterior, �α es derivable a partirde {�β : β ∈ Σ}. Por tanto Σ `f α. QED

Teorema 38 (de Correccion). Si Σ ` ϕ, entonces Σ |=l ϕ.

Demostracion. Supongamos que Σ ` ϕ. Sea Σ′ un subconjunto finitode Σ tal que Σ′�ϕ es derivable. Puesto que los secuentes derivables en LKK

son correctos, el secuente es valido. Por tanto Σ |=l ϕ. QED

Teorema 39 (de Correccion). Si Σ `f ϕ, entonces Σ |=g ϕ.

Demostracion. Supongamos que Σ `f ϕ, Ası, el secuente �ϕ es deri-vable a partir de los secuentes en {�ψ : ψ ∈ Σ}. Supongamos que M es unmodelo en el que las formulas de Σ son validas. En tal caso, elM son validoslos secuentes �ψ con ψ ∈ Σ. Por tanto por la proposicion 31 el secuente �ϕes valido en M, por lo que ϕ es valida en M. QED

3. Propiedades basicas de `

Como en logica clasica proposicional tenemos:

Proposicion 40. La relacion de deducibilidad tiene las siguientes pro-piedades:

1. Si ϕ ∈ ∆, entonces ∆ ` ϕ,2. Si para toda ϕ ∈ ∆, Σ ` ϕ, y ∆ ` ψ, entonces Σ ` ψ.3. Si Σ ` ϕ, entonces Σ ∪∆ ` ϕ.

Proposicion 41. La relacion de deducibilidad tiene ademas las propie-dades:

1. Si Σ ` ϕ→ ψ y Σ ` ϕ, entonces Σ ` ψ.2. Σ ` ϕ ∧ ψ sii Σ ` ϕ y Σ ` ψ.3. Si Σ ` ϕ o Σ ` ψ, entonces Σ ` ϕ ∨ ψ.4. Σ ∪ {ϕ} ` δ y Σ ∪ {ψ} ` δ sii Σ ∪ {ϕ ∨ ψ} ` δ.


5. Σ, ϕ ` ψ sii Σ ` ϕ→ ψ (teorema de la deduccion).6. Para toda formula ϕ, ⊥ ` ϕ.

Lema 42. Para cada formula ϕ,1. Si Σ ` ϕ0, . . . ,Σ ` ϕn y {ϕ0, . . . , ϕn} ` ψ, entonces Σ ` ψ.2. Si Σ ` ϕ y Σ ` ϕ→ ψ, entonces Σ ` ψ.

Ademas tenemos las siguientes propiedades

Proposicion 43. Si Σ ` ϕ, entonces 2Σ ` 2ϕ.

Demostracion. Supongamos que Σ ` ϕ. Hay pues Σ′ ⊆ Σ finito talque Σ′ � ϕ es un secuente derivable el LKK . QED

Proposicion 44. Para toda formula ϕ, 2¬ϕ ` ¬3ϕ y ¬3ϕ ` 2¬ϕ.

4. Conjuntos consistentes de formulas

Un conjunto Σ de formulas es consistente si Σ 6` ⊥. En caso contrariose dice que es inconsistente. De la definicion se sigue inmediatamente queΣ es inconsistente si y solo si alguno de sus subconjuntos finitos lo es.

Los siguientes dos lemas se demuestran como en logica clasica.

Lema 45. Σ ` ϕ si y solo si Σ ∪ {¬ϕ} es inconsistente.

Lema 46. Σ es inconsistente sii para toda formula ϕ, Σ ` ϕ.

Un conjunto de formulas Σ es una teorıa si para cada formula ϕ tal queΣ ` ϕ ocurre que ϕ ∈ Σ.

Una teorıa Σ es ϕ-relativamente maximal si Σ 6` ϕ y para todaformula ψ 6∈ Σ, Σ ∪ {ψ} ` ϕ.

Una teorıa Σ es prima si es consistente y para cualesquiera formulasϕ,ψ, si ϕ ∨ ψ ∈ Σ, entonces ϕ ∈ Σ o ψ ∈ Σ.

Una teoria Σ es relativamente maximal si hay una formula ϕ tal queΣ es ϕ-relativamente maximal.

Una teorıa Σ es consistente maximal si es consistente y para cadaformula ϕ 6∈ Σ, Σ ∪ {ϕ} es inconsistente.

Lema 47. Si Γ es un conjunto de formulas y ϕ es una formula tal queΓ 6` ϕ, entonces existe una teorıa ϕ-relativamente maximal Σ tal que Γ ⊆ Σ.

Corolario 48. Para cada conjunto de formulas Σ y cada formula α,Σ ` α sii α pertenece a toda teorıa relativamente maximal que incluye a Σ.

Proposicion 49. Sea Σ una teorıa. Son equivalentes1. Σ es ϕ-relativamente maximal para alguna formula ϕ.2. Σ es prima.3. Σ es consistente y para toda formula ϕ, ϕ ∈ Σ o ¬ϕ ∈ Σ.4. Σ es consistente maximal.

Demostracion. Como en logica clasica. QED

5. EL MODELO CANoNICO 39

Proposicion 50. Para todo conjunto de formulas consistente y maximalΣ,

(1) Si Σ ` α, entonces α ∈ Σ,(2) α ∧ β ∈ Σ sii α ∈ Σ and β ∈ Σ,(3) α ∨ β ∈ Σ sii α ∈ Σ o β ∈ Σ,(4) α→ β ∈ Σ sii α 6∈ Σ o β ∈ Σ,(5) ¬α ∈ Σ sii α 6∈ Σ.

Demostracion. La demostracion es como en el caso de la logica clasicaQED

5. El modelo canonico

Para motivar la definicion del modelo canonico, consideremos un modelocualquiera M = 〈F , V 〉. Dado w ∈W observemos que el conjunto

ΣM(w) = {α : 〈F , V 〉, w |= α}

es un conjunto maximal consistente que contiene toda formula valida en elmodelo.

Puede ocurrir que existan w,w′ ∈ W distintos que no se puedan distin-guir mediante una formula modal, es decir que tengan la propiedad de quelos conjuntos ΣM(w) y ΣM(w′) sean el mismo. Desde este punto de vistapodemos decir que un conjunto de formulas maximal consistente caracterizaun tipo de estado o de mundo posible.

Los puntos del modelo canonico seran todos los tipos de estado posi-bles. Es decir, los conjutnos de formulas maximal consistentes. Una formulasera verdadera en un estado del modelo canonico si y solo si pertenece alestado. Si denotamos con Mc el modelo canonico que vamos a definir, que-remos que tenga la propiedad siguiente. Para cada formula ϕ y cada puntode Mc (es decir cada conjunto maximal consistente) ∆,

Mc,∆ |= ϕ sii ϕ ∈ ∆.

Observemos que si esta condicion se cumple y ∆ es un conjunto maximalconsistente, entonces

ΣMc(∆) = ∆.

Si obtenemos el modelo Mc con la propiedad anterior, entonces si Σ 6`α, puesto que el conjunto Σ ∪ {¬α} es consistente, habra un conjunto deformulas maximal consistente ∆ tal que incluye a Σ∪{¬α}, por tanto en ∆(en tanto que punto del modelo canonico) las formulas de Σ seran verdaderasy ϕ sera falsa, con lo cual tendremos que Σ 6|=l α.

Para explicar como definir la relacion de accesibilidad del modelo canoni-co consideremos un modelo 〈F , V 〉 y observemos que si w, v ∈ W son talesque wRv entonces {α : 2α ∈ Σ(w)} ⊆ Σ(v). Por tanto si Rc es la rela-cion del modelo canonico que pretendemos definir, Rc debe cumplir quesi ∆Rc∆′, donde ∆ y ∆′ son conjuntos maximal consistentes, entonces


{α : 2α ∈ ΣMc(∆)} ⊆ ΣMc(∆′), es decir, teniendo en cuenta lo ante-rior, que {α : 2α ∈ ∆} ⊆ ∆′. Tomaremos esta ultima condicion como lacondicion para definir la relacion Rc de accesibilidad del modelo canonico.

El modelo canonico, que denotaremos con MK , se define como sigue.El conjunto de estados de MK es:

WK = {∆ : ∆ es un conjunto maximal consitente de formulas},y la relacion RK en WK de MK se define por

∆RK∆′ sii {α : 2α ∈ ∆} ⊆ ∆′.El marco FK = 〈WK , RK〉 es el marco canonico. El modelo canonico es

el modeloMK = 〈FK , VK〉, donde VK es la valoracion en el marco canonicodefinida por:

VK(p) = {∆ ∈WK : p ∈ ∆},para cada letra proposicional p.

El resultado principal sobre el modelo canonico es el lema fundamental.

Lema 51 (Lema Fundamental). Para todo conjunto maximal y consis-tente de formulas ∆ y toda formula α,

〈FK , VK〉,∆ |= α sii α ∈ ∆.

Demostracion. Se demuestra por induccion en α. Para las letras pro-posicionales vale por la definicion de la valoracion VK . Igualmente para lasconstantes proposicionales. Para las conectivas se sigue de las propiedadesde los conjuntos maximal consistentes del lema 83. Para el operador modal2 se argumenta como sigue. Supongamos, como hipotesis inductiva, que loque queremos demostrar vale para α. Observemos primero que gracias a lahipotesis inductiva tenemos que

〈FK , VK〉,∆ |= 2α sii ∀∆′ ∈WK si ∆RK∆′entonces α ∈ ∆′

sii ∀∆′ ∈WK si {β : 2β ∈ ∆} ⊆ ∆′,entonces α ∈ ∆′

Para demostrar que 〈FK , VK〉,∆ |= 2α sii 2α ∈ ∆, supongamos primeroque 2α ∈ ∆ y veamos que 〈FK , VK〉,∆ |= 2α. Por la observacion bastacon demostrar que para cada ∆′ ∈ WK , si {β : 2β ∈ ∆} ⊆ ∆′, entoncesα ∈ ∆′. Supongamos pues que ∆′ ∈ WK es tal que {β : 2β ∈ ∆} ⊆ ∆′.Puesto que 2α ∈ ∆, es claro que α ∈ ∆′. Para demostrar la otra implicacion,supongamos que 〈FK , VK〉,∆ |= 2α, es decir, de acuerdo con la observacion,que para todo ∆′ ∈WK , si {β : 2β ∈ ∆} ⊆ ∆′, entonces α ∈ ∆′. Veamos que2α ∈ ∆. Para este fin demostremos que el conjunto {β : 2β ∈ ∆}∪{¬α} esinconsistente. Si fuera consistente existirıa un conjunto maximal consistenteΓ que lo incluye y por la suposicion Γ tendrıa como elemento a α, lo que noes posible. Por tanto, al ser {β : 2β ∈ ∆} ∪ {¬α} inconsistente, {β : 2β ∈∆} ` α. Sea ahora {β0, . . . , βn} ⊆ {β : 2β ∈ ∆} tal que {β0, . . . , βn} `α. Entonces, {2β0, . . . ,2βn} ` 2α, y puesto que {2β0, . . . ,2βn} ⊆ ∆,obtenemos que 2α ∈ ∆.


Para el otro operador modal se razona de modo analogo. Supongamos,como hipotesis inductiva, que lo que queremos demostrar vale para α. Gra-cias a esta hipotesis inductiva tenemos que

〈FK , VK〉,∆ |= 3α sii ∃∆′ ∈WK t. q. ∆RK∆′ y α ∈ ∆′

sii ∃∆′ ∈WK t. q. {β : 2β ∈ ∆} ⊆ ∆′ y α ∈ ∆′.

Debemos ver que 〈FK , VK〉,∆ |= 3α sii 3α ∈ ∆. Supongamos pues que〈FK , VK〉,∆ |= 3α y que 3α 6∈ ∆. Ası por la observacion, hay ∆′ ∈ WK

tal que {β : 2β ∈ ∆} ⊆ ∆′ y α ∈ ∆′. Puesto que 3α 6∈ ∆, ¬3α ∈ ∆. Portanto, puesto que ¬3α ` 2¬α, obtenemos que 2¬α ∈ ∆. Ası, ¬α ∈ ∆′.Esto es absurdo pues ∆′ es consistente. Para demostrar la otra implicacion,supongamos que 3α ∈ ∆. Gracias a la observacion basta con encontrar ∆′ ∈WK tal que {β : 2β ∈ ∆} ⊆ ∆′ y α ∈ ∆′. Para conseguirlo, consideremos elconjunto Γ = {β : 2β ∈ ∆} ∪ {α} y veamos que es consistente. Si no lo estenemos que {β : 2β ∈ ∆} ` ¬α. Por tanto 2{{β : 2β ∈ ∆} ` 2¬α. Ahorabien, 2{{β : 2β ∈ ∆} ⊆ ∆. Conluimos que 2¬α ∈ ∆. Pero, 2¬α ` ¬3α.Por tanto, ¬3α ∈ ∆. Esto es absurdo puesto que ∆ es consistente y 3α ∈ ∆.Concluimos que Γ es consistente. Sea ∆′ maximal consistente tal que Γ ⊆ ∆′.Entonces {β : 2β ∈ ∆} ⊆ ∆′ y α ∈ ∆′. QED

Corolario 52. Para todo conjunto de formulas Γ y toda formula α,

Γ |=l α sii para todo Γ ∈WK tal que Σ ⊆ Γ, α ∈ Γ.

Demostracion. Supongamos que Γ |=l α. Sea Γ ∈WK tal que Σ ⊆ Γ.Entonces en el modelo canonico todas las formulas en Σ son verdaderas enel punto Γ. Por tanto, puesto que Γ |=l α, obtenemos que α es verdadera enel punto Γ, con lo cual α ∈ Γ.

Supongamos ahora que para todo Γ ∈ WK tal que Σ ⊆ Γ, α ∈ Γ.Supongamos que Γ 6|=l α. Sea puesM un modelo y sea w ∈W un punto delmismo en el que las formulas de Σ son verdaderas. Sabemos que el conjuntode formulas ΣM(w) = {ϕ : M, w |= ϕ} es maximal consistente. Por lasuposicion, Σ ⊆ ΣM(w). Por tanto, α ∈ ΣM(w), con lo que α es verdaderaen w. Ası concluimos que Γ |=l α. QED

Teorema 53. Para todo conjunto de formulas Γ y toda formula α,

Γ |=l α sii Γ ` α.

Demostracion. Por el corolario 48 y el corolario 52. QED

Capıtulo 6

Algunos resultados de correspondencia

Presentamos algunos resultados de la forma

La formula α es valida en el marco F sii F tiene la propiedad Φ.

Cuando se dispone de un resultado de este tipo se dice que la formula αcorresponda a la propiedad Φ.

Desde la perspectiva que este tipo de resultados introducen se puedeafirmar que las formulas modales, y mas en general los conjuntos de formulasmodales, sirven para describir propiedades de los marcos de Kripke. Loslenguajes modales sirven para este fin. Algunas clases de marcos puedendefinirse mediante formulas modales de este modo pero otra no.

Demostraremos algunas de las correspondencias de la tabla que hay acontinuacion.

2p→ p R es reflexiva2p→ 22p R es transitivap→ 23p R es semetrica2p→ 3p R es serial3p→ 2p R es una funcion3p↔ 2p R es una funcion con dominio W

Proposicion 54. La formula 2p → p es valida en un marco F sii larelacion R es reflexiva.

Demostracion. Supongamos que R es reflexiva. Seat V una valoracionen F y sea w ∈W . Si 2p es verdadera en w, puesto que wRw, tenemos quep es verdadera en w. Por tanto, 2p→ p es verdadera en w. Concluimos puesque 2p→ p es valida en F . Para demostrar la otra implicacion, supongamosque 2p→ p es valida en F . Sea w ∈W y consideremso cualquier valoracionV en F al que V (p) = {v ∈ W : wRv}. En tal caso, 2p es verdadera en wen el modelo 〈F , V 〉. Puesto que 2p → p es verdadera en w en el modelo〈F , V 〉, pes verdadera en w en el modelo 〈F , V 〉. Por tanto, w ∈ V (p), conlo cual wRw. Concluimos que R es reflexiva. QED

Proposicion 55. La formula 2p → 22p es valida en un marco F siila relacion R es transitiva.

Demostracion. La demostracion de la parte facil, que es la implica-cion de derecha a izquierda se deja como ejercicio. Para demostrar la otra

43

44 6. ALGUNOS RESULTADOS DE CORRESPONDENCIA

implicacion, supongamos que 2p → 22p es valida en F y que w, v, u ∈ Wson tales que wRv and vRu. Sea V una valoracion en F tal que V (p) = {x ∈W : wRix}. Claramente, 2p es verdadera en w en 〈F , V 〉. Puesto que porsuposicion 2p→ 22p tambien es verdadera en w, 22p es verdadera en w.Por tanto, 2p ies verdadera en v y p lo es en u. Por tanto, wRu. Concluimospues que R es transitiva. QED

Proposicion 56. La formula p→ 23p es valida en un marco F sii larelacion R es simetrica.

Demostracion. Supongamos que p→ 23p es valida en F y que w, v ∈W son tales que wRv. Sea V una valoracion cualquiera tal que V (p) = {w}.Puesto que p y p → 23p son verdaderas en w, 23p es verdadera en w.Por tanto, 3p es verdadera en v. La unica posibilidad de que esto sea ası esque vRw. Concluimos pues que R es simetrica. La demostracion de la otraimplicacion se deja como ejercicio. QED

Proposicion 57. La formula 2p→ 3p es valida en un marco F sii larelacion R es serial (i.e. para cada w ∈W existe v ∈W tal que wRv).


Capıtulo 7

Logicas modales normales

Sea F una clase de marcos. Consideremos el conjunto de fomulas

L(F) = {ϕ : para todo F ∈ F,F |= ϕ}.De acuerdo con los resultados de la seccion anterior L(F) contiene todas lasinstancias de sustitucion de las tautologıas, todos los axiomas distributivos(o axiomas K) y esta cerrado bajo Modus Ponens, la regla de necesidad einstancias de sustitucion. Un conjunto de formulas modales con estas carac-terısticas se dice que es una logica modal normal.

Definicion 58. Una logica modal normal es un conjunto de formulasmodales L tal que

1. contiene todas las instancias de sustitucion de las tautologıas2. contiene todas las formulas de la forma

(K) 2(ϕ→ ψ)→ (2ϕ→ 2ψ).3. contiene todas las formulas de las fomas 2α ↔ ¬3¬α y 3α ↔¬2¬α,

4. esta cerrado bajo Modus Ponens: si ϕ,ϕ→ ψ ∈ L, entonces ψ ∈ L5. esta cerrado bajo Necesidad: si ϕ ∈ L, entonces 2ϕ ∈ L,6. esta cerrado bajo instancias de sustitucion: si ϕ ∈ L y ψ es una

instancia de sustitucion de ϕ, entonces ψ ∈ L.

Ejemplos:1. Para cada clase de marcos F , L(F) es una logica modal normal.2. El conjunto de todas las formulas modales es una logica modal nor-

malUna logica modal normal L es una sublogica de una logica modal nor-

mal L′ si L ⊆ L′; es este caso tambien decimos que L′ es una extension deL.

Las formulas que pertenecen a una logica modal normal L se llaman amenudo los teoremas de L.

Lema 59. Si {Li : i ∈ I} es una coleccion no vacıa de logicas modalesnormales entonces

⋂i∈I Li es una logica modal normal.

Puesto que hay logica modales normales (por ejemplo el conjunto detodas las formulas modales), hay la menor logica modal normal, que es lainterseccion de la familia de todas las logicas modales normales. Se denotapor K en honor a Saul Kripke.

45

46 7. LoGICAS MODALES NORMALES

Corolario 60. Para cada conjunto de formulas modales Γ, hay la me-nor logica modal normal que contiene a Γ.

Demostracion. Sea X la coleccion de todas las logicas modales norma-les que contienen a Γ. Puesto que hay una logica modal normal que contienea Γ, a saber el conjunto de todas las formulas, X es no vaıca. Por tanto⋂X es una logica modal normal. Claramente, Γ ⊆

⋂X . Por otra parte,

si L es una logica modal normal y Γ ⊆ L, entonces L ∈ X . Por tanto,⋂X ⊆ L. QED

La menor logica modal normal que contiene a Γ se denota por L(Γ).Observese que al estar L(Γ) cerrado bajo instancias de sustitucion, todainstancia de sustitucion de cualquier formula de Γ pertenece a L(Γ). Ası,K = L(∅),

Sea L una logica modal normal. Diremos que un modelo es un modelode L si todo teorema de L es valido en el modelo. Analogamente, diremosque un marco es un marco de L si todo teorema de L es valido en el marco.Dada una logica modal normal L, consideremos su clase de marcos

Marc(L) = {F : para cada ϕ ∈ L,F |= ϕ}

es decir la clase de los marcos en los que son validas todos los teoremas deL. Consideraremos tambien la clase de sus modelos

Mod(L) = {〈W,R, V 〉 : para cada ϕ ∈ L, 〈W,R, V 〉 |= ϕ}

Evidentemente:

L ⊆ L(Marc(L))

pero esta inclusion no tiene porque ser una igualdad. Por otra parte,

{〈W,R, V 〉 : 〈W,R〉 ∈ Marc(L)} ⊆ Mod(L)

Ahora bien, de que 〈W,R, V 〉 ∈ Mod(L) no se sigue que el marco 〈W,R〉pertenezca a Marc(L). Debe tenerse en cuenta que 〈W,R〉 ∈ Marc(L) si ysolo si para toda valoracion V en 〈W,R〉, el modelo 〈W,R, V 〉 ∈ Mod(L).

1. Extensiones axiomaticas del calculo LKK

Supongamos que anadimos al calculo LKK una serie de reglas Gentzende la forma

∅� ϕ,

que al no tener premisas se llaman axiomas, o mejor reglas Gentzen axiomati-cas, obteniendo un calculo G. Para G definimos los conceptos de derivacion,derivacion a partir de un conjunto de secuentes, etc. como en el caso de LKK .De modo analogo a como definimos la relacion `, definimos la relacion `G,y de modo analogo a como definimos la relacion `f , definimos la relacion`f

G.

2. AXIOMATIZACIONES TIPO HILBERT DE LAS LoGICAS MODALES NORMALES47

Proposicion 61. Consideremos un calculo Gentzen G obtenido a partirde LKK anadiendo reglas Gentzen axiomaticas. El conjunto de formulas

L(G) = {ϕ : `G ϕ}es una logica modal normal.

Demostracion. Puesto que las formuals de las formas 2(α → β) →(2α → 2β) y 2α ↔ ¬3¬α, 3α ↔ ¬2¬α son deducibles de acuerdo con`K , lo son de acuerdo con `G. Por otra parte, si ϕ y ϕ → ψ ∈ L(G),entonces `G ϕ y `G ϕ → ψ, con lo que los secuentes �ϕ y �ϕ → ψ sonderivables en G. Por tanto, �ψ es derivable en G, con lo que ψ ∈ L(G). Demodo parecido, si ϕ ∈ L(G), entonces �ϕ es derivable en G, por tanto �2ϕes derivable en G, por lo que ϕ ∈ L(G). Finalmente, si ϕ ∈ L(G), entonces,�ϕ es derivable en G, pero entonces para toda sustitucion σ, �σ(ϕ) esderivable en G, por lo que σ(ϕ) ∈ L(G). QED

2. Axiomatizaciones tipo Hilbert de las logicas modalesnormales

Dada una logica modal normal L, un conjunto de formulas Σ es unconjunto de axiomas para L si L = L(Σ), es decir si L es la menor logicamodal normal que incluye a Σ. Se dice que L es finitamente axiomatizablesi tiene un conjunto finito de axiomas.

Dado un conjunto finito Σ de axiomas para L existe un calculo estiloHilbert H(Σ) para L. Consta de los siguientes axiomas:

Axiomas de la logica clasica: todas las instancias de sustitucion delas tautologıas,Axioms K: las formulas de la forma 2(α→ β)→ (2α→ 2β),Axiomas propios: las instancias de sustitucion de las formulas en Σ,Axiomas de interdefinibilidad de 2 y 3: 2α↔ ¬3¬α, 3α↔ ¬2¬α

y de las siguientes reglas de inferencia:Regla Modus Ponens: de α, α→ β inferir β.Regla de necesidad: de α inferir 2α.

Diremos que las instacias de sustitucion de las formulas elemento de Σ sonlos axiomas propios del calculo H(Σ).

Una demostracion en un calculo estilo Hilbert es una sucesion finita deformulas tal que cada uno de los miembros de la sucesion o es un axiomadel calculo o se obtiene de formulas anteriores en la sucesion por aplicacionde alguna de las reglas de inferencia. Se dice que una demostracion es unademostracion de su ultima formula. Una formula es demostrable en el calculosi hay una demostracion (en el calculo) de ella.

Proposicion 62. Si Σ es un conjunto finito de axiomas para L, entoncesL es el conjunto de formulas demostrables en el calculo H(Σ).

La menor logica modal normal K se axiomatiza mediante el conjuntovacıo de axiomas. Su calculo estilo Hilbert H(∅) consta pues de los axiomas:


Axiomas de la logica clasica: todas las instancias de sustitucion delas tautologıas,Axioms K: las formulas de la forma 2(α→ β)→ (2α→ 2β),Axiomas de interdefinibilidad de 2 y 3: 2α↔ ¬3¬α, 3α↔ ¬2¬α

y de las siguientes reglas de inferencia:

Regla Modus Ponens: de α, α→ β inferir β.Regla de necesidad: de α inferir 2α.

este calculo no tiene axiomas propios. Lo denotaremos porHK para recordarque es el calculo que axiomatiza la logica K.

La siguiente proposicion nos da una lista de teoremas de la of any normalmodal logic.

Proposicion 63. Para cualesquiera formulas α and β las formulas

(1) 2(α ∧ β)↔ (2α ∧2β)(2) 3(α ∨ β)↔ (3α ∨3iβ)(3) (2α ∨2β)→ 2(α ∨ β)(4) 3(α ∧ β)→ (3α ∧3iβ)(5) ¬2α↔ 3¬α.

son teoremas de K y por tanto de toda logica modal normal.

Algunas formulas importantes que sirven para axiomatizar las logicasmodales normales mas estudiadas son:

T 2p→ p 2p� p4 2p→ 22p 2p� 22pB p→ 23p p� 23pE 3p→ 23p 3p� 23pD 2p→ 3p 2p� 3pM 23p→ 32p 23p� 32pG 32p→ 23p 32p� 23pL 2(2p→ p)→ 2p, axioma de Lob 2(2p→ p) � 2pGrz 2(2(p→ 2p)→ p)→ p 2(2(p→ 2p)→ p) � p

Las logicas modales normales se suelen denotar con la letra K seguidade las letras para las formulas que las axiomatizan. Por ejemplo KT denotala logica axiomatizada por la formula T . Por razones historicas, hay logicasque usualmente se denotan de otro modo. Vamos a dar una lista de logicasimportantes. Primero daremos su nombre mas comun.

4. RELACIONES DE DEDUCIBILIDAD 49

S4 es la logica KT4.S5 es la logica KT4B, tambien la KT4E.T es la logica KTB es la logica KTBGL es la logica KL, llamada tambien logica de la demostrabilidad.D es la logica KDD4 es la logica KD4

3. Relaciones de consecuencia

Sea L una logica modal normal. La relacion de consecuencia localasociada a L se define como sigue. Sean ϕ una formula modal y Σ un conjuntode formulas modales. Se dice que ϕ es una L-consecuencia local de Σ, yescribimos Σ |=lL ϕ, si para todo modelo 〈W,R, V 〉 ∈ Mod(L) y para todow ∈W tal que para cada ψ ∈ Σ, w sat. ψ ocurre que w sat. ϕ.

La relacion de consecuencia global asociada a L se define como sigue.Sean ϕ una formula modal y Σ un conjunto de formulas modales. Se diceque ϕ es una L-consecuencia global de Σ, y escribimos Σ |=gL ϕ, si paratodo modelo 〈W,R, V 〉 ∈ Mod(L) tal que para cada ψ ∈ Σ, 〈W,R, V 〉 |= ψocurre que 〈W,R, V 〉 |= ϕ.

4. Relaciones de deducibilidad

A cada logica modal normal podemos asociar dos relaciones de deduci-bilidad, la local o debil y la global o fuerte.

Sea L una logica modal normal. Una demostracion de ϕ a partir de Σen L es una sucesion finita de formulas cuyos elementos son elementos de Lo de Σ, o se obtienen de formulas anteriores en la sucesion por aplicacion dela regla Modus Ponens.

Diremos que ϕ es localmente deducible en L, o L-deducible paraabreviar, de un conjunto de formulas Σ, en sımbolos Σ `L ϕ, si existe unademostracion de ϕ a partir de Σ en L.

De la definicion se sigue que si ϕ is localmente deducible de Σ en L,lo es de un subconjunto finito de Σ. Claramente las formulas localmentededucibles de el conjunto vacıo de formulas en L son los teoremas de L.

La relacion de deducibilidad local hereda de la logica clasica algunas desus propiedades:

Proposicion 64 (Teorema de deduccion). Para toda logica modal nor-mal L, todo conjunto de formulas Σ y cualesquiera formulas α, β,

si Σ ∪ {α} `L β entonces Σ `L (α→ β).

El estudio de la deducibilidad local en L se reduce, gracias al teoremade deduccion, al estudio de los teoremas de L.


Proposicion 65. Para toda logica modal normal L y cualesquiera formu-las β0, . . . , βn, α,

{β0, . . . , βn} `L α sii β0 ∧ . . . ∧ β1 → α ∈ L.

Demostracion. Recuerdese que la formula

(β0 ∧ . . . ∧ β1 → α)↔ (β0 → (β1 → . . . (βn → α) . . .)

es una instancia de sustitucion de una tautologıa.Supongamos que {β0, . . . , βn} `L α. El teorema de deduccion aplicado

reiteradamente nos da que (β0 → (β1 → . . . (βn → α) . . .) es un teoremade L. Utilizando la tautologıa anterior obtenemos que lo es (β0 ∧ . . .∧ β1 →α). La otra implicacion se obtiene de la tautologıa anterior por aplicacionrepetida de Modus Ponens. QED

Lema 66. Para toda logica modal normal L y cualesquiera formulasβ0, . . . , βn, α,

si {β0, . . . , βn} `L α entonces {2β0, . . . ,2βn} `L 2α.

Demostracion. Por la proposicion 65. Se deja como ejercicio. QED

La relacion de deducibilidad debil en L es correcta y completa relativa-mente a la relacion de consequencia local de L, la determinada por la clasede todos los modelos de L. Es decir:

Σ `L ϕ iff Σ |=lL ϕ.

Este resultado se demostrara mas adelante.

Capıtulo 8

Algunos resultados de correspondencia

Presentamos algunos resultados de la forma

La formula α es valida en el marco F sii F tiene la propiedad Φ.

Cuando se dispone de un resultado de este tipo se dice que la formula αcorresponda a la propiedad Φ.

Desde la perspectiva que este tipo de resultados introducen se puedeafirmar que las formulas modales, y mas en general los conjuntos de formulasmodales, sirven para describir propiedades de los marcos de Kripke. Loslenguajes modales sirven para este fin. Algunas clases de marcos puedendefinirse mediante formulas modales de este modo pero otra no.

Demostraremos algunas de las correspondencias de la tabla que hay acontinuacion.

2p→ p R es reflexiva2p→ 22p R es transitivap→ 23p R es semetrica2p→ 3p R es serial3p→ 2p R es una funcion3p↔ 2p R es una funcion con dominio W

Proposicion 67. La formula 2p → p es valida en un marco F sii larelacion R es reflexiva.

Demostracion. Supongamos que R es reflexiva. Seat V una valoracionen F y sea w ∈W . Si 2p es verdadera en w, puesto que wRw, tenemos quep es verdadera en w. Por tanto, 2p→ p es verdadera en w. Concluimos puesque 2p→ p es valida en F . Para demostrar la otra implicacion, supongamosque 2p→ p es valida en F . Sea w ∈W y consideremso cualquier valoracionV en F al que V (p) = {v ∈ W : wRv}. En tal caso, 2p es verdadera en wen el modelo 〈F , V 〉. Puesto que 2p → p es verdadera en w en el modelo〈F , V 〉, pes verdadera en w en el modelo 〈F , V 〉. Por tanto, w ∈ V (p), conlo cual wRw. Concluimos que R es reflexiva. QED

Proposicion 68. La formula 2p → 22p es valida en un marco F siila relacion R es transitiva.

Demostracion. La demostracion de la parte facil, que es la implica-cion de derecha a izquierda se deja como ejercicio. Para demostrar la otra

51

52 8. ALGUNOS RESULTADOS DE CORRESPONDENCIA

implicacion, supongamos que 2p → 22p es valida en F y que w, v, u ∈ Wson tales que wRv and vRu. Sea V una valoracion en F tal que V (p) = {x ∈W : wRix}. Claramente, 2p es verdadera en w en 〈F , V 〉. Puesto que porsuposicion 2p→ 22p tambien es verdadera en w, 22p es verdadera en w.Por tanto, 2p ies verdadera en v y p lo es en u. Por tanto, wRu. Concluimospues que R es transitiva. QED

Proposicion 69. La formula p→ 23p es valida en un marco F sii larelacion R es simetrica.

Demostracion. Supongamos que p→ 23p es valida en F y que w, v ∈W son tales que wRv. Sea V una valoracion cualquiera tal que V (p) = {w}.Puesto que p y p → 23p son verdaderas en w, 23p es verdadera en w.Por tanto, 3p es verdadera en v. La unica posibilidad de que esto sea ası esque vRw. Concluimos pues que R es simetrica. La demostracion de la otraimplicacion se deja como ejercicio. QED

Proposicion 70. La formula 2p→ 3p es valida en un marco F sii larelacion R es serial (i.e. para cada w ∈W existe v ∈W tal que wRv).


Capıtulo 9

Teoremas de completud

Para cada logica modal normal disponemos de tres objetos definidossintacticamente. La logica misma, la deducibilidad local asociada y la dedu-cibilidad global.

Como hemos visto, una clase de marcos F define una logica L(F), el con-junto de las formulas validas en todo marco de F. Por otra parte, una logicaL puede utilizarse para definir la clase de marcos Marc(L) cuyos elementosson los marcos en que todo teorema de L es valido.

Dada una logica L es natural preguntarse si la logica L(Fr(L)) es o noigual a L. Es claro que L ⊆ L(Fr(L)). La otra inclusion es la problematica.Se cumple para unas logicas y para otras no.

Podemos formular la pregunta analoga respecto a los modelos. A cadalogica L le corresponde la clase de modelos Mod(L), la de los modelos en losque todos los teoremas de L son validos. Para cada logica L, podemos pre-guntarnos si el conjunto Val(Mod(L)) de todas las formulas validas en todoslos modelos en Mod(L) es igual o no a L. Es claro que L ⊆ Val(Mod(L)).En este caso la otra inclusion se cumple para toda logica.

Una logica modal normal L se dice que es completa respecto a marcos siL = L(Marc(L)). Una logica L se dice que esta determinada por una clasede marcos F si L = L(F).

La observacion siguiente es importante.

Proposicion 71. Si una logica esta determinada por alguna clase demarcos entonces es completa respecto a marcos.

Demostracion. Supongamos que L esta determinada por la clase demarcos F. Entonces, F ⊆ Fr(L). Por tanto la logica de la clase de marcosFr(L) esta incluida en la logica de la clase de marcos F. Puesto que estaultima logica es L, concluimos que L = L(Marc(L)), en otras palabras quees completa respecto a marcos. QED

Una logica se dice que es completa respecto a modelos si L = Val(Mod(L)).Como veremos toda logica es completa respecto a modelos.

Los teoremas de correccion para las relaciones de deducibilidad asociadasa una logica normal L son los siguientes:

Teorema 72. Para cada formula ϕ y cada conjunto de formulas Σ

(1) si Σ `L ϕ, entonces Σ |=lL ϕ.

53

54 9. TEOREMAS DE COMPLETUD

Teorema 73. Para cada formula ϕ y cada conjunto de formulas Σ

(2) si Σ `gL ϕ, entonces Σ |=gL ϕ.

Procedemos a demostrar el primer teorema. Supongamos que Σ `L ϕ.Sea ϕ0, . . . , ϕn una demostracion en L de ϕ a partir de Σ. Demostremos porinduccion completa que para cada i si i ≤ n, Σ |=lL ϕi. Supongamos quepara todo k ≤ i ocurre que si k ≤ n, entonces Σ |=lL ϕk. Supongamos quei ≤ n y veamos que Σ |=lL ϕi. Si ϕi ∈ Σ, es claro. Si ϕi ∈ L, tambien puesen tal caso ϕi es verdadera en todo punto de todo modelo se L, en particularen los puntos en los que las formulas de Σ son veraderas. Si ϕi se obtiene porModus Ponens de formulas anteriores, digamos ϕm y ϕl, supongamos queϕl es ϕm → ϕi. Entonces m, l ≤ i ≤ n. Por tanto por la hipotesis inductivaΣ |=lL ϕm y Σ |=lL ϕm → ϕi. Supongamos que 〈W,R, V 〉 es un modelo deL y w ∈ W es tal que toda formula de Σ es verdadera en w. Entonces ϕm

y ϕm → ϕi son verdaderas en w. Por tanto lo es ϕi. Concluimos pues queΣ |=lL ϕi.

Se deja como ejercicio la demostracion del otro teorema de correccion.

1. L-teorıas, conjuntos L-consistentes, L-teorias primas,relativamente maximales y L-consistente maximales

Por comodidad abreviemos una contradiccion fijada, por ejemplo p∧¬pcon ⊥. Ası en todo modelo M y en todo punto w del modelo, M, w 6|= ⊥.

Una logica modal normal es consistente si no es el conjunto de todas lasformulas. Asi,

Lema 74. Una logica modal normal L es consistente sii ⊥ 6∈ L

Demostracion. Observemos que ⊥ → ϕ es de la forma de una tau-tologıa, para cada formula ϕ. Por tanto ⊥ → ϕ ∈ L. Por tanto si ⊥ ∈ L,puesto que L esta cerrada por Modus Ponens, ϕ ∈ L. Asi si ⊥ ∈ L, L no esconsistente. Por otra parte si L no es consistente, puesto que toda formulapertenece a L, ⊥ ∈ L. QED

Fijemos una logica modal normal consistente L.

Lema 75. Para cada formula ϕ,1. ¬ϕ `L ϕ→ ⊥2. ϕ→ ⊥ `L ¬ϕ3. ⊥ `L ϕ

Demostracion. 1. Tenemos que ¬ϕ→ (ϕ→ ⊥) es una tautologıa. Portanto pertenece a L. Utilizando Modus Ponens obtenemos que ¬ϕ `L ϕ →⊥.

2. Se demuestra de modo analogo.3. Se deja como ejercicio. QED

Lema 76. Para cada formula ϕ,1. Si Σ `L ϕ0, . . . ,Σ `L ϕn y {ϕ0, . . . , ϕn} `L ψ, entonces Σ `L ψ.

1. L-TEORIAS, CONJUNTOS L-CONSISTENTES, L-TEORIAS PRIMAS, RELATIVAMENTE MAXIMALES Y L-CONSISTENTE MAXIMALES55

2. Si Σ `L ϕ y Σ `L ϕ→ ψ, entonces Σ `L ψ.3.

Demostracion. (1) Supongamos que Σ `L ϕ0, . . . ,Σ `L ϕn. Sea paracada i ≤ n Di una demostracion en L de ϕi a partir de Σ. Sea D una de-mostracion en L de ψ a partir de {ϕ0, . . . , ϕn}. Claramente la concatenacionD0 . . . DnD de las demostaciones es una demostracion en L de ψ a partir deΣ.

(2) Utilizaremos (1). Es claro que {ϕ,ϕ→ ψ} `L ψ. Entonces si Σ `L ϕy Σ `L ϕ→ ψ, por (1) obtenemos que Σ `L ψ. QED

Lema 77. Si Σ `L ϕ, entonces para cada conjunto de formulas ∆, Σ ∪∆ `L ϕ.

Demostracion. Toda demostracion de ϕ en L a partir de Σ es tambienuna demostracion de ϕ en L a partir de Σ ∪∆. QED

Un conjunto Σ de formulas es L-consistente si Σ 6`L ⊥. En caso contra-rio se dice que es L-inconsistente. De la definicion se sigue inmediatamenteque Σ es L-inconsistente si y solo si alguno de sus subconjuntos finitos lo es.

Lema 78. Σ `L ϕ si y solo si Σ ∪ {¬ϕ} es L-inconsistente.

Demostracion. Si Σ `L ϕ, puesto que Σ∪{¬ϕ} `L ϕ→ ⊥, obtenemosque Σ ∪ {¬ϕ} ` ⊥, es decir que Σ ∪ {¬ϕ} es L-inconsistente. Por otraparte, si Σ ∪ {¬ϕ} es L-inconsistente, Σ ∪ {¬ϕ} `L ⊥. Por tanto, por elteorema de deduccion, Σ `L ¬ϕ→ ⊥. Ahora bien, ¬ϕ→ ⊥ `L ϕ. Por tantoΣ `L ϕ. QED

Lema 79. Σ es inconsistente sii para toda formula ϕ, Σ `L ϕ.

Demostracion. Si para toda formula ϕ, Σ `L ϕ, en particular Σ `L ⊥,por lo que es L-inconsistente. Si Σ es L-inconsistente, Σ `L ⊥. Por tanto,puesto que para toda formula ϕ, ⊥ `L ϕ, tenemos que para toda formula ϕ,Σ `L ϕ. QED

Un conjunto de formulas Σ es una L-teorıa si para cada formula ϕ talque Σ `L ϕ ocurre que ϕ ∈ Σ.

Una L-teorıa Σ es ϕ-relativamente maximal si Σ 6`L ϕ y para todaformula ψ 6∈ Σ, Σ ∪ {ψ} `L ϕ.

Una L-teorıa Σ es prima si es L-consistente y para cualesquiera formulasϕ,ψ, si ϕ ∨ ψ ∈ Σ, entonces ϕ ∈ Σ o ψ ∈ Σ.

Una L-teoria Σ es relativamente maximal si hay una formula ϕ talque Σ es ϕ-relativamente maximal.

Una L-teorıa Σ es L-consistente maximal si es L-consistente y paracada formula ϕ 6∈ Σ, Σ ∪ {ϕ} es L- inconsistente.

Lema 80. Si Γ es un conjunto de formulas y ϕ es una formula tal queΓ 6`L ϕ, entonces existe una L-teorıa ϕ-relativamente maximal Σ tal queΓ ⊆ Σ.


Demostracion. Consideremos una enumeracion ψ0, ψ1, ψ2, . . . , ψn, . . .de las formulas del lenguaje. Vamos a definir en pasos sucesivos una sucesionde conjuntos de formulas Σ0,Σ1, . . . , Σn, . . . tal que

1. Σ0 = Γ2. Para cada n, Σn 6`L ϕ3. Para cada n, Σn ⊆ Σn+1

La definicion de la sucesion es:Σ0 = Γ

Σn+1 ={

Σn si Σn ∪ {ψn} `L ϕΣn ∪ {ψn} si Σn ∪ {ψn} 6`L ϕ

Claramente se cumplen las condiciones deseadas. Sea

Σ =⋃n

Σn

Es decir, para cada formula ψ,

ψ ∈ Σ si y solo si hay n tal que ψ ∈ Σn.

Veamos que Σ es ϕ-relativamente maximal.1. Σ 6`L ϕ. En efecto, si Σ `L ϕ, hay ∆ ⊆ Σ finito tal que ∆ `L ϕ. De la

condicion 3 anterior y de que ∆ es finito se sigue que hay n tal que ∆ ⊆ Σn.Por tanto, Σn ` ϕ. Pero esto contracide la condicion 2 anterior.

2. Si ψ 6∈ Σ, entonces Σ ∪ {ψ} `L ϕ. En efecto, supongamos que ψ 6∈ Σy que Σ ∪ {ψ} 6`L ϕ Sea n tal que ψ es ψn. Entonces Σn ∪ {ψn} 6`L ϕ. Portanto ψn ∈ Σn+1 ⊆ Σ. Pero esto es absurdo. Por tanto Σ∪{ψ} `L ϕ. QED

Corolario 81. Para cada conjunto de formulas Σ y cada formula α,Σ `L α sii α pertenece a toda L-teorıa relativamente maximal que incluye aΣ.

Demostracion. Si Σ `L α y Γ es L-teorıa relativamente maximal queincluye a Σ, entonces Γ `L α. Por tanto α ∈ Γ. Por otra parte, si Σ 6`L αentonces hay L-teorıa Γ α-relativamente maximal tal que Σ ⊆ Γ. Puesto queα 6∈ Γ, tenemos que α no pertenece a toda L-teorıa relativamente maximalque incluye a Σ. QED

Proposicion 82. Sea Σ una L-teorıa. Son equivalentes1. Σ es ϕ-relativamente maximal para alguna formula ϕ.2. Σ es prima3. Σ es L-consistente y para toda formula ϕ, ϕ ∈ Σ o ¬ϕ ∈ Σ.4. Σ es L-consistente maximal.

Demostracion. 1 implica 2. Supongamos que Σ es ϕ-relativamentemaximal. Supongamos que ψ ∨ δ ∈ Σ. Puesto que Σ es ϕ-relativamentemaximal, si ψ, δ 6∈ Σ, Σ ∪ {ψ} `L ϕ y Σ ∪ {δ} `L ϕ. Por el teorema de ladeduccion Σ `L ψ → ϕ y Σ `L δ → ϕ. Ademas (ψ → ϕ) → ((δ → ϕ) →((ψ ∨ δ) → ϕ)) es instancia de sustitucion de una tautologıa. Por tantopertenece a L. Se sigue que Σ `L (ψ ∨ δ)→ ϕ. Por tanto Σ ∪ {ψ ∨ δ} `L ϕ.


Esto implica que, Σ `L ϕ, pero esto no es posible al ser Σ ϕ-relativamentemaximal. Ası ψ ∈ Σ o δ ∈ Σ. Por tanto Σ es una L-teorıa prima.

2 implica 3. Supongamos que Σ es prima. Por tanto es L-consistente.Ademas, para cada ϕ, ϕ∨¬ϕ ∈ Σ. Por tanto, al ser prima, ϕ ∈ Σ o ¬ϕ ∈ Σ.

3 implica 4. Supongamso que Σ es L-consistente y para toda formula ϕ,ϕ ∈ Σ o ¬ϕ ∈ Σ. Supongamos que ϕ 6∈ Σ. Por tanto, ¬ϕ ∈ Σ. Asi, Σ ∪ {ϕ}es inconsistente. Por tanto Σ es L-consistente maximal.

4 implica 1. Si Σ es L-consistente maximal, para cada ϕ 6∈ Σ, Σ esϕ-relativamente maximal. QED

Proposicion 83. Para todo conjunto de formulas L-consistent y maxi-mal Σ,

(1) Si Σ `L α, entonces α ∈ Σ,(2) α ∧ β ∈ Σ sii α ∈ Σ and β ∈ Σ,(3) α ∨ β ∈ Σ sii α ∈ Σ o β ∈ Σ,(4) α→ β ∈ Σ sii α 6∈ Σ o β ∈ Σ,(5) ¬α ∈ Σ sii α 6∈ Σ.


2. El modelo canonico

Para motivar la definicion del modelo canonico consideremos un modelocualquiera 〈F , V 〉. Dado w ∈W observemos que el conjunto

Σ(w) = {α : 〈F , V 〉, w |= α}

es un conjunto maximal K-consistente que contiene toda formula valida enel modelo. Ası, si el modelo es un modelo de L, Σ(w) es L-consistente.

Puede ocurrir que existan w,w′ ∈ W distintos que no se puedan distin-guir mediante una formula modal, es decir que tengan la propiedad de quelos conjuntos Σ(w) y Σ(w′) sean el mismo. Desde este punto de vista pode-mos decir que un conjunto de formulas maximal K-consistente caracterizaun tipo de estado o de mundo posible.

Un tipo de estado es compatible con una logica L si todo teorema de Lpertenece a el. El conjunto de estados del modelo canonico para una logicaL consiste en todos los tipos de estados compatibles con L. Una formulasera verdadera en un estado del modelo canonico si y solo si pertenece alestado. De este modo, puesto que si una formula α no es un teorems deL, el conjunto L ∪ {¬α} es L-consistente, habra un conjunto maximal L-consistente tal que incluye a L ∪ {¬α}, por tanto α no sera valida en elmodelo canonico.

Para explicar como definir la relacion de accesibilidad del modelo canoni-co de una logica modal normal L, consideremos un modelo 〈F , V 〉 de L yobservemos que si w, v ∈W son tales quet wRv entonces {α : 2α ∈ Σ(w)} ⊆Σ(v). Tomaremso esta urltima condicion como la condicion para definir larelacion de accesibilidad del modelo canonico.


La definicion del modelo canonico deuna logica modal normal es la si-guiente.

Sea L una logica consistente. Definamos el conjunto de estados del mo-delo canonico por:

WL = {∆ : ∆ es un conjunto maximal L-consitent de formulas },y la relacion RL en WL por

∆RL∆′ sii {α : 2α ∈ ∆} ⊆ ∆′.El marco FL = 〈WL, RL〉 es el marco canonico de L. El modelo canonico

de L es el modelo ML = 〈FL, VL〉, donde VL es la valoracion en el marcocanonico de L definida por:

VL(p) = {∆ ∈WL : p ∈ ∆},para cada letra proposicional p.

El resultado principal sobre el modelo canonico de L es el lema funda-mental.

Lema 84 (Lema Fundamental). Parta todo conjunto maximal y L-consistentede formulas ∆ y toda formula α,

〈FL, VL〉,∆ sat. α sii α ∈ ∆.

Demostracion. Se demuestra por induccion en α. Para las letras pro-posicionales vale por la definicion de la valoracion VL. Para las conectivas sesigue de las propiedades de los conjuntos maximal L-consistentes del lema 83.para el operador modal se argumenta como sigue. Observemos primero quegracias a la hipotesis inductiva temenemos que

〈FL, VL〉,∆ |= 2α sii ∀∆′ ∈WL si ∆RL∆′entonces α ∈ ∆′

sii ∀∆′ ∈WL si {β : 2β ∈ ∆} ⊆ ∆′ entonces α ∈ ∆′

Ahora, si 2α ∈ ∆ y {β : 2β ∈ ∆} ⊆ ∆′, claramente tenemos que α ∈ ∆′.Por tanto obtenemos la implicacion dr izquierda a derecha de la condicionque estamos demostrando. Para demostrar la otra implicacion, supongamosque ∀∆′ ∈ WL, si {β : 2β ∈ ∆} ⊆ ∆′ entonces α ∈ ∆′. Veamos que elconjunto {β : 2β ∈ ∆} ∪ {¬α} no es L-consistente. Si lo fuera existirıa unconjunto maximal L-consistente que lo extiende y por la suposicion tendrıacomo elemento a α, lo que no es posible. Por tanto, {β : 2β ∈ ∆} `L α. Seaahora {β0, . . . , βn} ⊆ {β : 2β ∈ ∆} tal que {β0, . . . , βn} `L α. Entonces,{2β0, . . . ,2βn} `L 2α, y puesto que {2β0, . . . ,2βn} ⊆ ∆, obtenemos que2α ∈ ∆. QED

Corolario 85. Para toda logica consistente L y toda formula α,

α ∈ L sii α es valida en el modelo canonico de L.

Demostracion. Por el lema 81, una formula α ∈ L sii α pertenece atoco conjunto maximal L-consistente. Por tanto, α ∈ L sii α es verdaderaen todo punto del modelo canonico de L. QED

3. LOS TEOREMAS DE COMPLETUD 59

3. Los teoremas de completud

El primer teorema de completitud que demostramos es una consecuenciainmediata del ultimo corolario. .

Teorema 86. Para toda logica L, todo conjunto de formulas Σ y todaformula α,

Σ `L α iff Σ |=lL α.

Demostracion. La direccion de izquierda a derecha es una consecuen-cia de que el conjunto de formulas verdadera en un punto de un modelo deL contiene todas las formulas de L y esta cerrado bajo Modus Ponens. Parademostrar la otra inclusion supongamos que Σ 6`L α. En tal caso, el conjuntoΣ∪{¬α} es L-consistente. Se pues ∆ un conjunto L- consistente y maximalque lo incluye. Este conjunto es uno de los elementos del modelo canonicode L, toda formula de Σ es verdadera en ∆ y α es falsa en ∆. Puesto que elmodelo canonico de L es un modelo de L, concluimos que Σ 6|=lL α. QED

Teorema 87. Toda logica es completa respecto a modelos.

Demostracion. Sea L una logica. Si L es la logica insonsistente, notiene modelos. Por tantoel conjunto de formulas validas en todo modelo deL es el conjunto de todas las formulas. Por tanto es la logica inconsistente.Si L es consistente, por el ultimo corolario el modelo canonico de L es unmodelo de L. Por tanto si una formula es valida en todo modelo de L, lo esen el modelo canonico de L. Oir tanto es un teorema de L. QED

Teorema 88. La logica K es completa respecto a marcos.

Demostracion. Puesto queK is la menor logica modal normal, es claroque todo teorema de K es valido en todo marco. Ası, la clase de marcos deK es la clase de todos los marcos. Pero ademas, si una formula es valida entodo marco, lo es en el modelo canonico de K. Por tanto es un teorema deK. QED

Corolario 89. Una formula es un teorema de K sii es valida en elmarco canonico de K.

El paso fundamental en la demostracion de que K es completa respectoa marcos consiste en la observacion de que el marco canonico de K es unmarco de K, es decir es un marco en el que todo teorema de K es valido.Cualquier logica modal normal que tenga esta propiedad es completa respec-to a marcos. Las logicas con esta propiedad, las que sus teorems son validosen su marco canonico, se llaman canonicas.

Teorema 90. Toda logica canonica es completa respecto a marcos.

Demostracion. Si L es canonica, FL ∈ Fr(L) y por tanto toda formulavalida en todos los marcos de L es valida en FL y por tanto en el modelocanonico de L, lo que implica que es un teorema de L. QED


Uno de los metodos para demostrar que una logica es completa respectoa marcos consiste en demostrar que es canonica. El modo mas comun de ha-cerlo consiste en seleccionar un conjunto de axiomas de la logica y encontraruna propiedad de los marcos que sea la que corresponde a los axiomas. Unavez hecho esto se demuestra que el marco del modelo canonico (el marcocanonico) tiene la propiedad. Ası, demostra la completitud de una logicamediante el marco canonico puede verse como una aplicacion de un resulta-do de correspondencia. A continuacion demostraremos que algunas logicasson completas respecto a marcos por este metodo.

Proposicion 91. Sea L una logica.

(1) Si T ∈ L, entonces la relacion del marco canonico de L es reflexiva.(2) Si 4 ∈ L, entonces la relacion del marco canonico de L es transitiva.(3) Si B ∈ L, entonces la relacion del marco canonico de L es simetrica.(4) Si D ∈ L, entonces la relacion del marco canonico de L es serial.

Demostracion. (1) Supongamos que 2p → p ∈ L. En tal caso, paracada formula α, 2α → α es verdadera en todo punto del modelo canonico.Sea Let ∆ ∈ WL y supongamos que 2α ∈ ∆. Ası, 2α es verdadera en ∆y por tanto α es verdadera en ∆ (ya que lo es 2p → p) . Es decir α ∈ ∆.Concluimos pues que ∆RL∆.

(2) Supongamos que 4 ∈ L. Por tanto toda formula α, 2α → 22αes verdadera en todo punto del modelo canonico de L. Supongamos que∆,∆′,∆′′ ∈WL son tales que ∆RL∆′ y ∆′RL∆′′. Si 2α ∈ ∆, entonces estaformula es verdadera en ∆ lo que implica que lo es 22α, pues 2α→ 22α esverdadera en ∆ . Por tanto, 22α ∈ ∆. Ası, 2α ∈ ∆′ y α ∈ ∆′′. Concluimosque ∆RL∆′′.

(3) Supongamos que B ∈ L. Entonces, para cada formula α, α→ 23αes verdadera en todo punto del modelo canonica de L. Supongamos que∆,∆′ ∈WL′ son tales que ∆RL∆′ y que 2α ∈ ∆′. Entonces 2α es verdaderaen ∆′ con lo que 32α tambien es verdadera en ∆. De este modo 23¬α esfalsa en ∆ y lo es ¬α. Por ello, α es verdadera en ∆ con lo cual α ∈ ∆.Concluimos que ∆′RL∆.

(4) Supongamos que D ∈ L. Entonces, cada formula α, 2α → 3α esverdadera en todo punto del modelo canonica de L. Sea ∆ ∈ WL. Consi-deremos el conjunto {α : 2α ∈ ∆}. Este conjunto es L-consistent. De locontrario, 2⊥ serıa deducible debilmente (solo con MP) de ∆ en L. Pero ental caso 3⊥ serıa verdadera en ∆. Por lo que habrıa un punto en el que ⊥serıa verdadera y esto no es posible. Por el lema de Lindenbaum el conjunto{α : 2α ∈ ∆} puede extenderse a un conjunto L-consistente maximal s∆′.Entonces, ∆RL∆′. QED

Teorema 92. Cualquier logica axiomatizada con formulas pertenecien-tes al conjunto

{T, 4, B,D}

3. LOS TEOREMAS DE COMPLETUD 61

es canonica y por tanto completa respecto a marcos. En particular lo son laslogicas KT , S4, S5, B, KD.

Demostracion. Por los teoremas de correspondencia y la ultima pro-posicion. QED

Hay logicas que son completas respecto a marcos pero sin embargo noson canonicas. Ub ejemplo es la logica de la demostrabilidad GL

Para concluir la seccion demostramos los teoremas de completitud paralas relaciones de deducibilidad global.

Corolario 93. Para toda logica L, todo conjunto de formulas Σ y todaformula α,

Σ `gL α iff Σ |=gL α.

Demostracion. Utilizamos los teoremas anteriores y los resultados querelacionan na deducibilidad logcal con la global asi como los que relacionanla consecuencia local y la global.

Σ `gL α iff 2Σ `lL αiff 2Σ |=lL αiff Σ |=gL α.

QED

Capıtulo 10

Logica modal cuantificacional

1. Sintaxis

El lenguaje de la logica modal cuantificacional consta del siguiente vo-cabulario:

1. Variables: x, y, z, x1, y1, z1, . . .2. Constantes: c, d, c1, d1, . . .3. Sımbolos relacionales: para cada n, sımbolos relacionales de ariedadn,

Rn1 , R

n2 , R

n3 , . . .

4. Conectivas: ∧,∨,¬,→5. Cuantificadores: ∀, ∃6. Operadortes modales: 2, 3

7. Parentesis

Denotaremos con V ar el conjunto de variables y con Con el de constan-tes.

Las constantes y los sımbolos relacionales son los sımbolos propiosdel lenguaje. Las expresiones son las sucesiones finitas de elementos delvocabulario y los terminos son las variables y las constantes.

Las formulas atomicas son las expresiones de la forma Rt1 . . . tn, dondeR es un sımbolo relacional n-ario y t1, . . . , tn son terminos.

Las formulas se definen de acuerdo con las siguientes reglas:

1. Toda formula atomica es una formula,2. Si α es una formula, lo son ¬α, 2α y 3α3. Si α y β son formulas, tambien lo son (α ∧ β), (α ∨ β) y (α→ β)4. Si α es una formula y x es una variable, ∀xα y ∃xα son fomulas.

El arbol genealogico de una formula se define de modo analogo a comose hace en logica de primer orden, ası como los conceptos de subformula,aparicion libre y aparacion ligada de una variable en una formula. Unaformula se dice que es abierta si contiene alguna aparicion libre de algunavariable. En caso contrario se dice que es cerrada o que es una sentencia. Laoperacion de sustitucion de variables por terminos en una formula se defineanalogamente a como se hace en logica de primer orden.

63

64 10. LoGICA MODAL CUANTIFICACIONAL

2. Las interpretaciones del lenguaje

Contextos opacos o intensionales. Los contextos opacos son aquellosen que algun principio de sustitucion falla. Al estudiar la logica proposicionalmodal vimos algunos de los contextos opacos proposicionales, aquellos paralos que falla el principio de sustitucion de los equivalentes materiales:

si α(p) es un enunciado y β y γ son enunciados,α(p/β), β ↔ γ |= α(p/γ).

Ahora interesa considerar el principio de sustitucion

t ≈ t′, ϕ |= ϕ(t/t′)

que podemos llamar de sutitucion de terminos equireferenciales, principiode sustitucion de los identicos, o, en terminologıa de Leibniz, principio de laindiscernibilidad de los identicos.

Vamos a dar algunos tipos de contexto en los que este principio falla. Demomento no analizamos las razones por las que el principio no vale.

Citas.

La oracion (3) no se sigue de las oraciones (1) y (2):(1) 3 ≈ 2 + 1(2) La expresion ‘3’ tiene un unico sımbolo(3) La expresion ‘2 + 1’ tiene un unico sımbolo.

La oracion (6) no se sigue de (4) y (5):(4) El autor del Quijote es Cervantes(5) El pronuncio las palabras ‘El autor del Quijote’(6) El pronuncio las palabras ‘Cervantes’

Lenguaje indirecto.

La oracion (9) no se sigue de (7) y (8)(7) El autor del Quijote es Cervantes(8) Juan dijo que el autor del Quijote es Cervantes(9) Juan dijo que el autor del Quijote es el autor del Quijote

Actitudes proposicionales.

La oracion (12) no se sigue de (10) y (11)(10) El ladron es Juan(11) Pedro cree que el ladron entro por la ventana(12) Pedro cree que Juan entro por la ventana

De igual modo, la oracion (15) no se sigue de (13) y (14)(13) El autor del Quijote es Cervantes(14) Pedro sabe que el autor del Quijote es el autor del Quijote(15) Pedro sabe que el autor del Quijote es Cervantes

Intenciones.

2. LAS INTERPRETACIONES DEL LENGUAJE 65

La oracion (18) no se sigue de (16) y (17)(16) El profesor es Alegre(17) Pedro espera que llegue el profesor(18) Pedro espera que llegue Alegre.

Expresiones temporales.

La oracion (21) no se sigue de (19) y (20)(19) George Bush jr. es el presidente de Estados Unidos(20) En 1992 el presidente de Estados Unidos inicio la

Guerra del Golfo(21) En 1992 George Bush jr. inicio la Guerra del Golfo.

Modalidades aleticas.

La oracion (24) no se sigue de (22) y (23)(22) El numero de planetas es 9(23) 9 es necesariamente igual a 9(24) El numero de planetas es necesariamente igual a 9.

Modalidades de dicto y modalidades de re. Consideremos la ora-cion ultima anterior

(24) El numero de planetas es necesariamente igual a 9.

Esta oracion puede entenderse de dos maneras diferentes que se expresan demodo preciso en las siguientes (pseudo) formalizaciones

(34) ∃x(x es el numero de planetas ∧2x ≈ 9)(35) 2∃x(x es el numero de planetas ∧ x ≈ 9)

La segunda formalizacion expresa la lectura de dicto de la modalidad queaparece en (24) y la primera, la lectura de re. (34) es verdadera pues 9 esel numero de planetas y 9 es necesariamente igual a 9. Sin embargo (35) esfalsa pues el numero de planetas podrıa muy bien ser 8 en lugar de 9. (35)puede reformularse como

(35’) Es una verdad necesaria que el numero de planetas es igual a 9.Sin embargo (34) no admite una lectura utilizando ‘es una verdad necesariaque’. Afirma que existe un objeto con dos propiedades, la de ser el numerode planetas y la de ser necesariamente igual a 9. En la formula 2x ≈ 9se dice que una cosa (res) x tiene una propiedad (ser igual a 9) de modonecesario.

Una modalidad es de dicto cuando se aplica a una proposicion (dictum),y es de re cuando se aplica a un objeto para decir que tiene cierta propiedaden el modo expresado por la modalidad. Consideremos la siguiente oracion:

(36) Algo es bello necesariamente.

La lectura de dicto se expresa por


(36’) 2∃xBxque afirma que la proposicion existe algo bello es necesaria. La lectura de rese expresa por

(36”) ∃x2Bx,

que afirma que hay al menos una cosa que posee, ella, la propiedad de labelleza de modo necesario.

Veamos un ejemplo mas. Consideremos el enunciado

(37) Cada uno de los presentes pudo cometer el asesinato.

En este enunciado no hay ambiguedad. La modalidad se aplica de re y laformalizacion serıa ∀x3Ax. La formalizacion 3∀xAx formaliza el enunciado

(38) Es posible que todos los presentes cometieran el asesinato

en el que la modalidad se aplica de dicto.En el lenguaje formal la distincion de dicto/de re se traduce en una

distincion en el alcance de los operadores modales. Si 2 o 3 van seguidosde una sentencia, expresan una modalidad de dicto, pero si van seguidos deuna formula abierta expresan una modalidad de re.

Semanticamente la distincion tiene que ver con la permutacion de dostipos de cuantificadores: la cuantificacion sobre contextos o mundos posiblesimplıcita en los operadores modales y la cuantificacion sobre individuos.(36’) es vedadera si en todo mundo posible hay al menos un objeto bello.(36”) es verdadera si en nuestro mundo actual hay un objeto que en todomundo posible tiene la propiedad de la belleza. Evidentemente, entendidasası las cosas, (36”) implica (36) pero no a la inversa.

La logica modal cuantificacional hace inteligible la idea de que los obje-tos mismos poseen propiedades necesaria o contingentemente, independien-temente de como hablamos de ellos. Volviendo al ejemplo anterior, puedeser necesario que exista un objeto bello, pero ello no implica que cada ob-jeto que posee la propiedad de la belleza la posee de modo necesario. Esperfectamente coherente aceptar que es necesario que exista un objeto be-llo y aceptar tambien que cada objeto bello posee esta cualidad de modocontingente.

Veamos un ejemplo de logica temporal para inistir en la distincion.

(39) El presidente del gobierno espanol siempre medira mas de 1′75 m.(40) Jose Luis Rodriguez Zapatero siempre medira mas de 1′75 m.

Si entendemos (37) de dicto es (seguramente) falsa, pero si la entendemosde re dice lo mismo que (38) que es verdadera.

Cuantificacion sobre actuales o sobre posibles. En logica modalcuantificacional se presenta el problema siguiente. Los individuos que existenen un mundo posbile puede que no sean los mismos que existen en otromundo posible. Cervantes prodrıa no haber existido nunca, por tanto en

2. LAS INTERPRETACIONES DEL LENGUAJE 67

algun mundo posible Cervantes no es uno de sus individuos. A la hora deevaluar por ejemplo los enunciados universales en un mundo, ¿se debenconsiderar solo los individuos de este mundo o todos los individuos posibles,es decir de todos los mundos? Si se opta por la segunda alternativa tenemos lacuantificacion sobre posibles: se cuantifica sobre los individuos actuales, losdel mundo en que se evalua, mas todos los individuos de los demas mundosposibles. Si se opta por la primera alternativa tenemos la cuantificacion sobreactuales: se cuantifica sobre los individuos del mundo en que se evalua laformula, el mundo actual.

La interpretacion sobre posibles de la cuantificacion nos da la semanticade modelos con dominio constante y la cuantificacion sobre actuales la demodelos con dominio variable.

Nombres propios y descripciones definidas. Designadores rigi-dos. Hay varias teorıas sobre la semantica de los nombres propios, perobasicamente son dos. La teorıa que asimila la semantica de los nombres pro-pios a la de las descripciones definidas y la que considera a los nombrespropios como designadores rigidos.

Descripciones definidas. Algunos ejemplos de descripciones definidas son:

(41) el numero de planetas del sistema solar(42) el actual jefe del gobierno frances(43) el padre del actual presidente de los Estados Unidos.

Las descripciones definidas cambian de referencia al cambiar de mundoposible. El numero de planetas del sistema solar es 9 pero podrıa haber sidootro, por ejemplo 8. En una situacion del ultimo tipo la descripcion ‘el nume-ro de planetas del sistema solar’ refiere a 8 en lugar de a 9. Igualmente,‘elpadre del actual presidente de los Estados Unidos’ en la epoca de Clintonno referia a George Bush (padre), ni en la epoca de Miterrand ‘el actualjefe del gobierno frances’ referıa a Lionel Jospin. Se puede decir que las des-cripciones definidas refieren a un concepto individual. La interpretacion deuna descripcion definida puede considerarse como una funcion que a cadamundo posible le asigna la referencia en el, si existe, de la descripcion.

Para ver de modo preciso lo que hemos dicho de las descripciones consi-deremos la oracion

(44) es necesario que el numero de planetas del sistema solar sea 9,

y tratemos la descripcion de acuerdo con la teorıa de Russell. Ası podemosformalizar (44) como

(44’) 2∃x(Nx ∧ ∀y(Ny → x = y) ∧ x = 9)

o como

(44’) ∃x(Nx ∧ ∀y(Ny → x = y) ∧2x = 9).


La primera formalizacion refleja la lectura de re y la segunda la lectura dedicto. La primera lectura es falsa, puesto que en otras situaciones alterna-tivas distintas a la actual el numero de planetas no es 9. Lo que importaes la referencia de las descripcion en estas situaciones alternativas. La se-gunda lectura es verdadera si suponemos que nueve es necesariamente iguala nueve. La referencia de la descripcion que importa es la referencia en lasituacion actual, que es el numero nueve. El hecho de que la referencia deuna descripcion varie de un mundo posible a otro es crucial para explicar ladiferencia entre la lectura de re y la lectura de dicto de oraciones como (44).

Otro ejemplo es el siguiente:

(45) El ganador del juego lo gano necesariamente

que se puede formalizar de dos modos

(45’) 2∃x(Gx ∧ ∀y(Ny → x = y))

y

(45”) ∃x(Gx ∧ ∀y(Ny → x = y) ∧2Gx).

Si el juego se jugo, (45) es verdadera, pero aun ası (45”) es falsa: en otrasituacion el ganador podrıa haber sido otro.

Nombres propios. La distincion Fregeana entre sentido y referencia tam-bien se ha aplicado a los nombres propios y se ha debatido mucho sobre si,ademas de referencia, tienen o no significado. Frege creıa que cada nombretiene un significado (Sinn) ademas de referencia, y que el significado puedeexpresarse como una descripcion definida, pero que sin embargo no todoslos hablantes asocian el mismo significado al mismo nombre. El significadoes el modo que tienen (cada uno) de acceder a (fijar) la referencia.

Si se opta por considerar el significado de un nombre propio como unadescripcion entonces los nombres funcionan como las descripciones, en cadamundo posible tienen o no una referencia que puede variar de un mundo aotro. Los nombres propios se tratan como refiriendo a un concepto indivi-dual.

Kripke introdujo una concepcion distinta de la semantica de los nombrespropios. Aunque la referencia de un nombre propio se fije mediante unadescripcion (Hesperus = la estrella matutina), una vez fijada la referencia,no varıa. En todos los mundos en los que refiere, refiere al mismo objeto. Sedice que los nombres propios son designadores rigidos.

3. Semantica de modelos con dominio constante: cuantificacionsobre posibles

Un marco es un triplo F = 〈W,R,D〉 donde:i)W es un conjunto no vacio, el conjunto de los mundo posibles o estados,ii) R es una relacion binaria en W ,

3. SEMaNTICA DE MODELOS CON DOMINIO CONSTANTE: CUANTIFICACIoN SOBRE POSIBLES69

iii) D es un conjunto no vacio, llamado el dominio del marco; sus ele-mentos son los individuos posibles.

Dado un marco F = 〈W,R,D〉, una interpretacion con dominioconstante I en F es una funcion que asigna a cada constante un elementode D y a cada par formado por un sımbolo relacional y un elemento deW una relacion n-adica en D, si n es la ariedad del sımbolo relacional.Formalmente, una interpretacion I en F es una funcion de Con ∪ (Rel×W )en⋃

n>0 P(Dn) tal que,i) para cada constante c, I(c) ∈ D,ii) para cada sımbolo relacional n-ario R y cada w ∈W , I(〈R,w〉) ⊆ Dn,

donde Dn es D, si n = 1, y es el producto cartesiano de D por si mismon-veces si n < 1.

Un modelo con dominio constante es un par M = 〈F , I〉 donde Fes un marco e I es una interpretacion en el. El dominio deM es el dominiode su marco F y el conjunto de mundos posibles de M es el conjunto demundos posibles de F .

Dado un modelo M = 〈〈W,R,D〉, I〉, denotaremos concM a I(c)

y conRM,w a I(〈R,w〉).

El objeto cM se llama la denotacion (en el modeloM) de la constante c. Ladenotacion de cada constante es la misma en todo mundo posible, es decirno varıa de un mundo a otro, por ello se dice que las constantes se tratancomo (o son) designadores rıgidos.

Dado un modelo M, una asignacion en M es una funcion que asignaa cada variable un elemento del dominio D de M. Dado a ∈ D y unavariable x la variante en x de una asignacion s determinada por a es laasignacion sx

a definida por: cada variable y diferente de x, sxa(y) = s(y) y

sxa(x) = a. Si x1, . . . , xn son variables distintas y a1, . . . , an son elementos

de D (no necesariamente diferentes) con sx1,...,xna1,...,an denotamos la asignacion

(. . . (sx1a1

) . . .)xnan

que se obtiene a partir de s.

Verdad en un mundo de un modelo con dominio constante.SeaM = 〈〈W,R,D〉, I〉. Dada una asignacion s enM, definimos para cadatermino t su denotacion tM[s] en M bajo s mediante:

1. para cada constante c, cM[s] = cM

2. para cada variable x, xM[s] = s(x)La relacion M, w |= α[s] entre mundos posibles de M, formulas y asig-

naciones en M se define como sigue:1. SiR es un sımbolo relacional n-ario y t1, . . . , tn son terminos,M, w |=Rt1 . . . tn[s] sii 〈tM1 [s], . . . , tMn [s]〉 ∈ RM,w.

2. M, w |= ¬α[s] sii M, w 6|= α[s].3. M, w |= (α ∧ β)[s] sii M, w |= α[s] y M, w |= β[s].4. M, w |= (α ∨ β)[s] sii M, w |= α[s] o M, w |= β[s].5. M, w |= (α→ β)[s] sii M, w 6|= α[s] o M, w |= β[s].


6. M, w |= 2α[s] sii para todo w′ ∈ W tal que wRw′, M, w′ |= α[s] yM, w |= β[s].

7. M, w |= 3α[s] sii existe w′ ∈ W tal que wRw′ y M, w′ |= α[s] yM, w |= β[s].

8. M, w |= ∀xα[s] sii para cada a ∈ D, M, w |= α[sxa].

9. M, w |= ∃xα[s] sii existe a ∈ D tal que M, w |= α[sxa].

Lema 94. SiM es un modelo, α es una formula y s y s′ son dos asigna-ciones que coinciden en lo que asignan a las variavbles libres de α entoncespara cada w ∈W ,

M, w |= α[s] sii M, w |= α[s′].

Corolario 95. Si M es un modelo y α es una sentencia entonces paracada w ∈W son equivalentes

1. M, w |= α[s] para alguna asignacion s2. M, w |= α[s] para toda asignacion s

Dado un modelo M, uno de sus mundos posibles w y una sentencia α,se dice que α es verdadera en w de M si hay alguna asignacion s en Mtal queM, w |= α[s]. Se dice ademas que α es valida enM si es verdaderaen todo mundo posible w de M. Finalmente, α es valida si es valida entodo modelo M.

Lema 96. Si M es un modelo, α es una formula, c una constante y suna asignacion, entonces para cada w ∈W ,

M, w |= α(x/c)[s] sii M, w |= α[sxcM ].

Ejemplos de sentencias validas.1. Todas las sentencias de la forma de una sentencia logicamente valida

de primer orden.2. 3∀xPx→ ∀x3Px3. ∃x2Px→ 2∃xPx4. 2∀xPx→ ∀x2Px5. ∃x3Px→ 3∃xPx6. ∀x2Px→ 2∀xPx7. 3∃xPx→ ∃x3Px

Formulas Barcan y Formulas Barcan inversas. Las formulas dela forma∀x2ϕ→ 2∀xϕ

o3∃xϕ→ ∃x3ϕ

se llaman Formulas Barcan. Las de la forma2∀xϕ→ ∀x2ϕ

o∃x3ϕ→ 3∃xϕ

se llaman Formulas Barcan inversas. Tanto las unas como las otras sonvalidas con la semantica de dominios constantes.

4. SEMaNTICA DE MODELOS CON DOMINIO VARIABLE: CUANTIFICACIoN SOBRE ACTUALES Y DESIGNACIoN RIGIDA71

4. Semantica de modelos con dominio variable: cuantificacionsobre actuales y designacion rıgida

Un marco con dominio variable es un triplo F = 〈W,R,D〉 donde:i)W es un conjunto no vacio, el conjunto de los mundo posibles o estados,ii) R es una relacion binaria en W ,iii) D es una funcion que asigna a cada w ∈W un conjunto no vacio.Dado un marco F = 〈W,R,D〉, para cada w ∈ w, denotaremos D(w)

con Dw, y denotartemos con D(F) el conjunto⋃

w∈W Dw. El conjunto Dw

es el conjunto de individuos que existen en el mundo w, se llama dominiode w. El conjunto D(F) es el dominio del marco.

Dado un marco F = 〈W,R,D〉, una interpretacion con dominiovariable I en F es una funcion que asigna a cada constante un elemento deD(F) y a cada par fomado por un sımbolo relacional y un elemento de Wuna relacion n-adica en D(F), donde n es la ariedad del sımbolo relacional.Formalmente, una interpretacion I en F es una funcion de Cont∪(Rel×W )en⋃

n>0 P(D(F)n) tal que,i) para cada constante c, I(c) ∈ D(F),ii) para cada sımbolo relacional n-ario R y cada w ∈ W , I(〈R,w〉) ⊆

D(F)n,donde D(F)n es D, si n = 1, y es el producto cartesiano de D(F) por simismo n-veces si n < 1.

Un modelo con dominio variable es un par M = 〈F , I〉 donde F esun marco e I es una interpretacion en el. El dominio de M es el dominiode su marco F y el conjunto de mundos posibles de M es el conjunto demundos posibles de F . Se dice queM = 〈F , I〉 es un modelo sobre el marcoF .

Dado un modelo M = 〈〈W,R,D〉, I〉, denotaremos concM a I(c)

y conRM,w a I(〈R,w〉).

El objeto cM se llama la denotacion (en el modelo M) de la constantec. La denotacion de cada constante es la misma en todo mundo posiblew, independientemente se si pertenece o no al dominio de w, es decir lasconstantes se tratan tambien en esta sematica como designadores rıgidos.

Dado un modelo M, una asignacion en M es una funcion que asignaa cada variable un elemento del dominio D de M. Dado a ∈ D y unavariable x la variante en x de una asignacion s determinada por a es laasignacion sx

a definida por: cada variable y diferente de x, sxa(y) = s(y) y

sxa(x) = a. Si x1, . . . , xn son variables distintas y a1, . . . , an son elementos deD(F) (no necesariamente diferentes) con sx1,...,xn

a1,...,an denotamos la asignacion(. . . (sx1

a1) . . .)xn

anque se obtiene a partir de s.

Verdad en un mundo de un modelo con dominio variable. SeaM = 〈〈W,R,D〉, I〉. Dada una asignacion s en M, definimos para cadatermino t su denotacion tM[s] en M bajo s mediante:


1. para cada constante c, cM[s] = cM

2. para cada variable x, xM[s] = s(x)

La relacion M, w |= α[s] entre mundos posibles de M, formulas y asig-naciones en M se define como sigue:

1. SiR es un sımbolo relacional n-ario y t1, . . . , tn son terminos,M, w |=Rt1 . . . tn[s] sii 〈tM1 [s], . . . , tMn [s]〉 ∈ RM,w.

2. M, w |= ¬α[s] sii M, w 6|= α[s].3. M, w |= (α ∧ β)[s] sii M, w |= α[s] y M, w |= β[s].4. M, w |= (α ∨ β)[s] sii M, w |= α[s] o M, w |= β[s].5. M, w |= (α→ β)[s] sii M, w 6|= α[s] o M, w |= β[s].6. M, w |= 2α[s] sii para todo w′ ∈ W tal que wRw′, M, w′ |= α[s] yM, w |= β[s].

7. M, w |= 3α[s] sii existe w′ ∈ W tal que wRw′ y M, w′ |= α[s] yM, w |= β[s].

8. M, w |= ∀xα[s] sii para cada a ∈ Dw, M, w |= α[sxa].

9. M, w |= ∃xα[s] sii existe a ∈ Dw tal que M, w |= α[sxa].

La diferencia con el caso de la semantica de modelos con dominio constanteesta en las condiciones para los cuantificadores. Ahora la cuantificacion serealiza sobre los individuos que existen en el mundo en que se evalua laformula, antes se realizaba sobre el dominio del marco.

Lema 97. SiM es un modelo, α es una formula y s y s′ son dos asigna-ciones que coinciden en lo que asignan a las variavbles libres de α entoncespara cada w ∈W ,

M, w |= α[s] sii M, w |= α[s′].

Corolario 98. Si M es un modelo y α es una sentencia entonces paracada w ∈W son equivalentes

1. M, w |= α[s] para alguna asignacion s2. M, w |= α[s] para toda asignacion s

Dado un modelo M, uno de sus mundos posibles w y una sentencia α,se dice que α es verdadera en w de M si hay alguna asignacion s en Mtal queM, w |= α[s]. Se dice ademas que α es valida enM si es verdaderaen todo mundo posible w de M.

Lema 99. Si M es un modelo, α es una formula, c una constante y suna asignacion, entonces para cada w ∈W ,

M, w |= α(x/c)[s] sii M, w |= α[sxcM ].

Observacion 100. Las formulas siguientes, que son validas en logicade primer orden, no son validas con semantica de dominios variables.

1. ∀xPx→ Pc2. Pc→ ∃xPx

4. SEMaNTICA DE MODELOS CON DOMINIO VARIABLE: CUANTIFICACIoN SOBRE ACTUALES Y DESIGNACIoN RIGIDA73

Por ello la logica modal de primer orden con dominios variables no es unaextension conservadora de la logica de primer orden. Es una extension con-servadora de la logica libre.

Observacion 101. Las formulas siguientes no son validas con semanti-ca de dominios variables.

1. 3∀xPx→ ∀x3Px2. ∃x2Px→ 2∃xPx3. 2∀xPx→ ∀x2Px4. ∃x3Px→ 3∃xPx5. ∀x2Px→ 2∀xPx6. 3∃xPx→ ∃x3Px

Un marco F = 〈W,R,D〉 se dice que es monotono si para cada w,w′ ∈W tal que wRw′ ocurre que Dw ⊆ Dw′ . Se dice que es antimonotono sipara cada w,w′ ∈W tal que wRw′ ocurre que Dw′ ⊆ Dw. Observese que Fes monotono y antimonotono sii para cada w,w′ ∈ W tal que wRw′ ocurreque Dw = Dw′ .

Proposicion 102. Un marco F es monotono sii las formulas Barcaninversas son validas en todo modelo M sobre F .

Proposicion 103. Un marco F es antimonotono sii las formulas Barcanson validas en todo modelo M sobre F .

Proposicion 104. Un marco F es monotono y antimonotono sii lasformulas Barcan y sus inversas son validas en todo modelo M sobre F .

La demostracion de la proposicion siguiente utiliza tecnicas que no sehan estudiado en el curso.

Proposicion 105. Las formulas validas en todo modelo con dominioconstante son exactamente las formulas validas en todo modelo sobre unmarco monotono y antimonotono.

Las formulas Barcan y sus inversas no solo expresan permutaciones delorden de los operadores modales y los cuantificadores, sino que dicen algosobre las suposiciones de existencia que se estan haciendo en la semanti-ca. Las formulas Barcan dicen que al pasar de un mundo a otro accesibledesde el no aparecen nuevos individuos pero pueden desaparecer algunos.Las inversas de las formulas Barcan expresan que al pasar de un mundo aotro accessible desde el pueden aparecer nuevos individuos pero que los queexistian en el primer mundo siguen haciendolo en el segundo.

logica modal

Documents