\documentclass[11pt, a4paper]{report}

\usepackage[brazil]{babel}
\usepackage[latin1] {inputenc}
\usepackage{fullpage}
\pagestyle{empty}
\newcounter{conta}
\newcounter{conta2}
\usepackage{gastex}
\usepackage[usenames]{color}
\usepackage{comment}

\begin{document}
\begin{center}\Large\bf
 Soluções da Lista 5
\end{center}

\vspace*{3mm}
\begin{flushleft}
\large\bf Subseção 2.3.5: Satisfabilidade, tautologias e contradições
\end{flushleft}

\begin{enumerate}
 \item[1.]
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item $\neg(\top\wedge\neg\bot)\leftrightarrow(\top\rightarrow\bot\vee\top)\,\equiv\,
           \neg(\top\wedge\top)\leftrightarrow(\top\rightarrow\top)\,\equiv\,\neg\top\leftrightarrow\top \,\equiv\,
           \bot\leftrightarrow\top \,\equiv\, \bot$.
           Logo, a fórmula é \underline{contraditória}.
        \item Para $v^i((p\rightarrow q)\wedge(\neg p\rightarrow q)\rightarrow q)$ ser $F$ deve-se ter
              $v^i((p\rightarrow q)\wedge(\neg p\rightarrow q))=V$ e $v^i(q)=F$. Para que
              $v^i((p\rightarrow q)\wedge(\neg p\rightarrow q))$ seja $V$, deve-se ter
              $v^i(p\rightarrow q)=V$ e $v^i(\neg p\rightarrow q)=V$. Mas é impossível ter-se
              \begin{itemize}
               \item $v^i(q)=F$ e
               \item $v^i(p\rightarrow q)=V$ e
               \item $v^i(\neg p\rightarrow q)=V$
              \end{itemize}
              pois, para isso, seria necessário ter $v^i(p)=F$ e $v^i(\neg p)=F$, o que não é possível!
              Portanto, a fórmula é \underline{tautológica}.
        \item Para $v^i((p\rightarrow q)\wedge\neg(q\rightarrow p))$ ser $V$ é necessário que $v^i(p\rightarrow q)=V$ e
              $v^i(\neg(q\rightarrow p))=V$, ou seja, $v^i(q\rightarrow p)=F$. Mas,
              $v^i(q\rightarrow p)=F$ apenas se $v^i(p)=F$ e $v^i(q)=V$. Portanto a fórmula é \underline{contigente}:
              verdadeira para $v^i(p)=F$ e $v^i(q)=V$, e falsa para $v^i(p)=V$ \underline{ou} $v^i(q)=F$.
        \item $p\rightarrow q\equiv\neg q\rightarrow \neg p$, ou seja, $v^i(p\rightarrow q)=
              v^i(\neg q\rightarrow\neg p)$. Logo, não é possível que $(p\rightarrow q)\wedge\neg(\neg q\rightarrow
              \neg p)$ seja $V$. A fórmula é \underline{contraditória}.
        \item Para que $v^i(\neg p\wedge(q\rightarrow p)\rightarrow\neg q)$ seja $F$ é necessário que
              $v^i(\neg p)=V$, $v^i(q\rightarrow p)=V$ e $v^i(\neg q)=F$. A primeira e a última, implicam que
              $v^i(p)=F$ e $v^i(q)=V$, mas, neste caso, $v^i(q\rightarrow p)=F$, contradizendo a segunda! Portanto,
              $v^i(\neg p\wedge(q\rightarrow p)\rightarrow\neg q)$ não pode ser $F$: a fórmula é
              \underline{tautológica}.
       \end{list}

 \item[3.] \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item $\alpha$ é tautologia se, e somente se, $\alpha$ não é falseável, \\
              $\alpha$ é satisfatível se, e somente se, $\neg\alpha$ é falseável, \\
              $\alpha$ é contradição se, e somente se, $\neg\alpha$ não é falseável, \\
              $\alpha$ é contingência se, e somente se, $\alpha$ e $\neg\alpha$ são falseáveis.
        \item $\alpha$ é satisfatível se, e somente se, $\neg\alpha$ não é tautologia, \\
              $\alpha$ é contradição se, e somente se, $\neg\alpha$ é tautologia, \\
              $\alpha$ é falseável se, e somente se, $\alpha$ não é tautologia, \\
              $\alpha$ é contingência se, e somente se, $\alpha$ e $\neg\alpha$ não são tautologias.
        \item $\alpha$ é tautologia se, e somente se, $\neg\alpha$ é contradição, \\
              $\alpha$ é satisfatível se, e somente se, $\alpha$ não é contradição, \\
              $\alpha$ é falseável se, e somente se, $\neg\alpha$ não é contradição, \\
              $\alpha$ é contingência se, e somente se, $\alpha$ e $\neg\alpha$ não são contradições.
       \end{list}

 \item[4.] Mostrando que sim ou que n\~ao.
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item Sim. \\
              Suponha que $\alpha\wedge\beta$ \'e satisfat\'{\i}vel. Segue-se que existe $i$ tal que
              $v^i(\alpha\wedge\beta)=V$. Então para tal $i$ $v^i(\alpha)=V$ e $v^i(\beta)=V$. Portanto,
              $\beta$ \'e satisfat\'{\i}vel. Logo, se $\alpha\wedge\beta$ \'e satisfat\'{\i}vel, $\beta$ \'e
              satisfat\'{\i}vel.
        \item Sim. \\
              Suponha que $\alpha\wedge\beta$ \'e tautologia. Segue-se que para toda $i$
              $v^i(\alpha\wedge\beta)=V$. Então para toda $i$ $v^i(\alpha)=V$ e $v^i(\beta)=V$. Portanto,
              $\beta$ \'e tautologia. Conclui-se que se $\alpha\wedge\beta$ \'e tautologia, $\beta$ \'e tautologia.
        \item Não. \\
              Contra-exemplo: $p\vee\bot$ \'e satisfatível, mas $\bot$ não é.
        \item Não. \\
              Contra-exemplo: $\top\vee\bot$ \'e tautologia, mas $\bot$ não é.
        \item Sim. \\
              Suponha que $\alpha\rightarrow\beta$ e $\alpha$ sejam tautologias. Seja $i$ uma interpretação qualquer.
              Como $\alpha$ é uma tautologia, $v_{i}(\alpha)=V$. Como $\alpha\rightarrow\beta$ \'e tautologia e
              $v_{i}(\alpha)=V$, segue-se que $v^{i}(\beta)=V$. Como $i$ é arbitrária, conclui-se que $v^i(\beta)=V$
              para toda $i$. Logo, se $\alpha\rightarrow\beta$ e $\alpha$ s\~ao tautologias, ent\~ao $\beta$ \'e
              tautologia.
        \item Sim. \\
              Suponha que $\alpha\rightarrow\beta$ \'e tautologia e $\alpha$ \'e satisfat\'{\i}vel. Seja $i$ tal que
              $v^i(\alpha)=V$. Como $\alpha\rightarrow\beta$ é uma tautologia e, $v_{i}(\alpha)=V$, segue-se que
              $v^{i}(\beta)=V$. Logo, existe $i$ tal que $v^i(\beta)=V$. Portanto, se $\alpha\rightarrow\beta$ \'e
              tautologia e $\alpha$ \'e satisfat\'{\i}vel, $\beta$ \'e satisfat\'{\i}vel.
        \item Não. \\
              Contra-exemplo: $p\rightarrow\bot$ e $p$ são satisfatíveis, mas $\bot$ não é.
       \end{list}
  \item[6.] Soluções dos problemas do tipo \emph{Knights and Knaves}:
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item Tem-se $v_A\leftrightarrow \neg v_A\vee\neg v_B$, que tem um único modelo: $i(v_A)=V$ e $i(v_B)=F$.
              Logo, $A$ sempre diz a verdade e $B$ é mentiroso.
        \item Tem-se $v_A\leftrightarrow (v_A\leftrightarrow v_B)$, que tem dois modelos: um em que $i(v_A)=V$ e
              $i(v_B)=V$, e outro em que $i(v_A)=F$ e $i(v_B)=V$. Logo, $B$ sempre diz a verdade, mas não se sabe
              se $A$ é mentiroso ou não.
        \item Tem-se o conjunto $\{v_B\leftrightarrow (v_A\leftrightarrow \neg v_A),v_C\leftrightarrow\neg v_B\}$,
              que tem os dois modelos em que $i(v_B)=F$ e $i(v_C)=V$. Logo, não se sabe se $A$ é mentiroso ou não,
              mas $B$ é mentiroso e $C$ sempre fala a verdade.
       \end{list}
  \item[7.] Variáveis proposicionais e significados:
        \begin{itemize}
         \item $a_1$: afirmativa da sala I é verdadeira;
         \item $a_2$: afirmativa da sala II é verdadeira;
         \item $m_1$: a moça está na sala I;
         \item $m_2$: a moça está na sala II;
         \item $t_1$: o tigre está na sala I;
         \item $t_2$: o tigre está na sala II;
        \end{itemize}
        Tem-se, então, que o problema se reduz a encontrar um modelo para o conjunto das três fórmulas:
        \begin{itemize}
         \item $a_1 \leftrightarrow m_1\wedge t_2$ (afirmativa da sala I)
         \item $a_2 \leftrightarrow m_1\wedge t_2\vee m_2\wedge t_1$ (afirmativa da sala II)
         \item $a_1\wedge\neg a_2\vee\neg a_1\wedge a_2$ (restrição do problema)
        \end{itemize}
        O único modelo para tal conjunto é aquele em que $i(a_1)=F$, $i(a_2)=V$, $i(m_1)=F$, $i(m_2)=V$, $i(t_1)=V$, $i(t_2)=F$. Logo, a moça está na sala II. 

\end{enumerate}

\end{document}