Cap. 2 - Contextos e estratégias de demonstração Flashcards
Como se usa a prova direta como método de demosntrção?
Dada a seguinte implicação p ⇒ q:
Consiste em admitir a
hipótese p como verdadeira e, mostrar que a tese q é verdadeira.
Exemplo:
Proposição - Se m é um número inteiro par e n um número inteiro arbitrário, então mn é um número inteiro par.
Prova - Seja m um número inteiro par.
Então,
∃k ∈ Z : m = 2k (por definição de número inteiro par)
⇒ mn = (2k)n (dado que a = b ⇒ ac = bc)
⇒ mn = 2(kn) (associatividade da multiplicação)
Logo, mn é um número inteiro par (por definição).
Como se usa a prova direta da equivalência?
Consiste numa prova direta em ambos sentidos.
Ou seja, partindo de p ⇒ q, assumimos p como verdadeiro e depois q como verdadeiro.
Exemplo:
Vamos demonstrar o seguinte teorema:
Teorema. (x, y) = (u, v) ⇔ (x = u ∧ y = v).
Em que consiste a demonstração por contraposição?
A demonstração por contraposição tem por base a seguinte tautologia:
(p ⇒ q) ⇔ (¬q ⇒ ¬p)
O processo passa por demonstrar que ¬q ⇒ ¬p é verdade, que por contraposição é a mesma coisa que mostrar que p ⇒ q.
Exemplo:
Slide4 do PPT 1 de Demonstrções
Como se demonstra algo usando a redução ao absurdo?
Esta demonstração tem por base as seguintes tautologias:
(p ⇒ q) ⇔ (¬p ∨ q) e ¬(p ⇒ q) ⇔ (p ∧ ¬q).
Para se provar a implicação p ⇒ q, admite-se p verdadeiro e q falso (ou seja, nega-se a implicação) e procura-se obter uma contradição.
Exemplo:
Se n^2 é um número inteiro par, então n é um número inteiro par.
Prova: n^2 par e n é ímpar implica n^2 + n ímpar.
Por outro lado, sabe-se que n(n + 1) é par.
Então:
∃m ∈ Z : m é ímpar e m é par, o que é contraditório.
Como funciona o princípio dei ndução matemática (Não completo)?
a) a proposição P(n0) é verdadeira ← Condição inicial.
b) para cada inteiro k ≥ n0, a implicação
P(k) ⇒ P(k + 1)
é também verdadeira, ou seja, se P(k) é verdadeira,
então P(k + 1) é também verdadeira.
• P(k) ⇒ P(k + 1) constitui o passo de indução.
- Começamos por establecer uma condição inicial. Para o n inicial (n0). Temos de comprovarque é verdadeira.
- Se for verdade para n=n0, então formulamos a hipótese de ser verdadeira para n=p.
- Formulamos agora a tese, que consiste em comprovar se o caso se verifica para n=p+1.
- Tendo estas duas proposições, tentamos a partir da tese, poder usar a hipótese e comprovar aquilo que procuramos.
Exemplo:
https://www.youtube.com/watch?v=OabymAXVaxA&t=360s&ab_channel=Explicamat
Como funciona o princípio da Gaiola dos Pombos?
Este princípio diz o seguinte, tendo n+1 pombos e tendo n gaiolas, podemos afirmar que existe uma gaiola que tem de conter 2 ou mais pombos.
O que nos diz o Teorema de Dirchlet, ou da Pior Hipótese?
Dando o exemplo de uma caixa com 5 bolas azuis, 4 pretas e 3 brancas, tem-se o seguinte. E quero saber o número mínimo de bolas que eu preciso de tirar para ter uma de cada cor, forçosamente?
A pior hipótese será sempre, tirar 5 bolas azuis, depois 4 pretas e depois restam 3 brancas, mas não necessitamos de as tirar todas, uma vez que queremos o nº mínimo de bolas.
