parte 05 relacao funcao.pdf

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

parte-05-relacao-funcao.pdf
EDUARDO 	
   F R E I R E 	
   NAKAMURA 	
  
I n s / t u t o 	
   d e 	
   C o m p u t a ç ã o 	
  
U n i v e r s i d a d e 	
   F e d e r a l 	
   d o 	
   A m a z o n a s 	
  
n a k a m u r a @ i c o m p . u f a m . e d u . b r 	
  
	
  
Relações	
  e	
  Funções	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
1	
  
1Este material baseia-se no capítulo 1 do livro: Vieira, N.J. Introdução aos Fundamentos da Computação: Linguagens e Máquinas, Pioneira 
Thomson Learning (atualmente, CENGAGE), 2006. 
OB J E T I VO 	
  
R EV ER 	
  O S 	
   CONCE I TO S 	
   D E 	
   R E LAÇÃO 	
  
Matemática Discreta Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) 
2	
  
Relação	
  
Definição	
  informal	
   Exemplos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
—  O	
  que	
  significa	
  relacionar	
  
dois	
  objetos?	
  
u  Comparar	
  dois	
  objetos	
  segundo	
  
uma	
  regra	
  definida	
  
u  Relação	
  é	
  uma	
  comparação	
  
entre	
  dois	
  “objetos”	
  
—  MatemáDca	
  
u  “Menor	
  do	
  que”	
  
u  “Maior	
  do	
  que”	
  
u  “É	
  paralelo	
  à”	
  
u  “É	
  um	
  subconjunto	
  de”	
  
3	
  
O	
  que	
  é	
  uma	
  relação?	
  
Definição	
  formal	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
	
  
	
  
—  Relação	
  binária:	
  R	
  ⊆	
  A	
  ×	
  B	
  
u  Domínio:	
  A	
  
u  Contradomínio:	
  B	
  
u  Imagem:	
  {	
  y	
  |	
  (x,y)	
  ∈	
  R	
  para	
  algum	
  x	
  }	
  
	
  
	
  
	
  
—  Notação	
  
4	
  
O	
  que	
  é	
  uma	
  relação?	
  
Relação	
  de	
  n	
  argumentos	
  sobre	
  A1,	
  A2,	
  …,	
  An	
  
Subconjunto	
  de	
  A1	
  × A2	
  ×	
  …	
  × An	
  
(x,y)	
  ∈	
  R	
  	
  ou	
  	
  x	
  R	
  y	
  
Que	
  relação	
  é	
  essa?	
   Definição	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
x	
  R	
  y	
  
u  x	
  é	
  irmão	
  de	
  y	
  
u  {	
  (Caim,	
  Abel),	
  (Abel,	
  Caim)	
  }	
  
5	
  
Exemplos	
  
Caim	
  
A	
  
Adão	
  
Abel	
  
Eva	
  
Caim	
  
A	
  
Adão	
  
Abel	
  
Eva	
  
Que	
  relação	
  é	
  essa?	
   Definição	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
x	
  R	
  y	
  
u  x	
  é	
  “marido”	
  de	
  y	
  
u  {	
  (Adão,	
  Eva)	
  }	
  
6	
  
Exemplos	
  
Caim	
  
A	
  
Adão	
  
Abel	
  
Eva	
  
Caim	
  
A	
  
Adão	
  
Abel	
  
Eva	
  
Que	
  relação	
  é	
  essa?	
   Definição	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
x	
  R	
  y	
  
u  x	
  =	
  y	
  
u  {	
  (1,1),	
  (2,2),	
  (3,3),	
  (4,4)	
  }	
  
7	
  
Exemplos	
  
1	
  
A	
  
2	
  
3	
  
4	
  
1	
  
A	
  
2	
  
3	
  
4	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
x	
  R	
  y	
  =	
  	
  
{	
  	
  
(1,2),	
  (1,4),	
  	
  
(2,1),	
  (2,3),	
  
(3,2),	
  (3,4),	
  
(4,1),	
  (4,3)	
  	
  
}	
  
8	
  
Exemplos	
  
1	
  
A	
  
2	
  
3	
  
4	
  
1	
  
A	
  
2	
  
3	
  
4	
  
x	
  R	
  y	
  ↔	
  x	
  +	
  y	
  é	
  ímpar	
  
Tipos	
  de	
  relações	
  binárias	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
9	
  
A	
   B	
   A	
   B	
  
A	
   B	
   A	
   B	
  
um-­‐para-­‐um	
  
muitos-­‐para-­‐um	
  
muitos-­‐para-­‐muitos	
  
um-­‐para-­‐muitos	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
10	
  
Representação	
  gráfica	
  de	
  uma	
  relação	
  
3
A	
  
4	
  
5	
  
6	
  
7	
  
8	
  
x	
  R	
  y	
  ↔	
  |x	
  –	
  y|	
  é	
  par	
   sobre	
  A	
  
3
A	
  
4	
  
5	
  
6	
  
7	
  
8	
  
3	
   4	
  
5	
  
6	
  7	
  
8	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
11	
  
Representação	
  gráfica	
  de	
  uma	
  relação	
  
3
A	
  
4	
  
5	
  
6	
  
7	
  
8	
  
x	
  R	
  y	
  ↔	
  |x	
  –	
  y|	
  é	
  par	
   sobre	
  A	
  
3
A	
  
4	
  
5	
  
6	
  
7	
  
8	
  
3	
   4	
  
5	
  
6	
  7	
  
8	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
12	
  
Representação	
  gráfica	
  de	
  uma	
  relação	
  
3
A	
  
4	
  
5	
  
6	
  
7	
  
8	
  
x	
  R	
  y	
  ↔	
  |x	
  –	
  y|	
  é	
  par	
   sobre	
  A	
  
3
A	
  
4	
  
5	
  
6	
  
7	
  
8	
  
3	
   4	
  
5	
  
6	
  7	
  
8	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
13	
  
Representação	
  gráfica	
  de	
  uma	
  relação	
  
3
A	
  
4	
  
5	
  
6	
  
7	
  
8	
  
x	
  R	
  y	
  ↔	
  |x	
  –	
  y|	
  é	
  par	
   sobre	
  A	
  
3
A	
  
4	
  
5	
  
6	
  
7	
  
8	
  
3	
   4	
  
5	
  
6	
  7	
  
8	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
14	
  
Representação	
  gráfica	
  de	
  uma	
  relação	
  
3
A	
  
4	
  
5	
  
6	
  
7	
  
8	
  
x	
  R	
  y	
  ↔	
  |x	
  –	
  y|	
  é	
  par	
   sobre	
  A	
  
3
A	
  
4	
  
5	
  
6	
  
7	
  
8	
  
3	
   4	
  
5	
  
6	
  7	
  
8	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
15	
  
Representação	
  gráfica	
  de	
  uma	
  relação	
  
3
A	
  
4	
  
5	
  
6	
  
7	
  
8	
  
x	
  R	
  y	
  ↔	
  |x	
  –	
  y|	
  é	
  par	
   sobre	
  A	
  
3
A	
  
4	
  
5	
  
6	
  
7	
  
8	
  
3	
   4	
  
5	
  
6	
  7	
  
8	
  
Propriedades	
  	
  de	
  uma	
  relação	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
16	
  
Quais	
  as	
  propriedades	
  das	
  relações	
  
abaixo?	
  
—  >	
  sobre	
  N	
  
Reflexiva,	
  Simétrica,	
  TransiDva?	
  
—  ≥	
  sobre	
  N	
  
Reflexiva,	
  Simétrica,	
  TransiDva?	
  
—  ⊆	
  sobre	
  P	
  	
  (N)	
  
Reflexiva,	
  Simétrica,	
  TransiDva?	
  
—  =	
  sobre	
  N	
  
Reflexiva,	
  Simétrica,	
  TransiDva?	
  
Inversa	
  de	
  R	
  
R-­‐1	
  =	
  {	
  (y,x)	
  |	
  (x,y)}	
  ∈	
  R	
  }	
  
Propriedades	
  de	
  uma	
  relação	
  	
  
binária	
  R	
  ⊆	
  A	
  ×	
  A	
  
•  Reflexiva:	
  ∀x	
  ∈	
  A,	
  xRx	
  
•  Simétrica:	
  ∀x,y	
  ∈	
  A,	
  (xRy	
  à	
  yRx)	
  
•  TransiDva:	
  ∀x,y,z	
  ∈	
  A,	
  (xRy	
  ∧	
  yRz)	
  à	
  xRz	
  
•  AnD-­‐simétrica:	
  
∀x,y	
  ∈	
  A,	
  (xRy	
  ∧	
  yRx)	
  à	
  x=y
Reflexiva,	
  Simétrica,	
  TransiDva	
  
Reflexiva,	
  Simétrica,	
  TransiDva	
  
Reflexiva,	
  Simétrica,	
  TransiDva	
  
Reflexiva,	
  Simétrica,	
  TransiDva	
  
Considere	
  A	
  =	
  {0,	
  1,	
  2,	
  3}	
   Representação	
  gráfica	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
—  Seja	
  a	
  relação	
  	
  
R	
  =	
  {	
  
(0,	
  0),	
  (0,	
  1),	
  (0,	
  3),	
  (1,	
  0),	
  	
  
(1,	
  1),	
  (2,	
  2),	
  (3,	
  0),	
  (3,	
  3)	
  
}	
  
—  Diga	
  quais	
  as	
  propriedades	
  
da	
  relação	
  
Reflexiva,	
  Simétrica,	
  TransiDva,	
  
Assimétrica	
  
17	
  
Representação	
  gráfica	
  de	
  uma	
  relação	
  
0	
   1	
  
2	
  3	
  
Considere	
  A	
  =	
  {0,	
  1,	
  2,	
  3}	
   Representação	
  gráfica	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
—  Seja	
  a	
  relação	
  	
  
R	
  =	
  {	
  
(0,	
  0),	
  (0,	
  1),	
  (0,	
  3),	
  (1,	
  0),	
  	
  
(1,	
  1),	
  (2,	
  2),	
  (3,	
  0),	
  (3,	
  3)	
  
}	
  
—  Diga	
  quais	
  as	
  propriedades	
  
da	
  relação	
  
Reflexiva,	
  Simétrica,	
  TransiDva,	
  
Assimétrica	
  
18	
  
Representação	
  gráfica	
  de	
  uma	
  relação	
  
0	
   1	
  
2	
  3	
  
Reflexiva?	
  
Propriedades	
  de	
  uma	
  relação	
  
•  Reflexiva:	
  ∀x	
  ∈	
  A,	
  xRx	
  
•  Simétrica:	
  ∀x,y	
  ∈	
  A,	
  (xRy	
  à	
  yRx)	
  
•  TransiDva:	
  ∀x,y,z	
  ∈	
  A,	
  (xRy	
  ∧	
  yRz)	
  à	
  xRz	
  
•  AnD-­‐simétrica:	
  ∀x,y	
  ∈	
  A,	
  (xRy	
  ∧	
  yRx)	
  à	
  x=y	
  
Considere	
  A	
  =	
  {0,	
  1,	
  2,	
  3}	
   Representação	
  gráfica	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
—  Seja	
  a	
  relação	
  	
  
R	
  =	
  {	
  
(0,	
  0),	
  (0,	
  1),	
  (0,	
  3),	
  (1,	
  0),	
  	
  
(1,	
  1),	
  (2,	
  2),	
  (3,	
  0),	
  (3,	
  3)	
  
}	
  
Diga	
  quais	
  as	
  propriedades	
  da	
  
relação	
  
Reflexiva,	
  Simétrica,	
  TransiDva,	
  
Assimétrica	
  
19	
  
Representação	
  gráfica	
  de	
  uma	
  relação	
  
0	
   1	
  
2	
  3	
  
SIM	
  
	
  
Existe	
  um	
  laço	
  para	
  cada	
  nó	
  	
  
cada	
  elemento	
  de	
  A	
  é	
  relacionado	
  
consigo	
  mesmo	
  
Propriedades	
  de	
  uma	
  relação	
  
•  Reflexiva:	
  ∀x	
  ∈	
  A,	
  xRx	
  
•  Simétrica:	
  ∀x,y	
  ∈	
  A,	
  (xRy	
  à	
  yRx)	
  
•  TransiDva:	
  ∀x,y,z	
  ∈	
  A,	
  (xRy	
  ∧	
  yRz)	
  à	
  xRz	
  
•  AnD-­‐simétrica:	
  ∀x,y	
  ∈	
  A,	
  (xRy	
  ∧	
  yRx)	
  à	
  x=y	
  
Considere	
  A	
  =	
  {0,	
  1,	
  2,	
  3}	
   Representação	
  gráfica	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
—  Seja	
  a	
  relação	
  	
  
R	
  =	
  {	
  
(0,	
  0),	
  (0,	
  1),	
  (0,	
  3),	
  (1,	
  0),	
  	
  
(1,	
  1),	
  (2,	
  2),	
  (3,	
  0),	
  (3,	
  3)	
  
}	
  
Diga	
  quais	
  as	
  propriedades	
  da	
  
relação	
  
Reflexiva,	
  Simétrica,	
  TransiDva,	
  
Assimétrica	
  
20	
  
Representação	
  gráfica	
  de	
  uma	
  relação	
  
0	
   1	
  
2	
  3	
  
Simétrica?	
  
Propriedades	
  de	
  uma	
  relação	
  
•  Reflexiva:	
  ∀x	
  ∈	
  A,	
  xRx	
  
•  Simétrica:	
  ∀x,y	
  ∈	
  A,	
  (xRy	
  à	
  yRx)	
  
•  TransiDva:	
  ∀x,y,z	
  ∈	
  A,	
  (xRy	
  ∧	
  yRz)	
  à	
  xRz	
  
•  AnD-­‐simétrica:	
  ∀x,y	
  ∈	
  A,	
  (xRy	
  ∧	
  yRx)	
  à	
  x=y	
  
Considere	
  A	
  =	
  {0,	
  1,	
  2,	
  3}	
   Representação	
  gráfica	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
—  Seja	
  a	
  relação	
  	
  
R	
  =	
  {	
  
(0,	
  0),	
  (0,	
  1),	
  (0,	
  3),	
  (1,	
  0),	
  	
  
(1,	
  1),	
  (2,	
  2),	
  (3,	
  0),	
  (3,	
  3)	
  
}	
  
Diga	
  quais	
  as	
  propriedades	
  da	
  
relação	
  
Reflexiva,	
  Simétrica,	
  TransiDva,	
  
Assimétrica	
  
21	
  
Representação	
  gráfica	
  de	
  uma	
  relação	
  
0	
   1	
  
2	
  3	
  
SIM	
  	
  
	
  
Para	
  cada	
  aresta	
  de	
  “ida”	
  existe	
  uma	
  
aresta	
  de	
  “volta”	
  
Propriedades	
  de	
  uma	
  relação	
  
•  Reflexiva:	
  ∀x	
  ∈	
  A,	
  xRx	
  
•  Simétrica:	
  ∀x,y	
  ∈	
  A,	
  (xRy	
  à	
  yRx)	
  
•  TransiDva:	
  ∀x,y,z	
  ∈	
  A,	
  (xRy	
  ∧	
  yRz)	
  à	
  xRz	
  
•  AnD-­‐simétrica:	
  ∀x,y	
  ∈	
  A,	
  (xRy	
  ∧	
  yRx)	
  à	
  x=y	
  
Considere	
  A	
  =	
  {0,	
  1,	
  2,	
  3}	
   Representação	
  gráfica	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
—  Seja	
  a	
  relação	
  	
  
R	
  =	
  {	
  
(0,	
  0),	
  (0,	
  1),	
  (0,	
  3),	
  (1,	
  0),	
  	
  
(1,	
  1),	
  (2,	
  2),	
  (3,	
  0),	
  (3,	
  3)	
  
}	
  
Diga	
  quais	
  as	
  propriedades	
  da	
  
relação	
  
Reflexiva,	
  Simétrica,	
  TransiDva,	
  
Assimétrica	
  
22	
  
Representação	
  gráfica	
  de	
  uma	
  relação	
  
0	
   1	
  
2	
  3	
  
SIM	
  	
  
	
  
Para	
  cada	
  aresta	
  de	
  “ida”	
  existe	
  uma	
  
aresta	
  de	
  “volta”	
  
Propriedades	
  de	
  uma	
  relação	
  
•  Reflexiva:	
  ∀x	
  ∈	
  A,	
  xRx	
  
•  Simétrica:	
  ∀x,y	
  ∈	
  A,	
  (xRy	
  à	
  yRx)	
  
•  TransiDva:	
  ∀x,y,z	
  ∈	
  A,	
  (xRy	
  ∧	
  yRz)	
  à	
  xRz	
  
•  AnD-­‐simétrica:	
  ∀x,y	
  ∈	
  A,	
  (xRy	
  ∧	
  yRx)	
  à	
  x=y	
  
Considere	
  A	
  =	
  {0,	
  1,	
  2,	
  3}	
   Representação	
  gráfica	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
—  Seja	
  a	
  relação	
  	
  
R	
  =	
  {	
  
(0,	
  0),	
  (0,	
  1),	
  (0,	
  3),	
  (1,	
  0),	
  	
  
(1,	
  1),	
  (2,	
  2),	
  (3,	
  0),	
  (3,	
  3)	
  
}	
  
Diga	
  quais	
  as	
  propriedades	
  da	
  
relação	
  
Reflexiva,	
  Simétrica,	
  TransiDva,	
  
Assimétrica	
  
23	
  
Representação	
  gráfica	
  de	
  uma	
  relação	
  
0	
   1	
  
2	
  3	
  
TransiDva?	
  
Propriedades	
  de	
  uma	
  relação	
  
•  Reflexiva:	
  ∀x	
  ∈	
  A,	
  xRx	
  
•  Simétrica:	
  ∀x,y	
  ∈	
  A,	
  (xRy	
  à	
  yRx)	
  
•  TransiDva:	
  ∀x,y,z	
  ∈	
  A,	
  (xRy	
  ∧	
  yRz)	
  à	
  xRz	
  
•  AnD-­‐simétrica:	
  ∀x,y	
  ∈	
  A,	
  (xRy	
  ∧	
  yRx)	
  à	
  x=y	
  
Considere	
  A	
  =	
  {0,	
  1,	
  2,	
  3}	
   Representação	
  gráfica	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
—  Seja	
  a	
  relação	
  	
  
R	
  =	
  {	
  
(0,	
  0),	
  (0,	
  1),	
  (0,	
  3),	
  (1,	
  0),	
  	
  
(1,	
  1),	
  (2,	
  2),	
  (3,	
  0),	
  (3,	
  3)	
  
}	
  
Diga	
  quais	
  as	
  propriedades	
  da	
  
relação	
  
Reflexiva,	
  Simétrica,	
  TransiDva,	
  
Assimétrica	
  
24	
  
Representação	
  gráfica	
  de	
  uma	
  relação	
  
0	
   1	
  
2	
  3	
  
NÃO	
  
	
  
Temos	
  1R0	
  e	
  0R3	
  mas	
  não	
  temos	
  1R3,	
  o	
  
que	
  implica	
  na	
  não	
  transi/vidade	
  
Propriedades	
  de	
  uma	
  relação
•  Reflexiva:	
  ∀x	
  ∈	
  A,	
  xRx	
  
•  Simétrica:	
  ∀x,y	
  ∈	
  A,	
  (xRy	
  à	
  yRx)	
  
•  TransiDva:	
  ∀x,y,z	
  ∈	
  A,	
  (xRy	
  ∧	
  yRz)	
  à	
  xRz	
  
•  AnD-­‐simétrica:	
  ∀x,y	
  ∈	
  A,	
  (xRy	
  ∧	
  yRx)	
  à	
  x=y	
  
Considere	
  A	
  =	
  {0,	
  1,	
  2,	
  3}	
   Representação	
  gráfica	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
—  Seja	
  a	
  relação	
  	
  
R	
  =	
  {	
  
(0,	
  0),	
  (0,	
  1),	
  (0,	
  3),	
  (1,	
  0),	
  	
  
(1,	
  1),	
  (2,	
  2),	
  (3,	
  0),	
  (3,	
  3)	
  
}	
  
Diga	
  quais	
  as	
  propriedades	
  da	
  
relação	
  
Reflexiva,	
  Simétrica,	
  TransiDva,	
  
Assimétrica	
  
25	
  
Representação	
  gráfica	
  de	
  uma	
  relação	
  
0	
   1	
  
2	
  3	
  
AnD-­‐simétrica?	
  
Propriedades	
  de	
  uma	
  relação	
  
•  Reflexiva:	
  ∀x	
  ∈	
  A,	
  xRx	
  
•  Simétrica:	
  ∀x,y	
  ∈	
  A,	
  (xRy	
  à	
  yRx)	
  
•  TransiDva:	
  ∀x,y,z	
  ∈	
  A,	
  (xRy	
  ∧	
  yRz)	
  à	
  xRz	
  
•  AnD-­‐simétrica:	
  ∀x,y	
  ∈	
  A,	
  (xRy	
  ∧	
  yRx)	
  à	
  x=y	
  
Considere	
  A	
  =	
  {0,	
  1,	
  2,	
  3}	
   Representação	
  gráfica	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
—  Seja	
  a	
  relação	
  	
  
R	
  =	
  {	
  
(0,	
  0),	
  (0,	
  1),	
  (0,	
  3),	
  (1,	
  0),	
  	
  
(1,	
  1),	
  (2,	
  2),	
  (3,	
  0),	
  (3,	
  3)	
  
}	
  
Diga	
  quais	
  as	
  propriedades	
  da	
  
relação	
  
Reflexiva,	
  Simétrica,	
  TransiDva,	
  
Assimétrica	
  
26	
  
Representação	
  gráfica	
  de	
  uma	
  relação	
  
0	
   1	
  
2	
  3	
  NÃO	
  
	
  
Temos	
  1R0	
  e	
  0R1,	
  e	
  1	
  ≠	
  2	
  
Propriedades	
  de	
  uma	
  relação	
  
•  Reflexiva:	
  ∀x	
  ∈	
  A,	
  xRx	
  
•  Simétrica:	
  ∀x,y	
  ∈	
  A,	
  (xRy	
  à	
  yRx)	
  
•  TransiDva:	
  ∀x,y,z	
  ∈	
  A,	
  (xRy	
  ∧	
  yRz)	
  à	
  xRz	
  
•  AnD-­‐simétrica:	
  ∀x,y	
  ∈	
  A,	
  (xRy	
  ∧	
  yRx)	
  à	
  x=y	
  
Exercícios	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
27	
  
Demonstre	
  as	
  propriedades	
  de	
  R	
  
1.  x	
  R	
  y	
  ↔	
  x	
  +	
  y	
  é	
  par,	
  sobre	
  N	
  
2.  	
  x	
  R	
  y	
  ↔	
  x	
  divide	
  y,	
  sobre	
  Z+	
  
3.  	
  x	
  R	
  y	
  ↔	
  x	
  =	
  y2,	
  sobre	
  N	
  
4.  	
  x	
  R	
  y	
  ↔	
  x	
  =	
  y2,	
  sobre	
  {0,	
  1}	
  
5.  	
  R	
  =	
  {	
  (1,1),	
  (2,2),	
  (3,3),	
  (1,2),	
  (2,1)	
  },	
  sobre	
  {1,	
  2,	
  3}	
  
6.  	
  R	
  =	
  {	
  (0,0),	
  (1,1),	
  (2,2),	
  (4,4),	
  (6,6),	
  (4,6),	
  (6,4)	
  }	
  
Propriedades	
  de	
  uma	
  relação	
  	
  
binária	
  R	
  ⊆	
  A	
  ×	
  A	
  
•  Reflexiva:	
  ∀x	
  ∈	
  A,	
  xRx	
  
•  Simétrica:	
  ∀x,y	
  ∈	
  A,	
  (xRy	
  à	
  yRx)	
  
•  TransiDva:	
  ∀x,y,z	
  ∈	
  A,	
  (xRy	
  ∧	
  yRz)	
  à	
  xRz	
  
•  AnD-­‐simétrica:	
  
∀x,y	
  ∈	
  A,	
  (xRy	
  ∧	
  yRx)	
  à	
  x=y	
  
Fechos	
  de	
  relações	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
28	
  
Uma	
  relação	
  binária	
  ρ*	
  em	
  um	
  conjunto	
  S	
  é	
  o	
  fecho	
  de	
  uma	
  
relação	
  ρ	
  em	
  S	
  em	
  relação	
  à	
  propriedade	
  P	
  se	
  
u  	
  ρ*	
  tem	
  a	
  propriedade	
  P;	
  
u  	
  ρ	
  ⊆	
  ρ*;	
  
u  	
  ρ*	
  é	
  subconjunto	
  de	
  qualquer	
  outra	
  relação	
  em	
  S	
  que	
  inclua	
  ρ	
  e	
  tenha	
  a	
  
propriedade	
  P.	
  
Considere	
  A	
  =	
  {1,	
  2,	
  3}	
   Considere	
  a	
  relação	
  R	
  abaixo	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
29	
  
Representação	
  gráfica	
  de	
  uma	
  relação	
  
1	
   2	
  
3	
  
Propriedades	
  de	
  uma	
  relação	
  
•  Reflexiva:	
  ∀x	
  ∈	
  A,	
  xRx	
  
•  Simétrica:	
  ∀x,y	
  ∈	
  A,	
  (xRy	
  à	
  yRx)	
  
•  TransiDva:	
  ∀x,y,z	
  ∈	
  A,	
  (xRy	
  ∧	
  yRz)	
  à	
  xRz	
  
•  AnD-­‐simétrica:	
  ∀x,y	
  ∈	
  A,	
  (xRy	
  ∧	
  yRx)	
  à	
  x=y	
  
Reflexiva?	
  Simétrica?	
  
TransiDva?	
  AnD-­‐simétrica?	
  
Considere	
  A	
  =	
  {1,	
  2,	
  3}	
   Considere	
  a	
  relação	
  R	
  abaixo	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
30	
  
Representação	
  gráfica	
  de	
  uma	
  relação	
  
1	
   2	
  
3	
  
Propriedades	
  de	
  uma	
  relação	
  
•  Reflexiva:	
  ∀x	
  ∈	
  A,	
  xRx	
  
•  Simétrica:	
  ∀x,y	
  ∈	
  A,	
  (xRy	
  à	
  yRx)	
  
•  TransiDva:	
  ∀x,y,z	
  ∈	
  A,	
  (xRy	
  ∧	
  yRz)	
  à	
  xRz	
  
•  AnD-­‐simétrica:	
  ∀x,y	
  ∈	
  A,	
  (xRy	
  ∧	
  yRx)	
  à	
  x=y	
  
R*	
  em	
  relação	
  a	
  
reflexividade?	
  
Considere	
  A	
  =	
  {1,	
  2,	
  3}	
   Considere	
  a	
  relação	
  R	
  abaixo	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
31	
  
Representação	
  gráfica	
  de	
  uma	
  relação	
  
1	
   2	
  
3	
  
Propriedades	
  de	
  uma	
  relação	
  
•  Reflexiva:	
  ∀x	
  ∈	
  A,	
  xRx	
  
•  Simétrica:	
  ∀x,y	
  ∈	
  A,	
  (xRy	
  à	
  yRx)	
  
•  TransiDva:	
  ∀x,y,z	
  ∈	
  A,	
  (xRy	
  ∧	
  yRz)	
  à	
  xRz	
  
•  AnD-­‐simétrica:	
  ∀x,y	
  ∈	
  A,	
  (xRy	
  ∧	
  yRx)	
  à	
  x=y	
  
R*	
  em	
  relação	
  a	
  	
  
simetria?	
  
Considere	
  A	
  =	
  {1,	
  2,	
  3}	
   Considere	
  a	
  relação	
  R	
  abaixo	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
32	
  
Representação	
  gráfica	
  de	
  uma	
  relação	
  
1	
   2	
  
3	
  
Propriedades	
  de	
  uma	
  relação	
  
•  Reflexiva:	
  ∀x	
  ∈	
  A,	
  xRx	
  
•  Simétrica:	
  ∀x,y	
  ∈	
  A,	
  (xRy	
  à	
  yRx)	
  
•  TransiDva:	
  ∀x,y,z	
  ∈	
  A,	
  (xRy	
  ∧	
  yRz)	
  à	
  xRz	
  
•  AnD-­‐simétrica:	
  ∀x,y	
  ∈	
  A,	
  (xRy	
  ∧	
  yRx)	
  à	
  x=y	
  
R*	
  em	
  relação	
  a	
  	
  
transiDvidade?	
  
Exercício	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
33	
  
1.  Encontre	
  os	
  fechos	
  reflexivo,	
  simétrico	
  e	
  transiDvo	
  da	
  relação	
  
u  S	
  =	
  {a,b,c};	
  	
  
u  R	
  =	
  {(a,a),	
  (a,b),	
  (b,c),(c,c)}	
  	
  
2.  Encontre	
  os	
  fechos	
  reflexivo,	
  simétrico	
  e	
  transiDvo	
  da	
  relação	
  
u  S	
  =	
  {a,b,c,d};	
  	
  
u  R	
  =	
  {(a,a),	
  (b,b),	
  (c,c),	
  (a,c),	
  (a,d),(b,d),	
  (c,a),	
  (d,a)}	
  	
  
Definição	
   Exemplo	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
34	
  
Função	
  
Função	
  parcial	
  
Uma	
  função	
  f:	
  A→B	
  é	
  uma	
  relação	
  f	
  ⊆	
  A×B,	
  
tal	
  que	
  
	
  
se	
  (x,y)	
  ∈	
  f	
  e	
  (x,z)	
  ∈	
  f,	
  então	
  y	
  =	
  	
  z	
  
	
  
Relação	
   Função?	
  
f:	
  {1,2,3}	
  → {1,2,3};	
  	
  
f	
  =	
  {(1,1),(2,3),(3,1),(2,1)}	
  
g:	
  Z→N;	
  	
  
g(x)	
  =	
  |x|
(módulo)	
  
h:	
  N→N	
  	
  
h(x)	
  =	
  x	
  –	
  4	
  
f:	
  R→R	
  	
  
f(x)	
  =	
  4x	
  –	
  1	
  
	
  
	
  
f:	
  R→R	
  	
  
f(x)	
  =	
  	
  	
  	
  x	
  
✗	
  
✔	
  
✗	
  
✔	
  
✗	
  
-  (x,y)	
  ∈	
  f	
  é	
  o	
  mesmo	
  que	
  f(x)	
  =	
  y	
  
-  f	
  é	
  indefinida	
  para	
  x,	
  se	
  não	
  existe	
  y	
  tal	
  
que	
  f(x)	
  =	
  y	
  
-  Função	
  total	
  definida	
  ∀x	
  no	
  domínio	
  
-  Função	
  f:	
  A1	
  ×…×	
  An→	
  B	
  de	
  n	
  argumentos	
  
Definição	
   Exemplo	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
	
  
	
  
35	
  
Função	
  
Função	
  parcial	
  
Uma	
  função	
  f:	
  A→B	
  é	
  uma	
  relação	
  f	
  ⊆	
  A×B,	
  
tal	
  que	
  
	
  
se	
  (x,y)	
  ∈	
  f	
  e	
  (x,z)	
  ∈	
  f,	
  então	
  y	
  =	
  	
  z	
  
	
  
Função	
   Total	
   Parcial	
  
+	
  :	
  	
  N	
  ×	
  N	
  →	
  N	
  
*	
  :	
  	
  N	
  ×	
  N	
  →	
  N	
  
÷	
  :	
  	
  N	
  ×	
  N	
  →	
  N	
  
÷	
  :	
  	
  N	
  ×	
  Z+	
  →	
  N	
  
✔	
  
✔	
  
✔	
  
✔	
  
Definição	
   Exemplo	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
	
  
	
  	
  
	
  	
  
36	
  
Funções	
  compostas	
  
Composição	
  de	
  duas	
  funções	
  g	
  e	
  f	
  
g ! f = g f (x)( )
f : Z→N, !tal!que!f (x) = x +1
g :N→ Z, !tal!que!g(x) = 2− x
g ! f : Z→ Z, !tal!que
g ! f( )(x) = g x +1( ) = 2− x +1( ) =1− x
f ! g :N→N, !tal!que
f ! g( )(x) = f 2− x( ) = 2− x +1
Tipos	
  de	
  funções	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
37	
  
Tipos	
  de	
  funções	
  
Uma	
  função	
  total	
  	
  f	
  :	
  A	
  à	
  B	
  	
  pode	
  ser	
  
1.  Injetora	
  
∀x,y	
  ∈	
  A,	
  [	
  x	
  ≠	
  y	
  →	
  f(x)	
  ≠	
  f(y)	
  ]	
  
Exemplo:	
  	
  f	
  :	
  N	
  →	
  N,	
  tal	
  que	
  f(x)	
  =	
  x	
  +	
  1	
  
2.  Sobrejetora	
  	
  
∀y	
  ∈	
  B,	
  ∃x	
  ∈	
  A,	
  f(x)	
  =	
  y	
  ,	
  ou	
  seja,	
  B	
  é	
  a	
  imagem	
  de	
  f	
  
Exemplo:	
  	
  f	
  :	
  R	
  →	
  R+	
  ∪	
  {0},	
  tal	
  que	
  f(x)	
  =	
  x2	
  
3.  Bijetora	
  
f	
  é	
  injetora	
  e	
  sobrejetora	
  
Exemplo:	
  	
  f	
  :	
  R	
  → R,	
  tal	
  que	
  f(x)	
  =	
  x3	
  
Exercício	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
38	
  
Diga	
  quais	
  relações	
  abaixo	
  são	
  funções	
  e	
  especifique	
  suas	
  
propriedades:	
  
1.  	
  f:	
  Z	
  →	
  N,	
  onde	
  f(x)=	
  x2+1	
  
2.  	
  f:{1,2,3}	
  →	
  {p,q,r},	
  onde	
  f	
  =	
  {	
  (1,q),	
  (2,r),	
  (3,p)	
  }	
  	
  
3.  	
  g	
  :	
  N	
  →	
  N,	
  onde	
  g	
  é	
  definida	
  por	
  g(x)	
  =	
  2x	
  
OB J E T I VO 	
  
A PR ENDER 	
   A 	
   D E F I N I R 	
   CON JUNTOS 	
   R E CURS I VAMENTE 	
  
A PR ENDER 	
   A 	
   P ROVAR 	
   P ROPR I EDADE S 	
   SOBRE 	
  O S 	
  
I N T E I ROS 	
   U SANDO 	
   I NDUÇÃO 	
  MATEMÁT I CA 	
  
Matemática Discreta Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) 
39	
  
Recursividade	
  e	
  	
  
Indução	
  MatemáDca	
  
Definição	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
40	
  
O	
  que	
  é	
  uma	
  definição	
  recursiva?	
  
Definição	
  Recursiva	
  do	
  Conjunto	
  A	
  
a)  Base:	
  especificação	
  de	
  B	
  ⊂	
  A	
  
b)  Passo	
  Recursivo:	
  como	
  obter	
  
elementos	
  de	
  A	
  a	
  parDr	
  de	
  
outros	
  elementos	
  de	
  A	
  
c)  Fechamento:	
  só	
  pertencem	
  a	
  A,	
  
os	
  elementos	
  obDdos	
  através	
  
dos	
  passos	
  (a)	
  ou	
  (b).	
  
Definição	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
41	
  
O	
  que	
  é	
  uma	
  definição	
  recursiva?	
  
Definição	
  Recursiva	
  do	
  Conjunto	
  A	
  
a)  Base:	
  especificação	
  de	
  B	
  ⊂	
  A	
  
b)  Passo	
  Recursivo:	
  como	
  obter	
  
elementos	
  de	
  A	
  a	
  parDr	
  de	
  
outros	
  elementos	
  de	
  A	
  
c)  Fechamento:	
  só	
  pertencem	
  a	
  A,	
  
os	
  elementos	
  obDdos	
  através	
  
dos	
  passos	
  (a)	
  ou	
  (b).	
  
Definição	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
É	
  possível	
  definir	
  recursivamente	
  
qualquer	
  conjunto	
  enumerável!	
  
42	
  
O	
  que	
  é	
  uma	
  definição	
  recursiva?	
  
Definição	
  Recursiva	
  do	
  Conjunto	
  A	
  
a)  Base:	
  especificação	
  de	
  B	
  ⊂	
  A	
  
b)  Passo	
  Recursivo:	
  como	
  obter	
  
elementos	
  de	
  A	
  a	
  parDr	
  de	
  
outros	
  elementos	
  de	
  A	
  
c)  Fechamento:	
  só	
  pertencem	
  a	
  A,	
  
os	
  elementos	
  obDdos	
  através	
  
dos	
  passos	
  (a)	
  ou	
  (b).	
  
Definição	
   Exemplo	
  01:	
  Números	
  naturais	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
43	
  
O	
  que	
  é	
  uma	
  definição	
  recursiva?	
  
Definição	
  Recursiva	
  do	
  Conjunto	
  A	
  
a)  Base:	
  especificação	
  de	
  B	
  ⊂	
  A	
  
b)  Passo	
  Recursivo:	
  como	
  obter	
  
elementos	
  de	
  A	
  a	
  parDr	
  de	
  
outros	
  elementos	
  de	
  A	
  
c)  Fechamento:	
  só	
  pertencem	
  a	
  A,	
  
os	
  elementos	
  obDdos	
  através	
  
dos	
  passos	
  (a)	
  ou	
  (b).	
  
Definição	
   Exemplo	
  01:	
  Números	
  naturais	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
Definição	
  
a)  0	
  ∈	
  N	
  
b)  Se	
  n	
  ∈	
  N,	
  então	
  n	
  +	
  1	
  ∈	
  N	
  
c)  Só	
  pertencem	
  a	
  N,	
  os	
  números	
  
gerados	
  usando	
  (a)	
  ou	
  (b).	
  
44	
  
O	
  que	
  é	
  uma	
  definição	
  recursiva?	
  
Definição	
  Recursiva	
  do	
  Conjunto	
  A	
  
a)  Base:	
  especificação	
  de	
  B	
  ⊂	
  A	
  
b)  Passo	
  Recursivo:	
  como	
  obter	
  
elementos	
  de	
  A	
  a	
  parDr	
  de	
  
outros	
  elementos	
  de	
  A	
  
c)  Fechamento:	
  só	
  pertencem	
  a	
  A,	
  
os	
  elementos	
  obDdos	
  através	
  
dos	
  passos	
  (a)	
  ou	
  (b).	
  
Definição	
   Exemplo	
  02:	
  Fatorial	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
Definição	
  	
  –	
  	
  	
  fat	
  :	
  N	
  →	
  N	
  
a)  	
  fat(0)	
  =	
  1	
  
b)  	
  ∀n	
  >	
  0,	
  fat(n)	
  =	
  n	
  ×	
  fat(n−1)	
  
c)  	
  implícito	
  
45	
  
O	
  que	
  é	
  uma	
  definição	
  recursiva?	
  
Definição	
  Recursiva	
  do	
  Conjunto	
  A	
  
a)  Base:	
  especificação	
  de	
  B	
  ⊂	
  A	
  
b)  Passo	
  Recursivo:	
  como	
  obter	
  
elementos	
  de	
  A	
  a	
  parDr	
  de	
  
outros	
  elementos	
  de	
  A	
  
c)  Fechamento:	
  só	
  pertencem	
  a	
  A,	
  
os	
  elementos	
  obDdos	
  através	
  
dos	
  passos	
  (a)	
  ou	
  (b).	
  
Definição	
   Exemplo	
  03:	
  Exponencial
an	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
Definição	
  	
  –	
  	
  	
  an	
  :	
  N	
  →	
  N	
  
a)  	
  a0	
  =	
  1	
  
b)  	
  ∀n	
  ∈	
  N,	
  an+1	
  =	
  a	
  ×	
  an	
  
c)  	
  implícito	
  
46	
  
O	
  que	
  é	
  uma	
  definição	
  recursiva?	
  
Definição	
  Recursiva	
  do	
  Conjunto	
  A	
  
a)  Base:	
  especificação	
  de	
  B	
  ⊂	
  A	
  
b)  Passo	
  Recursivo:	
  como	
  obter	
  
elementos	
  de	
  A	
  a	
  parDr	
  de	
  
outros	
  elementos	
  de	
  A	
  
c)  Fechamento:	
  só	
  pertencem	
  a	
  A,	
  
os	
  elementos	
  obDdos	
  através	
  
dos	
  passos	
  (a)	
  ou	
  (b).	
  
Definição	
   Exemplo	
  04:	
  Ling.	
  Proposicional	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
Definição	
  –	
  Ling.	
  proposicional	
  (LP)	
  
a)  Toda	
  a	
  variável	
  lógica	
  está	
  na	
  LP	
  
b)  Se	
  P	
  e	
  Q,	
  estão	
  na	
  LP,	
  então	
  
também	
  estão	
  na	
  LP:	
  
u  ¬P	
  
u  P∧Q	
  
u  P∨Q	
  
u  P→Q	
  
u  P↔Q	
  	
  
c)  	
  implícito	
  
47	
  
O	
  que	
  é	
  uma	
  definição	
  recursiva?	
  
Definição	
  Recursiva	
  do	
  Conjunto	
  A	
  
a)  Base:	
  especificação	
  de	
  B	
  ⊂	
  A	
  
b)  Passo	
  Recursivo:	
  como	
  obter	
  
elementos	
  de	
  A	
  a	
  parDr	
  de	
  
outros	
  elementos	
  de	
  A	
  
c)  Fechamento:	
  só	
  pertencem	
  a	
  A,	
  
os	
  elementos	
  obDdos	
  através	
  
dos	
  passos	
  (a)	
  ou	
  (b).	
  
Indução	
  matemáDca	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
48	
  
h}p://meangreenmath.files.wordpress.com/2013/08/dominoes.jpg	
  
Nono	
  axioma	
  de	
  Giuseppe	
  Peano	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
49	
  
Princípio	
  da	
  indução	
  
h}
p:
//
en
.w
ik
ip
ed
ia
.o
rg
/w
ik
i/G
iu
se
pp
e_
Pe
an
o	
  
ht
tp
:/
/w
w
w
.o
no
rd
es
te
.c
om
/a
dm
in
is
tr
ad
or
/p
er
so
na
lid
ad
es
/i
m
ag
em
Pe
rs
on
al
id
ad
e/
c6
cc
80
94
c2
dc
07
b7
00
ffc
c3
6d
64
e2
13
88
14
.jp
g 
Nono	
  axioma	
  de	
  Giuseppe	
  Peano	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
50	
  
Princípio	
  da	
  indução	
  
h}
p:
//
en
.w
ik
ip
ed
ia
.o
rg
/w
ik
i/G
iu
se
pp
e_
Pe
an
o	
  
ht
tp
:/
/w
w
w
.th
ea
rt
sd
es
k.
co
m
/s
ite
s/
de
fa
ul
t/
fil
es
/i
m
ag
es
/s
to
ri
es
/N
EW
_M
U
SI
C/
th
om
as
_h
_g
re
en
/
le
m
m
y2
.jp
g 
Nono	
  axioma	
  de	
  Giuseppe	
  Peano	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
—  Se	
  K	
  é	
  um	
  conjunto	
  tal	
  que	
  
1.  0	
  (zero)	
  está	
  pertence	
  a	
  K	
  
2.  Para	
  todo	
  natural	
  k	
  	
  
§  Se	
  k	
  está	
  conDdo	
  em	
  K,	
  
§  Então	
  o	
  sucessor	
  de	
  k	
  está	
  em	
  K	
  	
  
—  Então	
  K	
  contém	
  todos	
  os	
  
números	
  naturais	
  
51	
  
Princípio	
  da	
  indução	
  
h}
p:
//
en
.w
ik
ip
ed
ia
.o
rg
/w
ik
i/G
iu
se
pp
e_
Pe
an
o	
  
Reformulando...	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
—  Se	
  P	
  é	
  um	
  predicado	
  tal	
  que	
  
1.  	
  P(0)	
  é	
  verdade	
  
2.  	
  ∀k	
  ∈	
  N,	
  P(k)	
  →	
  P(k+1)	
  
—  Então,	
  	
  P(n)	
  é	
  verdadeiro	
  para	
  
todo	
  n	
  ∈	
  N	
  	
  
52	
  
Princípio	
  da	
  indução	
  
h}
p:
//
en
.w
ik
ip
ed
ia
.o
rg
/w
ik
i/G
iu
se
pp
e_
Pe
an
o	
  
Reformulando...	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
—  Se	
  P	
  é	
  um	
  predicado	
  tal	
  que	
  
1.  	
  P(0)	
  é	
  verdade	
  
2.  	
  ∀k	
  ∈	
  N,	
  P(k)	
  →	
  P(k+1)	
  
—  Então,	
  	
  P(n)	
  é	
  verdadeiro	
  para	
  
todo	
  n	
  ∈	
  N	
  	
  
53	
  
Princípio	
  da	
  indução	
  
É	
  possível	
  provar	
  propriedades	
  para	
  
conjuntos	
  naturais	
  e	
  inteiros	
  usando	
  
indução	
  matemáDca!	
  
Definição	
   Estrutura	
  de	
  demonstração	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
Princípio	
  da	
  indução	
  fraca	
  
Se	
  	
  
①  	
  P(0)*	
  
②  	
  ∀n,	
  P(n)	
  →	
  P(n+1)	
  
	
  
Então	
  
ü  	
  	
  	
  ∀n,	
  P(n)	
  
	
  
1.  Provar	
  P(0)	
  (caso	
  base)	
  
2.  Seja	
  n	
  ≥	
  0	
  abitrário	
  
3.  Suponha	
  P(n)	
  (hipótese	
  de	
  indução)	
  
4.  Provar	
  P(n+1)	
  
5.  Concluir	
  ∀n,	
  P(n)	
  
	
  
Os	
  passos	
  (2)	
  a	
  (4)	
  são	
  chamados	
  de	
  
passo	
  induDvo	
  
54	
  
Princípio	
  da	
  indução	
  fraca	
  
*Primeiro	
  elemento	
  do	
  conjunto,	
  não	
  	
  	
  	
  	
  	
  	
  
	
  	
  necessariamente	
  0	
  (zero)	
  
Exemplo	
  01	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
	
  
	
  
55	
  
Princípio	
  da	
  indução	
  fraca	
  
Prove	
  que	
  para	
  todo	
  n	
  ∈	
  Z+,	
  temos	
  que	
  
a	
  soma	
  1	
  +	
  3	
  +	
  5	
  +…+	
  (2n–1)	
  =	
  n2.	
  
1.  Caso	
  base	
  n	
  =	
  1	
  
u  1	
  =	
  12	
  
2.  Passo	
  induDvo	
  
u  Hipótese:	
  	
  
S(n)	
  =	
  1+3+5+…+(2n	
  –	
  1)	
  =	
  n2	
  
u  Tese:	
  	
  
S(n+1)	
  =	
  1+3+5+…+(2n–1)+[2(n+1)	
  –	
  1]	
  =	
  (n+1)2	
  	
  
	
  	
  
S(n+1)	
  =	
   1	
  +	
  3	
  +	
  5	
  +…+	
  (2n-­‐1)	
  +	
  [2(n+1)	
  –	
  1]	
  
S(n)	
  +	
  [2(n+1)	
  –	
  1]	
  
n2	
  +	
  [2(n+1)	
  –	
  1]	
  
n2	
  +	
  [2n	
  +	
  2	
  –	
  1]	
  
n2	
  +	
  2n	
  +	
  1	
  
(n	
  +	
  1)2	
  
Por	
  definição	
  
	
  	
  
S(n)	
  =	
  1	
  +	
  3	
  +	
  5	
  +…+	
  (2n	
  –	
  1)	
  
Exemplo	
  01	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
	
  
	
  
56	
  
Princípio	
  da	
  indução	
  fraca	
  
Prove	
  que	
  para	
  todo	
  n	
  ∈	
  Z+,	
  temos	
  que	
  
a	
  soma	
  1	
  +	
  3	
  +	
  5	
  +…+	
  (2n–1)	
  =	
  n2.	
  
1.  Caso	
  base	
  n	
  =	
  1	
  
u  1	
  =	
  12	
  
2.  Passo	
  induDvo	
  
u  Hipótese:	
  	
  
S(n)	
  =	
  1+3+5+…+(2n	
  –	
  1)	
  =	
  n2	
  
u  Tese:	
  	
  
S(n+1)	
  =	
  1+3+5+…+(2n–1)+[2(n+1)	
  –	
  1]	
  =	
  (n+1)2	
  	
  
	
  	
  
S(n+1)	
  =	
   1	
  +	
  3	
  +	
  5	
  +…+	
  (2n-­‐1)	
  +	
  [2(n+1)	
  –	
  1]	
  
=	
   S(n)	
  +	
  [2(n+1)	
  –	
  1]	
  
n2	
  +	
  [2(n+1)	
  –	
  1]	
  
n2	
  +
[2n	
  +	
  2	
  –	
  1]	
  
n2	
  +	
  2n	
  +	
  1	
  
(n	
  +	
  1)2	
  Por	
  hipótese	
  de	
  indução	
  
	
  	
  
S(n)	
  =	
  n2	
  
Exemplo	
  01	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
	
  
57	
  
Princípio	
  da	
  indução	
  fraca	
  
Prove	
  que	
  para	
  todo	
  n	
  ∈	
  Z+,	
  temos	
  que	
  
a	
  soma	
  1	
  +	
  3	
  +	
  5	
  +…+	
  (2n–1)	
  =	
  n2.	
  
1.  Caso	
  base	
  n	
  =	
  1	
  
u  1	
  =	
  12	
  
2.  Passo	
  induDvo	
  
u  Hipótese:	
  	
  
S(n)	
  =	
  1+3+5+…+(2n	
  –	
  1)	
  =	
  n2	
  
u  Tese:	
  	
  
S(n+1)	
  =	
  1+3+5+…+(2n–1)+[2(n+1)	
  –	
  1]	
  =	
  (n+1)2	
  	
  
	
  	
  
S(n+1)	
  =	
   1	
  +	
  3	
  +	
  5	
  +…+	
  (2n-­‐1)	
  +	
  [2(n+1)	
  –	
  1]	
  
=	
   S(n)	
  +	
  [2(n+1)	
  –	
  1]	
  
=	
   n2	
  +	
  [2(n+1)	
  –	
  1]	
  
n2	
  +	
  [2n	
  +	
  2	
  –	
  1]	
  
n2	
  +	
  2n	
  +	
  1	
  
(n	
  +	
  1)2	
  
Exemplo	
  01	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
	
  
58	
  
Princípio	
  da	
  indução	
  fraca	
  
Prove	
  que	
  para	
  todo	
  n	
  ∈	
  Z+,	
  temos	
  que	
  
a	
  soma	
  1	
  +	
  3	
  +	
  5	
  +…+	
  (2n–1)	
  =	
  n2.	
  
1.  Caso	
  base	
  n	
  =	
  1	
  
u  1	
  =	
  12	
  
2.  Passo	
  induDvo	
  
u  Hipótese:	
  	
  
S(n)	
  =	
  1+3+5+…+(2n	
  –	
  1)	
  =	
  n2	
  
u  Tese:	
  	
  
S(n+1)	
  =	
  1+3+5+…+(2n–1)+[2(n+1)	
  –	
  1]	
  =	
  (n+1)2	
  	
  
	
  	
  
S(n+1)	
  =	
   1	
  +	
  3	
  +	
  5	
  +…+	
  (2n-­‐1)	
  +	
  [2(n+1)	
  –	
  1]	
  
=	
   S(n)	
  +	
  [2(n+1)	
  –	
  1]	
  
=	
   n2	
  +	
  [2(n+1)	
  –	
  1]	
  
=	
   n2	
  +	
  [2n	
  +	
  2	
  –	
  1]	
  
n2	
  +	
  2n	
  +	
  1	
  
(n	
  +	
  1)2	
  
Exemplo	
  01	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
	
  
59	
  
Princípio	
  da	
  indução	
  fraca	
  
Prove	
  que	
  para	
  todo	
  n	
  ∈	
  Z+,	
  temos	
  que	
  
a	
  soma	
  1	
  +	
  3	
  +	
  5	
  +…+	
  (2n–1)	
  =	
  n2.	
  
1.  Caso	
  base	
  n	
  =	
  1	
  
u  1	
  =	
  12	
  
2.  Passo	
  induDvo	
  
u  Hipótese:	
  	
  
S(n)	
  =	
  1+3+5+…+(2n	
  –	
  1)	
  =	
  n2	
  
u  Tese:	
  	
  
S(n+1)	
  =	
  1+3+5+…+(2n–1)+[2(n+1)	
  –	
  1]	
  =	
  (n+1)2	
  	
  
	
  	
  
S(n+1)	
  =	
   1	
  +	
  3	
  +	
  5	
  +…+	
  (2n-­‐1)	
  +	
  [2(n+1)	
  –	
  1]	
  
=	
   S(n)	
  +	
  [2(n+1)	
  –	
  1]	
  
=	
   n2	
  +	
  [2(n+1)	
  –	
  1]	
  
=	
   n2	
  +	
  [2n	
  +	
  2	
  –	
  1]	
  
=	
   n2	
  +	
  2n	
  +	
  1	
  
(n	
  +	
  1)2	
  
Exemplo	
  01	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
	
  
	
  
Logo,	
  para	
  todo	
  n	
  ∈	
  Z+,	
  temos	
  que	
  	
  	
  	
  	
  
1	
  +	
  3	
  +	
  5	
  +…+	
  (2n–1)	
  =	
  n2.	
  
60	
  
Princípio	
  da	
  indução	
  fraca	
  
Prove	
  que	
  para	
  todo	
  n	
  ∈	
  Z+,	
  temos	
  que	
  
a	
  soma	
  1	
  +	
  3	
  +	
  5	
  +…+	
  (2n–1)	
  =	
  n2.	
  
1.  Caso	
  base	
  n	
  =	
  1	
  
u  1	
  =	
  12	
  
2.  Passo	
  induDvo	
  
u  Hipótese:	
  	
  
S(n)	
  =	
  1+3+5+…+(2n	
  –	
  1)	
  =	
  n2	
  
u  Tese:	
  	
  
S(n+1)	
  =	
  1+3+5+…+(2n–1)+[2(n+1)	
  –	
  1]	
  =	
  (n+1)2	
  	
  
	
  	
  
S(n+1)	
  =	
   1	
  +	
  3	
  +	
  5	
  +…+	
  (2n-­‐1)	
  +	
  [2(n+1)	
  –	
  1]	
  
=	
   S(n)	
  +	
  [2(n+1)	
  –	
  1]	
  
=	
   n2	
  +	
  [2(n+1)	
  –	
  1]	
  
=	
   n2	
  +	
  [2n	
  +	
  2	
  –	
  1]	
  
=	
   n2	
  +	
  2n	
  +	
  1	
  
=	
   (n	
  +	
  1)2	
  
Exemplo	
  02	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
	
  
Logo,	
  para	
  todo	
  n	
  ∈	
  Z+,	
  o	
  número	
  
22n	
  –	
  1	
  é	
  divisível	
  por	
  3	
  
61	
  
Princípio	
  da	
  indução	
  fraca	
  
Prove	
  que	
  para	
  todo	
  n	
  ∈	
  Z+,	
  o	
  
número	
  22n	
  –	
  1	
  é	
  divisível	
  por	
  3.	
  
1.  Caso	
  base	
  n	
  =	
  1	
  
u  22(1)	
  –	
  1	
  =	
  4	
  –	
  1	
  =	
  3	
  (divisível	
  por	
  3)	
  
2.  Passo	
  induDvo	
  
u  Hipótese:	
  22n	
  –	
  1	
  =	
  3m,	
  para	
  m,n	
  ∈	
  Z+	
  
u  Tese:	
  22(n+1)	
  –	
  1	
  =	
  3k	
  	
  
22(n+1)	
  –	
  1	
  	
  =	
   22n+2	
  –	
  1	
  
22n	
  (22)	
  –	
  1	
  	
  
22n	
  (4)	
  –	
  1	
  	
  
(3m+1)(4)	
  –	
  1	
  
3m(4)	
  +	
  4	
  –	
  1	
  
3(4m)	
  +	
  3	
  
3(4m	
  +	
  1)	
  
Exemplo	
  02	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
	
  
Logo,	
  para	
  todo	
  n	
  ∈	
  Z+,	
  o	
  número	
  
22n	
  –	
  1	
  é	
  divisível	
  por	
  3	
  
62	
  
Princípio	
  da	
  indução	
  fraca	
  
Prove	
  que	
  para	
  todo	
  n	
  ∈	
  Z+,	
  o	
  
número	
  22n	
  –	
  1	
  é	
  divisível	
  por	
  3.	
  
1.  Caso	
  base	
  n	
  =	
  1	
  
u  22(1)	
  –	
  1	
  =	
  4	
  –	
  1	
  =	
  3	
  (divisível	
  por	
  3)	
  
2.  Passo	
  induDvo	
  
u  Hipótese:	
  22n	
  –	
  1	
  =	
  3m,	
  para	
  m,n	
  ∈	
  Z+	
  
u  Tese:	
  22(n+1)	
  –	
  1	
  =	
  3k,	
  para	
  	
  k	
  ∈	
  Z+	
  
22(n+1)	
  –	
  1	
  	
  =	
   22n+2	
  –	
  1	
  
22n	
  (22)	
  –	
  1	
  	
  
22n	
  (4)	
  –	
  1	
  	
  
(3m+1)(4)	
  –	
  1	
  
3m(4)	
  +	
  4	
  –	
  1	
  
3(4m)	
  +	
  3	
  
3(4m	
  +	
  1)	
  
Exemplo	
  02	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
	
  
Logo,	
  para	
  todo	
  n	
  ∈	
  Z+,	
  o	
  número	
  
22n	
  –	
  1	
  é	
  divisível	
  por	
  3	
  
63	
  
Princípio	
  da	
  indução	
  fraca	
  
Prove	
  que	
  para	
  todo	
  n	
  ∈	
  Z+,	
  o	
  
número	
  22n	
  –	
  1	
  é	
  divisível	
  por	
  3.	
  
1.  Caso	
  base	
  n	
  =	
  1	
  
u  22(1)	
  –	
  1	
  =	
  4	
  –	
  1	
  =	
  3	
  (divisível	
  por	
  3)	
  
2.  Passo	
  induDvo	
  
u  Hipótese:	
  22n	
  –	
  1	
  =	
  3m,	
  para	
  m,n	
  ∈	
  Z+	
  
u  Tese:	
  22(n+1)	
  –	
  1	
  =	
  3k,	
  para	
  	
  k	
  ∈	
  Z+	
  
22(n+1)	
  –	
  1	
  	
  =	
   22n+2	
  –	
  1	
  
=	
   22n	
  (22)	
  –	
  1	
  	
  
22n	
  (4)	
  –	
  1	
  	
  
(3m+1)(4)	
  –	
  1	
  
3m(4)	
  +	
  4	
  –	
  1	
  
3(4m)	
  +	
  3	
  
3(4m	
  +	
  1)	
  
Exemplo	
  02	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
	
  
Logo,	
  para	
  todo	
  n	
  ∈	
  Z+,	
  o	
  número	
  
22n	
  –	
  1	
  é	
  divisível	
  por	
  3	
  
64	
  
Princípio	
  da	
  indução	
  fraca	
  
Prove	
  que	
  para	
  todo	
  n	
  ∈	
  Z+,	
  o	
  
número	
  22n	
  –	
  1	
  é	
  divisível	
  por	
  3.	
  
1.  Caso	
  base	
  n	
  =	
  1	
  
u  22(1)	
  –	
  1	
  =
4	
  –	
  1	
  =	
  3	
  (divisível	
  por	
  3)	
  
2.  Passo	
  induDvo	
  
u  Hipótese:	
  22n	
  –	
  1	
  =	
  3m,	
  para	
  m,n	
  ∈	
  Z+	
  
u  Tese:	
  22(n+1)	
  –	
  1	
  =	
  3k,	
  para	
  	
  k	
  ∈	
  Z+	
  
22(n+1)	
  –	
  1	
  	
  =	
   22n+2	
  –	
  1	
  
=	
   22n	
  (22)	
  –	
  1	
  	
  
=	
   22n	
  (4)	
  –	
  1	
  	
  
(3m+1)(4)	
  –	
  1	
  
3m(4)	
  +	
  4	
  –	
  1	
  
3(4m)	
  +	
  3	
  
3(4m	
  +	
  1)	
  
Exemplo	
  02	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
	
  
Logo,	
  para	
  todo	
  n	
  ∈	
  Z+,	
  o	
  número	
  
22n	
  –	
  1	
  é	
  divisível	
  por	
  3	
  
65	
  
Princípio	
  da	
  indução	
  fraca	
  
Prove	
  que	
  para	
  todo	
  n	
  ∈	
  Z+,	
  o	
  
número	
  22n	
  –	
  1	
  é	
  divisível	
  por	
  3.	
  
1.  Caso	
  base	
  n	
  =	
  1	
  
u  22(1)	
  –	
  1	
  =	
  4	
  –	
  1	
  =	
  3	
  (divisível	
  por	
  3)	
  
2.  Passo	
  induDvo	
  
u  Hipótese:	
  22n	
  –	
  1	
  =	
  3m,	
  para	
  m,n	
  ∈	
  Z+	
  
u  Tese:	
  22(n+1)	
  –	
  1	
  =	
  3k,	
  para	
  	
  k	
  ∈	
  Z+	
  
22(n+1)	
  –	
  1	
  	
  =	
   22n+2	
  –	
  1	
  
=	
   22n	
  (22)	
  –	
  1	
  	
  
=	
   22n	
  (4)	
  –	
  1	
  	
  
=	
   22n	
  (3	
  +	
  1)	
  	
  –	
  1	
  
3(22n)	
  +	
  22n	
  –	
  1	
  
3(22n)	
  +	
  3m	
  
3(22n	
  +	
  m)	
  
Exemplo	
  02	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
	
  
Logo,	
  para	
  todo	
  n	
  ∈	
  Z+,	
  o	
  número	
  
22n	
  –	
  1	
  é	
  divisível	
  por	
  3	
  
66	
  
Princípio	
  da	
  indução	
  fraca	
  
Prove	
  que	
  para	
  todo	
  n	
  ∈	
  Z+,	
  o	
  
número	
  22n	
  –	
  1	
  é	
  divisível	
  por	
  3.	
  
1.  Caso	
  base	
  n	
  =	
  1	
  
u  22(1)	
  –	
  1	
  =	
  4	
  –	
  1	
  =	
  3	
  (divisível	
  por	
  3)	
  
2.  Passo	
  induDvo	
  
u  Hipótese:	
  22n	
  –	
  1	
  =	
  3m,	
  para	
  m,n	
  ∈	
  Z+	
  
u  Tese:	
  22(n+1)	
  –	
  1	
  =	
  3k,	
  para	
  	
  k	
  ∈	
  Z+	
  
22(n+1)	
  –	
  1	
  	
  =	
   22n+2	
  –	
  1	
  
=	
   22n	
  (22)	
  –	
  1	
  	
  
=	
   22n	
  (4)	
  –	
  1	
  	
  
=	
   22n	
  (3	
  +	
  1)	
  	
  –	
  1	
  
=	
   3(22n)	
  +	
  22n	
  –	
  1	
  
3(22n)	
  +	
  3m	
  
3(22n	
  +	
  m)	
  
Por	
  hipótese	
  
de	
  indução:	
  
	
  	
  
22n	
  –	
  1	
  =	
  3m	
  
Exemplo	
  02	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
	
  
Logo,	
  para	
  todo	
  n	
  ∈	
  Z+,	
  o	
  número	
  
22n	
  –	
  1	
  é	
  divisível	
  por	
  3	
  
67	
  
Princípio	
  da	
  indução	
  fraca	
  
Prove	
  que	
  para	
  todo	
  n	
  ∈	
  Z+,	
  o	
  
número	
  22n	
  –	
  1	
  é	
  divisível	
  por	
  3.	
  
1.  Caso	
  base	
  n	
  =	
  1	
  
u  22(1)	
  –	
  1	
  =	
  4	
  –	
  1	
  =	
  3	
  (divisível	
  por	
  3)	
  
2.  Passo	
  induDvo	
  
u  Hipótese:	
  22n	
  –	
  1	
  =	
  3m,	
  para	
  m,n	
  ∈	
  Z+	
  
u  Tese:	
  22(n+1)	
  –	
  1	
  =	
  3k,	
  para	
  	
  k	
  ∈	
  Z+	
  
22(n+1)	
  –	
  1	
  	
  =	
   22n+2	
  –	
  1	
  
=	
   22n	
  (22)	
  –	
  1	
  	
  
=	
   22n	
  (4)	
  –	
  1	
  	
  
=	
   22n	
  (3	
  +	
  1)	
  	
  –	
  1	
  
=	
   3(22n)	
  +	
  22n	
  –	
  1	
  
=	
   3(22n)	
  +	
  3m	
  
3(22n	
  +	
  m)	
  
Exemplo	
  02	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
	
  
Logo,	
  para	
  todo	
  n	
  ∈	
  Z+,	
  o	
  número	
  
22n	
  –	
  1	
  é	
  divisível	
  por	
  3	
  
68	
  
Princípio	
  da	
  indução	
  fraca	
  
Prove	
  que	
  para	
  todo	
  n	
  ∈	
  Z+,	
  o	
  
número	
  22n	
  –	
  1	
  é	
  divisível	
  por	
  3.	
  
1.  Caso	
  base	
  n	
  =	
  1	
  
u  22(1)	
  –	
  1	
  =	
  4	
  –	
  1	
  =	
  3	
  (divisível	
  por	
  3)	
  
2.  Passo	
  induDvo	
  
u  Hipótese:	
  22n	
  –	
  1	
  =	
  3m,	
  para	
  m,n	
  ∈	
  Z+	
  
u  Tese:	
  22(n+1)	
  –	
  1	
  =	
  3k,	
  para	
  	
  k	
  ∈	
  Z+	
  
22(n+1)	
  –	
  1	
  	
  =	
   22n+2	
  –	
  1	
  
=	
   22n	
  (22)	
  –	
  1	
  	
  
=	
   22n	
  (4)	
  –	
  1	
  	
  
=	
   22n	
  (3	
  +	
  1)	
  	
  –	
  1	
  
=	
   3(22n)	
  +	
  22n	
  –	
  1	
  
=	
   3(22n)	
  +	
  3m	
  
=	
   3(22n	
  +	
  m)	
  
k	
  =	
  (22n	
  +	
  m)	
  ∈	
  Z+	
  
Exemplo	
  02	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
	
  
Logo,	
  para	
  todo	
  n	
  ∈	
  Z+,	
  o	
  número	
  
22n	
  –	
  1	
  é	
  divisível	
  por	
  3.	
  
69	
  
Princípio	
  da	
  indução	
  fraca	
  
Prove	
  que	
  para	
  todo	
  n	
  ∈	
  Z+,	
  o	
  
número	
  22n	
  –	
  1	
  é	
  divisível	
  por	
  3.	
  
1.  Caso	
  base	
  n	
  =	
  1	
  
u  22(1)	
  –	
  1	
  =	
  4	
  –	
  1	
  =	
  3	
  (divisível	
  por	
  3)	
  
2.  Passo	
  induDvo	
  
u  Hipótese:	
  22n	
  –	
  1	
  =	
  3m,	
  para	
  m,n	
  ∈	
  Z+	
  
u  Tese:	
  22(n+1)	
  –	
  1	
  =	
  3k,	
  para	
  	
  k	
  ∈	
  Z+	
  
22(n+1)	
  –	
  1	
  	
  =	
   22n+2	
  –	
  1	
  
=	
   22n	
  (22)	
  –	
  1	
  	
  
=	
   22n	
  (4)	
  –	
  1	
  	
  
=	
   22n	
  (3	
  +	
  1)	
  	
  –	
  1	
  
=	
   3(22n)	
  +	
  22n	
  –	
  1	
  
=	
   3(22n)	
  +	
  3m	
  
=	
   3(22n	
  +	
  m)	
  
Definição	
   Estrutura	
  de	
  demonstração	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
Princípio	
  da	
  indução	
  forte	
  
Se	
  	
  
①  [P(0)	
  ∧ P(1)	
  ∧...∧ P(k)]	
  →	
  P(k+1)*	
  	
  
	
  
Então	
  
ü  	
  	
  ∀n,	
  P(n)	
  
	
  
1.  Seja	
  n	
  ≥	
  0	
  abitrário	
  
2.  Suponha	
  ∀k	
  <	
  n,	
  P(k)	
  (hipótese	
  de	
  
indução)	
  
3.  Provar	
  P(k+1)	
  
4.  Concluir	
  ∀n,	
  P(n)	
  
	
  
70	
  
Princípio	
  da	
  indução	
  forte 	
  	
  
*Primeiro	
  elemento	
  do	
  conjunto,	
  não	
  	
  	
  	
  	
  	
  	
  
	
  	
  necessariamente	
  0	
  (zero)	
  
Exemplo	
  01	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
Caso	
  1:	
  (k+1)	
  é	
  primo	
  
Neste	
  caso	
  (k+1)	
  =	
  (k+1)(1),	
  
produto	
  de	
  dois	
  primos.	
  
71	
  
Princípio	
  da	
  indução	
  forte	
  
Prove	
  que	
  todo	
  n	
  >	
  1	
  ∈	
  Z+	
  pode	
  ser	
  
escrito	
  como	
  o	
  produto	
  de	
  números	
  
primos.	
  
1.  Caso	
  base	
  n	
  =	
  2	
  
u  2	
  =	
  2(1)	
  	
  	
  (produto	
  de	
  dois	
  primos)	
  
2.  Passo	
  induDvo	
  
u  Hipótese:	
  todo	
  2	
  ≤	
  r	
  ≤	
  k	
  ,	
  pode	
  ser	
  
escrito	
  como	
  o	
  produto	
  de	
  primos	
  
u  Tese:	
  	
  (k	
  +	
  1)	
  pode	
  ser	
  escrito	
  como	
  o	
  
produto	
  de	
  primos	
  
Exemplo	
  01	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática
Discreta 
Caso	
  2:	
  	
  (k+1)	
  não	
  é	
  primo	
  
Se	
  	
  (k+1)	
  não	
  é	
  primo,	
  então	
  (k+1)	
  é	
  
composto,	
  ou	
  seja,	
  
(k+1)	
  =	
  ab,	
  tal	
  que	
  2	
  ≤	
  a	
  ≤	
  b	
  	
  ≤	
  k.	
  
Por	
  hipótese,	
  todo	
  2	
  ≤	
  r	
  ≤	
  k	
  ,	
  é	
  o	
  
produto	
  de	
  primos.	
  
Logo,	
  a	
  e	
  b	
  podem	
  ser	
  escrito	
  como	
  
produtos	
  de	
  números	
  primos.	
  	
  
Portanto,	
  (k+1)	
  também	
  pode!	
  
72	
  
Princípio	
  da	
  indução	
  forte	
  
Prove	
  que	
  todo	
  n	
  >	
  1	
  ∈	
  Z+	
  pode	
  ser	
  
escrito	
  como	
  o	
  produto	
  de	
  números	
  
primos.	
  
1.  Caso	
  base	
  n	
  =	
  2	
  
u  2	
  =	
  2(1)	
  	
  	
  (produto	
  de	
  dois	
  primos)	
  
2.  Passo	
  induDvo	
  
u  Hipótese:	
  todo	
  2	
  ≤	
  r	
  ≤	
  k	
  ,	
  pode	
  ser	
  
escrito	
  como	
  o	
  produto	
  de	
  primos	
  
u  Tese:	
  	
  (k	
  +	
  1)	
  pode	
  ser	
  escrito	
  como	
  o	
  
produto	
  de	
  primos	
  
Exemplo	
  02	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
Por	
  hipótese,	
  temos	
  que	
  
u  (k	
  –	
  3)	
  pode	
  ser	
  escrito	
  como	
  a	
  
soma	
  de	
  4’s	
  ou	
  5’s	
  
u  Afinal,	
  12	
  ≤	
  (k	
  –	
  3)	
  ≤	
  k.	
  
Note	
  que	
  (k	
  +	
  1)	
  =	
  (k	
  –	
  3)	
  +	
  4.	
  	
  
Portanto,	
  (k	
  +	
  1)	
  também	
  pode	
  ser	
  
escrito	
  como	
  a	
  soma	
  de	
  4’s	
  ou	
  5’s.	
  
73	
  
Princípio	
  da	
  indução	
  forte	
  
Prove	
  que	
  todo	
  n	
  ≥	
  12	
  ∈	
  Z+	
  pode	
  ser	
  
obDdo	
  somando-­‐se	
  4’s	
  ou	
  5’s.	
  
1.  Caso	
  base	
  n	
  =	
  12,	
  13,	
  14,	
  15	
  
u  12	
  =	
  4	
  +	
  4	
  +	
  4 	
   	
  13	
  =	
  4	
  +	
  4	
  +	
  5	
  
u  14	
  =	
  4	
  +	
  5	
  +	
  5 	
   	
  15	
  =	
  5	
  +	
  5	
  +	
  5	
  
2.  Passo	
  induDvo	
  
u  Hipótese:	
  todo	
  15	
  ≤	
  r	
  ≤	
  k	
  é	
  a	
  soma	
  de	
  
4’s	
  ou	
  5’s	
  
u  Tese:	
  	
  (k	
  +	
  1)	
  é	
  a	
  soma	
  de	
  4’s	
  ou	
  5’s	
  
Exercícios	
  de	
  fixação	
  
Eduardo Freire Nakamura (nakamura@icomp.ufam.edu.br) Matemática Discreta 
74	
  
1.  Prove	
  que	
  para	
  todo	
  n	
  ∈	
  Z+	
  temos	
  que	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  .	
  
2.  Prove	
  que	
  que	
  11n	
  −	
  6	
  é	
  divisível	
  por	
  5	
  qualquer	
  n	
  ∈	
  Z+.	
  
3.  Prove	
  que	
  todo	
  n	
  ≥	
  8	
  ∈	
  Z+	
  pode	
  ser	
  obDdo	
  somando-­‐se	
  3’s	
  e	
  5’s.	
  
4.  A	
  função	
  de	
  Fibonacci	
  é	
  dada	
  por	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  .	
  
	
  	
  	
  	
  Prove	
  que	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  .	
  
2i
i=0
n
∑ = 2n+1 −1
F(n) =
0, !se!n = 0
1, !se!n =1
F(n−1)+F(n− 2), !se!n ≥ 2
#
$
%
&
%
F(n) = 15
1+ 5
2
!
"
#
$
%
&
n
−
1− 5
2
!
"
#
$
%
&
n(
)
*
*
+
,
-
-
__MACOSX/._parte-05-relacao-funcao.pdf