\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 Primeira Lista de Exerc\'{\i}cios} \hfill Entrega: 16/10/03

\begin{enumerate}
 \item Construa as \'arvores de forma\c c\~ao para as seguintes
       f\'ormulas, supondo o esquema de prioridades adotado no livro
       texto:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $p\wedge\neg q\rightarrow\neg p$.
        \item $\neg p\vee(p\rightarrow q)$.
        \item $p\leftrightarrow(\neg p\oplus(\neg \neg q\rightarrow p\wedge q))$.
       \end{list}

 \item Liste todas as subf\'ormulas das f\'ormulas da quest\~ao 1.

 \item Prove as seguintes equival\^encias l\'ogicas:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $A\wedge(B\vee C)\equiv (A\wedge B)\vee(A \wedge C)$.
        \item $A\rightarrow B\equiv \neg A \vee B$.
        \item $A\rightarrow B\equiv \neg (A \wedge \neg B)$.
        \item $((A\oplus B)\oplus B)\equiv A$.
       \end{list}

 \item Defina todos os operadores booleanos utilizando apenas:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\neg$ e $\vee$.
        \item $\uparrow$.
       \end{list}

 \item Verifique, dentre as seguintes f\'ormulas, quais s\~ao v\'alidas, quais
       s\~ao insatisfat\'{\i}veis e quais s\~ao contingentes (satisfat\'{\i}veis
       e false\'aveis) raciocinando a partir da {\em fun\c c\~ao de atribui\c c\~ao\/}
       $\nu$:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $p\wedge q\wedge(\neg p\vee\neg q)$.
        \item $(p\rightarrow q)\rightarrow (q\rightarrow p)$.
        \item $(p\rightarrow q)\rightarrow (\neg p\rightarrow \neg q)$.
        \item $(p\rightarrow q)\rightarrow (\neg q\rightarrow \neg p)$.
        \item $(p\leftrightarrow q)\rightarrow (\neg p\leftrightarrow \neg q)$.
        \item $(p\rightarrow(r\wedge q))\rightarrow(\neg r\rightarrow(p\vee r))$.
        \item $(p\wedge q)\rightarrow((p\rightarrow r)\rightarrow((r\rightarrow p)
               \rightarrow (p\leftrightarrow q)))$.
       \end{list}

 \item Verifique a validade (ou n\~ao) das seguintes consequ\^encias l\'ogicas:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{p\rightarrow q, r\rightarrow q\} \models p\rightarrow r$.
        \item $\{p\wedge q, q\wedge r\} \models p\rightarrow r$.
        \item $\{p\rightarrow q, p\rightarrow r\} \models p\vee q\vee r$.
       \end{list}

 \item Considere como {\em cavaleiros\/} aquelas pessoas que s\'o dizem a verdade, e
       como {\em cavilosos\/} aquelas que s\'o mentem. Resolva os seguintes problemas
       usando o c\'alculo proposicional, supondo que na ilha visitada por Greg\'orio
       cada pessoa \'e cavaleiro ou caviloso:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Greg\'orio foi visitar uma ilha em que cada casa continha apenas um casal.
              Ele bateu em uma porta, e foi atendido pelo marido. Perguntou: nesta
              casa quem \'e cavaleiro e quem \'e caviloso? Recebeu como resposta:
              somos ambos cavilosos.

              De que tipo \'e o marido e de que tipo \'e a esposa?
        \item Na casa seguinte, Greg\'orio perguntou ao marido: voc\^es s\~ao
              ambos cavilosos? Recebeu como resposta: pelo menos um de n\'os dois \'e.

              De que tipo \'e cada um?

        \item Na pr\'oxima casa, o marido disse a Greg\'orio: se eu for um cavaleiro,
              minha esposa tamb\'em o ser\'a.

              De que tipo \'e cada um?
       \end{list}

 \item Complete a prova do Teorema 2.48 (que a constru\c c\~ao de um tableau
       termina), p\'agina 33.

 \item Obtenha os mesmos resultados das quest\~oes 5 e 6 utilizando tableaux
       sem\^anticos.

\end{enumerate}

\end{document}
