Text Material Preview
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á necessidadede escolher
seis pessoas para o projeto um, quatro pessoas para o projeto 2,
seis para o projeto 3 e duas pessoas responsáveis pelo projeto 4. De
quantas formas é possível fazer-se a escalação?
Aprenda Praticando - Exercício Proposto 3.2
Os exercícios seguintes referem-se ao Capítulo 3. Para resolvê-los
você fará uso dos princípios de contagem estudados e das técnicas
de classificação de agrupamentos em permutação ou combinação.
Você deve responder as questões, discutir com seus colegas e, em
caso de dúvidas, consulte seus tutores.
1. Quantos anagramas de duas letras diferentes podemos formar
com um alfabeto de 26 letras?
2. Em um congresso há 12 professores de Física. De quantas
maneiras podemos formar uma comissão composta por 3
professores?
3. Considerando os dígitos 1, 2, 3, 4 e 5, quantos números de 2
algarismos diferentes podemos formar?
4. Considere os algarismos 1, 2, 3, 4, e 5. Quantos números com
algarismos distintos, superiores a 100 e inferiores a 1.000
podemos formar se:
a) o número é par?
b) o número é ímpar?
c) o número é par ou ímpar?
5. De quantas formas podem ser escolhidos um presidente e um
61
Matemática Discreta
vice-presidente dentre um grupo de 20 pessoas?
6. Quantas palavras de 6 letras distintas podemos formar com as
letras da palavra MAXWEL?
7. Uma biblioteca tem 4 livros sobre Sistemas Operacionais, 7
sobre Programação e 3 sobre Estrutura de Dados. De quantas
maneiras os livros podem ser arrumados numa prateleira,
sabendo os livros de uma mesma matéria precisam ficar
juntos?
8. Considere a palavra NUMERO:
a) Quantos são os anagramas que podemos formar com as letras
da palavra NUMERO?
b) Quantos anagramas começam e terminam por vogal?
c) Quantos começam e terminam por consoante?
d) Quantos anagramas começam por consoante e terminam por
vogal?
9. O corpo docente de um curso de Sistemas de Informação de
uma faculdade é composto por nove professores portadores do
título de mestrado e quatro professores com título de doutorado.
De quantas maneiras podemos formar uma comissão para
revisão curricular do curso composta por cinco professores,
sendo dois mestres e três doutores?
10. Em um congresso há 12 professores de Física e 10 de
Matemática e queremos formar comissões de 8 professores.
Quantas comissões podem ser formadas:
a) sem restrições
b) havendo pelo menos um professor de Matemática?
c) havendo pelo menos 4 professores de Matemática e 2 de
Física?
11. Um time de futebol leva 18 jogadores na comitiva; 11 jogadores
compõem o time titular. De quantas maneiras o time titular pode
ser formado?
12. De quantas formas um júri popular de 5 homens e 7 mulheres
pode ser selecionado dentre um elenco de 17 homens e 23
mulheres?
62
Matemática Discreta
13. Uma rede de computadores consiste em 60 nós. Pergunta-se:
a) A rede é projetada para resistir à falha de quaisquer dois
nós. De quantas formas esse tipo de falha pode ocorrer?
b) De quantas maneiras podem falhar um ou dois nós?
c) Se um dos nós falhar, de quantas maneiras podemos
selecionar sete nós, sem que estes sejam quaisquer um dos
nós que falharam?
d) Se dois nós falharem, de quantas maneiras podemos
selecionar sete nós de forma que eles incluam um dos nós
que falharam?
14. Uma caixa contém cinco fichas vermelhas e sete pretas.
Quatro fichas são retiradas da caixa, todas de uma só vez, sem
reposição.
a) De quantas formas podem ser retiradas quatro fichas?
b) De quantas formas podem ser retiradas 4 fichas, duas pretas
e duas vermelhas?
c) De quantas formas podemos retirar todas as quatro fichas
vermelhas ou todas as quatro pretas?
d) De quantas formas podemos retirar quatro, sendo três ou
quatro fichas pretas?
15. Numa classe existem 8 alunas, uma das quais se chama
Maria e sete alunos um dos quais se chama José. Formam-se
comissões de 5 alunas e 4 alunos. Quantas são as comissões
das quais:
a) Maria participa?
b) Maria participa sem José?
c) José participa?
d) José participa sem Maria?
e) Maria e José participam simultaneamente?
f) Maria e José são excluídos?
g) Ou Maria ou José participa?
16. Calcule C(6,0), C(6,1), C(6,2), C(6,3), C(6,4), C(6,5) e C(6,6).
63
Matemática Discreta
Algumas dessas combinações são iguais. Quais? Que relação
existe entre as combinações iguais? Teste.
17. Há quatro estradas diferentes entre as cidades A e B; 3 estradas
diferentes entre B e C e 2 estradas diferentes entre A e C. De
quantas maneiras podemos:
a) ir de A para C, passando por B?
b) ir de A até C, passando ou não por B?
c) ir de A até C e voltar?
d) ir de A até C e voltar, passando pelo menos uma vez por B?
e) ir de A até C e voltar, sem passar duas vezes pela mesma
estrada?
18. Quantas senhas de três letras podemos formar com as letras
A, B, C, D e E?
Quantas senhas de três letras sem repetição?
Quantas senhas de três letras diferentes não contêm a letra A?
Quantas senhas de três letras diferentes contêm a letra B?
19. Cinqüenta corredores competem em uma corrida de 10
quilômetros. Quantos resultados são possíveis, nos seguintes
casos, sem considerar empates:
a) Quando queremos saber em que lugar cada corredor
terminou a corrida.
b) A corrida é uma prova de qualificação, e desejamos apenas
saber quais são os dez corredores mais rápidos.
c) A corrida é um evento olímpico final e só interessa quem
ganha medalha de ouro, prata e bronze.
20. Um saco contém 20 fichas idênticas, numeradas de 1 a 20.
Extraem-se aleatoriamente cinco fichas. Calcular de quantas
formas cinco fichas podem ser extraídas, nos seguintes casos:
a) As fichas são extraídas uma a uma, sem reposição. Uma
vez extraída uma ficha, ela não é reposta no saco. Assim,
extrair as fichas 1, 2, 3, 4 e 5 é diferente de extrair as fichas
5, 4, 3, 2 e 1.
64
Matemática Discreta
b) As fichas são extraídas todas de uma vez, sem reposição.
Assim, extrair as fichas 1, 2, 3, 4 e 5 é o mesmo que extrair
as fichas 5, 4, 3, 2 e 1.
c) As fichas são extraídas uma de cada vez, com reposição.
Cada ficha extraída é devolvida ao saco. Assim, extrair as
fichas 1, 2, 2, 4, 5 é diferente de extrair 2, 4, 1, 2, 5.
21. (ENADE 2005). Para o desenvolvimento de um projeto,
determinada organização precisa definir dois grupos de trabalho,
um com três membros e outro com quatro membros. Para o
grupo de três elementos, o primeiro indivíduo nomeado será
o presidente, o segundo o relator, e o terceiro será o auxiliar,
enquanto que, para o grupo de quatro elementos, a ordem
de nomeação não é relevante. Essa organização conta com
um quadro de quatorze funcionários, todos igualmente aptos
a compor qualquer um dos grupos de trabalho, em qualquer
função, sendo que cada um integrará, no máximo, um desses
grupos.
Nessa situação, representando por C(m, p) a combinação de m
elementos p a p e por P(m, p) o permutação de m elementos
p a p, conclui-se que a quantidade de maneiras distintas que a
organização citada dispõe para compor os seus dois grupos é
igual a:
22. O jogo da Mega Sena consiste no sorteio de 6 números
distintos, escolhidos ao acaso, entre os números 1, 2, 3, ... ,
60. Uma aposta é uma escolha de 6 números distintos entre
os 60 possíveis, sendo premiadas aquelas que acertarem 4
(quadra), 5 (quina) ou todos os 6 números sorteados. Um grupo
de apostadores escolhe 20 números para jogar.
a) Quantos são os jogos de 6 números que o grupo pode fazer
com esses 20 números?
b) Caso o grupo acerte na sena, quantas quinas premiadas,
além da sena?
c) Caso o grupo acerte na sena, quantas quadras premiadas,
além da sena e das quinas?
23. Considere o seguinte algoritmo:
void MaxMin ( vetor A, vetor; int*Max, int* Min: integer)
65
Matemática Discreta
Max = A[1]; Min = A[1]
for(int I = 2; I , = 15; I++) {
if ( A[I] > Max) {
Max =A[i];
}
if (A[I] < Min) {
Min = A[i];
}
}
}
Quantas comparações entre os elementos do vetor A = [A[1],
A[2], ... ,A[15]] são efetuadas?
24. Numa certa comunidade, dois homens sempre se
cumprimentam (na chegada) com um aperto de mão e se
despedem (na saída) com outro aperto de mão. Um homem e
uma mulher se cumprimentam com um aperto de mão, mas se
despedem com um aceno. Duas mulheres só trocam acenos,
tanto para se cumprimentarem quanto para se despedirem.
Em uma comemoração, na qual participaram 20 homens e 17
mulheres, todos se cumprimentaram e se despediram na forma
acima descrita. Calcule quantos apertos de mão e quantos
acenos foram dados.
25. A partir de 64 cubos brancos, todos iguais, forma-se um novo
cubo. A seguir, este novo cubo tem cinco de suas seis faces
pintadas de vermelho. Qual o número de cubos menores que
tiveram pelo menos duas de suas faces pintadas de vermelho?
26. As permutações da palavra PROVA foram listadas em ordem
alfabética, como se fossem palavras de cinco letras em um
dicionário. Qual a 73ª palavra dessa lista?
27. Calcule:
a)
8
5
5
4
6
3
P
PP + b)
n
n
P
P
2
3 c)
5
2
3
3
8
5
P
PC +
d) nn
n
CC
P
23
2
−
e)
66
Matemática Discreta
Respostas dos Exercícios 3.1
2. C312 = 220
4. a) 24 b) 36 c) 60
6. 6!
8. a) 720 b) 144 c) 144 d) 216
10. a)
b)
=
c) +
12.
14. a) b) 52.72 CC c) 7454 CC + d) 7451.73 CCC +
16. C(n ,p) = C(n , n-p)
18. a) 53 b) 5 x 4 x 3 c) 4 x 3 x 2 d) 1 x 4 x 3 x 3
20. a) b) c) 20.20.20.20.20 = 205
22. a) C b) 6 c) 1
24. 720 apertos de mão e 612 acenos.
26. RAOPV
Saiba Mais
Neste capítulo você teve oportunidade de conhecer técnicas de
contagem de elementos de um dado conjunto, fazendo uso do princípio
aditivo e do princípio multiplicativo. Além disso, conheceu técnicas de
diferenciação de agrupamentos tipo combinação e permutação.
67
Matemática Discreta
Para conhecer mais sobre combinatória, consulte o seguinte livro:
SANTOS, José Plínio de Oliveira. Introdução a análise
combinatória. Campinas: Editora da Unicamp, 1995.
Desafio
Tito Flavius Josephus foi um historiador que viveu em Jerusalém
no século I D.C., conseguiu escapar da morte graças ao seu
conhecimento em matemática e sua habilidade de pensar rápido.
Conta a lenda que Josephus, como era conhecido, e mais quarenta
companheiros estavam numa caverna cercados por soldados
romanos. Sem alternativas, decidiram cometer suicídio. Fariam da
seguinte maneira: eles se posicionariam em forma de um circulo e
começariam a se matar: sempre o companheiro da esquerda. Como
Josephus não queria morrer, ele sentou-se num lugar seguro (na
verdade o lugar seguro) e todos os seus companheiros morreram e
apenas ele escapou. Como ele conseguiu isso?
Você está desafiado a resolver esse problema. Para melhor
equacioná-lo, pense em n pessoas, entre as quais se encontra
Josephus. Decide-se eliminar n-1 pessoas do grupo da seguinte forma:
as pessoas são colocadas em um círculo com lugares marcados em
ordem crescente no sentido horário, o círculo é percorrido no sentido
horário, tantas vezes quanto necessário, começando pela pessoa
no lugar 1, e toda segunda pessoa viva nesta visitação é eliminada
até que apenas uma sobreviva. Qual é a posição que a pessoa
sobrevivente ocupa?
68
Matemática Discreta
Participe de um fórum de discussão que será orientado pelos
professores executores e tutores para auxiliá-lo a resolver esse
problema. Boa sorte!
69
Matemática Discreta
Capítulo 04 - Relações: uma
abordagem
Intuitivamente o conceito de relação é próximo do conceito formal
de relação. No cotidiano, são exemplos de relação: “irmão de”, “maior
ou igual”, “faz fronteira com”. Em computação e Informática, muitas
construções são baseadas em relações, como Banco de Dados
Relacional.
Trataremos inicialmente de um tipo de relações, as relações
binárias.
Sejam A e B dois conjuntos. Uma relação binária R de A para B é
um conjunto de pares ordenados (x, y) com x A e y B.
Se (x, y) R, dizemos que x está relacionado a y por meio de R e
indicamos o fato escrevendo x R y. Para exprimir que R é uma relação
de A para B, escrevemos R: A B, onde o conjunto A é chamado de
conjunto de partida e B é o conjunto de chegada da relação R.
É claro que uma relação R de A para B é um subconjunto do produto
cartesiano A x B. Assim, o produto cartesiano A x B é ele próprio uma
relação de A para B. Podemos então dizer que dados dois conjuntos A
e B, uma relação binária de A em B é um subconjunto de A x B.
Se R é uma relação binária em A x B, então escrevemos x R y
(x, y) R
Exemplo 1. Sejam os conjuntos A = {1, 2, 3} e B = {2, 3}. O produto
cartesiano dos dois conjuntos A x B = {(1,2), (1,3), (2,2), (2,3), (3, 2) ,
(3, 3)}.
70
Matemática Discreta
a) Se estivermos interessados na relação de igualdade, então os
pares (2,2) e (3,3) são os únicos que apresentam essa propriedade.
Então a relação R que contém esses pares é R1= {(x, y) A x B: x =
y}.
b) Se estivermos interessados na propriedade do primeiro número
do par ser maior que o segundo escolheremos o par (3,2). Nesse
caso, a relação será R2 = {(x, y) A x B: x > y}.
c) A relação R3 = {(x, y) A x B: y = x+1} = {(1, 2), (2, 3) }.
A notação x R y indica que o par ordenado ( x, y ) satisfaz à relação
R. A relação R pode ser descrita com palavras ou simplesmente pela
enumeração dos pares ordenados que a satisfazem.
Exemplo 2. Considere S = {1, 2} e T = {2, 3, 4} e R a relação dada
pela descrição x R y x + y é ímpar. Então R = {(1, 2), (1, 4), (2,
3)}
Exemplo 3. Considere o conjunto A = {1, 2, 3, 4} e a relação R
definida de A em A pela condição (x, y) R x divide y. A divisão
no conjunto dos números naturais é aquela que não deixa resto, de
modo que 1 divide 1, 1 divide 2, 2 divide 4, 2 não divide 3, etc. Assim,
a relação R é constituída pelos pares (1, 1), (1, 2) (1, 3), (1, 4), (2,2),
(2, 4), (3, 3) e (4, 4).
4.1 Tipos de Relações Binárias
Em relação ao número de elementos que se relaciona com um
dado elemento, como se classificam as relações binárias?
Se R é uma relação binária em S x T, então R consiste em um
conjunto de pares ordenados (x, y). Uma determinada primeira
componente x e uma determinada segunda componente y podem
ser relacionadas diversas vezes na relação R.
a) A relação R é dita um-para-um (ou injetiva) se cada primeiro
componente x e cada segundo componente y aparecem apenas uma
vez na relação.
71
Matemática Discreta
Exemplo 4. A relação do conjunto S = {1, 2, 3, 4} no conjunto T =
{a, b, c, d, e} constituída pelos pares (1, b), (2, c), (3, a) e (4, d) é uma
relação um-para-um.
Exemplo 5. A relação R definida no conjunto S = {x: x é um CPF}
no conjunto T = {x: x é aluno do curso de Sistemas de Informação da
UAB – UFRPE} é uma relação um-para-um.
b) A relação R é dita um-para-vários se alguma primeira
componente x aparece mais de uma vez, isto é , se um determinado x
faz par com mais de um y.
Exemplo 6. A relação do conjunto S = {1, 2, 3, 4} no conjunto T
= {a, b, c, d, e}, constituída pelos pares (1, b), (1, c), (3, a) ,(2, d), é
uma relação um-para-vários.
Exemplo 7. A relação R que faz corresponder um departamento
(S) de uma empresa a uma seção (T) desse departamento.
c) A relação R é dita vários-para-um se alguma segunda
componente y faz par com mais de uma primeira componente x.
72
Matemática Discreta
Exemplo 8. A relação definida do conjunto S = {2, -2, 1, -1, 3} no
conjunto T = {1, 4,5, 9} pela condição (x, y) R y = x2.
Exemplo 9. A relação definida no conjunto A de todas as mulheres
da cidade de Trindade (PE) com correspondentes em A através da
condição (x, y) R x filha de y é uma relação vários-para-um.
d) A relação R é dita vários-para-vários se pelo menos um y faz
par com mais de um x e pelo menos um x faz par com mais de um y.
Exemplo 10. A relação definida do conjunto S = {0, -1, 1} no
conjunto T = {0, 1, -1} pela condição (x, y) R x2 + y2 2 é uma
relação vários para vários.
Exemplo 11. Uma relação R definida no conjunto C de clientes de
uma empresa no conjunto P dos produtos que esta empresa vende,
tal que (x, y) R x compra produto y, é uma relação vários para
vários.
73
Matemática Discreta
4.2 Relações binárias em um conjunto A
Uma relação em um conjunto A é uma relação do conjunto A em A.
Trata-se de um subconjunto do produto cartesiano A x A = A2.
Exemplo 12. Considere o conjunto A = {1, 2, 3}. Os pares da relação
R definida em A pela condição (x, y) R x 2y são
R = {(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,2), (3, 3)}.
Exemplo 13. Seja A = {Mara, Cláudia, Anamaria, Beth, João, Clara,
José} um conjunto de pessoas tais que, Anamaria é mãe de Clara e
de Cláudia, Clara é mãe de Beth e Beth é mãe de Mara, de João e de
José. Escreva os pares das seguintes relações definidas em A:
a) x R y x é irmã (ão) de y.
b) x S y x é ancestral de y. (x é ancestral de y, se x é pai, mãe,
avô ou avó de y)
Podemos escrever as relações na forma de tabelas:
Relação R Relação S
“irmã (ao) de” “ancestral de”
x y Anamaria Clara
Clara Cláudio Anamaria Cláudia
Cláudio Clara Anamaria Beth
Mara João Anamaria Mara
João Mara Anamaria João
Mara José Anamaria José
José Mara Clara Beth
João José Clara Mara
José João Clara João
Clara José
Beth Mara
Beth João
Beth José
74
Matemática Discreta
4.3 Operações com relações: como operar com
relações binárias?
Ora, as relações binárias são conjuntos de pares ordenados,
portanto podemos definir a união, a interseção de relações. Podemos
também definir a relação complementar. Além disso, definimos a
relação diferença e a relação diferença simétrica.
Sejam R1 e R2 relações binárias em num conjunto A. Isso significa
que R1 e R2 são subconjuntos de A x A. Então podemos realizar
seguintes operações que resultem em novos subconjuntos de A x A,
isto é, novas relações binárias denotadas por:
Exemplo 14. Considere R1 e R2 duas relações binárias em A = {1, 2,
3} definidas por x R1 y x y e x R2 y x y. Escreva os pares
ordenados de R1 e R2 .Forneça descrições verbais para as relações
abaixo e escreva os seus elementos:
As tabelas representativas das relações R1 e R2 são as seguintes:
Relação R1 Relação R2 Relação R1 R2
1 1 1 1 1 1
1 2 2 1 1 2
1 3 2 2 1 3
2 2 3 1 2 1
2 3 3 2 2 2
3 3 3 3 2 3
3 1
3 2
3 3
75
Matemática Discreta
Relação R1 R2 Relação Relação
1 1 2 1 1 2
2 2 3 1 1 3
3 3 3 2 2 3
Dizemos que: (x, y) (R1 R2) x y ou x y.
(x, y) (R1 R2) x = y.
(x, y) x > y.
(x, y) x < y.
Exemplo 15. Seja A o conjunto de todos os estudantes de uma
faculdade e B o conjunto de todos os livros de sua biblioteca. Sejam R
e S duas relações definidas, respectivamente, por:
(a, b) R o estudante a é obrigado ler livro b no seu curso.
(a, b) S o estudante a leu o livro b.
Descreveremos os pares, ordenados (a, b) em cada uma das
seguintes
a) (a, b) R S o estudante a é obrigado ler livro b no seu
curso ou já leu o livro b.
b) (a, b) R S o estudante a já leu o livro obrigatório b no
seu curso.
c) (a, b) o estudante a não é obrigado ler livro b no seu
curso.
d) (a, b) o estudante a não leu o livro b.
e) (a, b) R – S o estudante a é obrigado ler livro b no seu
curso e não o leu.
f) (a, b) S – R o estudante a já leu livro não obrigatório b.
g) (a, b) R S o estudante a é obrigado ler livro b no seu
curso e não o leu ou o Estudante a já leu livro não obrigatório
b.
76
Matemática Discreta
4.4 Propriedades das Relações definidas em um
conjunto A
Seja R uma relação binária em A. Dizemos que:
a) R é reflexiva se x A, x R x, isto é, x A, (x, x) R.
R não é reflexiva, se x A tal que (x, x) R.
b) R é simétrica, se x, y A, se x R y então y R x, isto é, se (x
y) R então (y, x) R, para x, y em A.
R não é simétrica, se (x, y) R, mas (y, x) R.
c) R é transitiva se x, y, z A, se x R y e y R z então x R z,
isto é, se (x,y) R e (y, z) R então (x , z) R, para x,y, z em
A.
R não é transitiva, se (x, y) R e (y, z) R, mas (x, z) R.
d) R é anti-simétrica, x,y A, se x y então, (x,y) R ou
(y,x) R, mas não ambos
R não é anti-simétrica, se x y com (x,y) R e (y,x) R
Exemplo 16. Considere as seguintes relações em S = {1, 2, 3, 4}.
Quais dessas relações são reflexivas, simétricas, anti-simétricas e
transitivas?
R1 = {(1,1), (1,2), (2,1), (2,2), (3,4), (4,1), (4,4)}
R2 = {(1,1), (1,2), (2,1)}
R3 = {(1,1), (1,2), (1,4), (2,1), (2,2), (3,3), (4,1), (4,4)}
R4 = {(2,1), (3,1), (3,2), (3,3), (4,1), (4,2), (4,3)}
R5 = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,3), (2,4), (3,3), (3,4), (4,4)}
R6 = {(3,4), (2,3)}
R7 = {(3,4)}
R8 = {(1,1), (2,2), (3,3), (4,4)}.
Reflexivas: R3, R5 e R8
Simétricas: R2, R3 e R8
Transitivas: R4, R5 ,R7 e R8
Anti-simétricas: R4, R5, R6, R7 e R8.
77
Matemática Discreta
Exemplo 17. Quais das relações abaixo são reflexivas, simétricas,
transitivas e anti-simétricas? Considere A = {a, b, c}
R1 = {(a,a),(b,b),(c,c)}
R2 = {(a,b),(b,a),(a,a),(a,c)}
R3 = {(a,b),(a,c),(c,a),(b,a)}
R4 = {(a,b),(b,b),(c,c)}
Relação R1: Reflexiva, simétrica, anti-simétrica e transitiva.
Relação R2: Não é reflexiva, não simétrica, não é anti-simétrica e
não é transitiva.
Relação R3: Não é reflexiva, não é anti-simétrica, não é transitiva.
É simétrica.
Relação R4: Não é reflexiva nem simétrica. É anti-simétrica e
transitiva.
4.5 Representação gráfica de Relações Binárias
Uma relação binária R de um conjunto finito A para um conjunto
finito B pode ser representada graficamente da seguinte maneira: a
cada elemento de A e cada elemento de B corresponde um nó, nodo
ou aresta, e, a cada par da relação (a, b) corresponde uma seta,
flecha ou linha, ligando o elemento a A ao elemento b B. Veja o
exemplo seguinte.
Exemplo 18. A relação R = {(a1, b1), (a1, b2), (a2, b1), (a2, b3), (a3,
b3)} do conjunto A = {a1, a2, a3, a4} no conjunto B = {b1, b2, b3} pode ser
representada por:
78
Matemática Discreta
4.6 Grafo de uma relação em um conjunto A
Uma relação R de A em A pode ser representada por um grafo
onde cada elemento do conjunto A é denominado nodo e cada par (a,
b) é representado por uma seta (aresta do grafo), com origem em a e
destino em b. Os pares (a, a) R são representados por um laço. A
tal representação dá-se o nome de grafo orientado ou dígrafo.
Exemplo 19. Seja R é uma relação de A em A= {1,2,3} definida por
R = (1,1), (1,2), (1,3), (2,1), (3,1), (3,2)}. A figura abaixo é o grafo de
R:
Exemplo 20. Seja A = {1,2,3}, R = {(1,1), (2,2), (3,3), (1,2), (1,3),
(3,2) é uma relação reflexiva.
Exemplo 21. A relação em A = {a, b, c}, onde R = {(a,a), (a,b) ,(b,a)
, (a,c), (c,a), (b,c) } não é simétrica. O grafo de apresenta uma seta
de b para c mas não apresenta seta de c para b.
Exemplo 22. A relação em A = {a, b, c}, onde R = {(a, a), (a, b),
Observe que uma
relação em A é
reflexiva se para
todo x A, x R
x, ou seja, o par
(x,x) A. Isso
significa que o
grafo de R tem
um laço em cada
nó, ou seja, uma
seta ligando cada
elemento a si
mesmo.
Atenção
O grafo de
uma relação
simétrica de A
em A apresenta,
para cada seta
entre dois nodos,
outraseta no
sentido contrário,
indicando que,
para cada par (a,
b) R existe o
par inverso (b, a).
Atenção
79
Matemática Discreta
(b, a), (a, c), (c, a), (b, c)} não é transitiva, pois apresenta seta de c
para a, seta de a para c, mas não apresenta laço de c para c.
Também apresenta seta ligando c ao elemento a, seta do a ao b,
mas não apresenta seta ligando c ao b. Observe que também falta um
laço em b.
Uma relação de A em A = {a, b, c} é dita anti-simétrica se x y
então (x, y) R ou (y, x) R
Exemplo 23. Considere a relação em A = {a, b, c} definida por R =
{(a, a), (a, b), (b, c), (c, a), (c, c)}. A relação R é anti-simétrica. No seu
grafo existe, no máximo, uma seta ligando dois nodos diferentes.
Exemplo 24. A relação no conjunto dos números naturais N é
reflexiva porque para qualquer x N, x x é verdadeira. É também
transitiva, pois para quaisquer x, y, z N, se x y e y z então
x z. A relação não é simétrica, pois 3 4 não implica 4 3. A
relação é anti-simétrica, pois, para quaisquer x, y N, se x y e
y x então x = y.
Exemplo 25. Seja X = {1, 2, 3,4} e S = P (X) = {Y: Y é subconjunto
de X}. Definimos a relação em S por A B A B. Verifica-se
que é reflexiva, simétrica, transitiva e não é anti-simétrica.
4.7 Relação n-ária
Dados os conjuntos A1, A2, A3, ..., An, uma relação n-ária em A1 x A2
Uma relação
R de A em A é
transitiva se x R
y e y R z então x
R z. Isto significa
que, se existe
uma seta de x
para y e uma seta
de y para z então
existe uma seta
de x para z.
Atenção
Observe que uma
relação R é anti-
simétrica se no
seu grafo existe,
no máximo, uma
seta ligando dois
nodos diferentes.
Atenção
80
Matemática Discreta
x A3 x ... x An é um subconjunto de A1 x A2 x A3 x ... x An. Os conjuntos
A1, A2 ..., An, são chamados de domínios da relação, e n é o seu grau.
Um elemento da relação é chamado uma n-upla.
Quando A1 = A2 = ... = An a relação é dita interna.
Caso, A1 A2 ... An, a relação é chamada relação externa.
Exemplo 26.
a) Seja R é uma relação interna ternária em N x N x N onde
(x , y, z) R x2 + y2 = z2. Alguns ternos da relação R são
apresentados na tabela a seguir.
0 5 5
5 0 5
3 4 5
4 3 5
6 8 10
8 6 10
b) Considere o conjunto A = {1, 2, 3, 4} e a relação interna R
definida no produto cartesiano A x A x A pela sentença: (x, y, z) R
x divide y + z. A tabela apresenta os ternos dessa relação.
1 1 1 1 2 3 1 4 1 2 2 2 3 1 2 4 2 2
1 1 2 1 2 4 1 4 2 2 2 4 3 2 1 4 3 1
1 1 3 1 3 1 1 4 3 2 3 1 3 2 4 4 4 4
1 1 4 1 3 2 1 4 4 2 3 3 3 3 3
1 2 1 1 3 3 2 1 1 2 4 2 3 4 2
1 2 2 1 3 4 2 1 3 2 4 4 4 1 3
Exemplo 27. Seja R uma relação externa consistindo de 5-uplas
(A, N, P, D, H) representando uma viagem aérea, onde A é a companhia
aérea, N é o número do vôo, P é o ponto de partida, D é o ponto de
destino e H é a hora da partida. Se TAM tem um vôo de número JJ
3501 de Recife para São Paulo às 02h35min então (TAM, JJ 3501,
Recife, São Paulo, 02h35min) pertence a R. Os seus domínios são
o conjunto de todas as companhias aéreas, o conjunto dos números
naturais, o conjuntos das cidades, o conjunto das cidades e o conjunto
das horas.
81
Matemática Discreta
Companhia Vôo Partida Destino Horário
TAM JJ 3501 RECIFE SÃO PAULO 2:35
TAM JJ 3515 RECIFE SÃO PAULO 10:00
GOL G3 1992 FORTALEZA NATAL 11:50
TAM JJ 3817 BELO
HORIZONTE
CURITIBA 20:00
GOL G3 1629 PORTO
SEGURO
RECIFE 3:20
Exemplo 28. Na Informática, a grande aplicação das relações
externas são os bancos de dados que utilizam os modelos relacionais.
Os modelos relacionais são compostos de relações ou tabelas
bidimensionais, cujas operações são descritas em termos de álgebra
relacional. Com este modelo, as tabelas de dados podem ser
manipuladas para retornar outras tabelas de dados oferecendo aos
usuários informações.
Por exemplo, um banco de dados contendo registro dos
vestibulandos de uma faculdade feito em domínios contendo o nome
do estudante, a inscrição do estudante, o curso pretendido, e a média
alcançada. O modelo relacional representa o banco de dados de
registros como uma relação n-ária. Esses registros são representados
por uma 4-upla da forma ( Nome, Inscrição, Curso, Média ). Abaixo
relacionamos alguns exemplos de registros desse banco de dados,
sob a forma de tabela.
Nome Inscrição Curso Média
FREDERICO 23456-5 DIREITO 7,9870
ANA 45629-2 DIREITO 6,9847
ROBERTA 12345-7 SI 8,7654
HUGO 98734-0 ADMINISTRAÇÃO 6,9834
Exemplo 29. Seja A = {A, B, C, D, E, F, G, H} o conjunto de alguns
estudantes de uma universidade e B = {L1, L2, L3,..., L10} o conjunto de
alguns livros de sua biblioteca.
Sejam R e S duas relações definidas de A em B, respectivamente,
por:
(a, b) R o estudante a é obrigado ler livro b no seu curso,
(a, b) S o estudante a leu o livro b, de acordo com as tabelas
82
Matemática Discreta
abaixo:
Relação R Relação S
Aluno Livro Aluno Livro
A L1 B L4
B L2 D L9
A L3 C L2
B L4 E L2
C L2 F L10
D L5 G L7
E L6 C L3
F L3 A L4
G L7 H L8
As tabelas abaixo apresentam as relações R S, R S, R – S,
S – R e R S.
R S
Aluno Livro Aluno Livro
A L1 D L9
B L2 E L2
A L3 F L10
B L4 C L3
C L2 A L4
D L5 H L8
E L6
F L3
G L7
R S R – S
Aluno Livro Aluno Livro
B L4 A L1
C L2 B L2
G L7 A L3
D L5
E L6
F L3
83
Matemática Discreta
S – R R S
Aluno Livro Aluno Livro Aluno Livro
D L9 A L1 D L9
E L2 B L2 E L2
F L10 A L3 F L10
C L3 D L5 C L3
A L4 E L6 A L4
H L8 F L3 H L8
4.8 Álgebra Relacional
É o conjunto de operações formais realizadas sobre relações
produzindo como resultado relações.
Considere o seguinte banco de dados composto pelas tabelas
(relações) seguintes:
Aluno
Nome Endereço Sexo
Aline da Silva Rua das Flores, 10 Feminino
Carina Sousa Rua Vargas, 23 Feminino
Carlos André Rua Abreu, 18 Masculino
Fernando Antunes Rua 24 de Abril,1 Masculino
Laura Abreu Rua do Padre,1 Feminino
Marcelo Silva Rua Getulio,90 Masculino
Vivian Peixoto Rua Jacinto,38 Feminino
Cadastro
Nome Cód_Disc
Aline da Silva MAT0285
Aline da Silva SIS0214
Carina Sousa MAT0285
Carlos André MAT0285
Carlos André SIS0225
Carlos André MAT0331
Fernando Antunes SIS0214
Laura Abreu MAT0285
Vivian Peixoto MAT0285
Vivian Peixoto SIS0214
84
Matemática Discreta
Disciplina
Cód_Disc Nome_da_disciplina Curso
MAT0285 Matemática Discreta Ciência da Comp.
SIS0214 Lógica Ciência da Comp.
SIS0237 Informática Administração
SIS0225 Teoria da Comp. Ciência da Comp.
MAT0331 Matemática I Licenciatura em Comp.
Podemos usar duas operações unárias com as relações.
A operação Restrição (seleciona) cria uma nova tabela
composta pelas linhas da tabela original que satisfaça a uma certa
propriedade (predicado) A sintaxe utilizada é
predicado (Relação)
Exemplo 30. Restrição de Aluno onde Sexo = “Masculino”
fornecendo Resultado 1:
sexo = Masculino (Aluno)
Resultado 1
Carlos André Rua Abreu, 18 Masculino
Fernando Antunes Rua, 24 de Abril, 100 Masculino
Marcelo Silva Rua Getulio,90 Masculino
Exemplo 31. Restrição de Disciplina onde Curso = “Ciência da
Computação” fornecendo Resultado 2:
curso = Ciência da Computação (Disciplina)
Resultado 2
Cód_Disc Nome_da_disciplina Curso
MAT0285 Matemática Discreta Ciência da Comp.
SIS0214 Lógica Ciência da Comp.
SIS0225 Teoria da Comp. Ciência da Comp.
Exemplo 32. Restrição de Cadastro onde Cód_Disc = “SIS0214”
fornecendo Resultado 3:
Cod_Disc = SIS 0214 (Cadastro)
85
Matemática Discreta
Resultado 3
Nome Cód_Disc
Aline da Silva SIS0214
Fernando Antunes SIS0214
Vivian Peixoto SIS0214
A operação Project (projeção) cria uma nova tabela composta
por determinadas colunas da tabela original, eliminando quaisquer
linhas duplicadas. A sintaxeusada é:
lista de atributos (Relação)
Exemplo 33. Projeção de Aluno baseada em (Nome, Endereço)
fornecendo Resultado 4:
Nome, Endereço (Aluno)
Resultado 4
Nome Endereço
Aline da Silva Rua das Flores, 10
Carina Sousa Rua Vargas, 23
Carlos André Rua Abreu, 18
Fernando Antunes Rua 24 de Abril,100
Laura Abreu Rua do Padre,1
Marcelo Silva Rua Getulio,90
Vivian Peixoto Rua Jacinto,38
Exemplo 34. Projeção de Disciplina baseada em (Nome_da_
disciplina, Curso) fornecendo Resultado 5:
Nome_da_disciplina, Curso (Disciplina)
Resultado 5
Nome_da_disciplina Curso
Matemática Discreta Ciência da Comp.
Lógica Ciência da Comp.
Informática Administração
Teoria da Comp. Ciência da Comp.
Matemática I Licenciatura em Comp.
86
Matemática Discreta
Exemplo 35. Projeção de Disciplina baseada em (Código da
disciplina, Nome da disciplina) fornecendo Resultado 6:
Cod_disc, Nome_da_disciplina (Disciplina)
Resultado 6
Cód_Disc Nome_da_disciplina
MAT0285 Matemática Discreta
SIS0214 Lógica
SIS0237 Informática
SIS0225 Teoria da Comp.
MAT0331 Matemática I
A operação junção natural (natural join) cria uma relação
pela combinação dos campos de uma relação com aquelas de outra
baseada nos valores comuns em um conjunto de colunas comuns.
É realizada pela “seleção” das linhas e a “projeção” das colunas do
“produto cartesiano” das relações. A sintaxe é:
(Relação A) |X| < condição de junção > (Relação B).
Exemplo 36. Junção de Aluno e Cadastro baseada em Nome
fornecendo Resultado 7:
(Aluno |X| <Nome> Cadastro):
Resultado 7
Nome Endereço Sexo Cód Disc
Aline da Silva Rua das Flores, 10 Feminino MAT0285
Aline da Silva Rua das Flores, 10 Feminino SIS0214
Carina Sousa Rua Vargas, 23 Feminino MAT0285
Carlos André Rua Abreu, 18 Masculino MAT0285
Carlos André Rua Abreu, 18 Masculino SIS0225
Carlos André Rua Abreu, 18 Masculino MAT0331
Fernando Antunes Rua 24 de Abril,100 Masculino SIS0214
Laura Abreu Rua do Padre,1 Feminino MAT0285
Vivian Peixoto Rua Jacinto,38 Feminino MAT0285
Vivian Peixoto Rua Jacinto,38 Feminino SIS0214
Exemplo 37. Junção de Cadastro e Disciplina baseada em Cod_
Disc fornecendo Resultado 8:
(Cadastro |X| < Cod_Disc > Disciplina):
87
Matemática Discreta
Resultado 8
Nome Cód_Disc Nome_da_
disciplina
Curso
Aline da Silva MAT0285 Matem. Discreta Ciência da Comp.
Carina Sousa MAT0285 Matem. Discreta Ciência da Comp.
Carlos André MAT0285 Matem. Discreta Ciência da Comp.
Laura Abreu MAT0285 Matem. Discreta Ciência da Comp.
Vivian Peixoto MAT0285 Matem. Discreta Ciência da Comp.
Aline da Silva SIS0214 Lógica Ciência da Comp.
Fernando Antunes SIS0214 Lógica Ciência da Comp.
Vivian Peixoto SIS0214 Lógica Ciência da Comp.
Carlos André SIS0225 Teoria da Comp. Ciência da Comp.
Carlos André MAT0331 Matemática I Licenc. em Comp.
Aprenda Praticando - Exercício Proposto 4.1
Agora é a sua vez! Verifique se você entendeu os assuntos
desse capítulo referentes ao conceito de relações, resolvendo os
exercícios propostos. As respostas dos exercícios de número par
serão apresentadas logo a seguir. Caso persistam 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. Considere as seguintes relações definidas de Z em Z.
R1 = {(a, b): a b} R2 = {(a, b): a > b}
R3 = {(a, b): a = b ou a = -b} R4= {(a, b): a = b}
R5 = {(a, b): a = b + 1} R6 = {(a, b): a + b 3}
Faça tabelas de cada uma das relações acima indicadas, cada
uma com pelo menos cinco pares.
2. Classifique cada uma das relações abaixo definidas de A em A,
onde A = {1, 2, 3,... 12} como um–para–um, um–para–vários,
vários–para–um e vários–para–vários.
a) R1 = {(1, 2), (1,4), (1, 6), (2, 3), (4, 3)}
b) R2 = {(9,7), (6,5), (3, 6), (8, 5)}
c) R3 = {(12, 5), (8, 4), (6, 3), (7, 12)}
88
Matemática Discreta
d) R4 = {(2,7), (8, 4), (2, 5), (7, 6), (10,1)}
3. Classifique cada uma das relações definidas de A em A, como
um–para–um, um–para–vários, vários–para–um e vários–
para–vários:
a) A = N x R y x = y + 1
b) A = conjunto de todas as mulheres de Recife x R y x é
filha de y
c) A = P({1, 2, 3}) A R B #A = #B
d) A = N x R y x = 5
4. Sejam R e S relações binárias em N definidas por xRy x
divide y e x S y 5x y. Quais pares pertencem às relações
seguintes:
5. Determine as relações R, definidas no conjunto de todas
as pessoas, são reflexivas, simétricas, anti-simétricas ou
transitivas, onde (a, b) R se e somente se;
a) a é mais alto que b
b) a e b nasceram no mesmo dia
c) a tem o mesmo primeiro nome que b
d) a é primo de b (a é primo de b se um dos pais de a é irmão
de um dos pais de b).
e) a é ancestral de b.
6. Dados os conjuntos A de alunos do Curso de SI, D de disciplinas
oferecidas no segundo semestre de 2008, L de salas onde
serão ministradas as aulas e H de horários de aulas:
A = {José, Joana, Bianca, Tiago}
D = {SI101, SI103, SI201, SI203, SI304}
L = {13, 34, 26, Lab2, Lab5}
H = {08h00min-09h50min, 10h00min-11h50min, 18h45min-
20h15min, 20h30min-22h00min}
89
Matemática Discreta
Simule tabelas (um mínimo de 5-uplas) representando as
seguintes relações: a) R1 de A em D, que fornece a relação das
disciplinas de cada aluno. b) R2 de D em L, relação entre as
disciplinas e o seu local. c) R3 de L em H, que relaciona a sala
de aula com horários.
7. Seja o conjunto S = {Mara, Cláudia, Anamaria, Beth, João, Clara,
José}. Sabendo que Anamaria é mãe de Clara e de Cláudia,
Clara é mãe de Beth e Beth é mãe Mara, de João e de José e as
seguintes relações definidas em S: x R y x é irmã (ão) de y, x
S y x é ancestral de y, desenhe os grafos das relações R, S,
S R, R S. Quais relações, R e S, são reflexivas, simétricas,
anti-simétricas e transitivas?
8. Classifique as relações a seguir, definidas nos conjuntos S
dados como reflexivas, simétricas, anti-simétricas e transitivas.
a) S = Z x R y |x| |y|
b) S = N x R y x.y é par
c) S = {1, 2, 3} x {1, 2, 3}, (x1, y1) R (x2, y2) x1 x2 e y1
y2
d) S = P({1,2,3}) A R B #A #B
9. Tomando por base as tabelas apresentadas no item 4.8, expresse
cada pesquisa abaixo em álgebra relacional e apresente o
resultado em forma de tabela:
a) Dê os nomes de todos os alunos que são do sexo feminino.
b)Dê os nomes de todas as disciplinas do Curso de Ciência da
Computação.
c)Dê os nomes de todos os alunos que cursam Matemática
Discreta.
d) Dê os nomes de todas as disciplinas que Carlos André
cursa.
e) Dê os nomes de todos os alunos do sexo feminino que
cursam SIS0214.
90
Matemática Discreta
Resposta do Exercício 4.1
2. a) vários – para – vários
b) vários – para – um.
c) um – para – um.
d) um – para - vários
4. a) (2, 6), (3, 17) e (1,0)
b) (2, 12)
c) (3, 17)
d) (2,15).
Conclusão
No último capítulo deste fascículo abordamos o conceito de relação.
Conhecemos como as relações se classificam quanto ao número de
elementos relacionados, aprendemos a distinguir as propriedades das
relações binárias internas e representar as relações por grafos, por
n – uplas e por tabelas. Aprendemos como efetuar operações com
relações, notadamente as operações de restrição (seleção), projeção
e junção em tabelas de banco de dados relacional..
Saiba Mais
As relações binárias podem ser também representadas por
matrizes booleanas da seguinte forma.
Suponhamos que R é uma relação do conjunto A = {a1 , a2, ...,
an} no conjunto B = {b1, b2, ... , bm }. A relação R é representada pela
matriz n x m MR = [mij], onde mij =1 se (ai, bj) R e mij = 0 se (ai, bj)
R.
91
Matemática Discreta
Por exemplo, considere a relação em A = {2, 3, 6} definida por a R
b a b. A matrizde R é M = .
A matriz de uma relação é uma excelente maneira de representar
relacionamentos e, através dela podemos verificar se uma dada
relação de A em A é reflexiva, simétrica, transitiva e anti-simétrica.
Se você se interessa pelo assunto, consulte as obras abaixo
indicadas.
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.
Considerações Finais
Caro cursista, nesse fascículo você teve oportunidade de conhecer
os conceitos de somatório, matrizes, contagem e relações. Percebeu
através de exemplos que existem muitas aplicações nas áreas de
computação e informática.
No próximo fascículo, abordaremos os seguintes temas da
Matemática Discreta que são também utilizados nos cursos das áreas
de computação e informática: Função, Recursão, Técnicas de Provas
e o Princípio de Indução Finita.
92
Matemática Discreta
Referências
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.
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.
SANTOS, José Plínio de Oliveira. Introdução a analise
combinatória. Campinas: Editora da Unicamp, 1995.
SCHEINERMAN, Edward R. Matemática Discreta: uma
introdução. Tradução de Alfredo Alves de Farias. São Paulo:
Pioneira Thomson Learning, 2003.
ROSS, Kenneth A; WRIGHT, Charles R. B. Discrete
Mathematics. Prentice-Hall, 1999.
TRUSS, J. K. Discrete mathematics for computer scientist.
Addison Wesley. 1999.
http://problemasteoremas.wordpress.com/2007/11/20/
somatorio-duplo/
http://www.ean.com.br
http://www.mat.ufmg.br/~elaine/GAAL/gaalt1.pdf
http://www.funepe.edu.br:91/funepe/professores/materiais/57/
MATRIZES.ppt#256,1,matrizesMore content from this subject
Conquista Matemática Ensino Fundamental- Estatística Descritiva
- rn_image_picker_lib_temp_dca41659-afdd-4a8f-b8e3-e8c5f2d165bf
- Ângulo inscrito
- Ângulo central
- Ângulo agudo
- Cilindro
- Soma dos ângulos externos
- Arestas em Poliedros
- Big Omega
- Geometria do Cone
- Cilindro
- Paciente V. C. M. C. gênero masculino, compareceu a clinica de odontologia da FACSETE para avaliação, com QP. de dor no dente 38 e dificuldade de higi
- ACX - Campus Access Mobility HPE7-A07 Dumps Questions
- The Open Group OGEA-10B Practice Test Questions