ESTUDO COMPARATIVO DE MODELOS EM SISTEMAS · PDF filedistingue claramente as premissas das regras de inferência e o surgimento dos ... cores. A questão da coloração de mapas

Anais do 13O Encontro de Iniciação Científica e Pós-Graduação do ITA – XIII ENCITA / 2007

Instituto Tecnológico de Aeronáutica, São José dos Campos, SP, Brasil, Outubro, 01 a 04, 2007.

ESTUDO COMPARATIVO DE MODELOS EM SISTEMAS ESPECIALISTAS ATRAVÉS DE LÓGICA DE PRIMEIRA ORDEM

Fleuri Domingues Barreto Arruda ITA–Instituto Tecnológico de Aeronáutica, H8-C, 317 Pç. Marechal Eduardo Gomes, n 50 – Campus do CTA, 12228-900, São José dos Campos – SP Bolsista PIBIC-CNPq [email protected] Paulo Marcelo Tasinaffo ITA–Instituto Tecnológico de Aeronáutica, Divisão de Ciência da Computação Pç. Marechal Eduardo Gomes, n 50 – Campus do CTA, 12228-900, São José dos Campos – SP [email protected] Vakulathil Abdurahiman ITA–Instituto Tecnológico de Aeronáutica, Divisão de Ciência da Computação Pç. Marechal Eduardo Gomes, n 50 – Campus do CTA, 12228-900, São José dos Campos – SP Resumo: O principal objetivo desse trabalho é mostrar as aplicações em lógica de primeira ordem na construção de um sistema

especialista. A construção do sistema especialista se dá através da utilização do PROLOG como linguagem de programação. São

abordados tópicos relacionados à coloração de grafos não orientados, uma vez que a modelagem utilizada exige tal procedimento.

Por fim, serão realizadas análises dos resultados obtidos, junto de comparações em relação ao grau de dificuldade e gasto de tempo

para que a obtenção dos mesmos se concretizasse caso não fossem utilizados os métodos computacionais abordados por esse

projeto.

Palavras-chave: linguagem Prolog, coloração de mapas, lógica de primeira ordem.

1. Introdução A lógica teve suas origens na filosofia e na matemática dos antigos gregos, quando após a morte de Aristóteles em 322 a.C. seus alunos reuniram suas principais anotações em um tratado denominado Organon. Modernamente pode-se analisar os silogismos de Aristóteles como regras de inferência e estes silogismos já incluíam elementos de lógica proposicional e de predicados. Ainda nesta época ocorreram outras contribuições de grandes filósofos e conjuntamente, pode-se descrevê-los através de Aristóteles (fundador da escola Aristotélica), Euclides (fundador da escola Megárica) e Zenon (fundador da escola dos Estóicos). A diferença básica entre essas três escolas [1] é que a primeira era predominantemente definida através da lógica de classes ou de predicados e as duas últimas pela lógica de preposições. Após os Estóicos inicia-se um período obscuro no desenvolvimento da lógica de proposições e até meados do século dezenove pode-se citar apenas alguns autores como Boécio (480-524 d.C.), Petrus Hispanus e Leibniz (1646-1716). Entretanto, a lógica moderna foi impulsionada a partir de 1847, quando George Boole (1815-1864) introduziu o primeiro sistema completo e funcional de lógica formal em seu livro The Mathematical Analysis of Logic e, logo após, em 1854 com seu clássico Investigations of the Laws of Thought. É devido a George Boole o famoso princípio da não-contradição, ou seja, “nenhum objeto pode ter duas propriedades contraditórias” ou a notação booleana:

verdadeiro1 ≡ e falso0 ≡ . Logo em seguida, Gottlob Frege (1848-1925) publica em 1879 o livro intitulado Escrita de

Conceitos que relata a primeira exposição completa da lógica moderna proposicional e de primeira ordem, que distingue claramente as premissas das regras de inferência e o surgimento dos quantificadores. O matemático italiano Giuseppe Peano (1859-1932) elabora uma notação matemática mais simples que a de Frege, criando assim, a anotação atual para a lógica de primeira ordem [4] em 1889. Bertrand Russel (1872-1970) e A. N. WhiteHead (1861-1947) publicam The Principia Mathematica, três volumes de 1910 a 1913 dando surgimento aos paradoxos dentro da própria lógica. Além disso, B. Russel introduz em 1902 o símbolo de igualdade dentro da lógica de predicados com os princípios da identidade e da substituibilidade. Alfred Tarski em 1935 – através da teoria de conjuntos – dá uma definição explícita de verdade e de satisfação em lógica de primeira ordem. No final do século XX vê-se a utilização da lógica de predicados ou de primeira ordem na construção e elaboração de compiladores, originando os primeiros sistemas especialistas em Inteligência Artificial através da descoberta de algoritmos automáticos de inferência [2] e [3] . Os principais deles são: algoritmo de encadeamento pra frente ou de encadeamento para trás em cláusulas de Horn e o algoritmo da Resolução Completa [2]. Este último podendo ser definido brevemente como uma generalização e sistematização do método de redução ao absurdo proposto ainda por Zenon na Grécia Antiga. Desta forma, Alfred Horn em 1951 introduziu a forma de Horn nas sentenças de primeira ordem e J.A. Robinson em 1965 introduziu a regra de Resolução Completa e uma prova de sua completeza mostrando assim, como

Anais do XIII ENCITA 2007, ITA, Outubro, 01-04, 2007

,

realizar o raciocínio de primeira ordem sem recorrer às técnicas proposicionais [2]. Em 1971, Stephen Cook mostrou que a definição de satisfabilidade de uma sentença em lógica proposicional é NP-Completa. Para uma aplicação interessante da lógica de primeira ordem, considere o problema que consiste na coloração dos estados do mapa do Brasil, observando-se o fato de que estados adjacentes não podem ter a mesma cor. Para a solução deste problema, deve-se tentar encontrar as soluções que utilizem o menor número possível de cores. A questão da coloração de mapas com número limitado de cores deu origem a vários trabalhos matemáticos [5], [6], [7], [8] e [9] que versavam sobre a possibilidade de se pintar um mapa qualquer se utilizando apenas quatro cores, dando origem ao Teorema das Quatro Cores. Tal problema foi proposto por Francis Guthrie em 1852 ao seu irmão, que era um estudante universitário de matemática em Cambridge. Várias tentativas surgiram na tentativa de se demonstrar tal teorema, entretanto, a solução que se mostrou verdadeiramente correta, foi apresentada por Appel-Haken em 1976. Essa demonstração só foi possível através da utilização de métodos computacionais, uma vez que esse processo gera grafos classificados em mais de 1400 configurações que, em seguida, foram testadas por um algoritmo de cerca de 740 páginas. Uma versão mais concisa dessa demonstração foi apresentada em 1997, entretanto ainda necessitava de um potente computador para realização. Mesmo que a primeira solução tenha sido apresentada na década de 70, não houve, até hoje, uma prova realmente sucinta da demonstração desse teorema. Desta forma, podemos partir do princípio de que o banco de cores possíveis para coloração do mapa do Brasil não precisa ter mais de quatro possibilidades, a não ser que haja a intenção de se determinar o número de possibilidades de se pintar certo mapa a partir de um conjunto de cores dado. Entretanto, para mapas nos quais o número de áreas a serem coloridas é relativamente elevado, a geração de todas as possibilidades torna-se consideravelmente dispendiosa. A exemplo do Brasil, considerando-se 26 estados e 4 cores

disponíveis para coloração, o número estimado de possibilidades é da ordem de 1510 , tornando completamente inviável a geração de todos esses resultados. 2. Desenvolvimento do projeto Uma cláusula de Horn é definida como um conjunto de disjunção (conectivo ou) de literais dos quais, no máximo um, é positivo. Exemplo: α β γ¬ ∨ ¬ ∨ é uma cláusula de Horn, enquanto α β γ¬ ∨ ∨ não é. Através

das regras de inferência de conversão do cálculo proposicional [1], o condicional ( )α β γ∧ → tem forma

equivalente a ( )α β γ¬ ∧ ∨ ou ( )α β γ¬ ∨ ¬ ∨ , ou seja, ele também está na forma de cláusulas definidas de Horn.

Assim, dentro do cálculo proposicional pode-se definir o encadeamento para frente como uma aplicação sistemática de

Modus Ponens, ou seja, a regra de inferência do tipo ,α α β

β

→ pode ser convertida na forma

,α α β

β

¬ ∨. Neste

sentido, pode-se dizer que o encadeamento para frente é consistente, ou seja, toda inferência é, em essência, uma aplicação de Modus Ponens. O encadeamento para frente também é completo, no sentido de que toda sentença atômica permitida será derivada. O encadeamento para frente em lógica de primeira ordem já permite a utilização dos quantificadores ( )x xϕ∀ e ( )x xϕ∃ que significam, respectivamente, “para todo x, ( )xϕ ” e “existe pelo menos um x

tal que ( )xϕ ”. Neste caso, tem-se a aplicação sistemática da regra de inferência Modus Ponens Generalizado. Em

particular, esta regra afirma que: ' ' ' '1, 2, 3, , 1 2... ( ... )

( , )n np p p p p p p q

Subst qθ

∧ → (1)

onde, '( , )iSubst pθ = ( , )iSubst pθ para todo i. O exemplo a seguir exemplifica a utilização de Modus Ponens

Generalizado [1]:

1 , ( ) ( )y REI y PODEROSO y∀ → H

2 , ( ) ( ) ( )x REI x GULOSO x PERVERSO x∀ ∧ → H

3 , ( )y REI y∀ H

4 , ( )z GULOSO z∀ H

5 ( )PERVERSO João 1, 2, 3 e 4 (MPG)

{ / , / , / }x João y João z Joãoθ =


,

Nesse processo, as linhas 1, 2, 3 e 4 são as hipóteses de uma Base de Conhecimento (BC) e, portanto as premissas das quais PERVERSO(João) pode ser inferido a partir da aplicação das regras de inferência 1 e o conjunto θ de substituição de variáveis denomina-se processo de unificação, fundamental em todos os algoritmos automáticos em inferência de primeira ordem. O processo de inferência anterior pode ser representado pela árvore de busca representada na Fig. 1.

Figura 1. Esquema Gráfico para representação da regra de inferência Modus Ponens Generalizado. A linguagem PROLOG consiste basicamente na aplicação sistemática dos algoritmos de encadeamento para frente e encadeamento para trás num sistema híbrido de inferências sobre cláusulas de Horn, que permitem manipular Bases de Conhecimento formuladas a partir da observação de fatos do mundo real, transformadas num processo de inferência em lógica de primeira ordem. Tais linguagens denominam-se Sistemas Especialistas [2] e [3] e atualmente muitos compiladores trabalham desta forma e podem ser obtidos gratuitamente na Internet , tais como, o SWI-PROLOG e o JESS para Java. Para o modelamento do problema de colorir mapas, utilizou-se a divisão política dos estados do território brasileiro mostrada na Fig.2.

Figura 2. Divisão dos estados do território brasileiro.

Utilizando-se desse mapa, montou-se o grafo não orientado mostrado na Fig. 3, que será base para a construção do código do sistema especialista.

Figura 3. Grafo representativo das adjacências entre os estados.


,

A partir desse ponto, a implementação em linguagem PROLOG pode ser iniciada. Inicialmente, foi implemento o código que gera todas as possibilidades de se pintar os estados utilizando-se quatro cores. Esse código, que abrange todos os estados simultaneamente, está representado na Fig.4.

Figura 4. Programa em PROLOG para coloração do mapa do Brasil.

Como era de se esperar, a execução desse programa não gerou resultados, já que o número de possibilidades de coloração é realmente muito grande. Uma possível maneira para a determinação de pelo menos uma solução para o problema se baseia na divisão do mapa do Brasil em macro-regiões. As macro-regiões geradas foram denominadas: nordeste, norte/centro-oeste e sul/sudeste. Cada uma dessas regiões contendo menos estados do que o mapa do Brasil como um todo permitiu a geração de soluções partindo do seguinte princípio: gera-se uma solução para determinada região e, em seguida, adapta-se as outras regiões à solução inicialmente obtida. Sendo assim, tomando-se a região nordeste como ponto de partida, construiu-se o seguinte programa em PROLOG, mostrado na Fig.5:

Figura 5. Programa em PROLOG para coloração da região Nordeste. Desta forma, a solução encontrada considerando-se essas restrições iniciais é mostrada na Fig. 6:

Figura 6. Solução gerada pelo programa para a região Nordeste.


,

Ilustrando a solução encontrada, tem-se: Figura 7. Coloração da região Nordeste.

O próximo passo foi gerar soluções para as macro-regiões norte/centro-oeste e sul/sudeste, considerando-se as

restrições adicionais devido à coloração da região nordeste. Para isso, criou-se o programa responsável por colorir a macro-região sul/sudeste levando-se em consideração a cor do estado da BA.

Figura 8. Programa em PROLOG para coloração da macro-região Sul/Sudeste. A solução gerada pelo programa é dada por:

Figura 9. Solução gerada pelo programa para a macro-região Sul/Sudeste.

Figura 10 . Coloração da macro-região Sul/Sudeste


,

Por fim, utilizando-se das cores já determinadas para as regiões acima mencionadas, basta criar o programa para coloração da macro-região norte/centro-oeste, considerando-se tais restrições adicionais. Sendo assim, tem-se:

Figura 11. Programa em PROLOG para coloração da macro-região Norte/Centro. As Fig.12 e Fig.13, mostram, respectivamente, a solução gerada e o mapa já colorido.

Figura 12. Solução gerada pelo programa para a macro-região Norte/Centro.

Figura 13 . Coloração da macro-região Norte/Centro.

Pôde-se notar, durante a execução dos três programas, que, no terceiro caso, o tempo para que a resposta fosse

gerada foi de alguns segundos, uma vez que o número de estados é relativamente grande e o número de restrições também é maior se comparado com as outras duas regiões. Para as duas primeiras, não se observa tempo considerável para geração dos resultados. Desta forma, o mapa do Brasil completo é dado por:


,

Figura 14 . Solução 1 - Mapa do Brasil completamente colorido. Utilizando-se do mesmo raciocínio, mais soluções podem ser geradas:

Figura 15 . Soluções 2 e 3 - Mapa do Brasil completamente colorido.

Para os casos em que o número de cores não era suficiente para se obter a coloração do mapa, o programa exibia a seguinte informação:

Figura 16. Caso em que não existe solução A exibição do ‘No’ indica que não é possível gerar pintar( ) de tal forma que todos as restrições de cores e adjacências sejam satisfeitas. 3. Conclusões O projeto como um todo versou sobre o tema da coloração de superfícies divididas em um certo número de regiões, de tal forma que regiões adjacentes não apresentassem a mesma coloração. Sendo assim, o Teorema das 4

cores deve de ser elucidado, uma vez que aborda o limite inferior do número de cores necessárias para se pintar uma


,

disposição de figuras adjacentes que se encontram num determinado plano. Para a coloração das regiões abordadas nesse trabalho, o teorema pôde ser verificado, uma vez que as hipóteses do mesmo estão sendo respeitadas. Em relação à intenção inicial do trabalho, nota-se que houve algumas alterações, pois se almejava uma solução direta para o problema da coloração, isto é, inicialmente, não seria necessário realizar a divisão do mapa em macro-regiões, entretanto, tal processo faz-se necessário já que o número de possibilidades a serem geradas e a quantidade de restrições que o programa deve obedecer acaba por tornar inviável sua execução. Desta forma, a estratégia de divisão do problema inicial em outros menores possibilitou a geração de soluções, entretanto, houve o ônus adicional de se restringir as cores das macro-regiões adjacentes devido à coloração da macro-região escolhida a priori. Logo, vê-se que a utilização do PROLOG como ferramenta para a resolução desse problema mostra-se extremamente útil, uma vez que a lógica de primeira ordem permite a obtenção de resultados importantes através de programas de implementação computacional relativamente simples. Tais resultados foram obtidos de maneira consideravelmente rápida se comparados ao tempo necessário para se obter manualmente através de tentativa e erro. A velocidade de processamento dos computadores auxilia na geração de inferências acerca do problema proposto e que respeitem as condições inicialmente impostas.

4. Agradecimentos

Agradeço ao CNPq e ao Prof. Paulo Marcelo Tasinaffo pelo apoio dado na elaboração deste projeto. Gostaria de agradecer também, a participação do professor Vakulathil Abdurahiman, em memória, que iniciou esta orientação. 5. Referências Bibliográficas [1] Hegenberg, L. Lógica Cálculo Sentencial. 2ª Ed., São Paulo: E.P.U. – Editora Pedagógica e Universitária, 1977.

[2] Russel, S. ; Norvig, P. Inteligência Artificial. Rio de Janeiro: Elsevier, 2004.

[3] Araribóbia, G. Inteligência Artificial: um Curso Prático. Rio de Janeiro: livros técnicos e científicos Editora Ltda,

1989.

[4] Smullyan, R. M. First-Order Logic. New York: Dover Publications, Inc, 1995.

[5] Four Color Theorem. Wikipedia, the free encyclopedia. Disponível em

<http://en.wikipedia.org/wiki/Four_color_theorem>. Acesso em Julho de 2007.

[6] Grupo Teorema de Matemática. Disponível em <http://www.grupoteorema.mat.br/artigos/quatro.pdf>. Acesso

em Julho de 2007.

[7] Instituto Politécnico de Viseu. Disponível em <http://www.ipv.pt/millenium/Millenium24/12.pdf>. Acesso em

Julho de 2007.

[8] Programa de Engenharia de Sistema e Computação – Universidade Federal do Rio de Janeiro. Disponível em:

<http://www.cos.ufrj.br/~sheila/Logica_de_primeira_Ordem_Sintaxe_Semantica_ Propriedades_Sintaticas.doc>.

Acesso em Julho de 2007

[9] Departamento de Matemática do Instituto Superior Técnico de Lisboa. Disponível em:

<http://www.math.ist.utl.pt/~mpg/tcAP0506/folhas/lprimord.pdf>. Acesso em Julho de 2007

Documents

ESTUDO COMPARATIVO DE MODELOS EM SISTEMAS · PDF filedistingue claramente as premissas das regras de inferência e o surgimento dos ... cores. A questão da coloração de mapas