Introdução

Matemática Discreta

Prof° Marcelo Maraschin de Souza

Disciplina

❏ Aulas:

Segunda-feira e terça-feira: 8:00 até 9:50

❏ Avaliações: listas de exercícios e três provas;

❏ Livros disponíveis na biblioteca (primeira parte do

conteúdos será baseada nos livros de Gersting e Garcia

et al).

Conteúdos

• Introdução;

• Lógica Proposicional e de primeira ordem;

• Conjuntos;

• Relações;

• Sequências e somas;

• Indução e recursão;

• Análise Combinatória;

• Elementos da teoria dos números.

Matemática Discreta

• É o estudo das estruturas algébricas discretas, em vez

de contínuas;

• Os objetos estudados em matemática discreta (números

inteiros, grafos, afirmações lógicas, etc) não variam

suavemente, mas tem valores distintos separados

(discrete);

• A matemática discreta tem sido caracterizada como o

ramo da matemática que lida com conjuntos contáveis.

• É o estudo matemático baseado em conjuntos contáveis,

finitos ou infinitos (ex: números naturais x reais).

Matemática Discreta x Computação

Segundo Diretrizes Curriculares do MEC,

“A matemática, para a área de computação, deve ser vista como

uma ferramenta a ser usada na definição formal de conceitos

computacionais. Os modelos formais permitem definir suas propriedades e

dimensionar suas instâncias, dadas suas condições de contorno. (...)

Considerando que a maioria dos conceitos computacionais pertencem ao

discreto, a matemática discreta é fortemente empregada.”

Qualquer sistema computacional possui limitações finitas

como, por exemplo, tamanho de memória, arredondamento,

etc.

Contínuo x Discreto

Contínuo x Discreto

Contínuo:

• álgebra linear e geometria analítica (fase 2);

• cálculo diferencial e integral (fase 3);

Discreto:

• Aritmética básica em computadores;

• Programação;

• Estrutura de dados;

• Grafos;

• Inteligência artificial;

• Cálculo numérico (fase 4);

• Simulação (pesquisa científica), etc.

Outros Exemplos

Velocidade de uma Ferrari 430 Scuderia 2008

Outros Exemplos

Imagens digitais

Outros Exemplos

Mapas (exemplo de grafo)

Outros Exemplos

Simulação computacional (elementos finitos)

Reforçando o entendimento

1) Seja a função 𝑓 𝑥 = 𝑥 + 1 com 𝑥 ∈ ℕ, então o conjunto

de valores de f é finito ou infinito? Este conjunto é

contável? Essa função é contínua?

2) Agora, no exemplo 1 considere 𝑥 ∈ ℝ. Responda as

mesmas perguntas.

Lógica

• A lógica matemática é a base pra qualquer estudo em

computação, em particular, para o estudo da matemática

discreta;

• Para desenvolver qualquer algoritmo e

consequentemente, qualquer software computacional,

são necessários conhecimentos básicos de lógica.

• Por isso, nosso primeiro tópico da disciplina será a lógica

formal.

Lógica

Em uma palestra no Simpósio Brasileiro de Engenharia de

Software, David Parnas, importante pesquisador

internacional e um dos pioneiros da engenharia de software

afirmou,

“O maior avanço da engenharia de software nos últimos dez

anos foram os provadores de teoremas.”

Exemplos de problemas: Pitágoras, Báskara, caminho até o

IFSC, tese de doutorado, etc.

Problema dos dois exércitos

Considere um campo de batalha com o seguinte cenário:

Problema dos dois exércitos

• O exército Azul está em maior número que o Branco, porém dividido

em dois;

• Cada metade do exército Azul está em menor número;

• Objetivo do Azul: coordenar ataque em conjunto ao exército Branco;

• O general do Azul 1 envia seu melhor soldado para entregar a seguinte

mensagem para o Azul 2:

“Vamos atacar conjuntamente o exército Branco amanhã às 6hs.”

Obs: ambos generais tem os relógios perfeitamente sincronizados e a

única forma de comunicação entre os generais é o mensageiro.

• O soldado entrega a mensagem pro general do Azul 2, que concorda

com o ataque, após isso, o soldado retorna até o Azul 1 e confirma com

seu general o ataque no dia seguinte.

• Sabendo disso, o que houve no dia seguinte?

Para pensar:

(CESPE 2014) Determine a negação da proposição “Lívia é

estudiosa e Marcos decora”.

a) Lívia é estudiosa ou Marcos decora

b) Lívia não é estudiosa e Marcos não decora.

c) Lívia não é estudiosa ou Marcos decora.

d) Lívia não é estudiosa ou Marcos não decora.

e) Marcos não decora e Lívia é estudiosa.

Para pensar:

ALTERNATIVA D

Para uma conjunção ser FALSA, basta que

apenas UMA das proposições que a forma também seja.

Logo, para negar uma conjunção basta que uma OU

OUTRA proposição seja falsa.