\documentclass[12pt, a4paper]{report}

\usepackage[portuguese]{babel}
\usepackage{fullpage}

\newcounter{conta}

\begin{document}
 
\noindent {\it TECC: L\'ogica Aplicada a Computa\c c\~ao}
\hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2003 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Lista de exerc\'{\i}cios preparat\'oria para a Segunda Prova}

\begin{enumerate}
 \item Dado o programa em Prolog
       \begin{tabbing}
        xxxx\={\tt q(X,f(X))} \={\tt :- q(X,X).} \kill
            \>{\tt p}         \>{\tt :- q(X,X).} \\
            \>{\tt q(X,f(X))} \>{\tt :- q(X,X).}
       \end{tabbing}
       e a cl\'ausula meta
       \begin{tabbing}
        xxxx\= \kill
            \>{\tt p}
       \end{tabbing}
       o que acontece se for tentada uma refuta\c c\~ao sem o teste de
       ocorr\^encia?

 \item Defina em Prolog as seguintes rela\c c\~oes (procedimentos):
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item {\tt ultimo(X,L)} de forma que {\em {\tt X} \'e o
              \'ultimo elemento da lista {\tt L}}.
        \item {\tt tampar(L)} de forma que {\em a lista {\tt L} tem
              tamanho par}.
        \item {\tt palindromo(L)} de forma que {\em a lista {\tt L} seja
              pal\'{\i}ndromo}.
        \item {\tt desloc(L1,L2)} de forma que {\em {\tt L2} \'e a
              lista {\tt L1} ``deslocada rotativamente'' de um elemento
              para a esquerda}. Por exemplo, a meta {\tt ?- desloc([1,2,3,4],L)}
              produz {\tt L=[2,3,4,1]}.
        \item {\tt max(X,Y,M)} de forma que {\em {\tt M} \'e o
              maior dos n\'umeros {\tt X} e {\tt Y}}.
        \item {\tt maxlist(L,M)} de forma que {\em {\tt M} \'e o
              maior n\'umero da lista {\tt L}}.
        \item {\tt somalista(L,S)} de forma que {\em {\tt S} \'e a
              soma dos n\'umeros da lista {\tt L}}.
        \item {\tt ordenada(L)} de forma que
              {\em {\tt L} \'e uma lista ordenada de n\'umeros}.
       \end{list}

 \item Seja o programa em Prolog:
       \begin{tabbing}
        xxxx\= \kill
            \>{\tt p(1).} \\
            \>{\tt p(2) :- !.} \\
            \>{\tt p(3).}
       \end{tabbing}
       Determine todas as respostas para as seguintes consultas:
       \begin{tabbing}
        xxxx\= \kill
            \>{\tt ?- p(X).} \\
            \>{\tt ?- p(X),p(Y).} \\
            \>{\tt ?- p(X),!,p(Y).}
       \end{tabbing}

 \item Defina o procedimento {\tt separa(Nums,Pos,Neg)} que separa a
       lista de n\'umeros {\tt Nums} em positivos (lista {\tt Pos}) e
       negativos (lista {\tt Neg}). Exemplo:
       \begin{tabbing}
        xxxx\= \kill
        \>{\tt separa([3,-2,0,5,-1],[3,0,5],[-2,-1])}.
       \end{tabbing}
       Proponha uma vers\~ao com corte e outra sem.

 \item Defina a rela\c c\~ao diferen\c ca de conjuntos
       {\tt difconj(C1,C2,D)}, onde os 3 conjuntos s\~ao representados como
       listas. Exemplo:
       \begin{tabbing}
        xxxx\= \kill
        \>{\tt difconj([a,b,c,d],[b,d,e,f],[a,c])}.
       \end{tabbing}

 \item Determine $wp({\tt x := x+y; y := x*y},x<y)$.

 \item Mostre que $wp({\tt if}\; B \;{\tt then begin}\; S1;S3 \;{\tt end\; else\; begin}\; S2;S3 \;{\tt end}, q)$
       \'e equivalente a $wp({\tt if}\; B \;{\tt then}\; S1 \;else\; S2; S3, q)$

 \item Prove a corre\c c\~ao parcial do programa:
       \begin{tabbing}
        xxxx\=xxxx\=xxxx\= \kill
        \>$\{a>0\wedge b>0\}$ \\
        \>{\tt x := a; y := b;} \\
        \>{\tt while x <> y do} \\
        \> \>{\tt if x > y} \\
        \> \> \>{\tt then x := x-y} \\
        \> \> \>{\tt else y := y-x} \\
        \>$\{x=\mbox{\em mdc\/}(a,b)\}$ \\
       \end{tabbing}

 \item Prove a corre\c c\~ao parcial do programa:
       \begin{tabbing}
        xxxx\=xxxx\=xxxx\= \kill
        \>$\{a\geq 0\wedge b\geq 0\}$ \\
        \>{\tt x := a; y := b; z := 1} \\
        \>{\tt while y <> 0 do} \\
        \> \>{\tt if odd(y)} \\
        \> \> \>{\tt then begin y := y-1; z := x*z end} \\
        \> \> \>{\tt else begin x := x*x; y := y div 2 end} \\
        \>$\{z=a^b\}$ \\
       \end{tabbing}
\end{enumerate}

\end{document}
