BCC101
Matemática Discreta I
Lógica de Predicados
1
O que é um Predicado?
Predicado
 Coleção parametrizada de proposições
 Exemplos:
 P(x): x é par
 D(x,y): x é divisível por y
 Tipicamente uma proposição diferente
para cada x
 P(2)
 D(10,5)
é True
é True
P(5)
é False
D(20,3) é False
 Domínio (ou universo de discurso)
 Conjunto de valores que as variáveis podem assumir
 Deve ser especificado explicitamente
2
Conjunto verdade de um Predicado
Seja P(x) um predicado
e suponha que P(x) tem domínio D
O conjunto verdade de P(x) é o
conjunto dos xD tais que P(x) é True
{ x D | P(x) }
Exemplo
P(x): 5<x<9 e D=Z
{ x D | P(x)} = {6,7,8}
3
 — Quantificador Universal, (para todo)
x p(x)
 É uma fórmula se p(x) é uma fórmula
 True se p(x) é True para cada valor de x no Domínio
 False se existe algum valor de x no Domínio tal que
p(x) é False
Exemplo – P(x): x é primo
 D = {2,5,11}
- x P(x) é True
x P(x) significa P(2)  P(5)  P(11)
 D = {3,6,9}
- x P(x) é False
Contra-exemplos: P(6) e P(9)
 D = N = {0, 1, 2, … } - x P(x) é False
x P(x) significa P(0)  P(1)  P(2)  …
“” provê uma maneira de escrever fórmulas que teriam
um número infinito de símbolos na Lógica Proposicional
4
 — Quantificador Existencial, (existe)
x p(x)
 É uma fórmula se p(x) é uma fórmula
 True se p(x) é True para algum valor de x no Domínio
 False p(x) é False para todo valor de x no Domínio
Exemplo – P(x): x é primo
 D = {3,6,9}
- x P(x) é True
x P(x) significa P(3)  P(6)  P(9)
 D = {6,9,15,28}
- x P(x) é False
x P(x) significa P(6)  P(9)  P(15)  P(28)
 D = N = {0, 1, 2, … } - x P(x) é True
x P(x) significa P(0)  P(1)  P(2)  …
“” provê uma maneira de escrever fórmulas que teriam
um número infinito de símbolos na Lógica Proposicional
5
Universo Vazio
 Qual o significado de x p(x) se o
universo de discurso é vazio?
 x p(x) é True
 Isso é compatível com o fato de que o  é uma
generalização do ∧ e a identidade do ∧ é true.
 Qual o significado de ∃x p(x) se o
universo de discurso é vazio?
 ∃x p(x) é False
 Isso é compatível com o fato de que o ∃ é uma
generalização do ∨ e a identidade do ∨ é false.
6
Exercício
Seja P(x): x == x2 e suponha que o universo é o
conjunto dos números inteiros. Qual é o valor
verdade de cada uma das afirmações a seguir:





P(0)
P(1)
P(2)
P(-1)
P(y)





x P(x)
x P(x)
x P(x)
x P(x)
x P(x)
7
Fórmulas com vários quantificadores
Seja N o domínio de discurso
N = {0, 1, 2, 3, … }
e se R (x,y ) = “x < y”.
Q1: O que significa x y R (x,y ) ?
 Todo número x admite um número maior y
 Verdadeiro ou falso?
Q2: O que significa y x R (x,y ) ?
 Algum número y é maior que todo x
 Verdadeiro ou falso?
8
Fórmulas com vários quantificadores
 x.y. p(x,y) é True se p(x,y) é True para todo
par (x,y) em DxD

Exemplo (D = N): xy y=x+1 -> x < y é True
 x. y. p(x,y) é True se, para cada x∈D, é
possível escolher um y∈D tal que p(x,y) é True

Exemplos (D = N): x y y ≥ x é True
 y.x. p(x,y) é True se existe um determinado
y∈D, tal que p(x,y) é True, para todo x∈D

Exemplo (D = N): y x y ≥ x é False
 y. x. p(x,y) é True se existe um par (x,y) ∈
DxD tal que p(x,y) é True
 Exemplo(D = N): y x y ≥ x é True
9
Exercícios
 Seja Q(x,y): x+y == x-y e suponha que o universo é
o conjunto dos números inteiros. Qual é o valor
verdade de cada uma das afirmações a seguir:






Q(1,1)
Q(2,0)
y Q(1,y)
x Q(x,2)
y Q(2,y)
x Q(x,y)





x y Q(x,y)
x y Q(x,y)
x y Q(x,y)
y x Q(x,y)
y x Q(x,y)
10
Lógica de Predicados – sintaxe formal
termo ::= var | func (termo1, …, termon) n ≥ 0
Termos denotam
objetos do
Domínio
Fórmulas denotam
valores lógicos (T
ou F)
formula ::= true | false
|pred (termo1, …, termon) n
≥0
|(¬ formula)
|(formula ∧ formula)
|(formula ∨ formula)
|(formula -> formula)
Precedência dos operadores
|(formula <-> formula)      

|(var. formula)
11
Lógica de Predicados - semântica
 Termos denotam objetos do domínio
Termos
2
constantes
variáveis
funções
aplicadas
a termos
Domínio = N
x
5
2
5
y
x+2
(y+1)2
3
6
4
49
12
Lógica de Predicados - semântica
 Fórmulas denotam valores lógicos
A interpretação
depende dos
valores de x e y
-- x e y são
variáveis livres
x=3, y=6
Fórmulas
Bool
T ou F?
x>y
T
(x > y) -> (y+1 = 3)
x x=3
F
x x+3=2y
A interpretação não
depende do valor de x!
-- x é uma variável ligada
A interpretação não depende do valor de x,
mas depende do valor de y!
-- x é uma variável ligada e y é livre
13
Variáveis livres e ligadas
$x(x + y =1)
variável ligada
variável livre
$xP(x)ÙQ(x)Ú"xR(x)
escopo de
x
escopo de
x
($xP(x))ÙQ(x)
ocorrência ligada
escopo de x
14
ocorrência livre
Traduzindo para Lógica de Predicados
G(x,y): x gosta de y
1. João gosta de Maria
G(João,Maria)
2. João gosta de todo mundo
y G(João,y)
3. Todo mundo gosta de João
x G(x,João)
4. Maria gosta de alguém
y G(Maria,y)
5. Maria não gosta de ninguém
¬y G(Maria,y)
6. Todo mundo gosta de alguém
x y G(x,y)
7. Ninguém gosta de todo mundo x y ¬G(x,y)
8. João gosta de todo mundo de quem Maria não
gosta
y ¬G(Maria,y)→G(João,y)
15
Exercícios
Traduza as seguintes sentenças para a
Lógica de Predicados:
1. Todo número par maior que 2 é a soma
de 2 primos
∀x (par(x) ∧ x>2 → ∃y∃z (primo(y) ∧ primo(z) ∧ x=y+z))
1. Em toda cidade existe uma rua que tem
pelo menos 1 buraco
∀x (Cidade(x) → ∃y∃b (Rua(y) ∧ Inr(R,b) ∧Buraco(b) ∧
Inb(R,b)))
16