Sumário

Aula 1

Aula 2

Obs A ≡ B é o mesmo que dizer que A ⇔ B é verdadeiro

Teorema 2 (identidade).

(1)

(2)

Teorema 3 (dominação).

(3)

(4)

Teorema 4 (idempotência).

(5)

(6)

Teorema 5 (dupla negação).

(7)

Teorema 6 (distributiva).

(8)

(9)

Teorema 7 (comutativa).

(10)

(11)

Teorema 8 (associativa).

(12)

(13)

Teorema 9 (De Morgan).

(14)

(15)

Aula 3

Um argumento com premissas P₁,P₂,…,P_n e conclusão Q é válido quando

ou seja

(16)

Aula 4

Uma sentença aberta é uma sentença parametrizada por uma ou mais variáveis. Uma sentença aberta não tem valor lógico. O domínio da(s) variável(is) é chamado universo do discurso .

O conjunto verdade de uma sentença aberta P(x) sobre o universo U é o conjunto

(17)

ou seja, o conjunto formado pelos elementos de U que tornam P(x) verdadeira.

Quantificador Universal é a proposição

(18)

significa que P(x) é verdadeiro para todos os valores de x no universo do discurso.

Quantificador Existencial é a proposição

(19)

significa que P(x) é verdadeiro para algum valor de x no universo do discurso.

Podemos caracterizar os quantificadores com proposições a cerca do conjunto-verdade,

Com isso é fácil deduzir a negação das proposições quantificadas

Em proposições com mais de uma variável a ordem em que os quantificadores aparece é importante. Por exemplo, se x e y são inteiros

(20)

não é logicamente equivalente a

(21)

pois (20) é verdadeiro enquanto que (21) é falso. Entretanto, em alguns casos vale a equivalência. Por exemplo, se x e y são números naturais

(22)

é verdadeira, assim como

(23)

pois todo x ∈ ℕ divide o 0.

Se X ⊆ U ou para explicitar o universo, escrevemos para todo x ∈ X, P(x) que significa

(24)

Aula 5

Aula 6

A e B agora denotam conjuntos.

x ∈ A denota a proposição x é elemento de A.

x ⁄∈ A denota a proposição não(x ∈ A).

∅ denota o conjunto vazio.

|A| denota a cardinalidade de A, isto é, o número de elementos quando A é finito.

Definição 8.

(25)

(26)

(27)

(28)

(29)

Teorema 25.

(30)

(31)

Definição 10. Sejam A₁,A₂,…,A_n conjuntos e n um natural positivo

(32)

Definição 11. Sejam A₁,A₂,…,A_n conjuntos e n um natural positivo

(33)

Definição 12. Sejam A₁,A₂,…,A_n conjuntos e n um natural positivo

(34)

Convenções Se n = 0

(35)

Se A_i = A para todo i

(36)

Aula 7

Notação [a..b] = {z ∈ ℤ: a ≤ z ≤ b}.

Somatórios

Seja X ⊆ ℝ um conjunto finito. Denotamos por

(37)

a soma de todos os elementos de X. Como X é um conjunto finito os seus elementos podem ser enumerados

(38)

e também escrevemos

(39)

Um tipo particular de soma será bastante utilizado mais tarde, a soma dos elementos de uma progressão aritmética e a soma dos elementos de uma progressão geométrica. Seja

A é uma progressão aritmética de razão r ∈ ℝ se

A é uma progressão geométrica de razão r ∈ ℝ se

(40)

para todo i ∈ [1..n - 1].

Teorema 27. Seja A = {a_i: i ∈ [0..n- 1]} uma progressão aritmética de razão r. Então

(41)

Teorema 28. Seja A = {a_i: i ∈ [0..n - 1]} uma progressão geométrica de razão r≠1. Então

(42)

Demonstração. Seja A = {a_i: i ∈ [0..n - 1]} uma progressão geométrica de razão r≠1. Vamos provar que ∑ _a∈Aa = a₀.

Da equação (40) temos que a_i = a₀rⁱ portanto

e usando o item 3 do teorema 26

e essa soma é telescópica, portanto

fatorando o a₀ no lado direito e dividindo tudo por r - 1 (o que podemos fazer pois r≠1), resulta em

♦

Aula 8

Um teorema é uma sentença que pode ser demonstrado ser verdadeira. Demonstramos que um teorema é verdadeiro exibindo uma sequência de proposições, que chamamos de prova de modo que em cada passo usamos um argumento válido para ter um conclusão verdadeira a partir de uma premissa verdadeira.

Vejamos algumas técnicas para construir provas de teoremas da forma A ⇒ B.

Prova direta. Pela definição de implicação A = V é o único caso que precisamos considerar para mostrar que a implicação A ⇒ B é verdadeira. Assumimos A verdadeiro e usamos argumentos válidos para concluir que B é verdadeiro, usualmente, com várias concicionais intermediarias e uma conclusão obtida por silogismo hipotético (veja a lista 1).

Por exemplo, se n é um número natural então a implicação

(43)

é verdadeira:

• Se 3 divide n é verdadeiro, então n = 3q é verdadeiro, por definição de divide;
• se n = 3q é verdadeiro, então n² = (3q)² é verdadeiro, elevando ao quadrado os dois lados da igualdade;
• se n² = (3q)² então n² = 9q²;
• se n² = 9q² então 9 divide n² é verdadeiro, por definição de divide.

Pelo silogismo hipotético: se 3 divide n então 9 divide n².

Como a variável n acima pode assumir qualquer valor natural, ou seja, n é um elemento genérico de ℕ, o que provamos de fato foi, pelo teorema 22 (generalização universal), que

Mais um exemplo:
Teorema A. Para todo n ∈ ℕ, se n é ímpar, então n² é ímpar.

Prova indireta. Nesse tipo de prova, demonstramos que uma proposição logicamente equivalente a A ⇒ B é verdadeira.

prova da contrapositiva:

Provamos que

é verdadeira e concluímos que A ⇒ B é verdadeira pela equivalência lógica

(44)

Por exemplo, a implicação

(45)

é verdadeira para todo número natural (tente uma prova direta).

Vamos provar a contrapositiva de (45)

• Suponha que n é ímpar, então pelo teorema A acima n² é ímpar.

Por (44) temos (45) verdadeira.

prova por vacuidade:

A proposição A ⇒ B é verdadeira porque conseguimos provar que A é falso. Veja o exercício 1 na aula 7.

prova por contradição:

Na prova por contradição assumimos que a negação da proposição a ser provada é verdadeira e derivamos disso uma contradição , ou seja, uma proposição falsa. De fato, se soubermos provar que não(C) ⇒ F é verdadeiro, então concluiremos a partir de definição de condicional que C é verdadeiro.

No caso de provar que A ⇒ B por contradição, provamos que não(A ⇒ B) ⇒ F e verdadeiro, que equivale a A e  não(B) ⇒ F ser uma proposição verdadeira.

O exercício 2 mostra algumas equivalências usadas nessa técnica.

Vamos provar por contradição:
Teorema B. Se a e b são números naturais coprimos, então não são ambos par.

Demonstração. Vamos provar que

por contradição.

Sejam a e b números naturais, vamos provar que é verdade a proposição

Suponha que mdc(a,b) = 1 e a par e b par é verdadeiro.

Se mdc(a,b) = 1 e a par e b par então a par e b par.

Se (a par e b par) então mdc(a,b) ≥ 2. Se mdc(a,b) ≥ 2 então mdc(a,b)≠1 portanto, por silogismos hipotético

cuja conclusão é uma contradição, ou seja, mdc(a, b)≠1 é falso. ♦

Essa demonstração não foi feita em aula. Vamos provar por contradição:
Teorema B’. Se d e e são números naturais, então

Demonstração. Sejam d e e números naturais, vamos provar que é verdade a proposição

Suponha que mdcd∕mdc(d,e),e∕mdc(d,e) = k e k > 1 é verdadeiro.

Se mdcd∕mdc(d,e),e∕mdc(d,e) = k então k divide d∕mdc(d,e) e k divide e∕mdc(d,e), portanto kmdc(d,e) divide d e kmdc(d,e) divide e.

Se k > 1 então kmdc(d,e) > mdc(d,e), uma contradição. ♦

Vamos provar por contradição:
Teorema C. é irracional.

Demonstração. Vamos provar que

por contradição, ou seja, vamos provar que

Suponha que ∈ ℚ.

Se ∈ ℚ então, por definição de ℚ, existem naturais positivos d e e tais que = .

Façamos

e temos mdc(a,b) = 1 pelo teorema B’, portanto, até aqui provamos

Se = então 2 = a²∕b².
Se 2 = a²∕b² então a² = 2b².
Se a² = 2b² então a² é par.
Se a² é par então a é par, pelo teorema A acima.
Se a é par então existe k ∈ ℕ, a = 2k.
Se a = 2k então 2b² = 4k².
Se 2b² = 4k² então b² = 2k².
Se b² = 2k² então b² é par.
Se b² então b é par.

Se a é par e b é par, então mdc(a,b) ≥ 2, que é uma contradição. ♦

Mais exemplos

Outra prova do teorema C . Seja x = . Vamos provar que

por contradição. De fato, provaremos que existem naturais positivos a e b tais que

(46)

(47)

e derivaremos daí uma contradição.

Vamos provar (46). Suponha que x ∈ ℚ. Então existem naturais positivos d e e tais que x = . Tomemos a = e b = , logo mdc(a,b) = 1.

Agora, vamos provar (47). Se x = então x² = a²∕b², ou seja, 2 = a²∕b². Multiplicando ambos os lados por b² temos 2b² = a², logo a² é par. Se a² é par então a é par, pelo teorema A acima. Se a é par então a = 2k e substituindo em 2b² = a² deduzimos 2b² = 4k², logo b² = 2k², ou seja b² é par. Pelo mesmo argumento dado anteriormente, b é par. Portanto, mdc(a,b) ≥ 2.

Usamos o teorema 16 e a partir de (46) e (47) obtemos

(48)

e simplificando o lado direito (teorema 13)

(49)

finalmente, pelo silogismo hipotético (veja (16) na lista 1) de (48) e (49)

e a conclusão é uma contradição. ♦

Outra prova do teorema B . Sejam a e b números naturais. Vamos provar que

Por (44) basta provarmos a contrapositiva

Suponha a par e b par. Então 2 divide a e 2 divide b, por definição de par, portanto, mdc(a,b) ≥ 2, ou seja, não(mdc(a,b) = 1) é verdadeiro. ♦

Aula 9

Demonstrações de proposições quantificadas existencialmente: Para demonstrar uma proposição da forma existe x, P(x), usualmente, ou

• (prova construtiva) exibimos um elemento c do universo tal que P(c) seja verdade, ou
• (prova não-construtiva) ou inferimos indiretamente a existência desse objeto que torna P verdadeira, por exemplo, através de uma prova por contradição: assumimos que tal objeto não existe e derivamos uma contradição.

Exemplos:

Teorema D. Existe um inteiro positivo que pode ser escrito como a soma de dois cubos de duas maneiras diferentes.

Teorema E. Existem x, y irracionais tais que x^y ∈ ℚ.

Teorema F. Existe uma partição {A,B} de ℤ com A e B infinitos.

Teorema G. Se ∈ ℚ então existe n ∈ ℤ, < n.

Teorema H. O poninômio p(x) = x³ + x - 1 tem exatamente uma raiz real.

Aula de EXERCÍCIOS E DÚVIDAS

Aula 10

questão 1 - 10 pts Sejam a,b,c naturais. Dê uma prova direta para: se a divide b e a divide c então a divide b + c.

questão 2 - 10 pts Prove pela contrapositiva: se x ∈ B - A então x ⁄∈ A ∩ B.

Sejam A,B conjuntos, vamos provar a contrapositiva

questão 3 - 10 pts Prove por contradição: (A - B) ∩ B = ∅.

questão 4 - 10 pts Prove: Se A ∩ B = ∅ então ∅⊆ A.

questão 5 - 20 pts Leia com atenção o seguinte teorema e uma suposta demonstração.

Teorema Sejam a, b, c, d números naturais. Se c divide a e c divide b e d divide a e d divide b e c não divide d, então dc divide a e dc divide b._________________________________________________________________________

(10 pts)

Dê um contraexemplo para a afirmação feita no teorema.

a = 6, b = 12, c = 6, d = 3.

(10 pts)

Indique o(s) erro(s) na demonstração.

Estão erradas as implicações:

Se c divide xd e não divide d, então c divide x.
Se c divide yd e não divide d, então c divide y.

No contraexemplo acima 6 divide 2 ⋅ 3 mas não divide 2 e não divide 3.

Um natural n pode dividir um produto de naturais pq mesmo que n não divida p e n não divida q.

questão 6 - 30 pts Determine uma fórmula em função de r e n, com r≠1, para

(Dica: use o truque da derivada explicado na lista. Pode usar que ∑ _i=0ⁿrⁱ = .)

Considere a soma dos n primeiros termos de uma PG que começa em 1 e tem razão r, onde n ∈ ℕ e r ∈ ℕ \{1}. Então

Podemos olhar para as duas expressões em cada lado da igualdade acima como uma função em r e derivá-las com respeito a r. No lado esquerdo temos

(50)

e no lado direito

Se f(r) = g(r), então f(r) = g(r), ou seja,

(51)

questão 7 - 30 pts Provamos em aula que o polinômio p(x) = x³ + x- 1 tem uma raiz real usando o Teorema do Valor Intermediário. Agora, usando contradição e o Teorema do Valor Médio prove que essa raiz é única.

Suponha que p(x) tem duas raízes e vamos deduzir uma contradição. Sejam r₁ e r₂ raízes distintas de p(x), de modo que r₁ < r₂. Como p(x) é contínua em [r₁,r₂] e derivável em (r₁,r₂) então podemos usar o teorema do valor médio para concluir que existe um ponto c ∈ [r₁,r₂] tal que

mas p(r₂) - p(r₁) = 0, portanto p′(c) = 0 que é uma contradição pois o p′(x) = 3x² + 1 > 0 qualquer que seja x.

Teorema do Valor Médio. Se f é contínua em [a,b] e derivável em (a,b) então existe c ∈ (a,b) tal que

Aula 11

correção da prova

Aula 12

A prova de invariantes ficará pra depois de indução.

Um programa está correto se a saída está correta para toda entrada. A prova da correção do programa tem duas partes: provar que a resposta está correta se o programa terminar ( correção parcial ), provar que o programa termina.

A seguir, p e q são proposições.

Notação p{S}q significa S está parcialmente correto com respeito a pré-condição p e a pós-condição q.

Exemplo Por exemplo, se p é x = 1 e q é z = 3 e S é o trecho de programa

então, p{S}q. De fato, suponha p. Após a execução de S, y = 2 e z = 1 + 2 pois de p temos x = 1. Portanto, z = 3.

Argumentos válidos para correção parcial de programas:

1. Composição

2. Condicional

2.1. No caso

o argumento é

2.2. No caso

o argumento é

3. Laços

No caso

o argumento é

A proposição (p e condição){S}p é o invariante do laço que por enquanto vamos assumir que é dado e é verdadeiro. Provar que uma proposição é invariante de laço precisa de indução, que veremos mais tarde.

Exemplo. Seja S o programa

Sejam p: m ∈ ℤ e n ∈ ℤ e q: p e a = |n| as proposições dadas no algoritmo, seja R o trecho de programa

Vamos provar

(52)

Assuma m ∈ ℤ e n ∈ ℤ.

Se m ∈ ℤ e n ∈ ℤ e n < 0 então após R terminar temos a = -n. Se n < 0 então |n| = -n portanto a = |n|, portanto

(53)

Agora, se m ∈ ℤ e n ∈ ℤ e não(n < 0) então após R terminar temos a = n. Se não(n < 0) então |n| = n portanto a = |n|. Portanto,

(54)

Portanto, de (53), (54) e do argumento 2.2 temos (52), e, portanto, p{R}q.

Agora, considere o trecho

e vamos provar (p e a = |n|){T}(q e k = 0 e x = 0).

Se V então após {k:=0;x:=0} vale k = 0 e x = 0, portanto

(55)

para qualquer proposição verdadeira q, em particular quando

é verdadeira.

Assuma r: q e k = 0 e x = 0. Se k < a (a condição do laço) então o invariante

é verdadeiro antes da primeira rodada do laço pois 0 = m0 e 0 ≤|n|. Assuma

antes de uma execução do trecho

Considere uma execução de U e denote por x′ e k′ os valores das variáveis x e k antes dessa execução. Então, por hipótese

e (condição) k′ < a; após a execução de U teremos x = x′ + m e k = k′ + 1.

Se x = x′ + m e x′ = mk′, então x = (mk′) + m = m(k′ + 1).
Se k = k′ + 1 x = m(k′ + 1) então x = mk.
Se k′ < a então k′ + 1 ≤ a.
Portanto, após a execução de U o invariante é verdadeiro, ou seja, “provamos”

e do argumento para laços, temos

ainda, (não(k < a) e x = mk e k ≤ a) ≡ (x = ma). Portanto,

logo r{enquanto (k<a) U}s, onde s: x = ma e a = |n|.

Finalmente, assuma s, denote por Q o trecho de programa

Se s, então x = m|n|.
Se x = m|n| e n < 0 então após Q, produto = -x.
Se produto = -x e x = m|n| e n < 0 então produto = -m|n| = -m(-n) = mn. Portanto t.

Agora, se x = ma e a = |n|, então x = m|n|.
Se x = m|n| e não(n < 0) então após Q, produto = x.
Se produto = x e x = m|n| e não(n < 0) então produto = m|n| = mn. Portanto, pelo argumento 2.2 para condicionais

Resumindo, provamos

1. p{se (n<0) então a:=-n; senão a:=n}q;
2. q{k:=0; x:=0}r;
3. r{enquanto (k<a){ c:=x+m; k:=k+1; }}s;
4. s{se (n<0) então produto:=-x;senão produto:=x}t;

De 1 e 2 temos

(56)

pela regra da composição. De 3 e 4 temos, por composição novamente

Aula 13

Um dos axiomas de Peano para os números naturais diz que para X ⊆ ℕ

(57)

Com isso temos o seguintes argumentos válidos: seja P(n) uma sentença aberta.

Teorema 29. Se

então

Provaremos:

Teorema 30. Seja a ∈ ℕ. Se

então

Demonstração. Para

se P(a) então 0 ∈ X. Seja n ≥ a e defina m = n - a. Se P(n) ⇒ P(n + 1) então m ∈ X ⇒ m + 1 ∈ X. Por (57) X = ℕ, portanto, P(n) para todo n ≥ a. ♦

Indução matemática é uma técnica de prova para proposições da forma para todo n ≥ a, P(n). Numa prova por indução provamos P(a) que é dito a base da indução, e provamos para todo n ≥ a, P(n) ⇒ P(n + 1) que é dito o passo da indução.

Exemplo Para todo n ∈ ℕ, ∑ _i=0ⁿi = n(n + 1)∕2.

Exemplo Para todo n ≥ 5, 2ⁿ > n².

A base é importante, sem ela poderíamos pensar que sabemos provar

que obviamente não vale, pois conseguimos provar a implicação do passo da indução para essa sentença. Vamos provar que

Seja n > 1 um natural e suponha que n(n + 1) é ímpar. Então

A passo é importante, uma prova descuidada pode por tudo a perder. Por exemplo, seja P(t) a sentença

Se max{a,b} = 0 então a = b = 0, portanto a base é verdadeira.

Seja t ∈ ℕ, suponha que

e vamos provar que para todo a, para todo b, (max{a,b} = t ⇒ a = b). Se max{a,b} = t então max{a - 1,b - 1} = t - 1, portanto pela hipótese acima a - 1 = b - 1, logo a = b.

Claramente, P(t) é falso (determine um contraexemplo). O problema com o passo é que P(0) ⁄⇒ P(1) quando a ou b vale 0.

Aula 14

Exemplo. Todo natural n ≥ 2 pode ser escrito como produto de primos.

Numa tentativa de prova usando o teorema 30 temos:

-a base é fácil, n = 2 é primo;
-no passo temos que provar que se n é produto de primos então n + 1 é produto de primos. Se n + 1 é primo a implicação é verdadeira (vacuidade), se n + 1 é composto então, por definição de número composto n + 1 = ab onde 1 ≤ a,b ≤ n são números naturais.

Se soubéssemos que a e b são produtos de primos então n + 1 seria produto de primos, mas só o que sabemos é que n é produto de primos.

Teorema 31. Sejam a ∈ ℕ e P(n) uma sentença aberta. Se

então

Ou seja, para todo n ≥ a, P(n) é verdadeiro sempre que P(a) é verdadeiro e para todo n ≥ a é verdadeiro que

Exemplo. Todo natural n ≥ 2 é primo ou pode ser escrito como produto de primos.

Exemplo. Todo inteiro n ≥ 7 poder ser escrito como múltiplo de 2 mais múltiplo de 5.

Exemplo. Seja P(n) a sentença: para todo n ∈ ℕ, 6n = 0.

Vamos provar P(n) por indução.

P(0) é verdadeiro. Seja n um natural arbitrário e vamos provar que para todo n, P(0) e P(1) e  e P(n) ⇒ P(n + 1). Suponhamos P(0) e P(1) e  e P(n). Então

pois de P(n) temos 6n = 0 e de P(1) temos 6 ⋅ 1 = 0; qual é o erro ?

Aula 15

Boa-Ordenação

Seja A ⊂ ℝ. O menor elemento de A, quando existe, é o elemento m ∈ A tal que para todo a ∈ A, m ≤ a.

Notação. min A denota o menor elemento de A, se ele existe.

Exemplo. A = (0, 1) ⊂ ℝ não tem menor elemento. (prove)

Exemplo. A = [0, 1) ⊂ ℝ tem menor elemento, min A = 0. (prove)

Teorema 32. Se A ⊂ ℕ e

então n + 1 é o menor elemento de A.

Demonstração. Se para todo x ∈ [0..n], x ⁄∈ A e existe x ∈ [0..n + 1], x ∈ A então n + 1 ∈ A.

Agora, precisamos provar que para todo a ∈ A, n + 1 ≤ a.

Por contradição. Suponha que não(para todo a ∈ A, n+1 ≤ a), ou seja,

Seja c ∈ A tal que c < n + 1 (instanciação existencial, teorema 22). Se c < n + 1 então c ∈ [0..n] portanto c ⁄∈ A, portanto

essa última proposição é uma contradição. ♦

Demonstração. Seja A um subconjunto não-vazio dos naturais. Vamos provar que A tem menor elemento em dois casos: 0 ∈ A e 0 ⁄∈ A.

No caso 0 ∈ A, o 0 é o menor elemento de A.

Assumimos que 0 ⁄∈ A e definimos

0 ∈ X, pois se 0 ⁄∈ A então 0 ∈ ℕ - A, logo {0} ⊂ ℕ - A. Notemos que {0} = [0..0].

Se A≠∅ então X≠ℕ.

Se 0 ∈ X e X≠ℕ então pela a contrapositiva do axioma de Peano (57)

concluímos que

Seja m tal que m ∈ X e m + 1 ⁄∈ X.
Agora, usando a definição de X,
se m ∈ X então [0..m] ⊂ ℕ - A.
[0..m] ⊂ ℕ - A ≡ para todo x ∈ [0..m], x ⁄∈ A;
se m + 1 ⁄∈ X então [0..m + 1] ⁄⊂ ℕ - A;
[0..m + 1] ⁄⊂ ℕ - A ≡ existe y ∈ [0..m + 1], y ∈ A;
portanto

e pelo teorema 32, m + 1 é o menor elemento de A. ♦

Exemplo. para todo inteiro n ≥ 5, existem naturais a e b tais que n = 2a + 5b.

Observação importante : os teoremas 29, 30, 31 e 33 são equivalentes. Prove esse fato.

Aula 16

Invariante de laço.

Consideremos o seguinte algoritmo:

Vamos provar que a seguinte proposição é um invariante do laço na terceira linha do algoritmo

(58)

Antes, porém, notemos que o invariante e a negação da condição do laço resulta que quando o laço termina temos i ≥ 1 e i ≤ n e f = i! e não(i < n), ou seja, i = n e f = n!, provando a correção parcial do algoritmo.

Vamos provar que a proposição (58) é verdadeira independente do número de vezes que o laço é executado. A prova é por indução no número de iterações do enquanto.

Suponhamos que a condição do laço vale, ou seja, i < n. Antes da primeira iteração (58) é verdadeiro pois i = f = 1! = 1.

Suponhamos que i < n e que i ≥ 1 e i ≤ n e f = i!. Após a execução de { f := f*(i+1); e após a execução de { i := i+1;} temos que para o novo valor de i, i ≥ 1 e i ≤ n e f = i!.

Voltemos ao exemplo da aula 12.

Suponha que a condição do laço, k < a, é verdadeira. Antes da primeira iteração o invariante é verdadeiro.

Suponha que a condição do laço, k < a, é verdadeira e que vale o invariante. Considere uma execução de { x:=x+m; k:=k+1; } e denote por x′ e k′ os valores das variáveis x e k antes dessa execução. Então, por hipótese

e (condição) k′ < a; após a execução temos x = x′ + m e k = k′ + 1.

Se x = x′ + m e x′ = mk′, então x = (mk′) + m = m(k′ + 1).
Se k = k′ + 1 x = m(k′ + 1) então x = mk.
Se k′ < a então k′ + 1 ≤ a.
Portanto, após a execução o invariante é verdadeiro

Algoritmos recursivos.

Exemplo 1.

A prova da correção é fácil usando indução.

Exemplo 2.

Aula 17

semana academica

Aula 18

Duas resoluções propostas pelo Leandro.

Exercício 18. Prove que o seguinte programa está parcialmente correto.

Demonstração. Sejam R o trecho de programa definido pelas linhas 1 e 2, S o trecho de programa definido pelas linhas 3 – 5, T todo o programa, e p e t as proposições:

É imediato que

(59)

Portanto,

Assumindo

como invariante do laço de S, temos, já que (r ⁄≥ d) é a condição de parada do laço, que

Logo,

e, dessarte, p{T}t.

Resta-nos ainda mostrar u serve como invariante do laço definido por S. Como r ≥ 0 e a = dq + r se r = a e q = 0, temos, da asserção 59, que p{R}u. Analisemos agora o que acontece quando executamos {r := r-d; q := q + 1} assumindo as linhas 4 e 5: sendo r′ e q′ os novos valores de, respectivamente, r e q, verificamos que q′ = q + 1 e r′ = r - d. Consequentemente, já que r ≥ d, r′≥ 0,

e, finalmente,

o que prova que u é de fato um invariante para o laço definido por S. ♦

Antes do próximo exercício, vamos provar que: Para quaisquer naturais não nulos a e b,

(60)

Demonstração. Como a e b são diferentes de 0,

Logo,

como queríamos mostrar. ♦

Exercício 6.h Prove usando indução que para todo n ≥ 0, ∑ _j=0ⁿ = 2ⁿ.

Demonstração. Sabemos que

Seja k um número natural qualquer. Por indução, suponhamos então que, para todo t ∈ [1..k], valha que

Como, de (60),

e, como

temos, da hipótese da indução, que

como queríamos mostrar. ♦

Aula 19

denota uma relação f ⊆ A×B que associada a todo a ∈ A um único b ∈ B, esse denotado por f(a), ou seja, b = f(a).

A é o domínio da função, B é o contradomínio da função, b é a imagem de a por f. A imagem de f é o conjunto

Função teto ⌈⌉: ℝ → ℤ dada por

Função chão ⌊⌋: ℝ → ℤ dada por

Aula 20

Teorema 35. Se f : ℝ → ℝ é contínua, crescente e tal que

então

Exemplo.
A função definida nos reais f(x) = , com k ∈ ℤ é contínua (pois é uma função linear) crescente e tal que f(x) ∈ ℤ ⇒ x ∈ ℤ (pois f(x) = t implica x = kt), portanto

Exercício. Prove que

Exemplo.
A função definida nos reais f(x) = , com k ∈ ℤ é contínua (pois é uma função linear) crescente e tal que f(x) ∈ ℤ ⇒ x ∈ ℤ (pois f(x) = t implica x = kt), portanto

Teorema 37. Se x ∈ ℝ então

Demonstração. Seja x ∈ ℝ e vamos provar que ⌊-x⌋ = -⌈x⌉. Sabemos do teorema 34 item 3 que

portanto

e do teorema 36 item 3 temos que

A prova de ⌈-x⌉ = -⌊x⌋é exercício. ♦

Aula 21

Definição indutiva . Seja n₀ ∈ ℕ e A = {n ∈ ℕ: n ≥ n₀}. Podemos definir uma função com domínio A usando indução da seguinte maneira:

• (base) especificamos o valor de f(n₀),
• (passo) especificamos para todo n ≥ n₀ como determinar f(n + 1) a partir de todos ou alguns elementos de {f(n₀),f(n₀ + 1),…,f(n - 1),f(n)}.

Se X ⊆ A é o conjunto dos pontos para os quais f está definida então pelo Princípio da Indução, teorema 31, X = A.

Exemplos

(1)

f(0) = 3 e para todo n ≥ 0, f(n + 1) = 2f(n) + 3.

(2)

F(0) = 1 e para todo n ≥ 0, F(n + 1) = (n + 1)F(n).

(3)

S(0) = 0 e para todo n ≥ 0, S(n + 1) = S(n) + g(n + 1), em que g é uma função

(4)

p(0) = 1 e para todo n ≥ 0, p(n + 1) = ap(n), em que a ∈ ℝ \{0}.

(5)

b(1) = 1 e para todo n ≥ 1, b(n + 1) = b + 1.

(6)

H(1) = 1 e para todo n ≥ 1, H(n + 1) = H(n) + .

Notemos que nos exemplos acima a função F é F(n) = n!, a função S é S(n) = ∑ _i=1ⁿg(i) e a função p é a função p(n) = aⁿ. O que podemos dizer a respeito das outras funções? Vamos provar que f(n) = 3(2ⁿ⁺¹ - 1) e que b(n) = ⌊log ₂(n)⌋ + 1.

Seja g: ℕ → ℕ definida por g(n) = 3(2ⁿ⁺¹ - 1). Vamos provar por indução que para f definida indutivamente no exemplo 1 acima vale para todo n, f(n) = g(n).

Se n = 0 então f(0) = 3 e g(0) = 3(2 - 1) = 3, portanto f(0) = g(0).

Agora, vamos provar que para todo n ∈ ℕ, se f(n) = g(n) então f(n + 1) = g(n + 1). Seja n um natural e assuma que f(n) = g(n). Então

Portanto, pelo teorema 29 para todo n, f(n) = g(n).

No caso do exemplo 5, seja ℓ: ℕ → ℕ definida por ℓ(n) = ⌊log ₂(n)⌋ + 1. Vamos provar por indução que para b definida indutivamente no exemplo acima vale para todo n, b(n) = ℓ(n).

Se n = 1 então b(1) = 1 e ℓ(1) = ⌊log ₂(1)⌋ + 1 = 1, portanto b(1) = ℓ(1).

Agora, vamos provar que para todo n ∈ ℕ, se para todo k ∈ [1..n], b(k) = ℓ(k) então b(n+1) = ℓ(n+1). Seja n um natural e assuma que para todo k ∈ [1..n], b(k) = ℓ(k). Então

Portanto, pelo teorema 29 para todo n ≥ 1, b(n) = ℓ(n).

Agora, o que podemos dizer da função H do exemplo 6? Podemos dizer muita coisa, menos uma fórmula aritmética simples para computar H(n), que é conhecido como n-ésimo número harmônico.

Aula 22

Relembrando dois conceitos do cálculo: seja f : ℕ → ℝ

lim _n→∞f(n) = 0 se e somente se

lim _n→∞f(n) = ∞ se e somente se

Exercício. Suponha f(x) > 0 para todo n ∈ ℕ. Prove que se lim _n→∞f(n) = 0 então lim _n→∞ = ∞.

Nessa aula f e g são funções de ℕ em ℝ.

Definição 16. Dizemos que f é muito menor que g se

Denotamos esse fato por f ≪ g.

Exemplos.
(1) 1 ≪ log(log(n)).
(2) log(log(n)) ≪ log(n).
(3) log(log(n)) ≪ log(n).
(4) log(n) ≪ n^ε para todo ε > 0.
(5) n^ε ≪ n^c para quaisquer 0 < ε < 1 ≤ c.
(6) n^c ≪ n^{log n} para todo 1 ≤ c.
(7) n^{log n} ≪ exp(n).
(8) exp(n) ≪ nⁿ.
(9) nⁿ ≪ exp(exp(n)).

Definição 17.

se existe n₀ ≥ 0 e existe c > 0 tais que

e nesse caso dizemos que g é um limitante superior assintótico para f.

Exemplos
(1) n² + 2n + 1 = O(n²).
(2) 5 sin(n) = O(1)

Atenção o símbolo de = na definição não é a igualdade no sentido usual. Notemos que

Observação. A recíproca não vale.

Aula 23

Exemplos.
(3) an² + bn + c = O(n²).

De

temos bn + c ≪ n² e pelo teorema 38, bn + c = O(n²). Certamente, an² = O(n²). Portanto, pelo teorema 40  an² + bn + c = O(n²).

De uma maneira geral podemos provar que

(4) para k ∈ ℕ constante, ∑ _i=0^ka _inⁱ = O(n^k).

De fato, ∑ _i=0^ka _inⁱ = a _kn^k + ∑ _i=0^k-1a _inⁱ e para o somatório temos

pois k -i > 0. Portanto, ∑ _i=0^k-1a _inⁱ ≪ n^k e pelo teorema 38 ∑ _i=0^k-1a _inⁱ = O(n^k). Como a_kn^K = O(n^k), pelo teorema 40 a _kn^k + ∑ _i=0^k-1a _inⁱ = O(n^k)

Exemplos.
(5) n log(n!) = O(n² log n).
Primeiro, temos n = O(n). Depois, n! = ∏ i = 1ⁿi < ∏i = 1ⁿn = nⁿ. Como log é crescente log(n!) < log(nⁿ) = n log(n), portanto log(n!) = O(n log(n)). Pelo teorema 42, n log(n!) = O(n² log n).

(6) para todo a > 0, log _a(n) = O(log ₂(n)).
De fato,

porém = O(1) e log ₂n = O(log ₂n) e pelo teorema 42, log _a(n) = O(log ₂(n)).

Não é verdade

1. se f₁(n) = O(g(n)) e f₂(n) = O(g(n)), então f₁(n) = f₂(n);
2. se f(n) = O(g(n)) então g(n) = O^-1(f(n));
3. se f₁(n) = O(g₁(n)) e f₂(n) = O(g₂(n)) e para todo n, g₁(n) < g₂(n), então para todo n, f₁(n) < f₂(n);
4. para quaisquer f e g, f(n) = O(g(n)) ou g(n) = O(f(n)).

Convenções.

• desconsiderar os coeficientes, por exemplo, usar O(n²) ao invés de O(an²), O(1) ao invés de O(1024);
• escrever no argumento de O(⋅) somente o termo mais significativo, por exemplo, usar O(n²) ao invés de O(an² + bn + c).

Definição 18.

e nesse caso dizemos que f é assintoticamente limitada inferiormente por g.

Teorema 43. f(n) = Ω(g(n)) se e somente se

Definição 19.

Teorema 44.

Teorema 45. f(n) = Θ(g(n)) se e somente se

Últimas aulas

Exemplos.
(7) log ₂ = Θ(log ₂(n)).

em que a igualdade segue do teorema 35 e a última desigualdade do teorema 34, item 3. Logo log ₂⌈n⌉ = O(log ₂n). Agora,

para todo n ≥ 4, portanto log ₂n = Ω(log ₂(⌈n⌉)). Pelo teorema 44 log ₂⌈n⌉ = Θ(log ₂(n)).

(8)  = Θ(log n).

(9) se a_k≠0 então ∑ _i=0^ka _inⁱ = Θ(n^k).
Vimos que ∑ _i=0^ka _inⁱ = O(n^k). Vamos provar que ∑ _i=0^ka _inⁱ = Ω(n^k).

porém

ainda

portanto

onde expressão são expressões algébricas que envolvem notação assintótica.

Nesses casos, os termos assintóticos em expressão 1 são quantificados universalmente, enquanto que os termos assintóticos em expressão 2 são quantificados existencialmente.

Exemplos.
(1)  n³ + O(n²) = O(n³) + n² + n entende-se como

para todo n.

Dado f(n) = O(n²), tome g(n) = n³ + f(n) - n² - n, então g(n) = O(n³) e n³ + f(n) = g(n) + n² + n.

(2) O número de comparações do Merge-Sort pode ser escrito como

(62)

que significa que existe f(n) = Θ(n) tal que T(n) = T + T + f(n), para todo n. É sabido que T(n) = Θ(n log n).

Veremos técnicas para solução assintótica de recorrências. Quando procuramos por soluções assintóticas não há motivo para especificar exatamente as condições iniciais, no caso (62), por exemplo, basta escrever T(n) = T + T + Θ(n)

Vimos que f dada por f(0) = 3 e f(n + 1) = 2f(n) + 3, se n ≥ 0, é dada por f(n) = 3(2ⁿ⁺¹ - 1). Isso pode ser descoberto iterando a definição indutiva. Assuma que n é grande

Resta provar por indução que f(n) = 3(2ⁿ⁺¹ - 1).

Da mesma forma, iterando b(1) = 1, b(n + 1) = b(⌊(n + 1)∕2⌋) + 1, temos (usaremos o exerc. 3 da lista 3)

Nem sempre funciona, ou as vezes é muito difícil chegar em algum lugar, por exemplo, tente o mesmo com

Por outro lado, em análise de algoritmos muitas vezes é suficiente uma solução assintótica, isto é, basta saber a ordem de grandeza da solução. Por exemplo, no caso da função F definida acima, podemos provar que F(n) = Θ(φⁿ), onde φ = por indução em n.

De fato, defina c = 1∕2, C = 1, e temos que verificar a base da indução n = 1 e n = 2 (exercício) que nesses casos

Seja n > 1 um natural e assuma que

Então

Considere a seguinte função definida indutivamente (recorrência)

Tomemos c = 1 e n₀ = 6.

Para n ∈ [2..6] temos

Essa solução está superestimada, de fato é possível provar uma solução justa ou seja, uma solução que limita assintoticamente superiormente e inferiormente a função T(n).

Vamos provar que T(n) = Θ(n log ₂n).

Primeiro vamos provar que T(n) = O(n⌈log ₂(n)⌉). Para tal, tomemos c = 2 e n₀ = 1 e vamos provar que

Para n = 1 temos T(1) = 0 e c1⌈log ₂(1)⌉ = 0 e para n = 2 temos T(2) = 1 e c2⌈log ₂(2)⌉ = 2, portanto, T(n) ≤ cn⌈log ₂(n)⌉ nesses casos.

Seja n > 2 inteiro e assumamos que

Por definição

e por hipótese

ainda, pelo teorema 35

e como ⌊x⌋≤ x e log ₂ é crescente

portanto

Com isso provamos que T(n) = O(n⌈log ₂(n)⌉). Ainda temos que n = O(n) e ⌈log ₂(n)⌉ = O(log ₂(n)), portanto, pelo teorema 42, n⌈log ₂(n)⌉ = O(n log ₂(n)), e pelo teorema 41 temos, finalmente, que T(n) = O(n log ₂(n)).

Agora, vamos provar que T(n) = Ω(n log ₂(n)) e com isso teremos que T(n) = Θ(n log ₂n). Para tal, tomemos c = 1∕2 e n₀ = 1 e vamos provar que

Para n = 1 temos T(1) = 0 e c1⌊log ₂(1)⌋ = 0 e para n = 2 temos T(2) = 1 e c2⌊log ₂(2)⌋ = 1, portanto, T(n) ≥ cn⌊log ₂(n)⌋ nesses casos.

Seja n > 2 inteiro e assumamos que

Por definição

e por hipótese

ainda, pelo teorema 36

e como ⌈x⌉≥ x e log ₂ é crescente

portanto

Com isso provamos que T(n) = Ω(n⌊log ₂(n)⌋). Ainda temos que n = Ω(n) e ⌊log ₂(n)⌋ = O(log ₂(n)) (prove), portanto, n⌊log ₂(n)⌋ = Ω(n log ₂(n)) (prove), finalmente, temos que T(n) = Ω(n log ₂(n)) (prove).

Notemos que de T(n) = Ω(n log ₂(n)) não vale que T(n) = O(n). Onde está o erro da seguinte prova.

Vamos provar que existem c,n₀ > 0 tais que T(n) ≤ cn para todo n ≥ n₀. Tomemos c = 1∕2 e n₀ = 1.

Para n = 1, 2 a desigualdade vale (verifique). Seja n > 2 inteiro e assumamos que para todo k ∈ [n₀..n - 1], T(k) ≤ ck. Vamos mostrar que T(n) ≤ cn.

Vamos usar a mesma técnica para mostrar que b(1) = 1, b(n+1) = b(⌊(n+1)∕2⌋)+1 tem solução assintótica b(n) = Θ(log ₂n) (claramente, essa prova é desnecessária pois sabemos que b(n) = ⌊log ₂n⌋ + 1 e é fácil provar que ⌊log ₂n⌋ + 1 = Θ(log ₂n), a idéia é dar mais um exemplo de demonstração de solução assintótica).

Primeiro, vamos mostrar que b(n) = O(⌊log ₂n⌋).

Vamos mostrar que para c = 3 e n₀ = 2, b(n) ≤ c⌊log ₂n⌋ para todo n ≥ n₀.

Para n = 2, 3 temos b(2) = b(3) = 2 e c⌊log ₂2⌋ = c⌊log ₂3⌋ = c, portanto, b(n) ≤ c⌊log ₂n⌋ nesses casos. Seja n > 3 e assuma que para todo k ∈ [n₀..n - 1], b(k) ≤ c⌊log ₂k⌋. Então