teorico4

Prévia do material em texto

Lógica Computacional
Material Teórico
Responsável pelo Conteúdo:
Prof.ª Dr.ª Cristiane Camilo Hernandez
Prof. Me. Manuel Fernandez Paradela Ledón
Revisão Textual:
Prof. Me. Luciano Vieira Francisco
Lógica de Predicados
• Motivação: a Lógica Proposicional;
• Lógica de Predicados;
• Convenções Utilizadas para a Lógica de Predicados.
• Conhecer as características fundamentais da lógica de predicados;
• Conhecer os conectivos lógicos e quantifi cadores utilizados na lógica de predicados;
• Analisar exemplos de proposições lógicas compostas em lógica de predicados.
OBJETIVOS DE APRENDIZADO
Lógica de Predicados
Orientações de estudo
Para que o conteúdo desta Disciplina seja bem 
aproveitado e haja maior aplicabilidade na sua 
formação acadêmica e atuação profissional, siga 
algumas recomendações básicas: 
Assim:
Organize seus estudos de maneira que passem a fazer parte 
da sua rotina. Por exemplo, você poderá determinar um dia e 
horário fixos como seu “momento do estudo”;
Procure se alimentar e se hidratar quando for estudar; lembre-se de que uma 
alimentação saudável pode proporcionar melhor aproveitamento do estudo;
No material de cada Unidade, há leituras indicadas e, entre elas, artigos científicos, livros, vídeos e 
sites para aprofundar os conhecimentos adquiridos ao longo da Unidade. Além disso, você tam-
bém encontrará sugestões de conteúdo extra no item Material Complementar, que ampliarão 
sua interpretação e auxiliarão no pleno entendimento dos temas abordados;
Após o contato com o conteúdo proposto, participe dos debates mediados em fóruns de discus-
são, pois irão auxiliar a verificar o quanto você absorveu de conhecimento, além de propiciar o 
contato com seus colegas e tutores, o que se apresenta como rico espaço de troca de ideias e 
de aprendizagem.
Organize seus estudos de maneira que passem a fazer parte 
Mantenha o foco! 
Evite se distrair com 
as redes sociais.
Mantenha o foco! 
Evite se distrair com 
as redes sociais.
Determine um 
horário fixo 
para estudar.
Aproveite as 
indicações 
de Material 
Complementar.
Procure se alimentar e se hidratar quando for estudar; lembre-se de que uma 
Não se esqueça 
de se alimentar 
e de se manter 
hidratado.
Aproveite as 
Conserve seu 
material e local de 
estudos sempre 
organizados.
Procure manter 
contato com seus 
colegas e tutores 
para trocar ideias! 
Isso amplia a 
aprendizagem.
Seja original! 
Nunca plagie 
trabalhos.
UNIDADE Lógica de Predicados
Motivação: a Lógica Proposicional
A lógica proposicional, igualmente conhecida como lógica das proposições, ou ain-
da lógica simbólica, utiliza proposições – ou símbolos lógicos – e conectivos lógicos.
Vejamos algumas características da lógica proposicional:
• Utiliza proposições interligadas por conectivos lógicos – operadores –, mos-
trados a seguir;
• As proposições simples, ou símbolos proposicionais, comumente são letras 
minúsculas, tais como p, q, r, s, t, a, b, c, d;
• Uma proposição lógica simples ou composta é uma afirmativa adequadamente 
formada, que terá um valor verdadeiro ou falso;
• A lógica proposicional tem algumas limitações, que serão superadas na lógica 
de predicados, a saber: estabelecer características para determinados objetos e 
relacionamentos entre objetos.
Assim, em lógica proposicional:
p: Ana é uma mulher.
q: Ana é alta.
r: Ana tem 25 anos.
s: Ana é irmã de Luiz.
Enquanto em lógica de predicados:
mulher(Ana, “alta”, 25)
irmãos(Ana, Luiz)
• As lógicas proposicional e de predicados não permitem ou consideram al-
gum nível de certeza nas afirmações. Por exemplo, p: Ana é alta – em lógica 
proposicional – e alta(Ana) – em lógica de predicados – não fornecem o grau 
de certeza da afirmação. Logo, Ana poderia ter uma altura apenas um pouco 
acima da média das mulheres em determinado universo, ou Ana poderia 
ser consideravelmente alta – o que não fica claro nas proposições lógicas 
utilizadas como fatos.
Quadro 1 – Principais conectivos lógicos
Λ onjunção, operação E
∨ disjunção, operação OU
~ ¬ negação, operação NÃO
→ condicional
↔ bicondicional
8
9
Vejamos descrições mais detalhadas dos principais conectivos empregados nas 
lógicas proposicional e de predicados:
• Λ: conjunção, operação E; por exemplo, p Λ q;
• ∨: disjunção, operação OU; por exemplo, p ∨ q;
• ~: negação, operação NÃO, em alguns textos usa-se ¬; por exemplo, ~q (não q);
• →: condicional; por exemplo, p → q, que significa se p então q;
• ↔: bicondicional; por exemplo, p ↔ q, que significa p se e somente se q;
• ( ): para agrupação de termos (prioridade) e para especificar a lista de parâme-
tros de um predicado;
• ≤ < > ≥ = ≠: operadores de relação (comparação);
• + − / ∗: operadores aritméticos.
Veja, a seguir, dois exemplos de proposições lógicas compostas em lógica pro-
posicional:
a Λ (b ∨ c) → d
(p ∨ ~q) ↔ a
Perceba os símbolos proposicionais a, b, c, d, p, q e os conectivos ou operado-
res lógicos ~ Λ ∨ → ↔.
Lógica de Predicados
A Lógica de Primeira Ordem (LPO), ou lógica de predicados, igualmente conhe-
cida como Cálculo de Predicados de Primeira Ordem (CPPO), ou simplesmente 
cálculo de predicados, é usualmente uma extensão da lógica proposicional.
As possibilidades da lógica de predicados são superiores às da lógica proposicional.
A lógica de predicados é também uma forma de armazenar conhecimento – da-
dos e “regras” para raciocínio lógico ou inferência.
O elemento fundamental da lógica de predicados é o predicado. Podemos 
considerar o predicado como uma função, que poderá ter uma lista de parâme-
tros ou argumentos e que retornará um valor lógico – verdadeiro ou falso. Se 
comparado a funções/métodos de Java, C++ e de outras linguagens de progra-
mação, ou com funções matemáticas, que podem retornar valores numéricos, 
textos etc., um predicado sempre retornará um valor lógico.
Predicados: permitem estabelecer relações entre objetos ou especificar característi-
cas dos objetos. Ex
pl
or
9
UNIDADE Lógica de Predicados
Em lógica de predicados podemos utilizar todos os conectivos lógicos – operadores 
– da lógica proposicional, mas também são permitidos os chamados quantificadores.
A quantificação é uma construção que especifica para quais indivíduos de um 
domínio de discurso se aplica uma proposição lógica. Os quantificadores ∀ e ∃ – 
universal e existencial – são utilizados para esse objetivo, onde:
• ∀x significa para todo o x, para qualquer x, qualquer que seja x; ou seja, 
exprime fatos sobre todos os objetos do universo;
• ∃x significa existe um x, existe algum x, existe pelo menos um x; ou seja, 
exprime fatos sobre objetos particulares.
∀ e ∃ são conhecidos como quantificadores universal e existencial, respectivamente.
A utilização de quantificadores permite melhor descrição da situação que neces-
sitamos representar, isto é, são elementos que ajudam no sentido de melhor com-
preensão do problema.
Convenções Utilizadas para 
a Lógica de Predicados
Na bibliografia desta área podemos encontrar diferentes convenções para es-
crever proposições na lógica ou cálculo de predicados, isto é, para representar as 
constantes, variáveis e nomes de predicados – símbolos de predicados –, mudando 
um pouco de um autor para outro. Inclusive, deve-se observar as características 
específicas de linguagens de programação que utilizem como base teórica a lógica 
de predicados, por exemplo, as considerações obrigatórias em uma linguagem 
como Prolog.
Quadro 2 – Convenções para o cálculo de predicados
Sintaxe do Cálculo de Predicados: Símbolos
Os elementos básicos da sintaxe do cálculo de predicados são símbolos que se referem a 
objetos, relações e funções:
símbolos para constantes, que se referem a objetos, como Aphroditee Zeus;
símbolos para variáveis, que se referem a objetos ou conjunto de objetos, como x, y, z, ...;
símbolos para predicados, que se referem a relações entre objetos, como Irmão, Primo;
símbolos para funções, que se referem a funções de objetos, como Pai, Mãe.
Fonte: adaptado de Sichman e Costa ([20--])
Já em linguagem de programação como Prolog, que utiliza como base a lógica 
ou o cálculo de predicados, a convenção é bem diferente (exemplo a seguir). Ob-
serve que as variáveis devem ser escritas com letra inicial maiúscula. As constantes 
simbólicas – pedro, ana, rosa, java, python, no exemplo – e os nomes de predica-
dos – pessoa, caracteristica, conhece, candidatoVaga, write, no seguinte exemplo 
– serão escritos com letra inicial minúscula.
10
11
Para utilizar uma ortografia correta, poderíamos considerar que a linguagem 
Prolog permite, também, empregar constantes de tipo texto, strings, escrevendo 
o texto entre aspas, vejamos:
característica(“Ana”, “responsável”).
conhece(“Pedro”, “Java”).
conhece(“Pedro”, “Python”).
Exemplo de programa na linguagem de programação Prolog:
pessoa(pedro).
pessoa(ana).
pessoa(rosa).
caracteristica(pedro, honesto).
caracteristica(pedro, responsavel).
caracteristica(ana, honesto).
caracteristica(rosa, responsavel).
conhece(pedro, java)
conhece(pedro, python)
conhece(ana, php)
conhece(rosa, vb6)
candidatoVaga(P) :- caracteristica(P,honesto),
caracteristica(P,responsavel), conhece(P,java),
conhece(P,vbnet).
?-write("Candidatos à vaga:"), candidatoVaga(pr), write(Pr).
Convenção Adotada Nesta Unidade
Utilizaremos a convenção a seguir para escrever proposições na lógica de 
predicados:
• Nomes de predicados (símbolos): utilizaremos letra inicial minúscula;
• Nomes de variáveis: utilizaremos letra inicial minúscula;
• Constantes: como nomes de pessoas, cidades, países: utilizaremos letra ini-
cial maiúscula.
Por exemplo:
capital(p,q)
capital(Espanha, Madri)
mulher(Ana)
11
UNIDADE Lógica de Predicados
Observe que os nomes próprios de pessoas, países e cidades – Espanha, Madri, 
Ana – foram escritos com letras iniciais maiúsculas, enquanto os nomes dos predi-
cados capital e mulher foram escritos com letras iniciais minúsculas e as variáveis 
p,q foram escritas com letras minúsculas.
Veja também que o predicado mulher possui apenas um parâmetro, que é uma 
pessoa – Ana, no exemplo anterior. Neste caso, o predicado mulher estabelece 
uma característica ao argumento Ana – Ana é uma mulher.
Já o predicado capital possui dois parâmetros, ou argumentos, separados por 
uma vírgula. Esse predicado estabelece uma relação entre os seus dois argumen-
tos. Por exemplo, capital (Espanha, Madri) estabelece que Madri é a capital 
do país Espanha.
Em princípio não existe limite para a quantidade de argumentos ou parâmetros 
de um predicado – outro exemplo, utilizaremos agora um predicado capital com 
três parâmetros:
capital(Brasil, Brasília, 2500000)
Que mostra que a capital do país Brasil é Brasília, que possui uma população de 
2.500.000 habitantes.
Os exemplos anteriores permitem observar a superioridade da lógica/cálculo de 
predicados com relação à lógica proposicional, no sentido de nos permitir estabe-
lecer propriedades para objetos individuais e relacionamentos entre os quais.
A lógica de predicados pode ser utilizada como base teórica ao projeto e à im-
plementação de linguagens de programação dentro do paradigma da programa-
ção lógica.
A seguir veremos como seria uma possível representação do exemplo do Qua-
dro 4 (Prolog) utilizando a nossa convenção para a lógica de predicados:
pessoa(Pedro)
pessoa(Ana)
pessoa(Rosa)
caracteristica(Pedro, “honesto”)
caracteristica(Pedro, “responsável”)
caracteristica(Ana, “honesto”)
caracteristica(Rosa, “responsável”)
conhece(Pedro, Java)
12
13
conhece(Pedro, Python)
conhece(Ana, PHP)
∀p: caracteristica(p, “honesto”) ^ caracteristica(p, “responsável”) ^
 conhece(p, Java) ^ conhece(p, Kotlin) → candidatoVaga(p)
Observe que nomes próprios como Pedro, Ana, Java e Python foram escritos 
com letra inicial maiúscula, enquanto constantes como honesto e responsável fo-
ram escritos como textos entre aspas e a variável p foi escrita com letra minúscula.
A proposição lógica da condicional → poderá ser lida como qualquer que seja 
p, se p tiver como característica ser honesto, e p for responsável, e p conhece 
as linguagens de programação Java e Kotlin, então p será candidato à vaga.
No próximo exemplo apresentamos mais um exemplo de lógica de predicados 
utilizando a convenção proposta nesta Unidade.
Fatos como nota(Ana, 5.5) utilizam dois argumentos ou parâmetros, sendo que 
o primeiro é o nome do aluno e o segundo é a sua nota. Este predicado – fato, 
neste caso – estabelece um relacionamento entre Ana e 5.5, sinalizando que Ana 
possui a pontuação 5.5 como nota.
Por sua vez, aprovado(x) indica que a pessoa x está aprovada. Neste caso, o 
predicado aprovado atribui uma característica à pessoa x.
Ademais, utilizaremos três condicionais que nos permitem representar determi-
nado raciocínio lógico, ou seja, partindo de condições chegaremos a uma determi-
nada conclusão:
∀x: ∀n: nota(x, n) ^ n >= 7.0 → aprovado(x)
∀x: ∀n: nota(x, n) ^ n < 7.0 → reprovado(x)
∃x: aprovado(x)
A proposição lógica ∀x: ∀n: nota(x, n) ^ n >= 7.0 → aprovado(x) pode ser 
lida como qualquer que seja x, qualquer que seja n, se o aluno x tem nota 
n, e essa nota n for maior ou igual que 7.0, então o aluno x está aprovado.
Já a proposição lógica ∀x: ∀n: nota(x, n) ^ n < 7.0 → reprovado(x) pode ser 
lida como qualquer que seja x, qualquer que seja n, se o aluno x tem nota n, 
e essa nota n for menor que 7.0, então o aluno x está reprovado. Nas duas 
primeiras proposições lógicas utilizamos o quantificador universal ∀.
Por fim, a proposição lógica ∃x: aprovado(x) poderia ser interpretada como 
existe pelo menos um x, tal que esse aluno x está aprovado. Aqui utilizamos 
o quantificador existencial ∃.
13
UNIDADE Lógica de Predicados
Exemplo de lógica de predicados utilizando a nossa convenção:
Sejam:
nota(Júlio, 9.5)
nota(Ana, 5.5)
nota(Luiz, 7.0)
nota(Betty, 8.0)
∀x: ∀n: nota(x, n) ^ n >= 7.0 → aprovado(x)
∀x: ∀n: nota(x, n) ^ n < 7.0 → reprovado(x)
∃x: aprovado (x)
Um livro onde encontraremos vários exemplos e exercícios sobre lógica de pre-
dicados é Matemática discreta e suas aplicações, de Kenneth Rosen (2010). 
Veja, o exemplo a seguir, um exercício proposto por este autor, que apresentamos 
com uma possível solução – observe que Rosen escreve os nomes dos predicados 
com letras iniciais maiúsculas (R e H, neste caso):
Exercício resolvido (adaptado de Rosen, 2010):
Transcreva estas proposições para o português, em que R(x) é “x é um coelho” 
e H(x) é “x salta” e o domínio são todos os animais.
1. ∀x (R(x) → H(x)) Todo coelho salta. Qualquer que seja x, se x é um coe-
lho, então ele salta.
2. ∀x (R(x) ^ H(x)) Todos os animais são coelhos e saltam.
3. ∃x (R(x) → H(x)) Existe um animal que se é o coelho então ele salta.
4. ∃x (R(x) Λ H(x)) Existe pelo menos um coelho que salta.
Outros exemplos de lógica de predicados presentes no terceiro capítulo – Ló-
gica de predicados de primeira ordem – do livro intitulado Lógica aplicada à 
computação, de Newton José Vieira ([20--]), mostram a utilização de quantifica-
dores, predicados e variáveis – observe que neste caso o autor utiliza nomes de 
predicados com letra inicial minúscula:
Exemplo de lógica de predicados:
∃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)
14
15
∀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)
Para finalizar, veremos alguns exemplos completos, detalhadamente comenta-
dos, utilizando a lógica de predicados com a convenção desta Unidade.
Exemplo 1:
Neste primeiro caso utilizaremos o predicado progenitor, que possui dois parâ-
metros: o primeiro é o nome do(a) progenitor(a) e o segundo argumento é o nome 
do(a) filho(a).
progenitor (Ana, Pedro) Ana é progenitora do Pedro
progenitor (Pedro, Rosa) Pedro é progenitor da Rosa
progenitor (Luiz, Leila) Luiz é progenitor da Leila
...
progenitor (Carlos, Heitor)
homem (Pedro) Pedro é homem
homem(Luiz) Luiz é homem
mulher(Ana) Ana é mulher
mulher(Rosa) Rosa é mulher
∀x: ∀y: progenitor(x,y) ^ mulher (x) → mãe(x,y)
A proposição lógica anterior tem este significado em português: para todo x, 
para todo y, SE x for progenitor de y E x for mulher, ENTÃO x é mãe de y.
∀x: ∀y: progenitor(x,y) ^ homem (x) → pai(x,y)
A proposição lógica anterior teria este significado em português: qualquer que 
seja x, qualquer que seja y, SE x for progenitor de y E x for homem, ENTÃO 
x é pai de y.
Exemplo 2:
Outras proposições lógicas mais complexas poderiam ser elaboradas como con-
tinuação do exemplo anterior. Veja a seguir proposições que definem avô, irmãos, 
primos e tio. Tente fazer uma figura para cada definição, o que lhe permitirá me-
lhor analisar o relacionamento definido:
∀x: ∀y: ∀z: progenitor(x,y) ^ progenitor(y,z) ^ homem (x) → avô(x,z)
∀x: ∀y: ∀z: progenitor(x,y) ^ progenitor(x,z) → irmaos(y,z)
15
UNIDADE Lógica de Predicados
∀x: ∀y: ∀a: ∀b: progenitor(x,y) ^ progenitor(a,b) ^ irmaos(x,a) → primos(y,b)
∀x: ∀a: ∀b: progenitor(a,b) ^ irmaos(a,x) → tio(x,b)
Analisemos a penúltima proposição lógica, que utiliza os predicados progeni-
tor, irmaos e primos. Estamos definindo aqui quando uma pessoa y e outra b são 
primos. A leitura dessa proposição lógica poderia ser: para todo x, para todo y, 
para todo a, para todo b, SE x é progenitor de y E a é progenitor de b, EN-
TÃO y e b são primos.
Exemplo 3:
Com fatos – axiomas – com a seguinte estrutura:
populacao(nome da cidade, população da cidade)
capital (nome do país, nome da cidade)
Por exemplo:
populacao(Campinas, 2000000)
Ou utilizando um texto para a cidade: populacao(“Campinas”, 2000000)
populacao(SaoPaulo, 15000000)
Ou um texto para a cidade: populacao(“São Paulo”, 15000000)
Exemplos de fatos:
populacao(Lima,1500000)
populacao(Brasília, 3000000)
capital(Brasil,Brasilia)
capital(Peru,Lima)
Definamos proposições para inferir:
• cidade grande – que tenha mais de 2.500.000 habitantes:
∀c: ∀h: populacao(c, h) Λ (h > 2500000) → cidadeGrande(c)
• capital importante – com mais de 2.500.000 habitantes
∀c, ∀p: cidadeGrande(c) Λ capital(p, c) → capital_importante(c)
Ou desta forma:
∀c, ∀p, ∀h: capital(p, c) Λ populacao(c, h) Λ h > 2500000 →
capital_importante(c)
16
17
Material Complementar
Indicações para saber mais sobre os assuntos abordados nesta Unidade:
 Livros
Inteligência Artificial
RICH, E.; KNIGHT, K. Inteligência artificial. 2. ed. São Paulo: Mcgraw-Hill do Brasil, 1993.
Inteligência Artificial
RUSSELL, S. J.; NORVIG, P. Inteligência artificial. Rio de Janeiro: Elsevier, 2004.
 Leitura
Noções de Lógica Matemática
Analise o material intitulado Noções de lógica matemática. Leia especificamente a 
convenção utilizada pela autora para representação de nomes de predicados, variáveis 
e constantes.
https://goo.gl/K3YCI
Lógica de Predicados
Finalmente, complemente os seus estudos por meio da leitura do Item 4.2 – Equivalência 
entre sentenças – do material do professor doutor Sílvio do Lago Pereira, intitulado 
Lógica de predicados.
https://goo.gl/bH2ntL
17
UNIDADE Lógica de Predicados
Referências
ABAR, C. A. A. P. Noções de lógica matemática. 2011. Disponível em: <http://
www4.pucsp.br/~logica>. Acesso em: 24 jan. 2019.
ABE, J. M. Introdução à Lógica para a Ciência da Computação. 2. ed. São 
Paulo: Arte Ciência, 2002.
ALENCAR FILHO, E. de. Iniciação à lógica matemática. São Paulo: Nobel, 2006.
BISPO, C. A. Introdução à lógica matemática. São Paulo: Cengage Learning, 2012.
LAGO, S. Lógica de predicados. [20--]. Disponível em: <https://www.ime.usp.
br/~slago/IA-logicaDePredicados.pdf>. Acesso em: 30 jan. 2019.
ROSEN, K. Matemática discreta e suas aplicações. 6. ed. Porto Alegre, RS: 
McGraw Hill, 2010.
SICHMAN, J. S.; COSTA, A. H. Lógica de predicados. [20--]. Disponível em: 
<https://edisciplinas.usp.br/pluginfile.php/385430/mod_resource/content/1/
Aula%209%20-%20Logica%20de%20Predicados.pdf>. Acesso em: 30 jan. 2019.
SOARES, E. Fundamentos de lógica: elementos de lógica formal e teoria da ar-
gumentação. 2. ed. São Paulo: Atlas, 2014.
18