\documentclass[12pt, a4paper]{article}
 
\newcounter{conta}
\newcounter{conta2}

\hyphenation{geo-gra-fia es-pe-cia-li-za-das e-xem-plo pro-je-to
com-ple-xi-da-de de-sa-pa-re-ce a-bor-da-gem co-mo fa-lhas es-co-lhi-da}

\begin{document}

\vspace*{7cm}
\begin{center}\Huge
Cap\'{\i}tulo 10: Sistemas de Racioc\'{\i}nio L\'ogico
\end{center}

\vfill
\hfill Cap\'{\i}tulo 10: Sistemas de Racioc\'{\i}nio L\'ogico

\pagebreak
\noindent{\LARGE Vantagens da representa\c c\~ao expl\'{\i}cita de conhecimento:}

\begin{itemize}\Large
 \item modularidade
 \item f\'acil experimenta\c c\~ao
 \item f\'acil modifica\c c\~ao
 \item f\'acil explica\c c\~ao do racioc\'{\i}nio
 \item possibilidade de aprendizagem
\end{itemize}

\vspace*{.5cm}
\noindent {\LARGE Tipos de sistemas de racioc\'{\i}nio automatizado:}

\begin{itemize}\Large
 \item Provadores de teoremas, Linguagens de programa\c c\~ao em l\'ogica
 \item Sistemas de produ\c c\~ao
 \item Sistemas de {\em Frames\/} e Redes sem\^anticas
 \item Sistemas de {\em Description logics\/}.
\end{itemize}

\vspace*{.5cm}
\noindent {\LARGE 5 tarefas importantes:}

\begin{itemize}\Large
 \item Adicionar novo fato na BC (TELL).
 \item Dada uma BC e um novo fato, derivar fatos (TELL).
 \item Verificar se consulta segue da BC (ASK).
 \item Verificar se consulta est\'a na BC.
 \item Remover uma senten\c ca da BC.
\end{itemize}

\vfill
\hfill Cap\'{\i}tulo 10: Sistemas de Racioc\'{\i}nio L\'ogico

\pagebreak
\noindent {\LARGE\bf Indexa\c c\~ao, Recupera\c c\~ao e Unifica\c c\~ao}

\vspace*{.5cm}
\noindent {\LARGE Implementa\c c\~ao de senten\c cas e termos:}

\begin{itemize}\Large
 \item Pode haver v\'arias representa\c c\~oes internas para uma senten\c ca.
 \item Tipo b\'asico prev\^e o acesso ao {\bf operador} (principal)  e {\bf argumentos}.

          Exemplo: Seja $c$ a senten\c ca $P(x)\vee Q(x)$; Ent\~ao:
          \begin{enumerate}
           \item[\ ] $\mbox{OP}(c)=\vee$ e $\mbox{ARGS}(c)=[P(x),Q(x)]$.
          \end{enumerate}
\end{itemize}

\vspace*{1cm}
\noindent {\LARGE {\em Store\/} e {\em fetch}}

\begin{itemize}\Large
 \item FETCH: encontrar senten\c cas que unifiquem com a consulta.
 \item ASK: causa infer\^encia com uma s\'erie de FETCHs.
 \item Custo de infer\^encia:
         \begin{itemize}
          \item estrat\'egia de busca usada por ASK;
          \item estruturas de dados para implementar FETCH.
         \end{itemize}
 \item STORE mais simples: armazenar uma lista ou vetor.

         STORE: $O(1)$; FETCH: $O(n)$.         
\end{itemize}

\vfill
\hfill Cap\'{\i}tulo 10: Sistemas de Racioc\'{\i}nio L\'ogico

\pagebreak
\noindent {\LARGE Indexa\c c\~ao por tabela - Exemplo:}

\vspace*{.5cm}
\begin{itemize}\Large
 \item Chave: s\'{\i}mbolos predicativos.
 \item Valor com 4 componentes:
         \begin{itemize}
          \item lista de literais positivos
          \item lista de literais negativos
          \item lista das senten\c cas que concluem o predicado
          \item lista das senten\c cas com o predicado na premissa
         \end{itemize}
\end{itemize}

\vspace*{.2cm}
\noindent {\LARGE Exemplo:}

\begin{enumerate}\large
 \item[\ ] $\mbox{\em Brother}(\mbox{\em Richard},\mbox{\em John})$
 \item[\ ] $\mbox{\em Brother}(\mbox{\em Ted},\mbox{\em Jack})\wedge
                \mbox{\em Brother}(\mbox{\em Jack},\mbox{\em Bobbie})$
 \item[\ ] $\neg\mbox{\em Brother}(\mbox{\em Ann},\mbox{\em Sam})$
 \item[\ ] $\mbox{\em Brother}(x,y)\Rightarrow\mbox{\em Male}(x)$
 \item[\ ] $\mbox{\em Brother}(x,y)\wedge\mbox{\em Male}(y)\Rightarrow\mbox{\em Brother}(y,x)$
 \item[\ ] $\mbox{\em Male}(\mbox{\em Jack})\wedge\mbox{\em Male}(\mbox{\em Ted})\wedge
               \ldots\wedge\neg\mbox{\em Male}(\mbox{\em Ann})$
\end{enumerate}

\vspace*{2cm}
\begin{center}
Figura 10.1
\end{center}

\vfill
\hfill Cap\'{\i}tulo 10: Sistemas de Racioc\'{\i}nio L\'ogico

\pagebreak
\noindent {\LARGE Indexa\c c\~ao baseada em \'arvore:}

\vspace*{.5cm}
\noindent {\LARGE Indexar, para cada predicado, tamb\'em em argumento:}

\vspace*{3.5cm}
\begin{center}
Figura 10.2
\end{center}

\vspace*{3.5cm}
\begin{itemize}\Large
 \item Aplic\'avel quando h\'a muitas cl\'ausulas para cada s\'{\i}mbolo.
 \item Problema: quando o argumento \'e vari\'avel.
 \item \'Indices combinados podem ocupar muito espa\c co.
 \item Indexa\c c\~ao cruzada: v\'arios \'{\i}ndices (ex: um para cada arg.),
          recuperar pelo mais ``promissor'' (menos cl\'ausulas).
\end{itemize}

\vfill
\hfill Cap\'{\i}tulo 10: Sistemas de Racioc\'{\i}nio L\'ogico

\pagebreak
\noindent {\LARGE O algoritmo de unifica\c c\~ao:}

\vspace*{5cm}
\begin{center}
Figura 10.3
\end{center}

\vfill
\hfill Cap\'{\i}tulo 10: Sistemas de Racioc\'{\i}nio L\'ogico

\pagebreak
\noindent {\LARGE\bf Sistemas de Programa\c c\~ao em L\'ogica}

\vspace*{1cm}
\noindent {\LARGE Rela\c c\~ao entre l\'ogica e algoritmos: \\
(R. Kowalski)}

\vspace*{.5cm}
\[\mbox{\Large\em Algoritmo}\,\, =\,\, \mbox{\Large\em L\'ogica}\,\, +\,\, \mbox{\Large\em Controle.}\]

\vspace*{.5cm}
\noindent {\LARGE Caracter\'{\i}sticas de Prolog:}

\begin{itemize}\Large
 \item Um programa \'e uma sequ\^encia de senten\c cas; vari\'aveis s\~ao universais.
 \item Senten\c cas s\~ao cl\'ausulas de Horn.
 \item Termos podem ser constantes, vari\'aveis ou s\'{\i}mbolos funcionais.
 \item Consultas podem ter conjun\c c\~oes, disjun\c c\~oes, vari\'aveis e s\'{\i}mbolos
         funcionais.
 \item Nega\c c\~ao por falha.
 \item Termos sintaticamente distintos referem-se a objetos distintos.
 \item Muitos predicados embutidos (aritm\'etica, E/S, etc.)
\end{itemize}

\vfill
\hfill Cap\'{\i}tulo 10: Sistemas de Racioc\'{\i}nio L\'ogico

\pagebreak
\noindent {\LARGE Implementa\c c\~ao de Prolog:}

\begin{itemize}\Large
 \item {\em Backward chaining\/} com busca em profundidade.
 \item Ordem de busca: ordem de escrita; esquerda para a direita.
 \item O teste de ocorr\^encia \'e omitido na rotina de unifica\c c\~ao.
 \item Execu\c c\~ao em 2 modos: interpretado ou executado.
\end{itemize}

\vspace*{.5cm}
\noindent {\LARGE Algumas sofistica\c c\~oes:}

\begin{itemize}\Large
 \item Paralelismo OU.
 \item Paralelismo E.
 \item PIM do Projeto de 5a. gera\c c\~ao: 64 milh\~oes de LIPS.
 \item Programa\c c\~ao em l\'ogica com restri\c c\~oes (CLP).
 \item Tipos.
\end{itemize}

\vfill
\hfill Cap\'{\i}tulo 10: Sistemas de Racioc\'{\i}nio L\'ogico

\pagebreak
\noindent {\LARGE Controle avan\c cado:}

\begin{itemize}\Large
 \item Ordena\c c\~ao da consulta. Exemplo:

         \[\mbox{\em Income}(s,i)\wedge\mbox{\em Casado}(s,p)\wedge\mbox{\em Occupation}(p,\mbox{\em President})\]
 \item {\em Backjumping}. Exemplo: determine as pessoas da mesma cidade que o presidente.

         \[\mbox{\em Resident}(p,t)\wedge\mbox{\em Resident}(x,p)\wedge\mbox{\em Resident}(p,\mbox{\em President})\]
 \item {\em Dependency-directed backtracking\/}: memoriza as falhas para que n\~ao sejam repetidas em outros pontos.
 \item Lembrar o que j\'a foi deduzido anteriormente (lemas).
\end{itemize}

\vfill
\hfill Cap\'{\i}tulo 10: Sistemas de Racioc\'{\i}nio L\'ogico

\pagebreak
\noindent {\LARGE\bf Provadores de Teoremas}

\vspace*{.5cm}
\noindent {\LARGE Diferen\c cas b\'asicas com rela\c c\~ao a programa\c c\~ao em l\'ogica:}

\begin{itemize}\Large
 \item Lida com LPO completa.
 \item Estrat\'egia de controle por conta do sistema.
\end{itemize}

\vspace*{.5cm}
\noindent {\LARGE Um exemplo de provador - OTTER:}

\begin{itemize}\Large
 \item O conhecimento \'e dividido pelo usu\'ario em 4 partes:
       \begin{itemize}
        \item Um {\bf conjunto de suporte} (CS).
        \item Um conjunto de {\bf axiomas utiliz\'aveis} (AU).
        \item Um conjunto de {\bf demoduladores}.
        \item Um conjunto de par\^ametros e cl\'asulas que definem a estrat\'egia de
              controle.
       \end{itemize}
 \item Em cada passo resolve uma  cl\'ausula de CS com uma de AU.
 \item Usa uma busca do tipo {\em best-first\/} (cada cl\'ausula tem um ``peso'').
\end{itemize}

\vspace*{.5cm}
\noindent {\LARGE Um outro exemplo - PTTP:}

\begin{itemize}\Large
 \item Extens\~ao de Prolog para LPO completa: teste de ocorr\^encia e contrapositivas.
 \item {\em Iterative deepening\/} ao inv\'es de {\em depth first\/}.
 \item Regras: expans\~ao e {\em redu\c c\~ao\/}.
\end{itemize}

\vfill
\hfill Cap\'{\i}tulo 10: Sistemas de Racioc\'{\i}nio L\'ogico

\pagebreak
\noindent {\LARGE\bf Sistemas de Produ\c c\~ao {\em forward-chaining}}

\vspace*{1cm}
\begin{itemize}\Large
 \item Regras do tipo condi\c c\~ao-a\c c\~ao.
 \item {\bf Mem\'oria de trabalho}: literais  positivos sem vari\'aveis.
 \item {\bf  Mem\'oria de regras}: com regras da forma
       \[p_1\wedge p_2\wedge\ldots\Rightarrow \mbox{\em a\c c\~ao}_1\wedge
         \mbox{\em a\c c\~ao}_2\wedge\ldots\]
       $\mbox{\em a\c c\~ao}_i$: adicionar ou deletar elemento na mem\'oria de trabalho,
       imprimir, etc.
 \item Em cada ciclo de execu\c c\~ao:
       \begin{itemize}
        \item fase de {\bf casamento}: determina regras com lado esquerdo satisfeito;
        \item fase de {\bf resolu\c c\~ao de conflito}: que regra deve ser aplicada;
        \item fase de {\bf a\c c\~ao}: execu\c c\~ao das a\c c\~oes da regra escolhida.
       \end{itemize}
\end{itemize}

\vspace*{.5cm}
\noindent {\LARGE Casamento:}

\begin{itemize}\Large
 \item Algoritmo RETE e varia\c c\~oes.
\end{itemize}

\vfill
\hfill Cap\'{\i}tulo 10: Sistemas de Racioc\'{\i}nio L\'ogico

\pagebreak
\noindent {\LARGE Resolu\c c\~ao de conflitos:}

\begin{itemize}\Large
 \item {\bf N\~ao duplica\c c\~ao}: n\~ao executar a mesma regra com os mesmos argumentos
       outra vez.
 \item {\bf Rec\^encia}: preferir regras que referenciam elementos mais recentes da mem\'oria
       de trabalho.
 \item {\bf Especificidade}: preferir regras mais espec\'{\i}ficas. Exemplo:
       \begin{enumerate}
        \item[\ ] $\mbox{\em mam\'{\i}fero}(x)\Rightarrow \mbox{\underline{add}}\,\,
                   \mbox{\em pernas}(x,4)$
        \item[\ ] $\mbox{\em mam\'{\i}fero}(x)\wedge\mbox{\em humano}(x)\Rightarrow
                   \mbox{\underline{add}}\,\, \mbox{\em pernas}(x,2)$
       \end{enumerate}
 \item {\bf Prioridade de opera\c c\~ao}: preferir a\c c\~oes mais priorit\'arias. 
\end{itemize}

\vspace*{.5cm}
\noindent {\LARGE Uso pr\'atico:}

\begin{itemize}\Large
 \item Sistemas especialistas.
 \item Arquiteturas cognitivas.
\end{itemize}

\vfill
\hfill Cap\'{\i}tulo 10: Sistemas de Racioc\'{\i}nio L\'ogico

\pagebreak
\noindent {\LARGE\bf Sistemas de {\em Frames} e Redes Sem\^anticas}

\vspace*{1cm}
\noindent {\LARGE L\'ogica expressa por meio de nodos e arestas. Como em Prolog:}

\begin{itemize}\Large
 \item visualiza\c c\~ao f\'acil das infer\^encias poss\'{\i}veis;
 \item linguagem de consultas simples.
\end{itemize}

\vspace*{1cm}
\noindent {\LARGE Sintaxe e sem\^antica de rede sem\^anticas:}

\begin{itemize}\Large
 \item Concentra\c c\~ao em {\bf categorias de objetos} e rela\c c\~oes entre elas.

         Exemplo: $\mbox{gatos}\,\,\stackrel{\subset}{\longrightarrow}\,\,\mbox{mam\'{\i}feros}$

         Em LPO: $\forall x[\mbox{gato}(x)\rightarrow\mbox{mam\'{\i}fero}(x) ]$

 \item {\bf Sem\^antica} \'e mais importante que nota\c c\~ao (sintaxe).

 \item Rede sem\^antica favorece uma vis\~ao do conhecimento, e tamb\'em sua
         implementa\c c\~ao, centradas nos objetos e categorias de objetos.

 \item {\bf Heran\c ca de propriedades}.

\end{itemize}

\vfill
\hfill Cap\'{\i}tulo 10: Sistemas de Racioc\'{\i}nio L\'ogico

\pagebreak
\noindent {\LARGE Rede de {\em frames} $\times$ L\'ogica; um exemplo:}

\vspace*{6cm}
\begin{center}
Figura 10.7
\end{center}

\vspace*{6cm}
\noindent {\LARGE Tipos de arestas e seus significados:}

\vspace*{2.5cm}
\begin{center}
Figura 10.8
\end{center}

\vfill
\hfill Cap\'{\i}tulo 10: Sistemas de Racioc\'{\i}nio L\'ogico

\pagebreak
\noindent {\LARGE Heran\c ca com exce\c c\~oes:}

\begin{itemize}\Large
 \item Um valor {\bf default} pode ser sobrepujado por uma exce\c c\~ao.

         Exemplo:
         \begin{enumerate}
          \item[\ ] $\mbox{Rel}(\mbox{Legs},\mbox{Mammals},4)$
          \item[\ ] $\mbox{Bats}\subset\mbox{Mammals}$
          \item[\ ] $\mbox{Rel}(\mbox{Legs},\mbox{Bats},2)$
         \end{enumerate}
 \item Em LPO n\~ao \'e t\~ao simples\ldots
\end{itemize}

\vspace*{1cm}
\noindent {\LARGE Heran\c ca m\'ultipla:}

\begin{itemize}\Large
 \item Possibilidade de conflito. Exemplo:

\vspace*{3cm}
\begin{center}  \normalsize
Figura 10.9
\end{center}

\end{itemize}

\hfill Cap\'{\i}tulo 10: Sistemas de Racioc\'{\i}nio L\'ogico

\pagebreak
\noindent {\LARGE Monotonismo:}

\begin{itemize}\Large
 \item $\mbox{\bf se }\,\,\mbox{KB}\,\,\vdash \,\,P\,\,\,
           \mbox{\bf ent\~ao}\,\,\, \mbox{KB}\wedge S\,\,\vdash\,\,P$

 \item Heran\c ca $\Longrightarrow$ {\bf n\~ao monotonismo}.
\end{itemize}



\end{document}





