\section{Fundamentos de L\'ogica}

\hypertarget{fundamentos-logica-1}{}
\newslide{O CONCEITO DE PROPOSI\c{C}\~AO}

\begin{itemize}
 \item \textcolor{black}{Proposi\c{c}\~{a}o:} afirma\c{c}\~{a}o que \'{e}
        verdadeira ou falsa.
 \item Exemplos:
       \begin{quote}
        Belo Horizonte \'{e} a capital de Minas Gerais. (verdadeira) \\
        Campinas \'{e} a capital de S\~{a}o Paulo. (falsa) \\
        $2+2=4$. (verdadeira) \\
        $1+1=1$. (falsa)
       \end{quote}
\end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{PROPOSI\c{C}\~AO SIMPLES E COMPOSTA}

\begin{itemize}
 \item \textcolor{black}{Proposi\c{c}\~{a}o simples:} representada por meio de
       {\bf vari\'{a}vel proposicional} ($\textcolor{black}{p}, \textcolor{black}{q}, \textcolor{black}{r}, \textcolor{black}{s}, \ldots$).
 \item \textcolor{black}{Proposi\c{c}\~{a}o composta:} combina\c{c}\~ao de
        proposi\c{c}\~{o}es por meio de \textcolor{black}{conectivos
        l\'{o}gicos}.
 \item \textcolor{black}{Conectivos l\'{o}gicos}:
       \begin{quote}
        Nega\c{c}\~{a}o: \textcolor{black}{$\neg$} \\
        Conjun\c{c}\~{a}o: \textcolor{black}{$\wedge$} \\
        Disjun\c{c}\~{a}o: \textcolor{black}{$\vee$} \\
        Implica\c{c}\~{a}o: \textcolor{black}{$\Rightarrow$} \\
        Bicondicional: \textcolor{black}{$\Leftrightarrow$}
       \end{quote}
\end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{EXEMPLOS DE PROPOSI\c{C}\~AO SIMPLES E COMPOSTAS}

\begin{itemize}
 \item  Proposi\c{c}\~{o}es simples:
        \begin{quote}
         \textcolor{black}{$p$}: voc\^{e} fez mais de 80 km/h. \\
         \textcolor{black}{$q$}: voc\^{e} foi multado.
        \end{quote} 
 \item Proposi\c{c}\~{o}es compostas:
       \begin{quote}
       \begin{tabular}{rl}
        \textcolor{black}{$\neg p$}:         & voc\^{e} n\~{a}o fez mais de 80 km/h. \\
        \textcolor{black}{$p\wedge \neg q$}: & voc\^{e} fez mais de 80 km/h, mas n\~{a}o foi multado. \\
        \textcolor{black}{$\neg p\vee q$}:   & voc\^{e} n\~{a}o fez mais de 80 km/h ou foi multado. \\
        \textcolor{black}{$\neg p\Rightarrow \neg q$}: & \parbox[t]{13cm}{se voc\^{e} n\~{a}o fez mais de 80 km/h,
        ent\~{a}o n\~{a}o foi multado.}
       \end{tabular}
       \end{quote}
\end{itemize}

%--------------------------------------------------------------------------------------------


\newslide{TABELAS DA VERDADE:}

\begin{itemize}
 \item \textcolor{black}{Nega\c{c}\~{a}o}:

 \ \\
              \hspace*{4cm} \begin{tabular}{|c|c|} \hline
                             $\alpha$ & $\neg \alpha$ \\ \hline
                             {\bf V} & {\bf F} \\
                             {\bf F} & {\bf V} \\ \hline
                            \end{tabular}
\end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{TABELAS DA VERDADE:}

\begin{itemize}
 \item \textcolor{black}{Conjun\c{c}\~{a}o}:
 
 \ \\
             \hspace*{4cm} \begin{tabular}{|c|c|c|} \hline
                               $\alpha$ & $\beta$ & $\alpha\wedge \beta$ \\
                                \hline
                               {\bf V} & {\bf V} & {\bf V} \\
                               {\bf V} & {\bf F} & {\bf F} \\
                               {\bf F} & {\bf V} & {\bf F} \\
                               {\bf F} & {\bf F} & {\bf F} \\ \hline
                              \end{tabular}
\end{itemize}

%--------------------------------------------------------------------------------------------


\newslide{TABELAS DA VERDADE:}

\begin{itemize}
\item \textcolor{black}{Disjun\c{c}\~{a}o}:
 
\ \\
             \hspace*{4cm} \begin{tabular}{|c|c|c|} \hline
                               $\alpha$ & $\beta$ & $\alpha\vee \beta$ \\ \hline
                               {\bf V} & {\bf V} & {\bf V} \\
                               {\bf V} & {\bf F} & {\bf V} \\
                               {\bf F} & {\bf V} & {\bf V} \\
                               {\bf F} & {\bf F} & {\bf F} \\ \hline
                              \end{tabular}
\end{itemize}


%--------------------------------------------------------------------------------------------


\newslide{TABELAS DA VERDADE:}

\begin{itemize}
\item \textcolor{black}{Condicional}:
 
\ \\
             \hspace*{4cm} \begin{tabular}{|c|c|c|} \hline
                            $\alpha$ & $\beta$ & $\alpha\Rightarrow \beta$ \\
                             \hline
                            {\bf V} & {\bf V} & {\bf V} \\
                            {\bf V} & {\bf F} & {\bf F} \\
                            {\bf F} & {\bf V} & {\bf V} \\
                            {\bf F} & {\bf F} & {\bf V} \\ \hline
                           \end{tabular}
\end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{TABELAS DA VERDADE:}

\begin{itemize}
 \item \textcolor{black}{Bicondicional}:

\ \\
             \hspace*{4cm} \begin{tabular}{|c|c|c|} \hline
                            $\alpha$ & $\beta$ & $\alpha\Leftrightarrow \beta$
                             \\ \hline
                            {\bf V} & {\bf V} & {\bf V} \\
                            {\bf V} & {\bf F} & {\bf F} \\
                            {\bf F} & {\bf V} & {\bf F} \\
                            {\bf F} & {\bf F} & {\bf V} \\ \hline
                           \end{tabular}
\end{itemize}

%--------------------------------------------------------------------------------------------


\newslide{EXPRESS\~OES PARA A CONDICIONAL}


\begin{itemize}
 \item $\alpha \Rightarrow \beta$
 \item se $\alpha$ ent\~{a}o $\beta$
 \item $\alpha$ implica $\beta$
 \item se $\alpha$, $\beta$
 \item $\alpha$ somente se $\beta$
 \item $\alpha$ \'{e} suficiente para $\beta$
 \item $\beta$ se $\alpha$
 \item $\beta$ caso $\alpha$
 \item $\beta$ \'{e} necess\'{a}rio para $\alpha$
\end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{EXPRESS\~OES PARA A BICONDICIONAL}


\begin{itemize}
 \item $\alpha \Leftrightarrow\beta$
 \item $\alpha$ se e somente se $\beta$
 \item $\alpha$ \'{e} necess\'{a}rio e suficiente para $\beta$
 \item se $\alpha$ ent\~{a}o $\beta$, e vice-versa
\end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{TIPOS DE F\'ORMULAS}


\begin{itemize}
 \item \textcolor{black}{Tautologia}: proposi\c{c}\~{a}o que \'{e} sempre verdadeira.
 \item \textcolor{black}{Contradi\c{c}\~{a}o}: proposi\c{c}\~{a}o que \'{e} sempre falsa.
 \item \textcolor{black}{Conting\^{e}ncia}: proposi\c{c}\~{a}o que n\~{a}o \'{e} tautologia nem contradi\c{c}\~{a}o.
\end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{EXEMPLOS}

\begin{center}
\begin{tabular}{cc||c||c||c|} \cline{3-5}
     &     & conting\^{e}ncia & tautologia & contradi\c{c}\~{a}o \\ \hline
 \multicolumn{1}{|c|}{\textcolor{black}{$p$}} & \textcolor{black}{$q$} & \textcolor{black}{$p\Leftrightarrow q$} &
  \textcolor{black}{$(p \wedge(p\Rightarrow q))\Rightarrow q$} & \textcolor{black}{$p\wedge \neg(p\vee q)$} \\ \hline
 \multicolumn{1}{|c|}{\bf V} & {\bf V} & {\bf V} & {\bf V} & {\bf F} \\
 \multicolumn{1}{|c|}{\bf V} & {\bf F} & {\bf F} & {\bf V} & {\bf F} \\
 \multicolumn{1}{|c|}{\bf F} & {\bf V} & {\bf F} & {\bf V} & {\bf F} \\
 \multicolumn{1}{|c|}{\bf F} & {\bf F} & {\bf V} & {\bf V} & {\bf F} \\ \hline
\end{tabular}
\end{center}
%--------------------------------------------------------------------------------------------

\newslide{CONSEQU\^ENCIA L\'OGICA}

\begin{itemize}
 \item $\alpha$ \'{e} \textcolor{black}{consequ\^{e}ncia l\'{o}gica} de $\beta$,
       $\beta \models \alpha$, se e somente se $\alpha$ \'{e} verdadeira sempre
       que $\beta$ \'{e} verdadeira.

 \item \underline{Exemplo}: $\textcolor{black}{p\wedge(p\Rightarrow q)} \models \textcolor{black}{q}$, pois:

\vspace*{3mm}
\hspace*{2cm} 
\begin{center}
\begin{tabular}{c|c|c|c|c|c} \cline{2-5}
 & \textcolor{black}{$p$} & \textcolor{black}{$q$} & \textcolor{black}{$p\Rightarrow q$} & \textcolor{black}{$p \wedge(p\Rightarrow q)$} \\ \cline{2-5}
 $\Longrightarrow$ & {\bf V} & {\bf V} & {\bf V} & {\bf V} & $\Longleftarrow$ \\
 & {\bf V} & {\bf F} & {\bf F} & {\bf F} \\
 & {\bf F} & {\bf V} & {\bf V} & {\bf F} \\
 & {\bf F} & {\bf F} & {\bf V} & {\bf F} \\ \cline{2-5}
\end{tabular}
\end{center}
\end{itemize}


%--------------------------------------------------------------------------------------------


\newslide{CONSEQU\^ENCIA LÓGICA}


\noindent \textcolor{black}{Teorema:} $\beta\models \alpha$ se, e somente se,
 $\beta\Rightarrow\alpha$ \'{e} tautologia.

\vspace*{3mm}
\noindent \underline{Exemplos}:

\begin{itemize}
 \item \textcolor{black}{$[(p\Rightarrow q)\wedge(q\Rightarrow r)] \Rightarrow (p\Rightarrow r)$}
       \'{e} tautologia. Logo,

       \[\textcolor{black}{(p\Rightarrow q)\wedge(q\Rightarrow r)} \models \textcolor{black}{p\Rightarrow r}\mbox{.}\]
 \item \textcolor{black}{$(p\wedge \neg p)\Rightarrow q$} \'{e} tautologia. Logo,

       \[\textcolor{black}{p\wedge\neg p} \models \textcolor{black}{q}\mbox{.}\]
\end{itemize}
%--------------------------------------------------------------------------------------------


\newslide{EQUIVAL\^ENCIA LÓGICA}


\begin{itemize}
 \item $\alpha$ e $\beta$ s\~{a}o \textcolor{black}{logicamente equivalentes}, $\beta \equiv
        \alpha$, se e somente se $\alpha \models \beta$ e $\beta\models\alpha$
 \item \underline{Exemplo}: \textcolor{black}{$\neg (p\wedge q) \equiv \neg p \vee \neg q$}, pois:

\vspace*{3mm}
\hspace*{2cm} 
\begin{center}
\begin{tabular}{|c|c|c||c||c|c||c||} \hline
 \textcolor{black}{$p$} & \textcolor{black}{$q$} & \textcolor{black}{$p\wedge q$} & \textcolor{black}{$\neg (p\wedge q)$} & \textcolor{black}{$\neg p$} & \textcolor{black}{$\neg q$} &
  \textcolor{black}{$\neg p \vee \neg q$} \\ \hline
 {\bf V} & {\bf V} & {\bf V} & {\bf F} & {\bf F} & {\bf F} & {\bf F} \\
 {\bf V} & {\bf F} & {\bf F} & {\bf V} & {\bf F} & {\bf V} & {\bf V} \\
 {\bf F} & {\bf V} & {\bf F} & {\bf V} & {\bf V} & {\bf F} & {\bf V} \\
 {\bf F} & {\bf F} & {\bf F} & {\bf V} & {\bf V} & {\bf V} & {\bf V} \\ \hline
\end{tabular}
\end{center}

\end{itemize}


%--------------------------------------------------------------------------------------------

\newslide{EQUIVAL\^ENCIA LÓGICA}


\noindent \textcolor{black}{Teorema:} $\alpha\equiv \beta$ se, e somente se,
 $\alpha\Leftrightarrow\beta$ \'{e} tautologia.

\vspace*{3mm}
\noindent \underline{Exemplos}:

\begin{itemize}
 \item \textcolor{black}{$(p\Rightarrow q)\Leftrightarrow(\neg p\vee q)$} \'{e} tautologia. Logo,

       \[\textcolor{black}{p\Rightarrow q} \equiv \textcolor{black}{\neg p\vee q}\mbox{.}\]
 \item \textcolor{black}{$[p\Rightarrow (q\Rightarrow r)]\Leftrightarrow[(p\wedge q)\Rightarrow
        r]$} \'{e} tautologia. Logo,

        \[\textcolor{black}{p\Rightarrow (q\Rightarrow r)}\equiv \textcolor{black}{(p\wedge q)\Rightarrow r}\mbox{.}\]
\end{itemize}

%--------------------------------------------------------------------------------------------


\newslide{PREDICADOS E QUANTIFICADORES}

\noindent Exemplos de \textcolor{black}{f\'{o}rmulas at\^{o}micas}:

\begin{itemize}
 \item \textcolor{black}{$\mbox{irm\~{a}os}(\mbox{Abel}, \mbox{Caim})$}
 \item \textcolor{black}{$2+2=4$}
 \item \textcolor{black}{$x \geq 0$}
 \item \textcolor{black}{$x = y + 1$}
\end{itemize}

\vspace*{2mm}
\begin{itemize}
 \item \textcolor{black}{$\mbox{irm\~aos}$}, \textcolor{black}{$=$} e
        \textcolor{black}{$\geq$} s\~ao \textcolor{black}{predicados}.
 \item Predicados denotam rela\c{c}\~oes.
\end{itemize}
%--------------------------------------------------------------------------------------------

\newslide{PROPOSI\c{C}\~OES SIMPLES}

\noindent Uma \textcolor{black}{proposi\c{c}\~{a}o simples} \'{e} representada
por uma f\'{o}rmula at\^{o}mica.

\vspace*{5mm}
\noindent Exemplos:

\begin{itemize}
 \item \textcolor{black}{$\mbox{irm\~{a}os}(\mbox{Abel}, \mbox{Caim})$} (verdadeira)
 \item \textcolor{black}{$2+2=4$} (verdadeira)
 \item \textcolor{black}{$-1 \geq 0$} (falsa)
 \item \textcolor{black}{$0 = -1 + 1$} (verdadeira)
\end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{PROPOSI\c{C}\~OES COMPOSTAS}


\noindent Representadas a partir de  f\'{o}rmulas at\^{o}micas, utilizando-se
 conectivos l\'{o}gicos.

\vspace*{5mm}
\noindent Exemplos:

\begin{itemize}
 \item \textcolor{black}{$\mbox{irm\~{a}os}(\mbox{Abel}, \mbox{Caim}) \wedge \mbox{irm\~{a}os}(\mbox{Caim}, \mbox{Abel})$}
 \item \textcolor{black}{$2+2=4 \vee -1 \geq 0$}
\end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{OS QUANTIFICADORES}


\noindent Dois conectivos l\'{o}gicos adicionais:

\begin{itemize}
 \item \textcolor{black}{Quantificador universal}: \textcolor{black}{$\forall$}
 \item \textcolor{black}{Quantificador existencial}: \textcolor{black}{$\exists$}
\end{itemize}

\vspace*{3mm}
\noindent Exemplos de f\'ormulas quantificadas:
\begin{itemize}
 \item \textcolor{black}{$\forall x \, x\geq 0$}
 \item \textcolor{black}{$\forall x\forall y \, (\mbox{irm\~{a}os}(x,y)\Rightarrow
  \mbox{irm\~{a}os}(y,x))$}
 \item \textcolor{black}{$\exists x \, x\geq 0$}
 \item \textcolor{black}{$\forall x \exists y \, x = y + 1$}
 \item \textcolor{black}{$\exists x \forall y \, x = y + 1$}
\end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{EXEMPLO}


\noindent Sejam: 
\begin{itemize}
 \item \textcolor{black}{$A(x)$}: $x$ \'{e} uma arara.
 \item \textcolor{black}{$M(x)$}: $x$ \'{e} multicor.
 \item \textcolor{black}{$Q(x)$}: $x$ \'{e} pequena.
 \item \textcolor{black}{$G(x)$}: $x$ faz ninho em \'{a}rvores altas.
\end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{EXEMPLO}

\noindent Representa\c{c}\~{a}o de algumas afirma\c{c}\~{o}es:

\begin{itemize}
 \item Todas as araras s\~{a}o multicores.
       \begin{enumerate}
        \item[\ ] \textcolor{black}{$\forall x \, (A(x)\Rightarrow M(x))$}
       \end{enumerate}
 \item Nenhum p\'{a}ssaro pequeno faz ninho em \'{a}rvores altas.
       \begin{enumerate}
        \item[\ ] \textcolor{black}{$\neg \exists x \, (Q(x)\wedge G(x))$}
       \end{enumerate} 
 \item P\'{a}ssaros que n\~{a}o fazem ninhos em \'{a}rvores altas
       n\~ao s\~{a}o multicores.
       \begin{enumerate}
        \item[\ ] \textcolor{black}{$\forall x \, (\neg G(x)\Rightarrow \neg M(x))$}
       \end{enumerate} 
 \item Conclus\~{a}o: Araras s\~{a}o grandes.
       \begin{enumerate}
        \item[\ ] \textcolor{black}{$\forall x \, (A(x)\Rightarrow \neg Q(x))$}
       \end{enumerate} 
\end{itemize}

%--------------------------------------------------------------------------------------------


\newslide{ALGUMAS EQUIVAL\^ENCIAS LÓGICAS}

\begin{itemize}
 \item $\textcolor{black}{\forall x \, P(x)} \equiv \textcolor{black}{\neg \exists x \, \neg P(x)}$
 
 \vspace*{2mm}
 \item $\textcolor{black}{\exists x \, P(x)} \equiv \textcolor{black}{\neg \forall x \, \neg P(x)}$
 
 \vspace*{2mm}
 \item $\textcolor{black}{\neg \exists \,x P(x)} \equiv \textcolor{black}{\forall x \,\neg P(x)}$
 
 \vspace*{2mm}
 \item $\textcolor{black}{\neg \forall \,x P(x)} \equiv \textcolor{black}{\exists x \,\neg P(x)}$
 
 \vspace*{2mm}
 \item $\textcolor{black}{\forall x \,(P(x)\wedge Q(x))} \equiv \textcolor{black}{\forall x \,P(x)\wedge
                \forall x \,Q(x)}$
 
 \vspace*{2mm}
 \item $\textcolor{black}{\exists x \,(P(x)\vee Q(x))} \equiv \textcolor{black}{\exists x \,P(x)\vee
                \exists x \,Q(x)}$
\end{itemize}

%--------------------------------------------------------------------------------------------


\newslide{ALGUMAS CONSEQU\^ENCIAS LÓGICAS }

\begin{itemize}
 \item $\textcolor{black}{\forall x \,P(x)} \models \textcolor{black}{P(A)}$
 
 \vspace*{2mm}
 \item $\textcolor{black}{P(A)} \models \textcolor{black}{\exists x \,P(x)}$
 
 \vspace*{2mm}
 \item $\textcolor{black}{\forall x \,P(x) \vee \forall x \,Q(x)} \models \textcolor{black}{\forall x \,(P(x)\vee
                 Q(x))}$
 
 \vspace*{2mm}
 \item $\textcolor{black}{\exists x \,(P(x)\wedge Q(x))} \models \textcolor{black}{\exists x \,P(x)\wedge
                \exists x \,Q(x)}$
 
 \vspace*{2mm}
 \item $\textcolor{black}{\exists x \forall y \,P(x,y)} \models \textcolor{black}{\forall y \exists x \,P(x,y)}$
\end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{TÉCNICAS ELEMENTARES DE PROVA}
\hypertarget{tecnicas-prova-1}{}


\noindent Ser\~{a}o vistas {\bf t\'{e}cnicas de prova} para proposi\c{c}\~{o}es das formas:

\vspace*{3mm}
\begin{itemize}
 \item \textcolor{black}{$\alpha \Rightarrow \beta$}
 \item \textcolor{black}{$\exists x \,\alpha(x)$}
 \item \textcolor{black}{$\neg \exists x \alpha(x)$}
 \item \textcolor{black}{$\forall x \,\alpha(x)$}
 \item \textcolor{black}{$\neg \forall x \,\alpha(x)$}
\end{itemize}

\noindent al\'em de racioc\'{\i}nio \textcolor{black}{por casos} e por \textcolor{black}{absurdo}.

%--------------------------------------------------------------------------------------------

\newslide{TÉCNICAS PARA IMPLICA\c{C}\~AO ($\alpha\Rightarrow\beta$)}


\vspace*{3mm}
\begin{itemize}
 \item \textcolor{black}{Prova por vacuidade}: 
       \begin{itemize}
        \item \underline{Base}:
              \begin{quote}
               $\textcolor{red}{\mbox{contradi\c{c}\~ao}}\Rightarrow\beta$ \'e tautologia.
              \end{quote}
        \item \underline{M\'{e}todo}:
              \begin{quote}
               Provar que $\alpha$ \'{e} falsa.
              \end{quote}
        \item \underline{Exemplo}:
              \begin{quote}
               $\emptyset$ \'{e} subconjunto de qualquer conjunto.
              \end{quote}
       \end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{TÉCNICAS PARA IMPLICA\c{C}\~AO ($\alpha\Rightarrow\beta$)}


\item \textcolor{black}{Prova trivial}: 
       \begin{itemize}
        \item \underline{Base}:
              \begin{quote}
               $\alpha \Rightarrow \textcolor{red}{\mbox{tautologia}}$ \'e tautologia.
              \end{quote}
        \item \underline{M\'{e}todo}:
              \begin{quote}
               Provar que $\beta$ \'{e} sempre verdadeira.
              \end{quote}
        \item \underline{Exemplo}:
              \begin{quote}
               Se $x$ e $y$ s\~{a}o n\'{u}meros irracionais ent\~{a}o
               $x^y$ \'{e} um n\'{u}mero racional ou irracional.
              \end{quote}
       \end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{TÉCNICAS PARA IMPLICA\c{C}\~AO ($\alpha\Rightarrow\beta$)}


\item \textcolor{black}{Prova direta}: 
       \begin{itemize}
        \item \underline{Base}:
              \begin{quote}
               Se $\alpha \models \beta$ ent\~{a}o $\alpha
               \Rightarrow \beta$ \'{e} sempre verdadeira.
              \end{quote}
        \item \underline{M\'{e}todo}:
              \begin{enumerate}
               \item[a)] supor que $\alpha$ \'{e} verdadeira;
               \item[b)] mostrar que, neste caso, $\beta$ \'{e} verdadeira.
              \end{enumerate}
        \item \underline{Exemplo}:
              \begin{quote}
               Se $n$ \'{e} um n\'{u}mero \'{\i}mpar,
               ent\~{a}o $n^2$ \'{e} um n\'{u}mero \'{\i}mpar.
              \end{quote}
       \end{itemize}
%--------------------------------------------------------------------------------------------

\newslide{T\'ECNICAS PARA IMPLICA\c{C}\~AO ($\alpha\Rightarrow\beta$)}


 \item \textcolor{black}{Prova indireta}: 
       \begin{itemize}
        \item \underline{Base}:
              \begin{quote}
               $\alpha\Rightarrow \beta \equiv \neg \beta
              \Rightarrow \neg \alpha$.
              \end{quote}
        \item \underline{M\'{e}todo}:
              \begin{quote}
               Provar $\neg \beta \Rightarrow \neg \alpha$,
               utilizando um dos m\'{e}todos acima.
              \end{quote}
        \item \underline{Exemplo}:
              \begin{quote}
               O \textcolor{black}{princ\'{\i}pio da casa de pombos}
               (pigeonhole principle): se $n+1$ objetos s\~{a}o distribuidos em
               $n$ caixas, ent\~{a}o alguma caixa conter\'{a} pelo menos
               dois objetos.
              \end{quote}
       \end{itemize}
       

%--------------------------------------------------------------------------------------------

\newslide{TÉCNICA PARA A UNIVERSAL ($\forall x \, \alpha(x)$)}

 \item \textcolor{black}{Prova para a universal}:

       \begin{itemize}
        \item \underline{Base}:
              \begin{quote}
               Se $\beta \models \alpha(c)$ e $c$ n\~ao ocorre em $\beta$,
               ent\~{a}o $\beta \models \forall x \, \alpha(x)$.
              \end{quote}
        \item \underline{M\'{e}todo}:
              \begin{enumerate}
               \item[a)] Supor a exist\^encia de um $c$ arbitr\'ario;
               \item[b)] provar $\alpha(c)$.
              \end{enumerate}
       \end{itemize}


%--------------------------------------------------------------------------------------------

\newslide{T\'ECNICAS ELEMENTARES DE PROVA}

 \item \textcolor{black}{Prova por Casos}: 

       \begin{itemize}
        \item \underline{Base}:
              \begin{quote}
               $(\alpha_1\vee\cdots\vee \alpha_n)\wedge 
               (\alpha_1\Rightarrow \beta)\wedge\cdots\wedge
               (\alpha_n\Rightarrow \beta) \models \beta$
              \end{quote}
        \item \underline{M\'{e}todo para provar $\beta$ dado que $\alpha_1\vee\cdots\vee \alpha_n$}:
              \begin{quote}
               1. provar $\alpha_1 \Rightarrow \beta$; \\
               2. provar $\alpha_2 \Rightarrow \beta$; \\
               $\vdots$ \\
               $n$. provar $\alpha_n \Rightarrow \beta$.
              \end{quote}
        \item \underline{Exemplo}:
              \begin{quote}
               $min(x,y)+max(x,y)=x+y$ para quaisquer
               $x,y\in\textcolor{black}{R}$.
              \end{quote}
       \end{itemize}


%--------------------------------------------------------------------------------------------


%\newslide{TÉCNICAS ELEMENTARES DE PROVA}


%\noindent {\bf Prova de equival\^{e}ncias} da forma\\
%$(\alpha_1\Leftrightarrow\cdots\Leftrightarrow \alpha_n) \equiv
% (\alpha_1\Rightarrow \alpha_2)\wedge\cdots\wedge (\alpha_n\Rightarrow
%  \alpha_1)$:

%\vspace*{5mm}       
%\begin{itemize}
% \item \underline{M\'{e}todo}: provar $\alpha_1 \Rightarrow \alpha_2$; $\ldots$;
%       provar $\alpha_n \Rightarrow \alpha_1$.
%\end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{TÉCNICAS ELEMENTARES DE PROVA}


 \item \textcolor{black}{Prova por Contradi\c{c}\~{a}o}
       (redu\c{c}\~{a}o a absurdo) de $\alpha$:
       \begin{itemize}
        \item \underline{Base}:
              \begin{quote}
               Se $\beta\wedge\neg \alpha \models
               \textcolor{red}{\mbox{contradi\c{c}\~ao}}$, ent\~{a}o
               $\beta \models \alpha$.
              \end{quote}
        \item \underline{M\'{e}todo}:
              \begin{enumerate}
               \item[a)] Supor que $\alpha$ \'{e} sempre falsa;
               \item[b)] derivar uma contradi\c{c}\~{a}o.
              \end{enumerate}
        \item \underline{Exemplo}:
              \begin{quote}
               $\sqrt{2}$ \'{e} irracional.
              \end{quote}
       \end{itemize}
\end{itemize}


%--------------------------------------------------------------------------------------------



\newslide{PROVA DE N\~AO EXIST\^{E}NCIA (prova de $\neg\exists x  \,\alpha(x)$)}

\begin{itemize}
 \item $\neg \exists x \alpha(x)$ \'{e} frequentemente provado
       \textcolor{black}{por contradi\c{c}\~{a}o}:
       \begin{itemize}
        \item supor que existe um $c$ tal que $\alpha(c)$;
        \item derivar uma contradi\c{c}\~{a}o.
       \end{itemize}
\end{itemize}

%--------------------------------------------------------------------------------------------


\newslide{PROVA DE EXIST\^{E}NCIA (prova de $\exists x  \,\alpha(x)$)}

\begin{itemize}
 \item \textcolor{black}{Prova construtiva}:
       \begin{itemize}
        \item \underline{Base}:
              \begin{quote}
               $\alpha(c) \models \exists x \,\alpha(x)$.
              \end{quote}
        \item \underline{M\'{e}todo}:
              \begin{quote}
               Provar $\alpha(c)$, para um elemento espec\'{\i}fico $c$.
              \end{quote}
        \item \underline{Exemplo}:
              \begin{quote}
               Para qualquer $n\in \mbox{\bf N}$ existem
               pelo menos $n$ naturais consecutivos n\~{a}o primos.
              \end{quote}
       \end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{PROVA DE EXIST\^{E}NCIA (prova de $\exists x  \,\alpha(x)$)}


 \item \textcolor{black}{Prova n\~{a}o construtiva}:
       \begin{itemize}
        \item \underline{M\'{e}todo}:
              \begin{quote}
               Provar $\exists x \,\alpha(x)$, sem exibir um
               $x$ espec\'{\i}fico (por absurdo, por casos,\ldots).
              \end{quote}
        \item \underline{Exemplo}:
              \begin{quote}
               Existem dois irracionais $x$ e $y$ tais que
               $x^y$ \'{e} racional.
              \end{quote}
       \end{itemize}
\end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{CONTRA-EXEMPLO (para provar $\neg \forall x \,\alpha(x)$)}


\begin{itemize}
 \item \textcolor{black}{Prova por contra-exemplo}:
       \begin{itemize}
        \item \underline{Base}:
              \begin{quote}
               $\neg \alpha(c) \models \neg \forall x \,\alpha(x)$
              \end{quote}
        \item \underline{M\'{e}todo}:
              \begin{quote}
               Exibir, ou construir, um elemento $c$ para o qual
               $\alpha(c)$ \'{e} falsa.
              \end{quote}
        \item \underline{Exemplo}:
              \begin{quote}
               Todo n\'{u}mero primo \'{e} \'{\i}mpar.
              \end{quote}
        \end{itemize}
\end{itemize}

%--------------------------------------------------------------------------------------------

\newslide{INDU\c{C}\~AO MATEM\'ATICA}

\begin{itemize}
 \item \textcolor{black}{Prova por Indu\c{c}\~{a}o Matem\'{a}tica} \\
       para provar $\forall x \,\alpha(x)$, quando o universo \'{e}
       \textcolor{black}{N}:

      \begin{itemize}
       \item \underline{Base}:
              \begin{quote}
               $\alpha(0)\wedge\forall x \,(\alpha(x)\Rightarrow
               \alpha(x+1))\models \forall x \alpha(x)$.
              \end{quote}
        \item \underline{M\'{e}todo}:
              \begin{list}{\alph{conta})}{\usecounter{conta}}
               \item \underline{Passo Base}: provar $\alpha(0)$;
               \item \underline{Passo Indutivo}: provar
                     $\forall x \,(\alpha(x)\Rightarrow\alpha(x+1))$.
              \end{list}
      \end{itemize}
\end{itemize}

%--------------------------------------------------------------------------------------------
