Skip to content

Knowledge and Logic

Jump to bottom
João Medeiros edited this page Apr 22, 2025 · 4 revisions

Introduction

A representação de conhecimento em sistemas de inteligência artificial simbólica é fundamentada, principalmente na lógica de predicados. Especificamente, em fatos e regras definidos por meio de uma linguagem de programação baseada em, ou que implemente, essa lógica. Prolog é uma linguagem declarativa fundamentada na utilização de um formato específico de construção de cláusulas da lógica de predicados. Essas cláusulas, denominadas cláusulas de Horn, e conceitos da lógica de predicados são apresentados a seguir.

Predicate Logic

Considere o seguinte argumento descrito em lógica de predicados.

$(\exists y)(\forall x)Lxy \qquad$ premissa
$\therefore (\forall x)(\exists y)Lxy \qquad$ conclusão

Assumindo, por exemplo, que o predicado relacional $Lab$ estabelece que $a$ gosta de $b$, temos que a premissa afirma que, no universo de discurso, existe $y$ para todo $x$ tal que $x$ gosta de $y$. A partir dessa única premissa, o argumento conclui que para todo $x$ existe $y$ tal que $x$ gosta de $y$. Em linguagem natural, o argumento define que se existe alguém de quem todo mundo gosta, então todo mundo gosta de alguém.

É possível utilizar o método de prova por contradição para tentar verificar a validade do argumento. Para isso, bloqueia-se a conclusão e supõe-se que ela é falsa.

1 $(\exists y)(\forall x)Lxy \qquad$ premissa
$\bullet \therefore (\forall x)(\exists y)Lxy \qquad$ conclusão
2 $\text{ sup. } \neg(\forall x)(\exists y)Lxy \qquad$ suposição

Na suposição tem-se a negação do quantificador universal. Utilizando a regra
RU: $\neg(\forall x)Px \rightarrow (\exists x)\neg Px$ ,
é possível concluir $(\exists x)\neg(\exists y)Lxy$ .

1 $(\exists y)(\forall x)Lxy \qquad$ premissa
$\bullet \therefore (\forall x)(\exists y)Lxy \qquad$ conclusão
2 $\text{ sup. } \neg(\forall x)(\exists y)Lxy \qquad$ suposição
3 $\therefore (\exists x)\neg(\exists y)Lxy \qquad$ RU em 2

Com a reescrita da sentença 2 na 3 é possível instanciar o quantificador existencial utilizando a regra
DE: $(\exists x)Px \rightarrow Pt$ ,
onde $t$ é uma letra que ainda não foi utilizada.

1 $(\exists y)(\forall x)Lxy \qquad$ premissa
$\bullet \therefore (\forall x)(\exists y)Lxy \qquad$ conclusão
2 $\text{ sup. } \neg(\forall x)(\exists y)Lxy \qquad$ suposição
3 $\therefore (\exists x)\neg(\exists y)Lxy \qquad$ RU em 2
4 $\therefore \neg(\exists y)Lay \qquad$ DE em 3

Em 4 tem-se a negação do quantificador existencial. Utilizando a regra
RE: $\neg(\exists x)Px \rightarrow (\forall x)\neg Px$ ,
é possível concluir $(\forall y)\neg Lay$ . Dessa forma, utilizando a regra RE em 4 e instanciando o quantificador existencial da premissa 1 em $b$ (uma vez que $a$ já foi utilizado) com a regra DE, tem-se o seguinte resultado.

1 $(\exists y)(\forall x)Lxy \qquad$ premissa
$\bullet \therefore (\forall x)(\exists y)Lxy \qquad$ conclusão
2 $\text{ sup. } \neg(\forall x)(\exists y)Lxy \qquad$ suposição
3 $\therefore (\exists x)\neg(\exists y)Lxy \qquad$ RU em 2
4 $\therefore \neg(\exists y)Lay \qquad$ DE em 3
5 $\therefore (\forall y)\neg Lay \qquad$ RE em 4
6 $\therefore (\forall x)Lxb \qquad$ DE em 1

Nesse ponto é possível identificar que é possível chegar a uma contradição ao instanciar o quantificador universal de 5 em $b$ (resultando em $\neg Lab$) e o de 6 em $a$ (resultando em $Lab$). Utilizando a regra
DU: $(\forall x)Px \rightarrow Pt$ ,
onde $t$ pode ser qualquer letra pois o quantificador universal se aplica a qualquer elemento do universo de discurso.

Com a contradição, é possível concluir que a suposição inicial é falsa por RAA (reductio ad absurdum, ou, redução ao absurdo). Resultando em $\neg\neg(\forall x)(\exists y)Lxy$. Para concluir a prova, bloqueia-se tudo que foi derivado desde a suposição e, utilizando a regra
SN: $\neg\neg P \rightarrow P$
remove-se a dupla negação (resultando em $(\forall x)(\exists y)Lxy$, a conclusão inicial). Dessa forma, é possível verificar que o argumento é válido pela seguinte prova por contradição.

1 $(\exists y)(\forall x)Lxy \qquad$ premissa
$\bullet \therefore (\forall x)(\exists y)Lxy \qquad$ conclusão
2 $\bullet \text{ sup. } \neg(\forall x)(\exists y)Lxy \qquad$ suposição
3 $\circ \therefore (\exists x)\neg(\exists y)Lxy \qquad$ RU em 2
4 $\circ \therefore \neg(\exists y)Lay \qquad$ DE em 3
5 $\circ \therefore (\forall y)\neg Lay \qquad$ RE em 4
6 $\circ \therefore (\forall x)Lxb \qquad$ DE em 1
7 $\circ \therefore Lab \qquad$ DU em 6
8 $\bullet \therefore \neg {L}ab \qquad$ DU em 5
9 $\therefore \neg\neg(\forall x)(\exists y)Lxy \qquad$ RAA em 2, cont. 7 e 8
10 $\therefore (\forall x)(\exists y)Lxy \qquad$ SN em 9

O método de prova por contradição e a utilização de argumentos da lógica de predicados são a base conceitual necessária para compreender a linguagem de programação Prolog. A seguir, são apresentadas as cláusulas de Horn. Elas são a fundamentação da linguagem e da gramática utilizada para definir argumentos da lógica de predicados em Prolog.

Horn Clauses

Uma fórmula atômica, ou átomo, tem formato $P t_1 \dots t_n$ , onde $P$ representa um predicado e $t_i$ um termo. Por exemplo, $Pj$ para representar "João é Professor" e $Arj$ para representar que "Romeu ama Julieta".

Um literal é um átomo ou a negação de um átomo, denominados, respectivamente, literal positivo e literal negativo. Por exemplo, $Pj$ é um literal positivo, enquanto $\neg Pj$ é um literal negativo.

Uma cláusula é uma disjunção de literais no formato $(L_1 \vee L_2 \vee \dots \vee L_n)$ , onde cada $L_i$ é um literal.

Uma cláusula de Horn é uma cláusula com no máximo um literal positivo, podendo ser subclassificada em:

  • cláusula definitiva, uma cláusula de Horn com exatamente um literal positivo;
  • cláusula unitária, uma cláusula definitiva sem literais negativos; e
  • cláusula objetivo, uma cláusula de Horn sem literais positivos.

Cláusulas definitivas podem ser interpretadas como regras de inferência. Por exemplo, considere a seguinte cláusula $$(H \vee \neg G_1 \vee \dots \vee \neg G_n) \text{ ,}$$ que pode ser reescrita como $$(H \vee \neg (G_1 \wedge \dots \wedge G_n)) \text{ .}$$

Utilizando a seguinte equivalência semântica entre a disjunção e a implicação $$(A \vee \neg B) \Leftrightarrow (B \rightarrow A) \text{ ,}$$ é possível reescrever a cláusula definitiva anterior como $((G_1 \wedge \dots \wedge G_n) \rightarrow H)$, ou $$(H \leftarrow (G_1 \wedge \dots \wedge G_n)) \text{ .}$$

The Language

Prolog usa as três cláusulas de Horn apresentadas como elementos de linguagem para construção de programas. Utilizando o operador :- (dois pontos traço) para representar a operação de implicação $\leftarrow$, e , (vírgula) para a conjunção $\wedge$, tem-se os seguintes elementos de linguagem:

  • regras: cláusulas definitivas no formato H :- G1, ..., Gn., onde Gi lê-se objetivo;
  • fatos: cláusulas unitárias no formato H.; e
  • consultas: cláusulas objetivo no formato ?- G1, ..., Gn..

Sobre a sintaxe da linguagem cabe reforçar que todos o elementos terminam com . (ponto) e que nas consultas o operador de implicação :- é substituído por ?-.

Uma questão importante relacionada a utilização de cláusulas de Horn é que o processo de dedução ou prova de programas é significativamente simplificado por causa da sua sintaxe simples. Embora essa simplificação reduza o poder de expressão da lógica de predicados, é conhecido que com a utilização cláusulas de Horn é possível construir programas com a mesma representatividade computacional da máquina de Turing. Ou seja, a utilização de cláusulas de Horn permite escrever programas para tudo que é conhecido como computável.

Basics

Considere o seguinte programa composto por três fatos.

love(romeo, juliet).
love(paris, juliet).
love(juliet, juliet).

Esse programa representa um dos possíveis universos de discurso do argumento apresentado no início da Seção Predicate Logic. Temos na premissa que $(\exists y)(\forall x)Lxy$, ou seja, um universo de discurso em que existe pelo menos um indivíduo que é amado por todos. No exemplo acima, esse indivíduo é juliet. Com o programa definido, é possível criar cláusulas de consulta.

?- love(romeo, juliet).
true.

NOTA - É possível experimentar programação em Prolog na plataforma on-line SWISH.

Nesse exemplo, o objetivo da consulta love(romeo, juliet) tem como resultado o valor verdade true. Isso quer dizer que o Prolog encontrou uma forma de demonstrar que o objetivo é verdadeiro com base no programa escrito. Considere agora as seguintes consultas.

?- love(romeo, paris).
false.

?- love(juliet, romeo).
false.

No primeiro caso, love(romeo, paris), o Prolog não encontrou uma forma de provar o objetivo e, por isso, o considerou falso (false). É importante destacar que a linguagem considera que o universo de discurso é fechado e, portanto, tudo aquilo que ela não consegue provar é considerado por ela falso. Veja que isso também é reforçado pela segunda consulta do exemplo. O programa também conclui que love(juliet, romeo) é falso, pois não há como concluir isso com base no programa apresentado.

Uma consulta em Prolog pode ser mais generalista através da utilização de variáveis. Por exemplo, é possível com objetivo love(rome, X) buscar por uma solução para X que torne o objetivo verdadeiro.

?- love(romeo, X).
X = juliet.

Nesse caso, tem-se como resposta uma solução para a variável X. De forma ainda mais geral, é possível criar a consulta love(X, Y), onde o Prolog tentará encontrar termos que possam substituir as variáveis X e Y a fim de tornar a consulta verdadeira.

?- love(X, Y).
X = romeo,
Y = juliet ;
X = paris,
Y = juliet ;
X = Y, Y = juliet.

Onde o símbolo , representa a conjunção $\wedge$ , e o símbolo ; representa a disjunção $\vee$ (ou inclusivo).

Em Prolog, as respostas a uma cláusula consulta podem ser dos seguintes tipo.

  1. Uma avaliação da cláusula objetivo: true ou false; ou
  2. Uma solução: podendo ser única ou um conjunto de soluções.

Deduction

No exemplo a seguir, inspirado no livro do Harry J. Gensler, tem-se um conjunto de fatos sobre uma festa em que o dinheiro de Herman foi roubado.

  1. Alice doesn’t love money.
  2. Bob loves money.
  3. Carol knew where the money was.
  4. David works for Herman.
  5. All who stole money love money.
  6. All who stole money knew where the money was.
  7. All who work for Herman hate Herman.
  8. All who hate Herman stole money.

Podemos traduzi-los para lógica de predicados a fim de verificar se é possível identificar culpados e inocentes.

did_not_stole(X, money) :- does_not_love(X, money).
does_not_love(alice, money).
hate(X, herman) :- works(X, herman).
knew_where_was(carol, money).
knew_where_was(X, money) :- stole(X, money).
love(bob, money).
love(X, money) :- stole(X, money).
stole(X, money) :- hate(X, herman).
works(david, herman).

Nessa tradução, um dos fatos originais é que Alice não gosta de dinheiro. Como a falha em provar resulta em false. Deve-se reescrever um novo predicado, no caso does_not_love(alice, money). Como a regra love(X, money) :- stole(X, money) é importante para inocentar Alice, devemos reescreve-la considerando o novo predicado does_not_love(X, Y). Como a tabela verdade de $(P \rightarrow Q)$ é igual a $(\neg Q \rightarrow \neg P)$, é possível reescrever a regra como sendo did_not_stole(X, money) :- does_not_love(X, money). Dessa forma, é possível realizar uma consulta para, com base no fatos, provar a culpabilidade e a inocência.

term@ai$ swipl -q party.pl 
?- stole(X, money).
X = david.

?- did_not_stole(X, money).
X = alice.

Com base nos fatos, não é possível concluir sobre a culpa ou inocência de Bob, Carol ou Herman.

NOTA - O programa utilizado nesse exemplo está disponível no arquivo party.pl no repositório. Uma versão estendida está disponível no arquivo party-plus.pl.

Calculation

O cálculo do fatorial de $n$ é um dos problemas clássicos para introduzir conceitos aritméticos e de recursão em um linguagem de programação. A relação fatorial $F(n,r)$ é verdadeira se $r=n!$. Por definição, $F(0,1)$ é verdadeiro e pode-se tratá-lo como fato. Porém, para o caso de $n>0$, aqui representado por $B(n,0)$, é possível definir recursivamente o fatorial a partir da multiplicação $n \times r_1$, onde $r_1$ é termo da relação $F(n_1,r_1)$, para $n_1=n-1$ . Escrevendo a relação de subtração como $M(n,1)$ e a de multiplicação como $P(n,r_1)$, é possível definir a seguinte cláusula definitiva ou regra $$F(n,r) \leftarrow B(n,0) \wedge I(n_1, M(n,1)) \wedge F(n_1,r_1) \wedge I(r, P(n,r_1)) \text{ ,}$$ onde o predicado $I(a,b)$ é verdadeiro se é possível vincular o termo $b$ ao termo não vinculado $a$.

Nessa cláusula definitiva é primeiro verificado pela avaliação do primeiro literal se $n>0$. Se verdadeiro, o segundo literal vincula à variável $n_1$ o valor $n-1$. A resolução do terceiro literal pelo sistema de dedução irá vincular a variável $r_1$ o valor do $(n-1)!$ a partir de sucessivas resoluções até encontrar como caso base o fato $F(0, 1)$. Com a vinculação de $r_1$, o quarto literal vincula à variável $r$ o resultado de $n \times r_1$, concluindo a inferência de $F(n,r)$.

O programa a seguir implementa essas cláusulas utilizando > para o predicado $B$, is para o predicado $I$, - para o predicado $M$ e * para o predicado $P$.

factorial(0, 1).
factorial(N, R) :- >(N, 0),
                   is(N1, -(N, 1)),
                   factorial(N1, R1),
                   is(R, *(N, R1)).

Com base no programa pode-se verificar o resultado das seguintes consultas.

term@ai$ swipl -q factorial.pl
?- factorial(0, R).
R = 1 .

?- factorial(5, R).
R = 120 .

NOTA - O programa utilizado nesse exemplo está disponível no arquivo factorial.pl no repositório. Também é possível encontrar exemplos para o teste de primalidade no arquivo prime.pl e cálculo de raiz exata no arquivo root.pl.

Search

Robot Walk

adjacent(a1, a2). adjacent(a1, b1).
adjacent(a2, a1). adjacent(a2, a3). adjacent(a2, b2).
adjacent(a3, a2). adjacent(a3, a4). adjacent(a3, b3).
adjacent(a4, a3). adjacent(a4, a5). adjacent(a4, b4).
adjacent(a5, a4). adjacent(a5, b5).

[...]

path(X, Y) :- path(X, Y, P), print(P).
path(X, Y, P) :- path(X, Y, F, [X]), append([X], F, P), !.
path(X, Y, P, V) :- adjacent(X, Y),
                    append([Y], [], P);
                    adjacent(X, Z),
                    not(member(Z, V)),
                    append([Z], V, W),
                    path(Z, Y, F, W),
                    append([Z], F, P).

path(X, Y) :- path(X, Y, P),            % Includes the P variable.
              print(P).                 % Prints the path P.
path(X, Y, P) :- path(X, Y, F, [X]),    % Includes X in the memory.
                 append([X], F, P).     % Appends X to the path P.
path(X, Y, P, V) :- adjacent(X, Y),     % Verify if X and Y are adjacent.
                    append([Y], [], P); % Appends Y to the path P.
                    adjacent(X, Z),     % Gets a Z adjacent to X.
                    not(member(Z, V)),  % Verify if Z is not visited.
                    append([Z], V, W),  % Appends Z to the memory.
                    path(Z, Y, F, W),   % Finds a path from Z to Y.
                    append([Z], F, P).  % Appends Z to the path.
term@ai$ swipl -q robot.pl 
?- path(a1, e5).
[a1,a2,a3,a4,a5,b5,c5,d5,e5]
true.

References

[1] Harry Gensler. Introduction to Logic.
[2] Peter Flach. Simply Logical.
[3] Markus Triska. The Power of Prolog.

Clone this wiki locally