Nos posts anteriores definimos porposições, teoremas, corolários, dentre outros. Para demonstrarmos teoremas significa que a proposição dada é uma tautologia, em que obtemos através das tabelas verdades. A seguir, apresentamos alguns métodos para demosntração de resultados.

Método dedutivo

O método dedutivo pe obtido através do uso de definições e outros resultados pré estabelecidos. Para isto, utilizamos as implicações $(\Rightarrow)$ e bi-implicações lógicas $(\Leftrightarrow)$.

Exermplo 1: Com as afirmações a seguir, vamos mostrar se é teorema ou não. Para isto, sejam as hipóteses:

  • $H_1$: tempo é dinheiro.
  • $H_2$: vagabundo tem muito tempo.

E a tese:

  • $T$: vagabundo tem muito dinheiro.

Será que a proposição $H_1 \wedge H_2 \Rightarrow T$ é um teorema?

Suponhamos:

  • $p$: “ter tempo”.
  • $q$: “ter dinheiro”.
  • $r$: “ser vagabundo”.

Com:

  • $H_1$: $p\wedge q$ (ter tempo e ter dinheiro).
  • $H_2$: $q\rightarrow r$ (ter dinheiro implica em ser vagabundo).
  • $T$: $r\rightarrow q$ (ser vagabundo implica ter dinheiro).

Com isso, podemos escrever a proposição:

$$H_1 \wedge H_2 \Rightarrow T$$

Hipótese 1 e hipótese 2 implica em Tese.

Como vale a tautologia:

$$(p\rightarrow q)\wedge (r \rightarrow p) \Rightarrow (r \rightarrow q)$$

(ter tempo implica ter dinheiro) e (ser vagabundo implica ter tempo) implica em (ser vagabundo implica ter dinheiro).

Portanto, a proposição dada é um teorema.

Do ponto de vista prático pode não fazer sentido este resultado, mas dependendo das afirmações utilizadas, podemos chegar a um absurdo.

Exemplo 2: Com as afirmações a seguir, vamos mostrar se é teorema ou não. Para isto, sejam as hipóteses:

  • $H_1$: penso, logo existo.
  • $H_2$: pedras não pensam.

E a tese:

  • $T$: pedras não existem.

Será que a proposição $H_1 \wedge H_2 \Rightarrow T$ é um teorema?

Suponhamos:

  • $p$: “pensar”.
  • $q$: “existir”.

Com:

  • $H_1$: $p\rightarrow q$ (pensar implica em existir).
  • $H_2$: $\sim p$ (não pensar).
  • $T$: $\sim q$ (não existir).

Com isso, podemos escrever a proposição:

$$H_1 \wedge H_2 \Rightarrow T$$

Hipótese 1 e hipótese 2 implica em Tese.

Como não é um tautologia:

$$(p\rightarrow q)\wedge (\sim p) \Rightarrow (\sim q)$$

(pensar implica em existir) e (não pensar) implica em (não existir).

Portanto, a proposição dada não é um teorema.

Este último resultado nem sequer é um resultado, pois nem é teorema. Com isso, o absurdo é natural.

Métodos de Demonstração

Nesta seção, vamos mostrar como demonstrar um teorema $p\Rightarrow q$. Boa parte das demonstrações de resultados caem em um dos trê métodos a seguir:

  • Método Direto.
  • Método por Contraposição.
  • Método por Contradição (Reduction ad absurdum).

Método Direto

Este método é obtido do método dedutivo, com a suposição da proposição $p$ ser verdadeira e a consequência, a proposição $q$ é uma equivalência lógica. Logo, o objetivo é deduzirmos que $q$ é verdadeira.

Exemplo 3: Se $x$ é um número inteiro par, então $x^2$ é um número inteiro par.

Demonstação:

Para construção deste resultado, assumimos a proposição $p$ verdadeira, isto é, $x$ é um número inteiro par.

Como consequência, temos que $x$ é divisível por 2 (ver post de números pares).

Por definição, $x$ é múltiplo de 2.

Logo, existe $n\in \mathbb{Z}$ tal que $x = 2n$.

Ao elevarmos ao quadrado os dois lados da igualdade, temos:

$$x^2 = (2n)^2 = 4n^2 = 2(2n^2)=2m, \qquad \text{para algum } m\in \mathbb{Z}$$

Portanto, $x^2$ é um número inteiro par.

$\square$

Método por Contraposição

O método por contraposição é obtido com a equivalência lógica:

$$p \rightarrow q \Longleftrightarrow ~ \sim q \rightarrow \sim p$$

Mais especificamente, para demonstrarmos o teorema:

$$p \Rightarrow q$$

Basta, demonstrarmos pelo método direto:

$$\sim q \Rightarrow \sim p$$

Exemplo 4: Se $x$ é um número inteiro tal que $x^2$ é ímpar, então $x$ é um número inteiro ímpar.

Demonstação:

Sejam $p$ e $q$ as proposições:

  • $p$: $x^2$ é um número inteiro ímpar.
  • $q$: $x$ é um número inteiro ímpar.

e queremos provar a implicação do $p \Rightarrow q$. Neste caso, o método direto não se aplica, pois ao supormos que $x^2$ é um número inteiro ímpar, existe $n\in \mathbb{Z}$ tal que $x^2 = 2n+1$.

Com isso, não podemos deduzir que existe um $m\in \mathbb{Z}$ tal que $x = 2m+1$.

Ao invés disso, vamos usar a equivalência lógica.

Suponhamos a proposição $\sim q: $ $x$ não é ímpar verdadeira, ou seja, $x$ é par.

Do exemplo do método direto, temos que este resultado implica em $\sim p:$ $x^2$ não é ímpar, ou seja, $x^2$ é par.

Portanto, $p \Rightarrow q$.

$\square$

Método por Contradição

O método por contrdição é obtido com a equivalência lógica:

$$p \rightarrow q \Longleftrightarrow ~ (p \wedge \sim q) \rightarrow \sim p$$

Mais especificamente, para demonstrarmos o teorema:

$$p \Rightarrow q$$

Basta, demonstrarmos:

$$(p \wedge \sim q) \rightarrow \sim p$$

e chegamos em um absurdo, pois se $p$ é verdadeira e concluímos que $\sim p$ é também verdadeira. Neste caso chegamos a um resultado

$$p \wedge \sim p$$

verdadeiro, que é um contradição.

Exemplo 5: Se $x$ é um número inteiro tal que $x^2$ é par, então $x$ é um número inteiro par.

Demonstação:

Sejam $p$ e $q$ as proposições:

  • $p$: $x^2$ é um número inteiro par.
  • $q$: $x$ é um número inteiro par.

e queremos provar a implicação do $p \Rightarrow q$.

Pelo método direto, assumimos que $(p \wedge \sim q)$ é verdadeira, ou seja,

  • $x^2$ é número inteiro par.
  • $x$ é número inteiro ímpar.

Disto, obtemos que $x=2n+1$ para algum $n \in \mathbb{Z}$.

Ao elevarmos ao quadrado os dois lados da igualdade, temos:

$$x^2 = (2n+1)^2 = 4n^2 + 4n + 1 = 2(2n^2 + 2n) + 1 = 2m+1$$

para algum $m\in \mathbb{Z}$

Isto implica $\Longrightarrow$ que $x^2$ é um número inteiro ímpar ($\sim p$). Portanto, chegamos a um absurdo, pois supomos $x^2$ par.

Desta forma, resumimos algumas técnicas para demosntração de resultados.