sl-cap2-7-4p

Prévia do material em texto

✬ ✩
2.7 CONSEQUÊNCIA LÓGICA
Newton José Vieira
UFMG
16 de setembro de 2008
✫ ✪
✬ ✩
Lógica Aplicada a Computação Cap. 2: Lógica Proposicional
Consequência lógica
Definição:
Uma fórmula α é uma consequência lógica de um conjunto de fórmulas H (ou
H implica logicamente α), H |= α, se, e somente se, para qualquer i, se i
satisfaz H, então i satisfaz α.
Em particular:
• H |= τ para todo H ⊆ F e toda tautologia τ ;
• {} |= τ para toda tautologia τ ;
• H |= ⊤ para todo H ⊆ F ;
• H |= α para toda α ∈ F se não existir modelo para H.
c©2007 Newton José Vieira UFMG✫ ✪
✬ ✩
Lógica Aplicada a Computação Cap. 2: Lógica Proposicional
Exemplo
vi(p ∧ q) = V se e somente se i(p) = i(q) = V .
Neste caso, vi(p) = V , vi(q) = V , vi(p ∨ q) = V , vi(p → q) = V . Logo:
• {p ∧ q} |= p;
• {p ∧ q} |= q;
• {p ∧ q} |= p ∨ q;
• {p ∧ q} |= p → q.
Analisando-se as tabelas da verdade, vê-se que sempre que vi(p) = V , segue-se que
vi(p ∨ q) = V , vi(q ∨ p) = V e vi(q → p) = V . Logo:
• {p} |= p ∨ q;
• {p} |= q ∨ p;
• {p} |= q → p.
c©2007 Newton José Vieira UFMG✫ ✪
✬ ✩
Lógica Aplicada a Computação Cap. 2: Lógica Proposicional
Exemplo de padrão de inferência
• Um modelo i para {p → q, p} é tal que vi(p) = V e vi(p → q) = V .
• Segue-se que vi(q) = V .
• Portanto, {p → q, p} |= q.
Racioćınio análogo mostra um resultado mais geral:
{α→β, α} |= β para quaisquer fórmulas α e β
Regra de inferência modus ponens:
Se forem deduzidas as fórmulas α→β e α,
então pode-se deduzir a fórmula β.
Como {α→β,¬β} |= ¬α, tem-se a regra de inferência modus tollens:
Se forem deduzidas α→β e ¬β,
então pode-se concluir ¬α.
c©2007 Newton José Vieira UFMG✫ ✪
✬ ✩
Lógica Aplicada a Computação Cap. 2: Lógica Proposicional
Relação entre |= e →
H ∪ {α} |= β se, e somente se, H |= α→β.
Em particular, se H = ∅:
{α} |= β se, e somente se, {} |= α→β, ou seja,
{α} |= β se, e somente se, α→β é uma tautologia.
c©2007 Newton José Vieira UFMG✫ ✪
✬ ✩
Lógica Aplicada a Computação Cap. 2: Lógica Proposicional
Exemplo
Para mostrar que q |= p → q, basta mostrar que q → (p → q) é uma tautologia:
q → (p → q) ≡ ¬q ∨ (p → q) [α→β ≡ ¬α∨β]
≡ ¬q ∨ (¬p ∨ q) [α→β ≡ ¬α∨β]
≡ ¬q ∨ (q ∨ ¬p) [α∨β ≡ β∨α]
≡ (¬q ∨ q) ∨ ¬p [α∨(β∨γ) ≡ (α∨β)∨γ]
≡ ⊤ ∨ ¬p [¬α∨α ≡ ⊤]
≡ ⊤ [⊤∨α ≡ ⊤]
c©2007 Newton José Vieira UFMG✫ ✪
✬ ✩
Lógica Aplicada a Computação Cap. 2: Lógica Proposicional
Algumas outras maneiras
Para mostrar que q |= p → q, basta mostrar que q → (p → q) é uma tautologia:
• Tabela da verdade.
• Algoritmo de verificação de satisfabilidade: já que q → (p → q) é tautologia se, e
somente se, ¬(q → (p → q)) é insatisfat́ıvel.
• Sistema formal ST :
1. ¬q,¬p, q (Ax)
2. ¬q, p → q (condp 1)
3. q → (p → q) (condp 2)
• Sistema formal SI:
1. q, p,¬q (Ax)
2. q,¬(p → q) (condn 1)
3. ¬(q → (p → q)) (condn 2)
c©2007 Newton José Vieira UFMG✫ ✪
✬ ✩
Lógica Aplicada a Computação Cap. 2: Lógica Proposicional
Outro exemplo
• Qualquer fórmula da forma (α→β) ∧ (β→γ) → (α→γ) é tautológica.
• Segue-se que {(α→β) ∧ (β→γ)} |= α→γ.
• Disto, segue-se também que {α→β, β→γ} |= α→γ.
• Isto corrobora a chamada regra do silogismo hipotético:
De α→β e β→γ,
pode-se deduzir α→γ.
c©2007 Newton José Vieira UFMG✫ ✪
✬ ✩
Lógica Aplicada a Computação Cap. 2: Lógica Proposicional
Relação entre |= e ≡
A relação entre consequência e equivalência lógicas é dada por:
α ≡ β se, e somente se, {α} |= β e {β} |= α.
c©2007 Newton José Vieira UFMG✫ ✪
✬ ✩
Lógica Aplicada a Computação Cap. 2: Lógica Proposicional
Tudo segue de uma contradição
• Fórmulas da forma ⊥ →β são tautologias.
• Logo, H ∪ {⊥} |= β para qualquer β.
• ⊥ ≡ γ para qualquer contradição γ.
• Portanto, qualquer fórmula é consequência lógica de um conjunto que tem
contradição!
• Mais ainda: se H |= γ, para qualquer contradição γ, então qualquer fórmula é
consequência lógica de H.
Lógica paraconsistente: nem tudo segue de um conjunto contraditório.
c©2007 Newton José Vieira UFMG✫ ✪
✬ ✩
Lógica Aplicada a Computação Cap. 2: Lógica Proposicional
Relação entre consequência lógica e satisfabilidade
Consequência lógica e satisfabilidade são redut́ıveis um ao outro:
Sejam H ⊆ F e α ∈ F . Então H |= α se e somente se H ∪ {¬α} é
insatisfat́ıvel.
Assim, o problema de determinar se H |= α, pode ser atacado assim:
• Por meio do algoritmo insat, recebendo H ∪ {¬α} como argumento. Pode-se
apresentar uma derivação no sistema SI;
• Por meio de uma versão determińıstica de satB-nd, satB, em que A é inicializada
com H ∪ {¬α}. Pode-se apresentar uma derivação em SI.
• Por meio de um algoritmo do tipo DPLL que receba como entrada H ∪ {¬α} na
FNC.
• Por meio de um algoritmo baseado no sistema ST , similar a insat, que receba
como entrada {¬γ | γ ∈ H} ∪ {α}. Pode-se apresentar uma derivação em ST .
c©2007 Newton José Vieira UFMG✫ ✪
✬ ✩
Lógica Aplicada a Computação Cap. 2: Lógica Proposicional
Algumas outras propriedades bem intuitivas da consequência lógica
Propriedades simples da consequência lógica (H ⊆ F e α, β ∈ F):
• H ∪ {α} |= α para toda α.
(Qualquer fórmula é consequência de um conjunto de fórmulas que a contém.)
• Se H |= α e H ∪ {α} |= β, então H |= β.
(Se β é consequência de um conjunto H acrescido de uma fórmula α, sendo α
consequência do conjunto H, segue-se que β é consequência de H.)
• Se H |= α, então H ∪ {β} |= α.
(Ao se acrescentar novas fórmulas a um conjunto, toda afirmativa que era
consequência antes continua sendo após o acréscimo.)
Uma lógica para a qual esta propriedade se verifica é dita ser monotônica.
c©2007 Newton José Vieira UFMG✫ ✪
✬ ✩
Lógica Aplicada a Computação Cap. 2: Lógica Proposicional
O conceito de Teoria
Uma teoria T é um conjunto de fórmulas fechado sob consequência lógica. Ou seja,
T ⊆ F é uma teoria se, e somente se, se T |= α então α ∈ T .
• Seja Cn(A) = {α |A |= α} para A ⊆ F .
• Com isto, T é uma teoria se, e somente se, T = Cn(T ).
• A menor teoria é T = Cn(∅) = {α | ∅ |= α}, ou seja, o conjunto de todas as
tautologias.
• Toda tautologia pertence a toda teoria.
• A maior teoria é F . Esta é a única teoria insatisfat́ıvel (já que toda fórmula é
consequência lógica de um conjunto insatisfat́ıvel): uma teoria T é insatisfat́ıvel
se, e somente se, T = F .
• Segue-se que uma teoria T é satisfat́ıvel se, e somente se, existe α ∈ F tal que
α 6∈ T .
c©2007 Newton José Vieira UFMG✫ ✪
✬ ✩
Lógica Aplicada a Computação Cap. 2: Lógica Proposicional
Teoria axiomática
• Muitas vezes, se especifica uma “teoria” exibindo-se um conjunto A, de axiomas
(ńıvel formal), que expressam os chamados postulados (ńıvel conceitual) da teoria.
A teoria é Cn(A).
• Seja i uma interpretação qualquer, e T (i) = {α ∈ F | vi(α) = V }.
• T (i) é uma teoria.
• Se I é um conjunto de interpretações, então
T (I) = {α ∈ F | vi(α) = V para toda i ∈ I}
também é uma teoria.
• Assim, se I é o conjunto de todos os modelos correspondentes a uma certa
aplicação, o problema da formalização usando lógica proposicional é o de
encontrar um conjunto de fórmulas A (axiomas da teoria) tal que T (I) = Cn(A).
c©2007 Newton José Vieira UFMG✫ ✪
✬ ✩
Lógica Aplicada a Computação Cap. 2: Lógica Proposicional
Teoria completa
A teoria T é completa se, e somente se, para qualquer α ∈ F , α ∈ T ou ¬α ∈ T .
Dada uma interpretação i, T (i) é sempre uma teoria completa:
se α 6∈ T (i), então vi(α) = F e, neste caso, vi(¬α) = V e portanto
¬α ∈ T (i).
Por outro lado, T (I) não é completa se I tem mais de um membro.
c©2007 Newton José Vieira UFMG✫ ✪
✬ ✩
Lógica Aplicada a Computação Cap. 2: Lógica Proposicional
FIM
c©2007 Newton José Vieira UFMG✫ ✪