Lógica de Predicados (§1.3) - DEINF/UFMA - …paiva/cursos/edlm/slides/2Logica_Parte2.pdf · lPodemos usar lógica proposicional para provar que certas inferências são válidas

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.



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’





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.


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.




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


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.




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.


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”.




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.”


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.




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


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




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.


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.”




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.


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




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


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.




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)


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)




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


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.]




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.



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.





∀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



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




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)?


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)




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))


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)




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.


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??




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?


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




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.


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))




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


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))




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))


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




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”


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




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”?


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))




l Pode a Lógica de Predicados afirmar:

Existe pelo menos dois objetos com a propriedade P?


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)




l Pode a lógica de predicados afirmar que:lExistem exatamente dois objetos com

a propriedade P


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 ))




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?


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




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”


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) ∨ …




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)


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




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


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.




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.


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




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)


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.




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


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.




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.”)


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.”)




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]


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))




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))


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.”




Exemplo de Cálculo

( )

( ) ( )

<−→<−

∀>∃>∀

⇔=→

εδδε

|)(|||::0:0

)(lim

Lxfaxx

Lxfax

l Maneira de definir precisamente o conceito de limite usandoquantificadores:

Documents

Lógica de Predicados (§1.3) - DEINF/UFMA - …paiva/cursos/edlm/slides/2Logica_Parte2.pdf · lPodemos usar lógica proposicional para provar que certas inferências são válidas