View
216
Download
0
Category
Preview:
Citation preview
Discrete Math - Module #0 - Overview 9/2/2005
(c)2001-2003, Michael P. Frank 1
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 64
Lógica de Predicados (§1.3)
l Podemos usar lógica proposicional paraprovar que certas inferências sãoválidas. Por exemplo,l Se está frio então vai nevar. Assim:l Se não nevar então não está frio
l Em lógica proposicional (fácil de verificar):l c → s. Então ¬s → ¬c.
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 65
Lógica de Predicados (§1.3)
l Mas algumas inferências não podem se provadas pela lógica proposicionall Algumas garotas são adoradas por todo
mundo. Então:l Todo mundo adora alguém
l Para inferências como esta, precisamosde uma lógica mais expressival Tratamento para `algum’ e `todo’
Discrete Math - Module #0 - Overview 9/2/2005
(c)2001-2003, Michael P. Frank 2
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 66
Lógica de Predicados (§1.3)
l Lógica de Predicados é uma extensãoda lógica proposicional que permitequantificação em classes de entidades.
l Lógica Propositional trata proposiçõessimples (sentenças) como entidadesatômicas.
l Por outro lado, lógica de predicadosdistingue o sujeito de uma sentença do seu predicado.
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 67
Lógica de Predicados - Aplicações
Uma das mais usadas notações formaispara escrever definições, axiomas e teoremas matemáticos.
Por exemplo, em álgebra linear, umaordem parcial é introduzida dizendo queuma relação R é reflexiva e transitiva – e estas noções são definidas usandológica de predicados.
Discrete Math - Module #0 - Overview 9/2/2005
(c)2001-2003, Michael P. Frank 3
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 68
Lógica de Predicados - Aplicações
l Base para provadores automáticos de teoremas e muitos sétemas de IA.l E.g. verificação automática de programas.
l Setenças parecidas com a lógica de predicados são suportadas por algumasarquiteturas de consultas a Banco de Dados
l Mas existem problemas no uso destalógica
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 69
Primeiro: Um pouco de gramática
l Na sentença “O cão está dormindo”:l O sujeito da sentença é : “o cão”.l O predicado é: “está dormindo”
l Uma propriedade do sujeito
l Lógica de predicados segue o mesmopadrão.
Discrete Math - Module #0 - Overview 9/2/2005
(c)2001-2003, Michael P. Frank 4
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 70
Fórmulas da Lógica de Predicados
l Constantes que identificam indivíduos ouobjetos: a,b,c,…
l variáveis individuais sobre objetos: x, y, z , …
l O resultado da aplicação de um predicado P a uma constante a é a proposição P(a)Significando: o objeto denotado por a possui a propriedade denotada por P.
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 71
Fórmulas da Lógica de Predicados(informal)
l O resultado da aplicação do predicado Pà variável x é a proposição P(x).
l E.g. se P = “é um número primo”, entãoP(x) é a forma proposicional de “x é um número primo”.
Discrete Math - Module #0 - Overview 9/2/2005
(c)2001-2003, Michael P. Frank 5
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 72
Predicados/relações com n argumentosl Lógica de predicados generaliza a noção de
predicado para permitir a inclusão de funçõesde qualquer número de argumentos. E.g., usando variáveis:l Seja R(x,y,) = “x ama y”, então se
x = “Mário”, y = “Maria” entãoR(x,y) = “Márioa ama Maria”
l Seja P(x,y,z) = “x deu a y a nota z”, então sex=“Mário”, y = “Maria”, z=“10”, então P(x,y,z) = “Mário deu a a Maria a nota 10.”
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 73
Universo de Discurso (U.D.s)
l A força da distinção de objetos com predicados reside no fato de podermos afirmarcoéas sobre vários objetos de uma única vez.
l E.g., Seja P(x)=“x*2≥x”. Podemos dizer,“Para qualquer número x, P(x) é true” e não
(0*2 ≥ 0) ∧ (1*2 ≥ 1) ∧ (2*2 ≥ 2) ∧ ...
l A coleção de valores que a variável x podeassumir é denominado universo de discurso de x.
Discrete Math - Module #0 - Overview 9/2/2005
(c)2001-2003, Michael P. Frank 6
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 74
Universo de Discurso (U.D.s)
l E.g., seja P(x)=“x*2 ≥ x”.
l “Para qualquer número x, P(x) é true” é true quando U.D. = N
l “Para qualquer número x, P(x) é true” é false quando U.D. = Z
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 75
Expressões com Quantificadores
lQuantificadores fornecem uma notaçãoque permite quantificar (contar) quantos objetos no U.D. satisfazem um dado predicado.l “∀” é o quantificador universal Para
todos.l “∃” é o quantificador existencial, Existe um
lPor exemplo, ∀x P(x) e ∃x P(x) sãoproposições
Discrete Math - Module #0 - Overview 9/2/2005
(c)2001-2003, Michael P. Frank 7
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 76
Significado de Expressões com Quantificadores
Primeiro informalmente:
l ∀x P(x) significa para todo x no U.D., Pse aplica.
l ∃x P(x) significa existe um x no U.D. (que é, 1 ou mais) tal que P(x) é true.
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 77
Exemplo: ∃
Seja x com U.D. estacionamentos do Brazil, e P(x) a propr. “x está cheio.”Então o quantificador existencial de P(x), ∃x P(x), é a proposição dizendo quel “Algum estacionamento no Brasil está
cheio.”l “Existe um estacionamento no Brazil está
cheio.”l “Ao menos um estacionamento no Brazil
está cheio.”
Discrete Math - Module #0 - Overview 9/2/2005
(c)2001-2003, Michael P. Frank 8
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 78
Exemplo: ∀
Seja x com U.D. estacionamentos do Brazil, e P(x) a propr. “x está ocupado.”O quantificador universal de P(x), ∀xP(x), é a proposição:l “Todos os estacionamentos do Brazil estão
ocupados.”l “Para cada estacionamento do Brazil, o espaço
está ocupado.”l Etc.
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 79
Consequências da Posição Padrão
Duas equivalências lógicas da Lógica de Predicados:
∀x P(x) ⇔ ¬∃x ¬P(x)∃x P(x) ⇔ ¬∀x ¬P(x)
Abordamos isto novamente depois
Discrete Math - Module #0 - Overview 9/2/2005
(c)2001-2003, Michael P. Frank 9
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 80
Mesma Situação em LógicaProposicional
Valor verdade de p → q quando p é Falso:F T TF T F
Podemos dizer que: se p é falso então nãoé válido dizer que “p implica q”
Ao invés disso, simplesmente dizemosque “p implica q” é True neste caso
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 81
Variáveis livres e restritas
l Diz-se que uma expressão como P(x) teuma variável livre x (significa que x éindefinida).
l Um quantificador (∀ ou ∃) opera em umaexpressão possuindo uma ou maisvariáveis livres, e restringe uma ou maisdessas variáveis, para produzir umaexpressão que possua uma ou maisvariáveis restritas.
Discrete Math - Module #0 - Overview 9/2/2005
(c)2001-2003, Michael P. Frank 10
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 82
Exemplo de Restrição
l P(x,y) possui 2 variáveis livres, x e y.l ∀x P(x,y) possui 1 variável livre e uma
variável restrita. [Qual?]l Uma expressão com zero variáveis livres
é uma proposição.l Uma expressão com uma ou mais
variáveis livres é similar a um predicado: e.g. Seja Q(y) = ∀x Adora(x,y)
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 83
Aninhamento de Quantificadores
Exemplo: Seja o u.d. de x e y pessoas.Seja L(x,y)=“x parece y” (predicado com 2
VL)Então ∃y L(x,y) = “Existe alguem que se
parece com x.” (predicado com 1 VL, x)E ∀x (∃y L(x,y)) = “Todo mundo tem
alguém parecido”.”(proposição; sem variáveis livres)
Discrete Math - Module #0 - Overview 9/2/2005
(c)2001-2003, Michael P. Frank 11
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 84
Mais Sobre Restrições
l ∀x ∃x P(x) - x não é uma VL em∃x P(x), assim a restrição ∀x não estásendo usada.
l (∀x P(x)) ∧ Q(x) - x está fora do escopode ∀x, sendo portanto uma VL. Não éuma proposição completa!
l (∀x P(x)) ∧ (∃x Q(x)) – proposiçãocompleta sem quantificadores superflúos
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 85
LN é ambiguo!
l “Todo mundo gosta de alguém.”l Para todo mundo, existe um alguém que
ele(a) gosta,l ∀x ∃y Likes(x,y)
l ou, existe alguem que gosta dele(a)?l ∃y ∀x Likes(x,y)
l Depende do contexto, da ênfase nafrase
[Probably more likely.]
Discrete Math - Module #0 - Overview 9/2/2005
(c)2001-2003, Michael P. Frank 12
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 86
Sintaxe da Lógica de Predicados(Predicados com 1 ou 2 variáveis)
l Variável: x,y,z,… Constantes: a,b,c,…l Predicados de uma variável: P,Q,…l Predicados de duas variáveis: R,S,…l Fórmulas atômicas:
Se α é um predicado de uma variável e β éuma variável ou constante, então α (β) é umafórmula atômica.Se α é um predicado de duas variáveis e β e γ são variáveis ou constantes, então α (β,γ) éuma fórmula atômica.
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 87
Sintaxe da Lógica de Predicados(Predicados com 1 ou 2 variáveis)
Fórmulas:
l Toda fórmula atômica é uma fórmula
l Se α e β são fórmulas então ¬α,(α ∧β), (α∨β), (α →β) são fórmulas.
l Se ϕ é uma fórmula então ∀x ϕ e ∃y ϕsão fórmulas.
Discrete Math - Module #0 - Overview 9/2/2005
(c)2001-2003, Michael P. Frank 13
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 88
Sintaxe da Lógica de Predicados(Predicados com 1 ou 2 variáveis)
∀xP(x) ∃yQ(x) ∀x∃y R(x,y) ∀xP(b)
l P(x) é uma fórmula atômica, então ∀xP(x) é umafórmula
l Q(x) é uma fórmula atômica, então ∃yQ(x) é umafórmula
l R(x,y) é uma fórmula atômica, então ∃y R(x,y) é umafórmula, então ∀x∃y R(x,y) é uma fórmula
l P(b) é uma fórmula atômica, então ∀xP(b) é umafórmula
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 89
Sintaxe da Lógica de Predicados(Predicados com 1 ou 2 variáveis)
l Exemplos: ∀xP(x) e ∃yQ(x),∀x(∃y R(x,y)), ∀x(∃x R(x,y)), ∀xP(b) etc.
l Alguns casos patológicos. Por exemplo,l ∀xP(b) é True sss P(b) é Truel um quantificador que não restringe
nenhuma variável pode ser ignorado
Discrete Math - Module #0 - Overview 9/2/2005
(c)2001-2003, Michael P. Frank 14
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 90
Considere ∀xP(a)
l Relembrando a definição:Seja ϕ uma fórmula. Então ∀xϕ é True se em
D cada expressão ϕ(x:=a) é True em D, e False de outra maneira.
l ∀xP(b) é True em D se cada expressãoda forma P(b)(x:=a) é True em D, falsade outra maneira.
l Qual é o conjunto de todas as expressões da forma P(b)(x:=a)?
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 91
Considere ∀xP(a)
l Qual é o conjunto de todas as expressões da forma P(b)(x:=a)?l O conjunto {P(b)} !,
l ∀xP(b) é True em D se P(b) é True, e False otherwise.
l Assim, ∀xP(b) significa P(b)
Discrete Math - Module #0 - Overview 9/2/2005
(c)2001-2003, Michael P. Frank 15
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 92
Algumas formas resumidas
l As vezes o U.D. é restrito dentro do quantificador, e.g.,l ∀x>0 P(x) é uma forma resumida para
“Para todo x maior que zero então, P(x).”=∀x (x>0 → P(x))
l ∃x>0 P(x) é uma forma resumida para“Existe um x maior que zero tal que P(x).”=∃x (x>0 ∧ P(x))
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 93
Algumas formas resumidas
l Quantificadores consecutivos do mesmotipo podem ser combinados:
∀xyz P(x,y,z) ⇔def ∀x ∀y ∀z P(x,y,z)
∃xyz P(x,y,z) ⇔def ∃ x ∃ y ∃ z P(x,y,z)
Discrete Math - Module #0 - Overview 9/2/2005
(c)2001-2003, Michael P. Frank 16
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 94
Avaliação de Quantificadores: Jogo
l Jogo para ajudar a definir quando uma proposiçãocomo quantificadores aninhados é True.
l Dois jogadores, ambos com mesmo conhecimento:l Verificador: quer demonstrar que a proposição é True.l Falsificador: quer demonstrar que a proposição é False.
l Regras:l Leia os quantificadores da esquerda para a direita atribuindo
os valores das variáveis.l Quando encontrar “∀”, o falsificador pode escolher o valor.l Quando encontrar “∃”, o verificador pode escolher o valor.
l Se o verificador sempre ganha, a proposição é True.l Se o falsificador sempre ganha, a proposição é False.
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 95
Exemplo!!!!
Seja B(x,y) [aniversário de “y” acontece até um mês após o aniversário de “x”]
Suponha que : ∀x ∃y B(x,y)
∃y B(so-and-so,y)
• E se eu mudar os quantificadores∃y ∀x B(x,y)?
Quem ganha??
Discrete Math - Module #0 - Overview 9/2/2005
(c)2001-2003, Michael P. Frank 17
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 96
Leis de Equivalência de Quantificadores
l Expandindo quantificadores: u.d.=a,b,c,…∀x P(x) ⇔ P(a) ∧ P(b) ∧ P(c) ∧ …∃x P(x) ⇔ P(a) ∨ P(b) ∨ P(c) ∨ …
l Assim podemos provar que:∀x P(x) ⇔ ¬∃x ¬P(x)∃x P(x) ⇔ ¬∀x ¬P(x)
l Quais equivalências posso usar paraprovar isso?
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 97
Lembrete
l Em lógica proposicional podiamos apenasconstruir fórmulas com tamanho finito.
l E.g., podemos escreverP(a) ∧ P(b) P(a) ∧ P(b) ∧ P(c) P(a) ∧ P(b) ∧ P(c) ∧ P(d) , etc.
l Mas não conseguimos escrever que todos osnúmeros naturais tem uma certa propriedadeP
Discrete Math - Module #0 - Overview 9/2/2005
(c)2001-2003, Michael P. Frank 18
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 98
l Em lógica de predicados podemosafirmar isto facilmente:∀xP(x)
l Mas ainda gostariamos de ter lógicaproposicional podendo escreverfórmulas de comprimento infinito.
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 99
Mais Leis de Equivalência
l ∀x ∀y P(x,y) ⇔ ∀y ∀x P(x,y)∃x ∃y P(x,y) ⇔ ∃y ∃x P(x,y)
l ∀x (P(x) ∧ Q(x)) ⇔ (∀x P(x)) ∧ (∀x Q(x))∃x (P(x) ∨ Q(x)) ⇔ (∃x P(x)) ∨ (∃x Q(x))
l Que tal esta?∃x (P(x) ∧ Q(x)) ⇔ (∃x P(x)) ∧ (∃x Q(x))
Discrete Math - Module #0 - Overview 9/2/2005
(c)2001-2003, Michael P. Frank 19
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 100
Mais Leis de Equivalência
l Que tal esta?
∃x (P(x) ∧ Q(x)) ⇔ (∃x P(x)) ∧ (∃x Q(x)) ?
l Esta equivalência é falsa.l Contra exemplo:
P(x): aniversário de x é 30 de AbrilQ(x): aniversário de x é 1 de agosto
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 101
Interações entre quantificadores e conectivos
Seja u.d. estacionamentos no Brasil.Seja P(x) “x está ocupado.”Seja Q(x) “x está gratuito.”1. ∃x (Q(x) ∧ P(x))2. ∀x (Q(x) ∧ P(x)) 3. ∀x (Q(x) →P(x))4. ∃x (Q(x) → P(x))
Discrete Math - Module #0 - Overview 9/2/2005
(c)2001-2003, Michael P. Frank 20
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 102
I. Construa frases em LN
Seja u.d. estacionamentos no Brasil.Seja P(x) “x está ocupado.”Seja Q(x) “x está gratuito.”1. ∃x (Q(x) ∧ P(x))2. ∀x (Q(x) ∧ P(x)) 3. ∀x (Q(x) →P(x))4. ∃x (Q(x) → P(x))
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 103
I. Construa frases em LN
1. ∃x (Q(x) ∧ P(x)) Alguns estac.sãogratuitos e estão ocupados
2. ∀x (Q(x) ∧ P(x)) Todos os estac. sãogratiutos e estão ocupados
3. ∀x (Q(x) →P(x)) Todos os estac. gratuitosestão ocupados
4. ∃x (Q(x) → P(x)) Para alguns estac. x. Se x é gratuito então está ocupado
Discrete Math - Module #0 - Overview 9/2/2005
(c)2001-2003, Michael P. Frank 21
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 104
Teoremas sobre a Lógica
l Estamos estudando a linguagem e oscálculos da lógica para entende-la melhor
l Lógicos estudam a lógica para entendersuas limitações
l Meta-teoremas podem dizer coisascomo “… isto não pode ser expresso emlógica de predicados”
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 105
Teoremas sobre a Lógica
l Podemos questionar sobre a lógica de predicadosl Que coisas ela pode expressar?l Quantos conectivos eu preciso?
l Sobre a lógica de predicados, os lógicosfazem questões similaresl Esses dois quantificadores são suficientes para
dizer qualquer coisas?l Estas são questões sobre o poder de
expressão da lógica de predicados
Discrete Math - Module #0 - Overview 9/2/2005
(c)2001-2003, Michael P. Frank 22
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 106
Exemplo 1
l Quantificadores são usados paraexpressar que um predicado é True paraum certo número de objetos.
l Exemplo: Pode a lógica de predicadosexpressar: “Existe exatamente um objetocom a propriedade P”?
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 107
Exemplo 1
∃x (P(x) ∧ ¬∃y (P(y) ∧ y≠ x))“Existe um x tal que P(x), onde naãoexista um y tal que P(y) e y é diferentede x.”
Definimos ∃!x P(x) para significar isto:
∃!x P(x) ⇔def∃x (P(x) ∧ ¬∃y (P(y) ∧ y≠ x))
Discrete Math - Module #0 - Overview 9/2/2005
(c)2001-2003, Michael P. Frank 23
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 108
l Pode a Lógica de Predicados afirmar:
Existe pelo menos dois objetos com a propriedade P?
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 109
l Pode a Lógica de Predicados afirmar:l Existe pelo menos dois objetos com a
propriedade P?
l Sim, isto é fácil:
∃x ∃y (P(x) ∧ P(y) ∧ x≠ y)
Discrete Math - Module #0 - Overview 9/2/2005
(c)2001-2003, Michael P. Frank 24
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 110
l Pode a lógica de predicados afirmar que:lExistem exatamente dois objetos com
a propriedade P
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 111
l Pode a lógica de predicados afirmar que:lExistem exatamente dois objetos com
a propriedade Pl Sim
∃x ∃y (P(x) ∧ P(y) ∧ x≠ y ∧∀z (P(z) → (z= x ∨ z= y ))
Discrete Math - Module #0 - Overview 9/2/2005
(c)2001-2003, Michael P. Frank 25
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 112
O que está errado?
l ∃x ∃y (P(x) ∧ P(y) ∧ x≠ y) ∧∀z (P(z) → (z= x ∨ z= y ))como uma fórmula de exatamente dois?
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 113
O que está errado?
l ∃x ∃y (P(x) ∧ P(y) ∧ x≠ y) ∧∀z (P(z) → (z= x ∨ z= y ))como uma fórmula de exatamente dois?
l Esta é uma conjunção de duasproposições separadas. Como resultadodisso, x e y não estão restritas, assimisto nem é uma proposição
Discrete Math - Module #0 - Overview 9/2/2005
(c)2001-2003, Michael P. Frank 26
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 114
l Pode a lógica de predicados afirmar que“Existem infinitos objetos com a propriedadeP”?
l Não! Isto vem do Teorema da Compacidade: “Um conjunto infinito S de modelos pode ser descrito por p sss cada subconjunto finito de S pode ser descrito por p”
l Similarmente, não podemos expressar “Existeum número finitos de objetos com a propriedade P”
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 115
l Similarmente, não podemos expressar“Existe um número finitos de objetoscom a propriedade P”
l A não ser que permitamos conjunçõesinfinitas:
∃!x P(x) ∨ ∃2!x P(x) ∨ ∃3!x P(x) ∨ …
Discrete Math - Module #0 - Overview 9/2/2005
(c)2001-2003, Michael P. Frank 27
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 116
l Pode a lógica de predicados dizer “a maioria dos objetos possui a propriedade P”?
l Não! (Isto vem do teorema daCompacidade. De novo, a menos quepossamos escrever disjunções infinitas)
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 117
Decidibilidade
l Mostramos duas maneiras de mostrarequivalências lógicas:
1. Tabelas Verdade ( pode ser feito de maneira automática:algoritmo)
2. Leis de equivalência (precisa de criatividade)
l Termo técnico: checar a equivalência na lógicaproposicional é decidível
Discrete Math - Module #0 - Overview 9/2/2005
(c)2001-2003, Michael P. Frank 28
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 118
Decidibilidade
l checar a equivalência na lógicaproposicional é decidível
l checar a equivalência na lógica de predicados não é decidívell Ebora a prova de teoremas seja uma arte
(para computadores e humanos) l Alguns “fragmentos” da lógica de
predicados é decidível. Uma aplicação: PROLOG
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 119
Bonus : Programação em Lógica
l Existe LPs inteiramente baseada na lógica de predicados!
l A mais famosa é Prolog.l Um programa Prolog é um conjunto de proposições
(“fatos”) e (“regras”) em lógica de predicados.l A entrada ao programa é uma proposiçào de consulta.
l Que queremos saber se é True ou False.
l O interpretador Prolog realiza algumas deduçõesautomáticas para determinar quando a perguntasegue dos fatos.
Discrete Math - Module #0 - Overview 9/2/2005
(c)2001-2003, Michael P. Frank 29
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 120
Fatos em Prolog
l Representa uma proposição simples, não composta em lógica dos predicados.l e.g., “Joao gosta de Maria”
l Pode ser escrito Gosta(Joao,Maria) em lógicade predicados.
l Pode ser escrito gosta(joao,maria). Em n Prolog!l Símbolos em letra minúscula deve ser usado para
constantes e predicados, maiúsculas reservadas paranomes de variáveis.
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 121
Regras em Prolog
l Uma regra em Prolog representa um proposição com quantificador universalcom a seguinte forma geral
∀x: [∃y P(x,y)]? Q(x),onde x e y deve ser variáveis compostasx=(z,w) e P,Q proposições compostas.
l Em Prolog, isto é escrito como uma regra: q(X) :- p(X,Y).
i.e., os quantificadores ∀,∃ são implícitos.l Exemplo: likable(X) :- likes(Y,X).
? Variables must be capitalized
Discrete Math - Module #0 - Overview 9/2/2005
(c)2001-2003, Michael P. Frank 30
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 122
Conjunção e Disjunção
l Conjunção lógica é codificada usandotermos separados por vírgulas em umaregra.
l Disjunção lógica é escrita usando regrasmúltiplas.
l E.g., ∀x [(P(x)∧Q(x))∨R(x)]? S(x)pode ser escrito em Prolog como:s(X) :- p(X),q(X)s(X) :- r(X)
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 123
Dedução em Prolog
l Quando uma pergunta é entrada para o interpretador Prolog, l Ele busca em sua base de dados se a
mesma pode ser definida como True a partir dos fatos já definidos.
l Caso positivo retorna True, se não, retornaFalse (!)
l Se a pergunta possui variáveis, todos osvalores que a tornam True são impressos.
Discrete Math - Module #0 - Overview 9/2/2005
(c)2001-2003, Michael P. Frank 31
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 124
Programa Prolog Exemplo
l Exemplo:gosta(joao,maria).gosta(maria,fred).gosta(fred,maria).segostam(X) :- gosta(Y,X).
l Pergunta:? segostam(Z)retorna: maria fred
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 125
Relação entrePROLOG e Lógica de Predicados
l PROLOG não pode usar todas as fórmulas da lógica de predicados. (somente cobre um fragmento.)
l Usa a negação como falhal Com essas limitações a dedução
baseada no odelo Prolog é decidível.
Discrete Math - Module #0 - Overview 9/2/2005
(c)2001-2003, Michael P. Frank 32
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 126
Exemplo de Dedução
l Definições: H(x) := “x é humano”; M(x) := “x é mortal”; G(x) := “x é um deus”
l Premissas:l ∀x H(x) → M(x) (“Humanos são mortais”) andl ∀x G(x) → ¬M(x) (“Deuses são imortais”).
l Mostre que ¬∃x (H(x) ∧ G(x))(“Nenhum humano é deus.”)
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 127
Prova Semântica
∀x H(x) → M(x) (“Humanos são mortais”) and
∀x G(x) → ¬M(x) (“Deuses são imortais”).Suponha ∃x (H(x) ∧ G(x)). Por exemplo,H(a) ∧ G(a). EntãoPela primeira premissa temos M(x).Pela segunda premissa temos ¬M(x).Contradição! Então segue que¬∃x (H(x) ∧ G(x)) (“Nenhum humano é
Deus.”)
Discrete Math - Module #0 - Overview 9/2/2005
(c)2001-2003, Michael P. Frank 33
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 128
Prova usando equivalências
l ∀x H(x)→M(x) and ∀x G(x)→¬M(x).l ∀x ¬M(x)→¬H(x) [Contrapositiva.]l ∀x [G(x)→¬M(x)] ∧ [¬M(x)→¬H(x)]l ∀x G(x)→¬H(x) [Transitividade →]l ∀x ¬G(x) ∨ ¬H(x) [Definição →.]l ∀x ¬(G(x) ∧ H(x)) [DeMorgan.]l ¬∃x G(x) ∧ H(x) [lei de equivalência]
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 129
Exemplos: Teoria dos Números
Seja u.d. = os números naturais 0, 1, 2, …
O que significa ?
l ∀x (E(x) ↔ (∃y x=2y))
l ∀x (P(x) ↔(x>1 ∧ ¬∃yz x=yz ∧ y≠1 ∧ z≠1))
Discrete Math - Module #0 - Overview 9/2/2005
(c)2001-2003, Michael P. Frank 34
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 130
Exemplos: Teoria dos Números
Seja u.d. = os números naturais 0, 1, 2, …l “Um número é par, E(x), sss ele é igual
a 2 vezes outronúmero.”∀x (E(x) ↔ (∃y x=2y))
l “Um número é primo, P(x), sss é maiorque 1 e não é o produto de doisnúmeros diferentes de 1.”∀x (P(x) ↔ (x>1 ∧ ¬∃yz x=yz ∧ y≠1 ∧z≠1))
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 131
Conjectura de Goldbach’s(não provada)
Usando E(x) e P(x) slide anterior,∀x( [x>2 ∧ E(x)] ?
∃p ∃q P(p) ∧ P(q) ∧ p+q = x).
“Todo número maior que dois é a soma de dois números primos.”
Discrete Math - Module #0 - Overview 9/2/2005
(c)2001-2003, Michael P. Frank 35
9/2/2005 Prof.Anselmo Paiva - DEINF/UFMA 132
Exemplo de Cálculo
( )
( ) ( )
<−→<−
∀>∃>∀
⇔=→
εδδε
|)(|||::0:0
)(lim
Lxfaxx
Lxfax
l Maneira de definir precisamente o conceito de limite usandoquantificadores:
Recommended