Fundamentos da logicas

Cap´ ıtulo 1

Fundamentos da l´gica matem´tica o a
1.1 Introdu¸˜o ca

A resolu¸ao ´ uma regra de inferˆncia apropriada para dedu¸ao autom´tica mecˆnica. Foi precisamente c˜ e e c˜ a a no contexto de dedu¸ao autom´tica que Robinson desenvolveu o seu princ´ c˜ a ıpio de resolu¸ao, publicado c˜ em 1965. A id´ia de que a l´gica de primeira-ordem poderia ser usada como uma linguagem de e o programa¸ao foi revolucion´ria, j´ que at´ 1972 a l´gica tinha sido considerada apenas como uma c˜ a a e o linguagem de especifica¸ao ou declara¸ao. Kowalski mostra que a l´gica possui uma interpreta¸ao c˜ c˜ o c˜ procedimental o que a faz efetiva como uma linguagem de programa¸ao. Em resumo, uma cl´usula c˜ a de programa A ← B1 , . . . , Bn ´ observada como uma defini¸ao de procedimento. Se ← C 1 , . . . , Ck ´ e c˜ e um “objetivo” ent˜o cada Cj (1 ≤ j ≤ k) ´ considerado como um chamado a um procedimento. Um a e programa ´ executado apresentando um objetivo inicial. Se o objetivo num momento da computa¸ao e c˜ ´ e ← C1 , . . . , C k (1.1)

um passso na execu¸ao consiste numa unifica¸ao de algum C j (1 ≤ j ≤ k) com a cabe¸a de uma c˜ c˜ c cl´usula de programa A ← B1 , . . . , Bn . Assim, o objetivo (1.1) ´ reduzido a a e (← C1 , . . . , Cj−1 , B1 , . . . , Bn , Cj+1 , . . . , Ck )θ, onde θ ´ a substitui¸ao da unifica¸ao de A e C j . A execu¸ao termina quando o objetivo vazio ´ atingido. e c˜ c˜ c˜ e A id´ia fundamental de Kowalski ´ que um algoritmo consiste de dois componentes distintos: e e - l´gica e o - controle O componente l´gico estabelece o que o programa deve resolver e o componente de cono trole como deve resolvˆ-lo. Em termos gerais, uma linguagem l´gica de programa¸ao deveria prover e o c˜ mecanismos para especificar cada um dos componentes. N˜o obstante, considera-se ideal liberar o a programador da especifica¸ao do componente de controle; fato este que ainda n˜o ´ poss´ com os c˜ a e ıvel 9

10

´ ´ Cap´ ıtulo 1 Fundamentos da logica matematica

atuais sistemas