INE5381 - Fundamentos Matemáticos da
Computação
Parte I - Elementos básicos:
1. Lógica Matemática
2. Conjuntos e subconjuntos
- Operações sobre conjuntos
3. Indução e recursão
4. Números inteiros
- Divisão nos inteiros, inteiros módulo n
5. Matrizes
6. Seqüêncas e somas
Matrizes
•
Matrizes são usadas para representar relações entre elementos de
conjuntos.
• Exemplo: redes de comunicações
•
Definição: uma matriz é uma tabela numérica arranjada em um
número m de linhas e um número n de colunas.
 a11 a12 ... a1n 
a

a
...
a
22
2n 
A   21
 :
:
:
: 


a m1 a m 2 ... a mn 
Matrizes
• A i-ésima linha de A é:
ai1
ai 2  ain 
• A j-ésima coluna de A é:
 a1 j 
a 
 2j
  
 
 amj 
1 
j  n
1  i  m
Matrizes – Notações e terminologia
Amxn: matriz A com m linhas e n colunas
Anxn: matriz quadrada de tamanho n
a11
a22  ann 
: diagonal principal de A
aij: elemento da i-ésima linha e da j-ésima coluna da matriz A
[aij]: denota uma matriz A onde a dimensão está definida
Exemplos de matrizes
 2 3 5
A

0

1
2


2 3
B

4
6


 1 0  1
D   1 2 3 
 2 4 5 
E  1 1 3 4
 1
C   2 
 0 
Matrizes
Definição: Uma matriz quadrada A=[aij] em que todos
elementos fora da diagonal são iguais a zero, isto é, aij=0
para ij, é chamada de matriz diagonal.
Exemplos:
4 0
F 

0
3


 2 0 0
G  0  3 0
0 0 5
Matrizes
Definição: Duas matrizes mxn A=[aij] e B=[bij] são ditas iguais
se aij=bij para 1im e 1jn.
Exemplo:
2  3  1
A  0 5
2 
4  4 6 
 2 x  1
B   y 5
2 
 4  4 z 
• A=B se e somente se x=-3, y=0, e z=6.
Aritmética de matrizes
Def.: Se A=[aij] e B=[bij] são duas matrizes mxn, então a
soma de A e B é a matriz C=[cij], de ordem mxn,
definida por:
cij = aij + bij
(1im , 1jn)
Exemplo:
3 4  1
A

5
0

2


4 5 3
B

0

3
2


45
 1  3  7 9 2
3  4
C  A B  



5

0
0

(

3
)

2

2
5

3
0

 

Aritmética de matrizes
Definição: Uma matriz cujos elementos são todos nulos é
chamada de matriz nula e é denotada por 0.
Exemplos:
O23
0 0 0


0
0
0


O33
0 0 0 
 0 0 0
0 0 0
Propriedades da soma de matrizes
Teorema:
a) A + B = B + A
b) (A + B) + C = A+ (B + C)
c) A + 0 = 0 + A = A
Aritmética de matrizes
Def.: Se A=[aij] é uma matriz mxp e B=[bij] é uma matriz pxn,
então o produto de A e B (AxB) é a matriz C=[cij], de ordem
mxn, definida por:
p
cij  ai1b1 j  ai 2b2 j    aipbpj   aik bkj
1  i  m,
1  j  n
k 1
 a11
a
 21
 

 a i1
 

a m1
a12  a1p 
a 22  a 2 p   b11 b12  b1 j  b1n   c11 c12  c1n 

  b 21 b 22  b 2 j  b 2 n   c 21 c 22  c 2 n 



a i 2  a ip   


   
 cij  

 


   b p1 b p 2  b pj  b pn  c m1 c m 2  c mn 

a m 2  a mp 
Produto de matrizes
Exemplo:
A 23
 2 3  4


1
2
3


B32
1
3
  2 2 
 5  3
23  3 2   45
C
 13  2 2  35
 20 20 
C

14

4


C22
? ?


?
?


21  32   4 3
11  22  3 3 
Propriedades do produto de matrizes
• As propriedades básicas do produto de matrizes são
dadas pelo seguinte teorema:
• Teorema:
a) A(BC) = (AB)C
b) A(B + C) = AB + AC
c) (A + B)C = AC + BC
• Note que, dadas duas matrizes Amxp e Bpxn, então A.B pode
ser calculada (mxn). Quanto a B.A pode ocorrer:
1. o produto B.A pode não ser definido
2. (m=n) e B.A é definida  mas A.B  B.A (tamanho)
3. A.B e B.A podem ter o mesmo tamanho mas A.B  B.A
4. A.B = B.A
Propriedades do produto de matrizes
Exemplos:
A 22
A 23
2 1 


3

2


 2 3  4


1
2
3


A 22
2 1 


1
2


B22
B34
1  1


2

3


 4 1 9 2 
 1 5  8  2
 3  4 2 5 
B22
 5  1



1
5


Multiplicação de matrizes
Questão: quantas operações são necessárias para calcular o
produto Cmxn de duas matrizes Amxp e Bpxn?
Resp.: - Há mxn elementos no produto de Amxp e Bpxn
- Para encontrar cada elemento são necessárias p (x) e p (+)
- Logo, um total de m.n.p (x) e m.n.p (+) são usadas.
Questão: Em que ordem as matrizes A1(30x20), A2(20x40) e
A3(40x10) devem ser multiplicadas (matrizes de inteiros) para
usar o menor no possível de operações?
• A1(A2A3)  20.40.10 para obter a matriz 20x10 A2A3
+ 30.20.10 para multiplicar por A1 = 14000
• (A1A2) A3  30.20.40 + 30.40.10 = 36000 (!)
Matriz identidade
• Definição: a matriz diagonal nn na qual todos os
elementos da diagonal são 1’s é chamado de matriz
identidade de ordem n e é denotada por In.
1
0

I  0

:
0
0 0 ... 0
1 0 ... 0
0 1 ... 0

: : : :
0 0 ... 1
• Nota: se A é uma matriz mn, vale:
Im.A = A.In = A
Potências de matrizes
• Pode-se definir potências de matrizes quadradas.
• Se A é uma matriz quadrada nxn, temos:
Ap = A.A...A
p vezes
onde: A0 = In
• Também se pode provar as leis de exponenciação:
ApAq = Ap+q
(Ap)q = Ap.q
Matrizes transpostas
Definição: Se A é uma matriz mxn, então a matriz nxm:
 
A t  a ijt
onde:
a ijt  a ji
1  i  m
e 1  j  n
é chamada de transposta da matriz A.
Exemplos:
5
3 4
A  2  1 0 
1 6  2
1 
B  3
0
1 
3 2
A t  4  1 6 
5 0  2
Bt  1 3 0
Propriedades de matrizes transpostas
Teorema: Se A e B são matrizes, então:
a) (At)t = A
b) (A+B)t = At + Bt
c) (A.B)t = Bt.At
Definição: Uma matriz A=[aij] é chamada simétrica se At=A
• se A é simétrica, A deve ser uma matriz quadrada.
Exemplo:
5
3 4
A  4  1 0 
5 0  2
Matrizes booleanas
• Matrizes constituídas apenas de zeros e 1’s são
frequentemente utilizadas para representar estruturas
discretas (como as relações - parte II).
Definição: Uma matriz booleana é uma matriz mxn em
que os elementos são zeros ou uns.
Exemplo:
0 1 1 0 0
B   1 0 1 0 1 
0 0 1 0 0
Operações com matrizes booleanas
Def.: sejam A=[aij] e B=[bij] duas matrizes booleanas,
1) AB=C=[cij] é a junção de A e B, dada por:
1 se a ij  1 ou bij  1
cij  
0 se a ij  0 e bij  0
2) AB=D=[dij] é o encontro de A e B, dado por:
 1 se a ij  1 e bij  1
d ij  
0 se a ij  0 ou bij  0
Note que A e B
devem ter o mesmo
tamanho
Operações com matrizes booleanas
Exemplo: Calcule a junção e o encontro de:
1 0 1
A

0
1
0


0 1 0
B

1
1
0


Solução:
1  0 0  1 1  0 1 1 1
AB 



0

1
1

1
0

0
1
1
0

 

1  0 0  1 1  0 0 0 0
AB 



0

1
1

1
0

0
0
1
0

 

Operações com matrizes booleanas
Def.: Sejam as matrizes booleanas A=[aij] (mxp) e B=[bij] (pxn). O
produto booleano de A e B é a matriz C mxn cujos elementos são
dados por:
cij = (ai1b1j)  (ai2b2j)  ... (aipbpj)
• Denota-se este produto por AB
• Note que esta operação é idêntica à multiplicação matricial
ordinária em que:
- a adição é substituída por 
- a multiplicação é substituída por 
Produto booleano
Exemplo: Encontre o produto booleano de A e B, onde:
1 0
A  0 1
1 0
1  1  0  0 
A  B  0  1  1  0 
1  1  0  0 
1 1 0
B

0
1
1


1  1  0  1 1  0  0  1
0  1  1  1 0  0  1  1
1  1  0  1 1  0  0  1
 1  0 1  0 0  0  1 1 0 
A  B  0  0 0  1 0  1  0 1 1
1  0 1  0 0  0 1 1 0
Note que #-colunas
de A deve ser =
#-linhas de B
Operações com matrizes booleanas
Teorema: Se A, B e C são matrizes booleanas, então:
1)
a) A  B = B  A
b) A  B = B  A
2)
a) (A  B)  C = A  (B  C)
b) (A  B)  C = A  (B  C)
3)
a) A  (B  C) = (A  B)  (A  C)
b) A  (B  C) = (A  B)  (A  C)
4)
A  (B  C) = (A  B)  C