Unidade II Aulas 02.pdf

Prévia do material em texto

Lógica para Computação
Unidade II – Aula 02
Profª MSc. Patricia Medyna Lauritzen de Lucena Drumond
patriciamedyna@ufpi.edu.br
Universidade Federal do Piauí
Centro de Ensino Aberto e a Distância
Curso de Sistemas de Informação
Aula 02
Lógica e Outras Teorias –
Princípio da Indução
Princípio da Indução Finita
 Considere duas fórmulas p e q tais que p implica q. Por
definição, p implica q ⇔ para toda interpretação de I, se
I[p] = V, então I[q] = V.
 No princípio da Indução existem duas condições: a
condição básica e a condição de indução.
Princípio da Indução Finita
 Definição (primeira forma do princípio da indução finita).
Suponha que para cada número natural n, n ≥ 1, seja feita a
assertiva A(n). Além disso, suponha que seja possível
demonstrar as duas propriedades a seguir:
1. Base da indução. A assertiva A(1) é verdadeira.
2. Passo da indução. Para cada número natural n ≥ 1, se
A(n) for verdadeira, então A(n+1) também é verdadeira.
Conclui-se que a assertiva A(n) é verdadeira para todo
número natural n.
Princípio da Indução Finita
 Exemplo: Demonstrar que a igualdade (1+2+. .+ n) =
n(n+1)/2 é válida para todo número natural n.
Princípio da Indução Finita
 Exemplo: Demonstrar que a igualdade (1+2+. .+ n) =
n(n+1)/2 é válida para todo número natural n.
1. Base da indução:
A(1): 1 = 1(1+1)/2. Logo, A(1) é verdadeira.
Princípio da Indução Finita
 Exemplo: Demonstrar que a igualdade (1+2+. .+ n) = n(n +
1)/2 é válida para todo número natural n.
1. Base da indução: A(1): 1 = 1(1+1)/2. Logo, A(1) é
verdadeira.
2. Passo indutivo: A(n+1): (1 + 2 + ... + n + (n +1)) =
(n+1)((n+1)+1)/2.
Princípio da Indução Finita
 Exemplo: Demonstrar que a igualdade (1+2+. .+ n) =
n(n+1)/2 é válida para todo número natural n.
1. Base da indução: A(1): 1 = 1(1+1)/2. Logo, A(1) é
verdadeira.
2. Passo indutivo: A(n+1): (1 + 2 + ... + n + (n +1)) =
(n+1)((n+1)+1)/2.
Hipótese de Indução: A(n): (1+2+. .+ n) = n(n+1)/2
Princípio da Indução Finita
 Exemplo: Demonstrar que a igualdade (1+2+. .+ n) =
n(n+1)/2 é válida para todo número natural n.
1. Base da indução: A(1): 1 = 1(1+1)/2. Logo, A(1) é
verdadeira.
2. Passo indutivo: A(n+1): (1 + 2 + ... + n + (n +1)) =
(n+1)((n+1)+1)/2.
Hipótese de Indução: A(n): (1+2+. .+ n) = n(n+1)/2
A(n+1): (1+2+...+n) + (n+1) = n(n+1)/2 + (n+1)
Princípio da Indução Finita
 Exemplo: Demonstrar que a igualdade (1+2+. .+ n) =
n(n+1)/2 é válida para todo número natural n.
1. Base da indução: A(1): 1 = 1(1+1)/2. Logo, A(1) é
verdadeira.
2. Passo indutivo: A(n+1): (1 + 2 + ... + n + (n +1)) =
(n+1)((n+1)+1)/2.
Hipótese de Indução: A(n): (1+2+. .+ n) = n(n+1)/2
A(n+1): (1+2+...+n) + (n+1) = n(n+1)/2 + (n+1)
= n(n+1)/2 + 2(n+1)/2 = (n+1)(n+2)/2.
Princípio da Indução Finita
 Exemplo: Demonstrar que a igualdade (1+2+. .+ n) =
n(n+1)/2 é válida para todo número natural n.
1. Base da indução: A(1): 1 = 1(1+1)/2. Logo, A(1) é
verdadeira.
2. Passo indutivo: A(n+1): (1 + 2 + ... + n + (n +1)) =
(n+1)((n+1)+1)/2.
Hipótese de Indução: A(n): (1+2+. .+ n) = n(n+1)/2
A(n+1): (1+2+...+n) + (n+1) = n(n+1)/2 + (n+1) =
n(n+1)/2 + 2(n+1)/2 = (n+1)(n+2)/2.
Assim, a assertiva é verdadeira para o caso base e para o
passo indutivo. Logo, ela é verdadeira para todo número
natural n.
Princípio da Indução Finita
 Exemplo: Demonstrar que a igualdade 2 + 6 + 10 + . . . +
(4n – 2) = 2n² é válida para todo número natural n.
Princípio da Indução Finita
 Exemplo: Demonstrar que a igualdade 2 + 6 + 10 + . . . +
(4n – 2) = 2n² é válida para todo número natural n.
1. Base da indução:
A(1): 4.1-2 = 2.1²
Princípio da Indução Finita
 Exemplo: Demonstrar que a igualdade 2 + 6 + 10 + . . . +
(4n – 2) = 2n² é válida para todo número natural n.
1. Base da indução:
A(1): 4.1-2 = 2.1²
2 = 2
Princípio da Indução Finita
 Exemplo: Demonstrar que a igualdade 2 + 6 + 10 + . . . +
(4n – 2) = 2n² é válida para todo número natural n.
1. Base da indução:
A(1): 4.1-2 = 2.1²
2 = 2, portanto A(1) é verdadeira.
Princípio da Indução Finita
 Exemplo: Demonstrar que a igualdade 2 + 6 + 10 + . . . +
(4n – 2) = 2n² é válida para todo número natural n.
2. Passo indutivo: A(n+1): (2 + 6 + 10 + ... + (4n-2) + (4n
+2)) = 2(n+1)².
Princípio da Indução Finita
 Exemplo: Demonstrar que a igualdade 2 + 6 + 10 + . . . +
(4n – 2) = 2n² é válida para todo número natural n.
2. Passo indutivo: A(n+1): (2 + 6 + 10 + ... + (4n-2) + (4n
+2)) = 2(n+1)².
Hipótese de Indução: A(n): (2 + 6 + 10 + ... + (4n-2)) =
2n²
Princípio da Indução Finita
 Exemplo: Demonstrar que a igualdade 2 + 6 + 10 + . . . +
(4n – 2) = 2n² é válida para todo número natural n.
2. Passo indutivo: A(n+1): (2 + 6 + 10 + ... + (4n-2) + (4n
+2)) = 2(n+1)².
Hipótese de Indução: A(n): (2 + 6 + 10 + ... + (4n-2)) =
2n²
Princípio da Indução Finita
 Exemplo: Demonstrar que a igualdade 2 + 6 + 10 + . . . +
(4n – 2) = 2n² é válida para todo número natural n.
2. Passo indutivo: A(n+1): (2 + 6 + 10 + ... + (4n-2) + (4n
+2)) = 2(n+1)².
Hipótese de Indução: A(n): (2 + 6 + 10 + ... + (4n-2)) =
2n²
Princípio da Indução Finita
 Exemplo: Demonstrar que a igualdade 2 + 6 + 10 + . . . +
(4n – 2) = 2n² é válida para todo número natural n.
2. Passo indutivo: A(n+1): (2 + 6 + 10 + ... + (4n-2) + (4n
+2)) = 2(n+1)².
Hipótese de Indução: A(n): (2 + 6 + 10 + ... + (4n-2)) =
2n²
Princípio da Indução Finita
 Exemplo: Demonstrar que a igualdade 2 + 6 + 10 + . . . +
(4n – 2) = 2n² é válida para todo número natural n.
2. Passo indutivo: A(n+1): (2 + 6 + 10 + ... + (4n-2) + (4n
+2)) = 2(n+1)².
Hipótese de Indução: A(n): (2 + 6 + 10 + ... + (4n-2)) =
2n²
A(n+1): (2 + 6 + 10 + ... + (4n-2) + (4n +2)) =
2n² + (4n+2)
Princípio da Indução Finita
 Exemplo: Demonstrar que a igualdade 2 + 6 + 10 + . . . +
(4n – 2) = 2n² é válida para todo número natural n.
2. Passo indutivo: A(n+1): (2 + 6 + 10 + ... + (4n-2) + (4n
+2)) = 2(n+1)².
Hipótese de Indução: A(n): (2 + 6 + 10 + ... + (4n-2)) =
2n²
A(n+1): (2 + 6 + 10 + ... + (4n-2) + (4n +2)) =
2n² + (4n+2) = 2(n²+2n+1)
Princípio da Indução Finita
 Exemplo: Demonstrar que a igualdade 2 + 6 + 10 + . . . +
(4n – 2) = 2n² é válida para todo número natural n.
2. Passo indutivo: A(n+1): (2 + 6 + 10 + ... + (4n-2) + (4n
+2)) = 2(n+1)².
Hipótese de Indução: A(n): (2 + 6 + 10 + ... + (4n-2)) =
2n²
A(n+1): (2 + 6 + 10 + ... + (4n-2) + (4n +2)) =
2n² + (4n+2) = 2(n²+2n+1) = 2(n+1)²
Princípio da Indução Finita
 Exemplo: Demonstrar que a igualdade 2 + 6 + 10 + . . . +
(4n – 2) = 2n² é válida para todo número natural n.
2. Passo indutivo: A(n+1): (2 + 6 + 10 + ... + (4n-2) + (4n
+2)) = 2(n+1)².
Hipótese de Indução: A(n): (2 + 6 + 10 + ... + (4n-2)) =
2n²
A(n+1): (2 + 6 + 10 + ... + (4n-2) + (4n +2)) =
2n² + (4n+2) = 2(n²+2n+1) = 2(n+1)²
Portanto é válida para todo o natural n.