lac-cap3parte1

Prévia do material em texto

Caṕıtulo 3
Lógica de Predicados de Primeira
Ordem
A good idea has a way of becoming simpler and solving problems other than
that for which it was intended. Robert E. Tarjan (1948–)
A atividade de modelagem que antecede a expressão de conhecimento em lógica
proposicional é muito simples. Consta apenas em identificar quais são as proposições
simples relevantes e associar a cada uma delas uma variável proposicional. Já em
lógica de predicados a atividade de modelagem pode ser bastante mais sofisticada,
sendo normalmente baseada em um tipo de estrutura matemática suficiente para se
expressar conhecimento com uma estrutura também mais sofisticada. Assim, antes de
abordar a linguagem da lógica de predicados, será feita, na primeira seção, uma pequena
revisão desse tipo estrutura. Depois, após a definição da linguagem propriamente dita
na Seção 3.2, será apresentada a semântica da linguagem. Completando os aspectos
semânticos, será apresentada em seguida a noção de consequência para a lógica de
predicados. Finalmente, será abordado o conceito de dedução.
3.1 Modelando a realidade por meio de estruturas
Considere o seguinte argumento, clássico em livros de lógica:
Todo homem é mortal. Sócrates é um homem. Portanto, Sócrates é mortal.
Em lógica proposicional não é posśıvel modelar esse argumento, ou seja, não há como
conceber fórmulas α, β e γ que representem, respectivamente, as proposições todo
homem é mortal , Sócrates é um homem e Sócrates é mortal , de tal forma que {α, β} |=
γ! Aqui, a capacidade de identificar objetos e propriedades povoando a realidade, de
tal forma que seja posśıvel dizer que um certo objeto (por exemplo, Sócrates) tem uma
certa propriedade (por exemplo, é mortal) é importante.
Um argumento menos trivial que, como o acima, também é válido:
167
168 c©2006 Newton José Vieira Lógica aplicada à computação'
&
$
%
'
&
$
%
'
&
$
%
HOMENS
Sócrates
Platão
Aristóteles
Epicuro
...
MORTAIS
Medusa
Quimera
Minotauro
Pégaso
...
MUNDO GREGO
Zeus
Atena
Afrodite
Posêidon
...
Figura 3.1: Objetos e propriedades.
Todos amam quem ama alguém. Existe alguém que não ama a si mesmo.
Portanto, alguém não me ama.
Intuitivamente, dado que todos amem quem ame alguém e que uma certa pessoa não
ame a si mesma, então tal pessoa não ama ninguém (se ela amasse alguém, todos a
amariam, inclusive ela própria!). Logo, essa pessoa não me ama e, portanto, alguém
não me ama.
A coleção dos objetos identificados na realidade em questão pode ser modelada,
em matemática, por meio de um conjunto que, no contexto da aplicação, fica sendo o
conjunto universo. Já as propriedades podem ser modeladas, cada uma, por meio de
um conjunto, aquele que contenha todos os elementos que denotem objetos com a pro-
priedade em questão. Assim, no exemplo acima, uma estrutura matemática adequada
para modelar a realidade poderia ter um conjunto universo constitúıdo de elementos
para certos homens, animais, deuses etc., e teria pelo menos dois conjuntos, um con-
tendo os elementos correspondentes aos mortais e outro os elementos correspondentes
aos homens. A Figura 3.1 ilustra o exemplo, considerando o conjunto universo como
modelando o mundo grego antigo e explicitando dois conjuntos para modelar as duas
propriedades “ser homem” e “ser mortal”.
Chamando-se os conjuntos que modelam as propriedades“ser homem”e“ser mortal”
de h e m, e chamando-se Sócrates de S, o argumento poderia ser assim expresso:
Para todo objeto x do conjunto universo, se x ∈ h então x ∈ m. S ∈ h.
Portanto, S ∈ m.
Além da expressão condicional “se. . . então”, já modelada em lógica proposicional, este
argumento envolve o uso de uma quantificação “para todo objeto x do conjunto uni-
verso”. Será necessário um novo conectivo para expressar a quantificação. Ele será
introduzido na Seção 3.2.
Em geral, uma aplicação pode requerer, não apenas a identificação de propriedades,
mas também de inter-relacionamentos entre objetos. Tais inter-relacionamentos são
Newton José Vieira Caṕıtulo 3: Lógica de predicados 169
modelados matematicamente através de relações. Por exemplo, em uma aplicação em
que seja importante identificar os laços familiares das pessoas, existiriam relações do
tipo:
mãe = {(Maria , João), (Maria, Ivo), (Eva,Ana), . . .},
irmãos = {(João, Ivo), (Ivo, João), (Maria,Eva), . . .},
primos = {(Ana, João), (João,Ana), (Ana, Ivo), . . .}.
Tais relações modelam uma realidade em que:
Maria é mãe de João e de Ivo. Eva é mãe de Ana. João e Ivo são irmãos,
assim como Maria e Eva. Ana e João são primos. Ana e Ivo também são
primos.
Com isto, será posśıvel expressar, por exemplo, as proposições:
• Uma pessoa é filha da própria mãe:
para todo x e todo y, se (x, y) ∈ mãe, então (y, x) ∈ filho-de .
• Se duas pessoas são irmãs, seus filhos são primos:
para todo x, todo y, todo z e todo w, se (x, y) ∈ irmãos e (z, x) ∈ filho-de e
(w, y) ∈ filho-de, então (z, w) ∈ primos .
Além de conjuntos e relações, será posśıvel também usar o conceito de funções para
estruturar o universo de discurso. Assim, por exemplo, “mãe” pode ser modelada como
uma função em vez de relação. Com isto, carrega automaticamente toda a conotação
de relação funcional . A proposição do parágrafo anterior que se refere a mãe pode ser
assim expressa:
• Uma pessoa é filho da própria mãe:
para todo x, (x,mãe(x)) ∈ filho-de .
Na lógica proposicional, uma fórmula atômica consta de uma variável proposicional
ν, que é interpretada como νi ∈ {V, F}. Na lógica de predicados, uma fórmula atômica
será ou uma variável proposicional, interpretada como em lógica proposicional, ou uma
expressão cujo significado será uma afirmação do tipo k ∈ R, em que k é uma n-upla
de objetos do universo e R uma relação n-ária (lembrando que uma relação unária é
um conjunto). E para referência aos objetos será posśıvel o uso de funções (como no
último exemplo visto).
Em preparação para a definição da semântica da lógica de predicados, define-se o
conceito de estrutura como sendo uma tripla E = (U,F,R), em que:
• U é um conjunto não vazio (universo de discurso);
• F é um conjunto de funções; e
• R é um conjunto de relações.
170 c©2006 Newton José Vieira Lógica aplicada à computação
Exemplo 99 Uma estrutura (U,F,R) pode ser usada para modelar conhecimento
como o exemplificado anteriormente, sendo:
• universo de discurso: U = {Maria, João, Ivo,Eva,Ana, . . .};
• funções: F = {mãe , . . .};
• relações: R = {irmãos , primos ,filho-de , . . .}.
Uma quantificação do tipo “para todo objeto x do conjunto universo” é denominada
quantificação universal. Além desta, será posśıvel expressar também a quantificação
existencial : “existe objeto x do conjunto universo tal que”. Com tal quantificação
pode-se expressar, por exemplo, as proposições:
• Hugo tem irmãos:
existe x tal que (Hugo, x) ∈ irmãos .
• Todos os primos de Hugo têm irmãos:
para todo x, se (Hugo, x) ∈ primos, então existe y tal que (x, y) ∈ irmãos.
Existe uma relação binária expecialmente importante que pode ser usada na lógica
de predicados, que é a de igualdade. Em lógica (em matemática), quando se afirma que
e1 = e2, sendo e1 e e2 duas expressões, está-se afirmando que e1 e e2 denotam a mesma
entidade do universo de discurso. Assim, por exemplo, pode-se expressar as seguintes
proposições usando-se a igualdade:
• Hugo e Gugu são, na verdade, a mesma pessoa:
Hugo = Gugu.
• Todos têm mães:
para todo x, existe y tal que y = mãe(x).
Dependendo da estrutura assumida para modelar o conhecimento a ser expresso
em lógica de predicados, a expressão do conhecimento pode ser mais fácil, mais dif́ıcil
ou, até mesmo, imposśıvel. Como escolher entre estruturas alternativas? Infelizmente,
não existe uma resposta precisa para essa pergunta. Mas sabe-se que amelhor escolha
irá depender do uso que se fará do conhecimento representado. Assim, o processo de
modelagem via uma estrutura deve levar em conta o uso pretendido.
Exerćıcios
1. Seguem algumas proposições. De forma análoga ao que foi feito na presente
seção, identifique o universo de discurso, as relações e as funções suficientes para
expressar, mesmo que de forma aproximada tais proposições, e mostre como elas
ficam expressas usando quantificações e igualdade, além dos tipos de composições
vistos para lógica proposicional.
a) Quem faz exerćıcios f́ısicos tem melhor qualidade de vida.
Newton José Vieira Caṕıtulo 3: Lógica de predicados 171
b) Alunos não gostam de fazer provas.
c) Nem tudo que reluz é ouro.
d) Pedro sabe programar em qualquer linguagem funcional existente.
e) Quem conhece Godofredo o adora.
f) Marcos não tem amigos que gostem de utilizar o sistema operacional SOW.
g) Nenhum artista assiste a filmes que todas as pessoas que não sejam artistas
gostam de assistir.
h) Não conheço quem não odeie as brincadeiras de Joãozinho.
i) Quem gosta de Pedrinho não o conhece.
j) A relação “irmãos” é simétrica, mas não é transitiva. (Use o śımbolo pred-
icativo irmãos de dois argumentos.)
k) Juca adormece se e somente se a luz fica acesa.
l) Gatos e cachorros atacam se são ameaçados.
m) Ninguém visita Hermengarda, a menos que ela esteja afônica.
n) Todos amam quem ama alguém.
Para o item (a), uma resposta seria:
Universo: pessoas. Dois conjuntos:
• ex : as pessoas que fazem exerćıcios f́ısicos,
• qual : as pessoas que têm melhor qualidade de vida.
Para todo x, se x ∈ ex, então x ∈ qual.
3.2 A linguagem da lógica de predicados
O alfabeto da linguagem consta de três tipos de śımbolos:
• Śımbolos não lógicos: um conjunto de constantes (que pode ser vazio) a0, a1,
. . . para denotar elementos do universo; um de śımbolos funcionais (que também
pode ser vazio) fn0 , f
n
1 , . . . , para n > 0, sendo f
n
i usado para denotar uma função
de n argumentos; e um conjunto de um ou mais śımbolos predicativos, Pn0 , P
n
1 ,
. . . , sendo, para cada n ≥ 0, Pni usado para denotar uma relação de n argumentos,
se n > 0, e para denotar variáveis proposicionais, se n = 0. Em aplicações, nor-
malmente se usa palavras (ou mesmo frases) para constantes, śımbolos funcionais
e śımbolos predicativos, de forma que lembrem os objetos, funções e relações que
representam. Isso será feito aqui nos exemplos.
• Śımbolos lógicos: há os conectivos ⊤ (verum), ⊥ (falsum),¬ (negação), ∧ (con-
junção), ∨ (disjunção), → (condicional), ↔ (bicondicional), ∀ (universal) e ∃
(existencial), e um conjunto enumerável de variáveis x0, x1, . . . . Nos exemplos
serão usados nomes como x, y, z etc., para variáveis, como usual.
172 c©2006 Newton José Vieira Lógica aplicada à computação
• Śımbolos auxiliares: abre e fecha parênteses.
Nos exemplos, não sendo importante lembrar o que os śımbolos não lógicos denotem,
serão usados:
• contantes: a, b, c etc., eventualmente com ı́ndices.
• śımbolos funcionais: f , g, h, eventualmente com ı́ndices.
• śımbolos predicativos: p, q, r etc., eventualmente com ı́ndices.
• variáveis: x, y, z etc., eventualmente com ı́ndices.
Além disso, esses próprios śımbolos poderão ser usados como variáveis sintáticas para
denotar śımbolos dos tipos respectivos. Por exemplo, f poderá ser usado para denotar
um śımbolo funcional qualquer. O contexto deixará claro esse tipo de uso.
Antes de definir as fórmulas propriamente, define-se os termos, T , que são usados
para referência aos elementos do universo.
Definição 25 O conjunto dos termos, T , é definido assim:
a) cada constante e cada variável é um termo;
b) se f é um śımbolo funcional associado a n argumentos e t1, t2, . . . , tn são termos,
f(t1, t2, . . . , tn) é um termo.
c) só são termos as palavras que podem ser obtidas como mostrado em a e b.
Exemplo 100 São exemplos de termos:
• a
• x
• f(x)
• g(x, a)
• g(g(a, y), f(b))
O terceiro termo faz referência a um śımbolo funcional f que deve denotar uma função
com 1 argumento e o quarto a um śımbolo funcional g que deve denotar uma função
com com 2 argumentos. Ambos os śımbolos são utilizados novamente no quinto termo.
Segue a definição de fórmula para a lógica de predicados de primeira ordem.
Definição 26 O conjunto das fórmulas, F , (ou fórmulas bem formadas) pode ser assim
definido, recursivamente:
Newton José Vieira Caṕıtulo 3: Lógica de predicados 173
a) se p é um śımbolo predicativo associado a n argumentos e t1, . . . , tn são termos,
então p(t1, t2, . . . , tn) é uma fórmula (denominada fórmula atômica); se n = 0,
os parênteses são omitidos (neste caso, p é variável proposicional);
b.1) ⊤ e ⊥ são fórmulas;
b.2) se α é uma fórmula, então (¬α) é uma fórmula;
b.3) se α e β são fórmulas, então (α∧β), (α∨β), (α → β) e (α ↔ β) são fórmulas;
b.4) se α é uma fórmula e ν é uma variável, então (∀να) e (∃να) são fórmulas;
c) só são fórmulas as palavras que podem ser obtidas como indicado em (a) e (b.1)
a (b.4).
Alguns exempos de fórmulas são apresentados a seguir.
Exemplo 101 Alguns exemplos de fórmulas atômicas:
• p1
• p(a, b)
• acima(a, sobre(b)) (o objeto cujo nome é a está acima do objeto que está sobre o
objeto de nome b)
• = (+(2, 2), 4) (2 + 2 = 4)
• casados(Abel,mãe(Carlos)) (Abel é casado com a mãe de Carlos)
• q(x)
• r(f(x, y), f(f(a, y), g(x))))
Seguem exemplos de fórmulas não atômicas. Parênteses são eliminados de acordo
com as regras já vistas no caso proposicional, na Seção 2.2, considerando que ∀ e ∃ têm
a mesma precedência que ¬. Por exemplo, ∀x¬p(x) → q(x) ∨ r(x) abrevia a fórmula
(∀x ((¬p(x)) → (q(x) ∨ r(x)))).
• ¬acima(B,A) (o objeto cujo nome é B não está acima do objeto de nome A)
• pai(Adão,Abel) ∧ pai(Adão,Caim) (Adão é pai de Abel e de Caim)
• chove → assiste-tv(Ana) (se chove, Ana assiste TV )
• ∃x tia(x,Ana) (Ana tem uma tia)
• ∀x∃y gosta(x, y) (Todo mundo gosta de alguém)
• ∃x∀y gosta(x, y) (Alguém gosta de todo mundo)
174 c©2006 Newton José Vieira Lógica aplicada à computação
• ∀x∀y (irmãos(x, y) → irmãos(y, x)) (se fulano e beltrano são irmãos, então bel-
trano e fulano são irmãos)
• ∀x∀y (gosta(x,mãe(y)) → gosta(y, x)) (Todos gostam de quem gosta de sua mãe)
• ∀x(∃y ama(x, y) → ∀zama(z, x)) (Todos amam quem ama alguém)
O conceito de subfórmula, dado pela Definição 4 para lógica proposicional, é adap-
tado a seguir para lógica de primeira ordem.
Definição 27 O conjunto das subfórmulas de uma fórmula α, subf (α), pode ser assim
definido:
a) se α é fórmula atômica, ⊤ ou ⊥, então subf (α) = {α};
b) se α = (¬β), α = (∃ν β) ou α = (∀ν β), então subf (α) = {α} ∪ subf (β);
se α = (β ◦ γ), em que ◦ ∈ {∧,∨,→,↔}, subf (α) = {α} ∪ subf (β) ∪ subf (γ).
A subfórmula β será dita o escopo de ∃ν em ∃ν β e de ∀ν em ∀ν β. Uma ocorrência
da variável ν é dita ligada em uma fórmula α se ela estiver em uma subfórmula de α da
forma ∃ν β ou ∀ν β; e é dita livre em α, caso contrário. Note que uma mesma variável
pode ter ocorrências ligadas e livres na mesma fórmula, como y em ∀x p(x, y) → ∃y q(y):
a primeira ocorrência é livre e as outras duas são ligadas. Uma fórmula em que toda
ocorrência de variável é ligada é dita ser uma sentença.
Exemplo 102 Seja α = ∀x∀y(gosta(x,mãe(y)) → gosta(y, x)). As subfórmulas de α
são:
• α,
• ∀y(gosta(x,mãe(y)) → gosta(y, x)),
• gosta(x,mãe(y)) → gosta(y, x),
• gosta(x,mãe(y)) e
• gosta(y, x).
Todas as ocorrências de x e y são ligadas em α. Logo, α é uma sentença. Por outro
lado, a subfórmula ∀y(gosta(x,mãe(y)) → gosta(y, x)) tem duas ocorrências livres da
variv́el x e, portanto, ela não é uma sentença.
A seguir será apresentada a definição de substituição de toda ocorrência de uma
variável por um termo. Para isto, requer-seque antes se defina as situações em que
uma variável ν é substitúıvel por um termo t: ν é substitúıvel por t na fórmula α se,
e somente se, ν não ocorre em α no escopo de alguma quantificação com variável que
ocorra em t. Com isto, por exemplo, em ∃xp(x, y), y não pode ser substitúıda por x,
nem por f(x) etc., pois o quantificador ∃ menciona x, que por sua vez ocorre nesses
termos.
Newton José Vieira Caṕıtulo 3: Lógica de predicados 175
Definição 28 A substituição de uma variável ν por um termo t em uma fórmula α,
αtν, é a fórmula obtida substituindo-se em α toda variável livre ν pelo termo t nos
casos em que ν seja substitúıvel por t (se α não tem variável livre, αtν = α). Se ν não
é substitúıvel por t, então αtν não é definida.
Toda vez que se usar uma expressão do tipo αtν , ficará impĺıcito que ν deve ser
substitúıvel por t.
Exemplo 103 Seja a fórmula γ = ∃yp(y, x) ∨ ∀x¬q(x, z). Então:
• A ocorrência de x em ∃yp(y, x) é uma ocorrência livre, mas as de x em ∀x¬q(x, z)
não são. E como a variável z do termo g(A, z) não está no escopo de quantificador
com z em ∃yp(y, x), tem-se que:
γg(A,z)x = ∃yp(y, g(A, z)) ∨ ∀x¬q(x, z).
• Por outro lado, x não pode ser substitúıda por g(A, y) em γ, já que a variável y
do termo g(A, y) está no escopo de quantificador com y em ∃yp(y, x).
• A ocorrência de z em γ pode ser substitúıda por qualquer termo t que não tenha
a ocorrência da variável x, pois z está no escopo de ∀x na subfórmula ∀x¬q(x, z).
A definição de substituição de toda ocorrência de uma subfórmula por outra é similar
à Definição 8 feita para lógica proposicional.
Definição 29 A substituição de uma subfórmula σ por uma fórmula ϕ em γ, γ[σ/ϕ],
pode ser assim definida:
a) se σ 6∈ subf (γ), então γ[σ/ϕ] = γ;
b) se σ ∈ subf (γ), então
• se γ = σ, então γ[σ/ϕ] = ϕ;
• se γ = (bα), em que b ∈ {¬,∀ν,∃ν}, então γ[σ/ϕ] = (bα[σ/ϕ]),
• se γ = (αcβ), em que c ∈ {∧,∨,→,↔}, γ[σ/ϕ] = (α[σ/ϕ]cβ[σ/ϕ]).
Exemplo 104 Seja α = ∀x(p(y) → p(x)) ∨ ∃y(p(x) ∧ p(y)). Então α[p(y)/p(f(x))] =
∀x(p(f(x)) → p(x)) ∨ ∃y(p(x) ∧ p(f(x))). Por outro lado, α
f(x)
y é indefinida.
Exerćıcios
1. Diga quais são os termos, fórmulas atômicas, e subfórmulas que ocorrem nas
fórmulas:
176 c©2006 Newton José Vieira Lógica aplicada à computação
a) chove → assiste-tv(Ana)
b) ∃x tia(x,Ana)
c) ∀x∃y gosta(x, y)
d) ∀x∀y (gosta(x,mãe(y)) → gosta(y, x))
e) ∀x(∃y ama(x, y) → ∀zama(z, x))
2. Expresse em lógica de predicados:
a) Quem faz exerćıcios f́ısicos tem melhor qualidade de vida.
b) Alunos não gostam de fazer provas.
c) Nem tudo que reluz é ouro.
d) Pedro sabe programar em qualquer linguagem funcional existente.
e) Quem conhece Godofredo o adora.
f) Marcos não tem amigos que gostem de utilizar o sistema operacional SOW.
g) Nenhum artista assiste a filmes que todas as pessoas que não sejam artistas
gostam de assistir.
h) Não conheço quem não odeie as brincadeiras de Joãozinho.
i) Quem gosta de Pedrinho não o conhece.
j) A relação “irmãos” é simétrica, mas não é transitiva. (Use o śımbolo pred-
icativo irmãos de dois argumentos.)
k) Juca adormece se e somente se a luz fica acesa.
l) Gatos e cachorros atacam se são ameaçados.
m) Ninguém visita Hermengarda, a menos que ela esteja afônica.
n) Todos amam quem ama alguém.
3. Para cada fórmula a seguir diga qual é o escopo de cada quantificação e quais
são as ocorrências livres e ligadas de todas as variáveis (lembre-se das regras de
eliminação de parênteses):
a) ∀y(∃zp(y, z) → ∀xp(x, y))
b) ∀xp(x, a) ∨ ∃yp(x, y)
c) p(x, 0) ∧ ∀y(p(x, y) → p(x,+(y, 1))) → ∀yp(x, y)
d) ∀x(p(x) → q1(a, f(y))) → ∀yq2(f(x), y, x)
4. Para cada fórmula α da questão anterior, para cada variável livre, ν, em α, diga
que variáveis não podem ocorrer em um termo t para que ν seja subtitúıvel por
t em α.
Newton José Vieira Caṕıtulo 3: Lógica de predicados 177
3.3 Semântica da linguagem
Em lógica proposicional, para ser posśıvel determinar se o valor lógico de uma fór-
mula é V ou F são necessárias interpretações para os śımbolos não lógicos: as variáveis
proposicionais. Para a lógica de predicados, para ser posśıvel determinar o valor lógico
de uma fórmula, são necessários um conjunto universo e interpretações para os śımbo-
los não lógicos (constantes, śımbolos funcionais e śımbolos predicativos). O conjunto
universo é necessário para avaliar as fórmulas governadas por quantificadores. Assim,
uma interpretação para a linguagem da lógica de predicados resulta no que se denomina
uma estrutura, como definida na Seção 3.1.
Uma estrutura i = (U,F,R) que seja uma interpretação para a linguagem consid-
erada deve tal que:
• o conjunto universo, U , é não vazio;
• para cada constante a, ai ∈ U (o elemento denotado por a);
• para cada śımbolo funcional f associado a n ≥ 1, F contém uma função f i :
Un → U (a função denotada por f); e
• para cada śımbolo predicativo p associado a n ≥ 1, R contém uma relação pi ⊆ Un
(a relação denotada por p).1
Observe que, mesmo dada uma estrutura i = (U,F,R), em que U contenha os
objetos ai (dentre outros, possivelmente), F seja o conjunto das funções f i e R o
conjunto das relações pi, é ainda imposśıvel interpretar um termo que contenha alguma
variável que não esteja no escopo de um quantificador. Na definição recursiva da função
de valoração vi, no entanto, será necessário fazer referência à interpretação de uma
variável. Para tornar posśıvel tal interpretação, será suposto existir uma espécie de
“interpretação padrão” para cada variável ν, um elemento espećıfico do universo de
discurso, o qual será denotado simplesmente por νi.
Com isso, dada uma estrutura i que dá uma interpretação para os śımbolos não
lógicos, pode-se definir a interpretação de um termo t, εi(t) (o elemento correspondente
a t), recursivamente:
a) εi(ν) = νi para cada variável ν;
b) εi(a) = ai para cada constante a;
c) εi(f(t1, t2, . . . , tn)) = f
i(εi(t1), ε
i(t2), . . . , ε
i(tn)) para cada śımbolo funcional f
associado a n.
Exemplo 105 Suponha um mundo em que os objetos sejam pessoas, dentre as quais
Sônia, Carlos, Pedro, Ana, Maria e João, dentre outros, e que precisamos formalizar
algumas relações familiares. A estrutura a ser usada seria:
1Para variáveis proposicionais, pode-se imaginar que pi = V corresponderia a se ter 〈〉 ∈ pi e pi = F
corresponderia a se ter 〈〉 6∈ pi, já que existem apenas duas relações de zero argumentos: {} e {〈〉}.
178 c©2006 Newton José Vieira Lógica aplicada à computação
• Universo: {Sônia, Carlos, Pedro, Ana, Maria, João, . . . }.
• Funções:
– mãe: mãe(Pedro) = Sônia, mãe(Ana) = Maria,. . .
• Relações:
– casados = {(Carlos ,Sônia), . . .}.
– masculino = {Carlos ,Pedro, João, . . .}.
– feminino = {Sônia,Ana,Maria, . . .}.
– filho = {(Pedro,Carlos), (Pedro,Sônia), . . .}.
– filha = {(Ana,Carlos), (Ana,Maria), . . .}.
Seguem śımbolos não lógicos com respectivas interpretações:
• Constantes: Si = Sônia, Ci = Carlos, P i = Pedro, Ai = Ana e M i = Maria.
• Śımbolos funcionais: mi = mãe.
• Śımbolos predicativos: casi = casados , masci = masculino, femi = feminino,
filhoi = filho, filhai = filha.
Supondo ainda que xi = yi = Godofredo, tem-se:
• εi(x) = xi = Godofredo;
• εi(M) = M i = Maria;
• εi(m(P )) = mi(εi(P )) = mãe(P i) = mãe(Pedro) = Sônia;
Ressalta-se dois pontos importantes. Em primeiro lugar, a interpretação i inclui o
universo de discurso considerado, U . Isto é importante para o significado dos quantifi-
cadores, a ser visto abaixo. Em segundo lugar, tal universo de discurso é suposto não
vazio. Isto simplifica o tratamento do assunto, sem constituir uma restrição relevante.
Uma relação binária muito usada em matemática, e que pode ser útil em muitas
aplicações, é a de igualdade, expressa utilizando-se o śımbolo “=”. Tal śımboloé op-
cional na linguagem e, quando se define pelo uso de lógica de primeira ordem, deve-se
decidir se a mesma terá igualdade ou não. O śımbolo de igualdade é considerado um
śımbolo lógico, visto que seu significado é pré-definido, como visto a seguir. Aqui será
feito como é comum: em vez de usar a notação prefixada será usada a infixada para a
igualdade. Por exemplo, no lugar de = (m(P ), S) será usada a notação m(P ) = S.
Definição 30 Dada uma estrutura i para interpretação dos śımbolos não lógicos e
supondo-se que i atribui um valor νi para cada variável ν, como dito anteriormente,
define-se recursivamente a valoração lógica de um fórmula:
Newton José Vieira Caṕıtulo 3: Lógica de predicados 179
• vi(ν) = νi para cada ν ∈ V;
• se α é uma fórmula atômica p(t1, . . . , tn), então v
i(α) = V se, e somente se,
(εi(t1), . . . , ε
i(tn)) ∈ p
i;
• se a linguagem tem igualdade, então se α é (a fórmula atômica) t1 = t2, então
vi(α) = V se, e somente se, εi(t1) = ε
i(t2);
2
• vi(⊤) = i⊤ = V e vi(⊤) = i⊥ = F ;
• se α ∈ F , então vi(¬α) = i¬ vi(α);
• se α, β ∈ F , então
vi(α ∧ β) = vi(α) i∧ vi(β),
vi(α ∨ β) = vi(α) i∨ vi(β),
vi(α → β) = vi(α) i→vi(β),
vi(α ↔ β) = vi(α) i↔vi(β).
• se α ∈ F , então vi(∀να) = V se, e somente se, para todo e ∈ U vi(α) = V ,
supondo νi = e e xi inalterado para x 6= ν.
• se α ∈ F , então vi(∃να) = V se, e somente se, existe e ∈ U tal que vi(α) = V ,
supondo νi = e e xi inalterado para x 6= ν.
Exemplo 106 Considere a linguagem definida no Exemplo 105, assim como as inter-
pretações lá assumidas. Seguem interpretações para algumas fórmulas:
• vi(cas(S,C)) = V , pois casi = casados, εi(S) = Si = Sônia, εi(C) = Ci = Carlos
e (Sônia,Carlos) ∈ casados .
• vi(m(P )=S) = V , pois εi(m(P )) = mi(P i) = mãe(Pedro) = Sônia = Si = εi(S).
• vi(masc(P ) ∨ fem(P )) = V , visto que
vi(masc(P ) ∨ fem(P )) = vi(masc(P )) i∨ vi(fem(P )) = V i∨ F = V
já que:
– vi(masc(P )) = V , pois εi(P ) = P i = Pedro, masci = masculino e Pedro ∈
masculino; e
– vi(fem(P )) = F , pois εi(P ) = P i = Pedro, femi = feminino e Pedro 6∈
feminino.
• vi(cas(S, y)) depende de um valor para xi. Se, por exemplo, xi = Carlos, então
vi(cas(S, y)) = V .
• vi(∃ycas(S, y)) = V , pois:
2Note que esta última iguadade quer dizer que εi(t1) é o mesmo elemento que ε
i(t2). Deve-se ficar
atento para os dois significados, dados pelo contexto em que o śımbolo “=” aparece.
180 c©2006 Newton José Vieira Lógica aplicada à computação
vi(∃ycas(S, y)) = V
sse existe e tal que vi(cas(S, y)) = V se yi = e
sse existe e tal que (Si, e) ∈ casi
sse existe e tal que (Sônia, e) ∈ casados.
Como (Sônia,Carlos) ∈ casados, vi(∃ycas(S, y)) = V .
• vi(∀x∀y(filha(x, y) → fem(x))) = V , pois:
vi(∀x∀y(filha(x, y) → fem(x))) = V
sse para todo e1, e2 v
i(filha(x, y) → fem(x)) = V se xi = e1 e y
i = e2
sse para todo e1, e2 v
i(filha(x, y)) i→vi(fem(x)) = V se xi = e1 e yi = e2.
Como sempre que (e1, e2) ∈ filha, e1 ∈ feminino, segue-se o resultado.
Como seria um algoritmo para determinar se uma interpretação i satisfaz uma
fórmula α? A construção de um algoritmo a partir da Definição 30, nos moldes em que
foi constrúıdo o algoritmo da Figura 2.3 para a lógica proposicional, não pode ser feita,
visto que o universo em i pode não ser finito. Mas, se o universo U da interretação i
for finito, um algoritmo baseado diretamente na Definição 30 seria como mostrado na
Figura 3.2. A variável t do algoritmo é uma variável local usada guardar o valor xi a
ser restaurado após o laço de verificação correspondente a ∀x ou ∃x.
Observe que se α é uma sentença (não tem variáveis livres) vi(α) não depende
dos valores xi atribúıdos às variáveis! Na verdade, vi(α) só depende dos valores xi
atribúıdos às variáveis livres de α.
O conceito de equivalência lógica visto na Definição 7 continua valendo aqui: duas
fórmulas α e β são logicamente equivalentes, α ≡ β, se, e somente se, vi(α) = vi(β) para
toda i. Assim, em particular, todas as fórmulas válidas são logicamente equivalentes
entre si, assim como todas as insatisfat́ıveis.
Aqui também vale o análogo do Teorema 2: sendo α, β, γ ∈ F e γ′ o resultado de
substituir em γ uma ou mais ocorrências de α por β, se α ≡ β, então γ ≡ γ′.
Seguem exemplos de equivalências lógicas particularmente importantes envolvendo
quantificadores. Note que todas as equivalências mostradas para lógica proposicional,
continuam valendo aqui (basta considerar α, β etc. como fórmulas da lógica de predi-
cados, em vez de lógica proposicional).
Exemplo 107 Suponha que α(x) é uma fórmula que tenha x como única variável
livre. Analogamente, α(x, y) tem duas variáveis livres. Algumas equivalências lógicas
importantes envolvendo quantificadores são:
• α(x) → β(x) ≡ ¬α(x)∨ β(x) (note que vi(α(x) → β(x)) = vi(¬α(x)∨ β(x)) para
toda i, independemente do valor que tenha xi)
• ∃xα(x) ≡ ¬∀x¬α(x) (assim, consegue-se expressar o quantificador existencial
utilizando-se o universal)
Newton José Vieira Caṕıtulo 3: Lógica de predicados 181
proc avalia(fórmula α, interpretação i) retorna {V, F}:
caso α seja
var: retorne αi
p(t1, . . . , tn):se (ε
i(t1), . . . , ε
i(tn)) ∈ p
i então
retorne V
senão
retorne F
fimse
⊤: retorne V
⊥: retorne F
¬β: retorne i¬ avalia(β, i)
β ∧ γ: retorne avalia(β, i) i∧ avalia(γ, i)
β ∨ γ: retorne avalia(β, i) i∨ avalia(γ, i)
β → γ: retorne avalia(β, i) i→ avalia(γ, i)
β ↔ γ: retorne avalia(β, i) i↔ avalia(γ, i)
∀xβ: t := xi;
para cada e ∈ U faça
xi := e;
se avalia(β, i) = F então retorne F fimse
fimpara;
xi := t; retorne V
∃xβ: t := xi;
para cada e ∈ U faça
xi := e;
se avalia(β, i) = V então retorne V fimse
fimpara;
xi := t; retorne F
fimcaso
fim avalia
Figura 3.2: Avaliação de uma fórmula para uma interpretação de universo finito.
182 c©2006 Newton José Vieira Lógica aplicada à computação
• ∀xα(x) ≡ ¬∃x¬α(x) (assim, consegue-se expressar o quantificador universal utilizando-
se o existencial)
• ¬∀xα(x) ≡ ∃x¬α(x)
• ¬∃xα(x) ≡ ∀x¬α(x)
• ∀x(α(x) ∧ β(x)) ≡ ∀xα(x) ∧ ∀xβ(x)
• ∃x(α(x) ∨ β(x)) ≡ ∃xα(x) ∨ ∃xβ(x)
• ¬∀x∃yα(x, y) ≡ ∃x¬∃yα(x, y) ≡ ∃x∀y¬α(x, y)
A seguir, é apresentado um exemplo com detalhes da demonstração de uma das
equivalências do exemplo anterior.
Exemplo 108 Para mostrar que ∀xα(x) ≡ ¬∃x¬α(x), basta provar que para toda
interpretação i, vi(¬∃x¬α(x)) = vi(∀xα(x)), ou seja, vi(¬∃x¬α(x)) = V se, e somente
se, vi(∀xα(x)) = V , o que é feito a seguir:
vi(¬∃x¬α(x)) = V sse i¬ vi(∃x¬α(x)) = V
sse vi(∃x¬α(x)) = F
sse não existe e ∈ U tal que vi(¬α(x)) = V se xi = e
sse para todo e ∈ U vi(¬α(x)) = F se xi = e
sse para todo e ∈ U i¬ vi(α(x)) = F se xi = e
sse para todo e ∈ U vi(α(x)) = V se xi = e
sse vi(∀xα(x)) = V .
Assim como na Definição 10, um modelo para uma fórmula α, agora da lógica
de predicados, é uma interpretação i, agora uma estrutura, tal que vi(α) = V . E,
analogamente à Definição 11, uma fórmula é satisfat́ıvel se, e somente se, tem um
modelo. Um conjunto de fórmulas que tenha um modelo também é dito satisfat́ıvel. E
se α não é satisfat́ıvel (não tem modelo), diz-se que é insatisfat́ıvel (ou uma contradição).
E um conjunto de fórmulas que não tenha um modelo também é dito insatisfat́ıvel.
Exemplo 109 Para mostrar que a fórmula ∀x∃yp(x, f(y)) é satisfat́ıvel, basta con-
struir um modelo para ela. Um exemplo de modelo para tal fórmula seria aquele
constitúıdo de:
• Universo: conjunto N dos números naturais;
• pi: menor ;
• f i: sucessor.
Newton José Vieira Caṕıtulo 3: Lógica de predicados 183
Com isto, vi(∀x∃yp(x, f(y))) = V , pois é verdade que para todo x ∈ N existe y ∈ N
tal que x < y + 1.
Um outro modelo seria:
• Universo: conjunto {0, 1};
• pi: igualdade;
• f i: função tal que f i(0) = 1 e f i(1) = 0.
Evidentemente, existe uma infinidade de modelos para ∀x∃yp(x, f(y)).
O conceito correspondente ao de tautologia é o de validade.
Definição 31 Uma fórmulaα é válida se, e somente se, vi(α) = V para qualquer
interpretação i. Se a fórmula não é válida, é dita ser falseável.
Seguem exemplos de fórmulas válidas, dentre as quais algumas tautológicas. As
tautológicas são aquelas cujas validades não dependem dos quantificadores eventual-
mente usados, ou seja, suas validades dependem apenas do significado dos conectivos
proposicionais.
Exemplo 110 As seguintes fórmulas são válidas, sendo que a primeira, a segunda e a
quinta são tautológicas. Para a última faz-se uma demonstração de validade.
• masc(a) ∨ ¬masc(a) (tautológica)
• masc(x) ∨ ¬masc(x) (tautológica, mesmo tendo variável livre)
• ∀x(masc(x) ∨ ¬masc(x))
• ∀x∃y(cas(x, y) → (fem(y) → cas(x, y)))
• ∃xp(x) ∨ ¬∃xp(x) (tautológica)
• ∃xp(x) ∨ ∀x¬p(x)
Para demonstrar a validade desta, deve-se mostrar que para toda i vi(∃xp(x) ∨
∀x¬p(x)) = V , ou seja vi(∃xp(x))ct∨vi(∀x¬p(x)) = V . Ou seja, basta mostrar
que se vi(∃xp(x)) = F , então vi(∀x¬p(x)) = V . Suponha então que vi(∃xp(x)) =
F . Segue-se que não existe e ∈ U tal que e ∈ pi. Com isto, para todo e ∈ U e 6∈ pi,
ou seja, para todo e ∈ U vi(p(x)) = F para xi = e. Logo, vi(∀x¬p(x)) = V .
O Teorema 3 continua valendo no contexto de lógica de primeira ordem: para
quaisquer fórmulas α e β, α ≡ β se, e somente se, α ↔ β é válida. Assim, por
exemplo, para mostrar que (∃xp(x) → ∀yq(y)) ↔ ∀x∀y(p(x) → q(y)) é válida basta
mostrar que ∃xp(x) → ∀yq(y) ≡ ∀x∀y(p(x) → q(y)) (ou vice-versa).
Ainda como em lógica proposicional, uma fórmula é uma contingência se e somente
se é satisfat́ıvel e falseável. Segue-se que uma fórmula é uma contingência se e somente
se não é válida nem insatisfat́ıvel.
184 c©2006 Newton José Vieira Lógica aplicada à computação
Exemplo 111 Sejam p um śımbolo predicativo binário e f um śımbolo funcional
unário. Seguem duas interpretações i = (U, {pi}, {f i}) para a fórmula ∀xp(x, f(x)),
uma que a satisfaz e outra que a falseia:
• U é o conjunto dos naturais, pi a relação menor e f i a função sucessor sobre os
naturais;
• U é o conjunto dos brasileiros, pi a relaçao odeia e f i a função mãe.
Como a primeira satisfaz e a segunda falseia ∀xp(x, f(x)), esta é uma contingência.
Para mostrar que uma fórmula não é válida, ou seja, que é falseável, basta apresentar
uma interpretação i que a falseie. Segue um exemplo.
Exemplo 112 Para mostrar que ∃x(p(x) → q(x)) → (∃xp(x) → ∃xq(x)) não é válida,
constrói-se uma interpretação i que a falseia:
• Universo: {a, b}.
• Conjuntos: pi = {a}; qi = {}.
vi(∃x(p(x) → q(x)) → (∃xp(x) → ∃xq(x))) = F , pois (1) vi(∃x(p(x) → q(x))) = V e
(2) vi(∃xp(x) → ∃xq(x)) = F :
(1) vi(∃x(p(x) → q(x))) = V , pois vi(p(x) → q(x)) = V para xi = b, já que b 6∈ pi; e
(2) vi(∃xp(x) → ∃xq(x)) = F , pois (2.1) vi(∃xp(x)) = V , já que a ∈ pi, e (2.2)
vi(∃xq(x)) = F já que a, b 6∈ qi.
Seguem exemplos de fórmulas insatisfat́ıveis (contraditórias).
Exemplo 113 As seguintes fórmulas são insatisfat́ıveis:
• p(a) ∧ ¬p(a)
• p(x) ∧ ¬p(x)
• ∀x(p(x) ∧ ¬p(x))
• ∃x(p(x) ∧ ¬p(x))
• ∃xp(x) ∧ ¬∃xp(x)
• ∃xp(x) ∧ ∀x¬p(x)
Newton José Vieira Caṕıtulo 3: Lógica de predicados 185
contingênciasvalidades contradições
satisfat́ıveis falseáveis
u uu u
u u
Figura 3.3: Relacionamentos entre fórmulas da lógica de predicados e suas negações.
Para mostrar a insatisfabilidade desta última, deve-se mostrar que para toda i vi(∃xp(x)∧
∀x¬p(x)) = F , ou ainda, que ∃xp(x) i∧ ∀x¬p(x) = F . Assim, basta mostrar que se
vi(∀x¬p(x)) = V então vi(∃xp(x)) = F . Suponha então que vi(∀x¬p(x)) = V . Segue-
se que para todo e ∈ U vi(¬p(x)) = V para xi = e, ou ainda, para todo e ∈ U
vi(p(x)) = F para xi = e. Logo, para todo e ∈ U e 6∈ pi e, assim, não existe e ∈ U tal
que e ∈ pi. Neste caso, não existe e ∈ U tal que vi(p(x)) = V para xi = e, e assim não
é o caso que vi(∃xp(x)) = V , o que leva à conclusão que vi(∃xp(x)) = F .
As relações entre fórmulas e suas negações, que valem para lógica proposicional,
valem aqui também. A Figura 3.3, análoga à Figura 2.8 para lógica proposicional,
mostra as relações entre os conceitos que se acabou de introduzir, incluindo as relações
entre fórmulas e suas negações.
Em lógica de predicados, o problema de determinar se uma fórmula é satisfat́ıvel
(ou falseável) é indecid́ıvel, assim como o de determinar se é insatisfat́ıvel (ou válida).
A seguir, é apresentada, na Figura 3.4, uma“tentativa frustrada”de construir um algo-
ritmo para satisfabilidade a partir de satA-nd (aquele da Figura 2.9). Em particular, ele
pode entrar em loop “tentando construir”uma relação infinita, como será exemplificado
mais à frente. A única diferença para satA-nd é o acréscimo das quatro últimas linhas
no final do pseudocomando caso para tratar dos quantificadores. Além disso, há as
seguintes restrições:
• Como ressaltado em comentário, escolha(A) só pode escolher fórmula marcada
da forma V ∀να ou F∃να em último caso, ou seja, se não houver outro tipo de
fórmula em A.
• A chamada constnova deve gerar uma constante nova (não presente em {sγ} ∪
Σ ∪ A).
• A chamada proxtsv(sγ,Σ,A) deve retornar um termo sem variáveis, com śımbolos
presentes em {sγ} ∪ Σ ∪ A, que ainda não tenha sido usado para instanciar sγ;
se em {sγ} ∪Σ ∪ A não existir nenhuma constante, deve retornar uma constante
nova. Aqui, instanciar sγ por um termo t significa substituir ν por t em α, tanto
no caso em que γ é ∀να, quanto no caso em que γ é ∃να.
186 c©2006 Newton José Vieira Lógica aplicada à computação
proc-nd satA-nd-lpo(fórmula γ):
conjunto de fórmulas marcadas A;
conjunto de variáveis marcadas Σ;
elemento de {V, F} s;
termo sem variáveis tsv;
Σ = ∅;
A := {V γ};
repita
sγ := escolha(A); A := A− {sγ}; { Só escolher ∀να ou F∃να em último caso!}
caso sγ seja
∗átomo: se sγ ∈ Σ então fracasso senão Σ := Σ ∪ {sγ} fimse
V⊤,F⊥: { continue }
V⊥,F⊤: fracasso
V ¬α: A := A ∪ {Fα}
F¬α: A := A ∪ {V α}
V α ∧ β: A := A ∪ {V α, V β}
Fα ∧ β: A := A ∪ {escolha-nd({Fα, Fβ})} { escolha não determińıstica }
V α ∨ β: A := A ∪ {escolha-nd({V α, V β})} { escolha não determińıstica }
Fα ∨ β: A := A ∪ {Fα, Fβ}
V α → β: A := A ∪ {escolha-nd({Fα, V β})} { escolha não determińıstica }
Fα → β: A := A ∪ {V α, Fβ}
V α ↔ β: A := A ∪ {escolha-nd({{V α, V β}, {Fα, Fβ}})} { escolha não determińıstica }
Fα ↔ β: A := A ∪ {escolha-nd({{V α, Fβ}, {Fα, V β}})} { escolha não determińıstica }
V ∀να: tsv := proxtsv(sγ,Σ,A);
se tsv 6= vazio então A := A ∪ {sγ, V αtsvν } fimse
F∀να: A := A ∪ {Fαconstnovaν }
V ∃να: A := A ∪ {V αconstnovaν }
F∃να: tsv := proxtsv(sγ,Σ,A);
se tsv 6= vazio então A := A ∪ {sγ, Fαtsvν } fimse
fimcaso
até A = ∅;
sucesso
fim satA-nd-lpo
Figura 3.4: Verificação de satisfabilidade em lógica de primeira ordem.
Newton José Vieira Caṕıtulo 3: Lógica de predicados 187
∅{V ∀xp(x) → ∃xp(x)}
∅{F∀xp(x)} ∅{V ∃xp(x)}
{}{Fp(a)} {}{V p(a)}
{Fp(a)}{}
sucesso
{V p(a)}{}
sucesso
Figura 3.5: Árvore de computação para satA-nd-lpo(∀xp(x) → ∃xp(x)).
O objetivo por trás dessa “solução” é a construção de uma interpretação com um uni-
verso o menor posśıvel que satisfaça a fórmula em questão. Para isto, o universo vai
sendo constrúıdo com os termos posśıveis de serem constrúıdos na computação em
questão, nos momentos em que se quer satisfazer fórmulas da forma ∀να e falsear
fórmulas da forma ∃να. Pode-se imaginar que termos diferentes designam elementos
diferentes, de tal forma que um termo t pode ser, ele mesmo, considerado um elemento
do universo constrúıdo até o momento. No caso em que as fórmulas presentes em
{sγ} ∪Σ ∪ A não contenham nenhuma constante ou śımbolo funcional, uma constante
nova é criada (afinal, o universo não é vazio). O problema (como não poderia deixar
de ser, e é exemplificado abaixo) é que essa geração desenfreada de termos, mesmo que
sistemática, pode levar o “algoritmo” a entrar em loop.
Segue uma série de exemplospara ressaltar diversos aspectos. Primeiramente, um
que lida com quantificação existencial, na forma V ∃νγ e também na forma F∀νγ.
Exemplo 114 A árvore de computação da Figura 3.5 mostra que a fórmula ∀xp(x) →
∃xp(x) é satisfat́ıvel. Tanto no ramo em que é encontrada a fórmula F∀xp(x), quanto
no ramo em que é encontrada V ∃xp(x), é gerada a constante nova (é suficiente ser nova
no ramo) a. No primeiro caso (ramo da esquerda), mostra-se que uma interpretação
i em que ai 6∈ pi falseia ∀xp(x) (isto é, vi(∀xp(x)) = F ), e no segundo caso, uma
interpretação i em que ai ∈ pi satisfaz ∃xp(x) (isto é, vi(∃xp(x)) = V ). Assim, uma
interpretação de universo {a} e relaçao pi = {} falseia ∀xp(x) e, portanto, satistaz
∀xp(x) → ∃xp(x); enquanto que uma interpretação de universo {a} e relaçao pi = {}
satisfaz ∃xp(x) e, logo, também satistaz ∀xp(x) → ∃xp(x).
O próximo exemplo, bem simples, envolve quantificação universal.
Exemplo 115 A Figura 3.6 apresenta a árvore de computação que mostra a satisfa-
bilidade de ∀xp(x). O modelo encontrado tem universo {ai} e pi = {ai}.
O próximo exemplo, que também lida com quantificação universal, mostra uma
tentativa de construir um modelo infinito.
188 c©2006 Newton José Vieira Lógica aplicada à computação
∅{V ∀xp(x)}
∅{V p(a), V ∀xp(x)}
{V p(a)}{V ∀xp(x)}
{V p(a)}{}
sucesso
Figura 3.6: Árvore de computação para satA-nd-lpo(∀xp(x).
Exemplo 116 Veja como a árvore de computação da Figura 3.7 apresenta um ramo
infinito à direita, provocando um loop. A fórmula p(0)∧∀xp(x) → p(f(x)) é satisfat́ıvel,
mas, como se pode notar no ramo da direita, o “algoritmo” está tentando construir uma
interpretação i para a qual:
• 0i ∈ pi
• f i(0i) ∈ pi
• f i(f i(0i)) ∈ pi
• e assim por diante, indefinidamente.
Uma interpretação que satisfaz a fórmula é aquela em que o conjunto universo contém
os números naturais, 0i é o número zero, f i é a função sucessor e pi é o conjunto
(infinito) dos naturais. Uma outra é aquela em que {0, 1} é um subconjunto do universo,
pi = {0, 1} e f i é tal que f i(0) = 1, f i(1) = 0 e f i(e) = e para todo e 6∈ {0, 1}.
O próximo exemplo mostra que é imposśıvel falsear a fórmula do Exemplo 114,
∀xp(x) → ∃xp(x)). Logo ela é válida.
Exemplo 117 A Figura 3.8 apresenta a árvore de computação que mostra a validade
de ∀xp(x) → ∃xp(x)).
Existiria um sistema formal similar a SA (ou SB) para satisfabilidade em lógica de
primeira ordem? A resposta é não! No entanto, existe um sistema formal similar a
SI para insatisfabilidade! Existindo este, dado que o problema é indecid́ıvel, realmente
não pode existir sistema formal para satisfabilidade. Um sistema formal similar a SI
para insatisfabilidade será visto por ocasião da apresentação do método de tableaux
semânticos.
Assim como em lógica proposicional, as árvores de computação em que é a raiz é
rotulada com Fα, sendo α uma fórmula a ser provada como válida, é o que se chama
um tableau. O sistema de tableaux semânticos para lógica de primeira ordem será
Newton José Vieira Caṕıtulo 3: Lógica de predicados 189
∅{V p(0) ∧ ∀xp(x) → p(f(x))}
∅{V p(0), V ∀xp(x) → p(f(x))}
{V p(0)}, {V ∀xp(x) → p(f(x))}
{V p(0)}{V p(0) → p(f(0)), V ∀xp(x) → p(f(x))}
{V p(0)}{Fp(0), V ∀xp(x) → p(f(x))} {V p(0)}{V p(f(0)), V ∀xp(x) → p(f(x))}
fracasso
{V p(0), V p(f(0))}{V ∀xp(x) → p(f(x))}
{V p(0), V p(f(0))}{V p(f(0)) → p(f(f(0))), V ∀xp(x) → p(f(x))}
{V p(0), V p(f(0))}{Fp(f(0)), V ∀xp(x) → p(f(x))}
{V p(0), V p(f(0))}{V p(f(f(0))), V ∀xp(x) → p(f(x))}fracasso
{V p(0), V p(f(0)), V p(f(f(0)))}{V ∀xp(x) → p(f(x))}
...
Figura 3.7: Árvore de computação para satA-nd-lpo(p(0) ∧ ∀xp(x) → p(f(x))).
abordado mais adiante, ocasião em que se deixará expĺıcitas as regras usadas para as
quantificações universal e existencial.
Exerćıcios
1. Determine fórmulas que expressem as proposições a seguir utilizando as seguintes
propriedades:
• arara(x): x é uma arara;
• cv(x): x tem cores vivas;
• pequeno(x): x é pequeno;
• grande(x): x é grande;
• nalto(x): x faz ninho em árvores altas.
a) Toda arara tem cores vivas.
b) Nenhum pássaro pequeno faz ninho em árvores altas.
c) Pássaros que não fazem ninho em árvores altas não têm cores vivas.
d) Araras são grandes.
190 c©2006 Newton José Vieira Lógica aplicada à computação
∅{F∀xp(x) → ∃xp(x))}
∅{V ∀xp(x), F∃xp(x)}
∅{V p(a), V ∀xp(x), F∃xp(x)}
{V p(a)}{V ∀xp(x), F∃xp(x)}
{V p(a)}{Fp(a), V ∀xp(x), F∃xp(x)}
fracasso
Figura 3.8: Árvore de computação para satA-nd-lpo(∀xp(x) → ∃xp(x)).
2. Sejam p um śımbolo predicativo binário e a uma constante. Apresente duas
interpretações, uma que satisfaça e outra que falseie a sentença ∀x(∃yp(x, y) →
p(x, a)).
3. Seja uma linguagem que tenha p, um śımbolo predicativo binário, como único
śımbolo não lógico. Como seriam as estruturas i que seriam modelos para a
fórmula ∀x∀y x = y?
4. Demonstre as equivalências lógicas:
a) ∃xα(x) ≡ ¬∀x¬α(x)
b) ∀x(α(x) ∧ β(x)) ≡ ∀xα(x) ∧ ∀xβ(x)
5. Demonstre as não equivalências lógicas:
a) ∀x(α(x) ∨ β(x)) 6≡ ∀xα(x) ∨ ∀xβ(x)
b) ∃x(α(x) ∧ β(x)) 6≡ ∃xα(x) ∧ ∃xβ(x)
6. Mostre que a seguinte fórmula é válida: ∃x(D(x) → ∀xD(x)). Interpretando
D(x) como x dança e supondo o universo como constitúıdo de pessoas, ela diz
“existe alguém tal que, se ele dança, então todos dançam”.
7. Mostre que ¬p(a) ∧ ∀xp(x) é insatisfat́ıvel.
8. Mostre que são válidas, para quaisquer α, β ∈ F :
a) ∀xα → ∃xα
b) ∀x(α → β) → (∀xα → ∀β
c) ∃x∃yα ↔ ∃y∃xα
d) ∃x∀yα ↔ ∀y∃xα
Newton José Vieira Caṕıtulo 3: Lógica de predicados 191
9. Mostre que não são válidas:
a) (∀xp(x) → ∀xq(x)) → ∀x(p(x) → q(x))
b) (∃xp(x) ↔ ∃xq(x)) → ∀x(p(x) ↔ q(x))
c) ∀x∃yr(x, y) → ∃xr(x, x)
10. Mostre que ∀xp(x) → p(x) (a última ocorrência de x é livre) é válida e que
p(x) → ∀xp(x) não é válida.
3.4 Consequência lógica
Assim como em lógica proposicional, uma fórmula α é consequência lógica de um con-
junto de fórmulas H, H |= α, se, e somente se, para toda interpretação i, vi(α) = V
sempre que vi(β) = V para toda β ∈ H. Ou seja, H |= α se, e somente, todo modelo
para H é um modelo para α. A diferença com relação a lógica proposicional, é que aqui
a interpretação é uma estrutura nos moldes definidos na seção anterior.
Exemplo 118 As seguintes consequências lógicas podem ser mostradas:
• {∀x(homem(x) → mortal (x)), homem(Sócrates)} |= mortal (Sócrates)
• {mortal (Sócrates)} |= ∃xmortal (x)
• {∃xp(x) → ∀xq(x), p(a)} |= ∀xq(x)
Algumas consequências lógicas gerais interessantes são apresentadas no exemplo a
seguir.
Exemplo 119 Suponha que α(x) é uma fórmula que tenha x como única variável livre.
Algumas consequências lógicas envolvendo quantificadores são:
• {∀xα(x)} |= α(a)
• {α(a)} |= ∃xα(x)
• {∀xα(x) ∨ ∀xβ(x)} |= ∀x (α(x) ∨ β(x))
• {∃x (α(x) ∧ β(x))} |= ∃xα(x) ∧ ∃xβ(x)
• {∃x∀y α(x, y)} |= ∀y∃xα(x, y)
Já o inverso desta última não é válida, pois existe interpretação i que satisfaz
∀y∃x p(x, y) e não satisfaz ∃x∀y p(x, y); por exemplo, uma em que:
– Universo: {a, b};
– pi = {(a, a), (b, b)}.
192 c©2006 Newton José Vieira Lógica aplicada à computação
As consequências lógicas do Exemplo 119 podem ser usadas para fundamentar regras
de inferência para se lidar com os quantificadores. No entanto, na próxima seção serão
apresentadas regras de mais longo alcance.
Aqui, como em lógica proposicional, α ≡ β, se, e somente se, {α} |= β e {β} |= α.
As propriedades da consequência lógica vistas na Seção 2.7 valem também para a
lógica de predicados. Em particular, vale o teorema da dedução, Teorema 12, segundo
o qual H ∪ {α} |= β se, e somente se, H |= α → β, assim como:
• H ∪ {α} |= α.
• Se H |= α e H ∪ {α} |= β, então H |= β.
• Se H |= α, então H ∪ {β} |= α. Ou seja, a lógica é monotônica.
• H |= α se e somente se H ∪ {¬α} é insatisfat́ıvel.
O problema de determinar se uma fórmula é consequêncialógica de um conjunto
de fórmulas, que era decid́ıvel em lógica proposicional, passa a ser indecid́ıvel em lógica
de primeira ordem. Para demonstrar tal indecidibilidade basta mostrar que, dada uma
máquina de Turing M e uma palavra w, é posśıvel construir (existe algoritmo para tal)
H e α tais que H |= α se e somente se M pára se a entrada é w.3
Exerćıcios
1. Repita o Exerćıcio 1 da seção anterior e mostre que a última fórmula é conse-
quência lógica das outras. Note que, para isto, é preciso explicitar a relação que
existe entre pequeno e grande.
3.5 Dedução
Assim como para a lógica proposicional, existem sistemas dedutivos corretos e comple-
tos para a lógica de predicados. Tais sistemas, basicamente, acrescentam axiomas e/ou
regras de inferência para lidar com os quantificadores universal e existencial.
Nesta seção serão revisitados alguns sistemas dedutivos vistos para lógica proposi-
cional com os acréscimos pertinentes.
3.5.1 Exemplos de regras de inferência e deduções
A seguir, são apresentadas algumas regras de inferência normalmente utilizadas para
lidar com os quantificadores. Evidentemente, as regras de inferência apresentadas na
Seção 2.8.1 continuam valendo para a lógica de predicados.
3Uma demonstração pode ser vista, por exemplo, em Ben-Ari, M. Mathematical Logic for Computer
Science, 2nd ed., Springer, 2001.