Introdução a matematica discreta

Cap´tulo 1 ı Introdu¸˜o a Matematica Discreta e ca `
´
Logica Formal
´
Edmilson Marmo Moreira
Universidade Federal de Itajub´ - UNIFEI a Instituto de Engenharia de Sistemas e Tecnologias da Informa¸˜o - IESTI ca “A maravilhosa disposi¸˜o e harmonia do universo s´ pode ter tido origem segundo ca o o plano de um Ser que tudo sabe e tudo pode. Isto fica sendo a minha ultima e
´
mais elevada descoberta”.
Isaac Newton

1

Considera¸˜es Iniciais co Este curso tem por objetivo apresentar os principais conceitos da Matem´tica Disa creta. Praticamente qualquer estudo em Computa¸ao e Inform´tica, te´rico ou aplicado, c˜ a o exige como pr´-requisito conhecimentos de diversos t´picos de matem´tica. Tal fato ´ e o a e normalmente explicitado na maioria dos livros de Computa¸ao e Inform´tica, sendo que c˜ a alguns possuem um cap´ ıtulo espec´ ıfico no qual tais t´picos s˜o brevemente ou resumidao a mente introduzidos (MENEZES, 2005).
As Diretrizes Curriculares do MEC para cursos de Computa¸ao e Inform´tica afirmam c˜ a que: “a matem´tica, para a ´rea da computa¸˜o, deve ser vista como uma ferramenta a a ca a ser usada na defini¸˜o formal de conceitos computacionais (linguagens, autˆmatos, ca o m´todos etc). Os modelos formais permitem definir suas propriedades e dimensionar suas e instˆncias, dadas suas condi¸˜es de contorno” (MEC, 2005). a co
Neste contexto, o aluno, acompanhando satisfatoriamente o conte´do deste curso, ir´: u a
1. Desenvolver a sua capacidade de ler, compreender e construir argumentos matem´a ticos; 2. Obter uma vis˜o abrangente de uma parte significativa da Computa¸ao e Inform´a c˜ a tica; 3. Estudar como trabalhar com estruturas discretas, que s˜o estruturas matem´ticas a a abstratas, usadas para representar objetos discretos e o relacionamento entre estes
1

Matem´tica Discreta - Notas de Aula - Cap´tulo 01 - 2 a ı objetos. Estas estruturas incluem conjuntos, permuta¸˜es, rela¸˜es,