Matematica Discreta fascículo 2 novo

Prévia do material em texto

Universidade Federal Rural de Pernambuco
Reitor: Prof. Valmar Corrêa de Andrade
Vice-Reitor: Prof. Reginaldo Barros
Pró-Reitor de Administração: Prof. Francisco Fernando Ramos Carvalho
Pró-Reitor de Extensão: Prof. Paulo Donizeti Siepierski
Pró-Reitor de Pesquisa e Pós-Graduação: Prof. Fernando José Freire
Pró-Reitor de Planejamento: Prof. Rinaldo Luiz Caraciolo Ferreira
Pró-Reitora de Ensino de Graduação: Profª. Maria José de Sena
Coordenação de Ensino a Distância: Profª Marizete Silva Santos
Produção Gráfica e Editorial
Capa e Editoração: Allyson Vila Nova, Rafael Lira, Aline Fidelis, Italo Amorim e Alesanco Andrade
Revisão Ortográfica: Ivanda Martins
Ilustrações: Allyson Vila Nova e Diego Almeida
Coordenação de Produção: Marizete Silva Santos
Sumário
Plano da Disciplina ........................................................................................ 6
Ementa .................................................................................................... 6
Objetivo Geral.......................................................................................... 6
Objetivos Específicos .............................................................................. 6
Conteúdo Programático........................................................................... 6
Referências ............................................................................................. 7
Apresentação ................................................................................................. 8
Capítulo 1 - Somatório: representando somas ........................................... 9
1.1 Conhecendo o somatório ....................................................................... 9
1.2 Propriedades do somatório e algumas somas especiais .................... 12
1.2.1 Propriedades ................................................................................ 12
1.2.2 Demonstrações ............................................................................ 12
1.2.3 Somas Especiais .......................................................................... 12
1.3 Dígito Verificador ................................................................................. 15
Capítulo 2 - Matrizes: armazenando dados ............................................... 27
2.1 Matriz ................................................................................................... 27
2.2 Definição .............................................................................................. 29
2.3 Tipos especiais de matrizes ................................................................. 29
2.4 Operações com matrizes ..................................................................... 32
2.4.1 Adição de matrizes ....................................................................... 32
2.4.2 Multiplicação de uma matriz por um escalar ................................ 33
2.4.3 Multiplicação de matrizes ............................................................. 34
2.4.4 Matrizes Booleanas ...................................................................... 36
2.4.5 Adição e multiplicação de matrizes booleanas ............................. 38
2.4.6 Multiplicação de matrizes booleanas............................................ 39
Capítulo 3 - Princípios de Contagem: como contar? ............................... 47
3.1 Listas ................................................................................................... 47
3.2 Princípio Multiplicativo: contagem de listas de comprimento dois ....... 48
3.3 Listas de comprimento maior do que dois ........................................... 49
3.4 Listas de comprimento k sem repetição de elementos ........................ 50
3.5 Princípio Aditivo ................................................................................... 50
3.6 Fatorial ................................................................................................. 57
3.7 Permutações ........................................................................................ 58
3.8 Combinações ....................................................................................... 58
Capítulo 04 - Relações: uma abordagem ................................................... 69
4.1 Tipos de Relações Binárias ............................................................. 70
4.2 Relações binárias em um conjunto A .............................................. 73
4.3 Operações com relações: como operar com relações binárias? .... 74
4.4 Propriedades das Relações definidas em um conjunto A ............... 76
4.5 Representação gráfica de Relações Binárias ................................. 77
4.6 Grafo de uma relação em um conjunto A ........................................ 78
4.7 Relação n-ária ................................................................................. 79
4.8 Álgebra Relacional .......................................................................... 83
Plano da Disciplina
Ementa
Conjuntos. Introdução à Lógica Matemática. Portas Lógicas. Somatório. Princípios 
de Contagem. Matrizes. Relações. Funções. Recursão. Técnicas de provas. Indução 
Matemática.
Objetivo Geral
O objetivo geral é abordar conteúdos selecionados da Matemática Discreta que 
realizam interface com o curso de Sistema de Informação, visando dar a base para 
a compreensão de conceitos de estruturas de dados, bem como, para dar suporte na 
construção de algoritmos em seus diferentes níveis de complexidade.
Objetivos Específicos
• Aprender a encontrar modelos matemáticos que representem certos problemas 
concretos (noções de modelagem matemática), em especial quando estes se 
referem a situações práticas 
• Familiarizar-se com a escrita matemática formal e a linguagem computacional 
• Representar fenômenos na forma algébrica e na forma gráfica 
• Conhecer técnicas de resolução de problemas 
• Desenvolver a capacidade de raciocínio abstrato (lógico-matemático).
Conteúdo Programático
Módulo 1 – Fascículo 1
Carga horária do Módulo 1: 20h
• Conjuntos. 
• Introdução à Lógica Matemática. 
• Portas Lógicas.
Módulo 2 – Fascículo 2
Carga horária do Módulo 2: 20h
Somatório. Princípios de Contagem. Matrizes. Relações
Módulo 3 – Fascículo 3
Carga horária do Módulo 3: 20h
• Funções.
• Recursão. Técnicas de provas.
• Indução Matemática.
Referências
GERSTING, Judith L. Fundamentos Matemáticos para a Ciência da Computação. 
Tradução Valéria de Magalhães Lorio. Rio de Janeiro: LTC, 2004.
Scheinerman, Edward R. Matemática Discreta: uma introdução. Tradução de 
Alfredo Alves de Farias. São Paulo: Pioneira Thomson Learning, 2003.
Livros de referência:
ABE, Jair Minoro; PAPAVERO, Nelson. Teoria intuitiva dos conjuntos. São Paulo 
McGraw Hill:, 1997
ALENCAR Filho, Edgard de. Iniciação à Lógica Matemática. São Paulo: Nobel, 
1995.
ROSS, Kenneth A; WRIGHT, Charles R. B. Discrete Mathematics. Prentice Hall, 
1999.
TRUSS, J. K. Discrete mathematics for computer scientist. Addison Wesley. 
1999.
LIPSCHUTZ, Seimour; LIPSON, Marc Lars. Teoria e Problemas de Matemática 
Discreta. Porto Alegre: Bookman, 2004
Apresentação
Caro(a) cursista,
Seja bem-vindo(a) a mais um módulo de Matemática Discreta!
Dando continuidade à disciplina, abordaremos, neste segundo fascículo, alguns 
tópicos de importância e aplicabilidade nas áreas de informática, tais como: somatórios, 
matrizes, princípios de contagem e relações.
No primeiro capítulo, você estudará as propriedades do somatório e como elas são 
úteis na determinação de somas especiais e de uso freqüente na matemática.
No segundo capítulo, você descobrirá como as matrizes podem ser utilizadas para 
armazenamento de dados e as operações aritméticas que nelas podem ser efetuadas. 
Além disso, conheceráas matrizes booleanas, muito empregadas na informática.
No terceiro capítulo, você terá oportunidade de conhecer diversas técnicas de 
contagem, empregadas no cálculo e na diferenciação dos agrupamentos que se podem 
formar com os elementos de um dado conjunto.
Por fim, no quarto capítulo será abordado o conceito de relações entre dois ou mais 
conjuntos, as operações entre relações e como elas podem ser usadas para manipulação 
de um banco de dados.
Esperamos que você aproveite ao máximo este segundo módulo, estudando 
detalhadamente o assunto e realizando todos os exercícios propostos.
Bons estudos!
9
Matemática Discreta
Capítulo 1 - Somatório: 
representando somas
Neste capítulo mostraremos o uso do somatório na escrita de somas 
de parcelas variáveis ou constantes. Estudaremos as propriedades do 
somatório e como elas são úteis na determinação de somas especiais 
e de uso freqüente na matemática. Por fim, apresentaremos métodos 
de geração de dígitos verificadores em seqüências especiais de 
algarismos, tais como o CPF, código de barras e número de conta 
corrente bancária.
1.1 Conhecendo o somatório
Você já se deparou com a necessidade de escrever expressões 
que envolvem somas com termos que obedecem a certa lei de 
formação do tipo 1 + 2 + 3 + 4 + ... + 100?
 Se temos uma soma de n parcelas, x1 + x2 + x3 + ... + xn, saiba que 
podemos codificá-la através do uso de somatório assim:
x1 + x2 + x3 + ... + xn = ∑
=
n
i
ix
1
A letra maiúscula grega ∑ (sigma) é o símbolo utilizado para 
representar as operações de adição entre as parcelas e xi é a parcela 
genérica.
Para representar a parte variável de cada parcela, utilizamos a letra 
i e indicamos a variação de i (no caso, i varia de 1 até n). A expressão 
∑
=
n
i
ix
1
 é lida assim: “soma dos valores xi para i variando de 1 até n”.
Você deve estar atento para o fato de que é fundamental que o 
índice i assuma todos os valores inteiros consecutivos entre dois 
valores dados, inclusive. Assim, a soma x1 + x2 + x3 pode ser escrita: 
∑
=
3
1i
ix
10
Matemática Discreta
Compreenda melhor a aplicação do conceito de somatório, através 
dos exemplos seguintes.
Exemplo 1: ∑
=
5
1i
ix = x1 + x2 + x3 + x4 + x5 é a soma de 5 parcelas.
Exemplo 2: ∑
=
7
1i
ix = x + x2 + x3 + ... + x7 representa a soma de 7 
parcelas. O índice i, variando de 1 a 7, indica quantas parcelas contém 
a soma, como identifica as parcelas como potências de expoente 
inteiro.
Exemplo 3: ∑
=
7
3i
ix = x3 + x4 + x5 + x6 + x7 indica a soma de 
7 - 3 + 1 = 5 parcelas, conforme a observação acima.
Exemplo 4: ∑
−
+
4
1
)1(
i
ixi = 2x1 + 3x2 + 4x3 + 5x4 indica a soma de 4 
parcelas xi multiplicadas por coeficientes variáveis (i+1).
Exemplo 5. Para representar por meio da notação de somatório a 
soma dos números pares, iniciando por 2 até 40, isto é: 2 + 4 + 6 + 8 
+ ... + 40, denotaremos as parcelas variáveis por xi = 2.i, com o índice 
i variando de 1 até 20, de forma que, podemos escrever
2 + 4 + 6 + 8 + ... + 40 = 
Exemplo 6. A soma dos números ímpares 1 + 3 + 5 + 7 + 9 + 
11 se escreve na notação de somatório, tomando as parcelas 
xi = 2i – 1, com i variando de 1 até 6, conforme podemos observar na 
tabela seguinte:
i = 1 2 3 4 5 6
xi = 2i -1 2.1 – 1 = 1 2.1 – 1 = 3 2.3 – 1 = 5 2.4 – 1 =7 2.5 -1 = 9 2.6 – 1= 11
Exemplo 7. A expressão 128
1....
8
1
4
1
2
1 ++++ indica a soma de 
parcelas iguais a uma fração onde o numerador é 1 e os denominadores 
são potências inteiras de 2: 21, 22, 23, até 27, de modo que podemos 
escrever a soma sob a forma de somatório com xi = i2
1 , do seguinte 
modo: 128
1....
8
1
4
1
2
1 ++++ = ∑
=
7
1 2
1
i
i
Exemplo 8. Para escrever a expressão 
Para contar 
quantos termos 
uma soma tem, 
basta calcular 
no somatório, a 
diferença entre o 
índice superior e 
o inferior e somar 
1.
A soma ak + ak+1 
+ ak+2 + ... + an = 
∑
=
n
ki
ia
 tem n - k + 
1 termos.
Atenção
11
Matemática Discreta
sob a forma de somatório, você deve notar que os denominadores 
assumem valores crescentes de 1 até 50, indicando que a soma é 
constituída por 50 parcelas e que a variação do índice i é de i = 1 
até i = 50. Além disso, verifica-se que os numeradores são números 
ímpares da forma 2i - 1, com a mesma variação do índice i. A soma 
acima pode ser então escrita assim: 
50
1
2 1
i
i
i=
−∑ .
Exemplo 9. A soma S dos 30 primeiros termos da série 
 pode ser expressa por meio de 
um somatório, lembrando que as parcelas xi são frações cujos 
numeradores constituem uma progressão aritmética de termo inicial 
480 e razão r = -5 com termo de ordem i, ai = 480 + (i-1).(-5) = 485 
– 5i. Os denominadores formam uma seqüência natural de inteiros, 
iniciando por 10, logo, da forma 9 + i, com o índice i variando de 1 até 
30. Então, a soma pode ser escrita assim: 
30
1
485 5
9i
i
i=
−
+∑
Confira os valores de xi = i
i
+
−
9
5485 na tabela seguinte:
i = 1 2 3 4 ... 30
i
i
+
−
9
5485
Exemplo 10. O somatório expressa a soma de cinco 
parcelas xi = 10i -1, conforme tabela seguinte:
i = 1 2 3 4 5
xi = 10i - 1 10.1-1= 9 10.2-1= 19 10.3 – 1= 29 10.4 – 1= 39 10.5 -1 = 49
Logo, temos = 9 + 19 + 29 + 39 + 49
12
Matemática Discreta
1.2 Propriedades do somatório e algumas 
somas especiais
No desenvolvimento de somatórios, algumas propriedades 
merecem destaque pela simplificação que emprestam aos cálculos.
1.2.1 Propriedades
a) ∑∑∑
===
+=+
n
ki
i
n
ki
ii
n
ki
i yxyx )(
b) ∑∑
==
=
n
ki
i
n
ki
i xxc .c. .
c) ( )1 c
n
i k
c n k
=
 
  
= − −∑ .
d) 
1 1 1 1
 
m n n m
ij ij
i j j i
x x
= = = =
=∑∑ ∑∑ . (somatório duplo)
1.2.2 Demonstrações
a) =+∑
=
)( i
n
ki
i yx (xk + yk) + (xk+1 + yk+1) + ... + (xn + yn) 
= (xk + xk+1 + ... + xn) + (yk + yk+1 + ... + yn) 
= ∑∑
==
+
n
ki
i
n
ki
i yx .
b) . =∑
=
n
ki
ixc c.xk + c.xk+1 + c.xk+2 + ... + c.xn = 
= c.(xk + xk+1 + xk+2 + ... + xn) = c. ∑
=
n
ki
ix
c) =∑
=
n
ki
c c + c + c + ... + c = c(n-k+1).
d) Consultar as referências bibliográficas.
1.2.3 Somas Especiais
As identidades seguintes são bastante úteis no cálculo de somas, 
13
Matemática Discreta
notadamente quando se deseja calcular quantas operações são 
executadas em programas de computador envolvendo laços (for).
a) ∑
=
n
i
i
1 
= 
2
)1( nn +
Prova: Bem, desenvolvendo o somatório, obtemos 
∑
=
n
i
i
1
 = 1 + 2 + 3 + 4 + ... + n. Trata-se da soma S dos termos de uma 
Progressão Aritmética cujo termo inicial a1 = 1 e termo final an = n e 
razão r = 1. Sabemos que a soma S = 
2
)( 1 naa n+ .
Assim, 1 + 2 + 3 + 4 + ... + n = 
2
)1( nn + .
b) ∑
=
−
n
i
i
1
)12( = n2.
Prova: ∑
=
−
n
i
i
1
)12(
 
= 1 + 3 + 5 + 7 + ... + (2n – 1) é a soma S dos n 
primeiros números inteiros ímpares positivos. Trata-se da soma S dos 
termos de uma Progressão Aritmética de termos inicial 1 e termo final 
2n - 1, logo, podemos escrever: S = 2
2
2
.2
2
).121( nnnn ==−+
c) )1()2(
1
+=∑
=
nni
n
i
Prova: =∑
=
n
i
i
1
)2(
 
2 + 4 + 6 + 8 + ... + 2n é a soma S dos n primeiros 
números inteiros pares positivos. Trata-se da soma S dos termos de 
uma Progressão Aritmética de termos inicial 2 e termo final 2n, logo, 
podemos escrever S = )1(
2
)22( +=+ nnnn
d) 
Veja demonstração nas referências.
Bom, como você poderá utilizar as somas especiais? Veja alguns 
1 + 2 + 3 + 4 + ... + 
n = 
2
)1( nn+ .
É a soma dos 
n primeiros 
números inteiros 
positivos!
Atenção
1 + 3 + 5 + 7 + ... + 
(2n-1) = n2
É a soma dos 
n primeiros 
números 
ímpares!
Atenção
A soma dos n 
primeiros inteiros 
pares positivos é
2 + 4 + 6 + 8 + ... + 
2n = n(n+1)
Atenção
12 + 22 + 32 + 
42 + ... + n2 = 
É a soma dos 
quadrados dos 
n primeiros 
números inteiros 
positivos!
Atenção
14
Matemática Discreta
exemplos.
Exemplo 1. Se você quer saber a soma S = 1 + 2 + 3 + 4 + ... + 
100, poderá fazer uso da identidade ∑
=
n
i
i
1
 = 
2
)1( nn + . De fato,
1 + 2 + 3 + 4 + ... + 100 =
Exemplo 2. Qual é o valor da soma 21 + 22 + 23 + ... + 79?
Observe que:
21 + 22 + 23 + ... + 79
= 1 + 2 + 3 + ... + 79 – (1 + 2 + 3 + ... + 20)
= = 
Exemplo 3. Qual o valor da soma S dos números ímpares entre 1 
e 79?
Observe que S = 1 + 3 + 5 + ... + 79.
Como os números são ímpares, eles são da forma xi = 2i - 1, para 
valores inteiros de i, de modo que, para i = 40, temos x40 = 2(40) – 1 
= 79. Assim, usando a identidade ∑
=
−
n
i
i
1
)12( = n2, a soma S pode ser 
escrita a forma seguinte: 
S = 1 + 3 + 5 + ... + 79 = = 402 = 1.600
Exemplo 4. Como calcular a soma S de todos os números pares 
entre 98 e 234? Você pode calcular essa soma fazendo uso da 
identidade )1()2(
1
+=∑
=
nni
n
i
.
Observe que
98 + 100 +102 + 104 + ... + 234
= 2 + 4 + 6 + ... + 234 – (2 + 4 + 6 + ... + 96)
= = 117(118) – 48(49) = 13.806 – 2.352 = 11.454
Exemplo 5. Como proceder para calcular a soma dos quadrados 
15
Matemática Discreta
dos 30 primeiros números inteiros positivos? Você quer calcular a 
soma S = 12 + 22 + 32 + 42 + ... + 302 e deverá fazer uso da identidade 
.
De modo que
S = 12 + 22 + 32 + 42 + ... + 302
= 
30
2
1
30.(30 1).(2.30 1) 30.(31).(61) 9455
6 6i
i
=
+ += = =∑ .
Como demonstração de que você entendeu o emprego da 
identidade , calcule a soma 172 + 182 + 192 + 
... + 452.
1.3 Dígito Verificador
Você já percebeu que alguns números de fundamental importância 
para nós, como o CPF, Conta Bancária, número de agência bancária, 
códigos de barras, constituem uma seqüência de algarismos que 
ao final tem a adição de um ou mais dígitos? Esse dígito adicional 
é denominado Dígito Verificador (DV) e é importante para se evitar 
erros na digitação de tais seqüências numéricas.
Como é calculado o dígito verificador?
Você vai conhecer alguns exemplos de cálculos desses dígitos 
verificadores. A maioria dos casos consiste em multiplicar cada um 
dos algarismos da seqüência por um peso, em geral inteiros em 
ordem crescente ou decrescente e tomar a soma S desses produtos. 
16
Matemática Discreta
Em seguida, dividir essa soma por um inteiro p (em geral 10 ou 11) 
e calcular o resto da divisão da soma S por p. Os restos da divisão 
de S por p são 0, 1, 2, ... , p - 1. Esses restos serão indicados pela 
expressão S mod p. Em seguida, tomar como dígito verificador o próprio 
resto, se menor do que 10. Se não, alternativas podem ser usadas. 
Conheça agora alguns exemplos da concepção e cálculos de dígitos 
verificadores:
Exemplo 1. Considere o número de matrícula de uma escola 
constituído por sete algarismos N1.N2.N3.N4.N5.N6 - D, onde D é o 
dígito verificador calculado da seguinte maneira:
Vamos multiplicar os algarismos da matrícula, da esquerda para 
direito pelos pesos 7, 6, 5, 4, 3 e 2. Em seguida calculemos a soma S = 
7.N1 + 6.N2 + 5.N3 + 4.N4 + 3.N5 + 2.N6. Observe que S = 
Definimos D = 11 – Smod 11 onde Smod 11 = resto da divisão de S por 
11
Se o valor encontrado para D for 10 ou 11, ponha D = 0.
Vamos calcular o dígito D da seguinte matrícula 240134-D.
Inicialmente, calculemos a soma S. Observe que a matrícula 
240134 – D tem os dígitos N1 = 2, N2 = 4, N3 = 0, N4 = 1, N5 = 3 e N6 = 
4, de modo que podemos escrever:
S = ∑
=
−
6
1
).18(
i
iN
= 7.N1 + 6.N2 + 5.N3 + 4.N4 + 3.N5 + 2.N6
= 7 . 2 + 6 . 4 + 5 . 0 + 4 . 1 + 3 . 3 + 2 . 4
= 14 + 24 + 0 + 4 + 9 + 8 = 59.
O valor de Smod 11 = 59mod 11 = 4. Isto é, 59mod11 = 4, pois o resto da 
divisão de 59 por 11 é 4.
O digito verificador é calculado assim: D= 11 - Smod 11 = 11 - 4 = 7.
A matricula é 240134-7.
Agora, verifique se entendeu como o digito verificador dessa 
matrícula foi calculado, efetuando os cálculos do dígito D da matrícula 
451236 – D. Você deve encontrar o valor D = 7. E então, acertou?
Exemplo 2. Uma rotina muito utilizada por programadores em 
17
Matemática Discreta
softwares comerciais é a validação do Cadastro de Pessoas Físicas 
- CPF que serve para identificar cada indivíduo no país. O número 
do CPF é constituído de 11 dígitos D1D2D3 ... D7D8D9 – D10D11, sendo 
os dois últimos os dígitos de verificação, calculados da seguinte 
maneira:
Dígito D10:
D10 = 11 - , onde S1 = .
Caso D10 resulte em 11 ou 10, ponha D10 = 0.
Dígito D11:
D11 = 11 - [ ]2S mod 11, onde S2 = .
Caso D11 resulte em 10 ou 11, ponha D11= 0
Vamos calcular os valores dos dígitos D10 e D11 do CPF 234.939.448 
–C10C11.
Inicialmente, o CPF apresenta os seguintes dígitos: D1= 2, D2 = 3, 
D3 = 4, D4 = 9, D5 = 3, D6 = 9, D7 = 4, D8 = 4 e D9 = 8.
No cálculo do digito D10 é necessário calcular inicialmente a soma 
S1.
S1 = 
= 10.D1 + 9.D2 + 8.D3 +7.D4 + 6.D5 + 5.D6 + 4.D7 + 3.D8 + 2.D9
= 10.2 + 9.3 + 8.4 + 7.9 + 6.3 + 5.9 + 4.4 + 3.4 + 2.8
= 20 + 27 + 32 + 63 + 18 + 45 + 16 + 12 + 16 = 249
(S1)mod11 = 249mod 11 = 7
O digito D10 = 11 – 7 = 4
A rotina do dígito D11 requer a soma S2.
S2 = 
= 11.D1 + 10.D2 + 9.D3 + 8.D4 + 7.D5 + 6.D6 + 5.D7 + 4.D8 + 3.D9 
+ 2.D10
= 11.2 + 10.3 + 9.4 + 8.9 + 7.3 + 6.9 + 5.4 + 4.4 + 3.8 + 2.4
= 22 + 30 + 36 + 72 + 21 + 54 + 20 + 16 + 24 + 8 = 303
(S2)mod 11 = 303mod11 = 6.
18
Matemática Discreta
De modo que o dígito D11 = 11 – 6 = 5.
E o CPF é 234.939.448 – 45.
Atenção
Você observou que os pesos que multiplicam os nove 
primeiros algarismos do CPF são 10, 9, 8, ... , 2, no cálculo do 
primeiro digito verificador D10 e que os pesos usados no cálculo 
do segundo digito verificador D11 são 11, 10, 9, ... , 2?
E agora, como teste, experimente calcular os dois dígitos 
verificadores do seu próprio CPF!
Exemplo 3. O Código de Barras EAN – 13 desenvolvido nos 
Estados Unidos por volta de 1970 é um dos mais usados no mundo na 
identificação dos produtos. Por ser lido por leitura ótica, os códigos de 
barras, agilizam processos de armazenagem, transporte de produtos, 
controle do estoque e de vendas. As barras armazenam informações 
sobre o produto no computador. O código EAN consiste em uma 
seqüência de 13 dígitos: N1.N2.N3.N4. ... .N13, distribuídos em três 
campos, de modo que os três primeiros dígitos identificam o país onde 
o produto foi fabricado (789, no caso do Brasil), o segundo campo 
identifica o fabricante, os próximos dígitos determinam o produto. O 
último dígito N13 é o dígito de controle.
Para o cálculo do dígito verificador do EAN 13, inicialmente 
devemos multiplicar os algarismos de ordem ímpar da seqüência 
N1.N2.N3.N4. ... .N12 pelo peso 1 e os algarismos de ordem par pelo 
19
Matemática Discreta
peso 3, em seguida somar os produtos. A soma S correspondente 
será S = 1.N1 +3.N2 + 1.N3 + 3.N4 + ... + 1.N11+ 3.N12 que escrita sob a 
forma se somatório, tomará a expressão S = ).3().1(
6
1
2
6
1
12 ∑∑
==
− +
i
i
i
i NN .
O digito N13 é definido por N13 = 10 – Smod 10.
Caso N13 resulte em 10, ponha N13 = 0.
Vamos verificar se o digito verificador do EAN da figura acima está 
calculado corretamente?
A figura acima mostra o EAN 789 12345 6789 5, o valor da soma 
S será:
S = 1.7 + 3.8 + 1.9 + 3.1 + 1.2 + 3.3 + 1.4 + 3.5 + 1.6 + 3.7 + 1.8 + 
3.9
= 7 + 24 + 9 + 3 + 2 + 9 + 4 + 15+ 6 + 21 + 8 + 27 = 135
Como Smod 10 = 135mod 10 = 5, temos que o digito N13 = 10 - 5 = 5. 
Está correto o digito verificador do EAN.
Agora você tem a tarefa de calcular o digito verificador do EAN 789 
61894 2011 N13 de uma garrafa de vinho produzido no Rio Grande do 
Sul. E então, achou N13 = 0?
Aprenda Praticando - Exercício Proposto 1.1
Demonstre que você entendeu bem os assuntos desse capítulo, 
resolvendo os exercícios propostos. As respostas dos exercícios de 
número par são apresentadas logo a seguir. Se tiver dúvidas, procure 
saná-las com professores executores e tutores da disciplina em fóruns 
de discussão que serão formados.
1. Escreva as expressões abaixo usando a notação de somatório.
a) 1 + 3 + 5 + 7 + 9 + ... +35 = b) 3 + 5 + 7 + 9 + ... + 57 =
c) 2 + 4 + 6 + ... + 220 = d) 53 +73 + 93 + ... + 1233 =
20
Matemática Discreta
e) 1 . 2 + 2 . 3 + 3 . 4 + 4 . 5 + ... + 30 . 31 = f) 
g) 11 + 21 + 31 + 41 + ... + 121= h) 1 + 4 + 9 + 16 + 25 + 36 =
i) j) 
k) (2 . 1 + 3) + (2 . 2 + 5) + (2 . 3 + 7) + ... + (2 . 15 + 31) =
l) 2 + 2 + 2 + 2 + 2 + 2 + 2 = m) 3 . 3 + 3 . 4 + 3 . 5 + ... + 3 . 17 =
2. Desenvolver os seguintes somatórios:
a) b) ∑
=
5
0
2
i
i c) )17(
5
1
∑
=
−
i
i
d) 2
4
0
)21( i
i
+∑
=
e) ∑
=
−
5
0
6
i
ia f) ∑
=
6
1j
jx
g) =+∑∑
==
6
4
3
1 2
1
2
1
i
i
i
i h) ∑
=
−
5
1
).12(
i
iDi i) 
j) ∑
=
5
1
.
i
iNi k) ∑
=
6
1i
ia l) ∑
=
n
i
ib1
1
m) ))((
3
1
4
2
∑ ∑
= =
+
i j
ji n) ))32((
3
1
4
2
∑ ∑
= =i j
ji
o) ∑ ∑
= =



5
1
5
1i j
jiba
p) q) r) ∑ ∑
= =



4
1
4
1
,
i j
jia
3. Escrever sob a forma de somatório as seguintes expressões:
 
 
 
4. Escrevam na forma de somatório, os seguintes dados:
a) A soma S dos 50 primeiros termos da série
....
4
991
3
994
2
997
1
1000 ++++
21
Matemática Discreta
b) A soma S dos 15 primeiros termos de
S = 
1
16384.......
144
8
169
4
196
2
225
1 +++++
5. As contas do Banco Baú da Sorte apresentam numeração com 
seis dígitos: N1.N2.N3.N4.N5.N6 seguidos de um dígito D de 
controle, calculado por :
Se o valor encontrado para D for 10 ou 11, ponha D = 0.
Calcule o dígito verificador C para as contas de números 
134792-D, 245318-C e 875346-D.
6. Suponha que o CNPJ de uma empresa seja N1 N2 N3 N4 N5 N6 
N7 N8 / N9 N10 N11 N12 – C1 C2.
Rotina para se obter os dígitos verificadores C1 e C2:
Cálculo de C1
1º. Multiplicamos da direita para esquerda os algarismos do CNPJ 
(de N12 até N1) pelos pesos 2, 3 e assim sucessivamente até 
9, e em seguida, recomeçamos multiplicando por 2, 3, etc, até 
encontrar o algarismo mais à esquerda N1.
2º. Calculamos a soma S1 dos resultados dessas multiplicações.
3º. Calculamos o resto R da divisão de S1 por 11.
4º. O dígito verificador será C1 = 11 – R. Se C1 = 10 ou 11, ponha 
C1 = 0.
Cálculo de C2
1º. Incorpore ao CNPJ o dígito C1 calculado, fazendo-o ocupar a 
posição N13. Multiplique da direita para esquerda os algarismos 
da forma utilizada para o calculo de C1.
2º. Proceda com a mesma rotina para calcular C1.
a) Forneça uma expressão matemática para a rotina acima 
descrita.
b) Calcular os dígitos do CNPJ 05559748/0001-C1C2
22
Matemática Discreta
7. Livros são identificados pelo ISBN (International Standard Book 
Number) com 9 dígitos N1, N2, N3 , ... , N9 que identificam a 
sua publicação. Esses nove dígitos são distribuídos em blocos 
que identificam a língua, a editora, o número designado pela 
companhia editora e são seguidos de um dígito verificador D, 
que pode ser um número inteiro de 0 a 9 ou a letra X (usada 
para representar o número 10). O cálculo de D é feito da 
seguinte maneira:
D = 
a) Calcule o dígito verificador D do ISBN 85.363.0361-D encontrado 
no livro de Matemática Discreta, do autor Seymour Lipschutz, 
editado pela Bookman.
b) Repetir o exercício, para o ISBN encontrado no livro de 
Programação utilizado por você.
c) Certo livro tem ISBN 85-221-02Q1 – 0. Calcule o valor de Q.
8. Calcule os dígitos verificadores do CPF 033.939.844-D10.D11 
usando os métodos descritos no Exemplo 2.
9. Pesquisar na Internet (www.google.com.br) o seguinte: “Dígito 
Verificador”. Você encontrará diversas formas do uso de dígito 
verificador, notadamente em inscrições de firmas comerciais 
na Secretaria da Fazenda dos estados brasileiros. Conheça 
alguns exemplos e expresse a fórmula do cálculo da inscrição 
por meio de somatório.
10. Calcule i
i
i yx .
6
1
∑
=
 sabendo que xi = 7 - i e yi = 1 + i2.
11. Dado que x1 = 1, x2 = 3, x3 = 5, x4 = 7, x5 = 9 e f1 = 1, f2 = 5, 
f3 = 3, f4 = 3, f5 = 5, calcule:
a) ∑
=
5
1i
ix b) ∑
=
5
1i
if c) ∑
=
5
1
.
i
ii fx d) ∑
=
5
1
2 .)(
i
ii fx
e) Mostre que 0)(
5
1
=−∑
=
xx
i
i , onde é a média aritmética dos xi.
12. Sabendo que 
2
)1(
1
+=∑
=
nni
n
i
, nkk
n
i
.
1
=∑
= 
e que ∑∑
==
=
n
1i
i
1
xk. .
n
i
ixk , 
23
Matemática Discreta
calcule:
a) ∑
=
100
1i
i b) c) d) 
e) 51 + 52 + 53 + ... + 183 =
f) 31 + 32 + 33 + ... + 101 =
g) 10(55) + 10(56) + 10(57) + ... + 10(99) =
13. Sabendo que 2
1
)12( ni
n
i
=−∑
=
, calcule:
a) ∑
=
−
100
1
)12(
i
i b) ∑
=
−
100
41
)12(
i
i
c) 1 + 3 + 5 + 7 + ... + 31 = d) 2.1 + 2.3 + 2.5 + ... + 2.51 =
e) 21 + 23 + 25 + 27 + ... + 87= f) 4(41) + 4(43) + 4(45) + ... + 4(87) =
Respostas dos Exercícios 1.1
2.
a) 1 + 3 + 5 + 7 + 9 b) 1 + 2 + 4 + 8 + 16 + 32
c) 6 + 13 + 20 + 27 + 34 d) 12 + 32 + 52 + 72
e) a6 + a5 + a4 + a3 + a2 + a1 f) x1 + x2 + ... + x6
g) 
h) 1.D1 + 3.D2 + 5.D3 + 7.D4 + 9.D5
i) 9.X1 + 8.X2 + 7.X3 + ... + 1.X9
j) 1.N1 + 2.N2 + 3.N3 + 4.N4 + 5.N5
k) a1 + a2 + ... + a6 l) 
nbbbb
1.....111 321 +++
24
Matemática Discreta
m) = ))((
3
1
4
2
∑ ∑
= =
+
i j
ji = 
= [(1 + 2) + (1 + 3) + (1 + 4)]
+ [(2 + 2) + (2 + 3) + (2 + 4)]
+ [(3 + 2) + (3 + 3) + (3 + 4)]
= [12] + [15] + [18] = 45
4. a) 
6. a) C1 = 11- 
Se C1 = 10 ou 11 ponha C1 = 0
C2 = 11- 
Se C2= 10 ou 11 ponha C2 = 0
b) 05559748/0001-77
8. 033.939.844-20
10. i
i
i yx .
6
1
∑
=
 = ∑
=
+−
6
1
2 )1).(7(
i
ii
= 6.2 + 5.5 + 4.10 + 3.17 + 2.26 + 1.37
12. a) 5.050 b) 15.150 c) 9.800 d) 1.250
Conclusão
 
No primeiro capítulo deste fascículo, você aprendeu o uso do 
somatório e como as suas propriedades facilitam o cálculo de somas. 
Além disso, conheceu o emprego de somatório na definição do dígito 
de verificação em numerações especiais como CPF, código de barras, 
ISBN, CNPJ, entre outros.
25
Matemática Discreta
Saiba Mais
Você poderá aprender mais sobre somatório, consultando os 
seguintes livros e sites:
 GERSTING, Judith L. Fundamentos Matemáticos para a 
Ciência da Computação. Tradução Valéria de Magalhães Iorio. 
Rio de Janeiro: LTC, 2004.
 LIPSCHUTZ, Seimour; LIPSON, Marc Lars. Teoria e Problemas 
de Matemática Discreta. Porto Alegre: Bookman, 2004.
 http://problemasteoremas.wordpress.com/2007/11/20/somatorio-duplo/
 http://www.ean.com.br
Orientação de Estudos
A demonstração da propriedade 1.2.1 letra d pode ser feita por 
você. Tente fazê-la e discuta o resultado com seus colegas nos fóruns 
de discussão que serão formados com esse objetivo.
A propriedade 
1 1 1 1
 
m n n m
ij ij
i j j i
x x
= = = =
=∑∑ ∑∑ é uma identidade que mostra 
como podemos somar os elementos de uma tabela constituída por m 
linha e n colunas: como a soma dos elementos xij situadosnas linhas 
da tabela ou como soma dos elementos situados nas colunas.
26
Matemática Discreta
Mostre a igualdade 
1 1 1 1
 
m n n m
ij ij
i j j i
x x
= = = =
=∑∑ ∑∑ se verifica, provando que 
a soma S dos elementos da tabela pode ser feita de duas maneiras: 
somando-se as linhas i ou somando-se as colunas j, de modo que:
S = lm
lll SSSS ++++ .....321 e S = 
cS1 + 
c
nS+++ .................S S
c
3
c
2 , 
o que justifica a troca da ordem no somatório duplo.
27
Matemática Discreta
Capítulo 2 - Matrizes: 
armazenando dados
Neste capítulo serão feitas revisões sobre matrizes de entradas 
reais, os diversos tipos de matrizes e as operações de soma, 
multiplicação de matriz por um número real e multiplicação de 
matrizes apropriadas. Trataremos também de matrizes booleanas 
e as operações definidas nesse tipo de matriz. Na literatura de 
informática, as matrizes são conhecidas por diversos nomes, entre os 
quais arranjos, arrays, etc. Nesse caso, as matrizes são estruturas 
que armazenam dados.
2.1 Matriz
Uma matriz m x n é uma tabela de mn números dispostos em m 
linhas e n colunas e será denotada assim A = (aij)m x n. O tamanho da 
matriz é a dimensão m x n da tabela seguinte:
A = 
A i-ésima linha de é 
28
Matemática Discreta
A j–ésima coluna de A é 
Exemplo 1. A matriz A seguinte é do tipo 4 x 3, sua 3ª linha é 
 e sua 3ª coluna é














8- 
2-
0 
3-
 A = 














8- 1- 9
2- 2- 2
0 1- 7
3- 2 1
 
Existem duas maneiras de denotar um elemento individual de uma 
matriz: aij ou representam o elemento da matriz A situado na 
posição ij, ou seja, que está na linha i na coluna j.
Exemplo 2. Podemos usar matrizes como modelo para representar 
dados. As observações sobre as temperaturas médias em três cidades 
diferentes ao longo de uma semana, podem ser representadas por uma 
matriz T do tamanho 3x7, cujo elemento genérico tij é a temperatura 
média (em graus Celsius) da cidade i no dia j. A matriz T é a tabela 
seguinte:
1 (Dom) 2 (Seg) 3 (Ter) 4 (Qua) 5 (Qui) 6 (Sex) 7 (Sab)
Cidade 1 23 23 24 25 21 24 25
Cidade 2 17 16 18 19 15 16 17
Cidade 3 29 27 28 29 31 30 30
Na matriz T podemos verificar que a temperatura média na cidade 
2 no dia 5 é t25 = 15°C e que a temperatura mínima na cidade 3 ocorreu 
no dia 2 com valor t23 = 27°C.
29
Matemática Discreta
2.2 Definição
Duas matrizes A = (aij)m x n e B = (bij)r x s são iguais se e somente se 
elas têm o mesmo tamanho, ou seja, m = r e n = s, e se os elementos 
que ocupam posições iguais são iguais.
Exemplo 3. O valor de x nas matrizes 




 +=








=
8 4
1x x
 B e 
8 x
3 2
 2A tal 
que A = B é x =2.
2.3 Tipos especiais de matrizes
Ao trabalharmos com matrizes, observamos que existem algumas 
que, seja pela quantidade de linhas ou colunas, ou pela natureza de 
seus elementos, têm propriedades que as diferenciam das demais. 
Além disso, estes tipos de matrizes surgem com freqüência na prática 
e, assim, recebem nomes especiais. Recordaremos alguns tipos.
• Matriz Quadrada é uma matriz n x n, isto é, tem o número de 
linhas igual ao número de colunas. Como exemplo, temos as 
matrizes A e B do Exemplo 2.
Numa matriz quadrada, por exemplo, A3x3 = os 
elementos aij tais que i = j são a11, a22 e a33 e constituem a diagonal 
principal de A. Caso a matriz seja A = 










7 1 5
6 2 0
5 4 8
, a diagonal principal 
é constituída pelos elementos 8, 2 e 7.
• Matriz Nula é aquela em que aij = 0 para todo i e j.
Por exemplo, A = 










=





0 0 
0 0 
0 0 
 B e 
0 0 0 
0 0 0 
.
• Matriz Coluna (matriz unidimensional) é aquela matriz 
A = (ai, j)i x 1, i = 1 , 2, 3, ... , m, que possui uma única coluna.
30
Matemática Discreta
Exemplo: 














8- 
2-
0 
3-
.
• Matriz Linha (matriz unidimensional) é a matriz A = (ai, j)ixj, j = 1, 
2, 3, ..., n, que possui apenas uma linha.
Exemplo: .
• Array. Freqüentemente, em programação, dados são 
armazenados em vetores (arrays), isto é, listas em que os 
elementos são indexados por um ou mais índices. Um array 
unidimensional é uma matriz linha ou matriz coluna e sua 
dimensão é o número de índices. Por exemplo, as notas em 
Matemática Discreta de dez alunos do Curso de Sistemas de 
Informação podem ser listados no seguinte array:
[8,1; 5,0; 8,7; 6,0; 9,5; 6,0; 2,0; 7,8; 10,0; 5,7]
Podemos denotar todas as notas da lista pelo símbolo n e 
índices diferentes que indicam a posição de cada nota no array: 
[n1, n2, n3, ... , n10]. De modo que, n3 = 8,7 e n7 = 2,0.
• Matriz Diagonal é uma matriz quadrada onde aij = 0 para 
i j, isto é os elementos que não estão na diagonal principal 
são nulos.
Exemplo: 










1 0 0
0 3 0
0 0 2
.
• Matriz Identidade Quadrada é a matriz quadrada em que 
aij = 1 se i = j e aij = 0 para i j.
Exemplos: I3 = 










1 0 0
0 1 0
 0 0 1
 e I2 = 





1 0
0 1
.
• Matriz Simétrica é aquela matriz quadrada onde aij = aji. 
Observe que, numa matriz simétrica, a parte superior é uma 
reflexão da parte inferior, em relação à diagonal.
31
Matemática Discreta
Exemplos: 










5 8 3
8 6 2
3 2 1
 e 





3 8 
8 1-
.
Os elementos simétricos em relação à diagonal principal são 
iguais.
• Matriz Transposta. Dada uma matriz A = (aij)m x n, podemos 
obter uma matriz AT = (bij)n x m, denominada transposta de A, 
cujas linhas são as colunas de A, isto é, bij = aji.
Exemplo: A = 





2 8 1
5 3 2
 AT = 










2 5
8 3
1 2
 
Observe que é uma matriz quadrada A é simétrica se e só se:
A = AT.
Exemplo 4. Considere a matriz A = do tipo 4 x 4.
a) A soma dos elementos situados na 3ª linha de A é S = 
4
3,
1
j
j
a
=
∑ = 
a3,1 + a3,2 + a3,3 + a3,4 = 20 + 18 + 17 + 16 = 71.
b) O somatório S = ∑
=
4
1
2,
i
ia representa a soma dos elementos da 
matriz A situados na 2ª coluna.
c) Se queremos escrever a soma dos elementos da matriz A 
situados na diagonal escrevemos S = ∑
=
4
1
,
i
iia , de modo que S = 
a1,1 + a2,2 + a3,3 + a4,4 = 10 + 13 + 17 + 24 = 64.
d) O duplo somatório SL = ∑ ∑
= =



4
1
4
1
,
i j
jia representa a soma de 
todos os elementos da matriz A. Para cada valor do índice i 
no primeiro somatório, o somatório interno calcula a soma dos 
elementos da linha i, fazendo o índice j variar de 1 a 4. Desse 
modo, obtemos:
32
Matemática Discreta
SL = ∑ ∑
= =



4
1
4
1
,
i j
jia
= ( )=+++∑
=
4
1
4,3,2,1,
i
iiii aaaa
= (a1,1 + a1,2 + a1,3 + a1,4) + (a2,1 + a2,2 + a2,3 + a2,4) +
 (a3,1 + a3,2 + a3,3 + a3,4) + (a4,1 + a4,2 + a4,3 + a4,4)
= (10 + 12 + 15 + 20) + (12 + 13 + 14 + 15) +
 (20 + 18 + 17 + 16) + (21 + 22 + 23 + 24)
= 57 + 54 + 71 + 90 = 272.
 Observe que somamos os elementos de A, tomando a soma de 
cada linha.
 Agora, se você quer obter a soma dos elementos de S tomando 
a soma dos elementos das colunas, experimente fazer 
SC = ∑ ∑
= =




4
1
4
1
,
ji i
jia , obtido do somatório anterior trocando a ordem 
dos índices i e j. É claro que a soma SC resultaem 272.
2.4 Operações com matrizes
Podemos definir operações numéricas entre matrizes cujos 
elementos (entradas) são numéricos. Essas operações tornam não só 
as matrizes muito interessantes, como objeto de estudo, como úteis 
na solução de diversos problemas.
2.4.1 Adição de matrizes
A adição de matrizes é definida para matrizes de mesmo tamanho. 
Isto é, se A e B são duas matrizes de mesmo tamanho m x n, a soma 
dessas duas matrizes, denotada por A + B, é também uma matriz 
Cm x n, cujo elemento na posição ij é definido como sendo a soma dos 
elementos de A e B que ocupam a posição ij. Ou seja, se A = (aij)m x n e 
B= (bij)m x n, então C = A + B é a matriz (cij)m x n definida por cij = aij + bij.
Exemplo 5. Se 





−
=





−
=
7/3 5
25 8 B 
2/3 3
23 2 A , então:
33
Matemática Discreta
C = .
Bem, você provavelmente está se perguntando, de que modo 
pode-se empregar a soma de matrizes em situações reais? O exemplo 
seguinte responde ao questionamento.
Exemplo 6. Um fabricante de um produto produz três modelos 
A, B e C. Cada um deles é produzido parcialmente na fábrica F1 em 
Campinas e, então, finalizado na fábrica F2 em São Paulo. O custo 
de cada produto é composto pelo custo de produção e pelo custo de 
transporte. As matrizes F1 e F2 seguintes descrevem o custo dos três 
produtos em cada fábrica.
F1 = 
F2 = 
A matriz F1 + F2 = FT fornece o total dos custos de produção e 
transporte para cada produto. Assim,
F1 + F2 = 
2.4.2 Multiplicação de uma matriz por um escalar
Na seção anterior você conheceu como as matrizes podem ser 
somadas. Bem, agora, vamos mostrar quando é possível multiplicar 
uma matriz de qualquer tamanho por um número real.
34
Matemática Discreta
Se A é uma matriz m x n e k é um escalar, o produto da matriz A 
pelo escalar k, denotado por kA, é também uma matriz m x n, cujo 
elemento na posição ij é definido como sendo o produto do elemento 
de A que ocupa a posição ij pelo escalar k. Isto é, se A = (aij)m x n então 
C = kA é a matriz (cij)m x n definida por cij = k . aij
Exemplo 7. Uma empresa de material fotográfico tem loja em 
cada uma das cidades A, B e C. Um marca específica de câmera 
está disponível para venda nos modelos automático, semi-automático 
e não-automático. Cada uma dessas câmeras tem uma unidade de 
flash correspondente que é vendida juntamente com a câmera. Os 
preços de venda das câmeras e das unidades de flash são fornecidos 
pela matriz V do tipo 2x3.
V = 
Bem, se a empresa planeja reduzir os preços de venda de seus 
produtos, oferecendo desconto de 10% para pagamentos à vista, 
então a tabela de preços sofrerá alteração, de modo que cada produto 
terá seu preço multiplicado por 0,9. A matriz dos novos preços será 
obtida multiplicando a matriz V por 0,9:
0,9 . V = 
2.4.3 Multiplicação de matrizes
A multiplicação de matrizes está definida quando o número de 
colunas da primeira matriz é igual ao número de linhas da segunda 
matriz. Assim, se A é uma matriz m x p e B é uma matriz p x n, o 
produto AB é possível. Além disso, a matriz C = AB é do tipo m x n.
Para encontrarmos o elemento ij da matriz produto AB, multiplicamos 
cada um dos elementos da linha i da matriz A pelo correspondente 
elemento da coluna j da matriz B e somamos os produtos obtidos. 
Como as linhas da matriz A tem o mesmo número de elementos que 
as colunas de B, não sobram nem faltam elementos.
35
Matemática Discreta
A B C
cij = ai1b1j + ai2b2j + ai3b3j + ... + aipbpj
cij = ∑
=
p
k
jkki ba
1
 i = 1, 2, 3, ... j = 1, 2, 3, ...
Exemplo 8. Considere as matrizes A = e B = . 
O produto AB é possível, pois A é do tipo 2x3 e B do tipo 3x2, a matriz 
C = AB é 2x2, onde C = ,
c11 = 
c12 = 
c21 = 
c22 = 
Exemplo 9. Caso as matrizes A e B do Exemplo 6 sejam A = 






4 0 3
1 3 2
 e B = 










2 3
2 0
3 1
, o produto A.B será uma matriz de tamanho 
2x2 obtida multiplicando os elementos de cada linha de A (Li) pelos 
respectivos elementos de cada coluna de B (Cj). Assim,
36
Matemática Discreta
A.B = 
[ ]
[ ] 



4 0 3
 1 3 2
.






























2
2
3
 
3
0
1
= 





2212
2111
.L .
.L .L
CCL
CC
 = 





++++
++++
4.2 0.2 3.3 4.3 0.0 3.1
1.23.22.3 1.33.0 2.1
= 
Exemplo 10. Considere a matriz F1 do Exemplo 6 que fornece o 
custo dos produtos A, B e C produzidos na fábrica F1. Se a matriz 
Q3x1 = representa a quantidade produzida de cada 
produto A, B e C, por mês, o que representa a matriz produto Q.F1?
Bom, multiplicando Q por F1, obtemos:
Q.F1 = 
= [ ]150.20200.80100.40 150.70200.50100.32 ++++
= [ ]23000 23700
A matriz Q.F1 apresenta o custo de produção e de transporte de 
toda a produção mensal dos três produtos.
Que informações sobre o custo dos produtos A, B e C, a matriz 
(F1)T.QT fornece? Recorde o conceito de matriz transposta!
2.4.4 Matrizes Booleanas
Na grande maioria dos casos nós utilizamos matrizes cujos 
elementos são números reais. Desse modo, os cálculos nas operações 
37
Matemática Discreta
de adição, multiplicação por escalar e multiplicação de matrizes são 
feitos com os elementos escritos na base decimal. Mas, na tecnologia 
da informação, o uso de dados na notação binária é necessário. Os 
dados codificados em binário são muito importantes e tem aplicações 
variadas no computador, notadamente em videogames, comunicação 
por fax, transferências de dinheiro por meio de caixas eletrônicos, 
etc.
Seja A = (ai,j) uma matriz cujos elementos são os bits 0 e 1, 
entendendo que esses dígitos como valores lógicos (0 representando 
FALSO e 1 representando VERDADEIRO). Essas matrizes são 
chamadas matrizes booleanas, homenagem ao matemático inglês 
do século XIX, George Boole. 
Exemplo 11. Suponha que numa sala de aula com 30 alunos 
queremos registrar a presença (1) e a ausência (0) nos 22 dias de 
aulas do mês. A matriz booleana que apresenta o registro da presença 
às aulas é uma matriz A30x22 da seguinte forma:
A = 












1 ........ 1 1 1 1 1 1 1
..............................
0 ....... 0 1 1 1 1 1 0
1 ...... 1 0 1 1 1 0 1
O elemento aij = 0, significa que o aluno i esteve presente à aula 
do dia j. O elemento aij = 0, quando o aluno i faltou à aula do dia j.
Exemplo 12. Considere que uma rede de comunicações tem 
cinco estações com transmissores de potências diferentes. Na matriz 
A abaixo estabelecemos que aij = 1, significa que a estação i pode 
transmitir diretamente à estação j, aij = 0 significa que a transmissão 
da estação i não alcança a estação j. Veja o diagrama abaixo.
A = 
















0 1 0 0 0
1 0 1 0 0
0 1 0 1 0
0 0 1 0 1
1 1 1 1 0
O elemento a13 = 1, significa que a estação 1 transmite diretamente 
à estação 3 e a31 = 0 significa que a estação 3 não transmite 
38
Matemática Discreta
diretamente à estação 1.
Qual o significado da diagonal nula de A? A matriz A é simétrica?
A diagonal nula de A, significa que uma estação não transmite 
para si mesma. Além disso, observe que A AT, logo a matriz A não é 
simétrica. Isso significa a não comutatividade da comunicação entre 
duas estações.
2.4.5 Adição e multiplicação de matrizes booleanas
Podemos definir a adição (∨ ) e produto booleano (∧ ) de duas 
matrizes de mesmo tamanho da maneira usual, exceto pelo fato de 
que agora usamos as operações booleanasde adição e multiplicação, 
conforme tabelas a seguir:
∨ 0 1 ∧ 0 1
0 0 1 0 0 0
1 1 1 1 0 1
Tabela da 
adição
Tabela da 
Multiplicação
As tabelas acima definem a adição booleana (∨ ) e o produto 
booleano (∧ ) de acordo com a seguinte notação:
x ∨ y = Max (x, y) e x ∧ y = Min (x,y)
Se A = (aij)n x m e B = (bij)n x m são matrizes booleanas, então:
 A ∨ B = (aij ∨ bij)n x m e A ∧ B = (aij ∧ bij)n x m
Exemplo 13.
a) A soma booleana das matrizes A = 




=





1 0 
1 0 
 B 
1 0
0 1
e é dada por 
 
1 0
1 1
 
11 00
10 01
 
1 0 
1 0 
 
1 0
0 1
 BA 




=





∨∨
∨∨
=




∨




=∨
b) O produto booleano das matrizes A = 




=





0 1
1 1
 B 
1 0 
1 1 
 é dado 
por A ∧ B = 




=





∧∧
∧∧
=




∧





0 0
1 1
 
 01 10
11 11
0 1
1 1
 
1 0 
1 1 
.
39
Matemática Discreta
Agora, é com você. Considere as matrizes booleanas A= 










1 1 1
1 0 0
1 0 1
, 
B = 










0 1 0
1 1 0
0 1 1
, C = 










1 0 0
1 1 1
1 0 1
. Efetue as seguintes operações booleanas:
a) A ∧ B b) A ∨ B c) B ∨ C d) A ∨ A e) B ∧ B
f) (A ∧ B) ∨ C g) A ∨ (C ∧ B)
2.4.6 Multiplicação de matrizes booleanas
A multiplicação de matrizes booleanas (Aij)m x p e (Bij)p x n denotada 
por A ⊗ B é definido como a matriz C do tipo m x n tal que 
cij = = (ai1 ∧ bij) ∨ (ai2 ∧ b2j) ∨ (ai3 ∧ b3j) ∨ ... ∨ (aip 
∧ bpj)
Perceba que esse produto é obtido multiplicando cada linha 
de A pelo produto booleano e somando esses produtos pela soma 
booleana.
Exemplo 14. Calcule o seguinte A ⊗ B nos seguintes casos:
a) A = 





 1 1 0
1 0 1
 B = 










0 0
 1 1
 1 0
b) A= 










1 1 1
1 0 0
1 0 1
 B = 










0 1 0
1 1 0
0 1 1
a) A ⊗ B = 





 1 1 0
1 0 1 ⊗ 










0 0
 1 1
 1 0
 = 
 
Agora, faça o exercício b.
Você deverá chegar à matriz booleana A ⊗ B = 










1 1 1
0 1 0
1 1 1
Exemplo 15. Os aeroportos 1, 2 e 3 estão interligados por vôos 
40
Matemática Discreta
diretos e/ou com escala. A matriz M = (ai,j)3x3 é tal que ai,j = 1, se há 
vôo direto do aeroporto i para o aeroporto j, e ai,j = 0, se não há vôo 
direto do aeroporto i para o aeroporto j é 
M = 










0 0 1
1 0 1
0 1 0
.
Os vôos de um aeroporto para outro são representados no 
diagrama seguinte:
Observe que não há vôos diretos 
do aeroporto 1 para o aeroporto 3, 
nem do 3 para 2. Mas, há esses 
vôos com escala. Isto é, partido de 1 
podemos alcançar 3, passado por 2. 
Além disso, partindo de 3 podemos 
atingir 2 passando por 1.
A matriz M2= (bi,j) onde M2 = M ⊗ M tal que bij =1 significa que há 
vôo do aeroporto i para o aeroporto j com escala, caso contrário, bij = 
0. De fato,
M ⊗ M = 










0 0 1
1 0 1
0 1 0
 ⊗ 










0 0 1
1 0 1
0 1 0
= 










0 1 0
0 1 1
1 0 1
O diagrama ao lado indica os 
vôos com escala.
41
Matemática Discreta
Aprenda Praticando - Exercício Proposto 2.1
Verifique se você entendeu bem os assuntos desse capítulo, 
resolvendo os exercícios propostos. As respostas dos exercícios 
de número par são apresentadas logo a seguir. Se tiver dúvidas, 
procure saná-las com professores e tutores da disciplina em fóruns de 
discussão que serão montados para esse fim.
1. Considere a matriz B = 












3 1 3- 0 
1 4 1- 2 
2 1 0 3 
1 2- 2 1 
. Calcule:
a) ∑
=
4
1
,2
j
jb b) ∑
=
4
1j
bi,3 c) ∑
=
4
1i
 (∑
=
4
1i
 bi,j) d) 
2. Calcule o produto A.B nos seguintes casos:
a) A = [ 1 -1 0] e B = 










− 2
1 
2 
b) A = 




−
1 3-
2 1
 e B = 





1- 1
2- 2
c) A = 





 1 2 1
0 3 2
 e B = 










2- 2 
 1 1- 
 1 2 
3. Se A = 





1 3
5- 2
 e B = 





3 1-
2 4-
, calcule:
a) A2 = A.A b) A3 c) B2 d) B3
e) Mostre que A.B B.A f) (A+ B)T
g) (A.B + A)T h) AT.BT + B
4. Considere as matrizes A = 





 1 2 1
0 3 2
 B = 










2- 2 
 1 1- 
 1 2 
. Calcule, 
quando possível, os seguintes produtos:
42
Matemática Discreta
a) AT.BT b) B.A c) BT.AT
5. Suponha que A, B e C são matrizes de números, respectivamente 
de ordens 3 x 7, 7 x 2 e 2 x 5. Qual o modo mais eficiente de 
calcular o produto ABC, é (A.B).C ou A.(B.C)? Justifique sua 
resposta computando o número de multiplicações que se efetua 
em cada caso.
6. Considere as matrizes indexadas 2 x 2 Bi definidas por 
Bi = 



++
−
2i 1i
i 1i
 com i N*.
a) Escreva as matrizes B1, B2, ..., B5
b) Calcule o valor da soma S = ∑
=
5
1i
iB
c) Determine o valor da soma S = t
i
iB )(
5
1
∑
=
d) Calcule a soma S = ).(
3
1
T
i
i
i BB∑
=
7. Considere a matriz A= (ai,j), do tipo 30 x 30:
a) Escreva os elementos de A.
b) Expresse sob a forma de somatório, a soma dos elementos 
situados na 12ª linha de A.
c) Expresse, sob a forma de somatório, a média aritmética dos 
elementos situados na 25ª coluna de A.
d) Expresse sob a forma de somatório, a soma dos elementos de 
A situados na 13ª coluna.
e) O que significa o valor encontrado para o seguinte somatório
MP = ?
8. Seja A = 





− 0 12
 x 2 2
x . Qual o valor de x tal que A
T = A
9. Os aeroportos 1, 2, 3 e 4 estão interligados por vôos diretos e/
43
Matemática Discreta
ou com escala. A matriz M = (ai,j)4x4 é tal que ai,j = 1, se há vôo 
direto do aeroporto i para o aeroporto j, e ai,j = 0, se não há vôo 
direto do aeroporto i para o aeroporto j é 
M = 












0 0 1 1
1 0 0 1
0 1 0 0
0 0 1 0
.
a) Faça um diagrama representando os vôos diretos.
b) Calcule a matriz M2= (bi,j) onde M2 = M ⊗ M tal que bi,j =1 significa 
que há vôo do aeroporto i para o aeroporto j com escala e faça 
um diagrama representativo da situação.
10. Uma fabricante produz janelas e portas e cada um desses 
produtos passa por um processo de montagem e por um 
processo de acabamento. O tempo gasto em cada um desses 
processos é fornecido (em horas) pela matriz
A= 










Porta 2 2
Janela 4 3
Acabamento Montagem
.
O fabricante tem uma fábrica em Caruaru e outra em Campina 
Grande e o custo de cada um desses processos, por hora 
trabalhada é fornecido pela matriz
B = 
Calcule a matriz A.B e diga o significado dos elementos do produto 
A.B.
11. Suponha seis pessoas – Adriano (A), Bernardo (B), Carla (C), 
Daniele (D), Eunice (E) e Fábio (F) – que adoram uma fofoca 
via telefone. Cada dia Adriano conversa com Bernardo e Fábio;Bernardo conversa com Adriano, Carla e Daniela; Carla com 
Bernardo, Daniele e Eunice; Daniele com Bernardo, Carla, 
Eunice e Fábio; Eunice conversa com Carla, Daniele e Fábio; e 
Fábio conversa com Adriano, Daniele e Eunice. Tudo que uma 
pessoa conversa com outra num dia, ela repassa a fofoca para 
as outras no dia seguinte.
44
Matemática Discreta
a) Modele este esquema de fofocas por telefone utilizando uma 
matriz booleana M = (mi,j)6x6 onde mi,j = 1 significa que a pessoa 
i conversa com a pessoa j. Caso contrário, mi,j = 0.
b) M é simétrica?
c) Quantos dias, no mínimo, uma fofoca recebida por Adriano na 
segunda–feira leva para chegar aos ouvidos de Daniele?
12. Na matriz booleana A3x3 abaixo, a letra L significa ligado (1) e 
a letra D significa desligado (0).
A = 










L L D
D L D
D L L
.
a) Encontre uma matriz B3x3 do tipo ligado/desligado tal que A v B 
seja uma matriz em que todos os elementos sejam ligado.
b) Encontre uma matriz B3x3 do tipo ligado/desligado tal que A ∧ 
B seja uma matriz em que todo elemento seja desligado.
Respostas dos Exercícios 2.1
2. a) [ ]1 b) 



5 5-
0 0 
 c) 



1 2
5 1
4. a) 










2- 1 1
2 1- 8
2 1- 5
 b) 










2- 2 2 
1 1- 1-
1 8 5 
 c) 
6. a) B1 = 2B ,3 2
1 0




, B2= ,4 3
2 1




 B3= 



5 4
3 2
, B4 = e B = 



7 6
5 4
.
b) S = ∑
=
5
1i
iB = 
c) S = 
t
i
iB )(
5
1
∑
=
 = 
d) S = ).(
3
1
T
i
i
i BB∑
=
45
Matemática Discreta
= +







3 1
2 0
.
3 2
1 0
+







4 2
3 1
.
4 3
2 1




5 4
3 2
. 



5 3
4 2
+ 



6 5
4 3
. 



6 4
5 3
+ 



7 6
5 4
. 



7 5
6 4
8. x = 1
10. AB = 
 A matriz AB indica o custo total de fabricação de janela e portas 
nas duas fábricas.
12. a) 










D D L
L L L
L D D
 b) 










D D L
L D L
D D D
Saiba Mais
No segundo capítulo deste fascículo, você aprendeu sobre matrizes, 
as operações que nelas podemos efetuar e como as matrizes podem 
ser usadas como estrutura de armazenamento de dados. Conheceu 
também as matrizes booleanas, cujos elementos são varáveis 
booleanas, tipo Sim/Não, Ligado/Desligado. As operações entre 
matrizes booleanas foram apresentadas através de exemplos.
Você poderá aprender mais sobre matrizes, consultando os 
seguintes livros e sites:
 GERSTING, Judith L. Fundamentos Matemáticos para a 
Ciência da Computação. Tradução Valéria de Magalhães Iorio. 
Rio de Janeiro: LTC, 2004.
 KOLMAN, Bernard. Introdução à Álgebra Linear: com 
aplicações. Tradução de Alessandra Bosquilha. Rio de Janeiro: 
LTC, 2006.
 LIPSCHUTZ, Seimour; LIPSON, Marc Lars. Teoria e Problemas 
de Matemática Discreta. Porto Alegre: Bookman, 2004.
46
Matemática Discreta
 http://www.mat.ufmg.br/~elaine/GAAL/gaalt1.pdf
 http://www.funepe.edu.br:91/funepe/professores/materiais/57/MATRIZES.
ppt#256,1,matrizes
Orientação de Estudos
Você sabe como funcionam os mecanismos de busca para 
encontrar informações e acessar a internet? Eles utilizam matrizes 
para rastrear as localizações da informação, cada tipo de informação 
em uma localização, determinam a palavra-chave que aparece na 
informação e os sites da Web que tem informações em comum.
O mecanismo utilizado no site do Google, por exemplo, em vez de 
rastrear diretamente uma determinada página real na Web ou de um 
único assunto de pesquisa, ele usa uma estrutura matricial focalizando 
buscas de páginas que correspondam ao assunto pretendido.
A busca é feita utilizando uma matriz booleana Anxn, chamada 
matriz de conectividade, onde n é o número de páginas acessíveis na 
Web durante um determinado mês, de modo que todos os elementos 
assumem inicialmente o valor zero. Quando o site j está relacionado 
com o site i, define-se o elemento ai,j = 1, caso contrário ai,j = 0. Dado 
que o número de sites é bastante grande, a maioria dos elementos da 
matriz A é igual a zero. Em seguida, são listados todos os sites que 
tem conexão com o site j.
Se você quer mais informações sobre o assunto acesse o site:
www.google.com/technology/index.html
e participe dos fóruns de discussão para debater o assunto com 
seus colegas e professores da disciplina.
47
Matemática Discreta
Capítulo 3 - Princípios de 
Contagem: como contar?
A Combinatória é a parte da matemática que tem como objetivo o 
estudo de problemas de contagem do número de agrupamentos que 
podem ser obtidos com os elementos de um dado conjunto. Fazer 
contagem é uma tarefa que temos em diversas situações. Por exemplo, 
quando queremos dimensionar quantos espaços um banco de dados 
consome, quantos usuários a configuração de um computador 
suporta, quantos cálculos certo algoritmo resolve, quantas linhas tem 
a tabela-verdade de uma proposição composta por n proposições 
simples, quantas senhas de acesso a um caixa eletrônico podem ser 
formadas, com quatro algarismos, entre outros casos.
Inicialmente, o que é uma lista?
3.1 Listas
Uma lista é uma seqüência ordenada de objetos. Para 
escrevermos uma lista, escrevemos os seus elementos entre 
parênteses. Por exemplo, (2, a ,3, X) é uma lista cujo primeiro 
elemento é 2, o segundo é a, o terceiro é 3 e o quarto elemento é X. 
Isso significa que a ordem em que os elementos figuram na lista é 
relevante: a lista (a, c, h) é diferente da lista (c, a, h). Além disso, uma 
lista pode conter elementos repetidos: (1, a , 2, 2).
O número de elementos de uma lista é dito comprimento da lista. 
A lista (1, a, 2, 2) tem comprimento 4. Uma lista de comprimento 2 é 
chamada de par ordenado, como por exemplo, (1, 2). Claro que ( ) é 
uma lista vazia, de comprimento 0.
48
Matemática Discreta
Dizemos que duas listas são iguais se tem o mesmo comprimento 
e se os elementos nas posições correspondentes são iguais.
Exemplo 1.
a) Senha numérica com quatro algarismos é uma lista de 
comprimento 4.
b) CPF é uma lista de comprimento 11.
c) Matricula de aluno de uma faculdade: 2008 2 169 034 é uma 
lista de comprimento 11.
d) O Código de Endereçamento Postal – CEP é uma lista de 
comprimento 8 (Veja exercício 15).
Como se calcula o número de listas?
O cálculo é feito por meio de princípios de contagem. Estudaremos 
dois deles.
3.2 Princípio Multiplicativo: contagem de 
listas de comprimento dois
Considere as listas de dois elementos em que o primeiro pode ser 
escolhido de n maneiras e, para cada uma dessas escolhas, há m 
escolhas do segundo elemento da lista. Então, o número de listas de 
comprimento dois é n.m.
Exemplo 1. Com os números 1, 2, 3, 4 e 5 podemos formar quantas 
dezenas?
Bom, uma dezena é uma lista de comprimento dois, constituída 
por dois algarismos, escolhidos dentre 1, 2, 3, 4 e 5. Assim, queremos 
formar listas do tipo (x, y). Temos 5 escolhas para o primeiro elemento 
x e, para cada escolha do primeiro, existem 5 escolhas para o segundo 
elemento. Logo, podemos formar 5 x 5 = 25 dezenas.
Exemplo 2. Suponha agora que queremos formar dezenas de dois 
algarismos diferentes com os algarismos 1, 2, 3, 4 e 5. A escolha do 
primeiro elemento do par pode ser feita de 5 maneiras. Escolhido o 
primeiro, restam 4 escolhas para o segundo elemento da lista. De 
modo que, podemos formar 5 x 4 = 20 listasde comprimento 2, com 
elementos distintos.
49
Matemática Discreta
Exemplo 3. Uma seqüência de dois bits é uma lista de comprimento 
dois formada por zero (0) e um (1) de comprimento dois. Podemos 
formar 2 x 2 = 4 listas: 00, 01, 10 e 11.
E quando as listas têm comprimento maior do que dois? Como é 
feito o cálculo delas?
3.3 Listas de comprimento maior do que dois
Suponhamos que temos n elementos e queremos formar listas de 
comprimento k. O primeiro elemento da lista pode ser escolhido de 
n formas diferentes, o segundo também de n maneiras diferentes e, 
assim, até o k-ésimo elemento que pode ser escolhido de n maneiras. 
Logo, a quantidade de listas será
  
Fatoresk 
........n n.n n ..n = nk
Exemplo 4. Um número binário é uma lista de zero e um. Um 
número binário com 8 dígitos é chamado “byte”.
a) Quantos “bytes” podem-se formar? 
Como um byte é uma lista de comprimento 8 tal que cada posição 
pode ser ocupada por zero (0) ou um (1), podemos formar 2 x 2 x 2 x 
2 x 2 x 2 x 2 x 2 = 28 = 256 bytes.
b) Quantos bytes começam por 10 e terminam por 01? 
As duas primeiras posições e as duas últimas são ocupadas cada 
uma delas por um único determinado bit, então podemos formar 1 x 1 
x 2 x 2 x 2 x 2 x 1 x 1= 16 bytes
c) Quantos bytes começam por 10 e não terminam por 01? 
Existe apenas uma maneira de preencher as duas primeiras 
posições e três maneiras de preencher as duas últimas: 00, 10 e 11. 
De modo que podemos formar 1 x 2 x 2 x 2 x 2 x 3 = 48 bytes.
Exemplo 5. Os aeroportos, embora tendo nomes diferentes, têm 
códigos de três letras. Por exemplo, o aeroporto que serve Recife é 
REC, o aeroporto que serve São Paulo (Guarulhos) é GRU e o que 
serve Brasília é BSB. Com as 26 letras do nosso alfabeto podemos 
formar 26.26.26 = 263 códigos diferentes.
50
Matemática Discreta
Quando as listas têm repetição de elementos, como se processa o 
seu cálculo?
3.4 Listas de comprimento k sem repetição 
de elementos
Agora, dispondo de n elementos, se queremos formar listas de 
k elementos (k n), sem repetições, procedemos assim: temos n 
escolhas para o 1º elemento da lista, n-1 escolhas para o 2º elemento 
da lista, n - 2 escolhas para o 3º, e finalmente n - (k - 1) escolhas para 
o kº elemento da lista. De modo que podemos formar
n x (n - 1) x (n - 2) x ... x (n – (k - 1)) listas de comprimento k
Exemplo 6. As placas de licença de carros em certo estado dos 
Estados Unidos consistem em seis elementos: os três primeiros 
são letras maiúsculas (A-Z) e os três últimos são algarismos (0-9). 
Podemos formar 263x103 placas distintas, das quais 26 x 25 x 24 x 10 
x 9 são placas em que nenhum elemento é repetido.
3.5 Princípio Aditivo
Se dois eventos A e B disjuntos (não ocorrem simultaneamente) 
tem n e m possibilidades, respectivamente, então, o número total de 
possibilidades para o evento A ou B é m + n.
Exemplo 7. Se A é o evento de escolher um número primo entre 10 
e 20 inclusive e B escolher um número par entre 10 e 20 inclusive, de 
quantas maneiras podemos escolher um número primo ou um número 
par entre 10 e 20, inclusive?
Bom, A = {11, 13, 17, 19} e B = {10, 12, 14, 16, 18, 20},
então #(A B) = #A + #B= 4 + 6 = 10.
51
Matemática Discreta
Atenção
O Princípio Aditivo pode ser usado apenas quando os 
eventos são disjuntos, isto é, quando não houver possibilidade 
em comum.
Os dois princípios podem ser usados simultaneamente num 
problema? Sim, veja o seguinte exemplo!
Exemplo 8. Uma rede de computadores é constituída por quatro 
nodos (ou nós): 1, 2, 3 e 4. Existem dois caminhos entre 1 e 3, dois 
entre 2 e 4, três entre 1 e 2 e quatro entre 3 e 4. Uma mensagem 
pode ser enviada do nodo 1 para o nodo 4 por meio 3.2 + 2.4 = 6 + 8 
= 14 caminhos distintos. Observe que os caminhos do nó 1 até o nó 4, 
indo pelo nó 2 ou nó 3, são eventos distintos.
Exemplo 9. Qual o valor de A após o seguinte código em C ter sido 
executado?
 int A = 0
 for (int I = 0; I < = 10; I ++) {
 A = A + 1;
 }
 for (int J =1; J < = 9: J ++){
 }
 for (int K =1; K < = 8; K++){
 }
52
Matemática Discreta
Ao final do primeiro for, A = 10 e no final do segundo for, A = 19. 
Por fim, A recebe o valor 27.
Exemplo 10. Qual o valor de A após o seguinte código em C ter 
sido executado?
 int A = 0
 for (int I = 1; I < = 10; I ++) {
 for (int J = 1; J < = 9; J ++) {
 for (int K = 1; K < = 8; K ++) {
 A = A + 1;
 }
 }
 }
Para K variando de 1 a 8, o valor de A é 8. Quando J varia de 1 a 
9, A assume o valor 9.8 = 72. Finalmente, para I variando de 1 a 10, A 
toma o valor 10.9.8 = 720.
Aprenda Praticando - Exercício Proposto 3.1
Bem, agora é a sua vez! Verifique se você entendeu os assuntos 
desse capítulo, resolvendo os exercícios propostos. As respostas dos 
exercícios de número par serão apresentadas logo a seguir. Se tiver 
dúvidas, tente esclarecê-las com os professores executores e tutores 
nos dos fóruns de discussão da disciplina que serão formados.
1. O número de telefone no país X é composto de dez algarismos, 
onde o primeiro não pode ser nem zero nem um. Quantos 
telefones são possíveis?
2. Um número de inscrição no Seguro Social de um país X é 
composto de nove algarismos (0-9).
a) Quantos números de Seguro Social são possíveis?
b) Quantos deles são números pares?
c) Quantos têm todos os algarismos números pares?
53
Matemática Discreta
d) Quantos podem ser lidos igualmente para trás e para frente 
(por exemplo, 122070221)?
e) Quantos não têm nenhum dos seus algarismos igual a 8?
f) Quantos têm exatamente um algarismo igual a 8?
g) Quantos têm ao menos um algarismo igual a 8?
3. Um sistema de computador permite atribuir nomes aos arquivos 
utilizando qualquer combinação de letras maiúsculas (A-Z) e de 
algarismos (0-9), mas o número de caracteres no nome deve 
ser no máximo cinco (e deve haver ao menos um caractere no 
nome do arquivo). Por exemplo, A423, WJ, 4AA e CDEF4321 
são nomes de arquivo válidos, mas J-31 e TURBINADA não 
são válidos. Quantos nomes de arquivo diferentes podem ser 
formados nesse sistema?
4. Uma prateleira contém 20 livros. De quantas maneiras diferentes 
esses livros podem ser dispostos na prateleira?
5. Um compact disc player tem espaço para 5 CDs; há cinco 
bandejas numeradas de 1 a 5 em que se colocam os CDs. 
Possuo 50 CDs.
a) De quantas maneiras o CD player pode ser carregado, se 
todas as bandejas são ocupadas por CDs?
b) De quantas maneiras o CD player pode ser carregado se eu 
coloco apenas um CD no aparelho?
6. Uma prova de múltipla-escolha tem 15 perguntas, cada qual 
com quatro respostas possíveis, e 15 perguntas adicionais, 
cada uma das quais com cinco respostas possíveis. Quantas 
folhas de respostas diferentes são possíveis?
7. Uma senha de um usuário em um computador de grande 
porte consiste em três letras seguidas de dois dígitos. Quantas 
senhas diferentes são possíveis (considere o alfabeto com 26 
letras)?
8. Quantas senhas são possíveis, na questão anterior, se 
diferenciarmos as letras maiúsculas das minúsculas?
9. Quantos números de CPF são possíveis?
10. Uma pessoa pode viajar no trecho Recife/Natal/Recife 
54
Matemática Discreta
de ônibus, automóvel, avião, navio ou trem. Se o meio de 
transporte da ida não é o mesmo da volta, de quantas maneiras 
essa pessoa pode realizar a viagem?
11. Um alfabeto consiste em três letras: A, B, C. Nessa língua, uma 
palavra é uma seqüência arbitrária de no máximo três letras. 
Quantas palavras existem nessa língua?
12. Qual o valor de A após o seguinte código em C ter sido 
executado?
 int A= 1
 for (int I =1; I < = 10; I++) {
 for (int J = 1; J < = 9; J++) {
 for (int K = 1; K < = 8; K++) {
 A= A + 1;
 }}
 }
13. Qual o valor de A após o seguinte código em C ter sido 
executado?
 int A = 2
 for (int I = 1; I < = 10; I++) {
 A = A + 1;
 }
 for (int J = 1; J < = 10; J ++) {
 A= A +1;
 }
 for (int K = 1; K < = 10: K ++) {
 A= A + 1;
 }
14. Qual o valor de A após o seguinte código C ter sido 
executado?
 int A= 1
 for (int I =1; I < = 10; I++) {
55
Matemática Discreta
 for (int J = 1; J < = 9; J++) {
 for (int K = 1; K < = 8; K++) {
 A= A + 2;
 }
 }
 }
15. O Código de Endereçamento Postal (CEP: _ _ _ _ _ - _ _ _) 
usado no Brasil tem como objetivo principal orientar e acelerar 
o tratamento e distribuição de objetos de correspondência. É 
constituído de 8 dígitos, cada um variando de 0 a 9, de modo 
que o 1º dígito representa a Região do Brasil, o 2º a Sub-
região, o 3º o Setor, o 4º o Sub-setor, o 5º o Divisor de Sub-
setor e os três últimos, recebem o nome de Sufixo e destinam-
se à identificação individual de localidades, Caixas Postais 
Comunitárias, Logradouros, códigos especiais, etc.
Região | Sub-Região | Setor | Sub-setor | Div de Setor | Sufixo | Sufixo | Sufixo
a) Quantos são os CEP’s possíveis?
b) Quantos são os CEP’s possíveis para atender à região 3 
(Sede em Salvador)?
c) Quantos são os CEP’s possíveis para atender à região 5 
(Sede em Recife)?
16. Um cofre tem três discos, cada um com as mesmas 26 letras e 
56
Matemática Discreta
só pode ser aberto quando se colocar uma determinada letra de 
cada um dos discos numa determinada posição. Supondo que 
se ignora o segredo do cofre, de quantas maneiras diferentes 
se podem colocar as letras dos discos nas referidas posições?
17. Quantos números diferentes de 3 algarismos podemos formar 
com os algarismos 1, 3 e 9 no sistema decimal?
18. Quantos números de quatro algarismos podemos formar com 
os algarismos 0, 2, 4, 6 e 8 no sistema decimal?
19. Com cinco pedaços de tecidos nas cores amarela, azul, verde, 
vermelho e branco, quantas bandeiras tricolores podemos 
formar supondo que os tecidos são colocados só em tiras 
verticais?
20. Uma senha de computador é constituída por seis caracteres: 
três letras (de 26 letras) seguidas de três dígitos (de 0-9). 
Determinar o número de senhas possíveis, nos seguintes 
casos:
a) tanto as letras como os dígitos podem ser repetidos;
b) os dígitos não podem ser repetidos;
c) as letras não podem ser repetidos;
d) nem as letras nem os dígitos podem ser repetidos.
21. Quantas senhas são possíveis no exercício anterior se elas 
apresentam as três letras e os três dígitos de forma alternada: 
LDLDLD ou DLDLDL?
22. Com os dígitos 0, 1, 2, 5 e 8, quantos números de quatro 
algarismos diferentes podemos formar? Quantos são múltiplos 
de 5? Quantos são múltiplos de 10?
57
Matemática Discreta
Respostas dos Exercícios 3.1
2) a) 109 b) 5x108 c) 59d) 105
 e) 9.98=99 f) 99g) 109 – 99
4) 20 x 19 x 18 x 17 x ... x 2 x 1 = 20!
6) 420 x 510
8) 523 x 102
10) 20
12) 721
14) 1.441
16) 263
18) 4.53 = 500
20) a) 263 x 103 b) 263 x 10 x 9 x 8
c) 26 x 25 x 24 x 103 d) 26 x 25 x 24 x 10 x 9 x 8
22) a) 96 b) 42 c) 24
3.6 Fatorial
Definimos o fatorial de um número inteiro n > 1 como o produto de 
todos os inteiros de n até 1.
Notação: n! = n . (n - 1) . (n-2) . ... . 2 . 1
Exemplos: 5! = 5.4.3.2.1 = 120 3! = 3.2.1 = 6 2! = 2.1 = 2
Obs. Sabemos que: 4! = 4.3.2.1 = 4.3! 5! = 5.4.3.2.1 = 5.4!
De modo geral podemos escrever n! = n . (n - 1)!
Além disso, definimos 1! = 1 e 0! = 1
Simplifique: a) 
!8
!6 b) 
!3
!5!.4 c) d) 
!3!.8
!6!.5
58
Matemática Discreta
e) 
!4!.2
!6 f) g) 
!4 !0
!5
3.7 Permutações
O Princípio Multiplicativo e suas generalizações aplicam-se 
freqüentemente quando fazemos várias escolhas de um único 
conjunto e temos interesse na ordem em que são feitas. 
Suponha que temos n elementos (n 1) e queremos formar 
grupos com p elementos distintos, 0 p n , que diferem entre si 
pela ordem ou pela natureza dos p elementos que compõem cada 
grupo. Qualquer um desses arranjos será chamado de permutação.
Pelo Princípio Multiplicativo, temos que a 1ª escolha pode ser feita 
de n maneiras diferentes, a segunda pode ser feita de n - 1 formas, 
a 3ª de n - 2 formas, e assim, sucessivamente, até que o p-ésimo 
elemento é escolhido de n - (p - 1) maneiras. Assim, o número de 
permutações npP que podemos formar com p elementos é:
n . (n-1) . (n-2) . [n - (p-1)]
= n . (n-1) . (n-2) . [n - (p-1)] . (n-p) . (n-p-1) ... 2 . 1
(n-p) . (n-p-1) ... 2 . 1
)!(
!
pn
nPnp −
=
Quando p = n, cada grupo é formado de n elementos e P nn = n!
3.8 Combinações
Desejamos selecionar p objetos de um grupo de n objetos, onde 
0 p n, mas não desejamos relevar a ordem na qual eles 
aparecem no agrupamento. Queremos assim encontrar o número de 
agrupamentos de p elementos que sejam diferentes apenas pela 
natureza de pelo menos um elemento. Esses agrupamentos são 
chamados de combinações e o número de combinações é dado por:
C )!(!
!
pnp
nn
p −
=
Como distinguir agrupamento tipo permutação do tipo 
59
Matemática Discreta
combinação?
Suponha que dispomos dos objetos A, B e C e queremos formar 
agrupamento de dois elementos.
Primeiro, forme um agrupamento: AB, em seguida mude a ordem 
de seus elementos: BA.
Pergunte se AB = BA ou AB BA.
Se AB = BA devemos fazer combinações. Se AB BA, devemos 
fazer permutações.
Exemplo 1. Com cinco pedaços de tecidos nas cores amarela, 
azul, verde, vermelho e branco, quantas bandeiras tricolores podemos 
formar supondo que os tecidos são colocados só em tiras verticais?
Dispomos de n = 5 pedaços de tecido e queremos escolher p = 3 
pedaços de tecido para formar uma bandeira de três cores distintas.
Forma-se uma bandeira com os pedaços de cores A B V. Mude a 
ordem dos pedaços de tecidos: BVA. Agora, pergunte: a bandeira ABV 
é igual ou diferente da bandeira BVA? É claro que as bandeiras são 
diferentes pela ordem com que os pedaços de tecido aparecem, a partir 
da haste da bandeira. Logo, bandeiras tricolores são agrupamentos 
que diferem pela ordem ou pela natureza de seus elementos (pedaços 
de tecido), constituindo-se permutações de 3 elementos escolhidos 
dentre 5. Assim podemos formar bandeiras.
Exemplo 2. Uma pessoa manifestou interesse por cinco livros 
diferentes numa feira de livros. Todos os livros estavam em promoção 
por um preço único. No entanto, a pessoa só dispõe de dinheiro para 
adquirir apenas três deles. De quantos modos podem ser feita a 
escolha de três desses livros?
Ora, dispondo de n = 5 livros, escolher p = 3 entre os cinco, é 
formar agrupamentos de três livros ABC. Agora mude a ordem dos 
livros: CAB, e indague se a escolha é a mesma ou diferente... É claro 
que elas são iguais, pois foram escolhidos os mesmos livros. Para 
uma escolha diferente, será necessária a troca de pelo menos um dos 
livros escolhidos inicialmente. Trata-se, portanto, de agrupamento tipo 
combinação.
O número de escolhas é 
60
Matemática Discreta
Exemplo 3. Há 15 estações num ramal de uma estrada de ferro. 
Quantos tipos de bilhetes de passagem são necessários para permitir 
a viagem entre duas estações quaisquer?
A viagem entre as estações C e D é diferente da viagem entre D 
e C. Trata-se, portanto de permutação de n = 15 com p = 2 estações. 
De modo que teremos .
Exemplo 4. Numa empresa de Tecnologia da Informação trabalham 
22 pessoas, todas disponíveis para exercer diversas atividades em 
quatro projetos atualmente em execução. Há necessidade