Representação de
Conhecimento
e
História da Lógica
Fred Freitas – CIn/UFPE
Interesses de RC

Representação e manipulação simbólica
de conhecimento visando raciocínio


Estruturas de representação que
mantenham o engajamento ontológico
(correspondência o mais fiel possível com
as estruturas e relações do mundo ou
universo de discurso)
Cujas deduções mecânicas sobre estas
estruturas sejam também verdadeiras no
universo de discurso
Disciplinas básicas para RC



Lógica – provê a estrutura formal (com
engajamento ontológico, i.e., sintaxe e
semântica) e regras de inferência
Ontologia – define o universo de
discurso, o vocabulário semântico
Computação – produz aplicações,
analisa a aplicabilidade algorítmica das
regras de inferência
Conceitos básicos

Conhecimento

Conceito muito vasto...


Reconhecer é um tipo de conhecimento...
Para RC, um conjunto de proposições, que podem
assumir valores verdade




Proposições são declarativas, expressas simbolicamente
A linguagem em elas são expressas regula sua
expressividade (mas não entraremos nisso por ora...)
Ex de proposição: Eu fui ao cinema.
Ex de valores verdade: {T,F}, {T,F,U},...
Conhecimento II

Formalmente, é a relação entre 2 domínios,
onde o 1º. significa o 2º


Não podemos dar margem a ambigüidades como
em linguagem natural!
Símbolo



Representa algum conceito abstrato (7, VII,
sieben) ou concreto (meu cão Latifundiário)
Para RC, o alfabeto e suas regras de agrupamento
devem ser bem-definidas (sintaxe da linguagem)
E também sua correspondência com o universo de
discurso, ou interpretação
Representação de
Conhecimento


Disciplina que estuda o uso de símbolos
formais para representar conjuntos de
proposições
Raciocínio – manipulação mecânica
destes símbolos de forma a criar novos
símbolos
Conhecimento:
Representação e Uso

Raciocínio:


processo de construção de novas sentenças a
partir de outras sentenças.
Deve-se assegurar que o raciocínio é
consistente (sound)
fatos
segue-se
fatos
Mundo
Representação
sentenças
implica
sentenças
7
Exemplo de raciocínio

Com as sentenças
. Se houver uma guerra nuclear, a
civilização será destruída.
. Haverá uma guerra nuclear

Após algumas manipulações,
produzimos
◊ A civilização será destruída por uma guerra
nuclear.
Hipótese de RC [Brian Smith]

Propriedades de um sistema cognitivo:



Um observador externo pode entender o que está
representado em suas proposições
O sistema se comporta de um dado jeito por
causa do que está representado nestas
proposições
Vantagem em relação a sistemas tradicionais
(procedimentais): pode-se perguntar a um
programa sobre o que ele sabe, etc...
O que é um Sistema
Baseado em Conhecimento ?
Qual deles é um SBC? Por quê?
printColor(snow) :- !, write(“It’s white.”).
printColor(grass) :- !, write(“It’s green.”).
printColor(sky) :- !, write(“It’s yellow.”).
printColor(X) :- write(“Beats me.”).
printColor(X) :-color(X,Y), !, write(“It’s “),
write(Y), write(“.”).
color(X, Y) :- madeOf(X, Z), color(Z, Y).
madeOf(grass, vegetation).
printColor(X) :- write(“Beats me.”).
color(snow,white).
color(sky,yellow).
color(vegetation, green).
Prós e contras



DECLARATIVO
Fácil adicionar mais
conhecimento ao
sistema
Fácil estendê-lo para
novas tarefas


Quais objetos têm a
mesma cor?
O sistema se explica!




PROCEDURAL
Mais rápido (já
possui o script)
Mas fácil de
produzir, em casos
de alguma
complexidade
Tomou o mercado...
Em que ramo pré-existente
da ciência se baseia
KR & R?
Lógica!


Tradição de ~25 séculos de estudos em
representação e algoritmos de raciocínio mecânico
A lógica matemática estuda sistemas de
representação e raciocínio em termos de





Decidibilidade (para representações ou lógicas)
 That is, there exists an algorithm such that for every
formula in the system the algorithm is capable of
deciding in finitely many steps whether the formula is
valid in the system or not.
Completude
Consistência
Complexidade
Monotonicidade
Conceitos básicos:
Conseqüência lógica

Definição informal:


Uma fórmula é uma conseqüência lógica
de um conjunto de fórmulas se sempre
que estas forem verdadeiras aquela
também seja verdadeira.
Definição formal:

Dada uma fórmula H e um conjunto de
hipóteses b, H é conseqüência lógica de b
num sistema de dedução, se existir uma
prova de H a partir de b
Notação de Conseqüência
Lógica e Teorema


Dada uma fórmula H, se H é
conseqüência lógica de um conjunto de
hipóteses b={H1,H2,...Hn}, diz-se que:
 b├ H ou
 {H1,H2,...Hn}├ H
Uma fórmula H é um teorema se existe
uma prova de H que não usa hipóteses
 ├ H
Métodos para determinação
de validade de fórmulas



Tabela verdade
Métodos de dedução
Método da negação ou absurdo
Método da negação ou
absurdo (cont.)

Para provar que H é uma tautologia

Supõe-se inicialmente, por absurdo que



H NÃO é uma tautologia
As deduções desta fórmula levam a um
fato contraditório (ou absurdo)
Portanto, a suposição inicial é falsa e:


H é uma tautologia
(A não-validade de H é um absurdo)
Lógica
História
Origens e caminhos da Lógica
Filosofia
Matemática
Lógica
Computação
Origens e Caminhos da
Lógica a partir da Filosofia
O Combate aos Sofistas

Escolas de pensamento


Sofistas e a dialética


Época rica de idéias e liberdade
O argumento pelo argumento 
Sócrates X Górgias

Método intuitivo: busca da contradição



Negação por absurdo
Platão tentou argumentos morais
Porém, faltava alguém para ordenar
(formalizar) este método

A busca do argumento correto
Origem da Lógica



Na Grécia Antiga, 342 a.C, o filósofo
Aristóteles procurou sistematizar o
conhecimento e o pensamento lógico
Organum (“ferramenta para o correto
pensar”), estabeleceu princípios
Categorias: Conhecimento
(=classificação dos objetos) do mundo
Origem do argumento (formal)


Aristóteles se preocupava com as formas
de raciocínio que, a partir de
conhecimentos considerados verdadeiros,
permitiam obter novos conhecimentos.
Formulação de leis gerais de
encadeamentos de conceitos que levariam
à descoberta de novas verdades


Formalização de padrões de raciocínio
Argumento
Silogismos

Pegar de Walicki
Criações de Aristóteles

Lógica formal


Regras de Inferência
formais


Preservação da verdade
Manipulação de
símbolos


Sentenças lógicas
Conceito de equivalência
Lógica de predicados

Quantificadores




Categorias (ontologias)
Variáveis (em lógica)
Conversões
Orientação a objetos 



...
Generalização
Especialização
b. Stagira, 384BC, d. Chalcis, 322BC
filho de nichomacus, médico de
amyntas, rei da macedônia... professor da academia de platão e tutor de
alexandre, o grande, filho de
amyntas...
o mundo segundo...
aristóteles
What
How
Reality
Knowledge
Substances, other material
things
Substances, other material
things
Substances are combinations of
form and matter
The senses provide all initial
information; reason (1) infers
what is not available to the
senses, (2) grasps the universal
element
http://hume.ucdavis.edu/phi022/matrix.htm
Caminhos da lógica na filosofia


Categorias -> Ontologias
Lógica e Linguagem



Wittgenstein, Searle, ...
Racionais x Empiricistas
...
Ontologias Gerais (ou de topo)

Trazem definições abstratas necessárias para a
compreensão de aspectos do mundo, como tempo,
processos, papéis, espaço, seres, coisas, etc.
[Sowa 99]
Idade Média (séc. XIV)
Concept
Activates
(intention)
Form
“Tank“
[Ogden, Richards, 1923]
Relates to
(extension)
^
Stands for
Referent
?
Origens e Caminhos da Lógica
na Matemática
gottfried wilhelm leibnitz


b. 1 July 1646, Leipzig
d. 14 Nov 1716, Hannover




filho de Catharina Schmuck
e Friedrich Leibniz, que morreu
quando leibniz tinha seis anos.
valores morais e religiosos aprendidos com a mãe:
impacto fundamental na vida e na filosofia
gênio: QI estimado em 205...
contra a vontade dos professores, ganhou acesso à
biblioteca do pai...
 acesso irrestrito à informação quase sempre gera
“subversão”…
Contribuições de Leibnitz



Cálculo proposicional
Mecanização do Cálculo proposicional
...
o calculus ratiocinator
“um” cr… uma álgebra da lógica
O Teorema veio antes da Lógica!




Também iniciou-se na Grécia
Euclides (séc. III), influenciado por Aristóteles
Sistematizou a geometria
Criação (intuitiva) do método axiomático como
guia para resolução de problemas



Aceitar sem demonstrações certas proposições
(axiomas)
Derivar deles as proposições válidas (os teoremas)
Axioma suspeito: retas paralelas

Como prová-lo??
Infinito quase encontrado 


Gauss, Lobatchevski e Riemann
provaram que isso não era possível
Provou-se a “impossibilidade de provar”
algo num sistema


Sistema – idéia de manipulação formal
Geometria de Riemann

Simples substituição deste axioma
Novos métodos na matemática...

A geometria de Euclides descreve bem o
espaço físico


Ninguém pensou em verificar inconsistências
A de Riemann só veio a ter utilidade com
Einstein!


Criação da idéia de modelo
Cada proposição de um sistema precisa ser
verdadeira em relação à estrutura modelada


A Geometria de Euclides modela o espaço físico
A de Riemann modela espaços curvos
Dependências entre modelos

Poincaré, Beltrami e Klein:



Se a geometria euclidiana não tiver
contradições
A de Lobatchevski também não terá!
Hilbert formalizou (axiomatizou) as
geometrias de Euclides e Riemann



“Grundlagen der Geometrie”
Ele iria mais longe...
Como estava a lógica nessa época?
george boole (1815-1864)



Tratamento sistemático da
lógica, com notação
matemática
Ainda não rigorosamente
axiomático
Recusa a idéia de
interpretação
Gottlob Frege




Introduziu o “rigor
matemático e
metodológico” na lógica
(1879)
Manipulação rigorosa de
símbolos
Derivações detalhadas,
embora ainda nãoaxiomáticas
Tabelas-verdade (ao
mesmo tempo que Peirce)
http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Frege.html
Unificando o vocabulário!

In
1879
Frege
published
his
first
major
work,
Begriffsschrift, eine der arithmetischen nachgebildete
Formelsprache des reinen Denkens (Conceptual notation,
a formal language modelled on that of arithmetic, for pure
thought):

In 1879, with extreme clarity, rigour and technical brilliance, he
first presented his conception of rational justification. In effect, it
constitutes perhaps the greatest single contribution to logic ever
made and it was, in any event, the most important advance since
Aristotle. For the first time, a deep analysis was possible of
deductive inferences involving sentences containing multiply
embedded expressions of generality. Furthermore, he presented a
logical system within which such arguments could be perspicuously
represented: this was the most significant development in our
understanding of axiomatic systems since Euclid. {George & Heck}
Hilbert e os Sistemas
axiomáticos






Primeiro sistema de prova formal
A partir de axiomas considerados verdadeiros,
deriva-se (ou não) a prova
Exemplo:
Ax1= A(BA)
Ax2= (A(BC)  ((AB)(AC))
Ax3= (A B)((AB)A)
Exemplo de prova

PP

(P((PP)P))  ((P(PP))(PP))





Ax2 com A=P, B=PP, C=P
P((PP)P), Ax1
(P(PP))(PP), Modus Ponens
(P(PP)), Ax1 com A=P, B=P
PP, Modus Ponens
Um sistema axiomático
estranhíssimo...




Usando apenas o conjunto de conectivos
completo {^ } (nand)
Regra de inferência: A
A ^ (B ^C)
C
Ax1: (A^(B^C))^((A^(C^ A))
^((C^B)^((A^C)^(A^C))))
Conclusão: Sistemas axiomáticos são
complicados de usar e de entender as
provas!!
David Hilbert e suas perguntas

David Hilbert (1862–
1943) propôs 23
problemas, que em sua
opinião ocupariam os
matemáticos pelo século
que se iniciara (e estava
correto!)


2o Congresso
Internacional de
Matemática, Paris, 1900
Ficou mais famoso pelos
problemas que criou do
que pelos que resolveu 
O Manifesto de Hilbert



Na verdade, ele tinha ideais bem mais
ambiciosos...
Lançou um manifesto defendendo a
formalização lógica das áreas de
matemática (como ele próprio fizera
com a geometria)
Se a lógica estivesse resolvida, toda a
matemática (formalizada
apropriadamente) também estaria...
o programa de Hilbert

"...the conviction (which every mathematician shares,
but which no one has as yet supported by a proof)
that every definite mathematical problem must
necessarily be susceptible of an exact settlement,
either in the form of an actual answer to the question
asked, or by the proof of the impossibility of its
solution and therewith the necessary failure of all
attempts."
Vamos às questões
fundamentais…

Hilbert (1928):



is mathematics logically complete?(1)
is mathematics logically consistent?(2)
is mathematics logically decidable?(3)

SURPRESA!

Gödel (1931): NÃO, NÃO…



mathematical logic is incomplete
its consistency can’t be proved within itself
Turing (1936): …e NÃO!


mathematical logic is undecidable
there is no procedure for determining whether a proposition is
provable
A sintaxe levou à semântica!

Teoria de modelos (Tarski)




Sistema: sintaxe, regras de dedução e semântica
Interpretações, ligadas a valores verdade
1944, "The Semantical Concept of Truth and the
Foundations of Semantics," Philosophy and
Phenomenological Research 4: 341-75.
Teoria de provas (Gentzen)


Estudo da estrutura de dedução da lógica
envolvida
Dedução natural, seqüentes
Os pais da semântica
Sistema de Dedução Natural de
Gentzen – regras de negação



De uma derivação de uma contradição (false) a
partir de uma hipótese H, pode-se descartar a
hipótese e inferir H e vice-versa
[H] (I)
|
false
H
[H]
|
false
H
Exercícios: HH e
H H
(E ou RAA)
reductio ad
absurdum
Herbrand (1930)



Uma fórmula válida é verdadeira sob todas as suas
interpretações
Herbrand desenvolveu um algoritmo para encontrar
uma interpretação que pode invalidar uma fórmula!
No entanto, se ela é válida, nenhuma dessas
interpretações pode existir


O algoritmo termina após um número finito de tentativas!
O método de Herbrand é a base para muitos
métodos modernos de prova automática
Breve História de IA


Turing: “Can machines think?”
(Computing Machinery and Intelligence,
50)
Início oficial: Dartmouth College, 56 (2
meses, 10 pessoas  IA!)



Logic Theorist (Newell&Simon)
LISP, 58
Podemos aplicar dedução sem escalas??

General Problem Solver, 59
Não!

Explosão combinatorial, e.g. dos
provadores de teorema(fins dos 60)


Problemas com escalabilidade.
Complexidade (NP-completo, etc) ainda
não formalizada (início dos 70) ->
indústria estruturada
Porque não colou de cara ??




Problemas matemáticos do slide anterior
Embevecimento,
falta de objetividade e
amadorismo dos pesquisadores
Falta de produtos no cotidiano, formando
indústria – porque isso representaria trabalho
“braçal” em Engenharia de Software e testes
de confiabilidade.
Falta de metodologias mais formalizadas
sobre como obter e codificar conhecimento
declarativo.
Algoritmos de prova


Herbrand
Resolução


Tableaux


R. Smullyan 1968
Prolog



J. A. Robinson 1965
Colmerauer 1972
D. H. Warren
NAF
Problemas com Hardware






O processo de inferência não ‘casou’ bem com as
implementações de hardware e software básico,
projetados para programação imperativa e não lógica.
A programação lógica deve tanto quanto possível
explorar concorrência e paralelismo(Ex:PIM,64 MLIPS).
Prolog embora criada em 1972, só popularizou-se em
1977, com as Warren Abstract Machines (WAMs).
Compila num código intermediário e depois executa.
instruções usam registradores e pilhas auxiliares, que a
WAM cria, implementados em C++.
Resultado : performance do nível de C (50 KLIPS).
“IA não dá em nada”

Insucessos



Dreyfuss: O que os computadores não podem fazer


GPS
Perceptrons
Xadrez, entre eles 
Searle e a sala chinesa (80)

Andersson (89): Nós fazemos manipulações formais,
porém biológicas
Sucessos

Sistemas especialistas, 70’s






Dendral
Mycin
Prospector
XCON
...
Agentes inteligentes de hoje!
Raciocínio expressivo em
grande escala



Lógica de descrições [Brachman &
Levesque 1984]
Raciocínio decidível
Web semântica! [Studer& Fensel 1997]
O prof. Studer (AIFB,
Alemanha)...
...fez uma ferramenta para
ontologias...
E propôs a Web Semântica !


Solução anterior: Dotar os sistemas de
inteligência
Solução: Dotar a Internet de inteligência:


Linguagens e padrões para definir páginas
com uma semântica clara e definida
formalmente
Os agentes poderão raciocinar e “conversar”
no contexto desta semântica
Ontologias
Expressividade de DLs

Classes podem ser construídas por:






União
Interseção
Complemento
Enumeração de instâncias
Classes podem ter disjunções
Propriedades podem ter:


transitividade, simetria, atributos inversos
propriedades funcionais

(se P(x,y) ^ P(y,x) => x=y)
Ontologias
OWL- Exemplo





Uma pizza de 4 queijos:
Roquefort  Queijo
Muzzarela  Queijo
...
Pizza4Queijos ≡ Pizza and temCobertura
some Tomate and
temCobertura = 4 Queijo and
temCobertura only (Queijo or Tomate)
Vantagens


Ontologias
Formalização: Não há ambigüidades na
interpretação dessas definições
Expressividade: Não é possível
expressar isso em XML!
Classificação automática por raciocínio



Não é preciso dizer que uma pizza é 4
queijos...
Ao descrevê-la o classificador já infere
isto!
Não é necessário, por exemplo, dizer
quais pizzas são vegetarianas
Bibliografia







Livro KR & R, Brachman & Levesque
Livro do Sowa
Livro de Guilherme Bittencourt
Livro de Michal Walicki
Livro de Carnielli-Epstein
Wikipedia
Slides de Sílvio Meira

Leibnitz e a parte de Filosofia