Lógica Computacional
LEI, 2015/2016
DI-UBI
Aula Prática 8
Análise do algoritmo T .
1. Mostre que:
(a)
(b)
(c)
(d)
ImplFree((¬p ∨ q) ∧ (p ∨ s)) = (¬p ∨ q) ∧ (p ∨ s)
NNFC((¬p ∨ q) ∧ (p ∨ s)) = (¬p ∨ q) ∧ (p ∨ s)
CNFC((¬p ∨ q) ∧ (p ∨ s)) = (¬p ∨ q) ∧ (p ∨ s)
CNFC(¬p ∧ (¬q ∨ ¬s)) = (¬p ∧ (¬q ∨ ¬s))
2. Prove que:
(a) Dada ϕ ∈ GP , a fórmula ψ = ImplFree(ϕ) é tal que ψ ∈ HP e ϕ ≡ ψ.
(b) Dada ϕ ∈ HP , a fórmula ψ = NNFC(ϕ) é tal que ψ ∈ HP , ϕ ≡ ψ e FNN(ψ). Mostre
também que ψ não tem ocorrências de duplas negações.
(c) Dadas ϕ1 , ϕ2 ∈ HP tais que FNN(ϕ1 ) e FNN(ϕ2 ), a fórmula ψ = Distr(ϕ1 , ϕ2 ) é tal
que ψ ∈ HP e FNN(ψ), e se FNC(ϕ1 ) e FNC(ϕ2 ) também FNC(ψ).
(d) Dada ϕ ∈ HP tal que FNN(ϕ), a fórmula ψ = CNFC(ϕ) é tal que ψ ∈ HP , ϕ ≡ ψ e
FNC(ψ).
1. (a) ImplFree((¬p ∨ q) ∧ (p ∨ s))
= (ImplFree(¬p ∨ q)) ∧ (ImplFree(p ∨ s)), caso em que ϕ = ϕ1 ∧ ϕ2
= (ImplFree(¬p) ∨ ImplFree(q)) ∧ (ImplFree(p) ∨ ImplFree(s)), caso em que ϕ =
ϕ1 ∨ ϕ2
= (¬ImplFree(p) ∨ ImplFree(q)) ∧ (ImplFree(p) ∨ ImplFree(s)), caso em que ϕ = ¬ϕ1
= (¬p ∨ q) ∧ (p ∨ s) pois ImplFree(p) = p para qualquer p ∈ P (caso base)
(b) NNFC((¬p ∨ q) ∧ (p ∨ s))
= (NNFC(¬p ∨ q)) ∧ (NNFC(p ∨ s)), caso em que ϕ = ϕ1 ∧ ϕ2
= (NNFC(¬p) ∨ NNFC(q)) ∧ (NNFC(p) ∨ NNFC(s)), caso em que ϕ = ϕ1 ∨ ϕ2
= (¬p ∨ q) ∧ (p ∨ s) pois NNFC(p) = p para qualquer p ∈ P (caso base)
(c) CNFC((¬p ∨ q) ∧ (p ∨ s))
= (CNFC(¬p ∨ q)) ∧ (CNFC(p ∨ s)), caso em que ϕ = ϕ1 ∧ ϕ2 na definição de CNFC
= (Distr(CNFC(¬p),CNFC(q))) ∧ (Distr(CNFC(p), CNFC(s))), caso em que ϕ = ϕ1 ∨
ϕ2 na definição de CNFC
= (Distr(¬p,q)) ∧ (Distr(p, s)), caso base na definição de CNFC
= (¬p ∨ q) ∧ (p ∨ s) pois Distr(p1 ,p2 ) = p1 ∨ p2 para qualquer p1 , p2 ∈ P (caso base)
(d) CNFC(¬p ∧ (¬q ∨ ¬s))
= (CNFC(¬p)) ∧ (CNFC(¬q ∨ ¬s)), caso em que ϕ = ϕ1 ∧ ϕ2 na definição de CNFC
= (CNFC(¬p)) ∧ (Distr(CNFC(¬q), CNFC(¬s)), caso em que ϕ = ϕ1 ∨ ϕ2 na definição
de CNFC
= ¬p ∧ (Distr(¬q, ¬s)), caso base na definição de CNFC
= ¬p ∧ (¬q ∨ ¬s) pois Distr(p1 ,p2 ) = p1 ∨ p2 para qualquer p1 , p2 ∈ P (caso base)
2. (a) Dada ϕ ∈ GP , a fórmula ψ =ImplFree(ϕ) é tal que ψ ∈ HP e ϕ ≡ ψ.
Prova por indução na estrutura de ϕ.
• Caso ϕ = p ∈ P então ψ =ImplFree(p) = p, por definição.
Ou seja, p ≡ p pois ≡ é reflexiva e p ∈ HP pois é um símbolo proposicional.
• Caso ϕ = ϕ1 ∧ ϕ2 então ψ =ImplFree(ϕ1 ) ∧ ImplFree(ϕ2 ), por definição.
Seja ψ1 =ImplFree(ϕ1 ) e ψ2 =ImplFree(ϕ2 ) então por H.I. sabemos que ϕ1 ≡ ψ1 ,
ψ1 ∈ HP e ϕ2 ≡ ψ2 , ψ2 ∈ HP . Logo ϕ1 ∧ ϕ2 ≡ ψ1 ∧ ψ2 , ψ1 ∧ ψ2 ∈ HP , como se
queria mostrar.
• Caso ϕ = ϕ1 ∨ ϕ2 então ψ =ImplFree(ϕ1 ) ∨ ImplFree(ϕ2 ), por definição.
Seja ψ1 =ImplFree(ϕ1 ) e ψ2 =ImplFree(ϕ2 ) então por H.I. sabemos que ϕ1 ≡ ψ1 ,
ψ1 ∈ HP e ϕ2 ≡ ψ2 , ψ2 ∈ HP . Logo ϕ1 ∨ ϕ2 ≡ ψ1 ∨ ψ2 , ψ1 ∨ ψ2 ∈ HP , como se
queria mostrar.
• Caso ϕ = ¬ϕ1 então ψ = ¬ImplFree(ϕ1 ), por definição.
Seja ψ1 =ImplFree(ϕ1 ) então por H.I. sabemos que ϕ1 ≡ ψ1 , ψ1 ∈ HP . Logo
¬ϕ1 ≡ ¬ψ1 , ¬ψ1 ∈ HP , ou seja, ¬ϕ1 ≡ ψ, ψ ∈ HP , como se queria mostrar.
• Caso ϕ = ϕ1 → ϕ2 então ψ = ¬ImplFree(ϕ1 ) ∨ ImplFree(ϕ2 ), por definição.
Seja ψ1 =ImplFree(ϕ1 ) e ψ2 =ImplFree(ϕ2 ) então por H.I. sabemos que ϕ1 ≡ ψ1 ,
ψ1 ∈ HP e ϕ2 ≡ ψ2 , ψ2 ∈ HP . Logo ¬ϕ1 ≡ ¬ψ1 , ¬ψ1 ∈ HP e ¬ϕ1 ∨ ϕ2 ≡ ¬ψ1 ∨ ψ2 ,
¬ψ1 ∨ ψ2 ∈ HP , como se queria mostrar.
(b) Dada ϕ ∈ HP , a fórmula ψ =NNFC(ϕ) é tal que ψ ∈ HP e ϕ ≡ ψ e ψ não tem ocorrências de duplas negações.
Seja DN(ϕ): HP → N0 , o número de ocorrências de duplas negações na fórmula ϕ, a
função definida indutivamente:

0




0




 1 + DN(ϕ1 )
DN(ϕ1 ) + DN(ϕ2 )
DN(ϕ) =


DN(ϕ

1 ) + DN(ϕ2 )



DN(ϕ
) + DN(ϕ2 )

1


DN(ϕ1 ) + DN(ϕ2 )
, ϕ = p and p ∈ P
, ϕ = ¬p and p ∈ P
, ϕ = ¬¬ϕ1
, ϕ = ϕ1 ∧ ϕ2
, ϕ = ϕ1 ∨ ϕ2
, ϕ = ¬(ϕ1 ∧ ϕ2 )
, ϕ = ¬(ϕ1 ∨ ϕ2 )
Prova por indução na definição de NNFC(ϕ).
• Caso ϕ seja um literal então ϕ =NNFC(ϕ), por definição.
Logo ϕ ≡ ϕ pois ≡ é reflexiva e DN(ϕ) = 0 pois é um literal.
• Caso ϕ = ¬¬ϕ1 então ψ =NNFC(ϕ1 ), por definição.
Então por H.I. sabemos que ϕ1 ≡ ψ e DN(ψ) = 0. Logo ¬¬ϕ1 ≡ ψ, ou seja ϕ ≡ ψ
e DN(ψ) = 0, como se queria mostrar.
• Caso ϕ = ¬(ϕ1 ∧ ϕ2 ) então ψ =NNFC(¬ϕ1 ) ∨ NNFC(¬ϕ2 ), por definição.
Seja ψ1 =NNFC(¬ϕ1 ) e ψ2 =NNFC(¬ϕ2 ) então por H.I. sabemos que ¬ϕ1 ≡ ψ1 ,
¬ϕ2 ≡ ψ2 e DN(ψ1 ) = DN(ψ2 ) = 0. Logo ψ = ψ1 ∨ψ2 tal que ¬ϕ1 ∨¬ϕ2 ≡ ψ1 ∨ψ2 ,
ou seja, ¬(ϕ1 ∧ ϕ2 ) ≡ ψ e DN(ψ) = 0, como se queria mostrar.
2
• Caso ϕ = ¬(ϕ1 ∨ ϕ2 ) então ψ =NNFC(¬ϕ1 ) ∧ NNFC(¬ϕ2 ), por definição.
Seja ψ1 =NNFC(¬ϕ1 ) e ψ2 =NNFC(¬ϕ2 ) então por H.I. sabemos que ¬ϕ1 ≡ ψ1 ,
¬ϕ2 ≡ ψ2 e DN(ψ1 ) = DN(ψ2 ) = 0. Logo ψ = ψ1 ∧ψ2 tal que ¬ϕ1 ∧¬ϕ2 ≡ ψ1 ∧ψ2 ,
ou seja, ¬(ϕ1 ∨ ϕ2 ) ≡ ψ e DN(ψ) = 0, como se queria mostrar.
• Caso ϕ = ϕ1 ∨ ϕ2 então ψ =NNFC(ϕ1 ) ∨ NNFC(ϕ2 ), por definição.
Seja ψ1 =NNFC(ϕ1 ) e ψ2 =NNFC(ϕ2 ) então por H.I. sabemos que ϕ1 ≡ ψ1 ,
ϕ2 ≡ ψ2 e DN(ψ1 ) = DN(ψ2 ) = 0. Logo ψ = ψ1 ∨ ψ2 tal que ϕ1 ∨ ϕ2 ≡ ψ1 ∨ ψ2 ,
ou seja, ϕ1 ∨ ϕ2 ≡ ψ e DN(ψ) = 0, como se queria mostrar.
• Caso ϕ = ϕ1 ∧ ϕ2 então ψ =NNFC(ϕ1 ) ∧ NNFC(ϕ2 ), por definição.
Seja ψ1 =NNFC(ϕ1 ) e ψ2 =NNFC(ϕ2 ) então por H.I. sabemos que ϕ1 ≡ ψ1 ,
ϕ2 ≡ ψ2 e DN(ψ1 ) = DN(ψ2 ) = 0. Logo ψ = ψ1 ∧ ψ2 tal que ϕ1 ∧ ϕ2 ≡ ψ1 ∧ ψ2 ,
ou seja, ϕ1 ∧ ϕ2 ≡ ψ e DN(ψ) = 0, como se queria mostrar.
(c) Para fazer
(d) Para fazer
3