sl-cap2-8-4p

•

Humanas / Sociais

0

Revisando com resumos

31/03/2023

E aí, curtiu este material?

Ajude a incentivar outros estudantes a melhorar o conteúdo

Gostou desse material? Compartilhe! 🧡

Trabalho de Conclusão de Curso - TCC

95.910 Materiais compartilhados

Baixe o app para aproveitar ainda mais

Leia os materiais offline, sem usar a internet. Além de vários outros recursos!

Prévia do material em texto

✬ ✩
2.8 DEDUÇÃO
Newton José Vieira
UFMG
18 de setembro de 2008
✫ ✪
✬ ✩
Lógica Aplicada a Computação Cap. 2: Lógica Proposicional
Argumento correto
• Um argumento que diz que α segue de {β1, . . . , βn} é correto se, e somente se,
{β1, . . . , βn} |= α.
– β1, . . . , βn: premissas;
– α: conclusão.
• Um argumento correto é dito também ser válido, leǵıtimo.
• Um argumento incorreto é dito também ser inválido, ileǵıtimo, um sofisma.
• Um argumento formal é a afirmação de que certa fórmula (a conclusão) pode ser
deduzida a partir de um conjunto de fórmulas (as premissas).
c©2007 Newton José Vieira UFMG✫ ✪
✬ ✩
Lógica Aplicada a Computação Cap. 2: Lógica Proposicional
Sistemas formais (dedutivos) para consequência lógica
• A noção correspondente a consequência lógica no ńıvel formal é a de dedução.
• Argumento “formal”: afirmação de que uma fórmula (a conclusão) é dedut́ıvel a
partir de um conjunto (as premissas).
São comuns dois tipos de sistemas formais para capturar a noção de consequência
lógica:
• Um em que a linguagem é F e em que as premissas e conclusões de regras de
inferência são fórmulas. Uma regra diz diretamente que uma fórmula é
consequência lógica das premissas.
• Outro em que a linguagem contém um śımbolo que representa consequência
lógica e em que as premissas e conclusões são expressões dessa linguagem
enriquecida. Uma regra define que caso certas consequências lógicas se verifiquem
(premissas) então uma certa consequência lógica (conclusão) se verifica.
Ambos capturam formalmente consequência lógica.
c©2007 Newton José Vieira UFMG✫ ✪
✬ ✩
Lógica Aplicada a Computação Cap. 2: Lógica Proposicional
Regra de inferência
• Uma regra de inferência é a afirmação de que uma conclusão de formato α segue
diretamente de premissas de formatos β1, β2, . . . , βn.
• Notação (a ordem dos formatos das premissas é irrelevante):
β1 β2 · · · βn
α
.
• Para se qualificar como uma regra de inferência, os argumentos correspondentes
devem ser corretos.
c©2007 Newton José Vieira UFMG✫ ✪
✬ ✩
Lógica Aplicada a Computação Cap. 2: Lógica Proposicional
Sistema dedutivo
Um sistema dedutivo para uma lógica é um sistema formal que prescreve em
que condições uma fórmula é consequência lógica de um conjunto de fórmulas.
As regras são denominadas regras de inferência. As derivações são
denominadas deduções.
Existem vários tipos de sistemas dedutivos para a lógica proposicional.
A seguir, exemplos de regras de inferência que podem ser utilizadas em sistemas
dedutivos e em sistemas computacionais subjacentes.
c©2007 Newton José Vieira UFMG✫ ✪
✬ ✩
2.8.1 EXEMPLOS DE REGRAS DE INFERÊNCIA E DEDUÇÕES
Newton José Vieira
UFMG
18 de setembro de 2008
✫ ✪
✬ ✩
Lógica Aplicada a Computação Cap. 2: Lógica Proposicional
Regras que podem ser usadas em sistemas dedutivos e sistemas computacionais
Adição:
ad1:
α
α∨β ad2:
β
α∨β
Conjunção:
conj:
α β
α∧β
Modus tollens:
mt:
α→β ¬β
¬α
Silogismo hipotético:
sh:
α→β β→γ
α→γ
Simplificação:
simp1:
α∧β
α simp2:
α∧β
β
Modus ponens:
mp:
α→β α
β
Silogismo disjuntivo:
sd1:
α∨β ¬α
β sd2:
α∨β ¬β
α
Dilema construtivo:
dc:
α→β γ→δ α∨γ
β∨δ
• Algumas são idênticas às de SB. Por exemplo, ad1 é idêntica à regra disjp1 de SB.
• No entanto, os propósitos são diferentes: em SB, disjp1 expressa o fato de que
para uma interpretação i (de Σi), se v
i(α) = V , então vi(α∨β) = V ; aqui, ad1
expressa o fato de que para toda interpretação i, se vi(α) = V , então
vi(α∨β) = V .
c©2007 Newton José Vieira UFMG✫ ✪
✬ ✩
Lógica Aplicada a Computação Cap. 2: Lógica Proposicional
Dedutibilidade
Rememorando o Caṕıtulo 1:
• H ⊢ α significa: α é dedut́ıvel a partir de H (H ⇒ α na notação de sistemas
formais).
• Dedução de α a partir de H: derivação de α a partir de H.
Como as regras de inferência codificam argumentos válidos, tem-se a correção do
sistema dedutivo:
se H ⊢ α, então H |= α.
Logo, para verificar se H |= α basta encontrar uma dedução de α a partir de H.
c©2007 Newton José Vieira UFMG✫ ✪
✬ ✩
Lógica Aplicada a Computação Cap. 2: Lógica Proposicional
Exemplo de dedução
A dedução
1. p ∧ q (H)
2. (p ∨ r) → s (H)
3. p (simp1 1)
4. p ∨ r (ad1 3)
5. s (mp 2,4)
6. p ∧ s (conj 3,5)
mostra que
{p ∧ q, (p ∨ r) → s} ⊢ p ∧ s
e, portanto,
{p ∧ q, (p ∨ r) → s} |= p ∧ s.
c©2007 Newton José Vieira UFMG✫ ✪
✬ ✩
Lógica Aplicada a Computação Cap. 2: Lógica Proposicional
Mais um exemplo
1. q ∨ (r1 → r2) (H)
2. q → s (H)
3. ¬s → (r2 → p) (H)
4. ¬s (H)
5. ¬q (mt 2,4)
6. r1 → r2 (sd1 1,5)
7. r2 → p (mp 3,4)
8. r1 → p (sh 6,7)
Logo,
{q ∨ (r1 → r2), q → s,¬s → (r2 → p),¬s} ⊢ r1 → p
e, portanto,
{q ∨ (r1 → r2), q → s,¬s → (r2 → p),¬s} |= r1 → p.
c©2007 Newton José Vieira UFMG✫ ✪
✬ ✩
Lógica Aplicada a Computação Cap. 2: Lógica Proposicional
Consistência
Um conjunto de fórmulas H ⊆ F é dito consistente se e somente se não existe
α ∈ F tal que H ⊢ α e H ⊢ ¬α.
Dado um sistema dedutivo correto e completo:
O conceito de consistência (no ńıvel formal) corresponde ao de satisfabilidade
(no ńıvel conceitual):
H é consistente e, e somente se, H é satisfat́ıvel.
c©2007 Newton José Vieira UFMG✫ ✪
✬ ✩
Lógica Aplicada a Computação Cap. 2: Lógica Proposicional
Consequência lógica, dedutibilidade, satisfabilidade e consistência
NÍVEL CONCEITUAL: consequência lógica
dedutibilidade
satisfabilidade
consistênciaNÍVEL FORMAL:
Relacionamento no ńıvel conceitual:
H |= α se somente se H ∪ {¬α} é insatisfat́ıvel
Relacionamento no ńıvel formal:
H ⊢ α se somente se H ∪ {¬α} é inconsistente.
c©2007 Newton José Vieira UFMG✫ ✪
✬ ✩
Lógica Aplicada a Computação Cap. 2: Lógica Proposicional
Inconsistência e dedução
• Vimos: qualquer fórmula é consequência lógica de um conjunto inconsistente;
• Para um sistema dedutivo completo: qualquer fórmula pode ser deduzida de um
conjunto inconsistente.
• Logo: se H é inconsistente, então H ⊢ α para toda α ∈ F .
Se H se tornar inconsistente com o acréscimo de uma fórmula, então tudo passa
a ser dedut́ıvel!!!
Lógicas paraconsistentes: evitam essa “trivialização”.
c©2007 Newton José Vieira UFMG✫ ✪
✬ ✩
2.8.2 SISTEMA DEDUTIVO DO TIPO HILBERT
Newton José Vieira
UFMG
18 de setembro de 2008
✫ ✪
✬ ✩
Lógica Aplicada a Computação Cap. 2: Lógica Proposicional
Completude
Existe um conjunto de regras de inferência tal que
se H |= α, então H ⊢ α?
Ou seja, existe um sistema dedutivo completo?
Recordando, um sistema dedutivo é composto de (além de uma linguagem):
• regras de inferência; e
• axiomas: fórmulas que podem fazer parte de uma dedução sem serem deduzidas.
c©2007 Newton José Vieira UFMG✫ ✪
✬ ✩
Lógica Aplicada a Computação Cap. 2: Lógica Proposicional
Observações
• Existem múltiplos sistemas dedutivos completos (com mais ou menos regras, mais
ou menos axiomas).
• Um axioma α deve ser uma tautologia, já que se {} ⊢ α, então deve-se ter que
{} |= α.
• Toda tautologia τ deve ser dedut́ıvel, já que {} |= τ .
• Os axiomas são normalmente especificados mediante esquemas de axiomas; por
exemplo:
α→ (β→α).
representa um conjunto infinito de axiomas.
c©2007 Newton José Vieira UFMG✫ ✪
✬ ✩
Lógica Aplicada a Computação Cap. 2: Lógica Proposicional
Um exemplo de sistema dedutivo correto e completo, tipo Hilbert
• Se α, β e γ são fórmulas, então são axiomas:
Ax1: α→ (β→α)
Ax2: (α→ (β→γ)) → ((α→β) → (α→γ))
Ax3: (¬β→ ¬α) → ((¬β→α) →β)
• Regra de inferência: modus ponens.
Este sistema dedutivo aproveita o fato de que o conjunto de conectivos {→,¬} é
completo, dadas as seguintes equivalências:
• α∨β ≡ ¬α→β
• α∧β ≡ ¬(α→ ¬β)
• α↔β ≡ (α→β) ∧ (β→α) ≡ ¬((α→β) → ¬(β→α))
c©2007 Newton José Vieira UFMG✫ ✪
✬ ✩
Lógica Aplicada a Computação Cap. 2: Lógica Proposicional
Leitura intuitiva dos axiomas
Considerando a regra modus ponens:
• Ax1: α→ (β→α):
seα for dedut́ıvel, então se qualquer β for dedut́ıvel, ainda assim α será dedut́ıvel.
• Ax2: (α→ (β→γ)) → ((α→β) → (α→γ)):
dado que se α e β forem dedut́ıveis então γ também será, segue-se que se a
dedução de α implicar na dedução de β, então implicará também na dedução de
γ.
• Imagine como seria a leitura para Ax3.
c©2007 Newton José Vieira UFMG✫ ✪
✬ ✩
Lógica Aplicada a Computação Cap. 2: Lógica Proposicional
Exemplo de dedução
A seguinte dedução mostra que {} ⊢ p → p:
1. (p → ((p → p) → p)) → ((p → (p → p)) → (p → p)) (Ax2)
2. p → ((p → p) → p) (Ax1)
3. (p → (p → p)) → (p → p) (mp 1,2)
4. p → (p → p) (Ax1)
5. p → p (mp 3,4)
Esse tipo de sistema dedutivo é de interesse teórico. Não é adequado como base
para processamento em computadores:
• Obtenção de deduções é complexa.
• Deduções são ileǵıveis.
c©2007 Newton José Vieira UFMG✫ ✪
✬ ✩
Lógica Aplicada a Computação Cap. 2: Lógica Proposicional
Regras de inferência derivadas
Um exemplo:
α
...
β
α→β
Esta regra (I→) diz que para deduzir α→β:
(1) supor α como uma hipótese adicional; (2) provar β.
Note que:
• dentro da caixa α pode ser usada como premissa;
• fora da caixa (após α→β), α não pode ser usada.
O teorema da dedução justifica essa regra:
Sejam α, β ∈ F e H ⊆ F . Tem-se: se H ∪ {α} ⊢ β, então H ⊢ α→β.
c©2007 Newton José Vieira UFMG✫ ✪
✬ ✩
Lógica Aplicada a Computação Cap. 2: Lógica Proposicional
Completude
Teorema da Correção: Sejam H ⊆ F e α ∈ F . Se H ⊢ α então H |= α.
O teorema da correção segue trivialmente do fato de que os axiomas para
qualquer um dos esquemas Ax1, Ax2 e Ax3 são tautologias e a regra modus
ponens é válida.
Teorema da Completude: Sejam H ⊆ F e α ∈ F . Se H |= α então H ⊢ α.
A demonstração do teorema da completude é bem mais elaborada e será
omitida aqui.
c©2007 Newton José Vieira UFMG✫ ✪
✬ ✩
Lógica Aplicada a Computação Cap. 2: Lógica Proposicional
Um exemplo
Mostrando que {p → (q → r), q} ⊢ p → r sem usar I→:
1. p → (q → r) (H)
2. q (H)
3. (p → (q → r)) → ((p → q) → (p → r)) (Ax2)
4. (p → q) → (p → r) (mp 1,3)
5. q → (p → q) (Ax1)
6. p → q (mp 2,5)
8. p → r (mp 4,6)
Usando a nova regra:
1. p → (q → r) (H)
2. q (H)
3. p (Suposição)
4. q → r (mp 1,3)
5. r (mp 2,4)
6. p → r (I→ 3–5)
c©2007 Newton José Vieira UFMG✫ ✪
✬ ✩
Lógica Aplicada a Computação Cap. 2: Lógica Proposicional
Uso de lemas e de regras adicionais
Para facilitar a obtenção de deduções:
• Uso de lemas. Por exemplo, a dedução de p → p pode ser adaptada para gerar
uma dedução de α→α para qualquer α ∈ F . Logo,
qualquer fórmula α→α pode ser usada (como lema) numa dedução.
• Uso de regras de inferência adicionais. Por exemplo, a dedução de p → r a partir
de {p → (q → r), q}, pode ser adaptada para mostrar que
{α→ (β→γ), β} ⊢ α→γ para quaisquer α, β, γ ∈ F , justificando o uso da regra:
α→ (β→γ) β
α→γ
c©2007 Newton José Vieira UFMG✫ ✪
✬ ✩
Lógica Aplicada a Computação Cap. 2: Lógica Proposicional
Sistemas de dedução natural
Regras de inferência “naturais” associadas a cada conectivo:
• introdução: para inferir uma fórmula em que o conectivo figure como principal;
• eliminação: para inferir fórmulas a partir de premissa em que o conectivo figure
como principal.
Por exemplo, associadas ao conectivo → existem as regras:
• I→, para inferir fórmulas da forma α→β;
• modus ponens para inferir fórmulas a partir de premissa da forma α→β.
São regras intuitivas para o ser humano, usadas em demonstrações (informais) de
teoremas.
A seguir, sistemas dedutivos mais adequados para processamento computacional.
c©2007 Newton José Vieira UFMG✫ ✪
✬ ✩
Lógica Aplicada a Computação Cap. 2: Lógica Proposicional
FIM
c©2007 Newton José Vieira UFMG✫ ✪