LOGICA DE PRIMEIRA ORDEM Cálculo dos Predicados

J.M.Barreto UFSC-INE

LOGICA DE PRIMEIRA LOGICA DE PRIMEIRA ORDEMORDEM

Cálculo dos PredicadosCálculo dos Predicados

• FUNDAMENTOS DA COMPUTACÃOFUNDAMENTOS DA COMPUTACÃO



O Cálculo das Proposições tem um poder de O Cálculo das Proposições tem um poder de representação limitado.representação limitado.

O Cálculo das Proposições se utiliza apenas sentenças O Cálculo das Proposições se utiliza apenas sentenças completas, isto é, as proposições para representar o completas, isto é, as proposições para representar o conhecimento sobre o Mundo usando constantes.conhecimento sobre o Mundo usando constantes.

A Lógica dos Predicados, ou Cálculo dos Predicados, A Lógica dos Predicados, ou Cálculo dos Predicados, é uma extensão da Lógica das Proposições em que é uma extensão da Lógica das Proposições em que se consideram variáveis e quantificadores sobre as se consideram variáveis e quantificadores sobre as variáveis.variáveis.



O Cálculo dos Predicados se preocupa em O Cálculo dos Predicados se preocupa em introduzir noções lógicas para expressar introduzir noções lógicas para expressar qualquer conjunto de fatos através de Classes qualquer conjunto de fatos através de Classes de Atributos e de Quantificadores. de Atributos e de Quantificadores.

O matemático americano Alonzo Church e o O matemático americano Alonzo Church e o inglês Alan Turing, mostraram inglês Alan Turing, mostraram independentemente, que não há procedimento independentemente, que não há procedimento de decisão para checar a validade de fórmulas de decisão para checar a validade de fórmulas da Lógica dos Predicadosda Lógica dos Predicados..


Cálculo dos PredicadosCálculo dos Predicados• CLASSE DE ATRIBUTOS: São representados pelos substantivos comuns, locuções CLASSE DE ATRIBUTOS: São representados pelos substantivos comuns, locuções

nominais, adjetivos, locuções adjetivas, verbos e locuções verbais.nominais, adjetivos, locuções adjetivas, verbos e locuções verbais.

Exemplo: Exemplo:

Sócrates é um Homem.Sócrates é um Homem. S é HS é H

Todo Homem é Mortal.Todo Homem é Mortal. Todo H é MTodo H é M

Logo, Sócrates é Mortal.Logo, Sócrates é Mortal. S é MS é M

Este exemplo é frequentemente apresentado como um silogismo de Aristóteles. Este exemplo é frequentemente apresentado como um silogismo de Aristóteles. Note-se que isto está completamente errado, Aristóteles tendo trabalhado Note-se que isto está completamente errado, Aristóteles tendo trabalhado sempre com variáveis.sempre com variáveis.



QUANTIFICADORES:QUANTIFICADORES: São São operadores lógicos, mas em vez de operadores lógicos, mas em vez de indicarem relações entre sentenças, indicarem relações entre sentenças, eles expressam relações entre eles expressam relações entre conjuntos designados pelas classes de conjuntos designados pelas classes de atributos, isto é, expressam atributos, isto é, expressam propriedades de coleções de objetos, propriedades de coleções de objetos, evitando que tenhamos de enumerar evitando que tenhamos de enumerar cada objeto individualmente como na cada objeto individualmente como na Lógica ProposicionalLógica Proposicional..


Cálculo dos PredicadosCálculo dos Predicados• Sintaxe do Cálculo de PredicadosSintaxe do Cálculo de Predicados

<fórmula>::= <fórmula-atômica> | <fórmula-complexa><fórmula>::= <fórmula-atômica> | <fórmula-complexa>

<fórmula-atômica>::= <predicado>(<termo,...) | <termo>=<termo><fórmula-atômica>::= <predicado>(<termo,...) | <termo>=<termo>

<termo>::=<função>(<termo>,...) | <constante>| <variável><termo>::=<função>(<termo>,...) | <constante>| <variável>

<fórmula-complexa>::= (<fórmula>) <fórmula-complexa>::= (<fórmula>)

| <fórmula> <conectivo> <fórmula >| <fórmula> <conectivo> <fórmula >

| | <fórmula> <fórmula>

| <quantificador><variavél>... <fórmula>| <quantificador><variavél>... <fórmula>

<conectivo>::= <conectivo>::= | | | | | |

<quantificador>::= <quantificador>::= | |

<constante>::=A | X1 | João | ...<constante>::=A | X1 | João | ...

<variável>::= x | y | z | ...<variável>::= x | y | z | ...

<predicado>::= Antes | Irmão | Cor | Mortal | ...<predicado>::= Antes | Irmão | Cor | Mortal | ...

<função>::= Mãede | PernaEsquerda | ...<função>::= Mãede | PernaEsquerda | ...



• Nota: A definição apresentada na página anterior é Nota: A definição apresentada na página anterior é clássica, entretanto cabe ressaltar que é possível clássica, entretanto cabe ressaltar que é possível usar:usar:

• <fórmula-atômica>::= (<predicado><termo) <fórmula-atômica>::= (<predicado><termo)

<termo>::=(<função><termo>,...) | <constante>| <variável><termo>::=(<função><termo>,...) | <constante>| <variável>

<fórmula-complexa>::= (<fórmula>) <fórmula-complexa>::= (<fórmula>)

| (<conectivo> <fórmula> <fórmula >)| (<conectivo> <fórmula> <fórmula >)

| (| ( <fórmula>) <fórmula>)

| (<quantificador><variavél>... <fórmula>)| (<quantificador><variavél>... <fórmula>)


Cálculo dos PredicadosCálculo dos Predicados• QuantificadoresQuantificadores

– A Lógica dos Predicados contém dois quantificadores, chamados UNIVERSAL e EXISTENCIAL.A Lógica dos Predicados contém dois quantificadores, chamados UNIVERSAL e EXISTENCIAL.

– QUANTIFICADOR UNIVERSAL (QUANTIFICADOR UNIVERSAL () Este tipo de quantificador é formado pelas expressões “para ) Este tipo de quantificador é formado pelas expressões “para todo”, “todo”.todo”, “todo”.

Exemplo: Exemplo: • Todo gato é mamífero. Ou seja,Todo gato é mamífero. Ou seja,• Qualquer que seja x, se x for um gato, então x é mamífero. Ou ainda,Qualquer que seja x, se x for um gato, então x é mamífero. Ou ainda,• Para todo x, se x for um gato, então x é mamífero.Para todo x, se x for um gato, então x é mamífero.

x Gato(x)x Gato(x)Mamífero(x)Mamífero(x)

Gato(Miau) Gato(Miau) Mamífero(Miau) ^Mamífero(Miau) ^

Gato(Felix) Gato(Felix) Mamífero(Felix) ^Mamífero(Felix) ^

Gato(Priscila) Gato(Priscila) Mamífero(Priscila) ^Mamífero(Priscila) ^

Gato(Ricardo) Gato(Ricardo) Mamífero(Ricardo) ^Mamífero(Ricardo) ^

......


Lógicas dos PredicadosLógicas dos Predicados• QuantificadoresQuantificadores

– QUANTIFICADOR EXISTENCIAL (QUANTIFICADOR EXISTENCIAL () Este tipo de quantificador é formado pelas ) Este tipo de quantificador é formado pelas expressões “algum”, “pelo menos um”.expressões “algum”, “pelo menos um”.

Exemplo: Exemplo: • Existe algum político honesto. Ou seja,Existe algum político honesto. Ou seja,• Para pelo menos um x, x é um político e x é honesto. Ou ainda,Para pelo menos um x, x é um político e x é honesto. Ou ainda,

x Político(x)^Honesto(x)x Político(x)^Honesto(x)

Político(João) ^ Honesto(João) VPolítico(João) ^ Honesto(João) V

Político(José) ^ Honesto(José) VPolítico(José) ^ Honesto(José) V

Político(Fulano) ^ Honesto(Fulano) VPolítico(Fulano) ^ Honesto(Fulano) V

Político(Siclano) ^ Honesto(Siclano) VPolítico(Siclano) ^ Honesto(Siclano) V

......


Cálculo dos PredicadosCálculo dos Predicados• Quantificadores AninhadosQuantificadores Aninhados

– Eventualmente desejamos expressar sentenças mais complexas com múltiplos quantificadores.Eventualmente desejamos expressar sentenças mais complexas com múltiplos quantificadores.

Exemplos: Exemplos: • Para todo x e todo y, se x é pai de y, então y é filho de x.Para todo x e todo y, se x é pai de y, então y é filho de x.

x,y Pai(x,y) x,y Pai(x,y) Filho(y,x) Filho(y,x)• Bob ama Cathy.Bob ama Cathy.

Ama(Bob, Cathy)Ama(Bob, Cathy)• Todo mundo ama Cathy.Todo mundo ama Cathy.

x Ama(x, Cathy)x Ama(x, Cathy)• Todo mundo ama alguém.Todo mundo ama alguém.

x x y Ama(x,y) y Ama(x,y)• Existe alguém que ama a todos.Existe alguém que ama a todos.

x x y Ama(x,y)y Ama(x,y)• Existe alguém que é amada por todos.Existe alguém que é amada por todos.

y y x Ama(x,y)x Ama(x,y)

– A ordem dos quantificadores é importante!A ordem dos quantificadores é importante!


Cálculo dos PredicadosCálculo dos Predicados• Igualdade ou IdentidadeIgualdade ou Identidade

– É um símbolo que se adiciona ao Çálculo de Predicados com o É um símbolo que se adiciona ao Çálculo de Predicados com o propósito de expressar o fato de dois termos se referirem ao mesmo propósito de expressar o fato de dois termos se referirem ao mesmo objeto, ou seja, “é idêntico a” ou “é a mesma coisa que”. objeto, ou seja, “é idêntico a” ou “é a mesma coisa que”.

Exemplos: Exemplos: • O Pai de João é Henrique.O Pai de João é Henrique.

Pai_de(João)= HenriquePai_de(João)= Henrique

Pai de João e Henrique se referem ao mesmo objeto.Pai de João e Henrique se referem ao mesmo objeto.• O Pai de João é também Avô de Pedro.O Pai de João é também Avô de Pedro.

Pai_de(João) = Avô_de(Pedro)Pai_de(João) = Avô_de(Pedro)


Cálculo dos PredicadosCálculo dos Predicados• Equivalência de QuantificadoresEquivalência de Quantificadores

– Os dois quantificadores estão intimamente relacionados entre si através da negação.Os dois quantificadores estão intimamente relacionados entre si através da negação.

Exemplo: Exemplo: • Ninguém gosta de pagar impostos.Ninguém gosta de pagar impostos.

x x GostarPagar(x,Impostos) GostarPagar(x,Impostos) x GostarPagar(x,Impostos) x GostarPagar(x,Impostos)

– Como Como é na verdade uma conjunção sobre o universo de objetos e o é na verdade uma conjunção sobre o universo de objetos e o é uma disjunção, não é é uma disjunção, não é surpreendente que eles obedeçam as Lei de De Morgan. surpreendente que eles obedeçam as Lei de De Morgan.

x x P P x P x P P ^ P ^ Q Q (P V Q) (P V Q)

x P x P x x P P (P ^ Q) (P ^ Q) P V P V Q Q

x P x P x x P P P ^ Q P ^ Q ( ( P V P V Q) Q)

x P x P x x P P P V Q P V Q ( ( P ^ P ^ Q) Q)


Cálculo dos PredicadosCálculo dos Predicados• Regras de InferênciaRegras de Inferência

– Todas as regras de inferência definidas na Lógica Todas as regras de inferência definidas na Lógica Proposicional são válidas para a Lógica de Predicados, Proposicional são válidas para a Lógica de Predicados, apenas referenciando-as para os quantificadores. apenas referenciando-as para os quantificadores.


Cálculo dos PredicadosCálculo dos Predicados• Regras de Inferência envolvendo QuantificadoresRegras de Inferência envolvendo Quantificadores








Cálculo dos PredicadosCálculo dos Predicados• Árvores de RefutaçãoÁrvores de Refutação

– São uma generalização da técnica utilizada na Lógica Proposicional.São uma generalização da técnica utilizada na Lógica Proposicional.

– A técnica de árvore de refutação generalizada incorpora as regras da lógica A técnica de árvore de refutação generalizada incorpora as regras da lógica proposicional e acrescenta 6 novas regras para inferir em sentenças que proposicional e acrescenta 6 novas regras para inferir em sentenças que contém quantificadores e o predicado de identidade.contém quantificadores e o predicado de identidade.

– Algumas árvores do cálculo dos predicados empregam somente as regras Algumas árvores do cálculo dos predicados empregam somente as regras do cálculo proposicional. do cálculo proposicional.

– NO CÁLCULO DE PREDICADOS, AS ÁRVORES DE REFUTAÇÃO NO CÁLCULO DE PREDICADOS, AS ÁRVORES DE REFUTAÇÃO NÃO APRESENTAM UMA LISTA COMPLETA DE CONTRA-NÃO APRESENTAM UMA LISTA COMPLETA DE CONTRA-EXEMPLOS, MAS SIM, UM “MODELO DE UNIVERSO” QUE EXEMPLOS, MAS SIM, UM “MODELO DE UNIVERSO” QUE CONTÉM EXATAMENTE OS OBJETOS MENCIONADOS PELO CONTÉM EXATAMENTE OS OBJETOS MENCIONADOS PELO NOME NO RAMO.NOME NO RAMO.


Cálculo dos PredicadosCálculo dos Predicados• Árvores de RefutaçãoÁrvores de Refutação

x P(x) x G(x), x G(x) x P(x)

1. x P(x) x G(x)

2. x G(x)

3. x P(x)

A árvore de refutação está COMPLETA,

isto é, com todos os ramos fechados,

logo, a busca de uma refutação para o

argumento de negar a conclusão falhou,

pois só encontrou CONTRADIÇÕES, e

portanto, a FORMA É VÁLIDA.

4. x P(x) 1 x G(x) 1

5. X 3,4 X 2,4


Cálculo dos PredicadosCálculo dos Predicados• Regras para Árvore de Refutação do Cálculo de PredicadosRegras para Árvore de Refutação do Cálculo de Predicados

– 1. Quantificação Universal (1. Quantificação Universal (): ): • Se uma fórmula bem formada do tipo Se uma fórmula bem formada do tipo ß Ø aparece num ramo aberto e se ß Ø aparece num ramo aberto e se é uma é uma

constante (ou letra nominal) que ocorre numa fbf naquele ramo, então ESCREVE-constante (ou letra nominal) que ocorre numa fbf naquele ramo, então ESCREVE-SE ØSE Ø / ß (o resultado de se substituir todas as ocorrências ß em Ø por / ß (o resultado de se substituir todas as ocorrências ß em Ø por ) no final do ) no final do ramo.ramo.

• Se nehuma fbf contendo uma letra nominal aparece no ramo, então escolhemos uma Se nehuma fbf contendo uma letra nominal aparece no ramo, então escolhemos uma letra nominal letra nominal e ESCREVE-SE Ø e ESCREVE-SE Ø / ß no final do ramo. / ß no final do ramo.

• Em cada caso, NÃO TICAMOS Em cada caso, NÃO TICAMOS ß Ø. ß Ø.


Cálculo dos PredicadosCálculo dos Predicados• Regras para Árvore de Refutação do Cálculo de Regras para Árvore de Refutação do Cálculo de

PredicadosPredicadosx (P(x) G(x)), x P(x) G(a)

1. x (P(x) G(x))

2. x P(x)

3. G(a)

4. P(a) G(a) 15. P(a) 2

6. P(a) 4 G(a) 4

7. X 5,6 X 3,6









PredicadosPredicados– 2. Quantificação Existencial Negada (2. Quantificação Existencial Negada ( ): ):

• Se uma fórmula bem formada não ticada da forma Se uma fórmula bem formada não ticada da forma ßØ ßØ aparece num ramo aberto, tica-se a fórmula e ESCREVE-SE aparece num ramo aberto, tica-se a fórmula e ESCREVE-SE ßß Ø no final de cada ramo aberto que contém a fbf ticada. Ø no final de cada ramo aberto que contém a fbf ticada.

x (P(x) G(x)), G(x) P(a)

1. x (P(x) G(x))

2. G(x)

3. P(a)

4. x G(x) 2 5. G(a) 46. P(a) G(a) 1

7. P(a) 6 G(a) 6

8. X 3,7 X 5,7









PredicadosPredicados– 3. Quantificação Universal Negada (3. Quantificação Universal Negada ( ): ):

• Se uma fórmula bem formada não ticada da forma Se uma fórmula bem formada não ticada da forma ßØ ßØ aparece num ramo aberto, tica-se a fórmula e ESCREVE-SE aparece num ramo aberto, tica-se a fórmula e ESCREVE-SE ßß Ø no final de cada ramo aberto que contém a fbf ticada. Ø no final de cada ramo aberto que contém a fbf ticada.

x (y P(x,y))

1. x (y P(x,y))

2. x (y P(y,x))

3. y P(a,y) 1 4. x ( y P(y,x)) 2 5. y P(y,b) 4 6. y P(y,b) 5 7. P(a,b) 6 8. P(a,b) 3 9. X 7,8

x (y P(y,x))

A fórmula testada é válida



PredicadosPredicados– 4. Quantificação Existencial (4. Quantificação Existencial (): ):

• Se uma fórmula bem formada não ticada da forma Se uma fórmula bem formada não ticada da forma ßØ aparece ßØ aparece num ramo aberto, tica-se a fórmula e escolhe-se uma letra nominal num ramo aberto, tica-se a fórmula e escolhe-se uma letra nominal QUE NÃO APARECEU NAQUELE RAMO e ESCREVE-SE QUE NÃO APARECEU NAQUELE RAMO e ESCREVE-SE ØØ / ß (o resultado de se substituir todas as ocorrências ß em Ø por / ß (o resultado de se substituir todas as ocorrências ß em Ø por ) no final do ramo.) no final do ramo.

x P(x)

1. x P(x)

2. x P(x)

3. P(a) 1 4. x P(x) 2 5. P(b) 4

x P(x)

A fórmula testada é INVÁLIDA POR HAVER RAMOS ABERTOS (linha 5)


Cálculo dos PredicadosCálculo dos Predicados• Regras para Árvore de Refutação do Cálculo de PredicadosRegras para Árvore de Refutação do Cálculo de Predicados

– 5. Identidade (=): 5. Identidade (=): • Se uma fórmula do tipo Se uma fórmula do tipo = ß aparece num ramo aberto e se uma outra = ß aparece num ramo aberto e se uma outra

fbf Ø contendo fbf Ø contendo ou ß aparece não ticada naquele ramo, então ou ß aparece não ticada naquele ramo, então escrevemos no final do ramo qualquer fbf que não esteja no ramo, que é escrevemos no final do ramo qualquer fbf que não esteja no ramo, que é o resultado de se substituir uma ou mais ocorrências de qualquer uma o resultado de se substituir uma ou mais ocorrências de qualquer uma dessas letras nominais pela outra em Ø.dessas letras nominais pela outra em Ø.

• Não se tica Não se tica = ß nem Ø. = ß nem Ø.

a = b

1. a = b

2. (P(a,b) P(b,a))

3. (P(a,a) P(a,a)) 1,2 =

4. P(a,a) 3 5. P(a,a) 3 6. X 4,5

P(a,b) P(b,a)




PredicadosPredicados– 5. Identidade Negada (5. Identidade Negada (=): =):

• Fechamos qualquer ramo aberto no qual uma fbf do tipo Fechamos qualquer ramo aberto no qual uma fbf do tipo = = ocorra. ocorra.

a = b

1. a = b

2. b = a

3. a = a 1,2 =

4. X 3 =

b = a



Dúvidas?Dúvidas?

Documents

LOGICA DE PRIMEIRA ORDEM Cálculo dos Predicados