J. M. Barreto UFSC-INE Lógica de Primeira Órdem R ecordação

J. M. Barreto UFSC-INE

Lógica de Primeira Órdem

RRecordaçãoecordação


Introdução e HistóricoIntrodução e Histórico• HistóricoHistórico

– Teoria da Resolução de Robinson - 1965. Transforma a expressão a ser Teoria da Resolução de Robinson - 1965. Transforma a expressão a ser provada para a forma normal conjuntiva ou forma clausal. Existe uma regra provada para a forma normal conjuntiva ou forma clausal. Existe uma regra de inferência única, chamada regra da resolução.Utiliza um algoritmo de de inferência única, chamada regra da resolução.Utiliza um algoritmo de casamento de padrões chamado algoritmo de unificação.casamento de padrões chamado algoritmo de unificação.

– Base para a Linguagem Prolog.Base para a Linguagem Prolog.– Recentemente Lógicas Não-Padrão ou Não-Clássicas tem sido cada vez mais Recentemente Lógicas Não-Padrão ou Não-Clássicas tem sido cada vez mais

utilizadas, não somente em IA. Lógica Temporal tem sido utilizada em utilizadas, não somente em IA. Lógica Temporal tem sido utilizada em estudos de programas concorrentes. estudos de programas concorrentes.

– Em IA estas lógicas vem sendo usadas para tratamento de imprecisão, Em IA estas lógicas vem sendo usadas para tratamento de imprecisão, informações incompletas e evolução com o tempo em que evolui o programa informações incompletas e evolução com o tempo em que evolui o programa de IA.de IA.


Lógicas das ProposiçõesLógicas das Proposições• Sintaxe das ProposiçõesSintaxe das Proposições

<fórmula>::= <fórmula-atômica> | <fórmula-complexa><fórmula>::= <fórmula-atômica> | <fórmula-complexa><fórmula-atômica>::= Verdadeiro | Falso | P | Q <fórmula-atômica>::= Verdadeiro | Falso | P | Q | R | ...| R | ...<fórmula-complexa>::= (<fórmula>) <fórmula-complexa>::= (<fórmula>) | <fórmula> <conectivo> <fórmula >| <fórmula> <conectivo> <fórmula >| | <fórmula> <fórmula><conectivo>::= <conectivo>::= | | | | | |

Hoje é segunda ou terça-feira.Hoje é segunda ou terça-feira.Hoje não é terça-feira.Hoje não é terça-feira.Logo, Hoje é segunda-feira.Logo, Hoje é segunda-feira.

S V T, S V T, T T S S


Cálculo das ProposiçõesCálculo das Proposições• Semântica da Lógica ProposicionalSemântica da Lógica Proposicional

– A semântica é definida especificando a interpretação dos A semântica é definida especificando a interpretação dos símbolos da proposição e especificando o significado dos símbolos da proposição e especificando o significado dos conectivos lógicos.conectivos lógicos.

P Q P P Q P V Q P Q P Q

V V F V V V V

V F F F V F FF V V F V V F

F F V F F V V


Cálculo das ProposiçõesCálculo das Proposições• Tabelas VerdadeTabelas Verdade

– Elas fornecem um teste rigoroso e completo para a validade ou invalidade de Elas fornecem um teste rigoroso e completo para a validade ou invalidade de formas de argumento da lógica proposicional, além de se constituir em um formas de argumento da lógica proposicional, além de se constituir em um algoritmo. Quando existe um algoritmo que determina se as formas de argumento algoritmo. Quando existe um algoritmo que determina se as formas de argumento expressáveis em um sistema formal são válidas ou não, esse sistema é dito expressáveis em um sistema formal são válidas ou não, esse sistema é dito DECIDÍVEL. Desta forma, elas garantem a decidibilidade da lógica proposicional.DECIDÍVEL. Desta forma, elas garantem a decidibilidade da lógica proposicional.

– Uma forma de argumento é válida se e somente se todas as suas instâncias são Uma forma de argumento é válida se e somente se todas as suas instâncias são válidas.válidas.

– Uma instância de uma forma é válida se é ímpossível que a sua conclusão seja falsa Uma instância de uma forma é válida se é ímpossível que a sua conclusão seja falsa enquanto as suas premissas são verdadeiras.enquanto as suas premissas são verdadeiras.

– Se a forma for válida, então qualquer instância dela deve ser igualmente válida. Daí Se a forma for válida, então qualquer instância dela deve ser igualmente válida. Daí podemos utilizar a Tabela-Verdade para estabelecer a validade não só de podemos utilizar a Tabela-Verdade para estabelecer a validade não só de argumentos, mas também de argumentos específicos.argumentos, mas também de argumentos específicos.


Cálculo das ProposiçõesCálculo das Proposições• Tabelas Verdade para Formas de ArgumentoTabelas Verdade para Formas de Argumento

– Tabelas-Verdade podem ser usadas, não apenas para definir a Tabelas-Verdade podem ser usadas, não apenas para definir a semântica do conectivos, mas também para testar a validade de semântica do conectivos, mas também para testar a validade de sentenças.sentenças.

– A Rainha ou a Princesa comparecerá à cerimônia.A Rainha ou a Princesa comparecerá à cerimônia.– A Princesa não comparecerá.A Princesa não comparecerá.– Logo, a Rainha comparecerá.Logo, a Rainha comparecerá.R V P, R V P, P P R R

P R P P V R

V V F V

V F F VF V V V

F F V F

R

V

FV

F


Cálculo das ProposiçõesCálculo das Proposições• Regras de InferênciaRegras de Inferência

– Sejam as fórmulas f1, f2, ..., fn (n>=1) e C. Então, toda afirmação de que uma Sejam as fórmulas f1, f2, ..., fn (n>=1) e C. Então, toda afirmação de que uma determinada seqüência finita de fórmulas tem como conseqüência final C, determinada seqüência finita de fórmulas tem como conseqüência final C, chama-se REGRA DE INFERÊNCIA.chama-se REGRA DE INFERÊNCIA.

– São regras hipotéticas ou não, que geram formas de argumento em uma série de São regras hipotéticas ou não, que geram formas de argumento em uma série de etapas simples e precisas de raciocínio, chamadas de DERIVAÇÃO ou PROVA.etapas simples e precisas de raciocínio, chamadas de DERIVAÇÃO ou PROVA.

– Um ARGUMENTO é uma seqüência de enunciados no qual um deles é a Um ARGUMENTO é uma seqüência de enunciados no qual um deles é a CONCLUSÃO e os demais são as PREMISSAS que servem para provar ou, pelo CONCLUSÃO e os demais são as PREMISSAS que servem para provar ou, pelo menos, fornecer algumas evidências para a conclusão.menos, fornecer algumas evidências para a conclusão.

– Evita o trabalho tedioso de ficar construindo Tabelas-Verdade.Evita o trabalho tedioso de ficar construindo Tabelas-Verdade. |- |- significa que significa que pode ser derivado de pode ser derivado de através do processo de inferência, através do processo de inferência,

onde onde e e são fórmulas bem formadas. são fórmulas bem formadas.


Lógicas das ProposiçõesLógicas das Proposições• Regras de InferênciaRegras de Inferência

– REGRAS BÁSICASREGRAS BÁSICAS


Cálculo das ProposiçõesCálculo das Proposições












Lógicas das ProposiçõesLógicas das Proposições



– REGRAS DERIVADASREGRAS DERIVADAS









– ExemploExemplo““Se há um jogo de futebol na Ressacada, então viajar de avião Se há um jogo de futebol na Ressacada, então viajar de avião

é difícil.”é difícil.”““Se eles chegarem no horário no aeroporto, então a viagem de Se eles chegarem no horário no aeroporto, então a viagem de

avião não será difícil.”avião não será difícil.”““Eles, chegaram no horário.”Eles, chegaram no horário.”““Logo, não houve jogo na Ressacada.”Logo, não houve jogo na Ressacada.”


Enfim, está melhorando?Enfim, está melhorando?

Ou querem destruir todos os computadores?

Documents

J. M. Barreto UFSC-INE Lógica de Primeira Órdem R ecordação