Upload
tchebraga
View
189
Download
17
Embed Size (px)
Citation preview
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
Conceitos Preliminares
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
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 I SAR O S CONCE I TO S D E LÓG I CA FORMAL
Fundamentos de Teoria da Computação Eduardo Freire Nakamura ([email protected])
2
Lógica formal
Lógica Formal
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
3
� Fornece bases para o método de pensar organizado;
� Expressa métodos de raciocínio sob a forma de argumentos.
� Tem duas aplicações diretas em Ciência da Computação 1. Programação Lógica 2. Prova se programas estão corretos ou não
� É análoga à lógica de circuitos de um computador
Lógica Formal
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
4
� Exemplos de uLlização em computação: ¡ Inteligência ArLficial; ¡ Circuitos Lógicos; ¡ Banco de Dados; ¡ Sistemas Computacionais (hardware e soWware) ¡ Sistemas Distribuídos; ¡ Teoria de autômatos e computabilidade; ¡ Teoria de linguagens;
Proposições
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
5
� Uma proposição é uma sentença declaraLva, ou uma afirmação, que admite apenas um dos dois valores lógicos verdadeiro ou falso, nunca ambos
� Proposições????? ¡ Manaus é a capital do Amazonas ¡ 1 + 1 = 2 ¡ Como você está? ¡ 9 < 6 ¡ Estudem regularmente ¡ Londres é na Dinamarca ¡ MatemáLca Discreta é fácil
Proposições
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
6
� PROPOSIÇÕES ATÔMICAS não podem ser sub-‐divididas em proposições mais simples ¡ Ex: O servidor de arquivos está desligado
� PROPOSIÇÕES COMPOSTAS são combinações de proposições atômicas via conecLvos lógicos ¡ Ex: A rede local está mal configurada ou o servidor de arquivos está
desligado ¡ O valor verdade é completamente determinado pelos valores-‐verdade das
subproposições junto com a forma que estão conectadas
Proposições
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
7
� PROPOSIÇÕES ATÔMICAS são representadas por meio de variáveis proposicionais ¡ Variáveis proposicionais: (P, Q, R, S, . . .) ¡ Constantes proposicionais: (V, F) → (T, F)
� Nas PROPOSIÇÕES COMPOSTAS, as variáveis proposicionais são combinadas através de pelo menos um operador ou conecLvo lógico
¡ Operadores lógicos são uLlizados para combinar proposições e formar novas proposições
ConecLvos Lógicos
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
8
� Terminologia
¡ Negação: ¬ ¡ Conjunção (e): ∧ ¡ Disjunção (ou): ∨ ¡ Condicional: → ¡ Bicondicional: ↔ ¡ QuanLficação Universal: ∀ ¡ QuanLficação Existencial: ∃
ConecLvos Lógicos
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
9
� Tabela da Verdade
� Negação
Negação P ¬P
V F
F V
ConecLvos Lógicos
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
10
� Tabela da Verdade
� Conjunção
Conjunção P Q P∧Q
V V V
V F F
F V F
F F F
ConecLvos Lógicos
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
11
� Tabela da Verdade
� Disjunção
Disjunção P Q P∨Q
V V V
V F V
F V V
F F F
ConecLvos Lógicos
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
12
� Tabela da Verdade
� Condicional
Condicional P Q P→Q
V V V
V F F
F V V
F F V
ConecLvos Lógicos
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
13
� Tabela da Verdade
� Bicondicional
Bicondicional P Q P↔Q
V V V
V F F
F V F
F F V
QuanLficação
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
14
� QuanLficação Universal ¡ ∀x P(x) ¡ P(x) é um predicado ¡ P(x) é verdadeiro para todo x
do universo
� Exemplo ¡ Todo número natural par ao
quadrado é par
� QuanLficação Existencial ¡ ∃x P(x) ¡ P(x) é um predicado ¡ P(x) é verdadeiro para algum x
do universo
� Exemplo ¡ Existe um número natural que
ao quadro é igual a ele mesmo
AfirmaLva Válida (Tautologia)
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
15
� Verdadeira para todos os valores verdades de suas sub afirmaLvas
� Exemplos ¡ P∨¬P ¡ P → P ¡ P ∨ (P → Q) ¡ P(a) →∃x P(x)
¡ ∀x P(x) ↔ ¬∃x ¬P(x)
Contradição
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
16
� Falsa para todos os valores-‐verdade de suas subafirmaLvas
� Exemplos ¡ P∧¬P ¡ P ↔ ¬P ¡ (P ∧ (P → Q)) ∧ ¬Q
¡ P(a) ∧ ¬∃x P(x) ¡ ∀x P(x) ∧ ∃x ¬P(x)
Equivalência Lógica
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
17
� Duas proposições P e Q são logicamente equivalentes (P ≡ Q), se ambas possuem tabelas-‐verdade idênLcas
� Exemplos ¡ P∨Q ≡ Q∨P ¡ P ∨ (Q ∧ R) ≡ (P ∨ Q) ∧ (P ∨ R) ¡ ¬(P ∧ Q) ≡ ¬P ∨ ¬Q ¡ P → Q ≡ ¬P ∨ Q ¡ P ↔ Q ≡ (P → Q) ∧ (Q → P) ¡ ¬∀x P(x) ≡ ∃x ¬P(x)
Regras de equivalência
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
18
Fórmula Lei P∨P ≡ P P∧P ≡ P Idempotência
(P∨Q)∨R ≡ P∨(Q∨R) (P∧Q)∧R ≡ P∧(Q∧R) AssociaLva
P∨Q ≡ Q∨P P∧Q ≡ Q∧P ComutaLva
(P∧Q)∨R ≡ (P∨R)∧(Q∨R) (P∨Q)∧R ≡ (P∧R)∨(Q∧R) DistribuLva
P∨F ≡ P P∨V ≡ V
P∧V ≡ P P∧F ≡ F IdenLdade
Regras de equivalência
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
19
Fórmula Lei P∨¬P ≡ V ¬V ≡ F
P∧¬P ≡ F ¬F ≡ V Complemento
¬¬P ≡ P Involução ¬(P∧Q) ≡ ¬P∨¬Q ¬(P∨Q) ≡ ¬P∧¬Q DeMorgan
P→Q ≡ ¬P∨Q Condicional
Regras de equivalência (resumo)
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
20
Fórmula Lei P∨P ≡ P P∧P ≡ P Idempotência
(P∨Q)∨R ≡ P∨(Q∨R) (P∧Q)∧R ≡ P∧(Q∧R) AssociaLva
P∨Q ≡ Q∨P P∧Q ≡ Q∧P ComutaLva
(P∧Q)∨R ≡ (P∨R)∧(Q∨R) (P∨Q)∧R ≡ (P∧R)∨(Q∧R) DistribuLva
P∨F ≡ P P∨V ≡ V
P∧V ≡ P P∧F ≡ F IdenLdade
P∨¬P ≡ V ¬V ≡ F
P∧¬P ≡ F ¬F ≡ V Complemento
¬¬P ≡ P Involução
¬(P∧Q) ≡ ¬P∨¬Q ¬(P∨Q) ≡ ¬P∧¬Q DeMorgan
P→Q ≡ ¬P∨Q Condicional
Consequência Lógica (Implicação Lógica)
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
21
� P ⇒ Q, se Q é verdade sempre que P é verdade
� Exemplos ¡ {P → Q, P} ⇒ Q ¡ {P → Q, ¬Q} ⇒ ¬P ¡ {P → Q, ¬P → Q} ⇒ Q ¡ {P → Q, Q → R} ⇒ P → R ¡ {P(a)} ⇒ ∃x P(x) ¡ {P(a), ∀x (P(x) → Q(x))} ⇒ Q(a)
Exemplos de regras de inferência
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
22
Modus ponens
P
P→Q
Q
FTC é fácil SE FTC é fácil, ENTÃO serei aprovado
serei aprovado
Exemplos de regras de inferência
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
23
Modus ponens
P
P→Q
Q
Modus tollens
¬Q
P→Q
¬P
NÃO fui aprovado SE estudei, ENTÃO fui aprovado
NÃO estudei
Exemplos de regras de inferência
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
24
Modus ponens
P
P→Q
Q
Modus tollens
¬Q
P→Q
¬P
Conjunção
P
Q
P∧Q
estudei fui aprovado
estudei E fui aprovado
Exemplos de regras de inferência
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
25
Modus ponens
P
P→Q
Q
Modus tollens
¬Q
P→Q
¬P
Conjunção
P
Q
P∧Q
Adição
P
P∨Q
estudei estudei OU dormi
Exemplos de regras de inferência
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
26
Modus ponens
P
P→Q
Q
Modus tollens
¬Q
P→Q
¬P
Conjunção
P
Q
P∧Q
Adição
P
P∨Q
Silogismo hipotéLco
P→Q
Q→R
P→R
SE estudar, ENTÃO FTC é fácil SE FTC é fácil, ENTÃO serei aprovado SE estudar, ENTÃO serei aprovado
Exemplos de regras de inferência
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
27
Modus ponens
P
P→Q
Q
Modus tollens
¬Q
P→Q
¬P
Conjunção
P
Q
P∧Q
Adição
P
P∨Q
Silogismo hipotéLco
P↔Q
Q↔R
P↔R
Silogismo hipotéLco
P→Q
Q→R
P→R
estudo SE, E SOMENTE SE, quero passar quero passar SE, E SOMENTE SE, aprendo
estudo SE, E SOMENTE SE, aprendo
Exemplos de regras de inferência
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
28
Modus ponens
P
P→Q
Q
Modus tollens
¬Q
P→Q
¬P
Conjunção
P
Q
P∧Q
Adição
P
P∨Q
Silogismo disjunLvo
P∨Q
¬Q
P
Silogismo hipotéLco
P↔Q
Q↔R
P↔R
Silogismo hipotéLco
P→Q
Q→R
P→R
estudei OU dormi NÃO dormi
estudei
Exemplos de regras de inferência
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
29
Modus ponens
P
P→Q
Q
Modus tollens
¬Q
P→Q
¬P
Conjunção
P
Q
P∧Q
Adição
P
P∨Q
Silogismo disjunLvo
P∨Q
¬Q
P
Silogismo hipotéLco
P↔Q
Q↔R
P↔R
Silogismo hipotéLco
P→Q
Q→R
P→R
Exemplo
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
30
� Você está saindo para a UFAM de manhã e percebe que não está usando os óculos. Ao tentar descobrir onde estão os óculos você começa a pensar sobre os seguintes fatos que são verdadeiros 1. Se os meus óculos estão na mesa da cozinha então eu os vi no café da
manhã; 2. Eu estava lendo o jornal na sala de estar ou eu estava lendo o jornal na
cozinha; 3. Se eu estava lendo o jornal na sala de estar então meus óculos estão na mesa
do café; 4. Eu não vi meus óculos no café da manhã; 5. Se eu estava lendo um livro na cama então meus óculos estão no criado-‐
mudo; 6. Se eu estava lendo o jornal na cozinha então meus óculos estão na mesa da
cozinha;
Exemplo
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
31
� Você está saindo para a UFAM de manhã e percebe que não está usando os óculos. Ao tentar descobrir onde estão os óculos você começa a pensar sobre os seguintes fatos que são verdadeiros 1. Se os meus óculos estão na mesa da cozinha então eu os vi no café da
manhã; P→Q 2. Eu estava lendo o jornal na sala de estar ou eu estava lendo o jornal na
cozinha; 3. Se eu estava lendo o jornal na sala de estar então meus óculos estão na mesa
do café; 4. Eu não vi meus óculos no café da manhã; 5. Se eu estava lendo um livro na cama então meus óculos estão no criado-‐
mudo; 6. Se eu estava lendo o jornal na cozinha então meus óculos estão na mesa da
cozinha;
Exemplo
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
32
� Você está saindo para a UFAM de manhã e percebe que não está usando os óculos. Ao tentar descobrir onde estão os óculos você começa a pensar sobre os seguintes fatos que são verdadeiros 1. Se os meus óculos estão na mesa da cozinha então eu os vi no café da
manhã; P→Q 2. Eu estava lendo o jornal na sala de estar ou eu estava lendo o jornal na
cozinha; R∨S 3. Se eu estava lendo o jornal na sala de estar então meus óculos estão na mesa
do café; 4. Eu não vi meus óculos no café da manhã; 5. Se eu estava lendo um livro na cama então meus óculos estão no criado-‐
mudo; 6. Se eu estava lendo o jornal na cozinha então meus óculos estão na mesa da
cozinha;
Exemplo
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
33
� Você está saindo para a UFAM de manhã e percebe que não está usando os óculos. Ao tentar descobrir onde estão os óculos você começa a pensar sobre os seguintes fatos que são verdadeiros 1. Se os meus óculos estão na mesa da cozinha então eu os vi no café da
manhã; P→Q 2. Eu estava lendo o jornal na sala de estar ou eu estava lendo o jornal na
cozinha; R∨S 3. Se eu estava lendo o jornal na sala de estar então meus óculos estão na mesa
do café; R→T 4. Eu não vi meus óculos no café da manhã; 5. Se eu estava lendo um livro na cama então meus óculos estão no criado-‐
mudo; 6. Se eu estava lendo o jornal na cozinha então meus óculos estão na mesa da
cozinha;
Exemplo
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
34
� Você está saindo para a UFAM de manhã e percebe que não está usando os óculos. Ao tentar descobrir onde estão os óculos você começa a pensar sobre os seguintes fatos que são verdadeiros 1. Se os meus óculos estão na mesa da cozinha então eu os vi no café da
manhã; P→Q 2. Eu estava lendo o jornal na sala de estar ou eu estava lendo o jornal na
cozinha; R∨S 3. Se eu estava lendo o jornal na sala de estar então meus óculos estão na mesa
do café; R→T 4. Eu não vi meus óculos no café da manhã; ¬Q 5. Se eu estava lendo um livro na cama então meus óculos estão no criado-‐
mudo; 6. Se eu estava lendo o jornal na cozinha então meus óculos estão na mesa da
cozinha;
Exemplo
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
35
� Você está saindo para a UFAM de manhã e percebe que não está usando os óculos. Ao tentar descobrir onde estão os óculos você começa a pensar sobre os seguintes fatos que são verdadeiros 1. Se os meus óculos estão na mesa da cozinha então eu os vi no café da
manhã; P→Q 2. Eu estava lendo o jornal na sala de estar ou eu estava lendo o jornal na
cozinha; R∨S 3. Se eu estava lendo o jornal na sala de estar então meus óculos estão na mesa
do café; R→T 4. Eu não vi meus óculos no café da manhã; ¬Q 5. Se eu estava lendo um livro na cama então meus óculos estão no criado-‐
mudo; U→X 6. Se eu estava lendo o jornal na cozinha então meus óculos estão na mesa da
cozinha;
Exemplo
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
36
Fatos transformados em proposições 1. P→Q 2. R∨S 3. R→T 4. ¬Q 5. U→X 6. S→P
Variável Argumento P meus óculos estão na mesa da cozinha
Q eu os vi no café da manhã
R estava lendo o jornal na sala de estar
S eu estava lendo o jornal na cozinha
T meus óculos estão na mesa do café
U eu estava lendo um livro na cama
X meus óculos estão no criado-‐mudo
Exemplo
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
37
Fatos transformados em proposições 1. P→Q 2. R∨S 3. R→T 4. ¬Q 5. U→X 6. S→P
1. P→Q
4. ¬Q
Exemplo
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
38
Fatos transformados em proposições 1. P→Q 2. R∨S 3. R→T 4. ¬Q 5. U→X 6. S→P
1. P→Q
4. ¬Q
7. ¬P Modus tollens
Exemplo
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
39
Fatos transformados em proposições 1. P→Q 2. R∨S 3. R→T 4. ¬Q 5. U→X 6. S→P
1. P→Q
4. ¬Q
7. ¬P Modus tollens
6. S→P
7. ¬P
Exemplo
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
40
Fatos transformados em proposições 1. P→Q 2. R∨S 3. R→T 4. ¬Q 5. U→X 6. S→P
1. P→Q
4. ¬Q
7. ¬P Modus tollens
6. S→P
7. ¬P
8. ¬S Modus tollens
Exemplo
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
41
Fatos transformados em proposições 1. P→Q 2. R∨S 3. R→T 4. ¬Q 5. U→X 6. S→P
1. P→Q
4. ¬Q
7. ¬P Modus tollens
6. S→P
7. ¬P
8. ¬S Modus tollens
2. R∨S
8. ¬S
Exemplo
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
42
Fatos transformados em proposições 1. P→Q 2. R∨S 3. RàT 4. ¬Q 5. U→X 6. S→P
1. P→Q
4. ¬Q
7. ¬P Modus tollens
6. S→P
7. ¬P
8. ¬S Modus tollens
2. R∨S
8. ¬S
9. R Silogismo disjun@vo
9. R→T
8. R
Exemplo
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
43
Fatos transformados em proposições 1. P→Q 2. R∨S 3. R→T 4. ¬Q 5. U→X 6. S→P
1. P→Q
4. ¬Q
7. ¬P Modus tollens
6. S→P
7. ¬P
8. ¬S Modus tollens
2. R∨S
8. ¬S
9. R Silogismo disjun@vo
9. R→T
8. R 10. T Modus Ponens
Exemplo
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
44
Fatos transformados em proposições 1. P→Q 2. R∨S 3. R→T 4. ¬Q 5. U→X 6. S→P
1. P→Q
4. ¬Q
7. ¬P Modus tollens
6. S→P
7. ¬P
8. ¬S Modus tollens
2. R∨S
8. ¬S
9. R Silogismo disjun@vo
9. R→T
8. R 10. T Modus Ponens
Exemplo
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
45
Fatos transformados em proposições 1. P→Q 2. R∨S 3. R→T 4. ¬Q 5. U→X 6. S→P
Variável Argumento P meus óculos estão na mesa da cozinha
Q eu os vi no café da manhã
R estava lendo o jornal na sala de estar
S eu estava lendo o jornal na cozinha
T meus óculos estão na mesa do café
U eu estava lendo um livro na cama
X meus óculos estão no criado-‐mudo
OB J E T I VO
R EV I SAR A S P R INC I PA I S T É CN I CA S D E P ROVA D E T EOREMAS
Fundamentos de Teoria da Computação Eduardo Freire Nakamura ([email protected])
46
Prova de teoremas
Prova de teoremas
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
47
� Argumentação induLva ¡ Parte de dados da experiência para concluir que uma dada proposição,
provavelmente, é verdadeira ¡ Exemplo: se em várias situações, sempre que P é verdade, Q também é,
formula-‐se a conjectura P→Q
� Argumentação induLva é uma prova?
Argumentação induLva
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
48
Considere o seguinte exemplo:
Seja o polinômio p(x) = x2 + x + 41, então ∀x ∈ N, p(x) é primo?
Verificando a conjectura observamos….
Parece verdade… Podemos assumir válida a conjectura?
Não, p(40) = 1681 não é um número primo, 1681 = 41*41!
x 0 1 2 3 … 20 … 39
p(x) 41 43 47 53 … 461 … 1601 Todos primos!
Outro caso…
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
49
Em 1769, Euler conjecturou que a4 + b4 + c4 = d4 não Lnha solução no conjunto dos números
inteiros posiLvos
http
://e
n.w
ikip
edia
.org
/wik
i/Le
onha
rd_E
uler
http
://w
ww
.log2
4.co
m/l
og/p
ix06
/060
410-
Elki
es3.
jpg
218 anos depois, em 1987, Noam Elkies provou que a conjectura era falsa, pois
95.8004 + 217.5194 + 414.5604 = 422.4814
Mais um…
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
50
� Conjectura: 313(x3+y3) = z3 não tem solução no conjunto dos inteiros posiLvos ¡ Falso, mas o menor contra-‐exemplo tem mais de 1000 dígitos ¡ O computador mais “poderoso” não seria capaz de obter essa solução
usando uma estratégia exausLva
O úlLmo teorema de Fermat
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
51
� Pierre de Fermat (1601/1607 – 1665) ¡ Advogado e, nas horas vagas, matemáLco ¡ Contribuições
÷ Cálculo infinitesimal
÷ Teoria dos números
÷ Gemoetria analíLca
÷ Probabilidade
÷ ÓLca
¡ Já como advogado …
http
://e
n.w
ikip
edia
.org
/wik
i/Pi
erre
_de_
Ferm
at
O úlLmo teorema de Fermat
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
52
� Em 1637, ele escreveu o “úlLmo teorema de Fermat”, como uma nota parLcular nas margens da obra ArithmeLca, escrita pelo matemáLco grego Diophantus 300 anos A.C.
“É impossível separar um cubo em dois cubos, ou uma quarta potência em duas quartas potências, ou em geral, qualquer potência maior que dois, em duas potências da mesma ordem. Eu descobri uma prova maravilhosa para este problema,
mas não cabe nesta margem”
� Fermat morreu em 1665 sem revelar a sua maravilhosa prova!
Não existem inteiros posiLvos a, b, c e n, com n > 2 que saLsfaçam an = bn + cn
O úlLmo teorema de Fermat
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
53
� Andrew Wiles provou o teorema em 1995* ¡ Trabalho de sete anos de pesquisa ¡ ArLgo de 108 páginas ¡ Introdução, cinco capítulos, mais apêndice
http
://e
n.w
ikip
edia
.org
/wik
i/W
iles'_
proo
f_of
_Fer
mat
's_La
st_T
heor
em
*http://en.wikipedia.org/wiki/Wiles'_proof_of_Fermat's_Last_Theorem
Fermat's Last Theorem: The story of a riddle that confounded the world's greatest minds for 358 years Simon Singh
Um caso em aberto…
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
54
� Conjectura de Goldbach (1690–1764) ¡ 07/06/1742 carta para Euler
¡ “Todo inteiro par maior que 2 é a soma de dois primos”
¡ Verificada até 4x1018 (04/04/2012)*
¡ Para valores entre 4x1018 e ∞ ?
*www.ieeta.pt/~tos/goldbach.html
Imagem: h�p://en.wikipedia.org/wiki/Goldbach's_conjecture
Por quê?
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
55
� Por que esses problemas são importantes? ¡ Achar soluções para tais equações é importante na área de curvas elípLcas ¡ Curvas elípLcas são importantes no estudo de fatoração de inteiros
“grandes” ¡ Fatorar inteiros “grandes” é importante no estudo de sistemas
criptográficos ¡ Criptografia é a base de todos os sistemas seguros de comunicação
atualmente!
Prova de teoremas
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
56
� Argumentação induLva ¡ Apenas para conjecturar
� Argumentação deduLva ¡ Garante que se todas as premissas forem verdadeiras, a conclusão
também o será; ¡ Exemplo: demonstrar P→Q (de conjectura, torna-‐se teorema); ¡ Duas opções
1. Provar o teorema
2. Encontrar um contra-‐exemplo
Prova de teoremas
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
57
� Contra-‐exemplo ¡ Apenas um é sufiente para provar a falsidade ¡ Se um contra-‐exemplo não for encontrado, não há garanLas de que a
conjectura é verdadeira
� Encontre um contra-‐exemplo para a conjectura ¡ Para todo inteiro posiLvo n, n! ≤ n2 ¡ Todo inteiro menor que 10 é maior do que 5
O que fazer quando não é possível encontrar um contra-‐exemplo?
Solução: Buscar uma prova
O que é uma prova?
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
58
� Em Ciência, a verdade surge da experimentação
� Na Lei, a verdade é avaliada por um julgamento e decidida por um juíz ou um júri
� Em MatemáLca temos a prova ¡ Argumentação que mostra, de maneira indiscu�vel, que uma afirmação é
verdadeira ¡ As provas matemáLcas são estruturadas cuidadosamente e escritas em
uma forma esLlizada
Exemplo
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
59
� Hipótese
� Todos números ímpares maiores que 1 são primos
� MatemáLco
� 3 é primo, 5 é primo, 7 é primo, mas 9 = 3*3, não é primo. Portanto, a hipótese é falsa!
Exemplo
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
60
� Hipótese
� Todos números ímpares maiores que 1 são primos
� Físico experimental
� 3 é primo, 5 é primo, 7 é primo, mas 9 não é primo, 11 é primo, 13 é primo. Portanto, 9 deve ser um erro experimental, e assim, a hipótese é verdadeira!
Exemplo
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
61
� Hipótese
� Todos números ímpares maiores que 1 são primos
� Advogado
� Senhores e senhoras do júri: não há dúvida que números ímpares são primos. A evidência é clara: 3 é primo, 5 é primo, 7 é primo, 9 é primo, 11 é primo, e assim por diante!
Obje/vo: Provar que P→Q
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
� Abordagem ¡ Mostrar que P→Q para
todos os elementos do domínio individualmente
¡ O domínio deve ser um conjunto finito
Prova:
Sim, pois: ¡ 12 = 1 ≤ 10 + 5(1) = 15 ¡ 22 = 4 ≤ 10 + 5(2) = 20 ¡ 32 = 9 ≤ 10 + 5(3) = 25 ¡ 42 = 16 ≤ 10 + 5(4) = 30 ¡ 52 = 25 ≤ 10 + 5(5) = 35
62
Técnicas de prova: demonstração exausLva
Para qualquer inteiro posi@vo menor ou igual a 5, o quadrado do inteiro é menor ou igual à soma de 10 mais 5 vezes o inteiro?
Demonstração
Obje/vo: Provar que P→Q
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
� Abordagem ¡ Mostrar que P→Q para
todos os elementos do domínio individualmente
¡ O domínio deve ser um conjunto finito
� Exemplo A
Prova:
Não, pois 72 = 49 é maior que 10 + 5(7) = 45!
Há outros contra-‐exemplos?
É preciso mostrar mais de um?
63
Técnicas de prova: falsidade por contra-‐exemplo
Para qualquer inteiro posi@vo, o quadrado do inteiro é menor ou igual à soma de 10 mais 5 vezes o inteiro?
Demonstração
Obje/vo: Provar que P→Q
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
� Abordagem P→Q ¡ Supor P (hipótese) ¡ Derivar Q (tese)
� Exemplo A
Prova:
P (hipótese): x e y são inteiros pares
Q (tese): xy é um inteiro par
Sejam os inteiros pares x = 2m e y = 2n, onde m,n ∈ Z. Portanto, xy = (2m)(2n) = 2(2mn). Como 2mn é um inteiro, xy é um inteiro par.
64
Técnicas de prova: direta
Prove que o produto de dois inteiros pares é par.
Demonstração
Obje/vo: Provar que P→Q
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
� Abordagem P→Q ¡ Supor P (hipótese) ¡ Derivar Q (tese)
� Exemplo B
Prova:
P (hipótese): x = 6k, k ∈ Z
Q (tese): 2x = 4m, m ∈ Z
Seja x = 6k, tal que k ∈ Z. Portanto, 2x = 2(6k) = 4(3k). Como 3k é inteiro, 2x é um inteiro divisível por 4.
65
Técnicas de prova: direta
Se um inteiro é divisível por 6, então duas vezes esse inteiro é divisível por 4.
Demonstração
Obje/vo: Provar que P→Q
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
� Abordagem ¬Q→¬P ¡ Supor ¬Q (hipótese) ¡ Derivar ¬P (tese)
� Exemplo A
Prova:
¬Q (hipótese): x é par
¬P (tese): x2 é par
Seja x = 2k, tal que k ∈ Z. Portanto, x2 = (2k)2 = 2(2k2) . Como k2 é um inteiro, x2 é um inteiro par. Logo, se o quadrado de um inteiro é ímpar, então o inteiro tem que ser ímpar.
66
Técnicas de prova: pela contraposiLva
Se o quadrado de um inteiro é ímpar, então o inteiro tem que ser ímpar.
Demonstração
Obje/vo: Provar que P→Q
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
� Abordagem ¬Q→¬P ¡ Supor ¬Q (hipótese) ¡ Derivar ¬P (tese)
� Exemplo B
Prova:
¬Q (hipótese): a ou b divisíveis por k
¬P (tese): ab divisível por k
Caso 1. Sejam a = mk e b, tais que m, k, b ∈ Z. Assim, ab = k(bm). Como bm é inteiro, ab é um inteiro divisível por k.
Caso 2. Sejam b = nk e a, tais que a, n, k ∈ Z. Assim, ab = k(an). Como mb é inteiro, ab é um inteiro divisível por k.
67
Técnicas de prova: pela contraposiLva
Se o produto de dois inteiros a e b não é divisível por um inteiro k, então os dois inteiros a e b não são divisíveis por k.
Demonstração
Obje/vo: Provar que P→Q
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
� Abordagem ¡ Supor P∧¬Q (hipótese) ¡ Derivar F, contradição (tese)
� Exemplo A
Prova:
Hipótese: x+x = x , x ≠ 0
Tese: F, uma contradição
Seja x um inteiro. Por hipótese, x + x = x, ou seja, x = x – x e, portanto, x = 0. Mas por hipótese, x ≠ 0, uma contradição.
68
Técnicas de prova: por contradição
Se um inteiro somado a ele mesmo é igual a ele mesmo, então esse número é 0.
Demonstração
Obje/vo: Provar que P→Q
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
� Abordagem ¡ Supor P∧¬Q (hipótese) ¡ Derivar F, contradição (tese)
� Exemplo B
Prova:
Hipótese: a, b ímpares, ab par
Tese: F, uma contradição
Sejam a = 2m+1 e b = 2n+1, tais que m, n ∈ Z. Portanto, ab = (2m+1)(2n+1) = 2(2mn + m + n) + 1. Como, m e n são inteiros, ab é um inteiro ímpar. Mas por hipótese, ab é par, uma contradição.
69
Técnicas de prova: por contradição
O produto de dois inteiros ímpares não é par.
Demonstração
Exercício
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
70
Prove as seguintes proposições 1. Se n é um inteiro par, 4 ≤ n ≤ 12, então n é uma soma de dois números
primos 2. A soma de um inteiro par com um inteiro ímpar é ímpar. 3. O produto de dois inteiros ímpares é ímpar. 4. O produto de dois inteiros consecuLvos é par. 5. Se a e b são números reais, tais que 0 < a < b, então a2 < b2.
OB J E T I VO
R EV I SAR O S CONCE I TO S BÁ S I CO S D E CON JUNTOS
Fundamentos de Teoria da Computação Eduardo Freire Nakamura ([email protected])
71
Conjuntos
Conjuntos
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
72
� Conjunto é uma abstração matemáLca que visa capturar o conceito de coleção ¡ Lista não ordenada de
elementos ou membros ¡ {1, 2} = {2, 1}
� Notação ¡ a ∈ A: a pertence ao conjunto A ¡ a ∉ A: a não pertence ao
conjunto A
� Exemplos ¡ {PAA, FTC, AED, IHC, ICC} ¡ {7, PAA, {1}, {FTC, 3, 4}}
Tipos de conjuntos e conjuntos importantes
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
73
� Conjunto vazio: ∅
� Conjunto unitário
� Conjunto finito e infinito
� N: números naturais
� Z: números inteiros
� R: números reais
� Q: números racionais
� Notações ¡ { x | P(x) }
÷ Exemplo: { k | k = 2n+1 e n ∈ N }
¡ { x ∈ A|P(x) }
÷ Exemplo: { k ∈ R | 0 ≤ k ≤ 1 }
Relações básicas entre conjuntos
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
74
Subconjunto: A ⊆ B se, e somente se, ∀x (x ∈ A → x ∈ B) Subconjunto próprio: A ⊂ B se, e somente se, A ⊆ B e A≠B
• ∅ ⊆ A • ∅ ⊂ A se A ≠ ∅ • ∅ ⊄ ∅
• N ⊂ Z • N ⊆ Z+ • R ⊄ N
Operações sobre conjuntos
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
75
h�p://nameson
node
s.org/ns/m
ath/2009/im
ages/set-‐ope
raLo
ns.png
União
A ∪ B = { x | (x ∈ A) ∨ (x ∈ B) }
Interseção
A ∩ B = { x | (x ∈ A) ∧ (x ∈ B) }
Diferença
A \ B = { x | (x ∈ A) ∧ (x ∉ B) }
Definição Exemplos
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
Dois conjuntos A e B são disjuntos se, e somente se, A ∩ B = ∅
� {1,2,3} e {5,4,9}
� ∅ e N
� A\B e B\A
� N e Z−
76
Conuntos disjuntos
A B
Algumas idenLdades
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
77
� IdenLdades sobre conjuntos
¡ A ∩ B = B ∩ A
¡ A ∪ B = B ∪ A
¡ A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
¡ A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
¡ (A = B) ↔ (A ⊆ B) ∧ (B ⊆ A)
Interseção de n conjuntos
União de n conjuntos
União e interseção generalizadas
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
78
Aii=1
n
∪ = A1∪A2∪"∪An
Aii=1
n
∩ = A1∩A2∩"∩An
ParLção
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
79
Par/ção de um conjunto
Uma parLção de A é um conjunto de subconjuntos de A dado por {B1, B2, …, Bn} tal que • Bi ≠ ∅, para 1 ≤ i ≤ n; • Bi∩ Bj = ∅, para 1 ≤ i < j ≤ n; • ∪1≤i≤n Bi = A
Definição Exemplo
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
Conjunto potência de A, denotado por P (A) é o conjunto formado por todos os subconjuntos de A
P (A) = { X | X ⊆ A}
Que conjunto é P ({1,2,3}) ?
{ ∅, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} }
Se |A| denota o tamanho de A, qual é o valor de |P (A)|?
|P (A)| = 2|A|
80
Conjunto potência
Definição Exemplos
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
� Produto cartesiano entre dois conjuntos A e B, denotado por A×B é formado pelo conjunto de pares ordenados (a,b) tais que a ∈ A e b ∈ B, ou seja,
� ∅ × {1,2} = ∅
� {1,2} × {3,4} = {(1,3), (1,4), (2,3), (2,4)}
� |A × B| = |A|.|B|, se A e B finitos
� An = A × A × ... × A (n vezes)
81
Produto cartesiano
A×B = { (a,b) | a ∈ A ∧ b ∈ B }
OB J E T I VO
R EV ER O S CONCE I TO S D E R E LAÇÃO E FUNÇÃO
Fundamentos de Teoria da Computação Eduardo Freire Nakamura ([email protected])
82
Relação e função
Definição informal Exemplos
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
� O que significa relacionar dois objetos? ¡ Comparar dois objetos segundo
uma regra definida ¡ Relação é uma comparação
entre dois “objetos”
� MatemáLca ¡ “Menor do que” ¡ “Maior do que” ¡ “É paralelo à” ¡ “É um subconjunto de”
83
O que é uma relação?
Definição formal Exemplo
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
� Relação binária: R ⊆ A × B
¡ Domínio: A ¡ Contradomínio: B ¡ Imagem: { y | (x,y) ∈ R para algum x }
� Notação
� Relação binária: < ⊆ N × N
¡ Domínio: N ¡ Contradomínio: N ¡ Imagem: N – {0}
{ y | (x,y) ∈ R para x menor que y }
84
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
Tipos de relações binárias
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
85
A B A B
A B A B
um-‐para-‐um
muitos-‐para-‐um
muitos-‐para-‐muitos
um-‐para-‐muitos
Propriedades de uma relação
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
86
Quais as propriedades das relações abaixo?
� > sobre N
Reflexiva, Simétrica, TransiLva?
� ≥ sobre N
Reflexiva, Simétrica, TransiLva?
� ⊆ sobre P (N)
Reflexiva, Simétrica, TransiLva?
� = sobre N
Reflexiva, Simétrica, TransiLva?
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)
- TransiLva: ∀x,y,z ∈ A, (xRy ∧ yRz) à xRz
Reflexiva, Simétrica, TransiLva
Reflexiva, Simétrica, TransiLva
Reflexiva, Simétrica, TransiLva
Reflexiva, Simétrica, TransiLva
- (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 ([email protected]) Fundamentos de Teoria da Computação
87
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 ([email protected]) Fundamentos de Teoria da Computação
88
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!queg ! f( )(x) = g x +1( ) = 2− x +1( ) =1− x
f ! g :N→N, !tal!quef ! g( )(x) = f 2− x( ) = 2− x +1
Tipos de funções
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
89
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
OB J E T I VO
D E F I N I R E A PR ENDER A R E CONHEC ER CON JUNTOS ENUMERÁVE I S E NÃO ENUMERÁVE I S
Fundamentos de Teoria da Computação Eduardo Freire Nakamura ([email protected])
90
Conjuntos enumeráveis
Conjunto enumerável
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
91
� Tamanho de um conjunto finito A
¡ Representado por |A| ¡ Corresponde ao número de elementos em A
� Dados A = {1,2,3,4,5} e B = {a,b,c,d,e,f,g,h}
¡ Quem é maior A ou B? ¡ |A| = 5, |B| = 8
� E se A e B são infinitos? Como compara-‐los?
¡ Quem é maior N ou Z? ¡ Quem é maior Z ou R?
http://www.kaninekisses.com/sitebuilder/images/great_dane_and_chihuahua-325x245.png
Conjunto enumerável
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
92
- Se card(A) = n, tal que n ∈ N, ou ainda, card(A) = |A|, então A é finito
- A é infinito se existe X ⊂ A, tal que card(X) = card(A)
Cardinalidade
Dois conjuntos A e B, possuem mesma cardinalidade, card(A) = card(B), se existe uma função bijetora de A para B
Conjunto enumerável e conjunto contável
- Um conjunto A é dito enumerável, se card(A) = card(N)
- Um conjunto A é dito contável, se A é finito ou enumerável
Conjunto enumerável
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
93
A é enumerável se existe uma bijeção f : N → A, ou uma bijeção f : A → N
Cardinalidade
Dois conjuntos A e B, possuem mesma cardinalidade, card(A) = card(B), se existe uma função bijetora de A para B
Conjunto enumerável e conjunto contável
- Um conjunto A é dito enumerável, se card(A) = card(N)
- Um conjunto A é dito contável, se A é finito ou enumerável
Conjunto enumerável
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
94
Se A é enumerável, então seus elementos podem ser colocados em sequência
Cardinalidade
Dois conjuntos A e B, possuem mesma cardinalidade, card(A) = card(B), se existe uma função bijetora de A para B
Conjunto enumerável e conjunto contável
- Um conjunto A é dito enumerável, se card(A) = card(N)
- Um conjunto A é dito contável, se A é finito ou enumerável
Um exemplo
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
95
Z− à −1 −2 −3 −4 −5 −6 −7 −8 −9 −10 −11 −12 … −∞
N à 0 1 2 3 4 5 6 7 8 9 10 11 12 … ∞
Z+ ∪ {0} à 0 1 2 3 4 5 6 7 8 9 10 11 12 … ∞
Se A é enumerável, então seus elementos podem ser colocados em sequência
A é enumerável se existe uma bijeção f : N → A, ou uma bijeção f : A → N
Um exemplo
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
96
Z− à −1 −2 −3 −4 −5 −6 −7 −8 −9 −10 −11 −12 … −∞
N à 0 1 2 3 4 5 6 7 8 9 10 11 12 … ∞
Z+ ∪ {0} à 0 1 2 3 4 5 6 7 8 9 10 11 12 … ∞
- N ⊂ Z, na verdade, Z = N ∪ Z− , então quem é maior? - Existe uma função bijetora de Z para N? - Qual sequência é possível formar?
??
Z− à −1 −2 -‐3 −4 -‐5 −6 −7 ...
N à 0 1 2 3 4 5 6 7 8 9 10 11 12 13 ...
Z+ ∪ {0} à 0 1 2 3 4 5 6 ...
Um exemplo
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
97
- N ⊂ Z, na verdade, Z = N ∪ Z− , então quem é maior? - Existe uma função bijetora de Z para N? - Qual sequência é possível formar?
Z colocado em uma sequência possível
N à 0 1 2 3 4 5 6 7 8 9 10 11 12 13 ...
Z à 0 −1 1 −2 2 −3 3 −4 4 −5 5 −6 6 −7 ...
Um exemplo
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
98
Se A é enumerável, então seus elementos podem ser colocados em sequência
Um exemplo
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
99
f :N→ Z, !tal!que,
f (x) =
x2, se!x !é!par
−x +12, se!x !é!ímpar
#
$%%
&%%
N à 0 1 2 3 4 5 6 7 8 9 10 11 12 13 ...
Z à 0 −1 1 −2 2 −3 3 −4 4 −5 5 −6 6 −7 ...
Se A é enumerável, então seus elementos podem ser colocados em sequência
Mais um exemplo
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
100
� O racionais posiLvos Q+ é enumerável? ¡ Q+ = { a/b | a ∈ N+ ∧ b ∈ N+ } ¡ Considere a função
f : Q+ → N, bijetora, que mapeia a/b em um natural
f(a,b) b
1 2 3 4 5 …
a
1 0 1 3 6 10 …
2 2 4 7 11 …
3 5 8 12 …
4 9 13 …
5 14 … N
… …
Mais um exemplo
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
101
� O racionais posiLvos Q+ é enumerável? ¡ Q+ = { a/b | a ∈ N+ ∧ b ∈ N+ } ¡ Considere a função
f : Q+ → N, bijetora, que mapeia a/b em um natural
f(a,b) b
1 2 3 4 5 …
a
1 0 1 3 6 10 …
2 2 4 7 11 …
3 5 8 12 …
4 9 13 …
5 14 … N
… …
N à 0
Q+ à 1/1
Mais um exemplo
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
102
� O racionais posiLvos Q+ é enumerável? ¡ Q+ = { a/b | a ∈ N+ ∧ b ∈ N+ } ¡ Considere a função
f : Q+ → N, bijetora, que mapeia a/b em um natural
f(a,b) b
1 2 3 4 5 …
a
1 0 1 3 6 10 …
2 2 4 7 11 …
3 5 8 12 …
4 9 13 …
5 14 … N
… …
N à 0 1
Q+ à 1/1 1/2
Mais um exemplo
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
103
� O racionais posiLvos Q+ é enumerável? ¡ Q+ = { a/b | a ∈ N+ ∧ b ∈ N+ } ¡ Considere a função
f : Q+ → N, bijetora, que mapeia a/b em um natural
f(a,b) b
1 2 3 4 5 …
a
1 0 1 3 6 10 …
2 2 4 7 11 …
3 5 8 12 …
4 9 13 …
5 14 … N
… …
N à 0 1 2
Q+ à 1/1 1/2 2/1
Mais um exemplo
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
104
� O racionais posiLvos Q+ é enumerável? ¡ Q+ = { a/b | a ∈ N+ ∧ b ∈ N+ } ¡ Considere a função
f : Q+ → N, bijetora, que mapeia a/b em um natural
f(a,b) b
1 2 3 4 5 …
a
1 0 1 3 6 10 …
2 2 4 7 11 …
3 5 8 12 …
4 9 13 …
5 14 … N
… …
N à 0 1 2 3
Q+ à 1/1 1/2 2/1 1/3
Mais um exemplo
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
105
� O racionais posiLvos Q+ é enumerável? ¡ Q+ = { a/b | a ∈ N+ ∧ b ∈ N+ } ¡ Considere a função
f : Q+ → N, bijetora, que mapeia a/b em um natural
f(a,b) b
1 2 3 4 5 …
a
1 0 1 3 6 10 …
2 2 4 7 11 …
3 5 8 12 …
4 9 13 …
5 14 … N
… …
N à 0 1 2 3 4
Q+ à 1/1 1/2 2/1 1/3 2/2
Mais um exemplo
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
106
� O racionais posiLvos Q+ é enumerável? ¡ Q+ = { a/b | a ∈ N+ ∧ b ∈ N+ } ¡ Considere a função
f : Q+ → N, bijetora, que mapeia a/b em um natural
f(a,b) b
1 2 3 4 5 …
a
1 0 1 3 6 10 …
2 2 4 7 11 …
3 5 8 12 …
4 9 13 …
5 14 … N
… …
N à 0 1 2 3 4 5
Q+ à 1/1 1/2 2/1 1/3 2/2 3/1
Mais um exemplo
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
107
� O racionais posiLvos Q+ é enumerável? ¡ Q+ = { a/b | a ∈ N+ ∧ b ∈ N+ } ¡ Considere a função
f : Q+ → N, bijetora, que mapeia a/b em um natural
f(a,b) b
1 2 3 4 5 …
a
1 0 1 3 6 10 …
2 2 4 7 11 …
3 5 8 12 …
4 9 13 …
5 14 … N
… …
N à 0 1 2 3 4 5 6 7 8 9 10 11 12 13 ...
Q+ à 1/1 1/2 2/1 1/3 2/2 3/1 1/4 2/3 3/2 4/1 1/5 2/4 3/3 4/2 ...
f (a b) =a+ b−1( ) a+ b− 2( )
2+ a−1( )
Teorema facilitador Propriedades
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
As seguintes afirmações são equivalentes
¡ A é contável ¡ Existe uma função injetora de A
para N ¡ A = ∅ ou existe uma função
sobrejetora de N para A
� Se A é contável, então X ⊆ A é contável
� Se A e B são contáveis, então A×B é contável
� Se A e B são contáveis, então A∪B é contável
*Demonstre estas propriedades como exercício.
108
Mais sobre conjuntos contáveis
E os números reais?
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
109
� O conjunto dos números reais é contável?
¡ Não, não é possível enumerar todos os números reais
� A prova, por contradição, foi proposta por Cantor em 1891 (Diagonal de Cantor)
h�p://en
.wikiped
ia.org/w
iki/G
eorg_C
antor
Diagonal de Cantor
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
110
1. Suponha que R é contável
2. Considere o conjunto R’ = { x ∈ R | 0 < x < 1 }
3. Note que R’ ⊆ R, portanto, se R é contável, então R’ é contável
4. Existe uma bijeção f : R’ → N que representa todos elementos de R’ como uma lista
N R’
0 r0 = 0 , d00 d01 d02 d03 …
1 r1 = 0 , d10 d11 d12 d13 …
2 r2 = 0 , d20 d21 d22 d23 …
3 r3 = 0 , d30 d31 d32 d33 …
… …
Diagonal de Cantor
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
111
4. Existe uma bijeção f : R’ → N que representa todos elementos de R’ como uma lista
N R’
0 r0 = 0 , d00 d01 d02 d03 …
1 r1 = 0 , d10 d11 d12 d13 …
2 r2 = 0 , d20 d21 d22 d23 …
3 r3 = 0 , d30 d31 d32 d33 …
… …
dij ∈ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
Por exemplo, se
r0 = 0 , 1 0 2 4 9 2…
então d00 = 1, d01 = 0, d02 = 2, d03 = 4, …
Diagonal de Cantor
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
112
5. Agora é preciso construir um número que não esteja listado abaixo
N R’
0 r0 = 0 , d00 d01 d02 d03 …
1 r1 = 0 , d10 d11 d12 d13 …
2 r2 = 0 , d20 d21 d22 d23 …
3 r3 = 0 , d30 d31 d32 d33 …
… …
Considere o número a = 0,a0a1a2a3... tal que
ai = 9 – dii
Diagonal de Cantor
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
113
5. Agora é preciso construir um número que não esteja listado abaixo
N R’
0 r0 = 0 , d00 d01 d02 d03 …
1 r1 = 0 , d10 d11 d12 d13 …
2 r2 = 0 , d20 d21 d22 d23 …
3 r3 = 0 , d30 d31 d32 d33 …
… …
a = 0 , a0 a1 a2 a3 …
Considere o número a = 0,a0a1a2a3... tal que
ai = 9 – dii
Diagonal de Cantor
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
114
5. Agora é preciso construir um número que não esteja listado abaixo
N R’
0 r0 = 0 , d00 d01 d02 d03 …
1 r1 = 0 , d10 d11 d12 d13 …
2 r2 = 0 , d20 d21 d22 d23 …
3 r3 = 0 , d30 d31 d32 d33 …
… …
≠ a = 0 , a0 a1 a2 a3 …
(d00 ≠ a0) → (a ≠ r0)
Considere o número a = 0,a0a1a2a3... tal que
ai = 9 – dii
Diagonal de Cantor
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
115
5. Agora é preciso construir um número que não esteja listado abaixo
N R’
0 r0 = 0 , d00 d01 d02 d03 …
1 r1 = 0 , d10 d11 d12 d13 …
2 r2 = 0 , d20 d21 d22 d23 …
3 r3 = 0 , d30 d31 d32 d33 …
… …
≠ ≠ a = 0 , a0 a1 a2 a3 …
(d11 ≠ a1) → (a ≠ r1)
Considere o número a = 0,a0a1a2a3... tal que
ai = 9 – dii
Diagonal de Cantor
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
116
5. Agora é preciso construir um número que não esteja listado abaixo
N R’
0 r0 = 0 , d00 d01 d02 d03 …
1 r1 = 0 , d10 d11 d12 d13 …
2 r2 = 0 , d20 d21 d22 d23 …
3 r3 = 0 , d30 d31 d32 d33 …
… …
≠ ≠ ≠ a = 0 , a0 a1 a2 a3 …
(d22 ≠ a2) → (a ≠ r2)
Considere o número a = 0,a0a1a2a3... tal que
ai = 9 – dii
Diagonal de Cantor
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
117
5. Agora é preciso construir um número que não esteja listado abaixo
N R’
0 r0 = 0 , d00 d01 d02 d03 …
1 r1 = 0 , d10 d11 d12 d13 …
2 r2 = 0 , d20 d21 d22 d23 …
3 r3 = 0 , d30 d31 d32 d33 …
… …
≠ ≠ ≠ ≠ a = 0 , a0 a1 a2 a3 …
(d33 ≠ a3) → (a ≠ r3)
Considere o número a = 0,a0a1a2a3... tal que
ai = 9 – dii
Diagonal de Cantor
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
118
5. Agora é preciso construir um número que não esteja listado abaixo
N R’
0 r0 = 0 , d00 d01 d02 d03 …
1 r1 = 0 , d10 d11 d12 d13 …
2 r2 = 0 , d20 d21 d22 d23 …
3 r3 = 0 , d30 d31 d32 d33 …
… …
≠ ≠ ≠ ≠ …
a = 0 , a0 a1 a2 a3 …
∀i ∈ N, (dii ≠ ai) → (a ≠ ri)
Considere o número a = 0,a0a1a2a3... tal que
ai = 9 – dii
Diagonal de Cantor
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
119
6. Assim, a ∈ R’ não está mapeado na bijeção f : R’ → N, uma contradição. Portanto, R’ não é contável. N R’
0 r0 = 0 , d00 d01 d02 d03 …
1 r1 = 0 , d10 d11 d12 d13 …
2 r2 = 0 , d20 d21 d22 d23 …
3 r3 = 0 , d30 d31 d32 d33 …
… …
≠ ≠ ≠ ≠ …
a = 0 , a0 a1 a2 a3 …
∀i ∈ N, (dii ≠ ai) → (a ≠ ri)
Logo, a ∈ R’, mas não está na lista com, supostamente, todos os
elementos de R’, uma contradição !?
Considere o número a = 0,a0a1a2a3... tal que
ai = 9 – dii
Diagonal de Cantor
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
120
7. Como, R’ ⊆ R não é contável, R também não é contável.
N R’
0 r0 = 0 , d00 d01 d02 d03 …
1 r1 = 0 , d10 d11 d12 d13 …
2 r2 = 0 , d20 d21 d22 d23 …
3 r3 = 0 , d30 d31 d32 d33 …
… …
≠ ≠ ≠ ≠ …
a = 0 , a0 a1 a2 a3 …
∀i ∈ N, (dii ≠ ai) → (a ≠ ri)
Logo, a ∈ R’, mas não está na lista com, supostamente, todos os
elementos de R’, uma contradição !?
Considere o número a = 0,a0a1a2a3... tal que
ai = 9 – dii
Outro exemplo
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
121
� Considere o conjunto F de todas as funções totais f : N → N
� F é finito? ¡ Infinito! ¡ Prove como exercício
� F é enumerável? ¡ Não! ¡ É incontável
Prova por contradição usando a diagonal de Cantor
Outro exemplo
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
122
1. Suponha que F é contável
2. Existe uma bijeção g : F → N que ordena os elementos de F como uma lista
g N
0 1 2 3 …
F
f0 f0(0) f0(1) f0(2) f0(3) …
f1 f1(0) f1(1) f1(2) f1(3) …
f2 f2(0) f2(1) f2(2) f2(3) …
f3 f3(0) f3(1) f3(2) f3(3) … …
…
…
…
…
Outro exemplo
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
123
3. É preciso encontrar uma função total h : N→N, tal que h ∈ F mas não está na lista abaixo
g N
0 1 2 3 …
F
f0 f0(0) f0(1) f0(2) f0(3) …
f1 f1(0) f1(1) f1(2) f1(3) …
f2 f2(0) f2(1) f2(2) f2(3) …
f3 f3(0) f3(1) f3(2) f3(3) … …
…
…
…
…
Outro exemplo
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
124
3. É preciso encontrar uma função total h : N→N, tal que h ∈ F mas não está na lista abaixo
g N
0 1 2 3 …
F
f0 f0(0) f0(1) f0(2) f0(3) …
f1 f1(0) f1(1) f1(2) f1(3) …
f2 f2(0) f2(1) f2(2) f2(3) …
f3 f3(0) f3(1) f3(2) f3(3) … …
…
…
…
…
h h(0) h(1) h(2) h(3) …
Considere h : N→N, tal que
h(i) = fi(i) + 1
Outro exemplo
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
125
3. É preciso encontrar uma função total h : N→N, tal que h ∈ F mas não está na lista abaixo
g N
0 1 2 3 …
F
f0 f0(0) f0(1) f0(2) f0(3) …
f1 f1(0) f1(1) f1(2) f1(3) …
f2 f2(0) f2(1) f2(2) f2(3) …
f3 f3(0) f3(1) f3(2) f3(3) … …
…
…
…
…
≠ h h(0) h(1) h(2) h(3) …
( h(0) ≠ f0(0) ) → ( h ≠ f0 )
Considere h : N→N, tal que
h(i) = fi(i) + 1
Outro exemplo
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
126
3. É preciso encontrar uma função total h : N→N, tal que h ∈ F mas não está na lista abaixo
g N
0 1 2 3 …
F
f0 f0(0) f0(1) f0(2) f0(3) …
f1 f1(0) f1(1) f1(2) f1(3) …
f2 f2(0) f2(1) f2(2) f2(3) …
f3 f3(0) f3(1) f3(2) f3(3) … …
…
…
…
…
≠ ≠ h h(0) h(1) h(2) h(3) …
( h(1) ≠ f1(1) ) → ( h ≠ f1 )
Considere h : N→N, tal que
h(i) = fi(i) + 1
Outro exemplo
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
127
3. É preciso encontrar uma função total h : N→N, tal que h ∈ F mas não está na lista abaixo
g N
0 1 2 3 …
F
f0 f0(0) f0(1) f0(2) f0(3) …
f1 f1(0) f1(1) f1(2) f1(3) …
f2 f2(0) f2(1) f2(2) f2(3) …
f3 f3(0) f3(1) f3(2) f3(3) … …
…
…
…
…
≠ ≠ ≠ h h(0) h(1) h(2) h(3) …
( h(2) ≠ f2(2) ) → ( h ≠ f2 )
Considere h : N→N, tal que
h(i) = fi(i) + 1
Outro exemplo
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
128
3. É preciso encontrar uma função total h : N→N, tal que h ∈ F mas não está na lista abaixo
g N
0 1 2 3 …
F
f0 f0(0) f0(1) f0(2) f0(3) …
f1 f1(0) f1(1) f1(2) f1(3) …
f2 f2(0) f2(1) f2(2) f2(3) …
f3 f3(0) f3(1) f3(2) f3(3) … …
…
…
…
…
≠ ≠ ≠ ≠ h h(0) h(1) h(2) h(3) …
( h(3) ≠ f3(3) ) → ( h ≠ f3 )
Considere h : N→N, tal que
h(i) = fi(i) + 1
Outro exemplo
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
129
3. É preciso encontrar uma função total h : N→N, tal que h ∈ F mas não está na lista abaixo
g N
0 1 2 3 …
F
f0 f0(0) f0(1) f0(2) f0(3) …
f1 f1(0) f1(1) f1(2) f1(3) …
f2 f2(0) f2(1) f2(2) f2(3) …
f3 f3(0) f3(1) f3(2) f3(3) … …
…
…
…
…
≠ ≠ ≠ ≠ …
h h(0) h(1) h(2) h(3) …
∀i ∈ N, ( h ≠ fi )
Considere h : N→N, tal que
h(i) = fi(i) + 1
Outro exemplo
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
130
4. Logo, h ∈ F, mas não está mapeada por g : F → N, uma contradição. Portanto, F não é contável.
g N
0 1 2 3 …
F
f0 f0(0) f0(1) f0(2) f0(3) …
f1 f1(0) f1(1) f1(2) f1(3) …
f2 f2(0) f2(1) f2(2) f2(3) …
f3 f3(0) f3(1) f3(2) f3(3) … …
…
…
…
…
≠ ≠ ≠ ≠ …
h h(0) h(1) h(2) h(3) …
Considere h : N→N, tal que
h(i) = fi(i) + 1
∀i ∈ N, ( h ≠ fi )
Logo, h ∈ F, mas não está na lista com, supostamente, todos os
elementos de F, uma contradição !?
Exercício de fixação
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
131
� Mostre que os conjuntos abaixo são enumeráveis (encontre uma bijeção sobre os naturais) 1. Z+ = {1, 2, 3, 4, …} 2. N \ {1, 2, 3} 3. Naturais Pares 4. Naturais Ímpares 5. Inteiros Pares
� Mostre que os conjuntos abaixo não são enumeráveis 1. P (N) 2. O conjunto B de todas as sequências infinitas de 0’s ou 1’s
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
Fundamentos de Teoria da Computação Eduardo Freire Nakamura ([email protected])
132
Recursividade e Indução MatemáLca
Definição
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
133
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 parLr de outros elementos de A
c) Fechamento: só pertencem a A, os elementos obLdos através dos passos (a) ou (b).
Definição
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
134
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 parLr de outros elementos de A
c) Fechamento: só pertencem a A, os elementos obLdos através dos passos (a) ou (b).
Definição
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
É possível definir recursivamente qualquer conjunto enumerável!
135
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 parLr de outros elementos de A
c) Fechamento: só pertencem a A, os elementos obLdos através dos passos (a) ou (b).
Definição Exemplo 01: Números naturais
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
136
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 parLr de outros elementos de A
c) Fechamento: só pertencem a A, os elementos obLdos através dos passos (a) ou (b).
Definição Exemplo 01: Números naturais
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
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).
137
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 parLr de outros elementos de A
c) Fechamento: só pertencem a A, os elementos obLdos através dos passos (a) ou (b).
Definição Exemplo 02: Fatorial
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
Definição – fat : N → N
a) fat(0) = 1
b) ∀n ∈ N, fat(n+1) = n * fat(n−1)
c) implícito
138
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 parLr de outros elementos de A
c) Fechamento: só pertencem a A, os elementos obLdos através dos passos (a) ou (b).
Definição Exemplo 03: Exponencial an
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
Definição – an : N → N
a) a0 = 1
b) ∀n ∈ N, an+1 = a × an
c) implícito
139
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 parLr de outros elementos de A
c) Fechamento: só pertencem a A, os elementos obLdos através dos passos (a) ou (b).
Definição Exemplo 04: Ling. Proposicional
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
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:
¡ ¬P ¡ P∧Q ¡ P∨Q ¡ P→Q ¡ P↔Q
c) implícito
140
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 parLr de outros elementos de A
c) Fechamento: só pertencem a A, os elementos obLdos através dos passos (a) ou (b).
Indução matemáLca
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
141
h�p://meangreenmath.files.wordpress.com/2013/08/dominoes.jpg
Nono axioma de Giuseppe Peano
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
� Se K é um conjunto tal que 1. 0 (zero) está pertence a K 2. Para todo natural k
÷ Se k está conLdo em K,
÷ Então o sucessor de k está em K
� Então K contém todos os números naturais
142
Princípio da indução
h�p://en
.wikiped
ia.org/w
iki/G
iusepp
e_Pe
ano
Reformulando...
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
� 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
143
Princípio da indução
h�p://en
.wikiped
ia.org/w
iki/G
iusepp
e_Pe
ano
Reformulando...
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
� 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
144
Princípio da indução
É possível provar propriedades para conjuntos enumeráveis usando
indução matemáLca!
Definição Estrutura de demonstração
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
Princípio da indução faca 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 induLvo
145
Princípio da indução fraca
*Primeiro elemento do conjunto, não necessariamente 0 (zero)
Exemplo 01
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
146
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 ¡ 1 = 12 (divisível por 3)
2. Passo induLvo ¡ Hipótese:
S(n) = 1+3+5+…+(2n – 1) = n2
¡ 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 ([email protected]) Fundamentos de Teoria da Computação
147
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 ¡ 1 = 12 (divisível por 3)
2. Passo induLvo ¡ Hipótese:
S(n) = 1+3+5+…+(2n – 1) = n2
¡ 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 ([email protected]) Fundamentos de Teoria da Computação
148
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 ¡ 1 = 12 (divisível por 3)
2. Passo induLvo ¡ Hipótese:
S(n) = 1+3+5+…+(2n – 1) = n2
¡ 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 ([email protected]) Fundamentos de Teoria da Computação
149
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 ¡ 1 = 12 (divisível por 3)
2. Passo induLvo ¡ Hipótese:
S(n) = 1+3+5+…+(2n – 1) = n2
¡ 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 ([email protected]) Fundamentos de Teoria da Computação
150
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 ¡ 1 = 12 (divisível por 3)
2. Passo induLvo ¡ Hipótese:
S(n) = 1+3+5+…+(2n – 1) = n2
¡ 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 ([email protected]) Fundamentos de Teoria da Computação
Logo, para todo n ∈ Z+, temos que 1 + 3 + 5 +…+ (2n–1) = n2.
151
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 ¡ 1 = 12 (divisível por 3)
2. Passo induLvo ¡ Hipótese:
S(n) = 1+3+5+…+(2n – 1) = n2
¡ 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 ([email protected]) Fundamentos de Teoria da Computação
Logo, para todo n ∈ Z+, o número 22n – 1 é divisível por 3
152
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 ¡ 22(1) – 1 = 4 – 1 = 3 (divisível por 3)
2. Passo induLvo
¡ Hipótese: 22n – 1 = 3m, para m,n ∈ Z+ ¡ 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 ([email protected]) Fundamentos de Teoria da Computação
Logo, para todo n ∈ Z+, o número 22n – 1 é divisível por 3
153
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 ¡ 22(1) – 1 = 4 – 1 = 3 (divisível por 3)
2. Passo induLvo
¡ Hipótese: 22n – 1 = 3m, para m,n ∈ Z+ ¡ 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 ([email protected]) Fundamentos de Teoria da Computação
Logo, para todo n ∈ Z+, o número 22n – 1 é divisível por 3
154
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 ¡ 22(1) – 1 = 4 – 1 = 3 (divisível por 3)
2. Passo induLvo
¡ Hipótese: 22n – 1 = 3m, para m,n ∈ Z+ ¡ 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 ([email protected]) Fundamentos de Teoria da Computação
Logo, para todo n ∈ Z+, o número 22n – 1 é divisível por 3
155
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 ¡ 22(1) – 1 = 4 – 1 = 3 (divisível por 3)
2. Passo induLvo
¡ Hipótese: 22n – 1 = 3m, para m,n ∈ Z+ ¡ 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 ([email protected]) Fundamentos de Teoria da Computação
Logo, para todo n ∈ Z+, o número 22n – 1 é divisível por 3
156
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 ¡ 22(1) – 1 = 4 – 1 = 3 (divisível por 3)
2. Passo induLvo
¡ Hipótese: 22n – 1 = 3m, para m,n ∈ Z+ ¡ Tese: 22(n+1) – 1 = 3k
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 ([email protected]) Fundamentos de Teoria da Computação
Logo, para todo n ∈ Z+, o número 22n – 1 é divisível por 3
157
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 ¡ 22(1) – 1 = 4 – 1 = 3 (divisível por 3)
2. Passo induLvo
¡ Hipótese: 22n – 1 = 3m, para m,n ∈ Z+ ¡ Tese: 22(n+1) – 1 = 3k
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 ([email protected]) Fundamentos de Teoria da Computação
Logo, para todo n ∈ Z+, o número 22n – 1 é divisível por 3
158
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 ¡ 22(1) – 1 = 4 – 1 = 3 (divisível por 3)
2. Passo induLvo
¡ Hipótese: 22n – 1 = 3m, para m,n ∈ Z+ ¡ Tese: 22(n+1) – 1 = 3k
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 ([email protected]) Fundamentos de Teoria da Computação
Logo, para todo n ∈ Z+, o número 22n – 1 é divisível por 3
159
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 ¡ 22(1) – 1 = 4 – 1 = 3 (divisível por 3)
2. Passo induLvo
¡ Hipótese: 22n – 1 = 3m, para m,n ∈ Z+ ¡ Tese: 22(n+1) – 1 = 3k
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 ([email protected]) Fundamentos de Teoria da Computação
Logo, para todo n ∈ Z+, o número 22n – 1 é divisível por 3.
160
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 ¡ 22(1) – 1 = 4 – 1 = 3 (divisível por 3)
2. Passo induLvo
¡ Hipótese: 22n – 1 = 3m, para m,n ∈ Z+ ¡ Tese: 22(n+1) – 1 = 3k
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 ([email protected]) Fundamentos de Teoria da Computação
Princípio da indução faca 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)
161
Princípio da indução forte
*Primeiro elemento do conjunto, não necessariamente 0 (zero)
Exemplo 01
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
Caso 1: (k+1) é primo
Neste caso (k+1) = (k+1)(1), produto de dois primos.
162
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 ¡ 2 = 2(1) (produto de dois primos)
2. Passo induLvo
¡ Hipótese: todo 2 ≤ r ≤ k , pode ser escrito como o produto de primos
¡ Tese: (k + 1) pode ser escrito como o produto de primos
Exemplo 01
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
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!
163
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 ¡ 2 = 2(1) (produto de dois primos)
2. Passo induLvo
¡ Hipótese: todo 2 ≤ r ≤ k , pode ser escrito como o produto de primos
¡ Tese: (k + 1) pode ser escrito como o produto de primos
Exemplo 02
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
Por hipótese, temos que ¡ (k – 3) pode ser escrito como a
soma de 4’s e 5’s ¡ 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 e 5’s.
164
Princípio da indução forte
Prove que todo n ≥ 12 ∈ Z+ pode ser obLdo somando-‐se 4’s e 5’s.
1. Caso base n = 12, 13, 14, 15 ¡ 12 = 4 + 4 + 4 13 = 4 + 4 + 5 ¡ 14 = 4 + 5 + 5 15 = 5 + 5 + 5
2. Passo induLvo ¡ Hipótese: todo 12 ≤ r ≤ k é a soma de
4’s e 5’s, onde k ≥ 15 ¡ Tese: (k + 1) é a soma de 4’s e 5’s
Exercícios de fixação
Eduardo Freire Nakamura ([email protected]) Fundamentos de Teoria da Computação
165
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 obLdo somando-‐se 3’s e 5’s.
4. A função de Fibonacci é dada por .
Prove que .
2ii=0
n
∑ = 2n+1 −1
F(n) =0, !se!n = 01, !se!n =1
F(n−1)+F(n− 2), !se!n ≥ 2
#
$%
&%
F(n) = 151+ 52
!
"#
$
%&
n
−1− 52
!
"#
$
%&
n(
)
**
+
,
--