\documentclass[11pt,a4paper]{article}

%\usepackage[portuguese]{babel}
\usepackage{fullpage}

\newcounter{conta}
\newcounter{conta2}
\hyphenation{pro-ble-mas}
\begin{document}

%\selectlanguage{portuguese}

\vspace*{8mm}
\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 2010 \\
Professor: \parbox[t]{14cm}{Newton Jos\'{e} Vieira \\
                     e-mail: nvieira@dcc.ufmg.br; sala 4023/ICEx} \\
{\bf Plano de Curso}

\vspace*{3mm}
\section{Ementa}
 
Conceitos b\'asicos de l\'ogica matem\'atica.
Estrat\'egias para demonstra\c c\~ao de teoremas.
Indu\c c\~ao matem\'atica. Recursividade.
 
\section{Programa}

\begin{list}{\arabic{conta}}{\usecounter{conta}}
 \item Conceitos b\'asicos de l\'ogica proposicional e de predicados:
       sintaxe e sem\^antica; satisfatibilidade e falseabilidade;
       tautologia e contradi\c c\~ao; equival\^encia l\'ogica;
       conseq\"u\^encia l\'ogica; consist\^encia; dedu\c c\~ao;
       refuta\c c\~ao; corre\c c\~ao e completude;
       a complexidade/decidibilidade do
       problema de dedu\c c\~ao autom\'atica.
 \item Conceitos b\'asicos de teoria dos conjuntos \`a luz das no\c c\~oes
       de l\'ogica: vari\'aveis e conjuntos; opera\c c\~oes; an\'alise da
       forma l\'ogica de afirmativas envolvendo conjuntos; conjuntos
       \'{\i}ndice; opera\c c\~oes envolvendo fam\'{\i}lias de conjuntos.
 \item Demonstra\c c\~oes: os conceitos de teorema, hip\'otese, lema e
       contraexemplo; estrat\'egias de prova relativas a cada conectivo
       l\'ogico: $\rightarrow$, $\leftrightarrow$, $\neg$, $\vee$, $\wedge$,
       $\forall$, $\exists$; prova por contradi\c c\~ao; prova de unicidade;
       o processo de infer\^encia: como usar o que se conhece, as
       hip\'oteses e o que vai sendo deduzido; prova por casos.
 \item Aplica\c c\~oes: demonstra\c c\~oes envolvendo rela\c c\~oes e
       as propriedades de reflexividade, simetria e transitividade;
       rela\c c\~oes de equival\^encia; rela\c c\~oes de ordem parcial;
       demonstra\c c\~oes envolvendo os conceitos de fun\c c\~oes injetoras,
       sobrejetoras e bijetoras.
 \item Indu\c c\~ao matem\'atica: onde voc\^e aprende, \`a luz dos
       conhecimentos anteriores, o verdadeiro significado de uma
       demonstra\c c\~ao por indu\c c\~ao matem\'atica; indu\c c\~ao
       fraca; indu\c c\~ao forte; recursividade; conjuntos enumer\'aveis;
       a rela\c c\~ao entre indu\c c\~ao matem\'atica, defini\c c\~ao
       recursiva e conjuntos enumer\'aveis.
\end{list}
 
\section{Bibliografia}

Assume-se, como prerequisito, que o aluno conhece rudimentos de conjuntos,
no n\'{\i}vel visto normalmente em uma disciplina de matem\'atica discreta.
Exemplos de livros que abordam conjuntos em tal n\'{\i}vel:
\begin{enumerate}
 \item Dean, N. {\em The Essence of Discrete Mathematics\/}, Prentice Hall, 1997.
 \item Grimaldi, R.P. {\em Discrete and Combinatorial Mathematics: An Applied Introduction\/},
       5th ed., Addison-Wesley, 2003.
 \item Rosen, K.H. {\em Discrete Mathematics and its Applications\/},
       6th ed., McGraw-Hill, 2006.
\end{enumerate}

\newpage
\vspace*{8mm}
A parte de l\'ogica matem\'atica poder\'a ser acompanhada a partir de
notas de aula a serem distribu\'{\i}das durante o curso, notas estas
que poder\~ao ser complementadas pelo estudo em livros como:
\begin{enumerate}
 \item Ben-Ari, M. {\em Mathematical Logic for Computer Science}, 2nd ed.,
       Springer-Verlag, 2001. 
 \item Bonevac, D. {\em Deduction: Introdutory symbolic logic\/}, 2nd ed.,
       Wiley-Blackwell, 2003.
 \item Enderton, H.B. {\em A Mathematical Introduction to Logic\/}, 2nd ed.,
       Academic Press, 2000.
 \item Huth, M.R.A., Ryan, M.D. {\em Logic in Computer Science: Modelling
       and reasoning about systems\/}, 2nd ed., Cambridge University Press,
       2004.
 \item Smullyan, R.M. {\em First-Order Logic\/}, Dover, 1968.
 \item Smullyan, R.M. {\em Logical Labyrinths\/}, A K Peters Ltd, 2009.
 \item Tarski, A. {\em Introduction to Logic and to the Methodology of Deductive Sciences\/},
       Dover, 1995.
\end{enumerate}

O restante do curso ser\'a coberto utilizando-se como base o
livro:
\begin{enumerate}
 \item[\ ] Velleman, D.J. {\em How To Prove It: A structured approach}, 2nd ed.,
       Cambridge University Press, 2006.
\end{enumerate}

Outros livros que poder\~ao ser utilizados em um ou outro t\'opico:
\begin{enumerate}
 \item Cupillari, A. {\em The Nuts and Bolts of Proofs}, 3rd ed.,
       Academic Press, 2005. 
 \item Eccles, P.J. {\em An Introduction to Mathematical Reasoning:
       Numbers, sets and functions}, Cambridge University Press, 1997. 
 \item P\'olya, G. {\em How to Solve It: A new aspect of mathematical
       method}, Princeton University Press, 1945. 
 \item Solow, D. {\em How to Read and Do Proofs}, 4th ed., John Wiley \& Sons,
       2005. 
\end{enumerate}

\section{Avalia\c{c}\~ao}
 
Ap\'os a primeira semana de aula, ser\~ao distribu\'{\i}das listas
de exerc\'{\i}cios semanais. A avalia\c c\~ao ser\'a feita com base
nesses exerc\'{\i}cios, valendo 80\%, e em um teste final, valendo
20\%. 

As listas de exerc\'{\i}cios, assim como este Plano de Curso e outras informa\c c\~oes,
estar\~ao disponiveis na p\'agina
http://www.dcc.ufmg.br/\verb+~+nvieira, na entrada relativa \`a disciplina.

\end{document}

