Uma ´algebra de Boole com operador ´e uma estrutura A = hA, ∧, ∨, −, 0, 1, f i,
onde hA, ∧, ∨, −, 0, 1i ´e uma ´algebra de Boole e f : A −→ A ´e uma fun¸c˜ao qualquer (o operador de A). Como em ´algebras de Boole sem operador, iremos nos referir `a ´algebra A pelo seu dom´ınio A.
Um homomorfismo entre duas ´algebras com operadores A e B ´e um ho- momorfismo h entre as ´algebras de Boole A e B tal que, para todo a ∈ A, h(fA(a)) = fB(h(a)), onde fA e fB s˜ao os operadores de A e B, respectiva-
mente.
Se S ´e um sistema de L´ogica Modal N˜ao-normal, Alg(S) ´e uma ´algebra com o operador ✷ dado por ✷[φ] = [✷φ]. Observe que o operador ✷ est´a bem definido, pois, pela regra da Congruˆencia, se [φ] = [φ′] ent˜
ao [✷φ] = [✷φ′].
Lembramos que chamamos de Snn o sistema minimal para L´ogica Modal N˜ao-normal, apresentado no Cap´ıtulo 3. Iremos definir satisfatibilidade em ´algebras de Boole.
Defini¸c˜ao 4.17 Seja φ uma f´ormula da L´ogica Modal e A uma ´algebra de Boole com operador. Dizemos que A satisfaz φ, e denotamos A |= φ, se para todo homomorfismo de ´algebras com operador v : Alg(Snn) −→ A, temos v([φ]) = 1.
Intuitivamente, um homomorfismo de Alg(Snn) em A ´e uma valora¸c˜ao definida em A. Como v(1) = 1, para todo homomorfismo v, e o elemento 1 de Alg(Snn) ´e o conjunto dos teoremas de Snn, temos que toda ´algebra com operador satisfaz os teoremas de Snn.
Note que, pela caracteriza¸c˜ao de normalidade dada pelos Lemas 3.7 e 3.8, podemos mostrar que uma ´algebra com operador A satisfaz o sistema K de L´ogica Modal Normal se e somente se o operador f satisfaz:
f (1) = 1; f (a ∧ b) = f (a) ∧ f (b).
Estruturas Gerais como ´Algebras de Boole
Seja Λ = hW, F, P i uma estrutura geral. Definimos a ´algebra com operador AΛ
como a ´algebra de conjuntos P com o operador f definido por f (X) = {w ∈ W : X ∈ F (w)},
para todo X ∈ P .
Mostremos que a rela¸c˜ao de satisfatibilidade em estruturas gerais coincide com a satisfatibilidade da ´algebra correspondente.
Lema 4.18 Seja Λ = hW, F, P i uma estrutura geral. Para toda f´ormula φ,
Λ |= φ se e somente se AΛ|= φ.
Demonstra¸c˜ao: Se Λ 6|= φ, isto ´e, existe uma valora¸c˜ao V tal que V (φ) 6= W , tome v : Alg(Snn) −→ P o homomorfismo dado por v([ψ]) = V (ψ). Observe que v est´a bem definido, pois se [ψ] = [ψ′] temos ⊢
Snn ψ ↔ ψ′ e, portanto,
V (ψ) = V (ψ′), e que ´e de fato um homomorfismo. Como v([φ]) = V (φ) 6= 1,
AΛ6|= φ.
Reciprocamente, dado um homomorfismo v : Alg(Snn) −→ P tal que v([φ]) 6= 1, tome V uma valora¸c˜ao dada por V (ψ) = v([ψ]), e teremos V (φ) 6= W .
O pr´oximo teorema diz que toda ´algebra com operador est´a associada a alguma estrutura geral.
Teorema 4.19 Para toda ´algebra com operador A, existe uma estrutura geral
Λ tal que A ∼= AΛ.
Demonstra¸c˜ao: Seja f : A −→ A o operador de A. Defina a estrutura Λ = hW, F, P i onde W = S(A) ´e o espa¸co de Stone de A, P = A∗= {a∗: a ∈ A}
e F : S(A) −→ 2P ´e dada por
F (u) = {a∗: f (a) ∈ u},
para todo u ∈ S(A). Temos que AΛ ´e a ´algebra A∗ do Teorema de Stone, com
o operador f∗: A∗−→ A∗ dado por:
f∗(a∗) = {u ∈ S(A) : a∗∈ F (u)} = {u ∈ S(A) : f (a) ∈ u} = (f (a))∗
. Portanto, o isomorfismo de ´algebras h : A −→ A∗ dado por h(a) = a∗ tamb´em
´e um isomorfismo de ´algebras com operador.
Completude Alg´ebrica
Apresentaremos um resultado geral de completude, an´alogo `a Proposi¸c˜ao 4.2, mas para ´algebras com operador. Usando a dualidade entre ´algebras com oper- ador e estruturas gerais, apresentada nesta se¸c˜ao, mostraremos a rela¸c˜ao desses
dois resultados, tra¸cando um paralelo entre ´algebras de Lindenbaum-Tarski com operadores e estruturas gerais para L´ogica Modal N˜ao-normal, via representa¸c˜ao de Stone.
Teorema 4.20 Seja S um sistema de L´ogica Modal N˜ao-normal, e seja Alg(S) a ´algebra de Lindenbaum-Tarski de S com o operador ✷ dado por ✷[φ] = [✷φ]. Ent˜ao, para toda f´ormula φ, Alg(S) |= φ se e somente se ⊢S φ.
Demonstra¸c˜ao: A demonstra¸c˜ao ´e an´aloga `a da Proposi¸c˜ao 4.2. Nas duas dire¸c˜oes, chamaremos de h o homomorfismo h : Alg(Snn) −→ Alg(S) dado por h([φ]) = [φ]S, onde [φ]S ´e a classe de equivalˆencia de φ na rela¸c˜ao ≡S. Como S
cont´em Snn, h est´a bem definida, pois se [φ] = [φ′], isto ´e, ⊢
Snnφ ↔ φ′, ent˜ao
[φ]S = [φ′]S, isto ´e, ⊢S φ ↔ φ′. Est´a claro que h ´e sobrejetor. Compare h com a
valora¸c˜ao do modelo geral canˆonico, definido em 4.1. Iniciemos a demonstra¸c˜ao. (⇒) Se 6⊢S φ, ent˜ao [φ]S 6= 1. Logo h([φ]) = [φ]S 6= 1, de onde conclu´ımos
que Alg(S) 6⊢ φ.
(⇐) Seja φ um teorema de S. e seja v : Alg(Snn) −→ Alg(S) um homo- morfismo. Sejam p1, ..., pn as f´ormulas atˆomicas que ocorrem em [φ]. Como
h ´e sobrejetor, para cada i = 1, ..., n seja ψi tal que v([pi]) = h([ψi]). Seja
ψ = φ[p1/ψ1, ..., pn/ψn] a f´ormula obtida de φ pela substitui¸c˜ao de pi por ψi.
Uma simples indu¸c˜ao sobre a constru¸c˜ao de ψ mostra que v([φ]) = h([ψ]) = [ψ]S
Pela regra da Substitui¸c˜ao Uniforme, como φ ´e teorema de S, ψ ´e teorema de
S. Portanto, [ψ]S= 1.
H´a uma equivalˆencia entre ultrafiltros em ´algebras de Lindenbaum-Tarski e conjuntos maximalmente consistentes. De fato, se u ´e um ultrafiltro em Alg(S), ent˜aoSu = {φ : [φ] ∈ u} ´e um conjunto maximalmente S-consistente. Reciprocamente, se Γ ´e um conjunto maximalmente S-consistente, o conjunto {[φ] : φ ∈ Γ} ´e um ultrafiltro.
Seja hW, F, P i a estrutura geral associada a Alg(S), como no Teorema 4.19. Isto ´e, W ´e o conjunto dos ultrafiltros em Alg(S), P = {[φ]∗ : [φ] ∈ Alg(S)},
onde [φ]∗ = {u ∈ W : [φ] ∈ u} e
F (u) = {[φ]∗
: ✷[φ] ∈ u},
para todo u ∈ W . Observe que essa ´e exatamente a defini¸c˜ao de estrutura geral canˆonica de S (Defini¸c˜ao 4.1), onde a fun¸c˜ao ( . )∗ : [φ] 7→ [φ]∗ faz o papel da
valora¸c˜ao do modelo canˆonico, trocando f´ormulas φ por classes de equivalˆencia [φ] e conjuntos maximalmente consistente por ultrafiltros.
Cap´ıtulo 5
Modaliza¸c˜ao N˜ao-normal
A exemplo do que foi feito na Se¸c˜ao 2.3, iremos aplicar uma L´ogica Modal N˜ao-normal externamente a um sistema l´ogico L. As defini¸c˜oes e resultados apresentados neste cap´ıtulo, incluindo o Mapeamento de Preserva¸c˜ao de Con- sistˆencia, s˜ao novos, e encontram-se publicados em [FF02].
Retomemos as defini¸c˜oes de sistema l´ogico do Cap´ıtulo 2. Como na tempo- raliza¸c˜ao, supomos que L ´e uma extens˜ao da l´ogica proposicional cl´assica e que o operador ✷, da L´ogica M , n˜ao est´a na linguagem de L.
Definimos M (L) = hLM(L), ⊢M(L), KM(L), |=M(L)i por:
Linguagem A linguagem1 L
M(L)´e o menor conjunto tal que:
• Se A ∈ M LL ent˜ao A ∈ LM(L);
• Se A, B ∈ LM(L)ent˜ao ¬A ∈ LM(L)e A ∧ B ∈ LM(L);
• Se A ∈ LM(L) ent˜ao ✷A ∈ LM(L).
Axiomatiza¸c˜ao O sistema de axiomas de M (L) ´e formado por: • Os axiomas de M ;
• As regras de inferˆencia de M ;
• A regra da Preserva¸c˜ao: se ⊢LA ent˜ao ⊢M(L)A.
Semˆantica Um modelo de M (L) ´e uma tripla M = hW, F, gi, onde hW, F i ´e uma estrutura de M e g ´e uma fun¸c˜ao g : W −→ KL. A rela¸c˜ao de satisfazibil-
idade |=M(L)´e definida, para w ∈ W , por:
• Se A ∈ M LL, M, w |= A sse g(w) |= A;
1
• M, w |= A ∧ B sse M, w |= A e M, w |= B; • M, w |= ¬A sse M, w 6|= A.
• M, w |= ✷A sse {w′∈ W : M, w′ |= A} ∈ F (w).
5.1
Corre¸c˜ao
A modaliza¸c˜ao n˜ao-normal transfere corre¸c˜ao.
Teorema 5.1 Se L ´e uma l´ogica correta, e M ´e uma L´ogica Modal N˜ao-normal correta, ent˜ao a l´ogica M (L) ´e correta.
Demonstra¸c˜ao: Pela corre¸c˜ao de L, as f´ormulas obtidas pela regra da Preser- va¸c˜ao s˜ao v´alidas nos modelos de L e, portanto, nos modelos de M (L). Pela corre¸c˜ao de M , os axiomas de M s˜ao v´alidos nas estruturas de M e suas regras de inferˆencia preservam validade nas estruturas de M . Como os modelos de M (L) s˜ao baseados em estruturas de M , segue que KM(L)satisfaz os axiomas
e preserva as regras de inferˆencias de M , de onde segue a corre¸c˜ao de M (L).