Indução em Aspectos Teóricos da Computação

Prévia do material em texto

Aspectos Teóricos da Computação I
06 - Indução
Leonardo Jose Silvestre1
1Departamento de Computação e Eletrônica (DCEL)
Centro Universitário do Norte do Espírito Santo (CEUNES)
Universidade Federal do Espírito Santo(UFES)
Aspectos Teóricos da Computação I, 2014/2
DCEL (UFES) 06 - Indução ATCI 1 / 66
Outline
1 Cardinalidade de Conjuntos
2 Indução
Prova Indutiva
Segundo Princípio da Indução Matemática
Definição Indutiva
Expressões Regulares
Computações de um Autômato Finito
DCEL (UFES) 06 - Indução ATCI 2 / 66
Cardinalidade de Conjuntos
Sumário
1 Cardinalidade de Conjuntos
2 Indução
Prova Indutiva
Segundo Princípio da Indução Matemática
Definição Indutiva
Expressões Regulares
Computações de um Autômato Finito
DCEL (UFES) 06 - Indução ATCI 3 / 66
Cardinalidade de Conjuntos
Introdução
Cardinalidade de um conjunto: medida de seu tamanho
Até o momento
Tratada de forma informal ou semi-formal
Exemplo de expressão usada com frequência:
número de elementos de um conjunto
DCEL (UFES) 06 - Indução ATCI 4 / 66
Cardinalidade de Conjuntos
Introdução
Um conjunto pode possuir um número finito ou infinito de
elementos
Finito:
Pode ser denotado por extensão (listando exaustivamente todos
os seus elementos)
Infinito:
Caso contrário
DCEL (UFES) 06 - Indução ATCI 5 / 66
Cardinalidade de Conjuntos
Introdução
Estudo formal: resposta a perguntas como
Como definir formalmente a cardinalidade de um conjunto?
Quando dois conjuntos possuem o mesmo cardinal?
O que é um cardinal infinito?
Existe mais de um, ou seja, diferentes cardinais infinitos?
Nesse caso, existe uma ordem de cardinais infinitos?
Estudo mais completo ou aprofundado
Foge um pouco do escopo da disciplina
Ênfase nos conceitos, resultados e interpretações usados em CC
DCEL (UFES) 06 - Indução ATCI 6 / 66
Cardinalidade de Conjuntos
Introdução
Cardinalidade é definida usando funções bijetoras (uso da bijeção é
intuitivo)
Comum em diferentes civilizações
Cardinalidade de conjuntos: bijeção entre
Conjunto de objetos em questão (rebanho de ovelhas. . . )
Subconjunto de dedos das mãos
Quando os dedos não eram suficientes: conjunto de pedras, nós
em cordas. . .
Uma bijeção qualquer: basta existir uma bijeção
Qualquer dedo (pedra ou nó) corresponde a qualquer animal
Se sobra um dedo (pedra ou nó), então falta um animal
DCEL (UFES) 06 - Indução ATCI 7 / 66
Cardinalidade de Conjuntos
Cardinalidade Finita e Infinita
Cardinalidade Finita, Cardinalidade Infinita - Definição
Cardinalidade de um conjunto A
#A
Finita: existe bijeção entre A e {1,2,3, . . . ,n}
#A = n
Infinita: existe bijeção entre A e um subconjunto próprio de A
DCEL (UFES) 06 - Indução ATCI 8 / 66
Cardinalidade de Conjuntos
Cardinalidade Finita e Infinita
Portanto, um conjunto
Finito (cardinalidade finita): possível representar por extensão
Infinito: possível retirar elementos e ainda assim estabelecer uma
bijeção com o próprio
DCEL (UFES) 06 - Indução ATCI 9 / 66
Cardinalidade de Conjuntos
Exemplo: Cardinalidade Infinita do Conjunto dos Números Inteiros
f : Z→ N tal que
se a ≥ 0, então f (a) = 2a (não negativos associados aos pares)
se a < 0, então f (a) = |2a| − 1 (negativos assoc. aos ímpares)
É bijetora e N ⊂ Z
⇒ Logo, Z é infinito
DCEL (UFES) 06 - Indução ATCI 10 / 66
Cardinalidade de Conjuntos
Conjunto Contável e Não-contável
Nem todos conjuntos infinitos possuem mesma cardinalidade
Contradiz a noção intuitiva
DCEL (UFES) 06 - Indução ATCI 11 / 66
Cardinalidade de Conjuntos
Conjunto Contável, Conjunto Não-Contável, Conjunto Enumerável
- Definições
A conjunto infinito
Finitamente Contável: finito
Infinitamente Contável ou Enumerável:
Existe uma bijeção entre A e um subconjunto infinito de N
Esta bijeção é denominada enumeração de A
Não-Contável: caso contrário
Obs.: Infinitamente contável: possível enumerar seus elementos como
uma sequência infinita
〈a1,a2,a3, . . .〉
DCEL (UFES) 06 - Indução ATCI 12 / 66
Cardinalidade de Conjuntos
Conjunto Contável, Conjunto Não-Contável, Conjunto Enumerável
Termo “conjunto contável”
usualmente significa finitamente ou infinitamente contável
Conjunto Infinitamente Contável - Exemplos
Z
Q
Prova de que um conjunto é não-contável
Pode ser realizada usando o método da Diagonalização de
Cantor (Georg Cantor - 1845-1918)
Frequente em provas na Computação e Informática
DCEL (UFES) 06 - Indução ATCI 13 / 66
Cardinalidade de Conjuntos
Teorema: Conjunto Não-Contável
O seguinte conjunto é não-contável:
S = {x ∈ R | 0 < x < 1}
Prova:
(por absurdo - Diagonalização de Cantor)
Suponha S contável
Existe uma enumeração de S
〈s1, s2, s3, . . .〉
Qualquer número s ∈ S: sequência contável de decimais
s = 0,d1d2d3 . . . dn . . .
Exemplo: pi/10 = 0,31415 . . .
DCEL (UFES) 06 - Indução ATCI 14 / 66
Cardinalidade de Conjuntos
Teorema: Conjunto Não-Contável
Prova (cont.):
Portanto, a enumeração 〈s1, s2, s3, . . .〉 pode ser representada por
s1 = 0,d11d12d13 . . . d1n . . .
s2 = 0,d21d22d23 . . . d2n . . .
s3 = 0,d31d32d33 . . . d3n . . .
. . .
sn = 0,dn1dn2dn3 . . .dnn . . .
. . .
Seja r o número real construído a partir da diagonal
r = 0,e1e2e3 . . . en . . . i ∈ {1,2,3, . . .}
ei = 1, caso dii 6= 1; ei = 2, caso dii = 1
DCEL (UFES) 06 - Indução ATCI 15 / 66
Cardinalidade de Conjuntos
Teorema: Conjunto Não-Contável
Prova (cont.):
Claramente, r ∈ S
r é diferente de qualquer número da enumeração 〈s1, s2, s3, . . .〉
Difere pelo menos no dígito destacado na diagonal (escolhemos
para que assim fosse)
Portanto, r /∈ S: contradição (afinal, fizemos a suposição de que a
enumeração continha todos os números de S!)
Logo, é uma absurdo supor que S é contável
Portanto, S é não-contável
DCEL (UFES) 06 - Indução ATCI 16 / 66
Cardinalidade de Conjuntos
Conjuntos Não-Contáveis
Prova de que R é não-contável é simples
Mas antes, vejamos a seguinte definição
Definição:Conjuntos Equipotentes
A e B conjuntos Equipotentes:
existe uma função bijetora entre A e B
Logo, conjuntos equipotentes: mesma cardinalidade
Todos conjuntos enumeráveis são equipotentes
Todo conjunto indexado é equipotente ao seu conjunto de índices
DCEL (UFES) 06 - Indução ATCI 17 / 66
Cardinalidade de Conjuntos
Teorema: R é um Conjunto Não-Contável
O conjuntos dos números reais R é não-contável.
Prova (direta):
Basta provar que R é equipotente a S = {x ∈ R | 0 < x < 1}
Seja f : S → R
Se 0 < s ≤ 1/2, então f (s) = (1/2s)− 1
Se 1/2 ≤ s < 1, então f (s) = (1/(2s − 2)) + 1,
que é uma bijeção (verificação: exercício)
DCEL (UFES) 06 - Indução ATCI 18 / 66
Cardinalidade de Conjuntos
Conjunto Não-Contável - Exemplos
I (conjuntos dos números irracionais)
C (conjunto dos números complexos)
R2
DCEL (UFES) 06 - Indução ATCI 19 / 66
Cardinalidade de Conjuntos
Cardinalidade dos Conjuntos Não-Contáveis
Conjuntos não-contáveis: mesma cardinalidade?
Nem todos os conjuntos não-contáveis tem a mesma
cardinalidade
A tem pelo menos tantos elementos quanto B
#A ≤ #B
quando existe função injetora f : A→ B
DCEL (UFES) 06 - Indução ATCI 20 / 66
Cardinalidade de Conjuntos
Existem infinitos cardinais não-contáveis
Conjunto das partes de um conjunto tem sempre cardinalidade maior
que este
Fato conhecido como Teorema de Cantor
DCEL (UFES) 06 - Indução ATCI 21 / 66
Indução
Sumário
1 Cardinalidade de Conjuntos
2 Indução
Prova Indutiva
Segundo Princípio da Indução Matemática
Definição Indutiva
Expressões Regulares
Computações de um Autômato Finito
DCEL (UFES) 06 - Indução ATCI 22 / 66
Indução
Princípio da Indução Matemática
Técnica para lidar com tipos de dados que têm uma relação de
boa-ordem
Relaçãode Boa-Ordem
Todo conjunto não-vazio de elementos do tipo de dado tem um
elemento mínimo segundo esta relação de ordem
Exemplo: N
DCEL (UFES) 06 - Indução ATCI 23 / 66
Indução
Princípio da Indução Matemática
Dada uma boa ordem
Pode-se aplicar indução para provar propriedades que valem para
todo elemento
Por simplicidade
Tipo de dados considerado: N
Ou qualquer outro conjunto isomorfo a N
Exemplo simples que ilustra o Princípio da Indução Matemática: efeito
dominó
DCEL (UFES) 06 - Indução ATCI 24 / 66
Indução
Efeito Dominó
Ao derrubar a primeira peça, todas as demais peças serão
derrubadas em cadeia
DCEL (UFES) 06 - Indução ATCI 25 / 66
Indução
Efeito Dominó
Para estar certo que ocorrerá
1 Primeira peça é derrubada (direção das demais)
2 Se qualquer peça está suficientemente próxima da seguinte,
então, ao ser derrubada, fará com que a seguinte também seja
derrubada
Então
Por (1), a primeira peça é derrubada
Por (2), a segunda peça é derrubada
Por (2), a terceira peça é derrubada
e assim sucessivamente . . .
Portanto, para i tão grande quanto se queira
i-ésima peça é derrubada
Logo, para qualquer n
n-ésima peça é derrubada
DCEL (UFES) 06 - Indução ATCI 26 / 66
Indução
Princípio da Indução Matemática - Definição
p(n) uma proposição sobre M = {n ∈ N | n ≥ m e m ∈ N}
Princípio da Indução Matemática
p(m) é verdadeira
Para qualquer k ∈ M, p(k)⇒ p(k + 1)
Então, para qualquer n ∈ N, p(n) é verdadeira
Base de indução
p(m)
Hipótese de indução
p(k)
Passo de indução
p(k)⇒ p(k + 1)
DCEL (UFES) 06 - Indução ATCI 27 / 66
Indução
Princípio da Indução Matemática
Na definição
Forma mais tradicional
Denominada de Primeiro Princípio da Indução Matemática
Formulações alternativas: adiante
Duas aplicações da Indução Matemática destacam-se
Prova Indutiva ou Prova por Indução
Técnica de demonstração comum na Computação
Não é do domínio da lógica pura
Definição Indutiva ou Definição Recursiva
Comum na Computação
Já usada anteriormente de forma informal
DCEL (UFES) 06 - Indução ATCI 28 / 66
Indução
Princípio da Indução Matemática
Recursão:
conceito próximo ao de indução e presente na grande maioria das
linguagens de programação
Exemplos de construções baseadas em indução e recursão e de
especial interesse para Computação:
Computações de um autômato finito
Gramáticas de Chomsky e a Forma de Backus Naur (ou BNF)
Expressões Regulares
Funções Recursivas Parciais ou Funções Recursivas de Kleene
DCEL (UFES) 06 - Indução ATCI 29 / 66
Indução Prova Indutiva
Sumário
1 Cardinalidade de Conjuntos
2 Indução
Prova Indutiva
Segundo Princípio da Indução Matemática
Definição Indutiva
Expressões Regulares
Computações de um Autômato Finito
DCEL (UFES) 06 - Indução ATCI 30 / 66
Indução Prova Indutiva
Prova Indutiva ou Prova por Indução
Técnica de demonstração
Baseada no Princípio da Indução Matemática
Não é do domínio da lógica pura
Limita-se a confirmar se p(n) é correta
Demonstração por indução
Demonstrar a base de indução p(m)
Fixado um k
Supor verdadeira a hipótese de indução p(k)
Demonstrar o passo de indução p(k)⇒ p(k + 1)
DCEL (UFES) 06 - Indução ATCI 31 / 66
Indução Prova Indutiva
Prova Indutiva ou Prova por Indução
MUITO IMPORTANTE!
Demonstração por indução
Demonstrar a base de indução p(m)
Fixado um k
Supor verdadeira a hipótese de indução p(k)
Demonstrar o passo de indução p(k)⇒ p(k + 1)
DCEL (UFES) 06 - Indução ATCI 32 / 66
Indução Prova Indutiva
Exemplo - Prova por Indução - p(n) : n < 2n
para qualquer n ∈ N, tem-se que n < 2n
Base de Indução. k = 0
0 < 1 = 20
Hipótese de Indução. Suponha que, para k ∈ N
p(k) : k < 2k é verdadeira
Passo de Indução. Prova para p(k + 1) : k + 1 < 2k+1
k + 1 < (hipótese de indução)
2k + 1 ≤ 2k + 2k = 2 ∗ 2k = 2k+1
Logo, para qualquer n ∈ N, tem-se que n < 2n
DCEL (UFES) 06 - Indução ATCI 33 / 66
Indução Prova Indutiva
Prova por Indução - p(n) : 2n < n!
Para qualquer n ∈ N, se n > 3, então 2n < n!
Base de Indução. k = 4
42 = 16 < 24 = 4!
Hipótese de Indução. Suponha para k > 3
p(k) : 2k < k ! é verdadeira
Passo de Indução. Prova para p(k + 1) : 2k+1 < (k + 1)!
2k+1 = 2 ∗ 2k < (hipótese de indução)
2 ∗ k ! < (k + 1) ∗ k ! = (k + 1)!
Logo, para qualquer n ∈ N, se n > 3, então 2n < n!
DCEL (UFES) 06 - Indução ATCI 34 / 66
Indução Prova Indutiva
Prova por Indução - 1 + 2 + . . .+ n = (n2 + n)/2
Para qualquer n ∈ N, tem-se que 1 + 2 + . . .+ n = (n2 + n)/2
Base de Indução. k = 0
(02 + 0)/2 = (0 + 0)/2 = 0/2 = 0
Hipótese de Indução. Suponha para k ∈ N
p(k) : 1 + 2 + . . .+ k = (k2 + k)/2 é verdadeira
DCEL (UFES) 06 - Indução ATCI 35 / 66
Indução Prova Indutiva
Prova por Indução - 1 + 2 + . . .+ n = (n2 + n)/2
Passo de Indução.
p(k + 1) : 1 + 2 + . . .+ k + (k + 1) = ((k + 1)2 + k + 1)/2
1 + 2 + . . .+ k + (k + 1) =
(1 + 2 + . . .+ k) + (k + 1) = pela hipótese de indução
(k2 + k)/2 + (k + 1) =
(k2 + k)/2 + (2k + 2)/2 =
(k2 + k + 2k + 2)/2 =
((k2 + 2k + 1) + (k + 1))/2 =
((k + 1)2 + (k + 1))/2
DCEL (UFES) 06 - Indução ATCI 36 / 66
Indução Prova Indutiva
Prova por Indução - #2A = 2#A
Foi afirmado que
Se o cardinal de um conjunto A é n, então o cardinal de 2A é 2n, o
que justifica a notação 2A.
Teorema (versão limitada a conjuntos finitos)
Para qualquer conjunto finito A, se #A = n, então tem-se que
#2A = 2n
Considere o seguinte exemplo motivacional:
P(∅) = {∅}
P({a}) = {∅, {a}}
P({a,b}) = {∅, {a}, {b}, {a,b}}
P({a,b, c}) = {∅, {a}, {b}, {c}, {a,b}, {a, c}, {b, c}, {a,b, c}}
DCEL (UFES) 06 - Indução ATCI 37 / 66
Indução Prova Indutiva
Prova por Indução - #2A = 2#A
Observe P({a,b}) e P({a,b, c}) (por exemplo)
Metade dos elementos de P({a,b, c}) corresponde a P({a,b})
P({a,b, c}) = P({a,b}) ∪ {{c}, {a, c}, {b, c}, {a,b, c}}
Outra metade de P({a,b, c}) corresponde a P({a,b}),
adicionando-se c a cada conjunto
P({a,b, c}) =P({a,b})∪
{∅ ∪ {c}, {a} ∪ {c}, {b} ∪ {c}, {a,b} ∪ {c}}
Ou seja, #P({a,b, c}) possui o dobro de elementos de
#P({a,b})
Cada elemento adicionado a um conjunto duplica o cardinal
do correspondente conjunto das partes
DCEL (UFES) 06 - Indução ATCI 38 / 66
Indução Prova Indutiva
Prova por Indução - #2A = 2#A
Base de Indução. Seja k = 0(#A = 0). Então A = ∅
P(∅) = {∅}
p(0) é verdadeira pois
#P(∅) = 1 = 20 = 2#∅
Hipótese de Indução. Suponha que, para algum k ∈ N(#A = k)
p(k) : #P(A) = 2#A é verdadeira
DCEL (UFES) 06 - Indução ATCI 39 / 66
Indução Prova Indutiva
Prova por Indução - #2A = 2#A
Passo de Indução. p(k + 1)
Sem perda de generalidade, suponha os seguintes conjuntos
(conjuntos com o mesmo cardinal são isomorfos)
A = {1,2,3, . . . , k}
B = {1,2,3, . . . , k , k + 1}
Por hipótese de indução #P(A) = 2k
P(A) são todos subconjuntos de B que não possuem o elemento k + 1
Demais subconjuntos B são aqueles que contém o elemento k + 1
A união de cada conjunto de P(A) com {k + 1}, resultando em
outros 2k conjuntos
#P(B) = 2k + 2k = 2k+1
Logo, para qualquer conjunto finito A, se #A = n, então tem-se que
#2A = 2n
DCEL (UFES) 06 - Indução ATCI 40 / 66
Indução Segundo Princípio da Indução Matemática
Sumário
1 Cardinalidade de Conjuntos
2 Indução
Prova Indutiva
Segundo Princípio da Indução Matemática
Definição Indutiva
Expressões Regulares
Computações de um Autômato Finito
DCEL (UFES) 06 - Indução ATCI 41 / 66
Indução Segundo Princípio da Indução Matemática
Segundo Princípio da Indução Matemática
Frequentemente é conveniente trabalhar com outras formulações do
Princípio da Indução Matemática
Primeiro Princípio da Indução Matemática: visto até agora
Segundo Princípio da Indução Matemática
Formulação especialmente importante
Considera não apenas o resultadoanterior p(k) mas todos os
anteriores para concluir p(k + 1)
DCEL (UFES) 06 - Indução ATCI 42 / 66
Indução Segundo Princípio da Indução Matemática
Relembrando
(Primeiro) Princípio da Indução Matemática - Definição
p(n) uma proposição sobre M = {n ∈ N | n ≥ m e m ∈ N}
Princípio da Indução Matemática
p(m) é verdadeira
Para qualquer k ∈ M, p(k)⇒ p(k + 1)
Então, para qualquer n ∈ N, p(n) é verdadeira
DCEL (UFES) 06 - Indução ATCI 43 / 66
Indução Segundo Princípio da Indução Matemática
Segundo Princípio da Indução Matemática - Definição
Seja p(n) proposição sobre M = {n ∈ N | n ≥ m e m ∈ N}
Primeira Versão
p(m) é verdadeira
Para qualquer k ∈ M, p(m) ∧ p(m + 1) ∧ . . . ∧ p(k)⇒ p(k + 1)
Então, para qualquer n ∈ N, p(n) é verdadeira
Segunda Versão. Suponha t ∈ N
p(m),p(m + 1), . . . ,p(m + t) são verdadeiras
Para qualquer k ∈ M tal que
k ≥ m + t : p(m) ∧ p(m + 1) ∧ . . . ∧ p(k)⇒ p(k + 1)
Então, para qualquer n ∈ N, p(n) é verdadeira
Segunda versão: prova os t primeiros casos em separado para
verificar a base de indução
DCEL (UFES) 06 - Indução ATCI 44 / 66
Indução Segundo Princípio da Indução Matemática
Segundo Princípio da Indução Matemática
Aplicação usual: definição e prova de propriedades de
Expressões
Fórmulas
Árvores etc.
Razão pela qual frequentemente é denominado de:
Indução em estrutura
Indução estruturada
Obs.: Interessante quando k + 1 depende de resultados anteriores a k
DCEL (UFES) 06 - Indução ATCI 45 / 66
Indução Segundo Princípio da Indução Matemática
Segundo Princípio: Proposição Lógica - Exemplo
Suponha que p é uma proposição lógica a qual contém
exclusivamente os conectivos lógicos ∧,∨ e→. Se o valor verdade de
todos os átomos de p é V , então o valor verdade de p é V
Uma prova por indução (no número de átomos, primeira versão):
Base de Indução. Seja k = 1
p é um átomo
Portanto, por hipótese, p é V
Hipótese de Indução. Suponha que, para algum k ∈ N, e para
qualquer u ∈ N tal que u ≤ k
se o número de átomos de p é u, então o valor verdade de p é V
DCEL (UFES) 06 - Indução ATCI 46 / 66
Indução Segundo Princípio da Indução Matemática
Segundo Princípio: Proposição Lógica - Exemplo
Passo de Indução. Seja p uma proposição com k + 1 átomos
p pode ser reescrita em um dos seguintes casos (q e r possuem
individualmente no máximo k átomos e, conjuntamente, k + 1
átomos):
q ∧ r
q ∨ r
q → r
Por hipótese de indução q e r são V . Portanto, em qualquer dos
casos, p é V
DCEL (UFES) 06 - Indução ATCI 47 / 66
Indução Segundo Princípio da Indução Matemática
Segundo Princípio: Postagem - Exemplo
Qualquer valor de postagem igual ou maior que 12 reais pode ser
formado usando exclusivamente selos de 4 e de 5 reais. Uma prova
por indução (no número de selos, segunda versão):
Base de Indução. Seja k ∈ {12,13,14,15}
12 reais: 3 selos de 4
13 reais: 2 selos de 4 e 1 selo de 5
14 reais: 1 selo de 4 e 2 selos de 5
15 reais: 3 selos de 5
DCEL (UFES) 06 - Indução ATCI 48 / 66
Indução Segundo Princípio da Indução Matemática
Segundo Princípio: Postagem - Exemplo
Hipótese de Indução. Suponha que, para algum k ∈ N, e para
qualquer u ∈ N tal que 15 ≤ u ≤ k
Se o valor é u, então pode ser formado usando selos de 4 e 5
Passo de Indução. Seja uma postagem cujo valor é k + 1 reais
Tal postagem pode ser formada usando:
Uma postagem de k − 3 reais
Mais um selo de 4 reais
DCEL (UFES) 06 - Indução ATCI 49 / 66
Indução Definição Indutiva
Sumário
1 Cardinalidade de Conjuntos
2 Indução
Prova Indutiva
Segundo Princípio da Indução Matemática
Definição Indutiva
Expressões Regulares
Computações de um Autômato Finito
DCEL (UFES) 06 - Indução ATCI 50 / 66
Indução Definição Indutiva
Definição Indutiva
Princípio da Indução Matemática: pode ser usado em definições
Definição Indutiva ou Definição Recursiva
Base de indução: explicita os casos elementares (os mais
simples)
Passo de indução/recursão: demais casos são definidos em
termos dos anteriores
DCEL (UFES) 06 - Indução ATCI 51 / 66
Indução Definição Indutiva
Definição Indutiva - Fecho Transitivo - Exemplo
Endorrelação R : A→ A. Fecho Transitivo
1 Se 〈a,b〉 ∈ R, então 〈a,b〉 ∈ R+
2 Se 〈a,b〉 ∈ R+ e 〈b, c〉 ∈ R+, então 〈a, c〉 ∈ R+
3 Os únicos elementos de R+ são os construídos como acima
(1) base de indução
(2) passo de indução (hipótese?)
(3) garante que, de fato, é definição indutiva
(3) pode ser omitido (subentendido)
DCEL (UFES) 06 - Indução ATCI 52 / 66
Indução Definição Indutiva
Definição Indutiva - Conjunto de Todas as Palavras - Exemplo
Alfabeto Σ = {a,b}
Σ∗ = {ε,a,b,aa,ab,ba,bb,aaa, . . .}
Base de Indução
ε ∈ Σ∗
qualquer x ∈ Σ, tem-se que x ∈ Σ∗
Passo de Indução
Se u e v são palavras de Σ∗ então a concatenação uv é palavra de Σ∗
DCEL (UFES) 06 - Indução ATCI 53 / 66
Indução Definição Indutiva
Definição Indutiva - Fórmula Lógica - Exemplo
Simplificada, não incluindo quantificadores, variáveis etc.
Base de Indução
Qualquer proposição atômica (incluindo V e F ) é fórmula
Passo de Indução: Se q e r são fórmulas, então também são
fórmulas
(¬q)
(q ∧ r)
(q ∨ r)
(q → r)
(q ↔ r)
DCEL (UFES) 06 - Indução ATCI 54 / 66
Indução Definição Indutiva
Definição Indutiva × Princípio da Indução Matemática - Exemplo
Ilustração da relação entre o Princípio da Indução e a definição
indutiva
Definição indutiva (no número de conectivos) de fórmula lógica
usando o Segundo Princípio
Base de Indução: Seja k = 0
Qualquer proposição atômica (incluindo V e F ) é uma fórmula
Hipótese de Indução: Suponha que, para algum k ∈ N, e para
qualquer i ∈ N tal que i ≤ k
Se p é uma fórmula com i conectivos, então p é uma fórmula lógica
DCEL (UFES) 06 - Indução ATCI 55 / 66
Indução Definição Indutiva
Definição Indutiva × Princípio da Indução Matemática - Exemplo
Passo de Indução. Seja p uma fórmula com k + 1 conectivos
p pode ser reescrita
q e r são fórmulas e possuem conjuntamente k conectivos
(¬q)
(q ∧ r)
(q ∨ r)
(q → r)
(q ↔ r)
DCEL (UFES) 06 - Indução ATCI 56 / 66
Indução Expressões Regulares
Sumário
1 Cardinalidade de Conjuntos
2 Indução
Prova Indutiva
Segundo Princípio da Indução Matemática
Definição Indutiva
Expressões Regulares
Computações de um Autômato Finito
DCEL (UFES) 06 - Indução ATCI 57 / 66
Indução Expressões Regulares
Expressões Regulares
Autômato Finito
Já introduzido
Especialmente importante
Define a classe das linguagens regulares
Possui diversas aplicações na Computação
Expressões Regulares
Alternativa para definir linguagens regulares
Definição indutiva que segue: Segundo Princípio da Indução
Matemática (segunda versão)
DCEL (UFES) 06 - Indução ATCI 58 / 66
Indução Expressões Regulares
Expressão Regular (ER) sobre um alfabeto Σ - Definição
Base de Indução
∅ é ER e denota a linguagem vazia
ε é ER e denota a linguagem {ε}
qualquer símbolo x ∈ Σ é ER e denota a linguagem {x}
Passo de Indução. Se r e s são ER e denotam as ling. R e S, então
União: (r + s) é ER e denota a linguagem R ∪ S
Concatenação: (rs) é ER e denota a linguagem
RS = {uv | u ∈ R e v ∈ S}
Concatenação Sucessiva: (r∗) é ER e denota a linguagem R∗
DCEL (UFES) 06 - Indução ATCI 59 / 66
Indução Expressões Regulares
Expressão Regular (ER) - Exemplos
Omissão de parênteses em uma ER é usual
Concatenação sucessiva: precedência sobre concatenação e
união
Concatenação: precedência sobre união
ER Linguagem Representada
aa somente a palavra aa
ba∗ todas palavras iniciam por b seguido por 0 ou mais a
(a + b)∗ todas as palavras sobre {a,b}
(a + b)∗aa(a + b)∗ todas as palavras contendo aa como subpalavra
a∗ba∗ba∗ todas as palavras contendo exatamente dois b
(a + b)∗(aa + bb) todas as palavras que terminam com aa ou bb
(a + ε)(b + ba)∗ todas as palavras sem dois a consecutivosDCEL (UFES) 06 - Indução ATCI 60 / 66
Indução Computações de um Autômato Finito
Sumário
1 Cardinalidade de Conjuntos
2 Indução
Prova Indutiva
Segundo Princípio da Indução Matemática
Definição Indutiva
Expressões Regulares
Computações de um Autômato Finito
DCEL (UFES) 06 - Indução ATCI 61 / 66
Indução Computações de um Autômato Finito
Computações de um Autômato Finito
Exemplos de modelos computacionais introduzidos
Rede de Petri, definida como uma relação
Autômato Finito, definido como uma função parcial
Definidos sintaticamente: definições formais de sua forma
Semântica ??
Interpretação do funcionamento ou processamento
Introduzida textualmente, de forma informal
DCEL (UFES) 06 - Indução ATCI 62 / 66
Indução Computações de um Autômato Finito
Autômato Finito
Processamento de um Autômato Finito é a sucessiva
aplicação de computações atômicas (transições)
DCEL (UFES) 06 - Indução ATCI 63 / 66
Indução Computações de um Autômato Finito
Programa de um Autômato Finito: função parcial
δ : Q × Σ→ Q
δ(〈q,a〉) = p
No estado q, ao ler o símbolo a, assume o estado p
Para dar semântica à sintaxe de um Autômato Finito
Estender a definição da função programa
Argumento: um estado e uma palavra
Definida indutivamente
DCEL (UFES) 06 - Indução ATCI 64 / 66
Indução Computações de um Autômato Finito
Função Programa Estendida
Base de indução: entrada vazia (palavra vazia)
Permanece no mesmo estado
Passo de indução: entrada não-vazia (palavra não-vazia)
Processa o primeiro símbolo da entrada, usando δ
Mesmo raciocínio sucessivamente ao resto da palavra
Função Programa Estendida - definição formal
δ : Q × Σ∗ → Q
δ(q, ε) = q
δ(q,aw) = δ(δ(q,a),w)
DCEL (UFES) 06 - Indução ATCI 65 / 66
Indução Computações de um Autômato Finito
Função Programa Estendida - Exemplo
δ(q0,abba) = δ(δ(q0,a),bba) =
δ(q1,bba) = δ(δ(q1,b),ba) =
δ(q2,ba) = δ(δ(q2,b),a) =
δ(qf ,a) = δ(δ(qf ,a), ε) =
δ(qf , ε) = qf
DCEL (UFES) 06 - Indução ATCI 66 / 66
	Cardinalidade de Conjuntos
	Indução
	Prova Indutiva
	Segundo Princípio da Indução Matemática
	Definição Indutiva
	Expressões Regulares
	Computações de um Autômato Finito