Aula 11 - Introdução à Lógica de Predicados

Prévia do material em texto

Prof. Ricardo Mesquita 
Lógica de Predicados 
Quantificadores 
 Quantificadores são operadores lógicos aplicados a uma 
variável e a uma expressão. 
 Os quantificadores foram definidos para capturar conceitos 
da linguagem natural como: 
Para todo mundo ... 
Não tem ninguém aqui que ... 
Todos aqui ... 
Tem alguém que poderia ... 
Qualquer um que ... 
Existe pelo menos um de nós ... 
02/28 
Quantificadores 
 No caso da lógica de predicados somente são considerados 
dois tipos de afirmações sobre vários elementos de um 
domínio: 
Afirmações universais, que devem ser válidas para todos os 
elementos de um domínio; 
Afirmações existenciais, que devem ser válidas para pelo menos 
um dos elementos do domínio. 
03/28 
Quantificadores 
 Para cada um destes tipos de afirmações, corresponde um 
diferente tipo de quantificador: 
Quantificador universal, para representar as afirmações 
universais. 
Quantificador existencial, para representar as afirmações 
existenciais. 
04/28 
Quantificadores 
 Quantificador Universal 
é usado para representar as afirmações universais, que no 
Português são expressas por orações similares a: 
Para todo mundo ... 
Todos aqui ... 
Qualquer um que ... 
Representação: 
 (∀x ∈ A)(P(x)) 
Lê-se: Para todo x ∈ A, P(x) é verdadeira 
05/28 
Quantificadores 
 Quantificador Universal 
Quando o domínio é conhecido, usamos apenas 
 ∀xP(x) 
Exemplo: 
Considere a sentença: “Todo aluno de Lógica é dedicado.” 
Assuma que A = conjunto dos alunos de Lógica 
Escrevemos: (x  A)(dedicado(x)) ou (x)(dedicado(x)) 
ou ainda, x dedicado(x). 
 
06/28 
Quantificadores 
 Quantificador Existencial 
O quantificador existencial é usado para representar as afirmações 
existenciais, que no Português são expressas por orações similares 
a: 
Tem alguém que poderia ... 
Para algum destes ... 
Existe pelo menos um de nós ... 
Representação: 
 (x  A)(P(x)) 
Lê-se: Existe pelo menos um x em A que torna P(x) 
verdadeiro 
07/28 
Quantificadores 
 Quantificador Existencial 
Exemplo 
Considere a sentença: “Na turma de Lógica, há aqueles que 
praticam esportes.” 
Note que nesta sentença, temos a ideia de que, na turma de 
lógica, existem alunos que praticam esportes... Ou seja, 
pelo menos um aluno da turma pratica esportes. 
Se A = conjunto de alunos de lógica, 
(x  A)(atleta(x)), ou, simplesmente, (x)(atleta(x)), ou 
ainda, x atleta(x). 
 
08/28 
Quantificadores 
 Sendo R o conjunto dos números reais, determinar o valor 
lógico das seguintes expressões: 
(∀x ∈ R) (|x| = x) 
(∃x ∈ R) (x2 = x) 
(∃x ∈ R) (|x| = 0) 
(∃x ∈ R) (x + 2 = x) 
(∀x ∈ R) (x + 1 > x) 
(∀x ∈ R) (x2 = x) 
09/28 
Quantificadores 
 Sendo R o conjunto dos números reais, determinar o valor 
lógico das seguintes expressões: 
(∀x ∈ R) (|x| = x) F 
(∃x ∈ R) (x2 = x) V 
(∃x ∈ R) (|x| = 0) V 
(∃x ∈ R) (x + 2 = x) F 
(∀x ∈ R) (x + 1 > x) V 
(∀x ∈ R) (x2 = x) F 
10/28 
Lógica de Predicados 
 Definição: Alfabeto 
 O alfabeto da Lógica de Predicados é constituído por: 
 símbolos de pontuação: 
( , ) 
 símbolos de verdade: 
True, false 
um conjunto enumerável de símbolos para variáveis: 
 x, y, z, w, x1,y1,... 
 
11/28 
Lógica de Predicados 
 Definição: Alfabeto 
um conjunto enumerável de símbolos para funções: 
f, g, h, f1, g1, h1, f2, g2, ... ; 
um conjunto enumerável de símbolos para predicados: 
p, q, r, p1, q1, r1, p2, q2, ... ; 
Conectivos e quantificadores: 
, , , , , ,  
 
 
12/28 
Lógica de Predicados 
 Observação: 
Associado a cada símbolo para função ou predicado, temos um número 
inteiro não-negativo k. Esse número indica a aridade, ou seja, o número 
de argumentos da função ou predicado. 
Exemplos: 
 bonita(x)  predicado de aridade 1 
 amigo(x, y)  predicado de aridade 2 
 soma(a, b)  função de aridade 2 
 
13/28 
Lógica de Predicados 
 Noções de Predicados e Funções: 
 Predicados: 
 Todo homem é mortal. 
 Seja H o conjunto dos homens. Então, 
 (x  H)(mortal(x)) 
 mortal é um predicado. 
 Funções: 
 soma(x, y) = x + y. 
 Note que soma retorna um valor que não pode ser avaliado como verdadeiro ou 
falso. 
14/28 
Lógica de Predicados 
 Definição: Termo 
 O conjunto dos termos da linguagem da Lógica de 
Predicados é o menor conjunto que satisfaz as regras a 
seguir: 
as variáveis são termos; 
se t1, t2, ..., tn são termos e f
 é um símbolo para função n-ária, 
então f(t1, t2, ..., tn) é um termo. 
 
15/28 
Lógica de Predicados 
 Definição: Átomo 
 O conjunto dos átomos da linguagem da Lógica de 
Predicados é o menor conjunto que satisfaz as regras a 
seguir: 
os símbolos de verdade true e false são átomos; 
se t1, t2, ..., tn são termos e p é um símbolo para predicado n-
ário, então, p(t1, t2, ..., tn) é um átomo. 
 
16/28 
Lógica de Predicados 
 Definição: Fórmula 
 O conjunto das fórmulas da linguagem da Lógica de 
Predicados é o menor conjunto que satisfaz as regras a 
seguir. 
Todo átomo é uma fórmula. 
Se H é uma fórmula, então (H) é uma fórmula. 
Se H e G são fórmulas, e * é um conectivo da lógica, então 
(H * G) é uma fórmula. 
Se H é uma fórmula e x é uma variável, então 
 (∀x)(H(x)) e (∃x)(H(x)) são fórmulas. 
 
 
17/28 
Lógica de Predicados 
 Definição: Expressão 
 Uma expressão da Lógica de Predicados é um termo ou 
uma fórmula. 
 
18/28 
Lógica de Predicados 
 Definição: Subtermo, Subfórmula, Subexpressão 
 Os elementos a seguir definem as partes de um termo ou fórmula 
E. 
Se E = x, então a variável x é um subtermo de E 
Se E = f(t1, t2, ..., tn), então ti e f(t1, t2, ..., tn) são subtermos de 
E. 
Se t1 é subtermo de t2 e t2 é subtermo de E, então t1 é subtermo 
de E. 
Se E =(H), então H e ( H) são subfórmulas de E. 
Se E é uma das fórmulas (H  G), (H  G), (H  G) ou (H  
G), então H, G e E são subfórmulas de E. 
 
 19/28 
Lógica de Predicados 
 Definição: Subtermo, Subfórmula, Subexpressão 
Se x é uma variável, e  é um dos quantificadores  ou  e 
E = ( x)(H(x)), então H e ( x)(H(x)) são subfórmulas de E. 
Se H1 é subfórmula de H2 e H2 é subfórmula de E, então H1 é 
subfórmula de E. 
Todo subtermo ou subfórmula é também uma subexpressão. 
 
20/28 
Lógica de Predicados 
 Definição: Literal 
 
 Um literal, na Lógica de Predicados, é um átomo ou a 
negação de um átomo. 
 
 Um átomo é um literal positivo. 
 
 A negação de um átomo é um literal negativo. 
 
21/28 
Lógica de Predicados 
 Ordem de precedência: 
maior precedência: ; 
precedência intermediária superior:  , ; 
precedência intermediária inferior: , ; 
precedência inferior: , . 
 
 
22/28 
Lógica de Predicados 
 Correspondência entre quantificadores: 
x(H(x))  x(H(x)) 
x(H(x))  x(H(x)) 
 
Negação: 
(x(H(x)))  x(H(x)) 
(x(H(x)))  x(H(x)) 
 
 
23/28 
Lógica de Predicados 
 Classificação de variáveis: 
Uma ocorrência de x em E é ligada se x está no escopo de um 
quantificador (∀x) ou (∃x) em E. 
Uma ocorrência de x em E é livre se não for ligada. 
Mas: 
 A variável x é ligada em E se existe pelo menos uma ocorrência ligada de 
x em E. 
 A variável x é livre em E se existe pelo menos uma ocorrência livre de x 
em E. 
 
24/28 
Lógica de Predicados 
 Símbolos livres: 
Dada uma fórmula E, os seus símbolos livres são as variáveis que 
ocorrem livres em E, os símbolos de função e os símbolos de 
predicado. 
 
 Fórmula fechada: 
Uma fórmula é fechada quando não possui variáveis livres. 
 
25/28 
Lógica de Predicados 
 Fecho de uma fórmula 
 Seja H uma fórmula da Lógica de Predicados e 
{x1, ..., xn} 
 o conjunto das variáveis livres em H. 
 O fecho universal de H, indicado por (∀∗)H, é dado pela 
fórmula 
(∀x1)...(∀xn)H. 
O fecho existencial de H, indicado por (∃∗)H, é dado pela 
fórmula 
 (∃x1)...(∃xn)H. 
 
26/28 
Exercícios 
1. Seja I uma interpretação sobre o conjunto dos naturais N, tal 
que I[a] = 5, I[b] = 3, I[x] = 7, I[p(x)] = V  xI < 9, I[r(x)] = V 
 xI > 4, I[q(x)] = V  xI = 7. Determine o resultado da 
interpretação das fórmulas a seguir segundo I: 
a. (x(p(x)  x(r(x)))  ((x(p(x))  x(r(x))) 
b. (x(p(x)  x(p(a)))  (p(x)  x(p(b))) 
c. (p(x)  q(x))  x(p(x)  q(x)) 
 
27/28 
Exercícios 
2. Quais os resultados informais das interpretações de H1, H2 e H3, 
onde I é uma interpretação sobre o conjunto dos números 
inteiros Z, tal que 
I[a] = 0, I[q(x, y)] = V  xI < yI , I[p(x)] = V  xI é um número 
primo, I[r] = “=” (r é a igualdade), I[f] = * (f é o produto). 
a. H1 = x y (q(x, y)  p(y)) 
b. H2 = x (q(a, y)  z (r(f(z, z), x))) 
c. H3 = x y (r(x, a)  z (r(f(x, z), y))) 
28/28