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

\hyphenation{ha-bi-li-da-de 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 to-ma-da su-ces-so
in-te-li-gen-tes a-gen-te co-nhe-ci-men-to ra-i-nhas e-fei-tos
al-go-rit-mo o-pe-ra-do-res ta-bu-lei-ro co-mo ne-nhu-ma co-lu-na
cons-tan-te}

\begin{document}

\vspace*{9cm}
\begin{center} \LARGE\bf Cap\'{\i}tulos 6: Agentes L\'ogicos
\end{center}

\vfill
\ 

\pagebreak
\noindent{\Huge\bf Agente Baseado em Conhecimento}

\vspace*{1cm}
\begin{itemize} \LARGE
 \item BC: conjunto de {\em senten\c cas\/} de uma {\em linguagem formal\/}
       ({\bf linguagem para representa\c c\~ao de conhecimento}).
 \item {\bf M\'aquina de infer\^encia}: algoritmo geral para infer\^encia.
\end{itemize}

\vspace*{1cm}
\noindent{\LARGE\bf Abordagem para intera\c c\~ao com a BC:}

\begin{itemize}\LARGE
 \item TELL: introduzir novo conhecimento na BC.
 \item ASK: consultar a BC.
\end{itemize}

\vspace*{1cm}
\noindent{\LARGE Um agente baseado em conhecimento, gen\'erico:}

\vspace*{3cm}
\begin{center}
 Figura 6.1
\end{center}

\vfill
\hfill Agentes L\'ogicos

\pagebreak
\noindent{\LARGE\bf Um agente deve ser capaz de:}

\vspace*{.5cm}
\begin{itemize} \Large
 \item Representar estados, a\c c\~oes, etc.
 \item Incorporar novos est\'{\i}mulos.
 \item Atualizar as representa\c c\~oes internas do mundo.
 \item Deduzir propriedades ``escondidas'' do mundo.
 \item Deduzir as a\c c\~oes a serem executadas.
\end{itemize}

\vspace*{1cm}
\noindent{\LARGE\bf Um agente baseado em conhecimento pode ser descrito em 3
n\'{\i}veis:}

\vspace*{.5cm}
\begin{itemize} \Large
 \item {\bf N\'{\i}vel de conhecimento:} o que o agente sabe. Exemplo: pode-se
       dizer que um agente motorista de t\'axi {\em sabe que a ponte Rio-Niter\'oi
       liga a cidade do Rio de Janeiro \`a cidade Niter\'oi\/}.
 \item {\bf N\'{\i}vel l\'ogico:} o que o agente sabe codificado em senten\c cas.
       Exemplo: $\mbox{\em Ponte\/}(\mbox{\em PRN\/},\mbox{\em Rio\/},
         \mbox{\em Niteroi\/})$.
 \item {\bf N\'{\i}vel de implementa\c c\~ao:} representa\c c\~ao f\'{\i}sica das
       sente\c cas do n\'{\i}vel l\'ogico. Exemplo: \[\mbox{\em Ponte\/}
       (\mbox{\em PRN\/},\mbox{\em Rio\/}, \mbox{\em Niteroi\/})\] implementada
       colocando-se um ``1'' em uma tabela tridimensional...
\end{itemize}

\vfill
\hfill Agentes L\'ogicos

\pagebreak
\noindent{\Huge\bf O Mundo do Wumpu}

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

\vspace*{4.5cm}
\noindent{\LARGE\bf Situa\c c\~ao inicial do Ambiente:}
\begin{itemize}\Large
 \item O agente come\c ca na {\em sala inicial\/} de frente p/ direita.
 \item As salas do ouro e do wumpu s\~ao escolhidas aleatoriamente.
 \item Cada sala pode ter um buraco mortal (prob. 0,2).
 \item Salas ao lado do wumpu t\^em cheiro.
 \item Salas ao lado de um buraco t\^em brisa.
 \item Uma sala tem brilho se, e somente se, tem ouro.
 \item O agente tem uma \'unica flexa.
\end{itemize}

\vfill
\hfill Agentes L\'ogicos

\pagebreak
\noindent{\LARGE\bf Meta:} {\Large pegar o ouro, voltar ao in\'{\i}cio e sair.}

\vspace*{.5cm}
\noindent{\LARGE\bf A\c c\~oes:}
\begin{itemize}\Large
 \item {\em esquerda\/}: o agente gira 90 graus para a esquerda.
 \item {\em direita\/}: o agente gira 90 graus para a direita.
 \item {\em anda\/}: o agente vai em frente para pr\'oxima sala ou bate na parede;
                     se sala cont\'em buraco ou wumpu, o agente morre.
 \item {\em pega\/}: o agente pega o que estiver na sala onde ele est\'a.
 \item {\em larga\/}: o agente larga o que estiver segurando no lugar em que ele est\'a.
 \item {\em atira\/}: atira a flexa para frente em linha reta, se estiver com ela; a
                      flexa vai at\'e acertar e matar o wumpu, ou at\'e bater na parede;
                      se o wumpu morrer, ele solta um grito que pode ser ouvido em todas
                      as salas.
 \item {\em sai\/}: deixa a caverna; s\'o funciona na sala inicial.
\end{itemize}

\vspace*{.5cm}
\noindent{\LARGE\bf Est\'{\i}mulos:} {\Large cheiro, brisa, brilho, trombada, grito.}

\vfill
\hfill Agentes L\'ogicos

\pagebreak
\noindent{\LARGE\bf Caracter\'{\i}sticas do mundo do wumpu:}

\begin{itemize}\Large
 \item Determin\'{\i}stico: \'unico estado sucessor ao atual.
 \item N\~ao totalmente acess\'{\i}vel: apenas percep\c c\~ao {\em local\/}.
 \item Est\'atico: o wumpu e os buracos n\~ao se movimentam.
 \item Discreto: conjuntos de est\'{\i}mulos e de a\c c\~oes finitos.
\end{itemize}

\vspace*{.5cm}
\noindent{\LARGE\bf Um exemplo:}


\vspace*{8cm}
\begin{center}
 Figuras 6.3 e 6.4
\end{center}

\vfill
\hfill Agentes L\'ogicos

\pagebreak
\noindent{\Huge\bf Representa\c c\~ao, racioc\'{\i}nio e l\'ogica}

\vspace*{1cm}
\noindent{\LARGE\bf L\'ogica:} {\Large linguagem formal para representa\c c\~ao
de conhecimento.}

\begin{itemize}\Large
 \item {\bf Sintaxe:} senten\c cas da linguagem.
 \item {\bf Sem\^antica:} significado das senten\c cas.
 \item {\bf Infer\^encia:} dedu\c c\~ao de (novas) senten\c cas.
\end{itemize}

\vspace*{.5cm}
\noindent{\LARGE Exemplo: linguagem da aritm\'etica}

\begin{itemize}\Large
 \item $x+2\geq y$ \'e senten\c ca; $x2+y\geq$ n\~ao \'e.
 \item $x+2\geq y$ \'e verdadeiro sse $x+2$ n\~ao \'e menor que $y$.
 \item Dado que $x+2\geq y$, infere-se que $x\geq y-2$.
\end{itemize}


\vspace*{1cm}
\noindent{\LARGE\bf A representa\c c\~ao e a realidade:}

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

\vfill
\hfill Agentes L\'ogicos

\pagebreak
\noindent{\LARGE\bf Consequ\^encia l\'ogica}

\vspace*{1cm}
{\LARGE
\[\mbox{BC}\models\alpha\]
}

\noindent{\LARGE $\alpha$ \'e {\bf consequ\^encia l\'ogica} de BC}

\vspace*{.3cm}
\noindent{\LARGE\em se, e somente se,}

\vspace*{.3cm}
\noindent{\LARGE $\alpha$ \'e verdadeira sempre que BC \'e verdadeira.}

\vspace*{1cm}
\noindent{\LARGE Exemplos:}

\vspace*{.5cm}
{\LARGE
\[\{x+2\geq y,\ldots\}\models x\geq y-2\]
}

\vspace*{.5cm}
{\LARGE
\[\{p\rightarrow q, p\} \models q\]
}

\vfill
\hfill Agentes L\'ogicos

\pagebreak
\noindent{\LARGE\bf Infer\^encia}

\vspace*{1cm}
{\LARGE
\[\mbox{BC}\vdash_i\alpha\]
}

\noindent{\LARGE $\Rightarrow$ $\alpha$ \'e {\bf deriv\'avel} de BC pelo procedimento $i$.}

\vspace*{.5cm}
\begin{itemize} \LARGE
 \item {\bf Corre\c c\~ao} ({\em soundness\/}): $i$ \'e correto quando
       \[\mbox{se BC } \vdash_i\alpha \mbox{ ent\~ao BC }\models\alpha\mbox{.}\]
\end{itemize}

\vspace*{.5cm}
\begin{itemize} \LARGE
 \item {\bf Completude}: $i$ \'e completo quando
       \[\mbox{se BC } \models\alpha \mbox{ ent\~ao BC }\vdash_i\alpha\mbox{.}\]
\end{itemize}

\vspace*{1cm}
\noindent{\LARGE {\em Adiantando\/}: Ser\'a vista uma l\'ogica, chamada 
\begin{center}{\bf l\'ogica de primeira ordem},\end{center}

\begin{itemize}
 \item que \'e expressiva o bastante para se dizer ``quase tudo'' que se necessite;
 \item para a qual existe um procedimento de infer\^encia correto e completo.
\end{itemize}
}

\vfill
\hfill Agentes L\'ogicos

\pagebreak
\noindent{\LARGE Uma l\'ogica consta de:}

\begin{enumerate} \Large
 \item Uma linguagem formal com

       \begin{itemize}
        \item Sintaxe
        \item Sem\^antica (teoria de modelos)
       \end{itemize}

 \item Uma {\bf teoria da prova}: conjunto de {\bf regras de infer\^encia}.
\end{enumerate}

\vspace*{1cm}
\noindent{\LARGE Exemplos de linguagens formais:}

\vspace*{3cm}
\begin{center}
 Figura 6.7
\end{center}

\vfill
\hfill Agentes L\'ogicos

\pagebreak
\noindent{\Huge\bf L\'ogica Proposicional}

\vspace*{1cm}
\noindent{\LARGE\bf Sintaxe:}

\begin{itemize}\Large
 \item {\bf V} e {\bf F} s\~ao senten\c cas.
 \item $P,Q,R,P_1,Q_1,R_1,P_2,\ldots$ s\~ao senten\c cas.
 \item Se $S$ \'e uma senten\c ca, $\neg S$ \'e senten\c ca.
 \item Se $S$ \'e uma senten\c ca, $(S)$ \'e senten\c ca.
 \item Se $S_1$ e $S_2$ s\~ao senten\c cas, ent\~ao s\~ao senten\c cas:
       \begin{enumerate}
        \item[\ ] $S_1\wedge S_2$
        \item[\ ] $S_1\vee S_2$
        \item[\ ] $S_1\Rightarrow S_2$
        \item[\ ] $S_1\Leftrightarrow S_2$
       \end{enumerate}
\end{itemize}

\vspace*{.5cm}
\noindent{\LARGE Usando gram\'atica:}

\vspace*{4cm}
\begin{center}
 Figura 6.8
\end{center}

\vfill
\hfill Agentes L\'ogicos

\pagebreak
\noindent{\LARGE\bf Sem\^antica:}

\vspace*{.5cm}
\noindent{\Large {\bf Modelo:} especifica V/F para cada s\'{\i}mbolo proposi\-cio\-nal.}

\vspace*{.5cm}
\noindent{\Large Exemplo:}

\begin{center} \Large
\begin{tabular}{ccc}
$P$ & $Q$ & $R$ \\
V & V & F
\end{tabular}
\end{center}

\vspace*{1cm}
\noindent{\LARGE Tabela da verdade para os conectivos:}

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

\vspace*{2cm}
\noindent{\LARGE Senten\c ca {\bf v\'alida}: V para todo modelo.}

\vspace*{1cm}
\noindent{\LARGE Exemplo:}

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

\vfill
\hfill Agentes L\'ogicos

\pagebreak
\noindent{\LARGE\bf Infer\^encia por enumera\c c\~ao}

\vspace*{1cm}
\noindent{\LARGE\em Teorema da dedu\c c\~ao:}

\vspace*{.4cm}
\noindent{\LARGE $\mbox{BC}\models \alpha$ se, e somente se, 
$\mbox{BC}\Rightarrow\alpha$ \'e v\'alida.}

\vspace*{1cm}
\noindent{\LARGE Exemplo:}

\vspace*{.5cm}
\noindent{\Large Sejam:}

\begin{itemize}\Large
 \item $P$: h\'a um wumpu em [1,3];
 \item $H$: h\'a um wumpu em [2,2];
\end{itemize}

\vspace*{.5cm}
\noindent{\Large Ent\~ao: $(P\vee H)\wedge \neg H \models P$, pois
$((P\vee H)\wedge \neg H) \Rightarrow P$ \'e v\'alida.}

\vspace*{2cm}
\noindent{\LARGE {\bf Abordagem dedutiva}: usa regras de infer\^encia.}

\vfill
\hfill Agentes L\'ogicos

\pagebreak
\noindent{\LARGE\bf Formas normais importantes:}

\begin{itemize}\Large
 \item {\bf Forma normal conjuntiva}: conjun\c c\~ao de disjun\c c\~oes de literais
       (cl\'ausulas).

       \vspace*{.3cm}
       Exemplo: $(A\vee\neg B)\wedge(B\vee\neg C\neg D)$
 \item {\bf Forma normal disjuntiva}: disjun\c c\~ao de conjun\c c\~oes de literais
       (termos).

       \vspace*{.3cm}
       Exemplo: $(A\wedge B)\vee(A\wedge \neg C)\vee\neg D$

 \item {\bf Cl\'ausulas de Horn}: cl\'ausulas com no m\'aximo 1 literal positivo.

       \vspace*{.3cm}
       Exemplo: $(A\vee \neg B)\wedge(B\vee \neg C\vee\neg D)$
\end{itemize}

\vfill
\hfill Agentes L\'ogicos

\pagebreak
\noindent{\LARGE\bf Dois m\'etodos de prova:}

\begin{itemize} \Large
 \item {\bf Model checking:} 

       \begin{itemize}
        \item enumera\c c\~ao (tabela da verdade);
        \item correto e completo.
       \end{itemize}
 \item {\bf Regras de infer\^encia:} 

       \begin{itemize}
        \item gera\c c\~ao de senten\c cas por regras de infer\^encia;
        \item existem proc's corretos e completos;
        \item proc's usam regras de infer\^encia como operadores em um
              algoritmo de pesquisa padr\~ao.
       \end{itemize}
\end{itemize}

\vspace*{1cm}
\noindent{\LARGE\bf Exemplos de regras de infer\^encia:}

\begin{itemize} \Large
 \item {\bf Resolu\c c\~ao} (p/ FNC): completo para l\'ogica proposicional.

       \vspace*{.3cm}
       de $\alpha\vee\beta$ e $\neg\beta\vee \gamma$, concluir $\alpha\vee \gamma$.

 \item {\bf Modus Ponens} (p/ Horn): completo para BCs Horn.

       \vspace*{.3cm}
       de $\alpha_1,\dots,\alpha_n$ e $\alpha_1\wedge\cdots\wedge\alpha_n\Rightarrow\beta$,
       concluir $\beta$.

\end{itemize}

\vfill
\hfill Agentes L\'ogicos

\pagebreak
\noindent{\Huge\bf Um Agente para o Mundo do Wumpu}

\vspace*{3cm}
\begin{center}
 Figura 6.15
\end{center}

\vspace*{3cm}
\noindent{\LARGE\bf A Base de Conhecimento:}

\vspace*{.5cm}
\begin{center} \Large
\begin{tabular}{rrr}
 $\neg \mbox{Ch11}$ & $\neg \mbox{Ch21}$ & $\mbox{Ch12}$ \\
 $\neg \mbox{Br11}$ & $\mbox{Br21}$ & $\neg \mbox{Br12}$ \\
etc... \\
\end{tabular}
\end{center}

\vspace*{.5cm}
\begin{enumerate} \Large
 \item[$R_1$:] $\neg \mbox{Ch11}\Rightarrow \neg \mbox{Wu11}\wedge\neg\mbox{Wu21}
                 \wedge\neg\mbox{Wu12}$
 \item[$R_2$:] $\neg \mbox{Ch21}\Rightarrow \neg \mbox{Wu11}\wedge\neg\mbox{Wu21}
                 \wedge\neg\mbox{Wu22}\wedge\neg\mbox{Wu31}$
 \item[$R_3$:] $\neg \mbox{Ch12}\Rightarrow \neg \mbox{Wu11}\wedge\neg\mbox{Wu12}
                 \wedge\neg\mbox{Wu22}\wedge\neg\mbox{Wu13}$
 \item[\ ] etc... 
 \item[$R_4$:] $\mbox{Ch12}\Rightarrow \mbox{Wu13}\vee\mbox{Wu12}\vee\mbox{Wu22}
                 \vee\mbox{Wu11}$
 \item[\ ] etc...
\end{enumerate}

\vfill
\hfill Agentes L\'ogicos

\pagebreak
\noindent{\LARGE\bf Encontrando o Wumpu:}

\begin{enumerate} \Large
 \item[1.] $\neg \mbox{Wu11}\wedge\neg\mbox{Wu21}\wedge\neg\mbox{Wu12}$

             (MP $R_1$, $\neg \mbox{Ch11}$)

 \item[2.] $\neg \mbox{Wu11}$ \hspace*{3mm} $\neg\mbox{Wu21}$ \hspace*{3mm} $\neg\mbox{Wu12}$

            (El$\wedge$ 1)

 \item[3.] $\neg \mbox{Wu22}$ \hspace*{3mm} $\neg\mbox{Wu21}$ \hspace*{3mm} $\neg\mbox{Wu31}$

            (MP $R_2$, $\neg \mbox{Ch21}$ e El$\wedge$)

 \item[4.] $\mbox{Wu13}\vee\mbox{Wu12}\vee\mbox{Wu22}\vee\mbox{W11}$

             (MP $R_4$, $\mbox{Ch12}$)

 \item[5.] $\mbox{Wu13}\vee\mbox{Wu12}\vee\mbox{Wu22}$

             (Res $4$, $\neg\mbox{Wu11}$ de 2)

 \item[6.] $\mbox{Wu13}\vee\mbox{Wu12}$

             (Res $5$, $\neg\mbox{Wu22}$ de 3)

 \item[7.] \framebox{$\mbox{Wu13}$}

             (Res $6$, $\neg\mbox{Wu12}$ de 2)
\end{enumerate}

\vspace*{1cm}
\noindent{\LARGE\bf Traduzindo conhecimento em a\c c\~ao:}

\begin{enumerate} \Large
 \item[\ ] $\mbox{Ag11}\wedge\mbox{Leste}\wedge\mbox{Wu21}\Rightarrow\neg Anda$
 \item[\ ] etc...
\end{enumerate}

\vfill
\hfill Agentes L\'ogicos

\pagebreak
\noindent{\LARGE\bf Problema para L\'ogica Proposicional:}

\vspace*{.5cm}
\begin{itemize}\Large
 \item N\~ao h\'a como dizer: {\em Que a\c c\~ao deve ser executada?}
\end{itemize}

\vspace*{1cm}
\noindent{\LARGE\bf Agente baseado em conhecimento com L\'ogica Proposicional:}

\vspace*{3cm}
\begin{center}
 Figura 6.16
\end{center}

\vfill
\hfill Agentes L\'ogicos


\end{document}

