Matemática discreta estuda estruturas compostas por objetos separados ou contáveis, em contraste com os domínios contínuos da análise. Conjuntos finitos, sequências, relações, grafos, códigos, estruturas algébricas e ordens parciais são exemplos centrais desse campo. Na ciência da computação, quase toda representação formal de dados e quase todo algoritmo dependem de ideias discretas.

Este capítulo reúne alguns dos temas mais recorrentes da área: iteração e indução, teoria dos conjuntos, pares ordenados, relações, funções, álgebra booleana, ordens, estruturas algébricas, teoria dos códigos e teoria dos domínios. O objetivo não é esgotar cada assunto, mas apresentar os conceitos com clareza suficiente para que eles sirvam de base para algoritmos, lógica, estruturas de dados, linguagens formais, circuitos e teoria da computação.

Iteração, indução e recursão são três ideias intimamente ligadas. Iterar significa repetir um procedimento. Induzir significa provar uma propriedade para todos os naturais a partir de um caso base e de um passo geral. Recursão significa definir um objeto em termos de versões menores dele mesmo. Em computação, essas três noções aparecem em laços, provas de correção e definições de funções ou estruturas.

Um processo iterativo repete instruções até atingir uma condição de parada. Por exemplo, ao somar os elementos de um vetor, percorremos as posições uma a uma. Em cálculo numérico, iteração também aparece em aproximações sucessivas, como ao buscar uma raiz por refinamentos progressivos.

A indução matemática é uma técnica de prova sobre os números naturais. Para demonstrar que uma proposição $P(n)$ vale para todo $n \in \mathbb{N}$, mostramos:

1. caso base: $P(0)$ ou $P(1)$ é verdadeiro, conforme o contexto;
2. passo indutivo: assumindo $P(k)$ verdadeiro, mostramos que $P(k+1)$ também é verdadeiro.

Considere a proposição

$$ P(n): n+n = 2n $$

No caso base, para $n=1$, temos

$$ 1+1 = 2 = 2\cdot 1 $$

Agora supomos que a igualdade vale para um inteiro arbitrário $k$:

$$ k+k = 2k $$

Então, para $k+1$, obtemos

$$ (k+1)+(k+1)=k+k+2=2k+2=2(k+1) $$

Logo, a propriedade vale para $k+1$, e portanto para todo natural.

A recursão descreve um valor ou procedimento usando instâncias menores do mesmo problema. O exemplo clássico é o fatorial:

$$ 0! = 1,\qquad n! = n\cdot (n-1)! \;\; \text{para } n\geq 1 $$

Essa definição contém um caso base e um passo recursivo. Sem caso base, a definição não termina; sem redução para instâncias menores, a recursão não é bem fundada.

Outro exemplo importante é a sequência definida por

$$ f(0)=1,\qquad f(n+1)=2f(n) $$

Os primeiros termos são

$$ f(1)=2,\qquad f(2)=4,\qquad f(3)=8 $$

e em geral reconhecemos o padrão $f(n)=2^n$. Em programação, definições como essa se traduzem naturalmente em funções recursivas, mas também podem ser implementadas iterativamente.

Na prática, iteração e recursão costumam resolver os mesmos problemas, mas com estilos diferentes. Percorrer uma árvore, decompor um problema por divisão e conquista ou definir linguagens formais geralmente favorece recursão. Já processar arrays, contadores e acumulações simples costuma favorecer iteração. A indução serve como ponte teórica entre os dois estilos, porque muitas correções de algoritmos recursivos e iterativos são demonstradas indutivamente.

Conjuntos são coleções de objetos chamadas elementos. Escrevemos $x\in A$ para dizer que $x$ pertence ao conjunto $A$, e $x\notin A$ quando não pertence. A teoria dos conjuntos fornece uma linguagem básica para praticamente toda a matemática e, em computação, para descrever domínios, coleções de estados, linguagens formais e relações.

Embora a ideia intuitiva de conjunto pareça simples, sua formalização exigiu cuidado. Paradoxos como o de Russell mostraram que não é seguro admitir qualquer coleção definida por linguagem informal. Por isso, as teorias modernas de conjuntos adotam axiomas, isto é, princípios formais que delimitam quais conjuntos podem ser construídos.

Os diagramas de Venn são úteis para visualizar operações, mas a definição formal é dada pela pertinência dos elementos. As operações mais comuns são:

União:

$$ x\in A\cup B \Leftrightarrow (x\in A \lor x\in B) $$

Intersecção:

$$ x\in A\cap B \Leftrightarrow (x\in A \land x\in B) $$

Diferença:

$$ A-B=\{x\mid x\in A \land x\notin B\} $$

Complemento, em relação a um universo $U$:

$$ \overline{A} = U-A $$

Conjunto das partes:

$$ \mathcal{P}(A)=\{X\mid X\subseteq A\} $$

Se $A$ tem $n$ elementos, então $\mathcal{P}(A)$ tem $2^n$ subconjuntos.

Produto cartesiano:

$$ A\times B=\{(a,b)\mid a\in A \land b\in B\} $$

Essas operações se conectam diretamente à lógica proposicional. União corresponde a disjunção, intersecção corresponde a conjunção, complemento corresponde a negação e inclusão $A\subseteq B$ se relaciona à implicação “se $x\in A$, então $x\in B$”. Essa ponte entre conjuntos e lógica é uma das razões pelas quais a matemática discreta é tão importante para a computação.

Exemplo: se $A=\{1,2,3\}$ e $B=\{3,4\}$, então

$$ A\cup B=\{1,2,3,4\},\qquad A\cap B=\{3\},\qquad A-B=\{1,2\} $$

e

$$ A\times B=\{(1,3),(1,4),(2,3),(2,4),(3,3),(3,4)\} $$

Em computação, conjuntos aparecem em coleções de estados, linguagens reconhecidas por autômatos, tabelas de símbolos, grupos de usuários, permissões, domínios de função e expressões de consulta. O conjunto das partes, em especial, está por trás da explosão combinatória, porque enumerar todos os subconjuntos de um conjunto com $n$ elementos custa em geral $2^n$ possibilidades.

Um par ordenado é uma dupla de elementos em que a posição importa. Escrevemos $(x,y)$ ou $\langle x,y\rangle$. Diferentemente de conjuntos, em que a ordem não importa, aqui em geral vale

$$ (x,y)\neq (y,x) $$

a menos que $x=y$.

Esse conceito é fundamental porque produto cartesiano, relações, funções, coordenadas, vetores e tuplas de banco de dados são todos construídos a partir de pares ou n-uplas ordenadas. Se $A$ e $B$ são conjuntos, então um elemento de $A\times B$ tem a forma $(a,b)$ com $a\in A$ e $b\in B$.

A generalização natural é a n-upla:

$$ (x_1,x_2,\ldots,x_n) $$

Ela é usada em vetores, registros, estados de algoritmos e linhas de tabelas relacionais.

No plano cartesiano, por exemplo, um ponto é representado por um par ordenado $(x,y)$. No espaço, usamos triplas $(x,y,z)$. Em programação, um par como (usuario, permissao) pode descrever uma relação entre um elemento e uma propriedade associada.

Se tratarmos pares ordenados como vetores em $\mathbb{R}^2$, podemos definir operações como soma:

$$ (x_1,x_2)+(y_1,y_2)=(x_1+y_1,\;x_2+y_2) $$

e multiplicação por escalar:

$$ \lambda(x_1,x_2)=(\lambda x_1,\lambda x_2) $$

Essas operações mostram como a noção aparentemente simples de par ordenado serve de base tanto para estruturas abstratas quanto para aplicações geométricas e computacionais.

Antes de definir função, convém passar por uma noção mais geral: relação. Uma relação binária de $A$ em $B$ é qualquer subconjunto de $A\times B$. Escrevemos

$$ R\subseteq A\times B $$

Se $(a,b)\in R$, também podemos escrever $aRb$.

Exemplo: se $A=\{1,2,3\}$ e $B=\{2,4,6\}$, a relação “$b=2a$” entre $A$ e $B$ é

$$ R=\{(1,2),(2,4),(3,6)\} $$

Uma endorrelação é uma relação de um conjunto em si mesmo, isto é, um subconjunto de $A\times A$. Relações desse tipo podem ser visualizadas por grafos dirigidos e também por matrizes de adjacência quando o conjunto é finito.

Quando $A$ e $B$ são finitos, uma relação também pode ser descrita por uma matriz $M$ de zeros e uns, em que $M_{ij}=1$ quando o elemento $a_i$ se relaciona com $b_j$.

A composição de relações é definida por

$$ S\circ R=\{(a,c)\mid \exists b\in B\; (aRb \land bSc)\} $$

Ela expressa a ideia de aplicar uma relação após outra.

Uma função é uma relação especial. Intuitivamente, ela associa a cada elemento do domínio exatamente um elemento do contradomínio. Formalmente, uma relação $f\subseteq A\times B$ é função quando:

1. é total no domínio: para todo $a\in A$, existe algum $b\in B$ tal que $(a,b)\in f$;
2. é univalorada: se $(a,b_1)\in f$ e $(a,b_2)\in f$, então $b_1=b_2$.

Escrevemos então

$$ f:A\rightarrow B $$

e, quando $(a,b)\in f$, escrevemos $f(a)=b$.

Exemplo: a função

$$ f:\mathbb{N}\rightarrow \mathbb{N},\qquad f(n)=n+1 $$

associa a cada natural seu sucessor. Já a relação “ser menor que” em $\mathbb{N}$ não é função, porque um mesmo número se relaciona com muitos outros.

Em computação, funções aparecem em praticamente todo lugar: métodos em programas, mapeamentos entre estados, transformações de dados, codificações, hash functions, linguagens funcionais e semântica formal. Também são essenciais em análise de algoritmos, quando descrevemos custo como função do tamanho da entrada.

A álgebra booleana modela raciocínio com dois valores, normalmente 0 e 1, falso e verdadeiro, desligado e ligado. Ela é a base matemática dos circuitos digitais e também uma linguagem conveniente para expressar condições lógicas em programas.

Uma álgebra booleana pode ser escrita como

$$ \langle B,+,*,',0,1\rangle $$

onde $+$ representa uma operação análoga ao “ou”, $*$ uma operação análoga ao “e”, e $'$ o complemento. No caso mais simples, $B=\{0,1\}$.

As propriedades centrais incluem comutatividade, distributividade, elementos neutros e complementação:

1. $a+b=b+a$ e $a*b=b*a$;
2. $a+(b*c)=(a+b)*(a+c)$ e $a*(b+c)=(a*b)+(a*c)$;
3. $a+0=a$ e $a*1=a$;
4. $a+a'=1$ e $a*a'=0$.

As leis de De Morgan são especialmente importantes:

$$ (a+b)'=a'*b',\qquad (a*b)'=a'+b' $$

Elas permitem transformar expressões trocando soma por produto e vice-versa sob complemento, e aparecem com frequência em simplificação de circuitos.

Uma expressão booleana em variáveis $x,y,z,\ldots$ é construída combinando essas variáveis com operações booleanas. Por exemplo:

$$ E=(x+y'z)'+(xyz'+x'y)' $$

Chamamos de literal uma variável ou seu complemento, como $x$ ou $x'$. Uma forma soma-de-produtos representa a expressão como soma de termos, cada um deles sendo produto de literais. Por exemplo:

$$ E=xy+ x'z + yz' $$

Minimizar uma função booleana significa encontrar uma expressão equivalente mais simples, geralmente com menos literais ou menos termos. Isso é importante porque circuitos menores costumam ser mais baratos, mais rápidos e consumir menos energia.

Exemplo: considere

$$ xy + xy' = x(y+y') = x\cdot 1 = x $$

Portanto, uma expressão com dois termos foi reduzida a um único literal.

Em engenharia digital, essa simplificação pode ser feita por manipulação algébrica, mapas de Karnaugh ou algoritmos como Quine-McCluskey. Em um circuito lógico, uma função booleana é também uma função

$$ f:B^n\rightarrow B $$

que recebe $n$ bits e devolve um único bit de saída. A tabela verdade descreve completamente esse comportamento.

Na prática, álgebra booleana conecta lógica formal, circuitos digitais e programação. Condições em if, portas AND/OR/NOT, máscaras de bits, filtros de banco de dados e circuitos combinacionais são manifestações concretas do mesmo formalismo.

Algumas relações possuem propriedades estruturais especiais. Entre as mais importantes estão as relações de equivalência e as relações de ordem.

Uma relação $R\subseteq A\times A$ é de equivalência quando é:

• reflexiva: $aRa$ para todo $a\in A$;
• simétrica: se $aRb$, então $bRa$;
• transitiva: se $aRb$ e $bRc$, então $aRc$.

Essas relações particionam o conjunto em classes de equivalência. Cada classe reúne os elementos que são equivalentes entre si segundo o critério adotado.

Exemplo: em $\mathbb{N}$, a relação “ter o mesmo resto na divisão por 2” é dada por

$$ aR b \Leftrightarrow a \bmod 2 = b \bmod 2 $$

Ela divide os naturais em duas classes: pares e ímpares.

O conjunto quociente é formado pelas classes de equivalência:

$$ A/R=\{[a]_R\mid a\in A\} $$

onde

$$ [a]_R=\{b\in A\mid aRb\} $$

Já uma relação de ordem parcial é uma relação $R\subseteq A\times A$ que é:

• reflexiva;
• antissimétrica: se $aRb$ e $bRa$, então $a=b$;
• transitiva.

Exemplos clássicos são $\leq$ nos números e $\subseteq$ no conjunto das partes. Em uma ordem parcial, nem todos os elementos precisam ser comparáveis. Por isso, ordens parciais modelam bem dependências, precedência entre tarefas e inclusão entre estruturas.

Diagramas de Hasse são representações visuais muito úteis dessas ordens. Eles omitem arestas reflexivas e transitivas implícitas, deixando o desenho mais limpo e facilitando a percepção de cobertura entre elementos.

Em computação, uma ordem parcial pode descrever dependências entre instruções, requisitos entre módulos, versões compatíveis, privilégios de acesso ou etapas de uma compilação. Quando uma tarefa precisa ser executada antes de outra, mas não necessariamente antes de todas as demais, a relação de precedência costuma ser parcial e não total.

Estruturas algébricas surgem quando combinamos conjuntos com operações e exigimos certas propriedades. Elas permitem estudar padrões muito gerais, presentes tanto em matemática pura quanto em computação.

Um reticulado é um conjunto parcialmente ordenado em que todo par de elementos possui:

• um maior limitante inferior, chamado ínfimo ou meet;
• um menor limitante superior, chamado supremo ou join.

No conjunto das partes $\mathcal{P}(A)$ com a ordem $\subseteq$, o ínfimo de dois conjuntos é sua intersecção e o supremo é sua união. Por isso, álgebra de conjuntos é um exemplo natural de reticulado.

Um semigrupo é um conjunto com uma operação associativa. Um monóide é um semigrupo com elemento neutro. Por exemplo, $(\mathbb{N},+)$ é um monóide, pois a adição é associativa e o zero é neutro:

$$ a+0=0+a=a $$

Um grupo adiciona a existência de inversos. Assim, $(\mathbb{Z},+)$ é grupo, porque todo inteiro $a$ possui inverso aditivo $-a$:

$$ a+(-a)=0 $$

Já $(\mathbb{N},+)$ não é grupo, porque os naturais não contêm inversos para todos os seus elementos.

Um anel é uma estrutura com duas operações, normalmente soma e produto, em que a soma forma um grupo abeliano e o produto é associativo, além de distribuir sobre a soma. O conjunto dos inteiros com $+$ e $\cdot$ é o exemplo clássico de anel.

Essas estruturas não são apenas objetos abstratos. Monóides aparecem em concatenação de strings e composição de transformações. Grupos aparecem em criptografia, simetria e teoria dos códigos. Anéis aparecem em aritmética modular, álgebra computacional e teoria dos números aplicada.

A teoria dos códigos estuda como representar informação de modo a detectar ou corrigir erros introduzidos durante transmissão ou armazenamento. Esse tema é central em telecomunicações, redes, memória de computadores, armazenamento em disco, comunicação espacial e transmissão sem fio.

Um modelo simples e muito usado é o canal binário simétrico, ou binary symmetric channel (BSC). Nele, cada bit transmitido pode ser invertido com probabilidade $p$, independentemente dos demais. Assim, 0 pode virar 1 e 1 pode virar 0 com a mesma taxa de erro.

A estratégia básica para tornar a comunicação mais robusta é introduzir redundância. Em vez de enviar apenas a informação bruta, enviamos informação adicional que permita verificar consistência e, em certos casos, reconstruir a mensagem correta.

Um código repetido simples envia a mensagem mais de uma vez. Se a palavra original for 1011, uma repetição dupla pode produzir 10111011. Isso aumenta a chance de detectar falhas, mas reduz a taxa de informação útil.

Outra técnica muito comum é o bit de paridade. Se desejamos paridade par, acrescentamos um bit que torna par o número total de 1s. Para a palavra 1011, que já tem três bits 1, adicionamos mais um 1 e transmitimos 10111. Se o receptor contar quantidade ímpar quando esperava quantidade par, conclui que houve erro.

Na teoria formal, um código de comprimento $n$ sobre um alfabeto $F$ é um subconjunto de $F^n$. No caso binário, usamos $F=\{0,1\}$. As palavras válidas do código são chamadas codewords.

Para medir proximidade entre palavras, usamos a distância de Hamming, que conta em quantas posições duas palavras diferem. Se

$$ u=0100,\qquad c_2=0101 $$

então

$$ d(u,c_2)=1 $$

pois apenas um bit mudou. Em decodificação por vizinho mais próximo, escolhemos a palavra válida mais próxima da recebida.

Se um código linear binário é visto como subespaço de $B^n$, podemos descrevê-lo com uma matriz geradora $G$. Dado um vetor de mensagem $u\in B^k$, a palavra codificada é:

$$ c=uG $$

Uma matriz de verificação de paridade $H$ satisfaz a condição

$$ Hc^T=0 $$

para toda palavra válida $c$. Assim, ao receber uma palavra $r$, calculamos $Hr^T$ para obter a síndrome do erro.

Os códigos de Hamming são exemplos clássicos de códigos lineares capazes de corrigir erros simples. No código $(7,4)$, quatro bits de informação são expandidos para sete bits totais por meio de três bits de verificação. A taxa é $4/7$, e o código permite identificar e corrigir a posição de um único erro.

Em termos computacionais, a teoria dos códigos combina álgebra linear, combinatória e probabilidade. Ela é fundamental para garantir confiabilidade em sistemas que trocam grandes volumes de dados, como redes, discos, SSDs, memória ECC, satélites e protocolos de comunicação digital.

A teoria dos domínios fornece estruturas matemáticas para descrever significado de programas, especialmente quando há computações parciais, recursão e aproximações sucessivas. Ela é muito importante em semântica denotacional de linguagens de programação.

A ideia central é que valores computacionais podem ser vistos como aproximações umas das outras. Um resultado parcial, como “ainda não terminou” ou “sabemos apenas parte da informação”, pode ser comparado com um resultado mais completo. Essa comparação é modelada por uma ordem parcial, frequentemente escrita como $\sqsubseteq$.

Uma ordem parcial $\langle D,\sqsubseteq\rangle$ deve ser reflexiva, antissimétrica e transitiva. Em teoria dos domínios, lemos $x\sqsubseteq y$ como “$x$ é menos informativo que $y$” ou “$x$ aproxima $y$”.

Uma estrutura importante é a complete partial order (cpo), em que certas cadeias crescentes possuem supremo. Isso permite modelar processos de refinamento: começamos com pouca informação e vamos obtendo aproximações cada vez melhores até atingir um limite.

Essa ideia é especialmente útil para definir funções recursivas por ponto fixo. Se $F$ é um operador sobre um domínio apropriado, buscamos um valor $x$ tal que

$$ F(x)=x $$

Esse ponto fixo pode representar o significado de uma definição recursiva. Em muitos casos, ele é construído como limite de uma sequência de aproximações iniciada em um elemento mínimo.

Continuidade, nesse contexto, não é a mesma continuidade do cálculo diferencial. Aqui ela expressa preservação de limites de cadeias dirigidas, o que garante que a informação computacional se propaga de maneira compatível com o processo de aproximação.

Na prática, a teoria dos domínios ajuda a formalizar programas que podem não terminar, funções definidas recursivamente, avaliação preguiçosa e semântica de linguagens funcionais. Embora o tema seja mais abstrato do que os anteriores, ele mostra como estruturas discretas e ordens parciais sustentam noções profundas de computação.

Referências:

1. Schaum Outline of Discrete Mathematics - Seymour Lipschutz, Marc Lipson.
2. Discrete Mathematics and Its Applications - Kenneth H. Rosen - McGraw-Hill.
3. An Introduction to Coding Theory via Hamming Codes - Nuh Aydin.
4. Domain Theory: An Introduction - Robert Cartwright, Rebecca Parsons.

< 5 - Lógica Matemática > 7 - Probabilidade e Estatística