Métodos Para Prova de Teoremas

Métodos de Provas de Teoremas

==========

Universidade Federal de Santa Catarina-UFSC

Disciplina: Fundamentos Matemáticos para Informática

Professor: Ricardo Custódio

Aluno: GABRIEL DONADEL DALL´AGNOL

Matricula: 18100853 - Sistemas de Informação

Métodos para Prova de Teoremas

1. Prova Direta

O método da Prova direta consiste no desenvolvimento direto do teorema, ou seja, consiste em supor que a hipótese está correta e a partir dela tentamos chegar a uma tese.

Teorema:

Se a é um inteiro ímpar então a² é um inteiro impar

Demonstração:

Supondo que a seja um inteiro ímpar, necessariamente existe algum inteiro k tal que a = 2k + 1. Logo,

a² = (2k + 1)² = 4k² + 4k + 1 = 2(2k² + 2k) + 1.

Sendo assim, está provado pelo método de prova direta, que a² é um inteiro ímpar.

1. Prova por Contraposição

O método da Prova por Contraposição é formado pelo uso da propriedade Contrapositiva, que mostra a equivalência de p → q e ¬q →¬p, a partir disso tentamos chega a uma tese para ¬q →¬p. Quando provamos que o valor de ¬q →¬p , igualmente provamos o que o valor p → q.

Teorema:

Se n é um inteiro e 3n + 2 é impar, então n é um inteiro impar.

Demonstração:

Assumindo que “Se 3n + 2 é impar, então n é um inteiro impar” seja falso, implicando em n seja par, teremos pela definição de um inteiro par n = 2k, para um inteiro k. Logo,

3n + 2 = 3(2k) + 2 = 6k + 2 = 2(3k + 1)

Sendo assim, fica provado que 3n + 2 é par, já que é múltiplo de 2 e logo não é impar, provando a negação da premissa de nosso teorema. Já que a negação da conclusão da declaração condicional implica que a hipótese seja falsa, então a declaração original é verdadeira, provando assim, que “Se n é um inteiro e 3n + 2 é impar, então n é um inteiro impar”.

Prova Vácuo e Prova trivial:

Podemos provar de maneira rápida que a condicional p → q é verdade quando sabemos que p é falso, porque p → q deve ser verdade, quando p é falso. Consequentemente, se conseguirmos demonstrar que p é falso, então teremos a prova, chamada de prova de vácuo, da declaração condicional p → q.

Outra maneira rápida de provar que a condicional p → q é verdade, será por meio do uso da prova trivial, que consiste em mostrar que q é verdade e sendo assim, p → q também deve ser verdade.

1. Prova por Contradição

O método de Prova por Contradição compõe-se de uma metodologia diferente das demais, ao invés de provar que p então q, admitimos que p é verdade e que q é falso, assim tentamos chegar a uma ideia absurda.

Teorema:

O número é um número irracional.

Demonstração:

Supondo por contradição que seja racional, então existem inteiros p e q sem fatores em comum, tais que = p/q. Logo, elevando os dois lados da equação ao quadrado obtemos:

2 = p² /q² .

Portanto,

2q² = p² .

Isto significa que p² é par e desta maneira p é par. Além disso, como p é par, então existe algum inteiro k tal que p = 2k. Logo, 2q² = 4k² , e assim, q² = 2k². Isto significa que q² é par e portanto q é par. Acabamos de mostrar que tanto p quanto q são divisíveis por 2. Isto contraria nossa hipótese inicial de que = p/q com p e q sem fatores em comum. Consequentemente, é irracional.

1. Prova de Equivalência

O método de Prova por Equivalência consiste em provar que uma declaração bicondicional ( uma declaração na forma p ↔ q) seja verdadeira tanto para

p → q quanto para q → p. A validade dessa abordagem é baseada na tautologia

(p ↔ q) ↔ (p → q ) ∧ (q → p).

Teorema:

Se n é um inteiro, então n é impar; se, e somente se, n² for impar.

Demonstração:

Nesse teorema de formato “p se e somente se q”, onde p é “n é impar” e q é “n² é impar”, precisamos mostrar que p → q e q → p são verdade.

Para provar que p → q é verdade, supomos que n seja um inteiro ímpar. Então existe algum inteiro k tal que n = 2k + 1. Logo,

n² = (2k + 1)² = 4k² + 4k + 1 = 2(2k² + 2k) + 1.

Sendo assim, está provado que n² é um inteiro ímpar e que p → q é verdade.

Agora, para provar que q → p usamos o método de contraposição, supondo que n não seja ímpar, logo n é par, isto implica na existência de um inteiro k tal que n = 2k. Assim, para provar este teorema precisamos mostrar que esta hipótese implica na conclusão de n² não é impar, ou seja, que n² é par. Elevando ao quadrado os dois lados desta equação obtemos,

n² = 4k² = 2(2k²)

resultando em n² também ser par porque n² = 2t, onde t = 2k². Já que a negação da conclusão da declaração condicional

...