Poder e informação

FESURV – UNIVERSIDADE DE RIO VERDE

FACULDADE DE CIÊNCIAS DA COMPUTAÇÃO

PODER E INFORMAÇÃO

SAMUEL DE MORAES LEMES

Orientador: Prof. ROBERTO LAURO TAMBASCO JÚNIOR

RIO VERDE - GOIÁS

MARÇO - 2008

RESUMO

LEMES, Samuel de Moraes. Poder e Informação. 2008. f. Resumo: Informática e Sociedade – Fesurv-Universidade de Rio Verde, Rio Verde, 2008.

[pic 1]

Prova por teorema

Definições:

• Axiomas ou postulados: são afirmações consideradas verdadeiras e usadas como hipóteses.
• Lemas: São teoremas menos importantes e usados na prova de outros teoremas.
• Teorema: é uma sentença que pode ser mostrada ser verdadeira.
• Corolário: é um teorema que pode ser estabelecido diretamente de outro teorema.
• Conjectura: é uma proposição que está se propondo ser verdadeira.

Exemplo de Teorema:

Se x>y, onde x e y são número reais positivos, então[pic 2][pic 3] > [pic 4][pic 5], que equivale, a, para todo real positivo x e y, se x > y então [pic 6][pic 7] > [pic 8][pic 9].

Usualmente, usa-se a lei de instanciação  universal, ou seja, escolhe um elemento do domínio, sem explicitamente mencionar seu uso e, posteriormente, a generalização universal é aplicada implicitamente para mostrar que o teorema vale para todos os elementos do domínio.

Prova Direta: supõe-se que P(x) é verdadeiro e usando-se axiomas e regras de inferências, chega-se à conclusão que Q(x) também deve ser verdadeiro.

Paridade: um inteiro par N é par se existir um inteiro K tal que N=2K e N é impar se existir um inteiro K tal que N=2K+1.

Prova por Contraposição:

É um método de prova indireto que usa o fato de que p ---> q é logicamente equivalente a ~p ---> ~q.

Exemplo:

Prove que se n é um inteiro e 3n + 2 é ímpar então n é ímpar.

Solução - primeira tentativa Tente demonstrar o teorema por prova direta.

Solução - segunda tentativa Assuma que n não é ımpar. Por definição de número par temos que n = 2k para algum inteiro k. Logo, 3n + 2 = 3(2k) + 2 = 6k + 2 = 2(3k + 1) e, portanto, 3n + 2 não é ımpar, o que finaliza a demonstração.

Prova por Vacuosidade: uma vez que p ---> q é verdadeiro sempre p é falso, uma forma de provar um teorema da forma p ---> q é demostrar que p é falso.

Exemplo:

 Mostre que P(0) é verdadeiro onde P(n) é “Se n > 1 então [pic 10][pic 11] > n” e o domínio é o conjunto dos inteiros.

 Solução Note que P(0) ´e “Se 0 > 1 então [pic 12][pic 13]> 0”. Podemos mostrar P(0) usando a prova por vacuosidade, pois a hipótese 0 > 1 é falsa. Logo, automaticamente, P(0) é verdadeiro.

Note que a conclusão não é usada neste tipo de prova!