Upload
others
View
1
Download
0
Embed Size (px)
Citation preview
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Sumario da semana
1 Cenas da 2a semana
2 Um sistema dedutivo para Logica Proposicional
3 Consistencia
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Vimos na 2a semana – pg. I
p → q: Se o time joga bem︸ ︷︷ ︸p
, entao o time ganha o campeonato︸ ︷︷ ︸q
.
¬p → r : Se o time nao joga bem︸ ︷︷ ︸¬p
, entao o tecnico e o culpado︸ ︷︷ ︸r
.
q → s: Se o time ganha o campeonato︸ ︷︷ ︸q
entao
os torcedores estao felizes︸ ︷︷ ︸s
.
¬s: Os torcedores nao estao felizes.
O tecnico e culpado?
Sao 16 interpretacoes possıveis.
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Vimos na 2a semana – pg. II
p q r s p → q ¬p → r q → s ¬s0 0 0 0 1 0 1 10 0 0 1 1 0 1 00 0 1 0 1 1 1 10 0 1 1 1 1 1 00 1 0 0 1 0 0 10 1 0 1 1 0 1 00 1 1 0 1 1 0 10 1 1 1 1 1 1 01 0 0 0 0 1 1 11 0 0 1 0 1 1 01 0 1 0 0 1 1 11 0 1 0 0 1 1 01 1 0 0 1 1 0 11 1 0 0 1 1 1 01 1 1 0 1 1 0 11 1 1 0 1 1 1 0
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Vimos na 2a semana – pg. III
So ha uma interpretacao que satisfaz p → q, ¬p → r ,q → s , ¬s
p q r s p → q ¬p → r q → s ¬s...
......
......
......
...0 0 1 0 1 1 1 1...
......
......
......
...
donde concluımos que e verdade r (“o tecnico e culpado”).
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Vimos na 2a semana – pg. IV
Se sao verdadeiras as premissas
Se o time joga bem entao o time ganha o campeonato.Se o time nao joga bem entao o tecnico e o culpado.Se o time ganha o campeonato entao os torcedores estao felizes.Os torcedores nao estao felizes.
entao uma conclusao logica e
o tecnico e culpado.
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Alternativamente....
Podemos obter a conclusao sem usar tabela-verdade usandoconsequencias semanticas notaveis
1. p → q, q → s sao premissas2. p → s por silogismo hipotetico a partir de 13. ¬p ∨ s pela equivalencia da implicacao em 24. ¬s premissa5. ¬p por silogismo aditivo de 3 e 46. ¬p → r premissa7. r por modus ponens com 5 e 6
Assim, {p → q,¬p → r , q → s,¬s} � r .
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Sistema dedutivo para Logica Proposicional
Um sistema dedutivo (ou formal) e um componente
sintatico
de uma logica.
Sao conhecidos varios: Sistema axiomatico a Hilbert, DeducaoNatural, Tableaux, Calculo de sequentes de Gentzen, por exemplo.
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
A linguagem proposicional revisitada I
Alfabeto:
Sımbolos proposicionais atomicos p1 p2 p3 · · ·Conectivos logicos ¬ →Sımbolos de pontuacao ( )
Uma fbf e qualquer expressao que pode ser formada aplicando-se as regras:
(F1) os sımbolos atomicos sao fbf, chamadas formulas atomicas;
(F2) se α e fbf, entao (¬α) e fbf;
(F3) se α e β sao fbfs, entao (α→ β) e fbf;
(F4) nao ha outras fbfs alem das obtidas pelo uso das regras (F1), (F2) e (F3) umnumero finito de vezes.
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
A linguagem proposicional revisitada II
As mesmas notacoes e simplificacoes
Formulas α, β, γ, . . . .
Conjuntos de formulas Σ, Γ,Θ, . . . .
Sımbolos proposicionais atomicos p, q, r , s
Regras para omissao de parenteses
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
A linguagem proposicional revisitada III
Definicoes
sımbolo le-se uso∧ conjuncao (α ∧ β) abrevia (¬(α→ (¬β)))∨ disjuncao (α ∨ β) abrevia ((¬α)→ β)↔ biimplica (α↔ β) abrevia ((α→ β) ∧ (β → α))⊥ falsum abrevia (α ∧ (¬α))> verum abrevia (¬⊥)
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Sistema de Kleene I
Axiomas
(A1) α→ (β → α)
(A2) (α→ (β → ξ))→ ((α→ β)→ (α→ ξ))
(A3) (α→ β)→ ((α→ ¬β)→ ¬α)
(A4) α→ (β → (α ∧ β))
(A5) α ∧ β → α
(A6) α ∧ β → β
(A7) α→ α ∨ β(A8) β → α ∨ β(A9) (α→ γ)→ ((β → γ)→ (α ∨ β → γ))
(A10) ¬¬α→ α
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Sistema de Kleene II
Regras de inferencias
(MP)α, α→ β
β
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Exemplos de deducao I
Teorema (1)
` α→ α
Prova.
1. α→ ((α→ α)→ α)) (A1)2. (α→ ((α→ α)→ α))→ ((α→ (α→ α))→ (α→ α)) (A2)3. α→ (α→ α)) (A1)4. (α→ (α→ α))→ (α→ α) (MP 2,1)5 α→ α (MP 3,4)
�
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Exemplos de deducao II
Teorema (Lei de Duns Scotus)
¬α, α ` β
Prova.1. α (premissa)2. ¬α (premissa)3. α→ (¬β → α) (A1)4. ¬α→ (¬β → ¬α) (A1)5. ¬β → α (MP 1,3)6. ¬β → ¬α (MP 2,4)7. (¬β → α)→
((¬β → ¬α)→ ¬¬β
)(A3)
8. (¬β → ¬α)→ ¬¬β (MP 5,7)9. ¬¬β (MP 6,8)10. ¬¬β → β (A10)11. β (MP 9,10)
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Exemplos de deducao III
�
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Exemplos de deducao IV
Teorema (2)
α→ β, β → γ ` α→ γ
Prova.1. α→ β (premissa)2. β → γ (premissa)3. (β → γ)→ (α→ (β → γ)) (A1)4. (α→ (β → γ) (MP 2,3)5. (α→ (β → γ))→ ((α→ β)→ (α→ γ)) (A2)6. (α→ β)→ (α→ γ) (MP 4,5)7. α→ γ (MP 1,6)
�
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Exemplos de deducao V
Teorema (3)
θ → (φ→ ξ) ` φ→ (θ → ξ)
Prova.1. θ → (φ→ ξ) (hipotese)2.
(θ → (φ→ ξ)
)→((θ → φ)→ (θ → ξ)
)(A2)
3. φ→ (θ → φ) (A1)4. (θ → φ)→ (θ → ξ) (MP 1,2)5.
((θ → φ)→ (θ → ξ)
)→(φ→
((θ → φ)→ (θ → ξ)
))(A1)
6. φ→((θ → φ)→ (θ → ξ)
)(MP 3,5)
7.(φ→
((θ → φ)→ (θ → ξ)
))→((
φ→ (θ → φ))→(φ→ (θ → ξ)
))(A2)
8.(φ→ (θ → φ)
)→(φ→ (θ → ξ)
)( MP 6,7)
9. φ→ (θ → ξ) (MP 4,5)�
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Exemplos de deducao VI
Teorema (3)
θ → (φ→ ξ) ` φ→ (θ → ξ)
Prova.1. θ → (φ→ ξ) (hipotese)2.
(θ → (φ→ ξ)
)→((θ → φ)→ (θ → ξ)
)(A2)
3. φ→ (θ → φ) (A1)4. (θ → φ)→ (θ → ξ) (MP 1,2)5.
((θ → φ)→ (θ → ξ)
)→(φ→
((θ → φ)→ (θ → ξ)
))(A1)
6. φ→((θ → φ)→ (θ → ξ)
)(MP 3,5)
7.(φ→
((θ → φ)→ (θ → ξ)
))→((
φ→ (θ → φ))→(φ→ (θ → ξ)
))(A2)
8.(φ→ (θ → φ)
)→(φ→ (θ → ξ)
)( MP 6,7)
9. φ→ (θ → ξ) (MP 4,5)�
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Exemplos de deducao VII
As linhas 1–7 da prova do teorema (2) sao “semelhantes” as linhas3–9 na prova do teorema (3).
Na linha 3, teo. (3), temos φ→ (θ → φ) e na 4 temos(θ → φ)→ (θ → ξ); o que precisamos e concluir queφ→ (θ → ξ), que e essencialmente o que o teorema (2) faz.
Para evitar esse trabalho extra permitimos que se justifique passosde uma prova com teoremas ja provados. Para dar um exemplo, aprova acima e re-escrita abaixo.
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Exemplos de deducao VIII
Para evitar esse trabalho extra permitimos que se justifique passosde uma prova com teoremas ja provados. Para dar um exemplo, aprova acima e re-escrita abaixo.
1. θ → (φ→ ξ) (hipotese)2.
(θ → (φ→ ξ)
)→((θ → φ)→ (θ → ξ)
)(A2)
3. φ→ (θ → φ) (A1)4. (θ → φ)→ (θ → ξ) (MP 1,2)5. φ→ (θ → ξ) (Teo. (2) 3,4)
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Exemplos de deducao IX
Teorema (4)
¬α→ ¬¬α ` α
Prova.1. ¬α→ ¬¬α (premissa)2. ¬α→ ((¬α→ ¬α)→ ¬α) (A1)3. (¬α→ ((¬α→ ¬α)→ ¬α))→ ((¬α→
→ (¬α→ ¬α))→ (¬α→ ¬α)) (A2)4. ¬α→ (¬α→ ¬α) (A1)5. (¬α→ (¬α→ ¬α))→ (¬α→ ¬α) (MP 2,3)6. ¬α→ ¬α (MP 4,5)7. (¬α→ ¬α)→ ((¬α→ ¬¬α)→ ¬¬α) (A3)8. (¬α→ ¬¬α)→ ¬¬α (MP 6,7)9. ¬¬α→ α (A10)
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Exemplos de deducao X
Continuacao10. ((¬¬α)→ α)→ ((¬α→ ¬¬α)→
((¬¬α)→ α)) (A1)11. ((¬α→ ¬¬α)→ ((¬¬α)→ α) (MP 9,10)12. ((¬α→ ¬¬α)→ ((¬¬α)→ α))→
(((¬α→ ¬¬α)→ (¬¬α))→((¬α→ ¬¬α)→ α)) (A2)
13. ((¬α→ ¬¬α)→ (¬¬α))→((¬α→ ¬¬α)→ α) (MP 11,12)
14. (¬α→ ¬¬α)→ α (MP 8,13)15. α (MP 1,14)
�
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Exemplos de deducao XI
Prova do teorema (4) usando o teorema (2)1. ¬α→ ¬¬α (premissa)2. ¬α→ ((¬α→ ¬α)→ ¬α) (A1)3. (¬α→ ((¬α→ ¬α)→ ¬α))→
((¬α→ (¬α→ ¬α))→ (¬α→ ¬α)) (A2)4. ¬α→ (¬α→ ¬α) (A1)5. (¬α→ (¬α→ ¬α))→ (¬α→ ¬α) (MP 2,3)6. ¬α→ ¬α (MP 4,5)7. (¬α→ ¬α)→ ((¬α→ ¬¬α)→ ¬¬α) (A3)8. (¬α→ ¬¬α)→ ¬¬α (MP 6,7)9. ¬¬α→ α (A10)10. (¬α→ ¬¬α)→ α (Teo. (2) 8,9)11. α (MP 1,14)
�
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Exemplos de deducao XII
Teorema (5)
` α→ ¬¬α
Prova.1. ¬¬¬α→ ¬α (A10)2. (¬¬¬α→ α)→
((¬¬¬α→ ¬α)→ ¬¬¬¬α
)(A3)
3. (¬¬¬α→ ¬α)→((¬¬¬α→ α)→ ¬¬¬¬α
)(Teo.(3) em 2)
4. (¬¬¬α→ α)→ ¬¬¬¬α (MP 1,3)5. ¬¬¬¬α→ ¬¬α (A10)6. (¬¬¬α→ α)→ ¬¬α (Teo.(2) em 4,5)7. α→ (¬¬¬α→ α) (A1)8. α→ ¬¬α (Teo.(2) em 7,6)
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Regras derivadas I
(SH)α→ β, β → γ
α→ γ
(TH)θ → (φ→ ξ)
φ→ (θ → ξ)
(CP1)α→ β
¬β → ¬α
(CP2)¬β → ¬αα→ β
(DN1)α
¬¬α
(DN2)¬¬αα
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Regras derivadas II
Prova de α→ β ` ¬β → ¬α:1. α→ β (hipotese)2. β → ¬¬β (Teo.(5))3. α→ ¬¬β (SH 1,2)4. ¬¬α→ α (A10)5. ¬¬α→ ¬¬β (SH 3,4)6. (¬¬α→ ¬¬β)→ ((¬¬α→ ¬¬¬β)→ ¬¬¬α) (A3)7. (¬¬α→ ¬¬¬β)→ ¬¬¬α (MP 5,6)8. ¬¬¬β → (¬¬α→ ¬¬¬β) (A1)9. ¬¬¬β → ¬¬¬α (SH 8,7)10. ¬β → ¬¬¬β (Teo.(5))11. ¬β → ¬¬¬α (SH 10,9)12. ¬¬¬α→ ¬α (A10)13. ¬β → ¬α (SH 11,12)
�
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
De volta ao exemplo inicial
p → q, q → s,¬p → r ,¬s ` r
1. p → q (hipotese)2. q → s (hipotese)3. ¬p → r (hipotese)4. ¬s (hipotese)5. p → s (SH 1,2)6. ¬s → ¬p (CP1 4)7. ¬p (MP 4,6)8. r (MP 3,7)
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Propriedades de ` I
Autodeducao Γ ` α para todo α ∈ Γ.
Monotonicidade Se Γ ` α entao Γ ∪ Σ ` α.
Regra do corte Se Γ ` α para todos α ∈ Σ e Σ ` β entao Γ ` β.
Compacidade Γ ` α se, e so se, existe ∆ ⊆ Γ finito tal que ∆ ` α.
Destacamento se Γ ` α e Γ ` α→ β entao Γ ` β.
Teorema da Deducaoα ` β se, e somente se, ` α→ β ou, mais geral,
Γ, α ` β se, e somente se, Γ ` α→ β.
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Propriedades de ` II
Exercıcio: Se Γ ` α e Γ ` α→ β entao Γ ` β.
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Prova do teorema da deducao: Γ, α ` β sse Γ ` α→ β
Prova de: Se Γ, α ` β entao Γ ` α→ β.
Se Γ, α ` β,1. ϕ1
...j. ϕj
...k. ϕk
...i. ϕi
...n. ϕn = β
Por inducao em i que Γ ` α→ ϕi .
Base: Γ ` α→ ϕ1
Hipotese: Γ ` α→ ϕ2...Γ ` α→ ϕi−1
Passo: Γ ` α→ ϕi
Em 3 casos:
1 ϕi e axioma ou premissa
2 ϕi e obtida por MP j,kcom j,k<i
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Prova do teorema da deducao: Γ, α ` β sse Γ ` α→ β
Prova de: Se Γ, α ` β entao Γ ` α→ β.Se Γ, α ` β,
1. ϕ1
...j. ϕj
...k. ϕk
...i. ϕi
...n. ϕn = β
Por inducao em i que Γ ` α→ ϕi .
Base: Γ ` α→ ϕ1
Hipotese: Γ ` α→ ϕ2...Γ ` α→ ϕi−1
Passo: Γ ` α→ ϕi
Em 3 casos:
1 ϕi e axioma ou premissa
2 ϕi e obtida por MP j,kcom j,k<i
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Prova do teorema da deducao: Γ, α ` β sse Γ ` α→ β
Prova de: Se Γ, α ` β entao Γ ` α→ β.Se Γ, α ` β,
1. ϕ1
...j. ϕj
...k. ϕk
...i. ϕi
...n. ϕn = β
Por inducao em i que Γ ` α→ ϕi .
Base: Γ ` α→ ϕ1
Hipotese: Γ ` α→ ϕ2...Γ ` α→ ϕi−1
Passo: Γ ` α→ ϕi
Em 3 casos:
1 ϕi e axioma ou premissa
2 ϕi e obtida por MP j,kcom j,k<i
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Prova do teorema da deducao: Γ, α ` β sse Γ ` α→ β
Prova de: Se Γ, α ` β entao Γ ` α→ β.Se Γ, α ` β,
1. ϕ1
...j. ϕj
...k. ϕk
...i. ϕi
...n. ϕn = β
Por inducao em i que Γ ` α→ ϕi .
Base: Γ ` α→ ϕ1
Hipotese: Γ ` α→ ϕ2...Γ ` α→ ϕi−1
Passo: Γ ` α→ ϕi
Em 3 casos:
1 ϕi e axioma ou premissa
2 ϕi e obtida por MP j,kcom j,k<i
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Prova do teorema da deducao: Γ, α ` β sse Γ ` α→ β
Prova de: Se Γ, α ` β entao Γ ` α→ β.Se Γ, α ` β,
1. ϕ1
...j. ϕj
...k. ϕk
...i. ϕi
...n. ϕn = β
Por inducao em i que Γ ` α→ ϕi .
Base: Γ ` α→ ϕ1
Hipotese: Γ ` α→ ϕ2...Γ ` α→ ϕi−1
Passo: Γ ` α→ ϕi
Em 3 casos:
1 ϕi e axioma ou premissa
2 ϕi e obtida por MP j,kcom j,k<i
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Prova do teorema da deducao: Γ, α ` β sse Γ ` α→ β
Prova de: Se Γ, α ` β entao Γ ` α→ β.Se Γ, α ` β,
1. ϕ1
...j. ϕj
...k. ϕk
...i. ϕi
...n. ϕn = β
Por inducao em i que Γ ` α→ ϕi .
Base: Γ ` α→ ϕ1
Hipotese: Γ ` α→ ϕ2...Γ ` α→ ϕi−1
Passo: Γ ` α→ ϕi
Em 3 casos:
1 ϕi e axioma ou premissa
2 ϕi e obtida por MP j,kcom j,k<i
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Prova do teorema da deducao: Γ, α ` β sse Γ ` α→ β
Prova de: Se Γ, α ` β entao Γ ` α→ β.Se Γ, α ` β,
1. ϕ1
...j. ϕj
...k. ϕk
...i. ϕi
...n. ϕn = β
Por inducao em i que Γ ` α→ ϕi .
Base: Γ ` α→ ϕ1
Hipotese: Γ ` α→ ϕ2...Γ ` α→ ϕi−1
Passo: Γ ` α→ ϕi
Em 3 casos:
1 ϕi e axioma ou premissa
2 ϕi e obtida por MP j,kcom j,k<i
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Prova do teorema da deducao: Γ, α ` β sse Γ ` α→ β
Prova de: Se Γ ` α→ β entao Γ, α ` β.
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Consistencia
Um conjunto de formulas e consistente se nao e possıvel deduziruma contradicao (α ∧ ¬α), o que equivale a dizer que nao epossıvel deduzir uma formula (α) e deduzir sua negacao (¬α).
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Consistencia
Lema 1
Se um conjunto de formulas Γ e inconsistente, entaoΓ ` α para toda formula α.
Dem.:
Γ ` β e Γ ` ¬β para algum β{β,¬β} ` α para qualquer αPela regra do corte Γ ` α. �
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Consistencia
Lema 1
Se um conjunto de formulas Γ e inconsistente, entaoΓ ` α para toda formula α.
Dem.:Γ ` β e Γ ` ¬β para algum β
{β,¬β} ` α para qualquer αPela regra do corte Γ ` α. �
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Consistencia
Lema 1
Se um conjunto de formulas Γ e inconsistente, entaoΓ ` α para toda formula α.
Dem.:Γ ` β e Γ ` ¬β para algum β{β,¬β} ` α para qualquer α
Pela regra do corte Γ ` α. �
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Consistencia
Lema 1
Se um conjunto de formulas Γ e inconsistente, entaoΓ ` α para toda formula α.
Dem.:Γ ` β e Γ ` ¬β para algum β{β,¬β} ` α para qualquer αPela regra do corte Γ ` α. �
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Consistencia
Lema 2
Se Γ ∪ {¬α} e inconsistente entao Γ ` α.
Dem.:Γ,¬α inconsistente.Γ,¬α ` β e Γ,¬α ` ¬β.Γ ` ¬α→ β e Γ ` ¬α→ ¬β.¬α→ β, ¬α→ ¬β ` α ((A3)+teo. deducao+(A10)).Portanto Γ ` α pela regra do corte. �
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Consistencia
Lema 2
Se Γ ∪ {¬α} e inconsistente entao Γ ` α.
Dem.:Γ,¬α inconsistente.
Γ,¬α ` β e Γ,¬α ` ¬β.Γ ` ¬α→ β e Γ ` ¬α→ ¬β.¬α→ β, ¬α→ ¬β ` α ((A3)+teo. deducao+(A10)).Portanto Γ ` α pela regra do corte. �
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Consistencia
Lema 2
Se Γ ∪ {¬α} e inconsistente entao Γ ` α.
Dem.:Γ,¬α inconsistente.Γ,¬α ` β e Γ,¬α ` ¬β.
Γ ` ¬α→ β e Γ ` ¬α→ ¬β.¬α→ β, ¬α→ ¬β ` α ((A3)+teo. deducao+(A10)).Portanto Γ ` α pela regra do corte. �
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Consistencia
Lema 2
Se Γ ∪ {¬α} e inconsistente entao Γ ` α.
Dem.:Γ,¬α inconsistente.Γ,¬α ` β e Γ,¬α ` ¬β.Γ ` ¬α→ β e Γ ` ¬α→ ¬β.
¬α→ β, ¬α→ ¬β ` α ((A3)+teo. deducao+(A10)).Portanto Γ ` α pela regra do corte. �
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Consistencia
Lema 2
Se Γ ∪ {¬α} e inconsistente entao Γ ` α.
Dem.:Γ,¬α inconsistente.Γ,¬α ` β e Γ,¬α ` ¬β.Γ ` ¬α→ β e Γ ` ¬α→ ¬β.¬α→ β, ¬α→ ¬β ` α
((A3)+teo. deducao+(A10)).Portanto Γ ` α pela regra do corte. �
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Consistencia
Lema 2
Se Γ ∪ {¬α} e inconsistente entao Γ ` α.
Dem.:Γ,¬α inconsistente.Γ,¬α ` β e Γ,¬α ` ¬β.Γ ` ¬α→ β e Γ ` ¬α→ ¬β.¬α→ β, ¬α→ ¬β ` α ((A3)+teo. deducao+(A10)).
Portanto Γ ` α pela regra do corte. �
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Consistencia
Lema 2
Se Γ ∪ {¬α} e inconsistente entao Γ ` α.
Dem.:Γ,¬α inconsistente.Γ,¬α ` β e Γ,¬α ` ¬β.Γ ` ¬α→ β e Γ ` ¬α→ ¬β.¬α→ β, ¬α→ ¬β ` α ((A3)+teo. deducao+(A10)).Portanto Γ ` α pela regra do corte. �
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Consistencia
∆ e consistente maximal se
1 e consistente.
2 ∆ ∪ {α} nao e consistente para qualquer α 6∈ ∆.
Lema 3
Se Γ e consistente entao existe ∆ ⊇ Γ consistente maximal.
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Consistencia
∆ e consistente maximal se
1 e consistente.
2 ∆ ∪ {α} nao e consistente para qualquer α 6∈ ∆.
Lema 3
Se Γ e consistente entao existe ∆ ⊇ Γ consistente maximal.
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Consistencia
lema 4
Se ∆ e consistente maximal entao
1 ∆ ` α se, e so se, α ∈ ∆;
2 ¬α ∈ ∆ se, e so se, α 6∈ ∆;
3 α→ β ∈ ∆ se, e so se, ¬α ∈ ∆ ou β ∈ ∆.
Dem.:
1 Se α ∈ ∆ entao ∆ ` α.
Se ∆ ` α mas α 6∈ ∆ entao ∆ ∪ {α} e inconsistente.∆, α ` β e ∆, α ` ¬β.∆ ` α→ β e ∆ ` α→ ¬β.De ∆ ` α temos ∆ ` β e ∆ ` ¬β, contradicao. �
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Consistencia
lema 4
Se ∆ e consistente maximal entao
1 ∆ ` α se, e so se, α ∈ ∆;
2 ¬α ∈ ∆ se, e so se, α 6∈ ∆;
3 α→ β ∈ ∆ se, e so se, ¬α ∈ ∆ ou β ∈ ∆.
Dem.:
1 Se α ∈ ∆ entao ∆ ` α.Se ∆ ` α mas α 6∈ ∆
entao ∆ ∪ {α} e inconsistente.∆, α ` β e ∆, α ` ¬β.∆ ` α→ β e ∆ ` α→ ¬β.De ∆ ` α temos ∆ ` β e ∆ ` ¬β, contradicao. �
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Consistencia
lema 4
Se ∆ e consistente maximal entao
1 ∆ ` α se, e so se, α ∈ ∆;
2 ¬α ∈ ∆ se, e so se, α 6∈ ∆;
3 α→ β ∈ ∆ se, e so se, ¬α ∈ ∆ ou β ∈ ∆.
Dem.:
1 Se α ∈ ∆ entao ∆ ` α.Se ∆ ` α mas α 6∈ ∆ entao ∆ ∪ {α} e inconsistente.
∆, α ` β e ∆, α ` ¬β.∆ ` α→ β e ∆ ` α→ ¬β.De ∆ ` α temos ∆ ` β e ∆ ` ¬β, contradicao. �
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Consistencia
lema 4
Se ∆ e consistente maximal entao
1 ∆ ` α se, e so se, α ∈ ∆;
2 ¬α ∈ ∆ se, e so se, α 6∈ ∆;
3 α→ β ∈ ∆ se, e so se, ¬α ∈ ∆ ou β ∈ ∆.
Dem.:
1 Se α ∈ ∆ entao ∆ ` α.Se ∆ ` α mas α 6∈ ∆ entao ∆ ∪ {α} e inconsistente.∆, α ` β e ∆, α ` ¬β.
∆ ` α→ β e ∆ ` α→ ¬β.De ∆ ` α temos ∆ ` β e ∆ ` ¬β, contradicao. �
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Consistencia
lema 4
Se ∆ e consistente maximal entao
1 ∆ ` α se, e so se, α ∈ ∆;
2 ¬α ∈ ∆ se, e so se, α 6∈ ∆;
3 α→ β ∈ ∆ se, e so se, ¬α ∈ ∆ ou β ∈ ∆.
Dem.:
1 Se α ∈ ∆ entao ∆ ` α.Se ∆ ` α mas α 6∈ ∆ entao ∆ ∪ {α} e inconsistente.∆, α ` β e ∆, α ` ¬β.∆ ` α→ β e ∆ ` α→ ¬β.
De ∆ ` α temos ∆ ` β e ∆ ` ¬β, contradicao. �
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Consistencia
lema 4
Se ∆ e consistente maximal entao
1 ∆ ` α se, e so se, α ∈ ∆;
2 ¬α ∈ ∆ se, e so se, α 6∈ ∆;
3 α→ β ∈ ∆ se, e so se, ¬α ∈ ∆ ou β ∈ ∆.
Dem.:
1 Se α ∈ ∆ entao ∆ ` α.Se ∆ ` α mas α 6∈ ∆ entao ∆ ∪ {α} e inconsistente.∆, α ` β e ∆, α ` ¬β.∆ ` α→ β e ∆ ` α→ ¬β.De ∆ ` α temos ∆ ` β e ∆ ` ¬β, contradicao. �
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Consistencia
lema 4
Se ∆ e consistente maximal entao
1 ∆ ` α se, e so se, α ∈ ∆;
2 ¬α ∈ ∆ se, e so se, α 6∈ ∆;
3 α→ β ∈ ∆ se, e so se, ¬α ∈ ∆ ou β ∈ ∆.
Dem.:
2 ¬α ∈ ∆ sse ∆ ` ¬α
∆ ` ¬α sse ∆ 6` α∆ 6` α sse α 6∈ ∆ �
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Consistencia
lema 4
Se ∆ e consistente maximal entao
1 ∆ ` α se, e so se, α ∈ ∆;
2 ¬α ∈ ∆ se, e so se, α 6∈ ∆;
3 α→ β ∈ ∆ se, e so se, ¬α ∈ ∆ ou β ∈ ∆.
Dem.:
2 ¬α ∈ ∆ sse ∆ ` ¬α∆ ` ¬α sse ∆ 6` α
∆ 6` α sse α 6∈ ∆ �
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Consistencia
lema 4
Se ∆ e consistente maximal entao
1 ∆ ` α se, e so se, α ∈ ∆;
2 ¬α ∈ ∆ se, e so se, α 6∈ ∆;
3 α→ β ∈ ∆ se, e so se, ¬α ∈ ∆ ou β ∈ ∆.
Dem.:
2 ¬α ∈ ∆ sse ∆ ` ¬α∆ ` ¬α sse ∆ 6` α∆ 6` α sse α 6∈ ∆ �
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Consistencia
lema 4
Se ∆ e consistente maximal entao
1 ∆ ` α se, e so se, α ∈ ∆;
2 ¬α ∈ ∆ se, e so se, α 6∈ ∆;
3 α→ β ∈ ∆ se, e so se, ¬α ∈ ∆ ou β ∈ ∆.
Dem.:
3 α→ β ∈ ∆ sse ∆ ` α→ β.
∆ ` α→ β sse ∆, α ` β.∆, α ` β sse ¬α ∈ ∆ ou β ∈ ∆ :
∆, α ` βSe ¬α 6∈ ∆ entao ¬¬α ∈ ∆, logo ∆ ` ¬¬α, portanto ∆ ` α(usando (A10), entao α ∈ ∆ portanto β ∈ ∆.
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Consistencia
lema 4
Se ∆ e consistente maximal entao
1 ∆ ` α se, e so se, α ∈ ∆;
2 ¬α ∈ ∆ se, e so se, α 6∈ ∆;
3 α→ β ∈ ∆ se, e so se, ¬α ∈ ∆ ou β ∈ ∆.
Dem.:
3 α→ β ∈ ∆ sse ∆ ` α→ β.∆ ` α→ β sse ∆, α ` β.
∆, α ` β sse ¬α ∈ ∆ ou β ∈ ∆ :
∆, α ` βSe ¬α 6∈ ∆ entao ¬¬α ∈ ∆, logo ∆ ` ¬¬α, portanto ∆ ` α(usando (A10), entao α ∈ ∆ portanto β ∈ ∆.
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Consistencia
lema 4
Se ∆ e consistente maximal entao
1 ∆ ` α se, e so se, α ∈ ∆;
2 ¬α ∈ ∆ se, e so se, α 6∈ ∆;
3 α→ β ∈ ∆ se, e so se, ¬α ∈ ∆ ou β ∈ ∆.
Dem.:
3 α→ β ∈ ∆ sse ∆ ` α→ β.∆ ` α→ β sse ∆, α ` β.∆, α ` β sse ¬α ∈ ∆ ou β ∈ ∆
:
∆, α ` βSe ¬α 6∈ ∆ entao ¬¬α ∈ ∆, logo ∆ ` ¬¬α, portanto ∆ ` α(usando (A10), entao α ∈ ∆ portanto β ∈ ∆.
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Consistencia
lema 4
Se ∆ e consistente maximal entao
1 ∆ ` α se, e so se, α ∈ ∆;
2 ¬α ∈ ∆ se, e so se, α 6∈ ∆;
3 α→ β ∈ ∆ se, e so se, ¬α ∈ ∆ ou β ∈ ∆.
Dem.:
3 α→ β ∈ ∆ sse ∆ ` α→ β.∆ ` α→ β sse ∆, α ` β.∆, α ` β sse ¬α ∈ ∆ ou β ∈ ∆ :
∆, α ` βSe ¬α 6∈ ∆ entao ¬¬α ∈ ∆, logo ∆ ` ¬¬α, portanto ∆ ` α(usando (A10), entao α ∈ ∆ portanto β ∈ ∆.
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Consistencia
lema 4
Se ∆ e consistente maximal entao
1 ∆ ` α se, e so se, α ∈ ∆;
2 ¬α ∈ ∆ se, e so se, α 6∈ ∆;
3 α→ β ∈ ∆ se, e so se, ¬α ∈ ∆ ou β ∈ ∆.
Dem.:
3 α→ β ∈ ∆ sse ∆ ` α→ β.∆ ` α→ β sse ∆, α ` β.∆, α ` β sse ¬α ∈ ∆ ou β ∈ ∆
:
¬α ∈ ∆ ou β ∈ ∆se ¬α ∈ ∆ entao ∆, α ` βse β ∈ ∆ entao ∆, α ` β
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Consistencia
lema 4
Se ∆ e consistente maximal entao
1 ∆ ` α se, e so se, α ∈ ∆;
2 ¬α ∈ ∆ se, e so se, α 6∈ ∆;
3 α→ β ∈ ∆ se, e so se, ¬α ∈ ∆ ou β ∈ ∆.
Dem.:
3 α→ β ∈ ∆ sse ∆ ` α→ β.∆ ` α→ β sse ∆, α ` β.∆, α ` β sse ¬α ∈ ∆ ou β ∈ ∆ :
¬α ∈ ∆ ou β ∈ ∆se ¬α ∈ ∆ entao ∆, α ` βse β ∈ ∆ entao ∆, α ` β
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
As demonstracoes estao escritas detalhadamente nas notas de aula.
Professor : [email protected]
Logica Basica
Cenas da 2a semana Um sistema dedutivo para Logica Proposicional Consistencia
Consistencia — cenas do proximo capıtulo
Metateorema da consistencia
Γ e consistente se, e so se, Γ e satisfazıvel.
Professor : [email protected]
Logica Basica