Matemática discreta
A matemática discreta é a matemática das coisas separadas e contáveis: verdadeiro ou falso, dentro de um conjunto ou fora dele, este caminho ou aquele. É a matemática em que os computadores rodam, e ela começa com uma lógica que você liga e desliga.
Última atualização
A matemática discreta é a matemática das coisas separadas e contáveis. Uma afirmação é verdadeira ou falsa, um elemento está num conjunto ou não, uma rede tem uma ligação entre dois pontos ou não tem. Não existe meio-termo, e é isso que "discreto" quer dizer, e é exatamente assim que um computador vê o mundo.
Uma primeira disciplina cobre seis temas: lógica, conjuntos, contagem, grafos, teoria dos números e demonstração. A lógica vem primeiro, porque todos os outros temas são escritos nela. Escolha um conectivo abaixo e alterne p e q.
Tabela-verdade de p ∧ q
| p | q | p ∧ q |
|---|---|---|
| V | V | V |
| V | F | F |
| F | V | F |
| F | F | F |
Alterne p e q, ou clique numa linha. A linha destacada é a que eles escolhem.
Leia p como "x está em A" e q como "x está em B". As regiões pintadas são onde a proposição é verdadeira; o ponto é a linha atual.
p ∧ q
Como se lê p e q
Com estes valores, p ∧ q é verdadeira.
Verdadeira só quando p e q são as duas verdadeiras.
Como conjuntos E é interseção: x está em A ∩ B exatamente quando x está em A e x está em B.
Lógica: proposições e conectivos
Uma proposição é uma frase que é verdadeira ou falsa, como "7 é primo" ou "está chovendo". A lógica constrói proposições maiores a partir de menores com alguns conectivos, e uma tabela-verdade lista o resultado para cada combinação de entradas.
| símbolo | nome | como se lê | verdadeira quando |
|---|---|---|---|
| ∧ | E, conjunção | "p e q" | as duas são verdadeiras |
| ∨ | OU, disjunção | "p ou q" | pelo menos uma é verdadeira |
| ¬ | NÃO, negação | "não p" | p é falsa |
| ⊕ | XOR, ou exclusivo | "p ou q, mas não as duas" | exatamente uma é verdadeira |
| → | IMPLICA, condicional | "se p, então q" | em todos os casos, exceto p verdadeira e q falsa |
| ↔ | SSE, bicondicional | "p se e somente se q" | p e q têm o mesmo valor |
Dois deles surpreendem. O OU lógico é inclusivo: "p ou q" é verdadeira quando as duas são verdadeiras, ao contrário do "chá ou café?" do dia a dia. A versão exclusiva tem nome próprio, XOR.
O outro é o IMPLICA. p → q só é falsa numa linha, quando p é verdadeira e q é falsa. Pense nela como uma promessa: "se chover, eu levo o guarda-chuva". A promessa só é quebrada se chover e não houver guarda-chuva. Num dia seco a promessa não foi quebrada, leve você o que levar, então a proposição conta como verdadeira.
Proposições equivalentes
Duas proposições são equivalentes quando suas tabelas-verdade coincidem em todas as linhas. No widget, escolha OU e negue p: a coluna de ¬p ∨ q é idêntica à coluna de p → q, então as duas dizem a mesma coisa.
As equivalências mais úteis são as leis de De Morgan, que dizem como o NÃO atravessa o E e o OU:
¬(p ∧ q) ≡ ¬p ∨ ¬q
¬(p ∨ q) ≡ ¬p ∧ ¬q
Em palavras: "não as duas" é o mesmo que "uma ou a outra é falsa", e "nenhuma" é o mesmo que "as duas são falsas". Programadores usam isso todo dia para reescrever uma condição como "não (logado e verificado)".
Lógica e conjuntos são uma ideia só
Leia p como "x está em A" e q como "x está em B". Então o E é a interseção, o OU é a união e o NÃO é o complementar, e toda tabela-verdade é um diagrama de Venn pintado, e é por isso que o widget desenha um ao lado da tabela. As leis de De Morgan viram regras sobre conjuntos:
(A ∩ B)′ = A′ ∪ B′
A página de notação de conjuntos pinta cada uma delas num diagrama que você pode clicar.
Contagem
Contar em matemática discreta significa contar sem listar. Duas regras fazem a maior parte do trabalho.
O princípio multiplicativo. Se uma escolha pode ser feita de m maneiras e uma segunda de n maneiras, o par pode ser feito de m × n maneiras. Uma senha de 4 dígitos tem 10 opções para cada dígito, então há 10^4 = 10000 senhas possíveis.
Combinações. O número de maneiras de escolher k coisas entre n, quando a ordem não importa, se escreve C(n, k). Escolher 3 coberturas entre 8:
C(8, 3) = (8 × 7 × 6) / (3 × 2 × 1) = 56
O numerador conta as escolhas ordenadas, e dividir por 3 × 2 × 1 remove as 6 ordens em que as mesmas três coberturas poderiam ter sido escolhidas.
A resposta é 6 × 5 dividido por 2, que é 15. Se você obteve 30, contou cada dupla duas vezes, uma em cada ordem.
Grafos
Um grafo é um conjunto de pontos, chamados vértices, ligados por linhas, chamadas arestas. Ele modela qualquer coisa feita de conexões: estradas entre cidades, amigos numa rede social, links entre páginas da web.
Um primeiro resultado: se 5 pessoas se cumprimentam todas uma vez com um aperto de mão, há C(5, 2) = 10 apertos de mão. Cada pessoa aperta 4 mãos, o que dá 5 × 4 = 20 pontas de aperto, e todo aperto tem duas pontas, então 20 / 2 = 10. Esse argumento é o lema do aperto de mãos: os graus de todos os vértices somam o dobro do número de arestas.
Teoria dos números e demonstração
A aritmética modular é a aritmética num relógio. 17 mod 5 é 2, o resto quando 17 é dividido por 5. Nove horas depois das 8 horas são 5 horas, porque 17 mod 12 é 5. A mesma ideia, com números enormes, é como funciona a criptografia RSA por trás dos sites seguros.
A demonstração por indução mostra que uma afirmação vale para todo número natural n em dois passos: verifique para n = 1, depois mostre que, se ela vale para algum n, também vale para n + 1. É assim que se prova, por exemplo, que
1 + 2 + ... + n = n(n + 1) / 2
para todo n, não só para os valores que você testou.
Para que serve a matemática discreta
- Programação: todo if é lógica, e as leis de De Morgan reescrevem condições.
- Bancos de dados: uma consulta que junta ou filtra tabelas é feita de operações com conjuntos.
- Algoritmos: a contagem diz quantos passos um programa leva à medida que a entrada cresce.
- Redes e mapas: rotas mais curtas e redes sociais são problemas de grafos.
- Segurança: a criptografia se apoia na teoria dos números e na aritmética modular.
- Hardware: um processador é construído com portas lógicas, que são tabelas-verdade em silício.
Matemática discreta é difícil?
É difícil de um jeito diferente da álgebra e do cálculo. Há poucas fórmulas para decorar e as contas são pequenas, mas muitas questões pedem para você provar algo em vez de calcular, e escrever um argumento convincente é uma habilidade nova para a maioria dos alunos.
O que mais ajuda é resolver casos pequenos à mão antes de procurar o padrão: desenhe o diagrama de Venn, escreva a tabela-verdade, liste todos os casos. A notação parece pesada no começo, mas quase toda ela são os símbolos desta página e da página de notação de conjuntos.
Perguntas frequentes
- O que é matemática discreta?
- O ramo da matemática que estuda objetos separados e contáveis, em vez de grandezas que variam de forma suave. Seus temas principais são lógica, conjuntos, contagem, grafos, teoria dos números e demonstração. O cálculo pergunta como as coisas mudam de forma contínua; a matemática discreta pergunta quantos, quais e se uma afirmação é verdadeira.
- Matemática discreta é difícil?
- É difícil de um jeito diferente do cálculo. Há menos fórmulas para aplicar e mais argumentos para construir, e para muitos alunos é a primeira disciplina construída em torno de escrever demonstrações. A álgebra costuma ser leve. Quem acha difícil está quase sempre se adaptando às demonstrações, e isso melhora rápido com prática em exemplos pequenos.
- Para que serve a matemática discreta?
- Para quase tudo em computação. A lógica é como funcionam os circuitos e os comandos if, os conjuntos estão por trás das consultas a bancos de dados, a contagem diz quanto tempo um algoritmo leva, os grafos modelam redes e mapas, e a teoria dos números é a base da criptografia que protege os pagamentos online.
- Que temas a matemática discreta cobre?
- Uma primeira disciplina típica cobre lógica proposicional e tabelas-verdade, conjuntos e diagramas de Venn, funções e relações, técnicas de demonstração incluindo indução, contagem com permutações e combinações, probabilidade básica, grafos e árvores, e aritmética modular. Algumas disciplinas acrescentam relações de recorrência e álgebra booleana.
- Preciso de matemática discreta para ciência da computação?
- Sim. Quase todo curso de ciência da computação exige essa disciplina, normalmente no primeiro ou segundo ano, porque algoritmos, estruturas de dados e teoria da computação partem dela. Para programar por conta própria dá para começar sem ela, mas lógica, conjuntos e contagem aparecem no código do dia a dia mais cedo do que a maioria espera.
- Qual a diferença entre matemática discreta e contínua?
- A matemática discreta trata de valores que você pode listar um a um, como números inteiros, verdadeiro e falso, ou os nós de uma rede. A matemática contínua, como o cálculo, trata de grandezas que podem assumir qualquer valor num intervalo, como tempo, distância ou temperatura.
- O que é uma tabela-verdade?
- Uma tabela que lista todas as combinações de verdadeiro e falso para as entradas de uma proposição lógica, e o valor da proposição em cada uma. Com duas entradas p e q há quatro linhas. Uma tabela-verdade é como se prova que duas proposições são equivalentes: se as colunas delas coincidem em todas as linhas, elas sempre concordam.
