\documentclass[12pt, a4paper]{article}

\addtolength{\topmargin}{-2cm}
\addtolength{\textheight}{4cm}

\pagestyle{empty}

\newcounter{conta}
\newcounter{conta2}
\begin{document}

\noindent Bacharelado em Matem\'atica Computacional
\hfill UFMG \\
{\it Matem\'{a}tica Discreta}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2002 \\
Professor: Newton Jos\'{e} Vieira  \\
{\bf Trabalho de Programa\c c\~ao}

\vspace*{2mm}
Fa\c ca um programa que, recebendo como entrada uma f\'ormula da L\'ogica
Proposicional, determine se a mesma \'e tautol\'ogica ou n\~ao. No caso
da f\'ormula n\~ao ser tautol\'ogica, o programa dever\'a dar valores das
vari\'aveis proposicionais para os quais a f\'ormula \'e falsa.
O algoritmo a ser implementado dever\'a ser baseado no m\'etodo de
refuta\c c\~ao descrito a seguir atrav\'es de exemplos.

\begin{description}
 \item[Exemplo 1] A f\'ormula $\neg(p\wedge \neg p)$ \'e uma tautologia, pois:

       \begin{enumerate}
        \item Para $\neg(p\wedge \neg p)$ ser {\bf falsa}, $p\wedge \neg p$
              tem que ser {\bf verdadeira}.
        \item Para $p\wedge \neg p$ ser {\bf verdadeira}, $p$ tem que ser
              {\bf verdadeira} e $\neg p$ tem que ser {\bf verdadeira}.
        \item Para $\neg p$ tem ser {\bf verdadeira}, $p$ tem que ser
              {\bf falsa}.
        \item Conclus\~ao: $\neg(p\wedge \neg p)$ n\~ao pode ser {\bf falsa},
              pois, para isto, $p$ teria que ser {\bf verdadeira} (item 2) e
              {\bf falsa} (item 3).
       \end{enumerate}
       O desenho abaixo ilustra o processo. As atribui\c c\~oes de va\-lo\-res
       {\bf V}/{\bf F} (verdadeiro/faso) \'e feita na ordem indicada pela
       posi\c c\~ao vertical: va\-lo\-res mais acima s\~ao atribuidos antes.

       \begin{picture}(400,80)
        \put(20,70){\makebox(0,0){$\neg$}}
        \put(35,70){\makebox(0,0){$($}}
        \put(50,70){\makebox(0,0){$p$}}
        \put(65,70){\makebox(0,0){$\wedge$}}
        \put(80,70){\makebox(0,0){$\neg$}}
        \put(95,70){\makebox(0,0){$p$}}
        \put(110,70){\makebox(0,0){$)$}}

        \put(20,55){\makebox(0,0){\bf F}}
        \put(65,40){\makebox(0,0){\bf V}}
        \put(65,55){\makebox(0,0){$|$}}
        \put(50,25){\makebox(0,0){\bf V}}
        \put(50,55){\makebox(0,0){$|$}}
        \put(50,40){\makebox(0,0){$|$}}
        \put(80,25){\makebox(0,0){\bf V}}
        \put(80,55){\makebox(0,0){$|$}}
        \put(80,40){\makebox(0,0){$|$}}
        \put(95,10){\makebox(0,0){\bf F}}
        \put(95,55){\makebox(0,0){$|$}}
        \put(95,40){\makebox(0,0){$|$}}
        \put(95,25){\makebox(0,0){\bf V}}
        \put(115,10){\makebox(0,0)[l]{$\Rightarrow$ contradi\c c\~ao!}}
       \end{picture}

 \item[Exemplo 2] A f\'ormula $(p\leftrightarrow (\neg q\vee r))\rightarrow
       (\neg p\rightarrow q)$ \'e uma tautologia:

       \begin{picture}(400,125)
        \put(20,115){\makebox(0,0){$($}}
        \put(35,115){\makebox(0,0){$p$}}
        \put(50,115){\makebox(0,0){$\leftrightarrow$}}
        \put(65,115){\makebox(0,0){$($}}
        \put(80,115){\makebox(0,0){$\neg$}}
        \put(95,115){\makebox(0,0){$q$}}
        \put(110,115){\makebox(0,0){$\vee$}}
        \put(125,115){\makebox(0,0){$r$}}
        \put(140,115){\makebox(0,0){$)$}}
        \put(155,115){\makebox(0,0){$)$}}
        \put(170,115){\makebox(0,0){$\rightarrow$}}
        \put(185,115){\makebox(0,0){$($}}
        \put(200,115){\makebox(0,0){$\neg$}}
        \put(215,115){\makebox(0,0){$p$}}
        \put(230,115){\makebox(0,0){$\rightarrow$}}
        \put(245,115){\makebox(0,0){$q$}}
        \put(260,115){\makebox(0,0){$)$}}

        \put(170,100){\makebox(0,0){\bf F}}
        \put(35,100){\makebox(0,0){$|$}}
        \put(50,100){\makebox(0,0){$|$}}
        \put(80,100){\makebox(0,0){$|$}}
        \put(95,100){\makebox(0,0){$|$}}
        \put(110,100){\makebox(0,0){$|$}}
        \put(125,100){\makebox(0,0){$|$}}
        \put(200,100){\makebox(0,0){$|$}}
        \put(215,100){\makebox(0,0){$|$}}
        \put(230,100){\makebox(0,0){$|$}}
        \put(245,100){\makebox(0,0){$|$}}

        \put(35,85){\makebox(0,0){$|$}}
        \put(50,85){\makebox(0,0){\bf V}}
        \put(80,85){\makebox(0,0){$|$}}
        \put(95,85){\makebox(0,0){$|$}}
        \put(110,85){\makebox(0,0){$|$}}
        \put(125,85){\makebox(0,0){$|$}}
        \put(200,85){\makebox(0,0){$|$}}
        \put(215,85){\makebox(0,0){$|$}}
        \put(230,85){\makebox(0,0){\bf F}}
        \put(245,85){\makebox(0,0){$|$}}

        \put(35,70){\makebox(0,0){$|$}}
        \put(80,70){\makebox(0,0){$|$}}
        \put(95,70){\makebox(0,0){\bf F}}
        \put(110,70){\makebox(0,0){$|$}}
        \put(125,70){\makebox(0,0){$|$}}
        \put(200,70){\makebox(0,0){\bf V}}
        \put(215,70){\makebox(0,0){$|$}}
        \put(245,70){\makebox(0,0){\bf F}}

        \put(35,55){\makebox(0,0){\bf F}}
        \put(80,55){\makebox(0,0){$|$}}
        \put(110,55){\makebox(0,0){$|$}}
        \put(125,55){\makebox(0,0){$|$}}
        \put(215,55){\makebox(0,0){\bf F}}

        \put(80,40){\makebox(0,0){$|$}}
        \put(110,40){\makebox(0,0){\bf F}}
        \put(125,40){\makebox(0,0){$|$}}

        \put(80,25){\makebox(0,0){\bf F}}
        \put(125,25){\makebox(0,0){\bf F}}

        \put(95,10){\makebox(0,0){\bf V}}
        \put(115,10){\makebox(0,0)[l]{$\Rightarrow$ contradi\c c\~ao!}}
       \end{picture}

 \item[Exemplo 3] Este exemplo mostra que pode haver {\em alternativas\/}
        para falsear uma f\'ormula. Neste caso, {\em todas\/} as possibilidades
        de falsear a f\'ormula devem redundar em contradi\c c\~ao para a mesma
        ser considerada uma tautologia.

        Seja a f\'ormula $(\neg p\vee q)\leftrightarrow (p \rightarrow q)$.
        Existem duas alternativas para a mesma ser {\bf falsa}:

       \begin{picture}(175,50)
        \put(0,40){\makebox(0,0){$($}}
        \put(15,40){\makebox(0,0){$\neg$}}
        \put(30,40){\makebox(0,0){$p$}}
        \put(45,40){\makebox(0,0){$\vee$}}
        \put(60,40){\makebox(0,0){$q$}}
        \put(75,40){\makebox(0,0){$)$}}
        \put(90,40){\makebox(0,0){$\leftrightarrow$}}
        \put(105,40){\makebox(0,0){$($}}
        \put(120,40){\makebox(0,0){$p$}}
        \put(135,40){\makebox(0,0){$\rightarrow$}}
        \put(150,40){\makebox(0,0){$q$}}
        \put(165,40){\makebox(0,0){$)$}}

        \put(45,25){\makebox(0,0){$|$}}
        \put(90,25){\makebox(0,0){\bf F}}
        \put(135,25){\makebox(0,0){$|$}}

        \put(45,10){\makebox(0,0){\bf V}}
        \put(135,10){\makebox(0,0){\bf F}}

        \put(180,5){\line(0,1){40}}

        \put(195,40){\makebox(0,0){$($}}
        \put(210,40){\makebox(0,0){$\neg$}}
        \put(225,40){\makebox(0,0){$p$}}
        \put(240,40){\makebox(0,0){$\vee$}}
        \put(255,40){\makebox(0,0){$q$}}
        \put(270,40){\makebox(0,0){$)$}}
        \put(285,40){\makebox(0,0){$\leftrightarrow$}}
        \put(300,40){\makebox(0,0){$($}}
        \put(315,40){\makebox(0,0){$p$}}
        \put(330,40){\makebox(0,0){$\rightarrow$}}
        \put(345,40){\makebox(0,0){$q$}}
        \put(360,40){\makebox(0,0){$)$}}

        \put(240,25){\makebox(0,0){$|$}}
        \put(285,25){\makebox(0,0){\bf F}}
        \put(330,25){\makebox(0,0){$|$}}

        \put(240,10){\makebox(0,0){\bf F}}
        \put(330,10){\makebox(0,0){\bf V}}
       \end{picture}

       A primeira alternativa redunda em:

       \begin{picture}(175,80)
        \put(0,70){\makebox(0,0){$($}}
        \put(15,70){\makebox(0,0){$\neg$}}
        \put(30,70){\makebox(0,0){$p$}}
        \put(45,70){\makebox(0,0){$\vee$}}
        \put(60,70){\makebox(0,0){$q$}}
        \put(75,70){\makebox(0,0){$)$}}
        \put(90,70){\makebox(0,0){$\leftrightarrow$}}
        \put(105,70){\makebox(0,0){$($}}
        \put(120,70){\makebox(0,0){$p$}}
        \put(135,70){\makebox(0,0){$\rightarrow$}}
        \put(150,70){\makebox(0,0){$q$}}
        \put(165,70){\makebox(0,0){$)$}}

        \put(15,55){\makebox(0,0){$|$}}
        \put(30,55){\makebox(0,0){$|$}}
        \put(45,55){\makebox(0,0){$|$}}
        \put(60,55){\makebox(0,0){$|$}}
        \put(90,55){\makebox(0,0){\bf F}}
        \put(120,55){\makebox(0,0){$|$}}
        \put(135,55){\makebox(0,0){$|$}}
        \put(150,55){\makebox(0,0){$|$}}

        \put(15,40){\makebox(0,0){$|$}}
        \put(30,40){\makebox(0,0){$|$}}
        \put(45,40){\makebox(0,0){\bf V}}
        \put(60,40){\makebox(0,0){$|$}}
        \put(120,40){\makebox(0,0){$|$}}
        \put(135,40){\makebox(0,0){\bf F}}
        \put(150,40){\makebox(0,0){$|$}}

        \put(15,25){\makebox(0,0){$|$}}
        \put(30,25){\makebox(0,0){\bf V}}
        \put(60,25){\makebox(0,0){\bf F}}
        \put(120,25){\makebox(0,0){\bf V}}
        \put(150,25){\makebox(0,0){\bf F}}

        \put(15,10){\makebox(0,0){\bf V}}
        \put(30,10){\makebox(0,0){\bf F}}
        \put(50,10){\makebox(0,0)[l]{$\Rightarrow$ contradi\c c\~ao!}}

       \end{picture}

       A segunda alternativa redunda em:

       \begin{picture}(175,80)
        \put(0,70){\makebox(0,0){$($}}
        \put(15,70){\makebox(0,0){$\neg$}}
        \put(30,70){\makebox(0,0){$p$}}
        \put(45,70){\makebox(0,0){$\vee$}}
        \put(60,70){\makebox(0,0){$q$}}
        \put(75,70){\makebox(0,0){$)$}}
        \put(90,70){\makebox(0,0){$\leftrightarrow$}}
        \put(105,70){\makebox(0,0){$($}}
        \put(120,70){\makebox(0,0){$p$}}
        \put(135,70){\makebox(0,0){$\rightarrow$}}
        \put(150,70){\makebox(0,0){$q$}}
        \put(165,70){\makebox(0,0){$)$}}

        \put(15,55){\makebox(0,0){$|$}}
        \put(30,55){\makebox(0,0){$|$}}
        \put(45,55){\makebox(0,0){$|$}}
        \put(60,55){\makebox(0,0){$|$}}
        \put(90,55){\makebox(0,0){\bf F}}
        \put(120,55){\makebox(0,0){$|$}}
        \put(135,55){\makebox(0,0){$|$}}
        \put(150,55){\makebox(0,0){$|$}}

        \put(15,40){\makebox(0,0){$|$}}
        \put(30,40){\makebox(0,0){$|$}}
        \put(45,40){\makebox(0,0){\bf F}}
        \put(60,40){\makebox(0,0){$|$}}
        \put(120,40){\makebox(0,0){$|$}}
        \put(135,40){\makebox(0,0){\bf V}}
        \put(150,40){\makebox(0,0){$|$}}

        \put(15,25){\makebox(0,0){\bf F}}
        \put(30,25){\makebox(0,0){$|$}}
        \put(60,25){\makebox(0,0){\bf F}}
        \put(120,25){\makebox(0,0){$|$}}
        \put(150,25){\makebox(0,0){\bf F}}

        \put(30,10){\makebox(0,0){\bf V}}
        \put(120,10){\makebox(0,0){\bf F}}
        \put(135,10){\makebox(0,0)[l]{$\Rightarrow$ contradi\c c\~ao!}}

       \end{picture}



\end{description}

\end{document}