Capítulo 1 introduçÃO



Baixar 0.71 Mb.
Página1/32
Encontro07.08.2016
Tamanho0.71 Mb.
  1   2   3   4   5   6   7   8   9   ...   32
LÓGICA DE PREDICADOS
SUMÁRIO





  • CAPÍTULO 1 - INTRODUÇÃO




  1. 1.1. Inteligência Artificial, Lógica Simbólica e Prova de Teoremas

Desde o nascimento do primeiro computador moderno, a tecnologia dos computadores desenvolveu-se numa velocidade fantástica. Hoje vê-se computadores sendo usados, não somente para resolver problemas de alta complexidade computacional, como realizar uma transformada rápida de Fourier ou inverter uma matriz de grandes dimensões, mas também para executar tarefas que poderiam ser chamadas de inteligentes, se feitas por seres humanos. Algumas destas tarefas são: escrita de programas, responder perguntas, provar teoremas. A Inteligência Artificial é um ramo da ciência da computação que está preocupado com a execução de tais tarefas.

A segunda metade dos anos 60 foi fenomenal para a inteligência artificial devido ao aumento no interesse na prova automática de teoremas. A disseminação deste interesse foi causada, não somente pela crescente consciência de que a habilidade de fazer deduções lógicas é uma parte integrante da inteligência humana, mas foi, talvez, um resultado do nível alcançado pelas técnicas de prova automática de teoremas ao final dos anos 60. Os fundamentos da prova automática de teoremas foram desenvolvidos por Herbrand em 1930. Seu método era impossível de ser implementado até a invenção do computador digital. E continuou assim até a publicação do fantástico artigo de J.A. Robinson em 1965, junto com o desenvolvimento do princípio da resolução, cujos maiores passos foram dados para obter os provadores de teroremas implementados em computadores. A partir deste momento, sucessivos refinamentos tem sido feitos no princípio de resolução.

Paralelamente ao progresso no aprimoramento das técnicas de prova automática de teoremas aconteceu o progresso na aplicação das técnicas de prova automática de teoremas a vários problemas de inteligência artificial. Elas foram inicialmente aplicadas a dedução (resposta de questões) e, posteriormente para solução de problemas, síntese e análise de programas entre muitas outras aplicações.

Existem muitos pontos de vista através dos quais pode-se estudar a lógica simbólica. Tradicionalmente, ela foi estudada através de orientações filosóficas e matemáticas. Aqui se está interessado em aplicações da lógica simbólica para resolução de problemas intelectualmente difíceis. Isto é, quer-se usar lógica simbólica para representar problemas e obter suas soluções.

A seguir vão ser apresentados alguns exemplos bastante simples para demonstrar como a lógica simbólica pode ser usada para representar problemas. Mesmo que não se tenha ainda discutido formalmente lógica simbólica pode-se utilizar a intuição para compreender o que segue.

Considere os seguintes fatos:
F1: Se está quente e úmido, então choverá.

F2: Se está úmido, então está quente.

F3: Está úmido agora.
A pergunta é : Vai chover ?
Os fatos acima são escritos em português. Deve-se usar símbolos para representá-los. Faça P, Q e R representar Está quente, Está Úmido e Choverá, respectivamente. Também são necessários alguns símbolos lógicos. Neste caso, pode-se usar  para representar o E e  para representar Implica Em. Então os três fatos acima podem ser representados como:
F1: P  Q  R

F2: Q  P

F3: Q
Traduzidas as sentenças em português para fórmulas lógicas. Pode-se observar que sempre que F1,F2 e F3 são verdadeiras , a fórmula:
F4: R , é verdadeira.
Portanto, pode-se dizer que F4 é conseqüência lógica de F1, F2 e F3. Isto é, choverá.
Considere outro exemplo, assumindo os seguintes fatos:
F1: Confúcio é um homem.

F2: Todos os homens são mortais.


Para representar F1 e F2, é necessário um novo conceito, chamado de predicado. Pode-se fazer P(x) e Q(x) representar x é um homem e x é mortal, respectivamente. Também usamos (x) para representar para todo x.
Portanto, os fatos acima serão representados por:
F1: P(Confúcio)

F2: (x) (P(x)  Q(x)).


Novamente, poder-se-á ver que a partir de F1 e F2 pode-se deduzir logicamente que:
F3: Q(Confúcio), significando que Confúcio é mortal.
Nos dois exemplos acima foi necessário provar que uma fórmula é conseqüência lógica de outras fórmulas.

Vai-se chamar de Teorema uma sentença na qual uma fórmula é conseqüência lógica de outras fórmulas. A demonstração de que um teorema é verdadeiro, isto é , que uma fórmula é conseqüência lógica de outras fórmulas, será chamada de Prova do Teorema. O problema de prova automática de teoremas é considerar métodos automáticos para encontrar provas de teoremas.


Existem vários problemas que podem ser, convenientemente, transformados em problemas de prova de teorema. Seguem alguns deles:
1. Num sistema de resposta a perguntas, fatos podem ser representados por fórmulas lógicas. Então, para responder uma pergunta através dos fatos, deve-se provar que a fórmula correspondente à resposta deriva das fórmulas representando os fatos.

2. Num problema de análise de programas, pode-se descrever a execução de um programa por uma fórmula A, e a condição de que o programa acabará, por outra fórmula B. Então, verificar se o programa acabará é equivalente a provar que a fórmula B é conseqüência lógica da fórmula A.

3. No problema de isomorfismo de grafos, quer-se saber se um grafo é isomórfico a um subgrafo de um outro grafo. Este problema não é meramente um problema interessante da matemática; mas, também é um problema prático. Por exemplo, a estrutura de um composto orgânico pode ser representada por um grafo. Portanto, testar se uma subestrutura de um composto orgânico é estrutura de um outro composto orgânico é um problema de isomorfismo de grafos. Para este problema, pode-se descrever grafos através de fórmulas. Então, o problema pode ser formulado como: provar que a fórmula que representa um grafo é conseqüência lógica da fórmula que representa outro grafo.

4. No problema de transformação de estados, existe uma coleção de estados e uma coleção de operadores. Quando um operador é aplicado a um estado, um novo estado é obtido. Partindo de um estado inicial, tenta-se encontrar uma seqüência de operadores que transformarão o estado inicial em um estado desejado. Neste caso, pode-se descrever os estados e as regras de transição entre eles através de fórmulas lógicas. Deste modo, a transformação do estado inicial em um estado desejado pode ser tratada como a verificação de que a fórmula representando o estado desejado é conseqüência lógica da fórmula que representa ambos os estados e as regras de transição entre eles.

Uma vez que muitos problemas podem ser formulados como problemas de prova automática de teoremas, está é uma área muito importante da ciência da inteligência artificial. Graças ao esforço de muitos pesquisadores, teve-se grande avanço no uso de computadores para provar teoremas.

  1   2   3   4   5   6   7   8   9   ...   32


©principo.org 2016
enviar mensagem

    Página principal