Lógica Modal 1

Base Axiomática para o Cálculo Proposicional

(Sistema PM)

Símbolos:•Letras romanas minúsculas, comou sem índice inferior;•Os símbolos: ~, ∨, (, )

Qualquer símbolo acima, ou qualquer se-quência de símbolos é uma expressão. Cha-maremos de fórmula às expressões forma-das segundo as seguintes regras:

Regras de Formação:•Uma letra isolada é uma fórmula;•Se α é uma fórmula, então ~α é uma fórmula;•Se α e β são fórmulas, então (α ∨ β) é umafórmula.

Lógica Modal 2

Para simplificar a notação, definiremos novosoperadores, a partir dos anteriores:

[Def. ⋅] (α ⋅ β) ≅ ∼(∼α ∨ ∼β)

[Def. ⊃] (α ⊃ β) ≅ (∼α ∨ β)

[Def. ≡] (α ≡ β) ≅ ((α ⊃ β) ⋅ (β ⊃ α))

Do ponto de vista semântico, podemos defi-nir, como anteriormente:

•atribuições de valores-verdade às letras sentenciais(também chamadas de variáveis proposicionais);

•extensão destas atribuições a todas as fórmulas docálculo proposicional, através da definição de umasemântica para os operadores;

•validade, chegando ao conceito de tautologia

Lógica Modal 3

Sistema Formal:

Axiomas:A1: (p ∨ p) ⊃ pA2: q ⊃ (p ∨ q)A3: (p ∨ q) ⊃ (q ∨ p)A4: (q ⊃ r) ⊃ ((p ∨ q) ⊃ (p ∨ r))

Chamaremos de tese qualquer axioma ou qual-quer fórmula obtida através das seguintes regras:

Regras de Transformação:

TR1: Substituição UniformeO resultado de substituir uniformementequalquer letra, numa tese, por uma fórmula, éuma tese;

TR2: Modus PonensSe α e (α ⊃ β) são teses então β também é.

Uma derivação é uma sequência de teses

Lógica Modal 4

Sistemas Modais Proposicionais

Vamos inicialmente considerar as seguintesmodalidades, na linguagem natural, segundoas quais uma proposição pode ser verdadeiraou falsa: (noções modais)

• necessariamente verdadeira;• impossível;• contingente;• possível.

O desenvolvimento a seguir deverá dar umsentido lógico a estes termos.

De uma maneira intuitiva, qualquer uma des-tas noções modais pode ser expressa em fun-ção de qualquer uma das outras.

Outra noção modal importante é o conceitode acarretamento.

Lógica Modal 5

Pode-se associar às noções modais acimaoperadores (unários ou binários) modais

Uma característica fundamental destes ope-radores é o fato de não serem funcionais-ve-ritativos.

Sistemas lógicos que possuam este tipo deoperador são chamados de sistemas modais.

O s sistemas modais que construiremos conte-rão o CS, mas não serão redutíveis a ele.

A questão crucial é:Que fórmulas chamaremos de válidas nossistemas modais?

Lógica Modal 6

Para a construção dos sistemas modais nãoé conveniente partir do conceito de validade(como fizemos no CS) pois ele não é eviden-te neste contexto.

Para que o sistema tenha a interpretação dese-jada, algumas condições (que veremos a seguir)devem ser preenchidas.

Contudo, contrariamente aos sistema elemen-tares, estas condições nem sempre são consen-suais, o que leva à existência de múltiplos sis-temas.

O procedimento adotado será:• estabelecer condições para os sistemas (fór-mulas que devem ser válidas);• definir os sistemas axiomáticos;• propor definições de validade, comparando-ascom os sistemas definidos.

Lógica Modal 7

Algumas condições a que devemsatisfazer os sistemas modais:

1) Lp ≡ ~M~pMp ≡ ~L~p

(das discussões anteriores)Pode-se escolher apenas uma delas como primitiva.{

2) Quanto ao operador de acarretamento,há alguma controvérsia; no entanto é con-sensual:

O sentido inverso é polêmico, mas vamosassumir:

ou, equivalentemente:

(p q) ⊃ ~ M (p ⋅ ~q)

(p q) ≡ ~ M (p ⋅ ~q)

(p q) ≡ L (p ⊃ q)

Lógica Modal 8

acarretamento implicação estrita

analogamente à relação entre ( ⊃, ≡ ) podemosdefinir o símbolo de equivalência estrita:

ou

(α = β) ≅ L(α ≡ β)

3) O operador L não é funcional-veritativo.Portanto não pode ser tese a fórmula:

Lp ≡ p

4) Axioma da NecessidadeLp ⊃ p pois aquilo que é necessaria-

mente verdadeiro é verdadeirooutra versão: p ⊃ Mp (axioma da possibilidade)

(deriváveis um do outro)

(α = β) ≅ ((α β) ⋅ (β α))

Lógica Modal 9

5) Qualquer fórmula válida é necessariamenteverdadeira (se α é válida, Lα também é).

6) Tudo o que “segue logicamente” de umaverdade necessária é uma verdade necessária.

L(p ⊃ q) ⊃ (Lp ⊃ Lq)

(de outra maneira, o risco de falsear a conclusão seriamaior do que o risco de falsear as premissas)

Terminologia:

Uma tese pertence a um sistema se é derivável nele

Dois sistemas são dedutivamente equivalentes ou equi-valentes se contém as mesmas teses (mesmo tendo basesdiferentes)

Se as teses de um sistema A pertencem a um sistema B,mas nem toda tese de B pertence a A, então:A é mais fraco que BB é mais forte que AB contém A

Lógica Modal 10

Sistema TÉ o mais fraco sistema modal que satisfaz àsexigências anteriores.

Símbolos:letras romanas minúsculas (var. proposicionais)~, L, ∨, (, )

Regras de Formação:•Uma variável proposicional isolada é uma fórmula.

•Se α é uma fórmula, então ~α e Lα são fór-mulas.

•Se α e β são fórmulas, então (α ∨ β) é umafórmula.

Lógica Modal 11

Definições de outros conectivos:

Mα ≅ ~L~α(α β) ≅ L(α ⊃ β)(α = β) ≅ ((α β) ⋅ (β α))

(⊃, ⋅, ≡) definidos como anteriormente;

Axiomas:A1 a A4 do sistema PM e ainda:

A5: (Lp ⊃ p)A6: L(p ⊃ q) ⊃ (Lp ⊃ Lq)

Regras de Transformação:TR1: Substituição Uniforme

TR2: Modus Ponens

TR3: Regra da Necessitação:Se α é uma tese então Lα é uma tese

Lógica Modal 12

obs.: não confundir a regra TR3 com a fórmula não-válida:

p ⊃ Lp

Uma derivação em T é definida de manei-ra análoga à proposta para o sistema PM

Algumas teses do sistema modal T:

T1: p ⊃ Mp

T2: (p = q) ⊃ (Lp ≡ Lq)

T3: L(p ⋅ q) ≡ (Lp ⋅ Lq) (lei da L-distribuição)

T4: L(p ≡ q) ≡ (p = q)T7: M(p ∨ q) ≡ Mp ∨ Mq (lei da M-distribuição)

Regra abreviada:DR1: Se (α ⊃ β) é tese então (Lα ⊃ Lβ) é tese

Regra abreviada:DR2: Se (α ≡ β) é tese então (Lα ≡ Lβ) é tese

Lógica Modal 13

Regra de Substituição de Equivalentes (Eq):Se α é uma tese e β difere de α somente pela ocorrência deuma fórmula δ no lugar de alguma fórmula γ (em todas oualguma ocorrências de γ) então, se (γ ≡ δ) é uma tese, β é uma tese.

T5: Lp ≡ ~M~pT5a: L~p ≡ ~MpT5b: ~Lp ≡ M~pT5c: LLp ≡ ~MM~p

T5d: LL~p ≡ ~MMpT5e: MM~p ≡ ~LLpT5f: LM~p ≡ ~MLpT5g: ML~p ≡ ~LMp

Regra do intercâmbio LM (LMI):Em qualquer sequência de L’s e M’s adjacentes, todos osL’s podem ser substituídos por M’s, e M’s por L’s desdeque o símbolo ~ seja inserido ou apagado imediatamenteantes e imediatamente após a sequência.

Regra abreviada:DR3: Se (α ⊃ β) é uma tese, então (Mα ⊃ Mβ)é uma tese.

T9: (Lp ∨ Lq) ⊃ L(p ∨ q)T10: M(p ⋅ q) ⊃ (Mp ⋅ Mq)

Comparar comT3 e T7}

Lógica Modal 14

Sistemas S4 e S5

O sistema T contém teses praticamenteconsensuais.

A seguinte fórmula não é tese em T esua validade é controversa:

Lp ⊃ LLp(o que é necessário é necessariamente necessário?)

Se a aceitarmos, estaremos aceitando também:

Lp ≡ LLp

Uma tese deste tipo é chamada de lei de redu-ção pois estabelece a equivalência entre umasequência de operadores modais e outra se-quência menor.

Lógica Modal 15

Apenas algumas leis de redução são plausíveisde modo a preservar a interpretação intuitivaatribuída aos operadores L e M:

R1: Mp ≡ LMpR2: Lp ≡ MLpR3: Mp ≡ MMpR4: Lp ≡ LLp

Nenhuma destas é tese em T, mas todas tem umaimplicação unilateral que é tese em T:

LMp ⊃ Mp Lp ⊃ MLp

Mp ⊃ MMpLLp ⊃ Lp

Portanto para ampliarmos o sistema T bastaacrescentar:

R1a: Mp ⊃ LMpR2a: MLp ⊃ LpR3a: MMp ⊃ MpR4a: Lp ⊃ LLp

Lógica Modal 16

Contudo, tem-se ainda que:

Portanto, os candidatos a novos axiomas sãop. ex. R1a e R4a. Mas:

R1a R4a embora a recíproca nãoseja verdadeira( )

Concluímos que:a) Se admitirmos R1a como axioma, teremoscomo teses todas as leis de redução R1 a R4;b) Se admitirmos R4a como axioma, teremosalgumas das leis de redução.

Sistema S4: construído acrescentando-se R4a;Sistema S5: construído acrescentando-se R1a.

É óbvio que: T ⊂ S4 ⊂ S5

R1a R2ae

R3a R4a

0bs.: A questão pode ser resumida como: uma proposiçãocom característica modal tem esta característica necessa-riamente?

Lógica Modal 17

Sistema S4: O mesmo que T, exceto peloacréscimo do axioma:

A7: Lp ⊃ LLp

Teses:T18: MMP ⊃ MpT19: Lp ≡ LLpT20: Mp ≡ MMpT21: MLMp ⊃ MpT22: LMp ⊃ LMLMpT23: LMp ≡ LMLMpT24: MLp ≡ MLMLp

Modalidades em S4: Uma modalidade é umasequência unicamente composta de operadoresunários (~, L, M), com zero ou mais termos.(caso zero representado por -)

Forma padrão: Usando LMI, transformare-mos qualquer modalidade em outra sem ne-nhuma negação ou com apenas uma negaçãono começo.

Lógica Modal 18

Modalidade Iterada: É a modalidade que con-tém dois ou mais operadores modais.

Modalidades Equivalentes: Ae B são modali-dades equivalentes num dado sistema se e so-mente se o resultado da substituição de A por Bou vice-versa é uma fórmula equivalente á ante-rior.

Se A e B são modalidades equivalentes (numsistema) e A contém menos operadores que Bentão B é redutível a A (no sistema).

Resultado: Em S4 toda modalidade é equiva-lente a alguma das seguintes modalidades (ouàs suas negações):

-; L; M; LM; ML; LML; MLM

Prova: usando-se os teoremas de S4.

Existem portanto no máximo 14 modalidadesem S4 (falta provar que são distintas).

Lógica Modal 19

Relações de implicação (em S4):Lp

p

LMLp

MLp LMp

MLMp

MpÉ possível a obtenção de interpretações (mo-delos) para as quais as recíprocas das implica-ções acima não se verificam. Desta maneira,fica provado que as 14 modalidades de S4 sãodistintas

Em T, devido à total ausência de leis de redução,o número de modalidades distintas é infinito.

Lógica Modal 20

Sistema S5: O mesmo que T, exceto peloacréscimo do axioma:

A8: Mp ⊃ LMp

Teses:T25: MLp ⊃ LpT26: Mp ≡ LMpT27: Lp ≡ MLp

O axioma A7 de S4 pode ser provado comotese de S5

Modalidades em S5: As quatro leis de redu-ção são teses de S5:

Mp ≡ LMpLp ≡ MLp

Mp ≡ MMpLp ≡ LLp

Como consequência, em S5 existem no má-ximo seis modalidades distintas:

-; L; M (e suas negações)

Lógica Modal 21

Validade em T, S4 e S5

Jogo para o cálculo proposicional:

•Cada jogador tem uma folha com um conjun-to de letras sentenciais

•Uma fórmula só é chamada se suas “partesconstituintes” tiverem sido chamadas.

• ~α é escrita numa folha se e somente sea fórmula α não estiver nesta folha.

• (α ∨ β) é escrita numa folha se e somente seα ou β estiverem nesta folha.

Uma fórmula é dita bem sucedida numa folhase ela aparece naquela folha.

Uma fórmula é dita bem sucedida no cálculoproposicional se ela aparece em qualquer folha.

Tautologias = fórmulas bem sucedidas no cál-culo proposicional

Lógica Modal 22

Jogo para T

Uma fórmula é dita bem sucedida numa folhase ela aparece naquela folha.

Uma fórmula é dita bem sucedida em T se elaaparece em qualquer folha, qualquer que sejao arranjo.

• Idêntico ao anterior, com alguns acréscimos

•Alguns jogadores “verão” outros, segundo umarranjo pré-determinado (todo jogador vê a sipróprio, relação reflexiva)

•Lα é escrita numa folha se α estiver em todasas folhas visíveis a partir daquela folha.

•Mα é escrita numa folha se α estiver em pelomenos uma folha visível a partir daquela folha.

Por definição, uma fórmula é válida em T seela é bem sucedida em T.

Lógica Modal 23

Jogo para S4: Impõe-se que a relações en-tre as folhas sejam reflexivas e transitivas

(todo o resto é idêntico ao sistema T)

Jogo para S5: Impõe-se que a relações en-tre as folhas sejam reflexivas, transitivas esimétricas (portanto uma relação de equiva-lência).

(todo o resto é idêntico aos sistemas T e S4)

Alguns meta-teoremas:

1) Toda tese de T é T-válida e vice-versa

2) Toda tese de S4 é S4-válida e vice-versa

3) Toda tese de S5 é S5-válida e vice-versa

4) T, S4 e S5 são sistemas distintos

Lógica Modal 24

Definição formal de validade

Um modelo para T é definido como uma triplaordenada <W, R, V> onde W é um conjunto deobjetos, R é uma relação diádica reflexiva entreelementos de W e V é uma atribuição de valores-verdade satisfazendo as seguintes condições:

1) Para qualquer variável proposicional pj e paraqualquer wi ∈ W: ou V(pj,wi) = 1 ou V(pj,wi) = 0

2) Para toda fórmula α e para qualquer wi ∈ W:V(~α, wi) = 1 se V(α, wi) = 0V(~α, wi) = 0 se V(α, wi) = 1

3) Para quaisquer fórmulas α e β e para qualquerwi ∈ W:

V((α ∨ β), wi) ={1 se V(α, wi)=1 ou V(β, wi)=10 em caso contrário

4) Para toda fórmula α e para qualquer wi ∈ W:V(Lα, wi) = 1 se ∀wj ∈ W tal que wiRwj: V(α,wj)=1V(Lα, wi) = 0 em caso contrário

Lógica Modal 25

Uma fórmula α é T-válida se e somente separa qualquer modelo para T: <W, R, V>e para todo wi ∈ W, V(α, wi) = 1

Modelo para S4: Idêntica à definição de modelo para T, com a restrição adicionalde que a relação R seja também transitiva

Modelo para S5: Idêntica à definição de modelo para T, com as restrições adicionaisde que a relação R seja também transitiva ereflexiva

S4-validade e S5-validade são definidas demaneira idêntica a T-validade, substituindo-se“modelo para T” respectivamente por “modelopara S4” e “modelo para S5”

Lógica Modal 26

≅ ⊃ ⋅ ≅ ⊃ ⋅ ≡ ∨