Binômio e Soluções Inteiras
Binômio e Soluções Inteiras
Textos de apoio
Jorge Picado
Departamento de Matemática
Universidade de Coimbra
Segunda Edição
Agosto de 2014
Índice
Prefácio i
1. Fundamentos 1
1.1. Como raciocinamos? Lógica proposicional . . . . . . . . . . . . . 1
1.2. Linguagens de primeira ordem: Lógica dos predicados . . . . 15
1.3. Raciocı́nio matemático, indução e recursão . . . . . . . . . . . . . 24
2. Algoritmos 37
2.1. Algoritmos e sua complexidade . . . . . . . . . . . . . . . . . . . . . 37
2.2. Somatórios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4. Números inteiros 89
4.1. Aritmética modular . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
4.2. Criptografia: o sistema RSA de chave pública . . . . . . . . . . 98
5. Contagem 109
5.1. Técnicas básicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
5.2. Técnicas avançadas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
Bibliografia 151
Apêndices
A.1. Usando Boole
usando
Boole Linguagens
de primeira
ordem
Raciocı́nio
Lógica pro- matemático
posicional
Relações de
recorrência
Técnicas de Indução e
contagem Funda- recursão
avançadas mentos
Combi-
Contagem
e proba- natória
bilidade
discreta
Comple-
xidade
Matemática Algo-
Discreta ritmos
Somatórios
Criptografia
Números
inteiros Grafos:
noções
básicas
Teoria dos
Aplicações
Grafos
Árvores
Aritmética Grafos
modular eulerianos
Problemas
Grafos ha-
famosos
miltonianos
Prefácio
Estes apontamentos incluem com algum pormenor os principais conceitos e resultados apresen-
tados nas aulas, completados com exemplos, observações e exercı́cios. Neles vamos introduzir os
conceitos básicos de matemática discreta, necessários para uma compreensão rigorosa da disci-
plina de informática e vamos motivar para o raciocı́nio matemático. Serão abordados temas que
vão da lógica à álgebra, passando pela teoria das probabilidades e pela teoria dos grafos, através
de uma articulação entre a teoria e a prática. Serão utilizados programas especı́ficos para a
parte da lógica: (Tarski World e Boole). Dada a extensão do programa será dada preferência
a uma abordagem de ensino teórico “em largura”, deixando para as aulas práticas, e trabalho
em casa, o aprofundamento das diversas matérias.
Espera-se que estes apontamentos sejam um auxiliar valioso para o curso, que permita uma
maior liberdade nas aulas, na explicação teórica dos assuntos, substituindo uma exposição com
grande pormenor formal por uma que realce a motivação e os aspectos intuitivos desses mesmos
conceitos e respectivas inter-relações, e que por outro lado sejam um estı́mulo à atenção e
participação activa dos estudantes. Devem ser encarados como um mero guião das aulas, não
sendo portanto um seu substituto. Na sua elaboração baseámo-nos fundamentalmente nos livros
• James Hein, Discrete Structures, Logic and Computability, Portland State University, 2002.
(03D/HEI)
• Jon Barwise e John Etchemendy, Language, Proof and Logic, CSLI Publications, 1999.
(03B/[Link])
Como material de estudo, além destes apontamentos recomendamos nalguns pontos do pro-
grama o livro
Podem ser encontradas mais informações sobre o curso (incluindo os apontamentos, restante
material de apoio, sumários das aulas, etc.) em
[Link]
i
Estruturas Discretas
A matemática discreta (ou, como por vezes também é apelidada, matemática finita ou ma-
temática combinatória) é a parte da Matemática devotada ao estudo de objectos e estruturas
discretas ou finitas (discreta significa que é formada por elementos distintos desconexos entre si).
O tipo de problemas que se resolvem usando matemática discreta incluem: De quantas maneira
podemos escolher uma password válida para um computador? Qual é a probablidade de ga-
nharmos o euromilhões? Qual é o caminho mais curto entre duas cidades para um determinado
sistema de transporte? Como é que podemos ordenar uma lista de inteiros de modo a que os
inteiros fiquem por ordem crescente? Em quantos passos podemos fazer essa ordenação? Como
podemos desenhar um circuito para adicionar dois inteiros?
Genericamente, a matemática discreta é usada quando contamos objectos, quando estuda-
mos relações entre conjuntos finitos e quando processos (algoritmos) envolvendo um número
finito de passos são analisados. Nos últimos anos tornou-se uma disciplina importantı́ssima da
Matemática porque nos computadores a informação é armazenada e manipulada numa forma
discreta.
A matemática discreta aborda fundamentalmente três tipos de problemas que surgem no
estudo de conjuntos e estruturas discretas:
I - Problemas de existência:
Existe algum arranjo de objectos de um dado conjunto satisfazendo determinada propriedade?
Exemplos:
(A1) Se num dado exame as notas foram dadas com aproximação até às décimas e a ele com-
pareceram 202 alunos, existirão dois alunos com a mesma nota?
(A2) Escolham-se 101 inteiros entre os inteiros 1, 2, 3, . . . , 200. Entre os inteiros escolhidos, exis-
tirão dois tais que um é divisor do outro?
(A3) Se 101 (resp. n2 + 1) pessoas se encontrarem alinhadas lado a lado numa linha recta, será
possı́vel mandar dar um passo em frente a 11 (resp. n + 1) delas de tal modo que, olhando
para este grupo da esquerda para a direita, as pessoas se encontrem por ordem crescente
ou decrescente das suas alturas?
Ou seja, de uma sequência
a1 , a2 , . . . , an2 +1
de números reais, será possı́vel extrair uma subsequência crescente ou decrescente com
n + 1 elementos?
Por exemplo, a sequência 3, 2, 12, 8, 10, 1, 4, 11, 9, 7 contém 10 termos. Note-se que 10 =
32 + 1. Existem 2 subsequências crescentes de comprimento 4, nomeadamente 3, 8, 10, 11
e 2, 8, 10, 11. Existe também uma subsequência decrescente de comprimento 4 que é
12, 10, 9, 7. Por outro lado, a sequência 3, 2, 12, 8, 10, 1, 4, 11, 7, 9 já não contém nenhuma
subsequência decrescente de comprimento 4. Em contrapartida, tem 5 subsequências cres-
centes de comprimento 4: 3, 8, 10, 11; 3, 4, 7, 9; 2, 8, 10, 11; 2, 4, 7, 9 e 1, 4, 7, 9.
iii
Estruturas Discretas Que é a Matemática Discreta?
(A4) O Rio Pregel atravessa a cidade de Königsberg, na Prússia Oriental (actualmente Kalini-
negrado, na Rússia), dividindo-a em quatro regiões, como se pode ver na seguinte gravura2
da cidade:
“1. Além do ramo da geometria que se preocupa com grandezas, e que sempre
recebeu a maior atenção, existe outro ramo, quase desconhecido anteriormente,
que Leibniz pela primeira vez mencionou, chamando-lhe ‘geometria da posição’.
Este ramo preocupa-se com a determinação de posições e suas propriedades;
não envolve medidas, nem cálculos feitos com elas. Ainda não se determinou
de modo satisfatório que tipo de problemas são relevantes para esta geometria
2 [M. Zeiller, Topographia Prussiae et Pomerelliae, Frankfurt, c. 1650], cópia em [1].
3 No artigo [Solutio Problematis ad Geometriam Situs Pertinentis, Commentarii Academiae Scientiarum Im-
perialis Petropolitanae 8 (1736) 128-140], baseado numa comunicação apresentada à Academia em 26 de Agosto
de 1735, e considerado por muitos o nascimento da Teoria dos Grafos. Euler foi um dos maiores génios da
matemática; este ano comemoram-se os 300 anos do seu nascimento.
iv
Estruturas Discretas Que é a Matemática Discreta?
ao caso particular do problema de Königsberg mas olhar para o problema geral, é tı́pico de um matemático.
Contudo Euler continuou com o caso particular em mente, voltando a ele mais do que uma vez, para interpretar e
verificar as suas novas descobertas. Isto é muito interessante, ilustrando como a generalização e a especialização
se complementam na investigação matemática. Outro aspecto muito interessante ocorre na Secção 4, quando
v
Estruturas Discretas Que é a Matemática Discreta?
(A5) Imagine uma prisão com 64 celas, dispostas como os quadrados de um tabuleiro de xadrez
(com 8 linhas e 8 colunas). Imagine ainda que entre cada duas celas vizinhas existe uma
porta. É proposta, ao prisioneiro colocado na cela de um dos cantos, a sua liberdade caso
consiga chegar à cela do canto diagonalmente oposto, depois de passar por todas as outras
celas uma única vez. Conseguirá o prisioneiro obter a sua liberdade?
(A6) Consideremos um tabuleiro de xadrez e algumas peças (idênticas) de dominó tais que cada
uma cobre precisamente 2 quadrados adjacentes do tabuleiro. Será possı́vel dispor 32
dessas peças no tabuleiro de modo a cobri-lo, sem sobreposição de peças?5
E se o tabuleiro tiver mn quadrados em m linhas e n colunas?
Exemplos:
Para outros valores de m e n já poderá não existir nenhuma cobertura perfeita. Por
exemplo, não existe nenhuma no caso m = n = 3. Para que valores de m e n existem?
Não é difı́cil concluir que um tabuleiro m × n possui uma cobertura perfeita se e só se
pelo menos um dos números m ou n é par, ou equivalentemente, se e só se o número mn
de quadrados do tabuleiro é par. Fischer determinou fórmulas gerais (envolvendo funções
trigonométricas) para o cálculo do número exacto de coberturas perfeitas de um tabuleiro
m × n.
Este problema é equivalente a um problema famoso em Fı́sica Molecular, conhecido como
o Problema das moléculas diatómicas7 .
vi
Estruturas Discretas Que é a Matemática Discreta?
(B4) O seguinte problema foi originalmente proposto por Leonardo de Pisa8 , mais conhecido
por Fibonacci, no séc. XIII:
Suponhamos que, para estudar a reprodução profı́cua dos coelhos, colocámos um par de
coelhos (sendo um de cada sexo) numa ilha. Passados dois meses, a fêmea deu à luz todos
os meses um novo par de coelhos, de sexos opostos. Por sua vez, a partir dos dois meses
de idade, cada novo par deu à luz um outro par, todos os meses. Quantos pares de coelhos
existiam na ilha ao cabo de n meses, supondo que nenhum coelho morreu entretanto?
A população de coelhos pode ser descrita por uma relação de recorrência. No final do
primeiro mês o número de pares de coelhos era 1. Como este par não reproduziu durante
o segundo mês, no final deste o número de pares de coelhos continuou a ser 1. Durante o
terceiro mês nasceu um novo par pelo que no final deste mês existiam 2 pares de coelhos.
Durante o quarto mês só o par inicial deu origem a um novo par, logo no final do quarto
mês existiam 3 pares de coelhos.
Denotemos por fn o número de pares de coelhos existentes no final do mês n. Este número é
claramente igual à soma do número de pares de coelhos existentes no final do mês anterior,
ou seja fn−1 , com o número de pares de coelhos entretanto nascidos durante o mês n, que
é igual a fn−2 . Portanto a sequência (fn )n∈N satisfaz a relação
fn = fn−1 + fn−2
para n ≥ 3, sendo f1 = f2 = 1.
8 No seu livro Liber Abacci (literalmente, um livro sobre o ábaco), publicado em 1202.
vii
Estruturas Discretas Que é a Matemática Discreta?
Esta sucessão é a famosa sucessão de Fibonacci, e os seus termos são chamados números
de Fibonacci9 .
Claro que para responder totalmente ao problema de Fibonacci teremos de encontrar um
método para determinar uma fórmula explı́cita para o número fn a partir daquela relação
de recorrência.
Exemplos:
(C1) A velocidade com que um gás flui através de uma tubagem depende do diâmetro do
tubo, do seu comprimento, das pressões nos pontos terminais, da temperatura e de várias
propriedades do gás. O desenho de uma rede de distribuição de gás envolve, entre outras
decisões, a escolha dos diâmetros dos tubos, de modo a minimizar o custo total da cons-
trução e operação do sistema. A abordagem standard consiste em recorrer ao “bom senso”
(método habitual da engenharia!) para a escolha de tamanhos razoáveis de tubagem e
esperar que tudo corra pelo melhor. Qualquer esperança de fazer melhor parece, à primeira
vista, não existir. Por exemplo, uma pequena rede com 40 ligações e 7 diâmetros possı́veis
de tubo, daria origem a 740 redes diferentes. O nosso problema é o de escolher a rede
mais barata de entre essas 740 possibilidades (que é um número astronómico!). Trata-se
assim de um problema de optimização, no qual procuramos o desenho (padrão ou arranjo)
óptimo para um determinado desempenho.
Este problema, mesmo com o uso dos actuais computadores de grande velocidade, não
parece tratável por exaustiva análise de todos os casos. Mesmo qualquer desenvolvimento
esperado na velocidade daqueles não parece ter influência significativa nesta questão. Con-
tudo, um procedimento simples implementado no Golfo do México10 , deu origem a um
método que permite encontrar a rede óptima em 7 × 40 = 280 passos em vez dos tais 740 ,
permitindo poupar alguns milhões de dólares. É um exemplo paradigmático das virtuali-
dades da chamada Optimização Combinatória.
(C2) Suponha que se fazem n cortes numa pizza. Qual o número máximo de partes em que a
pizza poderá ficar dividida?
on the First Two Days’ Sessions and a Brief Description of a Gas Pipeline Network Construction Problem,
em F. S. Roberts (ed.), Energy: Mathematics and Models, SIAM, Filadélfia, 1976, p. 239-252], [Rothfarb et
al., Optimal Design of Offshore Natural-Gas Pipeline Systems, Oper. Res. 18 (1970) 992-1020] e [N. Zadeh,
Construction of Efficient Tree Networks: The Pipeline Problem, Networks 3 (1973) 1-32].
viii
Estruturas Discretas Que é a Matemática Discreta?
6
4
6
3
6 6
1 2
Mas será possı́vel realizar tal operação com menos cortes, se as peças puderem ser deslo-
cadas entre cortes? Por exemplo, em
6
2
ix
Estruturas Discretas Que é a Matemática Discreta?
o segundo corte corta agora mais madeira do que cortaria se não tivéssemos rearranjado
as peças depois do primeiro corte. Parece, pois, um problema difı́cil de analisar. Olhemos
no entanto para ele de outro modo. As 6 faces do cubo do meio só se conseguem obter
com cortes (independentes). Portanto, são sempre necessários 6 cortes e fazer rearranjos
das peças entre os cortes não ajuda nada.
Agora outro problema (este de contagem) surge naturalmente: de quantas maneiras dife-
rentes pode o cubo ser cortado, realizando somente 6 cortes?
(C4) Em 1852, Francis Guthrie reparou que no mapa de Inglaterra os condados poderiam ser
coloridos, usando somente quatro cores, de modo a que condados vizinhos tivessem co-
res diferentes. Através do seu irmão perguntou a De Morgan se quatro cores chegariam
para colorir, naquelas condições, qualquer mapa. Em 1878, num encontro da Sociedade
Matemática de Londres, A. Cayley perguntou se alguém conseguia resolver o problema.
Assim teve origem o famoso Problema das 4 cores. Somente em 1976, K. Appel e W. Ha-
gen da Universidade do Illinois (E.U.A.), o conseguiriam resolver, com uma demonstração
polémica11 , com a ajuda imprescindı́vel do computador, que executou rotinas durante mais
de 1000 horas consecutivas!
A demonstração deste resultado está muito longe de ser apresentável, pelo que nos limita-
mos a enunciar a solução12 :
Em qualquer mapa sobre um plano ou uma esfera (representando um qualquer conjunto
de regiões tais que, para quaisquer dois pontos numa mesma região, existe sempre um
caminho, totalmente contido nessa região, ligando esses dois pontos), o menor número de
cores necessárias para o colorir, de tal modo que duas regiões adjacentes (ou seja, com um
número infinito de pontos fronteiros comuns) não tenham a mesma cor, é 4.
Por exemplo:
C1 C2
C1 C2
C1
C2
C3 C3 C4
C2 C1
As origens da Matemática Combinatória datam do séc. XVII em estreita ligação com os jogos
de azar e o cálculo das probabilidades; Pascal, Fermat, Jacob Bernoulli e Leibniz realizaram
investigações de problemas combinatoriais relacionados com jogos de azar, constituindo estas as
bases sobre as quais se desenvolveu o cálculo das probabilidades.
11 Parauma história mais completa das origens e resolução deste problema consulte [R. Fritsch e G. Fritsch,
The Four-Color Theorem, Springer, 1998].
12 K. Appel e W. Hagen, Every planar map is four coulorable, Bull. Amer. Math. Soc. 82 (1976) 711-712.
x
Estruturas Discretas Que é a Matemática Discreta?
No séc. XVIII Euler fundou a Teoria dos Grafos com a resolução do famoso problema das
pontes de Königsberg, como já referimos, e James Bernoulli publicou o primeiro livro13 contendo
métodos combinatoriais.
Com o desenvolvimento dos computadores, a Matemática Combinatória tornou-se uma dis-
ciplina autónoma dentro da matemática moderna, das que mais se tem desenvolvido, tendo
inúmeras aplicações a diversas áreas da matemática, engenharias e outras ciências.
Exercı́cios
1. Mostre que um tabuleiro com m × n quadrados possui uma cobertura perfeita se e só se pelo
menos um dos valores m ou n é par.
2. Para cada n ∈ N, seja f (n) o número de coberturas perfeitas de um tabuleiro 2 × n. Calcule
f (1), f (2), f (3), f (4) e f (5). Tente encontrar uma relação que seja satisfeita pela função f e que
lhe permita calcular f (12).
3. Determine o número de coberturas perfeitas distintas de um tabuleiro 3 × 4.
4. Seja n um inteiro positivo. Dizemos que uma n-coloração de um mapa é uma coloração de todas
as regiões do mapa, usando n cores, de tal modo que regiões adjacentes (isto é, regiões com um
número infinito de pontos fronteiros comuns) têm cores diferentes. Prove que:
(a) Um mapa formado no plano por um número finito de cı́rculos possui uma 2-coloração.
(b) Um mapa formado no plano por um número finito de linhas rectas também possui uma
2-coloração.
5. Mostre que o seguinte mapa de 10 paı́ses admite uma 3-coloração. Fixadas essas 3 cores, determine
o número de colorações distintas possı́veis.
' $
1 2 3
10 4 5 6
7 8 9
& %
b 5 d
u u
4 @ 6
@
a u 2 @uf
7
1
@
2@ 3
@u u
c 8 e
(Os valores junto de cada estrada representam os comprimentos destas, medidos numa determi-
nada unidade.)
13 Ars Conjectandi.
xi
Estruturas Discretas Que é a Matemática Discreta?
Referências
[1] N. L. Biggs, E. K. Lloyd e R. J. Wilson, Graph Theory 1736-1936, Clarendon Press, 1986.
(05-01/BIG)
xii
Estruturas Discretas 1.1. Lógica proposicional
1. Fundamentos
“(...) all rational inquiry depends on logic, on the ability of people to reason
correctly most of the time.”
“(...) there is an overwhelming intuition that the laws of logic are somehow more
irrefutable than the laws of the land, or even the laws of physics.”
Porque deve um estudante de Informática estudar lógica? Porque precisa de dominar ferra-
mentas lógicas que lhe permitam argumentar se um problema pode ou não ser resolvido num
computador, traduzir proposições lógicas da linguagem comum em diversas linguagens computa-
cionais, argumentar se um programa está correcto e se é eficiente. Os computadores baseiam-se
em mecanismos lógicos e são programados de modo lógico. Os informáticos devem ser capazes
de compreender e aplicar novas ideias e técnicas de programação, muitas das quais requerem
conhecimento dos aspectos formais da lógica.
Todos nós raciocinamos enunciando factos e tirando conclusões baseadas nesses factos. O
inı́cio de uma conclusão é habitualmente indicada por uma palavra como
Para chegarmos a uma conclusão aplicamos uma regra de inferência (ou regra de dedução).
A mais comum é a chamada regra modus ponens (modo que afirma): sendo A e B afirmações,
se A e “se A então B” são ambas verdadeiras, então podemos concluir que B é verdadeira.
Outra regra muito comum é a modus tollens (modo que nega): sendo A e B afirmações, se
“se A então B” é verdadeira e B é falsa, então podemos concluir que A é falsa.
Por exemplo:
Quando tiramos uma conclusão que não decorre dos factos estabelecidos previamente, o
raciocı́nio diz-se non sequitur (que não segue). Por exemplo:
1
Estruturas Discretas 1.1. Lógica proposicional
Neste primeiro capı́tulo começaremos por estudar um pouco de lógica. Algumas definições
de lógica que podemos encontrar nos dicionários:
• Sistema de raciocı́nio.
• Raciocı́nio válido.
Um cálculo é uma linguagem de expressões, onde cada expressão tem um valor lógico e há
regras para transformar uma expressão noutra com o mesmo valor. Aqui estudaremos um pouco
do cálculo proposicional. O cálculo proposicional é a linguagem das proposições. Uma proposição
é uma expressão da qual faz sentido dizer que é verdadeira ou que é falsa. Cada proposição tem
um e um só valor lógico, entre dois possı́veis: V (verdadeiro) ou F (falso).
Exemplo. “Coimbra é uma cidade portuguesa” é uma proposição com valor lógico verdadeiro.
Mas atribuir um valor lógico à afirmação “Hoje está um belo dia!” já não faz sentido, pois trata-
-se duma expressão subjectiva que exprime um sentimento de alguém, não de uma afirmação
objectiva.
O cálculo proposicional (tal como outros tipos de lógica) que vamos estudar pressupõe os
seguintes princı́pios:
Princı́pio da não contradição: Uma proposição não pode ser verdadeira e falsa ao mesmo tempo.
2
Estruturas Discretas 1.1. Lógica proposicional
negação ¬p (não p)
conjunção p ∧ q (p e q)
disjunção p ∨ q (p ou q)
implicação p→q (se p então q; p só se q; p é condição suficiente para
que q; q é condição necessária para que p)
equivalência (formal) p ↔ q (p é equivalente a q)
·
disjunção exclusiva p ∨ q (ou p ou q)
As proposições são representadas por fórmulas chamadas fórmulas bem formadas que são
construı́das a partir de um alfabeto constituı́do por:
• Sı́mbolos de verdade: V e F.
• Conectivos (operadores):
¬ (“não”, negação)
∧ (“e”, conjunção)
∨ (“ou”, disjunção)
→ (“implica”, implicação).
• Sı́mbolos de parênteses: (, ).
3
Estruturas Discretas 1.1. Lógica proposicional
Exemplo. A expressão p¬q não é uma fbf. Mas cada uma das seguintes expressões é uma fbf:
p ∧ q→r, (p ∧ q)→r, p ∧ (q→r).
Os parênteses funcionam como sı́mbolos auxiliares que indicam como é formada a fbf. Para
evitar um uso excessivo de parênteses e simplificar a escrita das expressões lógicas convenciona-
-se que as operações lógicas são consideradas pela seguinte ordem de prioridade: ¬, ∧, ∨, →.
Convenciona-se ainda que na presença de uma só das três últimas operações, na ausência de
parênteses as operações são realizadas da esquerda para a direita.
Exemplos.
¬p ∧ q significa (¬p) ∧ q
p∨q∧r significa p ∨ (q ∧ r)
p ∧ q→r significa (p ∧ q)→r
p→q→r significa (p→q)→r.
Relativamente a uma dada linguagem lógica podemos sempre estudar dois aspectos: a sintaxe
e a semântica. A sintaxe diz respeito às regras de formação das expressões lógicas a utilizar,
ou seja, as fórmulas bem formadas. Em cima, acabámos de descrever a sintaxe do cálculo
proposicional.
A semântica estuda o significado das expressões.
sintaxe (fórmulas bem formadas)
Linguagem (conjunto de sı́mbolos)
semântica (significado).
Quanto à semântica, dada uma fbf, interpretando cada uma das suas variáveis proposicionais
com os valores lógicos V ou F, é possı́vel dar um significado à fórmula através da interpretação dos
conectivos lógicos dada pelas respectivas tabelas de verdade. Cada conectivo tem uma tabela
de verdade (que vai ao encontro da forma corrente do significado das operações “não”, “e”,
“ou”, etc.). A tabela de verdade faz corresponder aos possı́veis valores lógicos das variáveis o
correspondente valor lógico da operação2 :
Em conclusão:
2 Nas aulas teórico-práticas usaremos o software Boole para nos ajudar a escrever tabelas de verdade. Consulte
o apêndice Usando Boole.
4
Estruturas Discretas 1.1. Lógica proposicional
p q ¬p (¬p) ∧ q
V V F F
V F F F
F V V V
F F V F
É claro que a cada fbf corresponde uma e uma só tabela de verdade.
Uma fbf diz-se uma tautologia se for verdadeira para todos os possı́veis valores lógicos das
suas variáveis proposicionais. Uma fbf diz-se uma contradição se for falsa para todos os possı́veis
valores lógicos das suas variáveis proposicionais. Uma fbf diz-se uma contingência se não for
uma tautologia nem uma contradição.
Exemplos. Suponhamos que queremos averiguar se p→p ∨ q é ou não uma tautologia. Para
isso basta construir a respectiva tabela de verdade:
p q p∨q p→p ∨ q
V V V V
V F V V
F V V V
F F F V
Como para quaisquer valores de p e q toma sempre o valor de verdade, concluı́mos que é uma
tautologia.
Mais exemplos: p∨¬p é uma tautologia, p∧¬p é uma contradição e p→q é uma contingência.
Duas fbf’s dizem-se (logicamente) equivalentes se tiverem o mesmo significado, isto é, a mesma
tabela de verdade. Para indicar que duas fbf’s A e B são equivalentes, escrevemos
A ≡ B.
Em vez do sı́mbolo ≡ também se costuma usar ⇔. Note que dizer que A e B são logicamente
equivalentes é o mesmo que dizer que as fórmulas (A→B) e (B→A) são tautologias (Prova:
A ≡ B sse A e B têm os mesmos valores de verdade sse (A→B) e (B→A) são tautologias).
5
Estruturas Discretas 1.1. Lógica proposicional
p ∨ (p ∧ q) ≡ p Leis da absorção
p ∧ (p ∨ q) ≡ p
(p ∨ q) ∨ r ≡ p ∨ (q ∨ r) Leis da associatividade
(p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) Leis da distributividade
p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
¬(p ∧ q) ≡ ¬p ∨ ¬q Leis de De Morgan
¬(p ∨ q) ≡ ¬p ∧ ¬q
p→q ≡ ¬p ∨ q
p q p∧q ¬(p ∧ q) ¬p ¬q ¬p ∨ ¬q
V V V F F F F
V F F V F V V
F V F V V F V
F F F V V V V
concluı́mos que ambas as fbf’s têm o mesmo valor lógico para os mesmos valores das variáveis
proposicionais, pelo que são logicamente equivalentes.
É possı́vel provar uma equivalência sem construir as tabelas de verdade por causa dos se-
guintes factos:
1. Se A ≡ B e B ≡ C, então A ≡ C.
6
Estruturas Discretas 1.1. Lógica proposicional
Exemplo. Use as equivalências básicas na tabela anterior para provar que p ∨ q→p ≡ q→p.
3. p→q ≡ (p ∧ ¬q)→F.
1. (p ∧ q ∧ r) ∨ (p ∧ r) ∨ r.
2. (s→t) ∧ (u ∨ t ∨ ¬s).
Se p é uma variável proposicional numa fbf A, denotemos por A(p/V) a fbf que se obtém de
A substituindo todas as ocorrências de p por V . De modo análogo podemos também definir a
fórmula A(p/F). As seguintes propriedades verificam-se:
7
Estruturas Discretas 1.1. Lógica proposicional
e
B(q/F) = (F→r) ∧ F→r ≡ F→r ≡ V,
o que mostra que B é uma tautologia. Portanto, A é uma tautologia.
No nosso dia a dia raciocinamos e tiramos conclusões usando determinadas regras. A lógica
ajuda a compreender essas regras permitindo distinguir entre argumentos correctos e argumen-
tos não correctos. Seguem-se alguns argumentos lógicos, cada um deles com um exemplo e a
respectiva formalização.
(1)
1. Se o gato vê o peixe, então o gato apanha o peixe.
2. Se o gato apanha o peixe, então o gato come o peixe.
3. Se o gato vê o peixe, então o gato come o peixe.
1. p→q
2. q→r
3. p→r
(2)
1. Se o João tem mais de 16 anos, então vai ao cinema.
2. O João tem mais de 16 anos.
3. O João vai ao cinema.
1. p→q
2. p
3. q
(3)
1. A Maria vai aos testes ou faz o exame.
2. A Maria não faz o exame.
3. A Maria vai aos testes.
1. p ∨ q
2. ¬q
3. p
8
Estruturas Discretas 1.1. Lógica proposicional
A1
A2
..
.
An
B
diz-se um argumento correcto se A1 ∧ A2 ∧ · · · ∧ An →B for uma tautologia. Neste caso também
se costuma escrever
A1 , A2 , . . . , An |= B
(o sı́mbolo |= lê-se “de ... deduz-se ...”). Habitualmente nas aulas e na prática da matemática
usa-se A ⇒ B para indicar A |= B.
Um literal é uma variável proposicional ou a sua negação; por exemplo, p e ¬p são literais
(ditos literais complementares).
Uma fbf diz-se uma forma normal disjuntiva (FND) se for da forma C1 ∨ C2 ∨ · · · ∨ Cn , onde
cada Ci é uma conjunção de literais (chamada conjunção fundamental).
Analogamente, uma fbf diz-se uma forma normal conjuntiva (FNC) se for da forma D1 ∧
D2 ∧ · · · ∧ Dn , onde cada Di é uma disjunção de literais (chamada disjunção fundamental).
Exemplos de formas normais disjuntivas:
¬p
p ∨ ¬q
p ∧ ¬q
(p ∧ q) ∨ (p ∧ ¬q)
p ∨ (p ∧ r)
¬p
p ∧ ¬q
¬p ∨ q
p ∧ (q ∨ r)
V ≡ p ∨ ¬p e F ≡ p ∧ ¬p.
Ambas as formas são FND e FNC. Qualquer fbf tem uma FND e uma FNC. De facto, em
qualquer fbf podemos usar equivalências básicas para obter uma forma normal conjuntiva:
9
Estruturas Discretas 1.1. Lógica proposicional
1. “Removem-se” todas as →.
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
(p ∧ q) ∨ r ≡ (p ∨ r) ∧ (q ∨ r)
Para obter uma forma normal disjuntiva procede-se de forma análoga, usando agora em 3 as
propriedades
p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
(p ∨ q) ∧ r ≡ (p ∧ r) ∨ (q ∧ r).
Uma função de verdade (ou função lógica) é uma função que só pode tomar os valores lógicos
V ou F e cujos argumentos também só podem tomar esses valores. Por exemplo,
V se p é V
f (p, q) = V se p e q são ambas F
F se p é F e q é V
p q f (p, q)
V V V
V F V
F V F
F F V
10
Estruturas Discretas 1.1. Lógica proposicional
A metodologia a seguir será encontrar uma fbf com a mesma tabela de verdade (podemos
construir quer uma FND quer uma FNC).
Técnica. Para construir uma FND, tendo em conta que a disjunção de um número finito de
fbf’s é V se e só se uma delas o for, basta tomar cada linha da tabela que tenha valor V e construir
uma conjunção fundamental que só seja verdadeira nessa linha. De modo análogo, para construir
uma FNC, basta considerar cada linha que tenha valor F e construir uma disjunção fundamental
que só seja falsa nessa linha.
f (p, q) ≡ p ∨ ¬q (FNC).
Uma FND para uma fbf A é uma FND plena (forma normal disjuntiva plena) se cada
conjunção fundamental contém o mesmo número de literais, um por cada variável proposicional
de A. Uma FNC para uma fbf A é uma FNC plena (forma normal conjuntiva plena) se cada
disjunção fundamental contém o mesmo número de literais, um por cada variável proposicional
de A.
Exemplo. No exemplo anterior obtivemos uma FND plena e uma FNC plena.
Podemos usar a técnica das funções de verdade para determinar uma FND plena ou uma
FNC plena de qualquer fbf com a excepção das tautologias (não têm uma FNC plena) e das
contradições (não têm uma FND). Por exemplo:
V ≡ p ∨ ¬p, que é uma FND plena e uma FNC, mas não é uma FNC plena,
F ≡ p ∧ ¬p, que é uma FNC plena e uma FND, mas não é uma FND plena.
Os conectivos lógicos que usámos para definir as fbf’s do cálculo proposicional são ¬, ∧, ∨
e →. É evidente que o sı́mbolo → não é absolutamente necessário (pela última lei da tabela
das equivalências básicas): qualquer fbf pode ser substituı́da por outra logicamente equivalente
e onde não figura o sı́mbolo →.
11
Estruturas Discretas 1.1. Lógica proposicional
{¬, ∧, ∨, →}
{¬, ∧, ∨}, {¬, ∧}, {¬, ∨}, {¬, →}, {F, →}.
Apêndice: sistemas formais. Como vimos, as tabelas de verdade são suficientes para deter-
minar quando uma fbf é uma tautologia. Contudo, quando uma proposição tem mais do que
duas variáveis e contém vários conectivos, a tabela de verdade pode começar a ficar muito com-
plicada. Nesses casos, o método alternativo que vimos de encontrar uma prova de equivalência
usando as leis de equivalência básicas ou ainda uma combinação dos dois (por exemplo, o método
de Quine) pode ser mais prático.
Quando usamos uma prova de equivalência, em vez de uma tabela de verdade, para verificar
se duas fbf’s são equivalentes, isso parece de certo modo mais parecido com o modo como
comunicamos habitualmente. Embora não seja necessário raciocinar formalmente desse modo
no cálculo proposicional, há outros tipos de sistemas lógicos onde isso já é necessário para
averiguar da validade das fbf’s pois aı́ as tabelas de verdade não funcionam. Para esses casos
existe uma ferramenta: os sistemas de raciocı́nio formal. Quais são as ideais básicas destes
sistemas?
(2) Um conjunto de sequências finitas destes sı́mbolos que constituem as chamadas fórmulas
bem formadas.
(3) Um determinado conjunto de fbf’s, chamadas axiomas, que se assumem ser verdadeiras.
(4) Um conjunto finito de “regras de dedução” chamadas regras de inferência que permitem
deduzir uma fbf como consequência directa de um conjunto finito de fbf’s.
Um sistema formal requere algumas regras que ajudem à obtenção de novas fórmulas, as cha-
madas regras de inferência. Uma regra de inferência (que corresponde sempre a uma tautologia
do cálculo proposicional) aplica uma ou mais fbf’s, chamadas premissas, hipóteses ou antece-
dentes, numa só fórmula, chamada conclusão ou consequente. Algumas regras de inferência
úteis:
12
Estruturas Discretas 1.1. Lógica proposicional
Aqui o conceito crucial é o de dedução. Uma dedução de uma certa conclusão — digamos S
— a partir de premissas P1 , P2 , . . . , Pn é feita passo a passo. Numa dedução, estabelecem-se con-
clusões intermédias, cada uma delas conclusão imediata das premissas e conclusões intermédias
anteriores. Podemos dizer que uma dedução consiste numa sucessão de afirmações, que são pre-
missas ou conclusões intermédias, e que termina, ao fim de um número finito de passos, quando
se obtém a conclusão S.
Cada passo de dedução é correcto, i.e., não oferece dúvidas quanto à validade de cada con-
clusão intermédia, em consequência da validade das premissas e das conclusões intermédias
anteriores.
Uma dedução de uma afirmação S a partir de premissas P1 , P2 , . . . , Pn é uma demonstração
passo a passo que permite verificar que S tem que ser verdadeira em todas as circunstâncias em
que as premissas sejam verdadeiras. Uma dedução formal assenta num conjunto fixo de regras
de dedução e tem uma apresentação rı́gida — um pouco à semelhança dos programas escritos
numa dada linguagem de programação.
Seja C um conjunto de fbf’s e seja P uma fbf em S. Diz-se que P é dedutı́vel a partir de C
em S, e escreve-se
C |=S P
(ou apenas C |= P se não houver dúvidas sobre o sistema S a que nos referimos) se existir uma
sequência finita de fbf’s, P1 , P2 , . . . , Pn tal que:
• Pn = P .
• Para cada i ∈ {1, . . . , n}, Pi é um axioma de S ou uma fbf em C ou uma consequência dos
Pi ’s anteriores através de aplicação das regras de inferência.
13
Estruturas Discretas 1.1. Lógica proposicional
Leituras suplementares:
14
Estruturas Discretas 1.2. Lógica dos predicados
O cálculo proposicional providencia ferramentas adequadas para raciocinarmos sobre fbf’s que
são combinações de proposições atómicas. Mas uma proposição atómica é uma sentença tomada
como um todo o que faz com que o cálculo proposicional não sirva para todo o tipo de raciocı́nio
que precisamos de fazer no dia a dia. Por exemplo, no argumento seguinte é impossı́vel encontrar
no cálculo proposicional um método formal para testar a correcção da dedução sem uma análise
mais profunda de cada sentença:
(1) Todos os alunos de Engenharia Informática têm um computador portátil.
• ∀x P (x).
Por exemplo, a afirmação
Existe um número real x tal que x2 + 2x + 1 = 0
pode ser escrita simbolicamente como
∃x (x2 + 2x + 1 = 0)
(desde que especifiquemos à partida que a variável x se refere a números reais, senão teremos
que escrever (∃x ∈ R) . . .). Para dizermos que
15
Estruturas Discretas 1.2. Lógica dos predicados
podemos escrever
∃S(∀x(S(x)→N(x)) ∧ ¬S(4)).
Note que a ordem dos quantificadores pode ser decisiva. Por exemplo, trocando a ordem em
(a afirmação de que não existe nenhum número natural máximo – uma afirmação verdadeira)
obtemos
(∃n ∈ N)(∀m ∈ N)(n > m),
uma afirmação muito diferente: existe um número natural que é maior que todos os naturais –
uma afirmação claramente falsa!
As seguintes equivalências (óbvias!) são muito úteis quando queremos negar um quantificador
e escrever a afirmação na positiva:
16
Estruturas Discretas 1.2. Lógica dos predicados
Predicados unários
Sentença atómica Interpretação
T et(a) a é um tetraedro
Cube(a) a é um cubo
Dodec(a) a é um dodecaedro
Small(a) a é pequeno
M edium(a) a é médio
Large(a) a é grande
Predicados binários
Sentença atómica Interpretação
SameSize(a, b) a tem o mesmo tamanho que b
SameShape(a, b) a tem a mesma forma que b
Larger(a, b) a é maior que b
Smaller(a, b) a é menor que b
SameCol(a, b) a está na mesma coluna que b
SameRow(a, b) a está na mesma linha que b
Adjoins(a, b) a e b estão localizados em casas adjacentes (mas não na diagonal)
Lef tOf (a, b) a está numa coluna à esquerda de b
RightOf (a, b) a está numa coluna à direita de b
F rontOf (a, b) a está numa linha à frente de b
BackOf (a, b) a está numa linha atrás de b
Predicados ternários
Sentença atómica Interpretação
Between(a, b, c) a, b e c estão na mesma coluna, linha ou diagonal, e a está entre b e c.
ou seja,
∀x (Cube(x) → Large(x)),
17
Estruturas Discretas 1.2. Lógica dos predicados
no seguinte mundo?:
Note que uma afirmação do tipo ∀x ∀y... será verdadeira quando for verdadeira para todos
os pares de objectos x e y no mundo (logo, em particular, quando y = x). Portanto, a primeira
fórmula é falsa porque falha no caso y = x (é impossı́vel um objecto estar à esquerda ou à direita
de si próprio). Quanto à segunda é claramente verdadeira (há diversos pares de objectos (x, y)
no mundo que a satisfazem) mas observe que continua a ser verdadeira mesmo quando o mundo
só contém um cubo (nesse caso, tome para x e y esse cubo).
Porque é que no mundo
as fórmulas
∀x ∀y ((Cube(x) ∧ Cube(y)) → ¬SameRow(x, y))
e
∀x ∀y [(T et(x) ∧ T et(y)) → ¬SameSize(x, y)]
são falsas?
Teste.
18
Estruturas Discretas 1.2. Lógica dos predicados
3. Qual é a diferença entre as fórmulas ∀x ((Cube(x) ∧ M edium(x)) → ¬∃y BackOf (y, x)) e
∀x ((Cube(x) ∧ M edium(x)) → ∃y ¬BackOf (y, x)) ? (Não afirmam a mesma coisa.)
Exemplo. No mundo
a fórmula
∀x ∀y ((T et(x) ∧ Small(x) ∧ T et(y) ∧ Small(y)) → x = y)
também é verdadeira (porquê?). Por outro lado, ∀x (Dodec(x) → x = b) parece afirmar uma
patetice mas é verdadeira, enquanto ∀x (Dodec(x) ↔ x = b) é falsa (sob que condições seria
verdadeira?). Claro que ∀x ((T et(x) ∧ Small(x)) ↔ x = b) já é verdadeira.
Exemplo. As fórmulas
∃x ∃y (T et(x) ∧ Larger(x, y))
e
∃x (T et(x) ∧ ∃y Larger(x, y))
e
∃x (Cube(x) ∧ ∃y (T et(y) ∧ Larger(x, y)))
19
Estruturas Discretas 1.2. Lógica dos predicados
para que a fórmula ∃x ∃y (T et(x) ∧ T et(y) ∧ Larger(x, y) ∧ BackOf (x, y)) seja verdadeira?
• Um objecto pode ter vários nomes, mas também pode não ter nome.
Os sı́mbolos de predicado ou relacionais são sı́mbolos que designam propriedades dos objectos
ou relações entre objectos.
Por exemplo, podemos usar o sı́mbolo EEI, um sı́mbolo de predicado unário (ou seja, de
aridade um), para designar, no universo dos alunos da FCTUC, ser Estudante de Engenharia
Informática. Outro exemplo: o sı́mbolo <, um sı́mbolo de predicado binário (ou seja, de aridade
dois), representa, no universo dos números reais, ser menor do que.
20
Estruturas Discretas 1.2. Lógica dos predicados
Portanto, numa linguagem de primeira ordem, a cada sı́mbolo de predicado está associado
exactamente um número natural — o número de argumentos que ocorre no predicado, que se
designa por aridade. Além disso, cada sı́mbolo de predicado ou relacional é interpretado por
uma propriedade bem determinada ou uma relação com a mesma aridade que o sı́mbolo.
Uma sentença atómica é uma sequência finita de sı́mbolos, escolhidos entre as constantes, os
sı́mbolos de predicados, os parênteses “(” e “)” e a vı́rgula, da forma
Exemplos.
Quando se traduz uma frase escrita em Português para uma sentença numa linguagem de
primeira ordem, tem-se em geral uma linguagem previamente definida, em que se conhecem
à partida as constantes, os sı́mbolos relacionais e (caso existam) os sı́mbolos funcionais. No
entanto, há situações em que há que decidir quais as constantes, os sı́mbolos relacionais e (caso
existam) os sı́mbolos funcionais adequados para expressar o que se pretende.
21
Estruturas Discretas 1.2. Lógica dos predicados
(1) Tomando o sı́mbolo de predicado binário ExplicouT arskiW orld podemos escrever
O poder expressivo da linguagem (2) é maior do que o da linguagem (1). De facto, conside-
rando a frase A Rita explicou o Boole ao Miguel, esta pode ser traduzida usando o sı́mbolo de pre-
dicado ternário Explicou — terı́amos Explicou(Rita, Boole, M iguel) — mas não pode ser tra-
duzida usando o sı́mbolo de predicado ExplicouT arskiW orld. O sı́mbolo de predicado Explicou
é mais versátil do que os sı́mbolos de predicado ExplicouT arskiW orld ou ExplicouBoole.
Para considerar as frases A Rita explicou o Boole ao Miguel no sábado e No domingo, o Miguel
explicou o Boole ao João podemos considerar um predicado quaternário Explicou(x, y, z, w) —
que se lê “x explicou y a z no w” — e traduzir as duas frases consideradas para LPO:
Os sı́mbolos funcionais são sı́mbolos que permitem obter outras designações para objectos.
Exemplos. (1) Jorge é pai do Nuno. Supondo que a afirmação é verdadeira, Jorge e pai(N uno)
são duas designações diferentes para o mesmo indivı́duo; pai é um sı́mbolo funcional unário.
(2) As expressões 3 e ((1 + 1) + 1) são duas designações diferentes do mesmo número natural; +
é um sı́mbolo funcional binário.
22
Estruturas Discretas 1.2. Lógica dos predicados
• São termos apenas as expressões que possam ser obtidas por aplicação sucessiva dos passos
anteriores um número finito de vezes.
Leituras suplementares:
23
Estruturas Discretas 1.3. Raciocı́nio matemático, indução e recursão
Para entendermos um texto matemático temos que compreender o que faz com que um argu-
mento esteja matematicamente correcto, isto é, seja uma prova. Uma prova é uma demonstração
de que alguma afirmação é verdadeira. Normalmente apresentamos provas escrevendo frases em
Português misturadas com equações e sı́mbolos matemáticos.
Um teorema é uma afirmação que se pode demonstrar ser verdadeira. Demonstra-se que um
teorema é verdadeiro com uma sequência de afirmações que formam um argumento, chamada
prova. Para construir provas, precisamos de métodos que nos permitam deduzir novas afirmações
a partir de afirmações já comprovadas. As afirmações usadas numa prova incluem os axiomas
ou postulados da teoria, as hipóteses do teorema a provar e teoremas previamente provados. As
regras de inferência são as ferramentas para deduzir novas conclusões e ligam os diversos passos
da prova. Recorde de 1.1 que um argumento do tipo
A1
A2
..
.
An
∴B
é uma regra de inferência se A1 ∧ A2 ∧ · · · ∧ An →B for uma tautologia. Por exemplo, é a
tautologia (p ∧ (p→q))→q que está por trás da regra modus ponens, como vimos na primeira
secção. Vimos na altura, também, uma lista das regras de inferência mais usadas no raciocı́nio
matemático:
24
Estruturas Discretas 1.3. Raciocı́nio matemático, indução e recursão
Qualquer argumento elaborado com regras de inferência diz-se válido. Quando todas as
afirmações usadas num argumento válido são verdadeiras, podemos ter a certeza de chegar a uma
conclusão correcta. No entanto, um argumento válido pode conduzir a conclusões incorrectas se
uma ou mais proposições falsas são usadas no argumento. Por exemplo,
“Se 101 é divisı́vel por 3 então 1012 é divisı́vel por 9. 101 é divisı́vel por 3. Logo,
1012 é divisı́vel por 9.”
é um argumento válido (baseado na regra MP) mas a conclusão é falsa: 9 não divide 1012 =
10 201.
Noutro tipo de falácias muito comum as conclusões estão incorrectas porque os argumentos
não são válidos: apesar de aparentarem ser regras de inferência, na realidade não o são ( baseiam-
se em contingências e não em tautologias).
Exemplo 1. A proposição ((p→q) ∧ q)→p não é uma tautologia (é falsa quando p é falsa e q é
verdadeira). No entanto, por vezes é usada como se fosse uma tautologia (este tipo de argumento
incorrecto chama-se falácia de afirmar a conclusão):
(É claro que pode aprender matemática discreta sem precisar de resolver todos os exercı́cios
destes apontamentos!)
Exemplo 2. A proposição ((p→q ∧ ¬p)→¬q não é uma tautologia, pois é falsa quando p é falsa
e q é verdadeira. É outro exemplo de proposição que por vezes é usada como regra de inferência
em argumentos incorrectos (a chamada falácia de negar a hipótese):
(É claro que pode aprender matemática discreta sem ter resolvido todos os exercı́cios destes
apontamentos!)
Os matemáticos usam diversos métodos para provar a validade de uma proposição ou argu-
mento. Façamos uma breve digressão, com exemplos, pelos mais comuns.
(1) Verificação exaustiva. Algumas proposições podem ser provadas por verificação exaustiva
de um número finito de casos.
25
Estruturas Discretas 1.3. Raciocı́nio matemático, indução e recursão
É claro que uma proposição enunciada para um número infinito de casos não poderá ser
provada directamente por verificação exaustiva (por mais casos que consigamos verificar nunca
conseguiremos verificar todos...). Por exemplo, se tentarmos comprovar, com a ajuda do com-
putador, a famosa conjectura de Goldbach, que afirma que
qualquer inteiro par maior do que 2 pode escrever-se como soma de dois primos
não encontraremos nenhum contra-exemplo (isto é, um exemplo que refute a conjectura). Pelo
contrário, à medida que o inteiro par cresce, mais soluções vamos encontrando para a partição
do inteiro em dois primos.
A seguinte figura, que mostra o cometa de Goldbach até ao número 2000 (isto é, o número
de maneiras possı́veis de escrever o inteiro par n como soma de 2 primos, para n de 4 até 2000)
reforça isso mesmo:
26
Estruturas Discretas 1.3. Raciocı́nio matemático, indução e recursão
Mesmo assim, não poderemos garantir que a conjectura é verdadeira para qualquer inteiro par
maior do que 2 (tal como ninguém o conseguiu fazer até hoje!). De facto, verificar que uma dada
proposição sobre os inteiros n é válida para muitos valores de n, não significa automaticamente
que a proposição seja verdadeira para todo o n.
A conjectura de Polya é um exemplo relevante disso mesmo:
Um número natural n diz-se de tipo par caso a sua factorização em primos tenha um número
par de factores, caso contrário diz-se de tipo ı́mpar. Por exemplo, os números 4 e 24 são de tipo
par (pois 4 = 2 × 2 e 24 = 2 × 2 × 2 × 3) enquanto 30 e 18 são de tipo ı́mpar (pois 30 = 2 × 3 × 5
e 18 = 2 × 3 × 3). Seja P (n) o número de naturais ≤ n de tipo par e seja I(n) o número de
naturais ≤ n de tipo ı́mpar. Se verificarmos para alguns valores de n ≥ 2 constataremos sempre
que
I(n) ≥ P (n).
Em 1919, o famoso matemático Polya conjecturou a possibilidade desta proposição ser verda-
deira. Depois de verificada para todo o n inferior a 1 milhão, mais matemáticos se convenceram
dessa possibilidade. No entanto, em 1962, R. Sherman Lehman encontrou um contra-exemplo:
para n = 906 180 359, tem-se I(n) = P (n) − 1. O contra-exemplo mais pequeno foi entretanto
encontrado por Minoru Tanaka em 1980: é o número n = 906 150 257. Portanto, para qualquer
inteiro n no intervalo [2, 906 150 256] tem-se de facto I(n) ≥ P (n).
Mais adiante, estudaremos o método de indução matemática que nos permite garantir a
validade de muitas afirmações para uma lista infinita de inteiros sem grande dificuldade.
(2) Prova de implicações (condicionais). A maioria dos teoremas que se provam em ma-
temática são implicações (ou equivalências, que são conjunções de duas implicações). A im-
27
Estruturas Discretas 1.3. Raciocı́nio matemático, indução e recursão
plicação (“se p então q” ou “p implica q”) é uma afirmação condicional com hipótese p e con-
clusão q. A sua contraposta é a afirmação “se não q então não p” e a sua recı́proca é “se q então
p”.
(2a) Prova directa. Como a maioria dos teoremas utilizados na prática da matemática são
implicações, as técnicas para provar implicações são muito importantes. Para provar que p ⇒ q,
ou seja, que p → q é uma tautologia, mostra-se que se p é verdadeira também q o é: começamos
por assumir que a hipótese p é verdadeira; depois tentamos encontrar uma proposição que resulte
da hipótese e/ou factos conhecidos; continuamos deste modo até chegarmos à conclusão q.
(2b) Prova indirecta. A seguinte tabela de verdade mostra que uma condicional e a sua
contraposta são equivalentes:
p q ¬q ¬p p→q ¬q→¬p
V V F F V V
V F V F F F
F V F V V V
F F V V V V
Esta equivalência proporciona um método alternativo para provar uma implicação (o cha-
mado método indirecto).
Prova. A contraposta desta afirmação é “se n é ı́mpar então n2 é ı́mpar”, que é verdadeira pelo
Exemplo anterior. 2
p q p→q p ∧ ¬q p ∧ ¬q→F
V V V F V
V F F V F
F V V F V
F F V F V
28
Estruturas Discretas 1.3. Raciocı́nio matemático, indução e recursão
Portanto temos aqui mais um método alternativo de demonstrar uma implicação: para provar
“se p então q” é suficiente provar “p e não q implica falso”, ou seja, assumir p e ¬q e depois
argumentar de modo a chegar a uma contradição (proposição sempre falsa, como vimos em 1.1).
Chama-se a esta técnica de demonstração prova por contradição (ou por redução ao absurdo).
Prova. Suponhamos, por absurdo, que n2 é ı́mpar e n é par. Então n = 2k para algum inteiro
k pelo que n2 = (2k)2 = 4k 2 = 2(2k 2 ) é também um inteiro par. Chegamos assim à conclusão
que n2 é simultaneamente um inteiro par e ı́mpar, o que é uma contradição. 2
Prova. Suponhamos, por absurdo, que 2|5n e n é ı́mpar. Então 5n = 2d para algum inteiro d e
n = 2k + 1 para algum inteiro k. Juntando tudo obtemos 2d = 5n = 5(2k + 1) = 10k + 5. Logo
5 = 2d − 10k = 2(d − 5k), o que é uma contradição pois afirma que 5 é um número par! 2
√
Exemplo 8. 2 é um número irracional.
√ √
Prova. Suponhamos, por absurdo, que 2 é racional. Então 2 = pq para algum par de
inteiros p e q (podemos assumir que a fracção p/q está já escrita na sua forma reduzida, isto
é, mdc(p, q) = 1). Elevando ao quadrado ambos os membros da igualdade anterior obtemos
2q 2 = p2 , pelo que p2 é par. Então, pelo Exemplo 5, p é par. Sendo p par, é claro que p2 é
um múltiplo de 4, ou seja, p2 = 4k para algum inteiro k. Consequentemente, 2q 2 = 4k, isto é,
q 2 = 2k é par, pelo que q também é par. Chegámos aqui a uma contradição: p e q são pares
mas mdc(p, q) = 1. 2
(3) Prova de equivalências (“se e só se”; abreviadamente “sse”). Uma proposição da
forma p ⇔ q (“p se e só se q”) significa a conjunção de “p implica q” e “q implica p”. Portanto,
é preciso apresentar duas provas. Por vezes, estas provas podem ser escritas como uma só prova
na forma “p sse r sse s sse ... sse q”, onde cada “... sse ...” é conclusão evidente da informação
anterior.
29
Estruturas Discretas 1.3. Raciocı́nio matemático, indução e recursão
(i) n é ı́mpar.
(ii) n2 é ı́mpar.
(iii) n2 − 2n + 1 é par.
Prova. Para provar a equivalência das três asserções, basta provar que as implicações (i)→(ii),
(ii)→(iii) e (iii)→(i) são verdadeiras:
(i)→(ii): Provada no Exemplo 4.
(ii)→(iii): Se n2 é ı́mpar então n2 + 1 é par. Como 2n é sempre par, então n2 − 2n + 1 é par.
(iii)→(i): No Exemplo 6 provámos que se n é par então n2 − 2n + 1 é ı́mpar. A implicação
(iii)→(i) é a sua contraposta, pelo que também é verdadeira. 2
(4) Prova de proposições com quantificadores. A maneira mais óbvia de provar uma
afirmação de existência ∃xP (x) é determinar um objecto particular a para o qual P (a) é V.
√
Por exemplo, para provar que existe um número irracional basta mostrar que 2 é irracional
(como fizemos no Exemplo 8). Mas às vezes não é fácil ou possı́vel determinarmos explicitamente
esse objecto e temos então que adoptar uma estratégia menos directa, como o exemplo seguinte
ilustra:
Observe que nesta prova não sabemos qual das duas possibilidades se verifica pelo que não
exibimos um par especı́fico de irracionais r, s tais que rs é racional. Limitámo-nos a mostrar
que tal par existe. Esta prova é também um exemplo de uma prova por casos, outra técnica de
demonstração muito útil.
Como poderemos provar uma afirmação universal ∀xP (x) ? Uma possibilidade é tomarmos
um x arbitrário e mostrar que satisfaz a propriedade P . Por exemplo:
30
Estruturas Discretas 1.3. Raciocı́nio matemático, indução e recursão
Note que ao iniciarmos a prova dizendo “Seja n um número natural arbitrário”, então usamos
sempre o sı́mbolo n ao longo da prova para representar esse número e assumimos que o seu valor
permanece constante (não impondo no entanto nenhuma restrição a esse valor).
Proposições da forma ∀xP (x) são às vezes provadas pelo método da contradição: assumindo
¬ ∀xP (x), obtemos um x tal que ¬P (x) (porque ¬ ∀xP (x) ≡ ∃x ¬P (x)). Temos assim uma
maneira de começar a prova. A dificuldade pode estar em terminá-la, isto é, em obter uma
contradição...
(5) Prova por indução matemática. A que é igual a soma dos n primeiros inteiros positivos
ı́mpares? Para n = 1, 2, 3, 4, 5, 6 tem-se
1 = 1,
1 + 3 = 4,
1 + 3 + 5 = 9,
1 + 3 + 5 + 7 = 16,
1 + 3 + 5 + 7 + 9 = 25.
Destes valores particulares é razoável conjecturar4 que a soma, para qualquer n, deverá ser
igual a n2 . O método de indução matemática permite-nos provar facilmente que esta conjectura
está correcta5 . Trata-se de um método muito potente para provar asserções deste tipo, enunci-
adas sobre o conjunto N dos naturais. Baseia-se na observação óbvia que todo o subconjunto
não vazio de N tem um elemento mı́nimo e no seguinte:
4 Veja [Link]/∼picado/ediscretas/somatorios/Matematica sem palavras files/soma [Link].
5 Assim como todas as outras em [Link]/∼picado/ediscretas/somatorios.
31
Estruturas Discretas 1.3. Raciocı́nio matemático, indução e recursão
Prova. Suponhamos, por absurdo, que S 6= N. Então N r S 6= ∅ logo tem um elemento mı́nimo
m. Como 1 ∈ S e m ∈ / S, então m > 1. Portanto, m − 1 é um natural e pertence a S (pois m
é o mı́nimo de N r S). Logo, por hipótese, (m − 1) + 1 ∈ S, isto é, m ∈ S. Chegamos assim a
uma contradição: m ∈
/ S e m ∈ S. Em conclusão, S = N. 2
80
881
79 2
75767778
86 85 8483
87
727374
88
71
70
69 6867
66 6564
63 6261
60
59
58
57
56
5 55
5253 4
5051
4849
47
46
454443
4241
40 3938
7
336
34 35
33
303132
28 29
27
2526
24
23
22
2210
1918
1716
15 1413
12
11
10
7 89
5 6
4
3
2
1
Princı́pio de Indução Matemática (PIM). Seja P (n), n ∈ N, uma proposição. Para provar
que P (n) é verdadeira para qualquer n ∈ N basta:
(2) (Passo indutivo) Mostrar que a implicação P (k)→P (k + 1) é verdadeira para qualquer
k ∈ N.
Prova. Suponhamos que os dois passos foram provados. Seja S = {n | P (n) é verdadeira}. O
passo inicial garante que 1 ∈ S; por outro lado, o passo indutivo garante que k ∈ S implica
k + 1 ∈ S. Então, pela Base do PIM, podemos concluir que S = N. 2
Exemplo 13. Para qualquer natural n, a soma dos n primeiros inteiros positivos ı́mpares é
igual a n2 .
32
Estruturas Discretas 1.3. Raciocı́nio matemático, indução e recursão
1 + 3 + 5 + · · · + (2n − 1) = n2 .
| {z }
n parcelas
P (1) é claramente verdadeira: 1 = 12 . Assumindo que P (k) é verdadeira, provemos que P (k +1)
é verdadeira (para qualquer k ≥ 1). O membro esquerdo de P (k + 1) é:
que é o membro direito de P (k + 1). Portanto, P (k + 1) é verdadeira e, pelo PIM, segue que
P (n) é verdadeira para qualquer n. 2
Exemplo 14. Para qualquer natural n, a soma dos n primeiros inteiros positivos pares é igual
a n2 + n.
2 + 4 + 6 + · · · + 2n = n2 + n.
| {z }
n parcelas
Queremos mostrar que P (n) é V para qualquer n ∈ N. Pelo método de indução matemática
teremos que mostrar duas coisas:
(1) P (1) é V: É óbvio, pois a identidade P (1) resume-se a 2 = 12 + 1.
(2) A implicação P (k) → P (k + 1) é V para qualquer k ≥ 1: Suponhamos que P (k) é V, isto é,
2 + 4 + 6 + · · · + 2k = k 2 + k.
Então
2 + 4 + 6 + · · · + 2k + (2k + 2) = k 2 + k + 2k + 2 = (k + 1)2 + k + 1,
n(n + 1)(2n + 1)
Então f (n) = para qualquer n ∈ N.
6
Prova. Seja P (n) a proposição f (n) = n(n+1)(2n+1)/6. Como f (1) = 1 e 1(1+1)(2+1)/6 = 1,
então P (1) é verdadeira. Assumindo que P (k) é verdadeira, provemos que P (k +1) é verdadeira.
33
Estruturas Discretas 1.3. Raciocı́nio matemático, indução e recursão
f (k + 1) = f (k + 1 − 1) + (k + 1)2 (definição de f )
2
= f (k) + (k + 1) (álgebra)
k(k + 1)(2k + 1)
= + (k + 1)2 (hip. indução)
6
(k + 1)(2k 2 + 7k + 6)
= (álgebra)
6
(k + 1)(k + 2)(2k + 3)
= (álgebra)
6
(k + 1)((k + 1) + 1)(2(k + 1) + 1)
= (álgebra)
6
que é o membro direito de P (k + 1). Portanto, P (k + 1) é verdadeira e, pelo PIM, segue que
P (n) é verdadeira para qualquer n. 2
1 1 1 1
Exemplo 16. Para qualquer natural n, + + ··· + n = 1 − n.
2 22 2 2
Prova. Seja P (n) a identidade
1 1 1 1
+ 2 + ··· + n = 1 − n.
2
| 2 {z 2 } 2
n parcelas
Queremos mostrar que P (n) é V para qualquer n ∈ N. Pelo método de indução matemática
teremos que mostrar duas coisas:
34
Estruturas Discretas 1.3. Raciocı́nio matemático, indução e recursão
1 1
(1) P (1) é V: É óbvio, pois a identidade P (1) resume-se a =1− .
2 2
(2) A implicação P (k) → P (k + 1) é V para qualquer k ≥ 1: Suponhamos que P (k) é V, isto é,
1 1 1 1
+ + ··· + k = 1 − k.
2 22 2 2
Então
1 1 1 1 1 1 1 1 2−1 1
+ 2 + · · · + k + k+1 = 1 − k + k+1 = 1 − k − k+1 = 1 − k+1 = 1 − k+1 ,
2 2 2 2 2 2 2 2 2 2
o que mostra precisamente que P (k + 1) também é V. 2
Queremos mostrar que P (n) é V para qualquer n ∈ N. Pelo método de indução matemática
teremos que mostrar duas coisas:
(1) P (1) é V: É óbvio, pois a identidade P (1) resume-se a 1 = 12 + 02 .
(2) A implicação P (k) → P (k + 1) é V para qualquer k ≥ 1: Suponhamos que P (k) é V, isto é,
Então
1 + 3+5 + · · · + (2k − 3) + (2k − 1) + (2k + 1) + (2k − 1) + (2k − 3) · · · + 5 + 3 + 1 =
= k 2 + (k − 1)2 + (2k + 1) + (2k − 1) = k 2 + (k − 1)2 + 4k = k 2 + k 2 − 2k + 1 + 4k =
= k 2 + k 2 + 2k + 1 = (k + 1)2 + k 2
o que mostra precisamente que P (k + 1) também é V. 2
É fácil adaptar a demonstração da Base do PIM para que este funcione também para pro-
posições P (n) onde n ∈ {a, a + 1, . . .}:
Princı́pio de Indução Matemática (PIM). Seja P (n), n ∈ {a, a + 1, . . .}, uma proposição.
Para provar que P (n) é verdadeira para qualquer n ≥ a basta:
(1) (Passo inicial) Mostrar que P (a) é verdadeira.
(2) (Passo indutivo) Mostrar que a implicação P (k)→P (k + 1) é verdadeira para qualquer
k ≥ a.
Em algumas situações pode ser difı́cil definir um objecto de modo explı́cito e ser mais fácil
defini-lo em função dele próprio. A este processo chama-se recursão e pode ser usado para definir
sequências, sucessões e conjuntos. Por exemplo, a sequência das potências de 2 pode ser definida
explicitamente por an = 2n para n = 0, 1, 2, . . ., mas também pode ser definida recursivamente
pelo primeiro termo a0 = 1 e pela regra que permite definir um termo à custa dos anteriores:
an+1 = 2an para n = 0, 1, 2, . . ..
Portanto, podemos definir uma função sobre os inteiros não negativos
35
Estruturas Discretas 1.3. Raciocı́nio matemático, indução e recursão
• dando uma regra que permita calcular o seu valor num inteiro a partir dos valores em
inteiros menores.
f (n) = n! = n × (n − 1) × (n − 2) × · · · × 2 × 1.
As definições recursivas são também utilizadas frequentemente para definir conjuntos. Nesse
caso, especifica-se um colecção inicial de elementos como pertencendo ao conjunto que se pretende
definir, e depois especificam-se as regras de construção dos elementos do conjunto a partir de
elementos que já se sabe estarem no conjunto. Foi o que fizemos, quando logo na Secção 1.1
definimos deste modo o conjunto das fórmulas bem formadas do cálculo proposicional. Os
conjuntos definidos deste modo ficam bem definidos e os teoremas sobre eles podem ser provados
usando a definição recursiva.
• 3 ∈ S,
• Se x ∈ S e y ∈ S então x + y ∈ S.
Mostre que S é o conjunto dos inteiros positivos divisı́veis por 3. (Assume-se implicitamente
neste tipo de definições que um elemento só pertence a S se puder ser gerado usando as duas
regras na definição de S.)
Prova. Seja C o conjunto de todos os inteiros positivos divisı́veis por 3. Para provar a igualdade
C = S temos que verificar as inclusões C ⊆ S e S ⊆ C.
C ⊆ S: Provemos por indução matemática que todo o inteiro positivo divisı́vel por 3 pertence
a S. Para isso seja P (n) a proposição “3n ∈ S”. O passo inicial P (1) é verdadeiro pela
primeira regra da definição recursiva. Para estabelecer o passo indutivo, assumimos que P (n) é
verdadeira, ou seja, que 3n ∈ S. Mas então, como 3 também pertence a S, pela segunda regra
da definição recursiva, 3n + 3 = 3(n + 1) também está em S.
S ⊆ C: Basta mostrar que as regras de definição de S só geram elementos que estão contidos
em C. A primeira é evidente: 3 ∈ C. Quanto à segunda, se x, y ∈ S são divisı́veis por 3 então
x + y também é divisı́vel por 3, o que completa a prova. 2
36
Estruturas Discretas 2.1. Algoritmos e sua complexidade
2. Algoritmos
Na matemática discreta abordamos muitos tipos de problemas. Em muitos deles, para chegarmos
à solução, temos que seguir um procedimento que, num número finito de passos, conduz à tão
desejada solução. A uma tal sequência chama-se algoritmo6 . Um algoritmo é um procedimento
para resolver um problema num número finito de passos.
• Compare o inteiro seguinte na sequência com o máximo temporário, e se for maior, tome
o máximo temporário igual a esse inteiro.
• Pare quando chegar ao fim da sequência. O máximo temporário será então o maior inteiro
da sequência.
Abreviadamente:
É claro que um algoritmo pode ser formulado explicitamente numa qualquer linguagem de
computação, mas nesse caso só poderemos utilizar expressões válidas dessa linguagem. Exempli-
fiquemos isso convertendo cada linha do algoritmo acima em código Maple7 . Podemos considerar
uma lista de números como um vector (matriz). Para usar esta funcionalidade no Maple temos
primeiro que abrir a package de Álgebra Linear linalg:
6 O termo algoritmo deriva do nome al-Khowarizmi de um matemático persa do século IX, cujo livro sobre
numerais hindus esteve na base da notação decimal moderna que hoje utilizamos.
7 Se estiver interessado no programa de cálculo simbólico Maple recomendamos a leitura do manual Maple
37
Estruturas Discretas 2.1. Algoritmos e sua complexidade
Continuando:
Fica assim traduzido o algoritmo em Maple. Dando como input uma qualquer sequência t
• Precis~
ao: os passos do algoritmo têm que estar definidos com precisão.
• Realizável: deve ser possı́vel realizar cada passo do algoritmo em tempo útil.
38
Estruturas Discretas 2.1. Algoritmos e sua complexidade
Uma definição recursiva exprime o valor de uma função num inteiro positivo em termos dos
valores da função em inteiros mais pequenos. Isto significa que podemos ter sempre um algoritmo
recursivo para calcular o valor de uma função definida por recursão. Por exemplo:
Também não é difı́cil especificar um algoritmo recursivo para o cálculo do máximo divisor
comum de dois inteiros:
Há outro modo de calcular a função potência f (n) = an a partir da sua definição recursiva:
em vez de reduzir sucessivamente o cálculo a inteiros mais pequenos, podemos começar com o
valor da função em 1 e aplicar sucessivamente a definição recursiva para encontrar os valores
da função em números sucessivamente maiores. Tal procedimento diz-se iterativo. Por outras
palavras, para calcular an usando um processo iterativo, começamos em 1 e multiplicamos
sucessivamente por cada inteiro positivo ≤ n:
39
Estruturas Discretas 2.1. Algoritmos e sua complexidade
Se simularmos este algoritmo para os primeiros 200 inteiros e contarmos o número de iterações
necessárias para levar a função até 1 obtemos a seguinte tabela:
40
Estruturas Discretas 2.1. Algoritmos e sua complexidade
Desde o valor inicial 27 até 1 a função atinge um pico na 77a iteração com o valor 9232. Grafi-
camente:
Eficiência de algoritmos. Além de produzir uma solução satisfatória e precisa para o problema
que pretende resolver, um algoritmo tem que ser eficiente (em termos de velocidade de execução).
Um dos objectivos da algoritmia consiste em medir a eficiência de algoritmos. Muitas vezes
dispomos de diferentes algoritmos que resolvem correctamente o problema, mas algum poderá
41
Estruturas Discretas 2.1. Algoritmos e sua complexidade
ser mais eficiente que os outros. Uma medida de eficiência será, claro, o tempo dispendido por
um computador para resolver o problema executando o algoritmo.
Seja P um problema e A um algoritmo para resolver P . O tempo de execução de A pode
ser analisado contando o número de determinadas operações que são efectuadas durante a sua
execução. Esta contagem pode depender do tamanho do input.
2(n − 1) + 1 = 2n − 1
comparações.
(2) Se P consiste em verificar se um determinado objecto pertence a uma dada lista, será também
natural contar o número de comparações efectuadas por A, que dependerá do tamanho da lista.
(3) Para resolver o problema da ordenação de listas existem diversos algoritmos de ordenação,
entre os quais o chamado algoritmo da inserção. A ideia por detrás deste algoritmo consiste em
dividir a lista L que se pretende ordenar em duas sublistas. A sublista L1 inclui os elementos
de L já ordenados e a sublista L2 , que é um sufixo da lista inicial, inclui os elementos de L
ainda não analisados. Cada passo do algoritmo consiste na inserção do primeiro elemento de L2
ordenadamente na lista L1 e, claro, na sua remoção da lista L2 . O algoritmo inicia-se com
L1 = {P rimeiro[L]} e L2 = Resto[L]
e termina quando L2 = ∅. No caso dos algoritmos de ordenação é tı́pico tomar-se como medida
de eficiência o número de comparações entre elementos. Claro que o número de comparações
depende da lista dada inicialmente.
Simulemos o algoritmo para a lista inicial
[3,8,6,2,5,4,10,9,7,1]
As seguintes figuras dão uma visão dinâmica da ordenação sucessiva efectuada pelo algoritmo.
As bolas verdes correspondem a elementos já ordenados (ou seja, elementos da sublista L1 ),
enquanto que as vermelhas correspondem aos elementos ainda não ordenados da sublista L2 .
42
Estruturas Discretas 2.1. Algoritmos e sua complexidade
3, 8, 6, 2, 5, 4, 10, 9, 7, 1 3, 8, 6, 2, 5, 4, 10, 9, 7, 1
3, 6, 8, 2, 5, 4, 10, 9, 7, 1 2, 3, 6, 8, 5, 4, 10, 9, 7, 1
2, 3, 5, 6, 8, 4, 10, 9, 7, 1 2, 3, 4, 5, 6, 8, 10, 9, 7, 1
43
Estruturas Discretas 2.1. Algoritmos e sua complexidade
2, 3, 4, 5, 6, 8, 10, 9, 7, 1 2, 3, 4, 5, 6, 8, 9, 10, 7, 1
2, 3, 4, 5, 6, 7, 8, 9, 10, 1 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
• situação média.
Um input no caso da pior situação é um input que leva A a executar o maior número de
operações. No caso da determinação do elemento máximo de uma sequência (exemplo (1)),
fixado o comprimento n da sequência, a pior situação acontece para qualquer lista de números
(pois o número de comparações é constante, igual a 2n − 1). No exemplo (2) a pior situação
será uma lista que não contém o objecto procurado.
No caso do algoritmo de inserção (exemplo (3)), a pior situação é quando a lista dada está
ordenada por ordem inversa.
A análise na situação média obriga a considerações probabilı́sticas pois é necessário atribuir
a cada situação uma probabilidade. Muitas vezes considera-se que as situações têm todas a
mesma probabilidade (a distribuição das mesmas é então uniforme).
44
Estruturas Discretas 2.1. Algoritmos e sua complexidade
Estudemos um pouco o caso da pior situação. Seja TA (n) o tempo de execução máximo de
A para inputs de tamanho n. A função TA chama-se a função da pior situação para A. Um
algoritmo A para resolver um problema P diz-se optimal na pior situação se qualquer algoritmo
B que resolve P satisfaz
Uma árvore de decisão para um algoritmo é uma árvore cujos nós representam pontos de
decisão no algoritmo e cujas folhas representam os resultados.
Teste. Dado um conjunto de nove moedas, uma das quais é mais pesada que as outras, use
uma balança de dois pratos (sem pesos) para determinar a moeda mais pesada.
1 2 3 4 Hu 5678
HH
H
12 u 34
u 5 6 Hu 7 8
H
@ P =9
@
@ @
1 u 2 3 @u 4 5 u 6 7 @u 8
A A A A
A A A A
u
Au u Au u Au u Au
P =1 P =2 P =3 P =4 P =5 P =6 P =7 P =8
Esta árvore tem profundidade três8 , o que significa que, neste algoritmo, o caso da pior
situação são 3 pesagens.
Será o algoritmo optimal na pior situação? Em cada pesagem pode acontecer uma de três
coisas: o prato da esquerda está mais pesado, o prato da direita está mais pesado ou os pratos
estão equilibrados. Portanto, neste tipo de problemas com balanças, as árvores de decisão são
ternárias (em cada nó haverá no máximo três ramos). Uma árvore ternária de profundidade d
tem, no máximo, 3d folhas. Como há 9 possı́veis resultados, então
Portanto, poderá haver, eventualmente, algum algoritmo cuja árvore tenha profundidade 2.
E, de facto, há:
8 A profundidade de uma árvore é o comprimento do maior caminho desde a raiz da árvore até às folhas. Na
árvore em questão, desde a raiz até às folhas há caminhos com um ramo (no caso da folha P = 9) ou três ramos
(nas restantes folhas). Mais tarde, quando estudarmos os grafos, estudaremos as árvores com mais cuidado.
45
Estruturas Discretas 2.1. Algoritmos e sua complexidade
u456
1 2 3H
HH
H
HH
u3 u 9 4 Hu 6
H
H
1 7
JJ
JJ
JJ
J
J
J
J
J
J
u
u Ju u
u Ju u
u Ju
P =1 P =2 P =3 P =7 P =8 P =9 P =4 P =5 P =6
Pela discussão acima podemos agora concluir que este é um algoritmo optimal na pior si-
tuação (2 pesagens).
Teste. Dado um conjunto de nove moedas, uma das quais é defeituosa (mais pesada ou mais
leve que as outras), determine um algoritmo optimal na pior situação para balanças de dois
pratos (sem pesos) que determine a moeda defeituosa e dê como output se a moeda é mais
pesada ou mais leve.
Uma árvore de decisão ternária com profundidade d terá no máximo 3d folhas, donde 3d ≥ 18,
isto é,
d ≥ log3 18 ≥ dlog3 18e = 3.
(A função d−e : R → N nos números reais é a chamada função tecto (ceiling) e aplica cada
número real x no menor inteiro dxe tal que dxe ≥ x. De modo análogo, podemos definir a
função chão (floor) b−c : R → N que a cada real x faz corresponder o maior inteiro bxc ≤ x.
Por exemplo, b 12 c = 0, d 12 e = 1, b− 12 c = −1, d− 12 e = 0.)
Portanto, qualquer algoritmo que resolva o problema terá sempre que efectuar pelo menos 3
pesagens. No algoritmo seguinte esse valor é igual a 3:
1 2!
3 !a u 456
! aa
! ! aa
!! aa
! aa
u u 1 2 3au
! ! a
1 2 3 7 8 9
! 7 8 Q7 8 9
@ Q
@ Q
@ Q
Q
1 u
3 4 u 6 7 u 9 7 u 9 7
@@ u 9 4 u 6 1Qu 3
Q
B B B B B B
B B B B B B
B B B B B B
u
u BBu u
u BBu u
u u
BBu u BBu u
u BBu u
u BBu
1P 2P 3P 6L 5L 4L 7P 8L 9L 9P 8P 7L 4P 5P 6P 3L 2L 1L
46
Estruturas Discretas 2.1. Algoritmos e sua complexidade
> ha := time():
> Funcaoqualquer(x):
> time() - ha;
Vamos agora usar estas funções para comparar dois algoritmos (ver Exercı́cios 11 e 12 da
ficha prática) que calculam o valor de um polinómio p(x) = a0 + a1 x + a2 x2 + · · · + an xn num
ponto especı́fico c, ou seja, o número p(c) = a0 + a1 c + a2 c2 + · · · + an cn . Os valores de entrada
são o número c e a lista de coeficientes a0 , a1 , a2 , . . . , an do polinómio.
Por exemplo, para o polinómio p(x) = 4 + 3x + 2x2 + x3 , o valor de p(5) é igual a 194:
47
Estruturas Discretas 2.1. Algoritmos e sua complexidade
e se fizermos
obtemos a lista dos coeficientes correspondentes, que podemos usar como input nos algoritmos
Polinomio e Horner. Agora, usando as ferramentas para medir o tempo de execução, obtemos:
> ha := time():
> Horner(104567890000000.0, q2000);
0.3913255222 1027971
> ha := time():
> Polinomio(104567890000000.0, q2000);
0.3913255222 1027971
Podemos assim concluir que o método de Horner de cálculo polinomial é marginalmente mais
rápido que o método tradicional da substituição da indeterminada x pelo valor onde queremos
calcular a função polinomial.
48
Estruturas Discretas 2.1. Algoritmos e sua complexidade
Teste. Mostre que qualquer função polinomial p com coeficientes reais, dada por p(n) = at nt +
at−1 nt−1 + · · · + a1 n + a0 , é da ordem de q onde q(n) = nt .
Complexidade Terminologia
O(1) Complexidade constante
O(log n) Complexidade logarı́tmica
O(n) Complexidade linear
O(n log n) Complexidade n log n
O(nb ) Complexidade polinomial
O(bn ), onde b > 1 Complexidade exponencial
O(n!) Complexidade factorial
Qual é a complexidade do algoritmo de inserção (de ordenação de listas)? No pior caso, onde
a lista está ordenada por ordem inversa, para cada i é necessário fazer i − 1 comparações. Como
i varia de 2 até ao comprimento n da lista, temos que o número de comparações no pior caso é
igual a
Xn
(i − 1) = 1 + 2 + 3 + · · · + (n − 1),
i=2
ou seja, é dado pela soma dos n − 1 primeiros números naturais (termos de uma progressão
aritmética de razão 1):
n
X n2 − n
(i − 1) = 1 + 2 + 3 + · · · + (n − 1) = .
i=2
2
1
(n − 1)n.
2
49
Estruturas Discretas 2.2. Somatórios
Suponhamos que queremos inserir um elemento na parte da lista já ordenada (a sublista L1
com i − 1 elementos) de modo que a lista resultante com i elementos esteja ordenada. Potenci-
almente, existem i posições onde esse elemento pode ser colocado (para além das i − 1 ocupadas
pela lista dada, ainda existe a possibilidade do novo elemento ser maior que todos os outros).
Vamos impor uma hipótese probabilı́stica que consiste em assumir que todas as posições são
equiprováveis para colocar o novo elemento. Isto é, cada posição tem probabilidade 1/i.
O número de comparações necessárias se o novo elemento tiver que ser colocado na posição
k ≥ 2 é i − k + 1 e na posição k = 1 é i − 1. Logo o número médio de comparações para introduzir
o novo elemento numa das i posições é dado pelo somatório
i
!
X 1 1
(i − k + 1) + (i − 1).
i i
k=2
i−1 i−2
+
i 2
que é igual a
i2 + i − 2
.
2i
Logo, o número médio de comparações para que a lista fique ordenada é dado pelo somatório
n
X 1 1 i
− + .
i=2
2 i 2
2.2. Somatórios
50
Estruturas Discretas 2.2. Somatórios
X X X X
(5) Aditividade dos ı́ndices: ai + ai = ai + ai (sendo J um conjunto finito
i∈I i∈J i∈(I∪J) i∈(I∩J)
também).
X X
(6) Mudança de variável: af (i) = aj , para qualquer função bijectiva f : I → J; mais
i∈I j∈J
X X
aj · #(f −1 ({j})) .
geralmente, para qualquer função f : I → J, af (i) =
i∈I j∈J
P P
Teste. Mostre que 0≤i<n (ai+1 − ai )bi = an bn − a0 b0 − 0≤i<n ai+1 (bi+1 − bi ).
n
X 1 n+1 n+1
(a + ri) = a + rn (n + 1) = (2a + rn) = [a + (a + rn)]
i=0
2 2 2
n
X n
X
(a + ri) = (a + r(n − i)) (por comutatividade, com p(i) = n − i)
i=0 i=0
n
X n
X
⇔ (a + ri) = (a + rn − ri)
i=0 i=0
n
X n
X n
X
⇔ 2 (a + ri) = (a + rn − ri) + (a + ri)
i=0 i=0 i=0
n
X n
X
⇔ 2 (a + ri) = ((a + rn − ri) + (a + ri)) (por associatividade)
i=0 i=0
n
X n
X
⇔ 2 (a + ri) = (2a + rn)
i=0 i=0
n
X n
X
⇔ 2 (a + ri) = (2a + rn) 1 (por distributividade)
i=0 i=0
n
X
⇔ 2 (a + ri) = (2a + rn)(n + 1) (por progressão constante)
i=0
n
X 1
⇔ (a + ri) = (a + rn)(n + 1).
i=0
2
51
Estruturas Discretas 2.2. Somatórios
n
X n
X
= a 1+r i (por distributividade)
i=0 i=0
n n−1
!
X X
= a 1+r i+n (por progressão constante)
i=0 i=1
n2 − n
= a(n + 1) + r +n
2
n2 + n
= a(n + 1) + r .
2
n
X arn+1 − a
ari =
i=0
r−1
n
X n+1
X
ari + arn+1 = ari (por aditividade com I = {0, . . . , n} e J = {n + 1})
i=0 i=0
Xn n+1
X
⇔ ari + arn+1 = ar0 + ari (por aditividade com I = {0} e J = {1, . . . , n + 1})
i=0 i=1
Xn Xn
⇔ ari + arn+1 = ar0 + ari+1 (por mudança de variável com I = {0, . . . , n})
i=0 i=0
Xn n
X
⇔ ari + arn+1 = a + r ari (por distributividade)
i=0 i=0
n
X arn+1 − a
⇔ ari = .
i=0
r−1
52
Estruturas Discretas 2.2. Somatórios
ser atacados de forma ad hoc (esta é uma das caracterı́sticas de muitas áreas da matemática
discreta: a não existência de métodos gerais de resolução que obrigam uma abordagem ad hoc ao
problema; aqui o conhecimento e a destreza na manipulação dos diversos métodos particulares
de resolução, que poderão só funcionar em alguns casos, é crucial).
Nestas observações finais indicaremos muito resumidamente algumas das técnicas mais ele-
gantes e importantes para resolver somatórios.
Método 1: Método ad hoc. Calculando as primeiras somas parciais do somatório (a1 +a2 , a1 +
a2 + a3 , etc.), é por vezes possı́vel adivinhar a correspondente fórmula geral. A ilustração deste
método em muitos exemplos interessantes pode ser vista e experimentada (interactivamente) no
módulo Somatórios10 na página da disciplina.
A fórmula deverá depois ser confirmada com uma prova formal, para termos a certeza da
sua validade. Essa prova pode ser feita de modo análogo como fizemos nalguns exemplos acima,
usando as propriedades dos somatórios que enunciámos, ou, mais facilmente, pelo método de
indução matemática estudado na secção anterior.
Método 2: Método da perturbação. A ideia por detrás deste método é a seguinte: tentar
obter duas expressões diferentes que tenham o mesmo valor, “perturbando” levemente a soma
a calcular. Um exemplo ilustra o funcionamento deste método:
Pn 2
Suponhamos que pretendemos calcular o valor de q(n) = i=1 i . Vamos perturbar le-
vemente a sua definição e tentar escrever q(n + 1) de duas formas diferentes. Por um lado,
q(n + 1) = q(n) + (n + 1)2 e, por outro lado, por uma mudança de variável,
n
X
q(n + 1) = (i + 1)2
i=0
n
X
= (i2 + 2i + 1)
i=0
n
X n
X n
X
= i2 + 2 i+ 1
i=0 i=0 i=0
n
X
= q(n) + 2 i + (n + 1).
i=0
ou seja,
n n
X (n + 1)2 − (n + 1)
X
(n + 1)2 = 2 i + (n + 1) ⇔ i= .
i=1 i=1
2
Pn
Parece que não fizemos muitos progressos! Limitámo-nos a obter a soma i=1 i (note também
Pn−1
que temos aqui uma prova formal, rigorosa, da fórmula para i=1 i que utilizámos anterior-
mente, na página 40). Mas isto sugere imediatamente o seguinte: se perturbando um pouco a
10 [Link]/∼picado/ediscretas/somatorios.
53
Estruturas Discretas 2.2. Somatórios
Pn
soma q(n) dos quadrados conseguimos obter uma fórmula para i=1 i, será que perturbando a
Pn
soma c(n) = i=1 i3 dos cubos conseguimos uma fórmula para q(n)?
A fórmula de recorrência de c(n) é c(n + 1) = c(n) + (n + 1)3 e, por outro lado, por uma
mudança de variável,
n
X
c(n + 1) = (i + 1)3
i=0
n
X
= (i3 + 3i2 + 3i + 1)
i=0
n
X n
X n
X n
X
= i3 + 3 i2 + 3 i+ 1
i=0 i=0 i=0 i=0
3
= c(n) + 3q(n) + n(n + 1) + (n + 1).
2
Igualando ambas as expressões, obtemos
3
c(n) + (n + 1)3 = c(n) + 3q(n) + n(n + 1) + (n + 1),
2
ou seja,
3 3
(n + 1)3 = 3q(n) + n(n + 1) + (n + 1) ⇔ 3q(n) = (n + 1)3 − n(n + 1) − (n + 1)
2 2
2(n + 1)3 − 3n(n + 1) − 2(n + 1)
⇔ q(n) =
6
2n3 + 6n2 + 6n + 2 − 3n2 − 3n − 2n − 2
⇔ q(n) =
6
2n3 + 3n2 + n
⇔ q(n) =
6
1
⇔ q(n) = n(n + 1)(2n + 1).
6
Em [Link]/∼picado/ediscretas/somatorios/Matematica sem palavras files/
soma [Link] pode ver uma “prova” geométrica, sem palavras, desta fórmula.
n3
3
n3
Analisemos agora o erro e(n) = q(n) − 3 desta aproximação:
n3
e(n) = q(n − 1) + n2 −
3
(n − 1)3 n3 (n − 1)3
= q(n − 1) − + n2 − +
3 3 3
1
= e(n − 1) + n − .
3
54
Estruturas Discretas 2.2. Somatórios
Consequentemente,
n3 (n + 1)n n
q(n) = + − .
3 2 3
Coincide com o resultado calculado anteriormente pelo método da perturbação? Basta reduzir
ao mesmo denominador e simplificar:
n(n + 1)(2n + 1)
.
6
Sim, coincide, claro!
55
Estruturas Discretas 3.1. Noções básicas
A Teoria dos Grafos é actualmente uma das áreas mais importantes da matemática discreta.
Tendo as suas raı́zes em jogos e recreações matemáticas, atribui-se a sua criação a Euler, ao
resolver o problema das pontes de Königsberg em 1736, mas foram os problemas acerca de
fórmulas de estrutura de compostos quı́micos, que A. Cayley resolveu na segunda metade do
século XIX, que a começaram a desenvolver. Hoje, a Teoria dos Grafos tem sido aplicada
a muitas áreas (Informática, Investigação Operacional, Economia, Sociologia, Genética, etc.),
pois um grafo constitui o modelo matemático ideal para o estudo das relações entre objectos
discretos de qualquer tipo.
Por exemplo, a seguinte secção de um mapa de estradas
podem ser ambas representadas por meio de pontos e segmentos de recta do seguinte modo:
P Q
T S
Um grafo simples G consiste num conjunto finito e não vazio V (G) de elementos chamados
vértices e num conjunto finito A(G) de pares não ordenados de elementos distintos de V (G),
chamados arestas.
57
Estruturas Discretas 3.1. Noções básicas
f
a c i
d g
a d
b c
P R
58
Estruturas Discretas 3.1. Noções básicas
Um grafo dirigido (ou, abreviadamente, digrafo) D consiste num conjunto finito não va-
zio V (D) de elementos chamados vértices, e num conjunto finito A(D) de arestas orientadas
(eventualmente múltiplas), chamadas aros. Por exemplo:
a d
b c
Um digrafo diz-se simples se não contiver lacetes e os seus arcos forem todos distintos. Muitas
das definições que iremos estudar para pseudografos podem ser imitadas nos digrafos.
A tabela seguinte resume as definições dos vários tipos de grafos:
f : V (G1 ) → V (G2 )
preservando a adjacência de vértices, isto é, tal que o número de vezes em que {u, v} ocorre em
A(G1 ) é igual ao número de vezes que {f (u), f (v)} ocorre em A(G2 ). Neste caso f diz-se um
isomorfismo de grafos. Escreveremos G1 ∼ = G2 para indicar que G1 e G2 são isomorfos.
Exemplo. Os grafos
a1 a5 b1 b4
a2 a4 b3 b2
a3 b5
(G1 ) (G2 )
59
Estruturas Discretas 3.1. Noções básicas
f : V (G1 ) → V (G2 )
ai 7→ bi (i = 1, 2, 3, 4, 5).
Observações. (1) Dois grafos isomorfos têm o mesmo número de vértices e o mesmo número
de arestas.
(2) No caso em que G1 e G2 são grafos simples, uma bijecção f : V (G1 )→V (G2 ) é um isomorfismo
se e só se {u, v} ∈ A(G1 ) exactamente quando {f (u), f (v)} ∈ A(G2 ).
(3) Se não fizermos distinção entre grafos isomorfos, os grafos simples com menos de 4 vértices
são determinados pelo seu número de vértices e de arestas. Sendo p o número de vértices e q o
número de arestas, o quadro
p=1 u
p=2 u u u u
u u u u
A A
p=3 A A
u u u u u Au u Au
u u u u
2C(p,2)
60
Estruturas Discretas 3.1. Noções básicas
v1
u
q=0
v2 u u v3
v1 v1 v1
u u u
q=1 A
A
v2 u u v3 v2 u
u v3 v2 u Au v3
v1
v1 v1
u
u A u
q=2 A A
A
v2 u Au v3
v2 u
Au v3 v2 u
u v3
v1
u
q=3 A
A
v2 u
Au v3
É claro que os grafos da figura anterior com uma aresta são isomorfos entre si, o mesmo
acontecendo com os de duas arestas. A relação de isomorfismo particiona assim o conjunto
dos 23 grafos simples com vértices v1 , v2 , v3 , em 4 classes de equivalência, cada uma constituı́da
respectivamente pelos grafos simples com 0 arestas, 1 aresta, 2 arestas e 3 arestas. Representa-se
cada uma dessas classes por um (qualquer) dos grafos simples nela contidos, sem designação dos
vértices:
u u u u
A A
A A
u u u u u Au u Au
61
Estruturas Discretas 3.1. Noções básicas
u u
u u
q=0
u u
u u
q=1
u u u u
u u u u
q=2
u u u u u u
@
@
u u u @u u u
q=3
u u u u
u u u u
q=4
u u
u u
q=5
u u
@
@
u @u
q=6
O número de grafos simples em cada classe, com vértices v1 , v2 , v3 , v4 , é dado pela seguinte
tabela:
62
Estruturas Discretas 3.1. Noções básicas
(G1 ) (G2 )
embora G2 o seja.
Podemos combinar dois grafos de modo a obter um grafo maior. Se G1 e G2 são dois grafos
tais que V (G1 ) ∩ V (G2 ) = ∅, podemos definir a sua união G1 ∪ G2 como sendo o grafo G tal que
V (G) = V (G1 ) ∪ V (G2 ) e A(G) = A(G1 ) ∪ A(G2 ).
Um grafo é conexo se não puder ser expresso como união de dois grafos, e desconexo caso
contrário. Evidentemente qualquer grafo desconexo G pode ser expresso como união de grafos
conexos, cada um destes dizendo-se uma componente de G. Por exemplo,
63
Estruturas Discretas 3.1. Noções básicas
K8
K20
64
Estruturas Discretas 3.1. Noções básicas
Um grafo diz-se regular se todos os seus vértices tiverem o mesmo grau. Se esse grau for r
diz-se que o grafo é regular de grau r. Na figura seguinte, o grafo da direita é regular (de grau
3), o da esquerda não.
Proposição 1. [Euler (1736)] Em qualquer grafo a soma dos graus dos vértices é o dobro do
número de arestas, sendo portanto um número par.
Este resultado é habitualmente apelidado de Lema dos apertos de mão, pelo facto de implicar
que se um grupo de pessoas apertar as mãos entre si, o número total de mãos apertadas será
par — precisamente porque exactamente duas mãos estão envolvidas em cada aperto de mão.
Esta proposição implica imediatamente o seguinte:
Corolário 2. Seja G um grafo regular tal que todo o vértice tem grau 3. Então |V (G)| é par.
Prova. Designemos os vértices de G por v1 , v2 , . . . , vp . Como g(vi ) = 3 para cada i ∈ {1, 2, . . . , p},
Xp p
X
g(vi ) = 3p. Mas, pela Proposição 1, g(vi ) = 2q, sendo q o número de arestas de G. Logo
i=1 i=1
3p = 2q e, consequentemente, p é par. 2
65
Estruturas Discretas 3.1. Noções básicas
é o complementar de
Teorema 2. Para qualquer grafo simples G com 6 vértices, G ou G admitem K3 como subgrafo
(ou seja, G ou G contêm um triângulo).
Prova. Seja v um vértice de G. A soma dos graus de v nos grafos G e G é 5. Portanto, num
dos grafos G ou G, v está unido com, pelo menos, outros 3 vértices. Suponhamos, sem perda
de generalidade, que isto se passa em G, isto é, que há 3 vértices em G unidos a v por uma
aresta. Se dois destes vértices forem adjacentes em G então eles formam com v um triângulo.
Se, pelo contrário, não houver arestas em G entre quaisquer dois destes 3 vértices então eles são
adjacentes em G e formam, pois, um triângulo em G. 2
Utilizando este teorema podemos provar que se 6 pessoas participam numa festa, então 3
delas conhecem-se mutuamente ou desconhecem-se mutuamente (basta traduzir esta situação
por um grafo com 6 vértices, representando as 6 pessoas, fazendo dois vértices adjacentes se as
pessoas que representam se conhecem).
Embora seja muito conveniente representar um grafo por um diagrama de pontos ligados por
arestas, tal representação pode ser inconveniente se a pretendermos armazenar em computador.
Um modo alternativo de representar um grafo simples é por listagem dos vértices adjacentes a
cada vértice do grafo. Por exemplo, o grafo
w x
v y
66
Estruturas Discretas 3.1. Noções básicas
u: v, w
v: u, w, y
w: v, x, u
x: w, y, v
y: v, x
Contudo as representações mais úteis são as que usam matrizes. Seja G um grafo com vértices
v1 , v2 , . . . , vn . A matriz de adjacência de G é a matriz A = [αij ], de ordem n × n, onde αij é
o número de arestas que ligam o vértice vi ao vértice vj . Se G tiver arestas a1 , a2 , . . . , am , a
matriz de incidência de G é a matriz B = [βij ], de ordem n × m, onde βij = 1 caso aj seja
incidente em vi e βij = 0 caso contrário.
Por exemplo,
0 1 0 1
1 1 1 2
A=
0 1 0 1
1 2 1 0
e
1 0 0 1 0 0 0
1 1 0 0 1 1 1
B=
0 1 1 0 0 0 0
0 0 1 1 1 1 0
são as matrizes de adjacência e de incidência do grafo
v1
v2
v4
v3
Observações. (1) Toda a matriz de adjacência é simétrica. Se o grafo não possuir lacetes então
os elementos da diagonal principal são nulos. No caso do grafo não possuir arestas múltiplas as
entradas da matriz só podem tomar os valores 0 e 1. As matrizes de adjacência representam
de forma completa os grafos, na medida em que é possı́vel recuperar toda a informação sobre
um grafo a partir da sua matriz de adjacência. Toda a matriz de números inteiros positivos,
simétrica, determina um grafo.
(2) Se na matriz de adjacência de um grafo G fizermos uma troca de colunas acompanhada da
respectiva troca de linhas, isso equivale, no grafo G, a renumerar os seus vértices.
67
Estruturas Discretas 3.1. Noções básicas
(3) Uma matriz de incidência de um grafo sem lacetes tem em cada coluna exactamente dois
elementos não nulos. No caso de haver lacetes, a respectiva coluna possui só um elemento não
nulo.
(4) Toda a matriz de elementos no conjunto {0, 1}, tal que em cada coluna há entre um e dois
elementos não nulos, determina um grafo.
v0 , a1 , v1 , a2 , v2 , . . . , vm−1 , am , vm
v0 , a1 , v1 , a2 , v2 , . . . , vm−1 , am , vm
68
Estruturas Discretas 3.1. Noções básicas
Pn
(pois, não havendo arestas múltiplas, aij ∈ {0, 1}) e j=1 aij = g(vi ).
Um grafo bipartido G é um grafo cujo conjunto de vértices admite uma partição em dois
subconjuntos não vazios, V1 e V2 , de tal modo que toda a aresta de G é incidente num elemento
de V1 e noutro de V2 . Se todo o vértice de V1 estiver ligado por uma (e uma só) aresta a cada
vértice de V2 , G diz-se um grafo bipartido completo. Neste caso, se |V1 | = m e |V2 | = n, G
denota-se por Km,n . Se |V1 | = 1, G diz-se uma estrela.
Apresentemos alguns exemplos de grafos bipartidos:
uP
P u $
PP @
PP @
PP
e e Pe
@
e
e
@
@
u u e @u
@ @
@ @
e @e @e
K1,3 K2,3
u e
AA @
@ av v v ! v
Q Q
e A @u AAQa a
Q a A Q
AaQ!!A !
A
!
@
A
A A Q
Q
Aa
! !aQ
Q
A
A f!
!Q
A f
aa QA f
@u e
@ A
K3,3 K4,3
Prova. Seja V (G) = V1 ∪ V2 uma partição de V (G) em dois subconjuntos não vazios, tais que
toda a aresta de G une um elemento de V1 com um de V2 . Consideremos um ciclo v1 v2 . . . vm v1
e suponhamos (sem perda de generalidade) que v1 ∈ V1 . Então todos os vértices de ı́ndice ı́mpar
do ciclo estão em V1 e os de ı́ndice par pertencem a V2 . Como vm tem que estar em V2 , m é
par. 2
69
Estruturas Discretas 3.2. Grafos eulerianos
Recordemos o problema das pontes de Königsberg onde se pergunta se será possı́vel atravessar
cada uma das 7 pontes na figura
exactamente uma vez e voltar ao ponto de partida. Isto é equivalente a perguntar se no grafo
C
D
A
Um grafo diz-se euleriano se admite um caminho fechado sem repetição de arestas, contendo
todas as arestas. Designa-se esse caminho por caminho euleriano.
Portanto a questão que se põe é a de saber se o grafo acima é euleriano. Problemas sobre
grafos eulerianos aparecem frequentemente em passatempos recreativos (um problema tı́pico é
o de saber se determinada figura geométrica pode ser desenhada sem levantar a ponta do lápis
do papel e sem passar por nenhuma linha mais do que uma vez).
Lema. Se G é um grafo no qual o grau de qualquer vértice é pelo menos 2, G contém um ciclo.
Prova. Se G possui lacetes ou arestas múltiplas, o resultado é óbvio. Podemos pois assumir
que G é simples. Seja v um vértice de G e construamos um caminho v v1 v2 . . . , escolhendo v1
entre os vértices adjacentes a v e, para cada i > 1, escolhendo vi+1 entre os vértices adjacentes
a vi diferentes de vi−1 (a existência de tal vértice é garantida pela hipótese). Como G contém
somente um número finito de vértices, teremos que a dada altura ter como única hipótese a
escolha de um vértice que já o tinha sido anteriormente. Se vk for o primeiro destes vértices
então a parte do caminho entre as duas ocorrências de vk é o ciclo requerido. 2
Todo o grafo euleriano é obviamente conexo. O seguinte teorema, demonstrado por Euler
em 1736, permitindo a resolução imediata do problema das pontes de Königsberg, caracteriza
os grafos conexos que são eulerianos.
70
Estruturas Discretas 3.2. Grafos eulerianos
Teorema. [Euler (1736)] Um grafo conexo G é euleriano se e só se o grau de qualquer vértice
de G for par.
Prova. Seja E um caminho euleriano em G. Cada vez que um vértice aparece em E tem duas
arestas incidentes. Como cada aresta ocorre precisamente uma vez em E, o grau de cada vértice
é par.
Provaremos a recı́proca por indução sobre o número de arestas de G. Suponhamos então que
o grau de cada vértice de G é par. O caso em que G não possui arestas é trivial. Portanto, como
hipótese de indução, admitiremos que o resultado é válido se G possuir menos de n arestas e
nessas condições provaremos que o resultado é válido no caso de G possuir n arestas (n ≥ 1).
Como G é conexo, cada vértice terá pelo menos grau 2 e, portanto, pelo Lema, G contém
um ciclo C. Se C contiver todas as arestas de G, a prova está terminada. Senão, removamos
de G todas as arestas de C, formando um novo grafo H, eventualmente desconexo, com menos
arestas que G e no qual todo o vértice continua a ter grau par. Pela hipótese de indução, cada
componente de H possui um caminho euleriano. Como cada componente de H possui pelo
menos um vértice em comum com C (pela conexidade de G) obtemos o caminho euleriano de
G seguindo as arestas de C até um vértice não isolado de H ser alcançado, traçando o caminho
euleriano da componente de H que contêm tal vértice e, de seguida, continuando pelas arestas
de C até encontrar um vértice não isolado pertencendo a outra componente de H, traçando o
caminho euleriano desta, e assim sucessivamente. O processo terminará quando voltarmos ao
vértice inicial. 2
É importante notar que a demonstração do Teorema de Euler nos dá um algoritmo para
construirmos um caminho euleriano num grafo euleriano. O seguinte exemplo mostra-nos como
pode ser utilizada para resolver os tais passatempos com lápis e papel referidos anteriormente.
Exemplo. Será que se consegue desenhar a cimitarra de Mohammed sem levantar a ponta do
lápis do papel e sem passar por nenhum traço mais do que uma vez?
É claro que o Teorema nos diz imediatamente que tal é possı́vel, pois o grau de cada vértice
de G é par. Usando a respectiva demonstração podemos obter um caminho euleriano em G, que
nos diz como realizar tal desenho:
Primeiro consideramos o ciclo
a b d g h j i f e a.
O subgrafo H obtido por remoção das arestas contidas neste ciclo é o grafo
71
Estruturas Discretas 3.2. Grafos eulerianos
cdf gkhiebc
é um caminho euleriano em H. Pondo este circuito no ciclo inicial, no lugar apropriado, produz
o caminho euleriano
abcdf gkhiebdghj if ea :
Ciclo C a b d g h j i f e a
Caminho c d f g k h i e b
euler. em H
Claro que, como as escolhas dos ciclos em cada passo não são únicas, muitas outras soluções
se podem obter. Por exemplo, se tomarmos inicialmente o ciclo i f d c b e i, o subgrafo H é, neste
caso,
72
Estruturas Discretas 3.2. Grafos eulerianos
g h k g
d b a e f g j i h
é um caminho euleriano de G.
A prova do Teorema de Euler pode ser ligeiramente modificada de modo a obtermos o seguinte
resultado:
Corolário. Um grafo conexo é euleriano se e só se o conjunto das suas arestas pode ser parti-
cionado em ciclos.
Prova. Seja G um grafo euleriano. O caso em que G não possui arestas é trivial. Sendo G
conexo e tendo pelo menos uma aresta, todo o seu vértice tem, pelo menos, grau 2. Portanto,
pelo Teorema de Euler, possui um ciclo C1 . Retirando a G as arestas de C1 obtemos um subgrafo
gerador G1 cujos vértices têm ainda todos grau par. Se G1 não tem arestas, está terminada a
demonstração desta implicação. Caso contrário, G1 tem um ciclo C2 e a repetição do argumento
anterior conduz-nos a um grafo G2 , subgrafo gerador de G1 , cujos vértices têm grau par. Se
G2 não tem arestas terminamos, caso contrário repete-se o argumento. E continuamos com este
raciocı́nio sucessivamente até obtermos um grafo Gn totalmente desconexo (isto é, sem arestas).
Aı́ teremos uma partição das arestas de G em n ciclos.
Reciprocamente, suponhamos que o conjunto das arestas de G admite uma partição em
ciclos. Seja C1 um desses ciclos. Se G se reduz a este ciclo então, evidentemente, G é euleriano.
Senão existe outro ciclo C2 da partição, com um vértice comum a C1 . Sejam
C1 ≡ v0 v1 . . . vn ,
com v0 = vn = v, e
C2 ≡ w0 w1 . . . wm
73
Estruturas Discretas 3.2. Grafos eulerianos
Exemplo. O Dominó tem 28 peças. Seguindo a sua regra básica, é possı́vel dispor as 28
peças na mesa, formando um circuito fechado. Isso pode ser comprovado rapidamente com a
ajuda de grafos. Representando cada peça por uma aresta (podemos ignorar os dobles, peças
com igual número de pintas nas duas metades, pois isso é irrelevante para o problema) o grafo
correspondente ao Dominó é o K7 :
74
Estruturas Discretas 3.2. Grafos eulerianos
1 2
0 3
6 4
(Se quisermos considerar os dobles basta acrescentar um lacete a cada vértice.) Como todos
os vértices têm grau par, existe um circuito euleriano. Este facto está na base de um truque
de magia muito conhecido: o Mágico esconde uma peça e entrega as 27 peças restantes a um
voluntário e pede a este que as coloque numa sequência, respeitando a regra básica do Dominó,
sem a mostrar ao Mágico. Este consegue adivinhar as pintas das extremidades de tal sequência!
Porquê? Por exemplo, se o Mágico guardou a peça (3,5), o grafo correspondente às 27 peças
restantes é semi-euleriano, somente com dois vértices de grau ı́mpar: o 3 e o 5. Claro que são
estes os extremos da sequência (caminho semi-euleriano).
1 2
0 3
6 4
75
Estruturas Discretas 3.3. Grafos hamiltonianos
76
Estruturas Discretas 3.3. Grafos hamiltonianos
Mais exemplos:
77
Estruturas Discretas 3.3. Grafos hamiltonianos
Prova. Observemos antes de mais que G é conexo. Se não fosse, teria pelo menos duas compo-
nentes. Suponhamos que uma tinha n1 vértices e a outra n2 , onde n1 + n2 ≥ n. Sendo v um
vértice da primeira componente e w um vértice da outra, v e w não estariam ligados por nenhuma
aresta. Além disso, g(v) ≥ n1 − 1 e g(w) ≥ n2 − 1, pelo que g(v) + g(w) ≥ n1 + n2 − 2 ≥ n − 2,
o que contradiz a hipótese. Portanto G é conexo.
Seja agora C = v1 v2 . . . vr um caminho sem repetição de vértices com o maior comprimento
possı́vel.
é um caminho hamiltoniano:
vi−1 u u v
Q @ i
Q
Q @
vi−2 u Q @u vi+1
Q @
Q @
Q
· ·
· ·
Q
·
Q
Q ·
Q
v2 u @u vn−1
Q
Q@
Q@
Q@
u @u vn
Q
v1 Q
Mostremos que tal vértice terá que existir, o que completará a prova deste caso. Se vn não
estivesse unido a nenhum dos vértices de C imediatamente precedentes a um dos p vértices à
qual v1 está ligado, então os q vértices à qual vn está ligado fariam parte de um conjunto de
(n − 1) − p vértices. Consequentemente (n − 1) − p ≥ q, ou seja, n − 1 ≥ p + q, o que contradiz
o facto p + q ≥ n.
78
Estruturas Discretas 3.3. Grafos hamiltonianos
CASO 2: r < n Suponhamos que v1 está ligado a um vértice v que não é um vértice de C.
Então v v1 v2 . . . vr seria um caminho sem repetição de arestas, de comprimento maior do que
C. Portanto v1 está ligado somente a vértices de C. Analogamente, poderemos concluir que vr
está também ligado somente a vértices de C. Podemos então repetir um raciocı́nio análogo ao
realizado no caso 1 e concluir que existe um ciclo C 0 de comprimento r, v1 v2 . . . vr v1 ou
Corolário. [Dirac (1952)] Seja n ≥ 3. Se G é um grafo simples com n vértices e g(v) > n2
para qualquer vértice v, então G é hamiltoniano. 2
Para terminar recordemos o Problema (A5) da Introdução. Representando cada cela por um
vértice e cada porta por uma aresta obtemos o grafo
B
s s s s s s s s s
s s s s s s s s s
s s s s s s s s s
s s s s s s s s s
s s s s s s s s s
s s s s s s s s s
s s s s s s s s s
s s s s s s s s s
s s s s s s s s s
A
B
s s s s s s s s s
s s s s s s s s s
s s s s s s s s s
s s s s s s s s s
s s s s s s s s s
s s s s s s s s s
s s s s s s s s s
s s s s s s s s s
s s s s s s s s s
A
79
Estruturas Discretas 3.4. Problemas famosos
Os avanços mais importantes da Teoria dos Grafos têm sido motivados, quase sempre, pela
tentativa de resolução de problemas práticos muito especı́ficos — Euler e o problema das pontes
de Königsberg, Cayley e a enumeração de compostos quı́micos, Kirchoff e problemas de redes
eléctricas, etc.
Abordemos sucintamente alguns desses problemas com importância na vida real.
4 6
8
a 1 2 z
2 3
c 10 e
Notemos que noutros problemas, os números no grafo poderão representar, não os compri-
mentos das estradas, mas sim os tempos gastos a percorrê-las ou os custos de as percorrer.
Portanto, possuindo um algoritmo para resolver o problema do caminho mais curto, este algo-
ritmo pode também ser utilizado para determinar o caminho mais rápido, o mais económico,
etc.
Nestes problemas o nosso mapa pode ser visto como um grafo conexo no qual um número
não negativo é atribuı́do a cada aresta. Tais grafos chamam-se grafos com pesos e o número
atribuı́do a cada aresta a chama-se o peso de a.
Existe um algoritmo eficiente, isto é, um procedimento com um número finito de passos que
rapidamente nos conduz à solução. A ideia deste algoritmo consiste em movermo-nos ao longo
do grafo, da esquerda para a direita, associando a cada vértice v um número L(v) indicando a
distância mı́nima entre a e v. Isto significa que, quando chegarmos por exemplo ao vértice d,
L(d) é o menor dos números L(b) + 5 ou L(c) + 8.
Para aplicar o algoritmo começamos por definir L(a) = 0 e damos a b, c, d, e as etiquetas
temporárias L(b) = L(c) = L(d) = L(e) = ∞. Em seguida consideramos os vértices adjacentes
a a. O vértice b fica com a etiqueta temporária L(a) + 4 = 4 e o vértice c com L(a) + 2 = 2.
Consideramos a menor destas, que será a etiqueta definitiva de c: L(c) = 2. Em seguida
consideramos os vértices adjacentes a c ainda não etiquetados definitivamente. O vértice e fica
etiquetado com L(c) + 10 = 12, o vértice d com L(c) + 8 = 10 e podemos descer a etiqueta de b
para L(c) + 1 = 3. A menor destas etiquetas é agora 3 (em b). Será esta a etiqueta permanente
de b. Agora consideramos os vértices adjacentes a b. O vértice d desce a sua etiqueta temporária
para L(b) + 5 = 8. A menor das etiquetas temporárias é agora 8 (em d). Escreveremos então
L(d) = 8. Continuando deste modo, obtemos sucessivamente as etiquetas permanentes L(e) = 10
e L(z) = 13. Portanto o caminho mais curto entre a e z mede 13, que é o caminho a c b d e.
Resumindo:
80
Estruturas Discretas 3.4. Problemas famosos
4 (a) ∞
∞ ∞ b 5 d
u u
b 5 d
u u 4 @ 6
@
4 a u 1 2 @uz ∞
@ 6 8
@ 0
0 a u 1 2 @uz ∞
8 @
2@ 3
@ @u u
2@ 3 c e
@u u 10
c 10 e 2 (a) ∞
∞ ∞
3 (a, c) 8 (a, c, b)
b 5
d
u u
4 @ 6
@
a u 1
0
8
2 @u
z 13
@ (a, c, b, d, e)
2@ 3
@u u
c 10
e
2 (a) 10 (a, c, b, d)
Este algoritmo deve-se a Dijkstra (1959) e a sua formulação geral diz o seguinte:
81
Estruturas Discretas 3.4. Problemas famosos
Algoritmo de Dijkstra (1959). Determinação do caminho mais curto do vértice v1 aos outros
vértices do grafo, onde os comprimentos das arestas são positivos:
1. Faça
Comprimento da aresta vi vj
caso ela exista
c(vi , vj ) =
∞ caso contrário
3. Enquanto vn 6∈ S faça
Existem muitas variantes deste algoritmo para aplicação, por exemplo, aos digrafos, à deter-
minação do caminho mais longo, etc.
82
Estruturas Discretas 3.4. Problemas famosos
pode ser obtido, como vimos, pelo algoritmo do Teorema de Euler. Se o grafo não for euleriano,
o problema é muito mais complicado, embora se conheça um algoritmo eficiente para o resolver,
que não apresentaremos aqui. A ideia é acrescentar a G cópias de algumas das suas arestas de
modo a obter um multi-grafo que tenha um caminho euleriano. Assim, o problema de determinar
o trajecto óptimo para o carteiro é equivalente à determinação do menor número de cópias de
arestas de G a juntar a G de maneira a obter um multigrafo com um caminho euleriano.
D 9 C
5 8 3 7
4 8
E B
6
6 2
12 Este problema do caixeiro-viajante é um exemplo de problema que tem desafiado os investigadores na procura
de um bom algoritmo. Pertence a uma classe de problemas conhecidos como NP-completos ou NP-difı́ceis, para os
quais não se acredita ser possı́vel encontrar um algoritmo de complexidade polinomial. Uma das actividades mais
importantes na Matemática Discreta é a procura de algoritmos eficientes que forneçam uma boa aproximação da
solução óptima destes problemas. É o que acontece com o problema do caixeiro-viajante para o qual já existem
alguns algoritmos heurı́sticos que fornecem rapidamente uma solução aproximada.
83
Estruturas Discretas 3.5. Árvores
3.5. Árvores
u
XXXXX
XXX
u u Xu
XXX
@ @ @
@ @ @
u @u u @u u @u
A A A A A A
A A A A A A
u
u Au u u Au u u Au u u Au u
u Au u
u Au
Nikolaus
(1623-1708)
PP
PP
PP
P P
P
Jacob I Nikolaus Johann I
(1654-1705) (1662-1716) (1667-1748)
HH
HH
H
Nikolaus I Nikolaus II Daniel Johann II
(1687-1759) (1695-1726) (1700-1782) (1710-1790)
@
@
@
Johann III Jackob II
(1746-1807) (1759-1789)
84
Estruturas Discretas 3.5. Árvores
Outros exemplos de árvores são dados por algumas moléculas orgânicas — os vértices repre-
sentando os átomos e as arestas as ligações entre eles:
tH
tH H t t tH
C
H
H t tC tH t
H t tC tH H t tC tC tH
H t tC tH t
H
H t tC tH H t tC tH
tH tH
A. Cayley foi o primeiro a estudar árvores de modo sistemático13 . Mais tarde14 , aplicou esse
estudo à quı́mica orgânica, mostrando a sua utilidade na enumeração de compostos quı́micos.
Esta enumeração conduziu-o à descoberta de compostos desconhecidos.
A figura seguinte contém todas as árvores estruturalmente diferentes (ou seja, não isomorfas)
com 1, 2, 3, 4, 5 e 6 vértices.
t
t t t
t t t t t t t t
A
A
t t t At t t t t t
t t t t t t t t
13 Nos artigos [A. Cayley, On the theory of the analytical forms called trees, Philosophical Magazine 13 (1857)
172-176] e [A. Cayley, On the theory of the analytical forms called trees, part II, Philosophical Magazine 18
(1859) 374-378].
14 Nos artigos [A. Cayley, On the mathematical theory of isomers, Philosophical Magazine 47 (1874) 444-446] e
[A. Cayley, On the analytical forms called trees, with applications to the theory of chemical combinations, Rep.
Brit. Advance Sci. 45 (1875) 257-305].
85
Estruturas Discretas 3.5. Árvores
t t t
t t t t t t
t t t t t t t t t t
t t t t t t t t t
A
t t t t t t At
A
(6)
Como veremos, as árvores têm “boas” propriedades. Muitas vezes, na tentativa de provar
um resultado geral para grafos, começa-se por tentar prová-lo para árvores. De facto, existem
muitas conjecturas que ainda não foram provadas para grafos arbitrários mas que já se sabe
serem verdadeiras para as árvores.
Em qualquer grafo conexo, dados dois vértices arbitrários distintos, existe sempre um ca-
minho sem repetição de vértices ligando-os. O resultado seguinte diz-nos que as árvores são
precisamente os grafos conexos nos quais cada par de vértices distintos está ligado por exacta-
mente um caminho sem repetição de vértices:
Teorema 1. Um grafo simples G é uma árvore se e só se quaisquer dois vértices de G estão
ligados por um único caminho sem repetição de vértices.
Prova. Seja G uma árvore e sejam x e y dois vértices de G. Como G é conexo, existe um caminho
sem repetição de vértices que os liga. Resta provar que este caminho é único. Se existisse outro
caminho, o caminho formado pela combinação do primeiro, de x para y, com o caminho de y
para x obtido seguindo o segundo caminho na direcção de y para x, formaria um ciclo, o que
seria uma contradição.
Reciprocamente, suponhamos que existe um único caminho sem repetição de vértices unindo
quaisquer dois vértices de G. Então G é claramente conexo. Além disso, não poderá ter ciclos:
se contivesse um ciclo, contendo os vértices x e y, existiriam evidentemente dois caminhos sem
repetição de vértices unindo x a y (pois qualquer ciclo que passe por x e y é constituı́do por dois
caminhos sem repetição de vértices, um unindo x a y, o outro unindo y a x). 2
Fixando um vértice qualquer r de uma árvore é possı́vel, usando o teorema anterior, dar uma
direcção a todas as arestas do seguinte modo: como existe um único caminho de r para cada um
dos restantes vértices do grafo, direccionamos cada aresta usando esses caminhos. Por exemplo,
na árvore
86
Estruturas Discretas 3.5. Árvores
r t t
tH
HHt
A
At t
A
t
6
r t -t
t
Ht
Y
H H ?
A
t -t
AAU
Este grafo dirigido diz-se uma árvore com raiz r. Outra escolha de raiz produzirá uma outra
árvore com raiz:
t t
6
t t t -t
t t 6
Ht s
HH
Ht s
Y
H H
A A
At t
A
t -t
AAU
Prova. Fixando um vértice qualquer r, e construindo a respectiva árvore com raiz r, é evidente
que existe uma correspondência bijectiva entre as arestas da árvore e os vértices diferentes de r
(a cada seta corresponde o respectivo vértice terminal). Como há n − 1 vértices diferentes de r,
a árvore tem n − 1 arestas. 2
87
Estruturas Discretas 3.5. Árvores
Sabemos pelo Lema dos apertos de mão (Proposição 1 da Secção 2.1) que a soma dos graus
dos vértices de um grafo é o dobro do número das arestas. Se G for uma árvore com vértices
v1 , v2 , . . . , vn e m arestas, então m = n − 1 pelo Teorema 2. Logo
n
X
g(vi ) = 2m = 2(n − 1).
i=1
Consequentemente, no caso de G não ser K1 , como não existem vértices isolados, existem pelo
menos dois vértices de grau 1. Podemos assim afirmar que toda a árvore diferente de K1 possui
pelo menos dois vértices de grau 1.
Teorema 3. Uma árvore m-ária plena com i vértices internos possui n = m i + 1 vértices.
Prova. Todo o vértice, com excepção da raiz, é descendente de um vértice interno. Como cada
um dos i vértices internos tem m descendentes, existem m i vértices na árvore além da raiz.
Assim, no total existem m i + 1 vértices. 2
88
Estruturas Discretas 4.1. Aritmética modular
4. Números inteiros
Se eu escrever
11 + 22 = 9
11 + 22 = 33 ou 11 + 22 = 9 ?
mas quando calculamos as horas, 11 + 22 = 9. Portanto, a aritmética que usamos para calcular
as horas é uma aritmética um pouco diferente da habitual, na qual 24 conta como zero, isto
é, 24 = 0. Esta aritmética chama-se aritmética módulo 24. Para a distinguir da aritmética
habitual escrevemos
11 +24 22 =24 9.
O quociente é 10 e o resto é 2.
Definição. Dados dois inteiros m e n, diz-se que r é o resto da divisão inteira de n por m, e
denota-se por r = n mod m, se 0 ≤ r < |m| e n = q × m + r para algum inteiro q. No caso
particular em que r = 0, diz-se que m divide n e escreve-se m | n.
> 23 mod 7
para obtermos
15 [Link]
89
Estruturas Discretas 4.1. Aritmética modular
Portanto
n = 3469016345521790021102382940567489953,
a +n b = (a + b) mod n, a ×n b = (a × b) mod n.
É esta a chamada aritmética modular16 nos inteiros.
16 Para mais informação e manipulação destas operações no caso 1 ≤ n ≤ 10 vá a [Link]/mat/
90
Estruturas Discretas 4.1. Aritmética modular
(a +n b) +n c = a +n (b +n c)
(a ×n b) ×n c = a ×n (b ×n c)
a ×n (b +n c) = (a ×n b) +n (a ×n c).
Mas a particularidade da aritmética módulo n é que algumas vezes um inteiro a pode ter
um inverso a1 que é ainda um inteiro! Isto é, para um determinado número a módulo n, pode
existir um número b módulo n tal que
a ×n b = 1.
• a ≡n a (reflexiva).
• Se a ≡n b então b ≡n a (simétrica).
• Se a ≡n b e b ≡n c então a ≡n c (transitiva).
(C2) Se a ≡n b e c ≡n d então a + c ≡n b + d.
(C3) Se a ≡n b e c ≡n d então a × c ≡n b × d.
Aplicações.
(1) Códigos. Com esta aritmética temos já uma maneira simples de codificar e descodificar
uma informação! Efectivamente, podemos multiplicar por 7 módulo 10 para codificar a in-
formação e depois, multiplicar por 3 módulo 10 para descodificar. Fazer estas duas operações
consecutivamente corresponde exactamente a multiplicar por 1 módulo 10, isto é, não fazer nada!
Recuperamos assim a informação inicial!
91
Estruturas Discretas 4.1. Aritmética modular
Como x9 = x0 e cada termo na sequência só depende do anterior, a sequência terá nove
números diferentes antes de se começar a repetir:
3, 7, 8, 6, 1, 2, 0, 4, 5, 3, 7, 8, 6, 1, 2, 0, 4, 5, 3, . . .
A maioria dos computadores usa este método para gerar números pseudo-aleatórios. Por
exemplo, é muito utilizado o sistema módulo m = 231 − 1 com incremento c = 0 e multiplicador
a = 75 = 16 807, que permite gerar 231 − 2 números antes que a repetição comece.
(3) Cálculo do máximo divisor comum. O algoritmo mais antigo que se conhece, e que
aparece no livro VII dos Elementos de Euclides (c. 325 a.C. - 265 a.C.), calcula o máximo divisor
comum mdc(a, b) de dois inteiros a e b.
92
Estruturas Discretas 4.1. Aritmética modular
252 = 54 × 4 + 36
54 = 36 × 1 + 18
36 = 18 × 2 + 0
∴ mdc(252, 54) = 18
Não se trata de uma coincidência: não é difı́cil provar que, seguindo este procedimento para
quaisquer outro par de inteiros positivos, o último resto não nulo é sempre igual a mdc(a, b).
Este é o algoritmo de Euclides:
A B C D E F G H I J L M N O P Q R S T U V X Z
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
D E F G H I J L M N O P Q R S T U V X Z A B C
Este sistema de encriptação pode ser descrito matematicamente de forma muito abreviada:
substituı́mos cada letra por um inteiro de 0 até 22, baseado na sua posição no alfabeto:
17 A criptografia é a parte da criptologia (ciência dos códigos) que se dedica ao estudo de mensagens secretas e
93
Estruturas Discretas 4.1. Aritmética modular
A B C D E F G H I J L M
0 1 2 3 4 5 6 7 8 9 10 11
N O P Q R S T U V X Z
12 13 14 15 16 17 18 19 20 21 22
Portanto o método de César é definido pela função f que aplica cada inteiro n, 0 ≤ n ≤ 22, no
inteiro
f (n) = (n + 3) mod 23.
Por exemplo,
X←→ 21
↓
f (21) = 24 mod 23 = 1 ←→ B.
Teste. Como fica a mensagem “DESCOBRI A SOLUCAO” depois de encriptada pela cifra de
César ?
É claro que a cifra de César é um método de encriptação muito pouco seguro. Podemos melhorá-
-lo um pouco definindo, mais geralmente, f (n) = (an + b) mod 23, com a e b inteiros escolhidos
de modo a garantir que f é uma bijecção.
Teste. Que letra substitui J com a função encriptadora f (n) = (7n + 3) mod 23 ?
∗PIBE∗ ^ D ^ W@P
(onde o sı́mbolo ^ indica um espaço em branco) que foi encriptada utilizando o alfabeto da
figura seguinte e a função f (p) = (22p + 25) mod 29.
A B C D E F G H I J K L M N O P Q R S T U V X Y Z W ∗ @ ^
l l l l l l l l l l l l l l l l l l l l l l l l l l l l l
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
Números primos.
Quais são os elementos de Zn , chamados invertı́veis, que têm inverso relativamente à operação
×n ? Estes elementos estão intimamente ligados aos números primos.
94
Estruturas Discretas 4.1. Aritmética modular
Definição. Um natural p ≥ 2 diz-se primo quando, para qualquer natural n, se n divide p então
n = 1 ou n = p.
> prime(23)
Os números primos têm um papel fundamental relativamente aos outros números naturais
por causa do seguinte resultado:
95
Estruturas Discretas 4.1. Aritmética modular
Definição. Dois naturais m e n dizem-se primos entre si se mdc(m, n) = 1 (diz-se também que
m é coprimo de n).
Podemos agora caracterizar facilmente os elementos de Zn que são invertı́veis para a multi-
plicação ×n :
Prova. “⇒”: ab ≡n 1 significa que ab = nq + 1, isto é, ab − nq = 1, para algum inteiro q. Então,
se d é um divisor comum de a e n, será um divisor de ab − nq = 1, pelo que necessariamente
d = 1 ou d = −1. Isto mostra que mdc(a, n) = 1.
“⇐”: Se mdc(a, n) = 1 então, pelo algoritmo de Euclides (usado em ordem inversa — ver
exemplo na página seguinte), existem inteiros s e t tais que 1 = sa+tn, ou seja, sa = n×(−t)+1,
o que mostra que sa ≡n 1. Consequentemente, todos os números da forma s + kn (k ∈ Z) são
solução da equação xa ≡n 1 e um deles pertence necessariamente a Zn . Esse será o inverso de
a em Zn . 2
1 ×5 1 = 1, 2 ×5 3 = 1, 3 ×5 2 = 1, 4 ×5 4 = 1.
96
Estruturas Discretas 4.1. Aritmética modular
φ:N → N
n 7→ #{m : m ≤ n e m é coprimo de n}
cujos valores podemos calcular com o WolframAlpha, recorrendo à função totient ou phi:
> phi(107)
106
> phi(106)
52
Portanto, em Z107 há 106 elementos invertı́veis e em Z106 só há 52.
Acabámos de obter uma solução para as congruências do tipo ax ≡n 1. Mais geralmente:
27 = 10 × 2 + 7
10 = 7×1+3
7 = 3×2+1
Portanto mdc(10, 27) = 1. Agora invertamos o processo para encontrar inteiros s e t tais que
1 = 10s + 27t:
1 = 7−3×2
= 7 − (10 − 7 × 1) × 2
= 7 × 3 − 10 × 2
= (27 − 10 × 2) × 3 − 10 × 2
= 10 × (−8) + 27 × 3.
97
Estruturas Discretas 4.2. Criptografia: o sistema RSA de chave pública
Teorema de Fermat-Euler.19
Os resultados sobre os inteiros que acabámos de estudar estão na base de toda a criptografia
actual, que permite a troca de mensagens confidenciais por intermédio de um canal público,
supondo que os agentes comunicantes, digamos a Alice e o Bruno, não partilham segredo nenhum.
Se a Alice quiser enviar uma mensagem x ao Bruno, pede-lhe para ele gerar um par de chaves,
uma chave pública u (conhecida por toda a gente) e uma chave privada v (conhecida apenas pelo
Bruno). As chaves u e v são aplicações do espaço das mensagens para o espaço das mensagens
e, para que o sistema funcione bem e permita manter o secretismo na comunicação, devem ter
as seguintes propriedades:
98
Estruturas Discretas 4.2. Criptografia: o sistema RSA de chave pública
Será de facto um bom sistema, isto é, satisfaz as propriedades (P1) e (P2) ?
Os conceitos e resultados relativos aos números inteiros apresentados nesta secção permitem-
nos verificar a propriedade (P1), como veremos mais adiante. Quanto à propriedade (P2), a sua
confirmação é ainda hoje um problema em aberto20 .
Este sistema permite enviar mensagens encriptadas por uma chave pública a, mas para
desencriptar a mensagem o receptor precisa de ter uma chave privada b (só do seu conhecimento).
Sejam
p e q primos, n = pq, m = (p − 1)(q − 1).
A B C D E F G H I J L M
00 01 02 03 04 05 06 07 08 09 10 11
N O P Q R S T U V X Z
12 13 14 15 16 17 18 19 20 21 22
O inteiro x daı́ resultante é depois transformado, com a ajuda da chave pública a, num inteiro
u(x) = xa mod n.
Teste. Codifique a mensagem HELP usando o sistema RSA com p = 43, q = 59 e a = 13.
20 Trata-se de um dos problemas em aberto mais importantes da matemática, com grandes implicações práticas:
até hoje, ninguém conseguiu demonstrar se o sistema RSA verifica a propriedade (P2), apesar de todos os
especialistas conjecturarem que isso seja verdadeiro. Portanto, toda a criptografia actual assenta, não numa
certeza absoluta, mas numa conjectura.
99
Estruturas Discretas 4.2. Criptografia: o sistema RSA de chave pública
Solução. Neste sistema n = 43 × 59 = 2537. Note que, como 13 é primo, mdc(13, 42 × 58) =
1. Traduzindo as letras no seu valor numérico, H→07, E→04, L→10 e P→14. A mensagem
corresponde então ao número x = 07041014. Se aplicarmos já a chave pública u a x obtemos
uma mensagem só com quatro algarismos: u(x) = 0704101413 mod 2537 = 1507. Para manter o
número de algarismos na mensagem encriptada, como n = 2537 tem quatro algarismos, agrupam-
-se os algarismos de x em blocos de quatro e só depois se aplica u a cada um desses blocos21 :
u
0704 −→ 70413 mod 2537 = 0981,
u
1014 −→ 101413 mod 2537 = 1175.
O receptor quando recebe a mensagem desencripta-a com a ajuda da chave privada b que só
ele conhece:
v(u(x)) = u(x)b mod n.
Teste. Descodifique a mensagem seguinte, recebida usando o sistema RSA do exemplo anterior:
2128 2431.
Solução. Temos que resolver a congruência 13b ≡42×58 1 para determinar a chave privada b:
42 × 58 = 2436 = 13 × 187 + 5
13 = 5×2+3
5 = 3×1+2
3 = 2×1+1
donde
1 = 3−2×1
= 3 − (5 − 3 × 1)
= 3×2−5
= (13 − 5 × 2) × 2 − 5
= 13 × 2 − 5 × 5
= 13 × 2 − (2436 − 13 × 187) × 5
= 13 × (2 + 187 × 5) − 2436 × 5
= 13 × 937 − 2436 × 5.
Portanto b = 937. Então 2128b mod 2537 = 2128937 mod 2537 = 1718 e 2431b mod 2537 =
2431937 mod 2537 = 1314, pelo que a mensagem original é, na versão numérica, 1718 1314, ou
seja STOP.
21 Portanto, deveremos ter o cuidado de ter sempre x < n.
100
Estruturas Discretas 4.2. Criptografia: o sistema RSA de chave pública
Já sabemos como encriptar e desencriptar mensagens no sistema RSA. Falta assegurar, como
tı́nhamos anunciado, que o RSA satisfaz a propriedade (P1), isto é, que a desencriptação v é de
facto inversa da encriptação u:
Prova. Uma vez que v(u(x)) = v(xa mod n) = (xa mod n)b mod n = xab mod n, e ab =
k(p − 1)(q − 1) + 1 para algum inteiro k, temos
Mas como x é menor do que p e q, não é divisı́vel por p e q logo, pelo Teorema de Fermat-Euler
(b), (x(p−1)(q−1) )k mod n = 1. Portanto v(u(x)) = x mod n = x. 2
Basta assim usarmos mensagens com número x inferior a p, q para termos a certeza que a
função de desencriptação v recupera a mensagem original.
Como é que o processo de troca de mensagens secretas entre a Alice e o Bruno se desenrola
na realidade? O Bruno, o receptor, faz o seguinte:
A Alice tem agora os elementos para encriptar as suas mensagens com a função u e enviá-las
ao Bruno. Como só este conhece o valor de b, só ele poderá decifrar a mensagem aplicando a
função v.
E que trabalho tem que fazer uma terceira pessoa mal intencionada, que conhece só a função
de encriptação, para desencriptar uma mensagem?
101
Estruturas Discretas 4.2. Criptografia: o sistema RSA de chave pública
operações.
Quando uma terceira pessoa mal intencionada conhece n = pq, sabendo que p e q são números
primos de 80 algarismos, tem que dividir n por todos os números de 80 algarismos para descobrir
os factores p, q. Há 1080 números de 80 algarismos ou menos, e 1079 números de 79 algarismos
ou menos. Então há
1080 − 1079 = 1079 (10 − 1) = 9 × 1079
9 × 1079 9
40
= × 1038 ≈ 2, 4 × 1037
370 × 10 37
vezes mais difı́cil do trabalho do Bruno. Isto significa que se o computador do Bruno gastar um
segundo a encontrar os primos p, q, um computador do mesmo tipo tem que trabalhar durante
aproximadamente 1037 segundos para quebrar o código. É muito tempo?
A Terra tem cerca de [Link] anos, ou seja,
102
Estruturas Discretas 4.2. Criptografia: o sistema RSA de chave pública
Exemplo. O Bruno começa por procurar dois primos grandes p e q, por exemplo com 80 alga-
rismos. No WolframAlpha com qualquer expressão próxima de random integer (n) obtemos
um inteiro aleatório r com 80 algarismos e depois next prime (r) calcula o menor primo maior
do que o inteiro r:
r : 19669081321110693270343633073697474256143563558458718976746753830538032062222085
p : 19669081321110693270343633073697474256143563558458718976746753830538032062222257
s : 74121768604305613921745580037409259811952655310075487163797179490457039169594160
q : 74121768604305613921745580037409259811952655310075487163797179490457039169594213
A selecção primeiro de dois inteiros aleatórios r e s tem a intenção de tornar mais difı́cil de
adivinhar os primos p e q. Em seguida, o Bruno calcula n = pq e m = (p − 1)(q − 1).
> pxq
n : 14579070943426365719341081596858629803265159149118248616433975229804975507362306
15496046802186876835611836753440525199587698019954839165932427842278373706998741
Este valor de n com 160 algarismos permite encriptar mensagens até 80 letras num só bloco.
> (p-1)x(q-1);
m : 14579070943426365719341081596858629803265159149118248616433975229804975507362305
21705196876770569643522623642333791131491479151420633025388494521283302475182272
Em seguida, decide a escolha de a. Como será um valor público, não se preocupa em gerar
números aleatoriamente. A única preocupação é que satisfaça mdc(a, m) = 1. Por exemplo,
pode fazer a = 216 + 1 = 65537. Depois calcula b tal que ab ≡m 1:
103
Estruturas Discretas 4.2. Criptografia: o sistema RSA de chave pública
b : 34180298922096847472065507840720943425419102236324807359431775852717312155060777
8293183240178522095499109087453784896094825475099226794560236481979918863102913
y : 44669982652857045772784970284788245601106395884543657540636484577393488318578590
4969215738362722324430978629195687422700096164664107349103915395164169538874261
Solução.
> 1445271342077333850810587930721246119637276300086542923991011323094820
8915317126596566680325137342547829329336431874588144606598803386096533964035759
67077856790^b mod(n)
417181903041104171816191819160017030817021604180017
Como o primeiro par de algarismos, 41, não corresponde a nenhuma letra (ver tabela da
página 94), o par original deverá ser 04 (o WolframAlpha não escreveu o 0), ou seja, é a letra E.
Continuando, 17→S, 18→T, 19→U, etc. A mensagem original é
“ESTUDEMESTRUTURASDISCRETAS”.
Observe que, em geral, no sistema RSA assume-se que quase tudo é do conhecimento público,
incluindo a forma da função encriptadora. Isto significa que um intruso que intersecta uma
mensagem RSA sabe que esta foi formada com a função u(x) = xa mod n, e conhece os valores
a e n. A vantagem desta informação ser pública reside no facto da Alice e do Bruno para
comunicarem entre si numa linha de comunicação insegura não precisarem de pensar numa
maneira de trocarem entre si secretamente o expoente de encriptação a e o módulo n. Só a
chave privada b nunca pode circular entre ambos pelo canal de comunicação, para que não possa
ser interceptada.
Leituras suplementares. (1) Até agora utilizámos um método muito simples de con-
versão de letras em números, que representa A pelo número 0, B pelo número 1, etc., até Z. Este
104
Estruturas Discretas 4.2. Criptografia: o sistema RSA de chave pública
método tem uma desvantagem óbvia: não funciona conjuntamente com maiúsculas e minúsculas,
com espaços, acentos e outros caracteres. Existe um método muito utilizado de conversão de
caracteres no código ASCII, usado pela maioria dos computadores, permitindo a conversão de
cadeias de caracteres alfanuméricos em inteiros e vice-versa. No WolframAlpha e Mathematica
a instrução é
ToCharacterCode[“xxx”]
[66, 111, 109, 32, 100, 105, 97, 44, 32, 97, 32, 118, 111, 115, 115, 97, 32, 109, 105, 115, 115, 227,
111, 32, 112, 97, 114, 97, 32, 104, 111, 106, 101, 32, 233, 32, 99, 111, 100, 105, 102, 105, 99, 97,
114, 32, 101, 115, 116, 97, 32, 109, 101, 110, 115, 97, 103, 101, 109, 46]
Em sentido inverso:
> convert {66, 111, 109, 32, 100, 105, 97, 44, 32, 97, 32, 118, 111, 115, 115,
97, 32, 109, 105, 115, 115, 227, 111, 32, 112, 97, 114, 97, 32, 104, 111, 106,
101, 32, 233, 32, 99, 111, 100, 105, 102, 105, 99, 97, 114, 32, 101, 115, 116,
97, 32, 109, 101, 110, 115, 97, 103, 101, 109, 46} to characters
(2) O sistema RSA tem resistido a ataques de criptoanalistas, à custa do aumento da dimensão
das chaves, mas é necessário ir acompanhando os desenvolvimentos mais recentes. Apesar da
matemática subjacente ser há muito conhecida, a cifra RSA surgiu apenas nos anos 70 por-
que é aplicável apenas com números primos de grande dimensão e só nos anos 70 apareceram
computadores potentes de custo aceitável. Ataques mais conhecidos em 2006:
• Em computação paralela são conhecidos ataques até 640 bits (actualmente recomenda-
-se o uso de números RSA-1024, ou RSA-2048)25 .
105
Estruturas Discretas 4.2. Criptografia: o sistema RSA de chave pública
Exemplo. n := 408508091.
Demorou 2099 passos, e n só tem 9 algarismos! Imagine RSA-640 com 193 algarismos decimais...
• Primeiro prémio (100 dólares) atribuı́do em Abril 1994, pela factorização de números RSA-
129.
• O prémio mais elevado (20 000 dólares) foi ganho em Novembro 2005 na factorização do
RSA-640
31074182404900437213507500358885679300373460228427275457201619488232064405
18081504556346829671723286782437916272838033415471073108501919548529007337
724822783525742386454014691736602477652346609
163473364580925384844313388386509085984178367003309231218111085238933310010
4508151212118167511579
190087128166482211312685157393541397547189678996851549366663853908802710380
2104498957191261465571
Os cálculos foram efectuados durante 540 dias por um conjunto de 80 AMD64 Opteron
(CPU que equipa cerca de 10% dos supercomputadores mais rápidos do mundo).
74037563479561712828046796097429573142593188889231289084936232638972765034028266
27689199641962511784399589433050212758537011896809828673317327310893090055250511
6877063299072396380786710086096962537934650563796359
26 [Link]/rsalabs/[Link]?id=2093.
106
Estruturas Discretas 4.2. Criptografia: o sistema RSA de chave pública
terá 20 valores à disciplina e pode candidatar-se ao prémio de 30 000 dólares da RSA Security.
DMUC: 26986751662544233897390996989562786998209640195002153770034468141230169
50163931124306976585375250715400911398515483295152423812242464904341510349824376
57607908609525327637173783415854826421482431563077009840890804022964491227968726
58542504958657945923684483016763566353046590571882008173675016517836292426828436
78677672254248775317520385
107
Estruturas Discretas 5.1. Técnicas básicas
5. Contagem
Neste capı́tulo começaremos por abordar os dois princı́pios gerais, intuitivamente claros, que
fundamentam os raciocı́nios básicos que se fazem na resolução de problemas elementares de
contagem.
O princı́pio fundamental da contagem (chamado princı́pio da multiplicação) diz que se há p
maneiras de fazer uma escolha E1 e, feita a escolha E1 , há q maneiras de fazer a escolha E2 ,
então o número de maneiras de fazer sucessivamente as escolhas E1 e E2 é p × q.
Mais geralmente:
Exemplo. O menu de um restaurante apresenta duas entradas, três pratos principais e duas so-
bremesas. Quantas ementas diferentes (com uma entrada, um prato principal e uma sobremesa)
podemos escolher?
Num problema tão simples podemos esquematizar as várias possibilidades e contá-
-las; se designarmos por E = {e1 , e2 } o conjunto das entradas, por P = {p1 , p2 , p3 } o con-
junto dos pratos principais e por S = {s1 , s2 } o conjunto das sobremesas, o seguinte quadro
mostra os resultados possı́veis:
e1 e2
p1 p2 p3 p1 p2 p3
s1 s2 s1 s2 s1 s2 s1 s2 s1 s2 s1 s2
109
Estruturas Discretas 5.1. Técnicas básicas
Por outro lado, é evidente que o número de maneiras diferentes de escolher uma entrada
ou um prato principal ou uma sobremesa é igual a 2 + 3 + 2 = 7. Este raciocı́nio é um caso
particular do chamado Princı́pio da Adição:
Teste 1. Uma bandeira é formada por 7 listras que devem ser coloridas usando apenas as cores
verde, amarela e vermelha. Se cada listra deve ter apenas uma cor e não se pode usar cores
iguais em listras adjacentes, de quantas maneiras se pode colorir a bandeira?
Solução. Colorir a bandeira equivale a escolher a cor de cada listra. Há 3 maneiras de escolher
a cor da primeira listra e, a partir daı́, 2 maneiras de escolher a cor de cada uma das outras 6
listras. Portanto a resposta é 3 × 26 = 192.
Solução. O primeiro algarismo pode ser escolhido de 9 maneiras, pois não pode ser igual a
0. O segundo algarismo pode ser escolhido de 9 maneiras, pois não pode ser igual ao primeiro
algarismo. O terceiro algarismo pode ser escolhido de 8 maneiras, pois não pode ser igual ao
primeiro e segundo algarismos. A resposta é 9 × 9 × 8 = 648.
Estes exemplos mostram-nos qual deve ser a estratégia para resolver problemas de contagem.
Citando Elon Lages Lima27 :
(1) Postura. Devemos sempre colocar-nos no papel da pessoa que deve fazer a acção solicitada
pelo problema e ver que decisões devemos tomar. No Teste 2, colocámo-nos no papel da pessoa
que deveria escrever o número de três algarismos; no Teste 1, colocámo-nos no papel da pessoa
que deveria colorir a bandeira.
27 A matemática do ensino médio, Sociedade Brasileira de Matemática, 2000.
110
Estruturas Discretas 5.1. Técnicas básicas
(2) Divisão. Devemos, sempre que possı́vel, dividir as decisões a serem tomadas em decisões
mais simples. Colorir a bandeira foi dividido em colorir cada listra; formar um número de três
algarismos foi dividido em escolher cada um dos três algarismos.
(3) Não adiar dificuldades. Pequenas dificuldades adiadas costumam transformar-se em grandes
dificuldades. Se uma das decisões a serem tomadas for mais restrita que as demais, essa é a
decisão que deve ser tomada em primeiro lugar. No Teste 2, a escolha do primeiro algarismo é
uma decisão mais restrita do que as outras, pois o primeiro algarismo não pode ser igual a 0.
Essa é portanto a decisão que deve ser tomada em primeiro lugar; adiá-la só serve para causar
problemas. Com efeito, começando a escolha dos algarismos pelo último, há 10 maneiras de
escolher o último algarismo. Em seguida, há 9 maneiras de escolher o algarismo central, pois
não podemos repetir o algarismo já usado. Agora temos um impasse: de quantas maneiras
podemos escolher o primeiro algarismo? A resposta é “depende”. Se antes não tivermos usado
o zero, haverá 7 maneiras de escolher o primeiro algarismo, pois não poderemos usar nem o zero
nem os dois algarismos já usados; se já tivermos usado o zero, haverá 8 maneiras de escolher
o primeiro algarismo. Isto mostra como algumas pessoas conseguem, por erros de estratégia,
tornar complicadas as coisas mais simples.
Solução. Há 5 maneiras de escolher o último algarismo. Note que começamos pelo último
algarismo, que é o mais restrito; o último algarismo só pode ser 0,2,4,6 ou 8. Em seguida, vamos
ao primeiro algarismo. De quantas maneiras se pode escolher este algarismo? A resposta é
“depende”: se não tivermos usado o 0, haverá 8 maneiras de escolher o primeiro algarismo, pois
não poderemos usar nem o 0 nem o algarismo já usado na última posição; se já tivermos usado
o 0, haverá 9 maneiras de escolher o primeiro algarismo, pois apenas o 0 não poderá ser usado
na primeira posição.
Este tipo de impasse é comum na resolução de problemas e há dois métodos para ultrapassá-
-lo. O primeiro método consiste em voltar atrás e contar separadamente os números que termi-
nam em 0 e os que não terminam em 0. Comecemos pelos que terminam em 0. Há uma maneira
de escolher o último algarismo, 9 maneiras de escolher o primeiro e 8 maneiras de escolher o
algarismo central. Há assim 1 × 9 × 8 = 72 números terminados em 0. Para os que não termi-
nam em 0, há 4 maneiras de escolher o último algarismo, 8 maneiras de escolher o primeiro e 8
maneiras de escolher o algarismo central. Há pois 4 × 8 × 8 = 256 números que não terminam
em 0. A resposta final é 72 + 256 = 328.
O segundo método consiste em ignorar uma das restrições do problema, o que nos fará contar
em demasia. Depois descontaremos o que tiver sido contado indevidamente. Em primeiro lugar
fazemos de conta que o 0 pode ser usado na primeira posição do número. Procedendo assim,
há 5 maneiras de escolher o último algarismo (só pode ser 0,2,4,6, ou 8), 9 maneiras de escolher
o primeiro algarismo (não podemos repetir o algarismo usado na última casa) e 8 maneiras de
escolher o algarismo central. Há 5 × 9 × 8 = 360 números, aı́ incluı́dos os que começam por 0.
Por fim vamos determinar quantos desses números começam por 0; são esses os números que
foram contados indevidamente. Há só uma maneira de escolher o primeiro algarismo (tem que
ser 0), 4 maneiras de escolher o último (só pode ser 2,4,6, ou 8 — lembre-se que os algarismos
111
Estruturas Discretas 5.1. Técnicas básicas
são distintos) e 8 maneiras de escolher o algarismo central (não podemos repetir os algarismos já
usados). Há assim 1 × 4 × 8 = 32 números começados por 0. A resposta final é 360 − 32 = 328.
É claro que este problema poderia ter sido resolvido com um truque. Para determinar
quantos são os números pares de três algarismos distintos, poderı́amos calcular os números de
três algarismos distintos menos os números ı́mpares de três algarismos distintos.
Para os números de três algarismos distintos, há 9 maneiras de escolher o primeiro algarismo,
9 maneiras de escolher o segundo e 8 maneiras de escolher o último. Portanto há 9 × 9 × 8 = 648
números de três algarismos distintos.
Para os números ı́mpares de três algarismos distintos, há 5 maneiras de escolher o último
algarismo, 8 maneiras de escolher o primeiro e 8 maneiras de escolher o algarismo central. Há
pois 5 × 8 × 8 = 320 números ı́mpares de três algarismos distintos.
A resposta final é 648 − 320 = 328.
(1) De um conjunto de 4 letras {A, B, C, D}, quantas sequências de 3 letras se podem formar
se repetições de uma mesma letra não forem permitidas?
(2) Considere 4 pontos A, B, C, D num plano, tais que nenhum grupo de 3 esteja situado
sobre uma mesma recta. Quantos triângulos diferentes podem ser construı́dos usando esses
pontos como vértices?
C C
B A
D D
B A
A C B C
D D
B A
D D
C C
112
Estruturas Discretas 5.1. Técnicas básicas
B B
A A
D C
A A
C B D B
D C
A A
D C
B B
Note-se que neste caso a ordem pela qual se escrevem as letras na sequência é fundamental:
definem o mesmo triângulo (o que define um triângulo é o conjunto dos seus três vértices, e não
a ordem pela qual os poderemos escrever).
Estes dois problemas revelam-nos duas estruturas diferentes, que ocorrem frequentemente, e
que abordaremos de seguida, de uma maneira mais formal e sistemática.
(a, b), (a, c), (b, a), (b, c), (c, a), (c, b).
Logo P (3, 2) = 6. As permutações de 3 elementos são (a, b, c), (a, c, b), (b, a, c), (b, c, a), (c, a, b) e
(c, b, a) pelo que P (3, 3) = 6.
É possı́vel fazer estes cálculos no WolframAlpha:
113
Estruturas Discretas 5.1. Técnicas básicas
P (n, r) = n × (n − 1) × · · · × (n − r + 1).
Prova. O primeiro elemento da sequência ordenada pode ser escolhido de entre n elementos
diferentes. O segundo de entre n−1, e assim sucessivamente, até ao elemento na r-ésima posição
que poderá ser escolhido de entre n−(r−1) = n−r+1 elementos diferentes. Logo, pelo Princı́pio
da Multiplicação, a construção da sequência pode ser realizada de
n × (n − 1) × · · · × (n − r + 1)
Exemplo. As combinações dos elementos de S = {a, b, c}, dois a dois, são {a, b}, {a, c} e {b, c}.
Portanto C(3, 2) = 3. As combinações dos elementos de S três a três reduzem-se a {a, b, c}.
Logo C(3, 3) = 1.
114
Estruturas Discretas 5.1. Técnicas básicas
115
Estruturas Discretas 5.1. Técnicas básicas
P (n, r) n!
C(n, r) = = . 2
r! r!(n − r)!
A combinatória28 e a teoria das probabilidades partilham raı́zes comuns e estão muito ligadas.
De facto, o cálculo de uma probabilidade discreta (probabilidade de um acontecimento num
espaço de resultados finito29 ) é um mero problema de contagem: numa experiência aleatória
com um espaço S de resultados equiprováveis e finito, a probabilidade p(A) de um acontecimento
A é igual a |A|/|S|, ou seja,
Basta então contar o número total de resultados possı́veis e, de entre esses, quais são favoráveis
à realização do acontecimento.
Exemplo 1. Existem várias lotarias, como o totoloto, que dão prémios avultados a pessoas
que acertam correctamente em 6 números escolhidos entre os primeiros n inteiros positivos
(habitualmente, n está entre 30 e 50). Qual é a probabilidade de uma pessoa ganhar o prémio
no caso n = 40?
Solução. Só existe uma combinação vencedora. O número total de resultados possı́veis é igual
ao número de maneiras diferentes de escolher um subconjunto de 6 números entre os primeiros
40 inteiros positivos, ou seja, é igual a
40!
C(40, 6) = = 3 838 380.
34! 6!
Consequentemente, a probabilidade de acertar na combinação vencedora é igual a
28 Área
da matemática que trata dos problemas de contagem.
29 Uma experiência aleatória é um procedimento aleatório donde resulta um de entre vários resultados possı́veis.
O espaço dos resultados é o conjunto dos resultados possı́veis da experiência. Um acontecimento aleatório
é um subconjunto do espaço dos resultados, formado pelos elementos que são favoráveis à realização desse
acontecimento.
116
Estruturas Discretas 5.1. Técnicas básicas
30 593775 0.168413961510−5
31 736281 0.135817710910−5 41 4496388 0.222400735910−6
32 906192 0.110351890110−5 42 5245786 0.190629202210−6
33 1107568 0.902879100910−6 43 6096454 0.164029778610−6
34 1344904 0.743547494810−6 44 7059052 0.141662081510−6
35 1623160 0.616082210010−6 45 8145060 0.122773804010−6
36 1947792 0.513401841710−6 46 9366819 0.106759829610−6
37 2324784 0.430147489010−6 47 10737573 0.931309151510−7
38 2760681 0.362229464410−6 48 12271512 0.814895507610−7
39 3262623 0.306501854510−6 49 13983816 0.715112384210−7
40 3838380 0.260526576310−6 50 15890700 0.629298898110−7
Exemplo 2. Qual é a probabilidade que uma mão de cinco cartas no póquer contenha quatro
cartas do mesmo tipo?
Solução. Pela regra da multiplicação, o número de mãos de cinco cartas com quatro cartas do
mesmo tipo é o produto do número de maneiras de escolher um tipo (de entre os 13 tipos de
carta diferentes) pelo número de maneiras de escolher quatro cartas desse tipo de entre todas as
117
Estruturas Discretas 5.1. Técnicas básicas
cartas do baralho desse tipo (4 também) e pelo número de maneiras de escolher a quinta carta:
C(13, 1) × C(4, 4) × C(48, 1). Como existem, no total, C(52, 5) mãos diferentes de cinco cartas,
a probabilidade pedida é igual a
Solução. Designemos pelas letras a, b, c, d, c os cinco bandidos de modo que as respectivas al-
turas satisfaçam alt(a) < alt(b) < alt(c < alt(d) < alt(e). O objectivo do inspector Loureiro
é, portanto, prender o bandido a. A probabilidade de ele realizar tal evento é igual ao quo-
ciente do número de permutações favoráveis do conjunto {a, b, c, d, e} (isto é, as permutações
x1 x2 x3 x4 x5 tais que o elemento de {x3 , x4 , x5 } com menor ı́ndice que seja mais baixo do que x1
e x2 seja exactamente o bandido a) pelo número de permutações total (que é igual a 5! = 120).
Determinemos então o número de permutações favoráveis:
Claro que nenhuma permutação na qual a aparece na 1a ou 2a posições é favorável. Aquelas
em que a aparece na 3a posição são todas favoráveis e são em número de 4! = 24. Contemos
agora as permutações favoráveis nas quais a aparece na 4a posição: as 6 nas quais b está na 1a
posição são favoráveis; analogamente as 6 nas quais b está na 2a posição são também favoráveis;
nenhuma das que b aparece na 3a posição é favorável; das que b aparece na 5a posição somente 4
são favoráveis (cdcab, dceab, ccdab, ecdab). Portanto ao todo temos 16 permutações favoráveis
nas quais a esta na 4a posição.
Finalmente contemos as permutações favoráveis nas quais a aparece na 5a posição: obviamente
são aquelas em que b aparece na 1a ou 2a posições; portanto, são 3 × 2 + 3 × 2 = 12 permutações.
Em conclusão, o número de permutações favoráveis é igual a 24 + 16 + 12 = 52 e, consequente-
52
mente, a probabilidade do inspector Loureiro apanhar o chefe do bando é igual a 120 ∼ 0, 433333.
Os números nr = C(n, r) chamam-se números (ou coeficientes) binomiais (por razões que
n n
2
Corolário 3. Para quaisquer inteiros n e r tais que 0 ≤ r ≤ n tem-se r = n−r .
118
Estruturas Discretas 5.1. Técnicas básicas
n n n n n n n n n
n 0 1 2 3 4 5 6 7 8 ...
0 1
1 1 1
2 1 2 1
3 1 3 3 1
4 1 4 6 4 1
5 1 5 10 10 5 1
6 1 6 15 20 15 6 1
7 1 7 21 35 35 21 7 1
8 1 8 28 56 70 56 28 8 1
.. .. .. .. .. .. .. .. .. .. ..
. . . . . . . . . . .
Muitas das relações envolvendo coeficientes binomiais podem ser descobertas através da
simples observação do Triângulo de Pascal. Por exemplo:
1 3 6 10
119
Estruturas Discretas 5.1. Técnicas básicas
15 21
A validade destas identidades pode depois ser facilmente verificada utilizando o Princı́pio de
Indução Matemática.
Prova. Não é difı́cil provar o Teorema Binomial por indução matemática. No entanto, a
seguinte prova, puramente combinatorial, é mais curta e elegante:
Quando efectuamos a multiplicação (x+y)(x+y) · · · (x+y) até não restarem mais parênteses,
cada um dos factores (x + y) contribui com um x ou um y para cada parcela. Resultam portanto
2n parcelas e cada uma delas pode ser escrita na forma xr y n−r para algum r ∈ {0, 1, . . . , n}.
Obtemos a parcela xr y n−r precisamente quando escolhemos x em r dos factores e y nos restantes
n − r. Então o número de vezes que a parcela xr y n−r ocorre na expansão é igual ao número de
maneiras diferentes de seleccionar r dos n factores (x+y), ou seja, ao número nr de combinações
de n elementos r a r. 2
x+y
x2 + 2xy + y
x3 + 3xy + 3xy + y 3
x4 + 4x3 y + 6x2 y 2 + 4xy 3 + y 4
x5 + 5x4 y + 10x3 y 2 + 10x2 y 3 + 5xy 4 + y 5
30 O Teorema Binomial dá-nos uma fórmula para o desenvolvimento de (x + y)n com x, y ∈ R, n ∈ N. Em
1676, Newton generalizou-o, obtendo um desenvolvimento para (x + y)α com α ∈ R. Para se obter esta forma
é necessário estender o domı́nio de definição dos números binomiais n
r
, permitindo que n ∈ N e r ∈ Z. Neste
caso geral o desenvolvimento torna-se uma série infinita e consequentemente algumas questões de convergência
se levantam, por isso não vamos sequer enunciar esse resultado.
120
Estruturas Discretas 5.1. Técnicas básicas
estes números são precisamente os coeficientes da expansão do Binómio de Newton. Note que a
fórmula do binómio ainda é válida para n = 0.
Do Binómio de Newton podemos obter, como casos particulares, algumas identidades úteis.
Por exemplo:
Para x = 1 e y = 1,
n
n
X n
2 = , para n ≥ 0.
r=0
r
Para y = 1,
n n
n
X n X
r n
(x + 1) = x = xr , para n ≥ 0.
r=0
r r=0
n − r
Para x = −1 e y = 1,
n
X n
0= (−1)r , para n ≥ 1.
r=0
r
Em resumo, temos à disposição vários métodos que podemos usar para obter identidades
envolvendo os números binomiais:
(1) Definição;
121
Estruturas Discretas Apêndice: O Princı́pio dos Pombais
Há um outro princı́pio combinatorial básico muito intuitivo que, apesar de elementar, permite
a resolução de muitos problemas (de existência de determinadas configurações), alguns surpre-
endentes e difı́ceis.
Prova. Faremos a demonstração por redução ao absurdo. Suponhamos que em cada caixa
ficava, no máximo, um objecto. Então o número de objectos seria no máximo n, o que contradiz
a hipótese. Portanto alguma caixa conterá, pelo menos, dois objectos. 2
Formulado em termos de pombos este princı́pio diz que se n pombos voarem para n − 1
pombais, necessariamente um pombal será ocupado por dois ou mais pombos. Por exemplo, no
caso de 13 pombos e 12 pombais,
H H H H H H H H H H H
H H H H H H H H H H
H H H H H H H H H H H
H H H H H H H
Solução do Problema (A2).31 Escolhendo 101 inteiros entre os inteiros 1, 2, . . . , 200, vamos
aplicar o Princı́pio dos Pombais para mostrar que entre os inteiros escolhidos existem dois tais
que um é divisor do outro.
Qualquer inteiro pode ser escrito na forma 2k a, com k ∈ N0 e a ı́mpar. Para qualquer inteiro
entre 1 e 200, a é um dos números 1, 3, 5, . . . , 199. Logo, entre os 101 escolhidos, dois são da
forma 2k1 a1 e 2k2 a2 com a1 = a2 . Se k1 ≤ k2 então 2k1 a1 é divisor de 2k2 a2 . Caso k1 > k2 ,
2k2 a2 é divisor de 2k1 a1 . 2
Vamos agora apresentar uma forma mais geral do Princı́pio dos Pombais.
122
Estruturas Discretas Apêndice: O Princı́pio dos Pombais
Prova. Suponhamos por absurdo que, para cada i ∈ {1, 2, . . . , n}, a i-ésima caixa ficava com,
no máximo, pi − 1 elementos. Então o número total de objectos não excederia
o que é absurdo. Logo existe i ∈ {1, 2, . . . , n} tal que a i-ésima caixa conterá pelo menos pi
objectos. 2
“se n(r − 1) + 1 objectos forem colocados em n caixas, pelo menos uma das caixas
ficará com r ou mais objectos”.
Por exemplo, no problema (A1), como o número de caixas é igual ao número de notas
possı́veis, ou seja, 201, podemos assegurar que se comparecerem 201(r − 1) + 1 = 201r − 200
alunos ao exame, r de entre eles terão a mesma nota.
Solução do Problema (A3).32 Provemos, utilizando a Observação (2), que de uma sequência
a1 , a2 , . . . , an2 +1 de números reais é possı́vel extrair uma subsequência crescente ou decrescente
com n + 1 elementos.
Suponhamos que não existe nenhuma subsequência crescente com n + 1 elementos. Para
k ∈ {1, 2, . . . , n2 + 1} seja mk o número de elementos da maior subsequência crescente que
começa em ak . É evidente que, para cada k ∈ {1, 2, . . . , n2 + 1}, mk ≥ 1 e mk ≤ n. Temos então
n2 + 1 inteiros, m1 , m2 , . . . , mn2 +1 , entre 1 e n. Como n(r − 1) + 1 = n2 + 1 para r = n + 1,
podemos concluir que n + 1 desses inteiros são iguais entre si. Sejam eles
onde
1 ≤ k1 < k2 < · · · < kn+1 ≤ n2 + 1.
Se existisse algum i ∈ {1, 2, . . . , n} tal que aki < aki+1 , seria possı́vel construir uma subsequência
crescente começando em aki com mki+1 +1 elementos, o que é absurdo uma vez que mki = mki+1 .
Consequentemente,
ak1 ≥ ak2 ≥ · · · ≥ akn+1 ,
isto é,
ak1 , ak2 , · · · , akn+1
Em particular, nos primeiros 101 números naturais, dispostos por qualquer ordem, será
sempre possı́vel encontrar 11 números que formam ou uma sequência crescente ou uma sequência
32 Difı́cil!
123
Estruturas Discretas Apêndice: O Princı́pio dos Pombais
decrescente. Isto já não acontece se tomarmos apenas os primeiros 100 números naturais. Como
se poderá ordenar esses números de forma a não ser possı́vel encontrar a desejada sequência
de 11 elementos? Bastará começar com 91, 92, 93 até 100, depois 81, 82, 83 até 90 e assim
sucessivamente:
91 92 93 94 95 96 97 98 99 100
81 82 83 84 85 86 87 88 89 90
71 72 73 74 75 76 77 78 79 80
61 62 63 64 65 66 67 68 69 70
51 52 53 54 55 56 57 58 59 60
41 42 43 44 45 46 47 48 49 50
31 32 33 34 35 36 37 38 39 40
21 22 23 24 25 26 27 28 29 30
11 12 13 14 15 16 17 18 19 20
1 2 3 4 5 6 7 8 9 10
124
Estruturas Discretas 5.2. Técnicas avançadas de contagem
Teorema 1. O número destas permutações, que denotaremos por P (n, r), é igual a nr .
n × n × · · · × n = nr
| {z }
r vezes
permutações diferentes. 2
Exemplos. (1) Se quisermos ter a certeza de obter 13 resultados certos no totobola teremos de
preencher P (3, 13) = 313 colunas.
(2) Observámos anteriormente que o número de subconjuntos de um conjunto S = {a1 , a2 , . . . , an }
é igual a 2n . Podemos concluir isso de outro modo: se a cada subconjunto S 0 de S fizermos
corresponder uma sequência (a01 , a02 , . . . , a0n ) de comprimento n, definida por
1 se ai ∈ S
0
ai =
0 se ai 6∈ S
Teste. Qual é a probabilidade p(n) de, entre n pessoas, existirem pelo menos duas que façam
anos no mesmo dia ?
Solução. Admitiremos só como datas possı́veis de nascimento os 365 dias de um ano não
bissexto. Calculemos a probabilidade do acontecimento contrário, isto é, a probabilidade de
todas as pessoas fazerem anos em dias diferentes. O número de casos possı́veis é igual a P (365, n),
uma vez que cada caso é uma sequência de n elementos, que se podem repetir, escolhidos entre
os 365 dias. O número de casos favoráveis é igual a P (365, n) pois cada caso favorável é uma
125
Estruturas Discretas 5.2. Técnicas avançadas de contagem
sequência de n elementos, sem repetição, escolhidos entre os 365 dias. A probabilidade p(n) é
então dada por
P (365, n) 365 × 364 × 363 × · · · × (365 − n + 1)
1− =1− .
P (365, n) 365n
Alguns valores particulares de p: p(5) = .0713557370, p(10) = .1169481777, p(15) = .2529013198,
p(20) = .4114383836, p(25) = .5686997040 e p(30) = .7063162427.
Qual é o menor valor de n para o qual p(n) ≥ 0.5 ? e para o qual p(n) ≥ 0.99 ? O seguinte
procedimento calcula esses limites inferiores:
23, 57
Este é o chamado problema dos aniversários, muito conhecido pois a resposta parece, à
primeira vista, um pouco surpreendente: não é preciso um n muito grande para a probabilidade
ser maior que 0.99, basta n ≥ 57.
Aniversarios(.11)=10
Aniversarios(.22)=14
Aniversarios(.33)=18
Aniversarios(.44)=21
Aniversarios(.55)=25
Aniversarios(.66)=29
Aniversarios(.77)=33
Aniversarios(.88)=40
Aniversarios(.99)=57
126
Estruturas Discretas 5.2. Técnicas avançadas de contagem
Designemos por multi-conjunto uma estrutura similar à de um conjunto mas com a diferença
de os seus elementos não terem forçosamente que ser distintos. Por exemplo, M = {a, a, b, b, b, c}
é um multi-conjunto com 6 elementos: 2 a’s, 3 b’s, 1 c. Costuma indicar-se um multi-conjunto
especificando o número de ocorrências de cada elemento. Portanto o multi-conjunto M também
se denota por {2 · a, 3 · b, c}. Chamaremos combinação com repetição dos elementos de S, r a r,
aos multi-conjuntos de r elementos de S.
Multi-conjunto Representação
{a1 , a1 , a2 , a4 , a4 , a4 } ∗ ∗ | ∗ | | ∗ ∗∗
{a2 , a2 , a3 , a3 , a3 , a3 } | ∗ ∗| ∗ ∗ ∗ ∗|
Em resumo:
127
Estruturas Discretas 5.2. Técnicas avançadas de contagem
Exemplos. (1) O Dominó tem 28 peças. De facto, cada peça é uma combinação com repetição
{n, m} onde n, m ∈ {0, 1, . . . , 6}, pelo que o número de peças é igual a C(7, 2) = C(8, 2) =
56/2 = 28.
(2) O número de sequências crescentes (em sentido lato) com r componentes, escolhidas no
conjunto {1, 2, . . . , n}, é igual a C(n + r − 1, r).
(3) O número de soluções da equação x1 + x2 + x3 = 11, (x1 , x2 , x3 ∈ N0 ), é igual a
Mais geralmente, C(n, r) é igual ao número de soluções inteiras (não negativas) da equação
x1 + x2 + · · · + xn = r. De facto, qualquer combinação com repetição de elementos de S =
Pn
{a1 , a2 , . . . , an }, r a r, contém, para cada i, pi elementos iguais a ai , e i=1 pi = r; por
outro lado, é evidente que a cada conjunto {p1 , p2 , . . . , pn } de inteiros positivos ou nulos, com
p1 + p2 + · · · + pn = r, podemos fazer corresponder a combinação com repetição de elementos
de S, r a r,
{a1 , a1 , . . . , a1 , a2 , a2 , . . . , a2 , . . . , an , an , . . . , an }.
| {z } | {z } | {z }
p1 vezes p2 vezes pn vezes
k := 0
for i1 := 1 to n
for i2 := 1 to i1
for i3 := 1 to i2
.
.
.
for ir := 1 to ir−1
k := k + 1
Observemos que o valor inicial de k é 0 e que uma unidade é adicionada a k de cada vez que
o ciclo é atravessado com um conjunto de inteiros i1 , i2 , . . . , ir tais que
1 ≤ ir ≤ ir−1 ≤ · · · ≤ i2 ≤ i1 ≤ n.
Podemos impôr algumas restrições à repetição dos elementos nas combinações e permutações:
128
Estruturas Discretas 5.2. Técnicas avançadas de contagem
C(n, r − r1 − · · · − rn ) = C(n + r − r1 − · · · − rn − 1, r − r1 − · · · − rn ).
129
Estruturas Discretas 5.2. Técnicas avançadas de contagem
Prova. Basta observar que o número dessas permutações é, pelo Princı́pio da Multiplicação,
igual a
X
C(r, s1 )×C(r−s1 , s2 )×C(r−s1 −s2 , s3 )×· · ·×C(r − s1 − s2 − · · · − sn−1 , sn ).
| {z }
s1 +s2 +···+sn =r;si ≥ri
sn
r! (r − s1 )! (r − s1 − s2 )! (r − s1 − s2 − · · · − sn−1 )!
× × × ··· × =
s1 ! (r − s1 )! s2 ! (r − s1 − s2 )! s3 ! (r − s1 − s2 − s3 )! sn ! (r − s1 − s2 − · · · − sn )!
| {z }
=0
r! r
= = .
s1 !s2 ! . . . sn ! s1 , s2 , . . . , sn
2
É claro que podemos também impôr condições ao número máximo de vezes que cada ele-
mento pode ser repetido nas combinações e permutações. Aqui as fórmulas são um pouco mais
complicadas e não as apresentaremos.
x+y+z
x2 + 2xy + 2xz + y 2 + 2yz + z 2
x3 + 3x2 y + 3x2 z + 3xy 2 + 6xyz + 3xz 2 + y 3 + 3y 2 z + 3yz 2 + z 3
x4 + 4x3 y + 4x3 z + 6x2 y 2 + 12x2 yz + 6x2 z 2 + 4xy 3 + 12xy 2 z + 12xyz 2 + 4xz 3 + y 4 + 4y 3 z+
6y 2 z 2 + 4yz 3 + z 4
Princı́pio da Inclusão-Exclusão
O Princı́pio da Inclusão-Exclusão que vamos agora apresentar é também conhecido por fórmula
do crivo ou fórmula de da Silva-Sylvester33 e generaliza o Princı́pio da Adição.
Se A e B forem dois subconjuntos de X qual será o número de elementos da união A ∪ B? Se
somarmos simplesmente o número de elementos de A com o número de elementos de B estaremos
33 O Princı́pio da Inclusão-Exclusão foi publicado pela primeira vez em 1854, num artigo de Daniel da Silva, e
mais tarde, em 1883, por Sylvester. Por isso, a fórmula do crivo e suas similares são, por vezes, apelidadas de
fórmulas de da Silva ou de Sylvester. Realçamos o facto de Daniel da Silva, na opinião de Gomes Teixeira o mais
notável matemático português do séc. XIX, ter sido estudante da Universidade de Coimbra; transcrevemos de [J.
Silva Oliveira, Daniel Augusto da Silva, Boletim da SPM 2 (1979) 3-15]: “Daniel da Silva (1814-1878) foi, além de
matemático eminente do seu tempo, oficial da Armada e professor da Escola Naval. Como estudante frequentou
primeiro a Academia Real de Marinha e prosseguiu depois os seus estudos na Universidade de Coimbra onde,
com altas classificações, se licenciou em Matemática e acabou por se doutorar”.
130
Estruturas Discretas 5.2. Técnicas avançadas de contagem
a contar, uma vez cada um, os elementos de A − B e os de B − A, mas estaremos a contar por
duas vezes os elementos da intersecção A ∩ B (é o que o número 2 indica na região A ∩ B na
figura):
|A| + |B|:
Deste modo estaremos a contar, uma vez cada um, os elementos de A − (B ∪ C), os de
B − (A ∪ C) e os de C − (A ∪ B), mas estaremos a contar por duas vezes os elementos de
(A ∩ B) − C, (A ∩ C) − B e (B ∩ C) − A, e, pior ainda, estaremos a contar por três vezes os
elementos da intersecção A ∩ B ∩ C. Podemos começar por descontar os primeiros adicionando
|A ∩ B|, |A ∩ C| e |B ∩ C|.
131
Estruturas Discretas 5.2. Técnicas avançadas de contagem
Mas agora acabámos por descontar os elementos da intersecção A ∩ B ∩ C mais do que devı́amos
(o zero na figura acima indica que os elementos dessa região ainda não foram considerados para
a contagem dos elementos de A ∪ B ∪ C), tendo que os contar novamente, para que a contagem
fique certa.
|A| + |B| + |C| − (|A ∩ B| + |A ∩ C| + |B ∩ C|) + |A ∩ B ∩ C|:
Prova. É evidente que o conjunto dos elementos de X que possuem alguma das propriedades
P1 , P2 , . . . , Pn é a união A1 ∪ A2 ∪ · · · ∪ An . Podemos verificar a validade da identidade a provar
132
Estruturas Discretas 5.2. Técnicas avançadas de contagem
mostrando que um objecto com alguma das propriedades P1 , P2 , . . . , Pn contribui com uma
unidade para a soma do enunciado do princı́pio e que um objecto que não verifique nenhuma
dessas propriedades contribui com um zero para essa mesma soma.
Designemos esta soma por M . Cada elemento de X que não possui nenhuma das propriedades
P1 , P2 , . . . , Pn contribui com
0 − 0 + 0 − · · · + (−1)n+1 × 0 = 0
34
que, por sua vez, é igual a C(m, 0) = 1, pois por uma fórmula deduzida na secção anterior ,
Prova. É claro que o número de elementos de elementos de X que não verificam nenhuma das
propriedades P1 , P2 , . . . , Pn é o cardinal de A1 ∩ A2 ∩ · · · ∩ An = X − (A1 ∪ A2 ∪ · · · ∪ An ). Pelo
Princı́pio da Inclusão-Exclusão esse número é igual a
n
X n
X n
X
|X| − |Ai | − |Ai ∩ Aj | + |Ai ∩ Aj ∩ Ak | − · · · + (−1)n+1 |A1 ∩ A2 ∩ · · · ∩ An |
i=1 i,j=1 i,j,k=1
i<j i<j<k
n
X n
X n
X
= |X| − |Ai | + |Ai ∩ Aj | − |Ai ∩ Aj ∩ Ak | + · · · + (−1)n |A1 ∩ A2 ∩ · · · ∩ An |.
i=1 i,j=1 i,j,k=1
i<j i<j<k
2
133
Estruturas Discretas 5.2. Técnicas avançadas de contagem
Este problema é um caso particular do seguinte problema geral, designado por problema
dos desencontros:
1 1 1 1
Solução do problema. Para qualquer n ∈ N, Dn = n! 1 − + − + · · · + (−1)n .
1! 2! 3! n!
Prova. Seja X o conjunto de todas as permutações de S. Claro que |X| = n!. Seja ainda Ai
(i = 1, 2, . . . , n) o conjunto das permutações aj1 aj2 . . . ajn tais que aji = ai (portanto aquelas
em que ai está na posição primitiva). Claro que |Ai | = (n − 1)!. As permutações em Ai ∩ Aj
têm ai e aj fixos, nas posições i e j respectivamente, e os restantes n − 2 elementos permutados
nas restantes n − 2 posições, pelo que |Ai ∩ Aj | = (n − 2)! para i, j ∈ {1, 2, . . . , n}, i < j.
Analogamente, podemos concluir que |Ai1 ∩ Ai2 ∩ · · · ∩ Aik | = (n − k)! para k ∈ {1, 2, . . . , n},
i1 , i2 , . . . , ik ∈ {1, 2, . . . , n}, i1 < i2 < · · · < ik . Como Dn = |A1 ∩ A2 ∩ · · · ∩ An |, decorre pelo
Princı́pio da Inclusão-Exclusão que
n! n! n! n!
Dn = n! − + − + · · · + (−1)n
1! 2! 3! n!
1 1 1 1
= n! 1 − + − + · · · + (−1)n .
1! 2! 3! n!
35 Também costuma aparecer enunciado do seguinte modo, na forma de um jogo de cartas: “No chamado ‘jogo
dos pares’, as 52 cartas de um baralho são dispostas em linha, com o seu valor à vista. As cartas de um segundo
baralho são dispostas também em linha por cima das outras. A pontuação é determinada contando o número
de vezes em que a carta do segundo baralho coincide com a do primeiro sobre a qual foi colocada. Qual é a
probabilidade de se obterem zero pontos?”
134
Estruturas Discretas 5.2. Técnicas avançadas de contagem
Cálculo de D2 , D3 , . . . , D15 :
Na sua forma original o problema (B3) foi formulado em termos de probabilidades, questio-
nando a probabilidade de nenhuma pessoa receber de volta o respectivo chapéu. Evidentemente,
a resposta é a probabilidade de uma permutação de n objectos, escolhida aleatoriamente, ser
um desencontro, ou seja,
Dn 1 1 1 1
= 1 − + − + · · · + (−1)n .
n! 1! 2! 3! n!
n, probabilidade
2, 0.50000000000000000000
3, 0.33333333333333333333
4, 0.37500000000000000000
5, 0.36666666666666666667
6, 0.36805555555555555556
7, 0.36785714285714285714
8, 0.36788194444444444444
9, 0.36787918871252204586
10, 0.36787946428571428571
11, 0.36787943923360590027
12, 0.36787944132128159906
13, 0.36787944116069116069
14, 0.36787944117216190629
15, 0.36787944117139718992
16, 0.36787944117144498469
17, 0.36787944117144217323
18, 0.36787944117144232942
19, 0.36787944117144232120
20, 0.36787944117144232161
36 Usando factos da Análise Matemática é possı́vel provar que
∞
Dn X 1 1 1 1 1
lim = (−1)n =1− + − + · · · + (−1)n + · · · = e−1 ∼ 0.3679.
n→+∞ n! n=0
n! 1! 2! 3! n!
135
Estruturas Discretas 5.2. Técnicas avançadas de contagem
Vejamos agora como o Princı́pio da Inclusão-Exclusão também serve para resolver o Problema
(B2) da Introdução.
Seja A = {a1 , a2 , . . . , at } e denotemos o conjunto dos primeiros n números naturais por [n].
Designando o conjunto {x ∈ [n] | x é divisı́vel por ai } por Ai , o número pedido dos inteiros
positivos inferiores ou iguais a n, não divisı́veis por nenhum dos elementos de A é o cardinal de
A1 ∩ A2 ∩ · · · ∩ At . j k
Claramente |Ai | é a parte inteira do número ani , ou seja, ani . Como
|A1 ∩ A2 ∩ · · · ∩ At | é igual a
t j t j
X nk X n k j n k
n− + − · · · + (−1)t .
i=1
ai i,j=1
mmc(ai , aj ) mmc(a1 , a2 , . . . , at )
i≤j
No caso particular em que os elementos de A são todos primos entre si, o número de inteiros
positivos inferiores ou iguais a n que não são divisı́veis por nenhum dos elementos de A é igual a
t j t j t
X nk X n k X j n k j n k
n− + − + · · · + (−1)t .
i=1
ai i,j=1
ai aj i,j,k=1
ai aj ak a1 a2 . . . at
i≤j i≤j≤k
Contemos agora o número φ(n) de inteiros positivos, inferiores a n, primos com n. Seja
n = pα1 α2 αt
1 p2 · · · pt a factorização de n em números primos. Como os conjuntos
n o
k ∈ N | 1 ≤ k ≤ n e mdc(k, n) = 1
e n o
k ∈ N | 1 ≤ k ≤ n e pi 6 |k para i = 1, 2, . . . , t
φ: N → N
n 7→ φ(n) = |{k ∈ N | 1 ≤ k ≤ n e mdc(k, n) = 1}|
136
Estruturas Discretas 5.2. Técnicas avançadas de contagem
é um processo que permite enumerar todos os primos entre 1 e qualquer inteiro positivo k:
j√ k
• Calcula-se c = k ;
137
Estruturas Discretas 5.2. Técnicas avançadas de contagem
• em seguida, determinar, com a ajuda da fórmula acima deduzida, quantos inteiros positivos
inferiores ou iguais a n não
j√ são divisı́veis
k por nenhum dos elementos de A = {p1 , p2 , . . . , pt }.
Como os primos entre n + 1 e n são exactamente os inteiros positivos inferiores ou
iguais a n (com excepção do 1) que não são divisı́veis por nenhum dos elementos de A, o
seu número é igual a
t j t j t
X nk X n k X j n k j n k
M (n) = n − 1 − + − + · · · + (−1)t .
i=1
pi i,j=1
pi pj i,j,k=1
pi pj pk p1 p2 . . . pt
i≤j i≤j≤k
Relações de recorrência
Não é difı́cil concluir que, em geral, um tabuleiro m × n possui uma cobertura perfeita se e só
se pelo menos um dos números m ou n é par:
Se o tabuleiro possui uma cobertura perfeita então o dobro do número de peças na confi-
guração deverá ser igual a mn. Portanto 2|mn pelo que 2|m ou 2|n. Reciprocamente suponha-
mos, sem perda de generalidade, que m é par. Nesse caso é evidente que cada coluna pode ser
perfeitamente coberta (basta alinhar sucessivamente m/2 peças)
1
2
3
4
5
6
.. ..
. .
m−1
m
pelo que qualquer número n de colunas pode também ser coberto de modo perfeito.
Mais difı́cil é contar o número de coberturas perfeitas. Façamo-lo no caso mais simples de
um tabuleiro 2×n. Para cada n ∈ N, seja f (n) o número de coberturas perfeitas de um tabuleiro
2 × n. Comecemos por calcular f (1), f (2), f (3), f (4) e f (5):
f (1) = 1:
138
Estruturas Discretas 5.2. Técnicas avançadas de contagem
f (2) = 2:
f (3) = 3:
| {z } | {z }
f (3) f (2)
f (n) = f (n − 1) + f (n − 2) (n ≥ 3).
1 2 3 ··· n 1 2 3 ··· n
| {z } | {z }
f (n − 1) f (n − 2)
Esta relação, conjuntamente com os valores iniciais f (1) = 1 e f (2) = 2 , determina univo-
camente a sequência dos números de coberturas perfeitas f (1), f (2), f (3), . . . .
Por exemplo, f (12) é igual a
f (11) + f (10) = 2f (10) + f (9) = 3f (9) + f (8) = · · · = 21f (5) + 13f (4) = 233.
É claro que para valores muito grandes de n este método de cálculo de f (n) não será praticável
sem a ajuda de um computador, porque não temos aqui uma fórmula fechada para o valor de
139
Estruturas Discretas 5.2. Técnicas avançadas de contagem
f (n) mas sim uma relação de recorrência que estabelece o valor de f em n a partir de valores
de f em inteiros anteriores a n.
Como podemos resolver relações de recorrência destas, isto é, como podemos obter, a partir
da relação de recorrência, a respectiva fórmula fechada? É o que veremos agora.
u : N0 → S
n 7 → u(n).
O valor u(n) costuma representar-se simplesmente por un e é frequente apresentar uma sucessão
dispondo sucessivamente as imagens da aplicação u:
u0 , u1 , u2 , . . . .
Muitas vezes uma sucessão é dada mediante a indicação do que se chama o seu termo geral,
ou termo de ordem n (por exemplo, un = n2 , un = sin 2n /(n + 1)2 , etc.). É uma situação
cómoda pois, além de nesse caso ser possı́vel calcular sem grandes problemas qualquer termo
da sucessão, o estudo de várias propriedades (como a monotonia, convergência, etc.) fica muito
facilitado. Usaremos a notação (un ) para nos referirmos à sucessão u0 , u1 , u2 , . . . .
Como vimos nos exemplos acima, nem sempre uma sucessão é definida por indicação do
seu termo geral, mas sim por uma relação de recorrência: são dados uns tantos termos iniciais
da sucessão, u0 , u1 , . . . , uk−1 , e cada um dos seguintes determina-se a partir dos k anteriores
por intermédio de uma relação que permanece invariável, uk = f (u0 , u1 , . . . , uk−1 ), uk+1 =
f (u1 , u2 , . . . , uk ), etc. Estas são as chamadas relações de recorrência para a sucessão (un ). Ao
número k chama-se ordem da relação de recorrência.
Uma sucessão diz-se uma solução de uma relação de recorrência se os seus termos satisfizerem
a relação. De entre todas as relações de recorrência destacam-se, não só pela sua simplicidade
mas também pela frequência com que ocorrem, as chamadas relações de recorrência lineares
homogéneas com coeficientes constantes. São as do tipo
com a1 , a2 , . . . , ak constantes.
O adjectivo “linear”refere-se ao facto de todos os valores de u ocorrerem como potências
de expoente 1, enquanto que o adjectivo “homogéneo”refere-se ao facto de não existir termo
independente (constante).
Por exemplo, un = u2n−1 + 2un−2 (n = 2, 3, . . . ) não é linear, enquanto que un = 3un−1 + 2
(n = 1, 2, . . . ) não é homogénea. Por outro lado, a relação un = (n + 2)un−1 + 2un−2 (n =
2, 3, . . . ) é linear e homogénea mas não tem coeficientes constantes (o primeiro coeficiente n + 2
varia com n).
un = run−1 (n ≥ 1).
140
Estruturas Discretas 5.2. Técnicas avançadas de contagem
(2) As progressões aritméticas de razão r podem ser vistas como sucessões satisfazendo relações
de recorrência homogéneas lineares de segunda ordem: de un−1 = un−2 + r e un = un−1 + r
obtém-se, subtraindo a primeira identidade da segunda,
un = 2un−1 − un−2 .
(3) A sucessão do número de coberturas perfeitas satisfaz uma relação de recorrência homogénea
linear de segunda ordem.
u2 = au1 + bu0
u3 = au2 + bu1 = (a2 + b)u1 + abu0
u4 = au3 + bu2 = (a3 + 2ab)u1 + (a2 b + b2 )u0
..
.
Não é fácil descortinar aqui uma lei de formação que permita conjecturar o que deverá ser un em
função de n, a, b, u0 e u1 . É claro que para as sucessões recorrentes lineares de ordem superior a
situação será ainda pior.
Curiosamente, como veremos, o caso das relações de recorrência lineares homogéneas com
coeficientes constantes é tratável de uma forma sistemática, embora as técnicas existentes se
possam revelar muito trabalhosas na prática. Apesar de ser um método indirecto e pouco
natural, é elegante e engenhoso.
Restringemo-nos então à classe das relações de recorrência lineares homogéneas com coefici-
entes constantes, isto é, das relações de recorrência da forma
onde a1 , a2 , . . . , ak são constantes. Podemos sempre supor que ak 6= 0 pois, caso contrário, a
relação reduz-se a uma de ordem inferior.
Associemos à relação de recorrência (∗), a equação
xk − a1 xk−1 − a2 xk−2 − · · · − ak = 0,
141
Estruturas Discretas 5.2. Técnicas avançadas de contagem
1, α, α2 , α3 , . . . , αn , . . .
Prova. A sucessão (un ), onde un = αn , é uma solução de (∗) se e só se, para n ≥ k,
ou, equivalentemente,
αk − a1 αk−1 − a2 αk−2 − · · · − ak = 0.
ainda é solução de (∗). Combinando este facto com o Teorema 1 obtemos imediatamente o
Corolário. 2
No caso das raı́zes caracterı́sticas serem todas distintas podemos obter todas as soluções de
(∗):
142
Estruturas Discretas 5.2. Técnicas avançadas de contagem
Prova. Seja (un ) uma solução da relação de recorrência (∗). Uma vez que (∗), conjuntamente com
os k valores iniciais u0 , u1 , . . . , uk−1 , determinam completamente a sucessão (un ), bastará provar
que existem constantes c1 , c2 , . . . , ck tais que a sucessão de termo geral c1 α1n + c2 α2n · · · + ck αkn
satisfaz (∗) e tem como primeiros k elementos os valores u0 , u1 , . . . , uk−1 . Pelo Corolário, bastará
provar que existem constantes c1 , c2 , . . . , ck tais que
c1 + c2 + · · · + ck = u0
c1 α1 + c2 α2 + · · · + ck αk = u1
...
c1 α1k−1 + c2 α2k−1 + · · · + ck αkk−1 = uk−1 .
deste sistema é uma matriz muito especial, chamada matriz de Vandermonde. O seu determi-
nante é dado por
Yk
(αj − αi )
i,j=1
i<j
(a prova deste facto encontra-se em muitos livros de Álgebra Linear). Como as raı́zes α1 , α2 , . . . , αk
são todas distintas, este determinante é diferente de zero. Isto quer dizer que o sistema possui
exactamente uma solução. 2
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765
143
Estruturas Discretas 5.2. Técnicas avançadas de contagem
As raı́zes
√
da equação caracterı́stica
√
x2 − x − 1 = 0 desta relação de recorrência são o número
1+ 5 1− 5
de ouro 2 e o seu conjugado 2 . Então, pelo Teorema 2, os números de Fibonacci são
dados por
1 + √5 n 1 − √5 n
F (n) = c1 + c2 ,
2 2
para algum par de constantes c1 e c2 . As condições iniciais F (0) = 0 e F (1) = 1 permitem-nos
determinar tais constantes. Com efeito,
c1 + c2 = F (0) = 0
√ √
c1 1+ 5 + c2 1− 5 = F (1) = 1
2 2
√ √
5 5
cuja solução é c1 = 5 e c2 = − 5 .
144
Estruturas Discretas 5.2. Técnicas avançadas de contagem
Fica assim resolvido o Problema (B4) da Introdução: o número de pares de coelhos existentes
na ilha ao fim de n meses será igual a
√ √
1 h 1 + 5 n 1 − 5 n i
√ − .
5 2 2
Solução. De acordo com a definição do código, T (1) = 3 (as únicas palavras de comprimento 1
são: ‘0’, ‘’1 e ‘2’) e T (2) = 8:
00, 01, 02, 10, 11, 12, 20, 21.
··· 0 ··· 1
| {z } | {z }
T (n−1) T (n−1)
No entanto, nas palavras de comprimento n que terminam em 2, a penúltima posição n − 1 já só
pode conter os números 0 ou 1, pelo que as palavras são, no total, em número igual a 2 T (n − 2):
··· 0 2 ··· 1 2
| {z } | {z }
T (n−2) T (n−2)
145
Estruturas Discretas 5.2. Técnicas avançadas de contagem
não é uma solução geral da relação de recorrência. Por exemplo, a relação de recorrência un =
4un−1 − 4un−2 tem como equação caracterı́stica x2 − 4x + 4 = (x − 2)2 = 0. Neste caso (1) é
igual a
un = c1 2n + c2 2n = (c1 + c2 )2n = c2n
onde c = c1 + c2 é uma constante. Temos então uma só constante c e não será sempre possı́vel
escolhê-la de modo a que os dois valores iniciais u1 e u2 sejam satisfeitos. Por exemplo, se u0 = 1
e u1 = 3 teria que ser c = 1 e 2c = 3, o que é manifestamente impossı́vel. Portanto, un = c2n
não é uma solução geral daquela relação (isto é, nem toda a solução da relação de recorrência
pode ser expressa na forma c2n para alguma constante c).
O teorema seguinte, que não demonstraremos, diz-nos como determinar uma solução geral
nestes casos. A ideia da demonstração é a mesma da do Teorema 2, mas naturalmente mais
técnica e trabalhosa.
tais que
un = c11 + c12 n + · · · + c1e1 ne1 −1 α1n + c21 + c22 n + · · · + c2e2 ne2 −1 α2n + · · · +
+ ct1 + ct2 n + · · · + ctet net −1 αtn .
146
Estruturas Discretas 5.2. Técnicas avançadas de contagem
enquanto que a parte correspondente à raiz 2 é c21 2n . As constantes estão sujeitas às condições
iniciais
c11 + c21 = 1
−c − c − c + 2c
11 12 13 21 = 0
c 11 + 2c 12 + 4c13 + 4c 21 = 1
−c11 − 3c12 − 9c13 + 8c21 = 2,
pelo que, resolvendo o sistema, obtemos c11 = 7/9, c12 = −1/3, c13 = 0 e c21 = 2/9. Em
conclusão, a solução é
2n+1
7 1
un = − n (−1)n + (n ∈ N0 ).
9 3 9
un = un−1 + n3
= un−2 + (n − 1)3 + n3
= ···
= u1 + 23 + · · · + (n − 1)3 + n3
= 13 + 23 + · · · + n3 .
Assim, un é a soma dos primeiros n cubos. Podemos determinar uma expressão simples para
esta soma? Usando a relação de recorrência podemos determinar os primeiros valores de un e
147
Estruturas Discretas 5.2. Técnicas avançadas de contagem
u1 = 1
u2 = 1 + 23 = 9 = 32 = (1 + 2)2
u3 = 9 + 33 = 36 = 62 = (1 + 2 + 3)2
u4 = 36 + 43 = 100 = 102 = (1 + 2 + 3 + 4)2
u5 = 100 + 53 = 225 = 152 = (1 + 2 + 3 + 4 + 5)2 .
Como
n(n + 1)
1 + 2 + 3 + ··· + n = ,
2
podemos conjecturar que
n2 (n + 1)2
un = ,
4
o que pode ser confirmado pelo método de indução matemática.
No caso não homogéneo, é possı́vel em alguns casos uma abordagem sistemática que nos conduza
à solução. Uma recorrência linear, não necessariamente homogénea, de coeficientes constantes é
dada por uma equação do tipo
onde o termo independente g(n) é uma função de n que toma valores reais. A uma recorrência
deste tipo podemos, esquecendo a função g, associar a recorrência homogénea
Será de esperar que as soluções de (1) estejam relacionadas com as soluções de (2). De facto, é
fácil provar que:
Teorema 4. Seja
un = a1 un−1 + a2 un−2 + · · · + ak un−k + g(n)
uma relação de recorrência linear com coeficientes constantes e seja (αn ) uma solução desta
relação de recorrência. Se (βn ) é também uma solução dessa relação de recorrência, então a
sucessão (γn ) = (βn − αn ) é uma solução da relação de recorrência homogénea
Reciprocamente, se (γn ) é uma solução desta relação de recorrência homogénea, então a sucessão
(βn ) = (αn + γn ) é uma solução da relação de recorrência inicial.
Assim, para determinar a expressão geral das soluções de uma dada relação de recorrência
linear com coeficientes constantes, bastará:
148
Estruturas Discretas 5.2. Técnicas avançadas de contagem
(1) Obter a expressão geral das soluções (γn ) da relação de recorrência homogénea associada;
(3) A expressão geral das soluções (αn ) da relação de recorrência é dada pela soma (αn ) =
(βn + γn ).
O passo (1) pode realizar-se pelo método apresentado no caso homogéneo, mas a realização
de (2) depende da função g envolvida. Em geral, não há nenhuma garantia que (2) se possa
efectuar de modo fácil; os casos mais simples são aqueles em que g é polinomial ou exponencial.
A tabela seguinte fornece-nos soluções particulares para esses casos:
149
Bibliografia
[1] Carlos André e Fernando Ferreira, Matemática Finita, Universidade Aberta, 2000.
[2] Stephen Barnett, Discrete Mathematics: Numbers and Beyond, Prentice Hall, 1998.
[3] Jon Barwise e John Etchemendy, Language, Proof and Logic, CSLI Publications, 1999.
[4] James Hein, Discrete Structures, Logic and Computability, Portland State University, 2002.
[5] James Hein, Maple Experiments in Discrete Mathematics, Portland State University, Janeiro
2005.
[6] Kenneth H. Rosen, Discrete Mathematics and its Applications, McGraw-Hill, 1995.
[7] Kenneth H. Rosen, Exploring Discrete Mathematics with Maple, McGraw-Hill, 1997.
151