\documentclass[11pt,a4paper]{article}

\usepackage[portuguese]{babel}
\usepackage[dvips]{graphics,color}

%=================================================================
%\setlength{\oddsidemargin}{16mm}
\setlength{\oddsidemargin}{6mm}
%\setlength{\evensidemargin}{-.8mm}
%\setlength{\evensidemargin}{9.2mm}
\setlength{\evensidemargin}{9mm}
\setlength{\textwidth}{14.5cm}
%=================================================================

\newcounter{conta}

\pagestyle{myheadings}
\pagenumbering{roman}

\begin{document}

\selectlanguage{portuguese}

\noindent P\'os-Gradua\c{c}\~ao em Ci\^{e}ncia da Computa\c{c}\~{a}o
 \hfill DCC/ICEx/UFMG \\
{\it Demonstra\c c\~ao de Teoremas}
 \hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2006 \\
Professor: Newton Jos\'{e} Vieira \\
{\bf Exerc\'{\i}cios de L\'ogica Proposicional}

\begin{enumerate}
 \item \label{ereal1}
      Identifique as proposi\c c\~oes simples que comp\~oem os as proposic\~oes
       a seguir, assim como os conectivos utilizados. Procure identificar o
       m\'aximo poss\'{\i}vel de conectivos, isto \'e, considere uma
       proposi\c c\~ao como simples somente se n\~ao for poss\'{\i}vel
       consider\'a-la composta. H\'a certos aspectos que n\~ao s\~ao
       represent\'aveis em l\'ogica proposicional; ignore-os.

       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item Jo\~ao \'e pol\'{\i}tico mas \'e honesto.
        \item Jo\~ao \'e honesto, mas seu irm\~ao n\~ao \'e.
        \item Vir\~ao \`a festa Marta ou sua irm\~a, al\'em da m\~ae.
        \item A estrela do espet\'aculo n\~ao canta, dan\c ca, nem
              representa.
        \item Sempre que o trem apita, o menino sai correndo.
        \item Caso Jo\~aozinho n\~ao perca o dinheiro no jogo, ele vai \`a feira.
        \item Aquele motorista vai ser multado, a menos que diminua a velocidade ou
              a rodovia n\~ao tenha radar.
        \item Vav\'a vai ao teatro somente se estiver em cartaz uma com\'edia.
        \item Se voc\^e for brasileiro, gosta de futebol, desde que n\~ao
              tor\c ca para o Tabajara.
        \item A propina ser\'a paga exatamente nas situa\c c\~oes em que
              o deputado votar como instru\'{\i}do pela organiza\c c\~ao.
        \item Se Godofredo testemunhar e disser a verdade, ser\'a
              absolvido, mas se ele n\~ao testemunhar, n\~ao
              ser\'a absolvido.
        \item Se, mas somente se, Ti\~ao n\~ao peder o dinheiro no jogo,
              ele ir\'a pagar o que lhe deve.
        \item Se Cac\'a for ao circo ou ao futebol hoje, ele estar\'a
              sem dinheiro amanh\~a. 
       \end{list}
 \item \label{ereal2}
       Considere o seguinte conjunto de proposi\c c\~oes:
       \begin{quote}
        O mordomo \'e inocente ou culpado. Se o mordomo \'e inocente,
        ent\~ao a testemunha mentiu. Se o mordomo tem um c\'umplice,
        ent\~ao a testemunha n\~ao mentiu. A testemunha tendo mentido ou n\~ao,
        o mordomo tem um c\'umplice.
       \end{quote}
       Supondo que tais proposi\c c\~oes sejam verdadeiras, responda: o
       mordomo \'e culpado ou \'e inocente? Explique sua resposta de uma forma
       coloquial, sem apelar para os conceitos e formalismos l\'ogicos que
       porventura conhe\c ca.

 \item Represente as proposi\c c\~oes do exerc\'{\i}cio~\ref{ereal1}
       por meio de f\'ormulas.
       Ao faz\^e-lo, indique que vari\'aveis proposicionais representam que
       proposi\c c\~oes simples. Como l\'a, procure usar o m\'aximo
       poss\'{\i}vel de conectivos, isto \'e, considere uma proposi\c c\~ao
       como simples somente se n\~ao for poss\'{\i}vel consider\'a-la composta.
       Aspectos n\~ao represent\'aveis em l\'ogica proposicional devem se
       ignorados.
 \item \label{eling2}
       Represente as proposi\c c\~oes do exerc\'{\i}cio~\ref{ereal2}
       por meio de f\'ormulas.

 \item A disjun\c c\~ao vista nessas notas \'e a chamada disjun\c c\~ao {\em
       inclusiva\/}. Uma outra, menos usada em matem\'atica (mas mais
       usada em outros contextos, como constru\c c\~ao de circuitos digitais)
       \'e a disjun\c c\~ao {\em exclusiva\/}, em que se considera
       $\alpha$ ``ou'' $\beta$ verdadeira apenas se $\alpha$ \'e
       verdadeira ou $\beta$ verdadeira, mas n\~ao ambas. Fa\c ca a tabela da
       verdade para ``ou exclusivo''. Mostre como expressar ``ou exclusivo''
       sem um s\'{\i}mbolo espec\'{\i}fico para tal (ou seja, usando apenas os
       conectivos j\'a vistos).

 \item Descubra, para cada f\'ormula abaixo, se ela \'e tautol\'ogica,
       contradit\'oria ou contingente. Em seguida, explique da maneira mais
       sucinta que puder a sua resposta:
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item $\neg(\top\wedge\neg\bot)\leftrightarrow(\top\rightarrow\bot\vee\top)$
        \item $(p\rightarrow q)\wedge(\neg p\rightarrow q)\rightarrow q$
        \item $(p\rightarrow q)\wedge\neg(q\rightarrow p)$
        \item $(p\rightarrow q)\wedge\neg(\neg q\rightarrow \neg p)$
        \item $\neg p\wedge(q\rightarrow p)\rightarrow\neg q$
       \end{list}

 \item Considere as f\'ormulas obtidas para o Exerc\'{\i}cio~\ref{eling2}.
       Construa um modelo para tal conjunto. Este modelo
       diz o que, caso se interprete as vari\'aveis proposicionais de acordo
       com as proposi\c c\~oes do Exerc\'{\i}cio~\ref{ereal2}?

 \item Suponha que voc\^e tem algoritmos para determinar, para uma f\'ormula
       qualquer, se ela \'e (1) tautologia; (2) contradi\c c\~ao;
       (3) satisfat\'{\i}vel; (4) false\'avel.
       Explique como voc\^e poderia utilizar cada um desses quatro algoritmos
       para determinar, dados um conjunto de f\'ormulas $H$ e uma f\'ormula
       $\alpha$, se $H\models \alpha$. (Comece supondo que $H=\{\beta_1,\beta_2,
       \ldots,\beta_n\}$\ldots)

 \item Mostre que $\{\neg p\}\models p\rightarrow q$.

 \item Para os pares de f\'ormulas a seguir, descubra se s\~ao logicamente
       equivalentes, ou se uma \'e conseq\"u\^encia l\'ogica da outra.
       Em seguinda, explique da maneira mais sucinta que puder a sua resposta.
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item $(p\rightarrow r)\wedge(q\rightarrow r)$ e $(p\vee q)
               \rightarrow r$
        \item $(p\rightarrow r)\wedge(q\rightarrow s)$ e $(p\wedge q)
               \rightarrow (r\vee s)$
        \item $p \leftrightarrow q$ e $(p\wedge q)\vee(\neg p\wedge\neg q)$
       \end{list}

 \item Seguem alguns argumentos expressos em portugu\^es. Expresse-os em
       l\'ogica proposicional. Depois verifique se os mesmos s\~ao corretos
       usando o conceito de conseq\"u\^encia l\'ogica.
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item Se eu ganhei na megasena, ent\~ao sou rico. Eu n\~ao ganhei na
              megasena. Logo, n\~ao sou rico.
        \item Se n\~ao chover, a ro\c ca n\~ao produz e o pasto seca. Se o pasto
              seca, o gado n\~ao resiste. Portanto, se n\~ao chover, o gado n\~ao
              resiste.
        \item Jo\~ao ser\'a absolvido ou condenado. Se for absolvido, ser\'a porque
              a testemunha mentiu. Mas a testemunha n\~ao mentiu. Portanto,
              Jo\~ao ser\'a condenado.
        \item Se Deus \'e todo-poderoso e infinitamente bom, ent\~ao n\~ao
              existe o diabo. Deus \'e todo-poderoso e existe o diabo. Portanto,
              Deus n\~ao \'e infinitamente bom.
        \item Se voc\^e come demais, acaba ficando obeso. Se faz exerc\'{\i}cio
              f\'{\i}sico todo dia, fica bem condicionado. E se n\~ao \'e obeso
              e \'e bem condicionado, n\~ao adoece com facilidade. Mas voc\^e
              adoece com facilidade. Portanto, voc\^e come demais e n\~ao faz
              exerc\'{\i}cio f\'{\i}sico todo dia.
       \end{list}

 \item Uma abordagem para demonstra\c c\~ao autom\'atica, alternativa ao m\'etodo
       dedutivo, \'e baseada em verificar
       se um conjunto de f\'ormulas tem ou n\~ao um modelo. A abordagem \'e
       justificada pelo fato de que:
       \[H\models \alpha \mbox{ se, e somente se } H\cup\{\neg\alpha\}\models \bot\]
       ou melhor:
       \[H\models \alpha \mbox{ se, e somente se } H\cup\{\neg\alpha\} \mbox{ n\~ao
       tem um modelo.}\]
       Suponha que um algoritmo determine um modelo para $H\cup\{\neg\alpha\}$. Como
       tal modelo pode ser usado para justificar que $H\not\models \alpha$?

 \item Especifique uma estrat\'egia para provar afirmativas da forma
       $\alpha\oplus\beta$, em que $\oplus$ deve ser interpretado como
       ``ou exclusivo''.

 \item Suponha que:
       \begin{enumerate}
        \item[\ ] $H\models\alpha_1\vee\alpha_2\vee\cdots\vee\alpha_n$, $n\geq 2$;
        \item[\ ] $H\models\alpha_1\rightarrow\beta$;
        \item[\ ] $H\models\alpha_2\rightarrow\beta$;
        \item[\ ] $\vdots$
        \item[\ ] $H\models\alpha_n\rightarrow\beta$.
       \end{enumerate}
       Mostre que, neste caso, $H\models\beta$. Formule uma estrat\'egia de prova,
       {\em diferente da prova por casos\/}, justific\'avel por este resultado.
\end{enumerate}

\end{document}

