ProvasFormais
52 pág.

ProvasFormais


DisciplinaTeoria da Computação545 materiais16.685 seguidores
Pré-visualização3 páginas
Teoria da Computação 
Revisão de Provas Formais 
Versão dos Slides: 0.7 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
 
 
 
DCC-UFLA, Lavras 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Conceitos Básicos 
\uf0a7 Definições descrevem os objetos e noções usadas 
em uma determinada abstração 
\uf0a7 Postulados matemáticos são feitos a respeito 
destes objetos 
\uf0a7 Uma prova é um argumento lógico convincente 
de que um postulado é verdadeiro 
\u2022 Informalmente, o principal objetivo de uma prova é 
convencer alguém. Por exemplo, um colega, um 
revisor, o professor... 
2 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Conceitos Básicos 
\uf0a7 Um teorema é um postulado matemático 
provado como verdadeiro 
\u2022 Um postulado sem prova é uma conjectura 
\uf0a7 Normalmente, teoremas são associados com 
postulados de interesse especial e aplicam-se 
a um conjunto infinito de casos 
\uf0a7 Se um postulado aplica-se a apenas alguns 
casos específicos, dizemos que o mesmo se 
trata de uma observação 
3 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Conceitos Básicos 
\uf0a7 Ocasionalmente, postulados são provados 
apenas para assistir na prova de outro 
postulado mais importante. Estes postulados 
são chamados lemas 
\uf0a7 Ocasionalmente, um teorema, ou a prova do 
mesmo, permite a conclusão direta de que 
outros postulados relacionados também são 
verdadeiros; estes postulados são 
chamadados corolários 
4 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Provas Formais 
\uf0a7 Existem dois tipo básicos de provas formais: 
\u2022 Provas por dedução 
\u2022 Provas por indução 
\uf0a7 Aqui, estudaremos provas por dedução; 
provas por indução serão vistas juntamente 
com o material sobre funções recursivas 
5 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Provas por Dedução 
\uf0a7 Uma prova por dedução consiste em uma 
sequência de postulados cuja verdade nos 
leva de um postulado inicial, chamado 
hipótese, até uma conclusão 
\uf0a7 Cada passo da prova deve obtido usando 
princípios lógicos reconhecidos e a partir de 
fatos assumidos no enunciado, postulados 
prévios e outros teoremas 
6 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Teoremas Provados por Dedução 
\uf0a7 Teoremas provados por dedução possuem, 
geralmente, o seguinte enunciado: 
\u2022 Se H então C 
\u2022 Dizemos que C é deduzido de H 
\uf0a7 Em lógica, dizemos que H implica em C 
\u2022 \ud835\udc3b \u2192 \ud835\udc36 
\uf0a7 Inferência Modus Ponens: Dado H, podemos 
inferir C 
7 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Teoremas Provados por Dedução 
\uf0a7 Em alguns teoremas, o formato \u201cSe H, então C\u201d 
não é apresentado de maneira implícita 
\u2022 Exemplo: \ud835\udc60\ud835\udc56\ud835\udc5b2\ud835\udf03 + \ud835\udc50\ud835\udc5c\ud835\udc602\ud835\udf03 = 1 
\u2022 Leia-se: Se \ud835\udf03 é um ângulo, então \ud835\udc60\ud835\udc56\ud835\udc5b2\ud835\udf03 + \ud835\udc50\ud835\udc5c\ud835\udc602\ud835\udf03 = 1 
\uf0a7 Outros formatos: 
\u2022 \ud835\udc3b implica \ud835\udc36 
\u2022 \ud835\udc3b apenas se \ud835\udc36 
\u2022 \ud835\udc36 se \ud835\udc3b 
\u2022 Sempre que \ud835\udc3b é verdadeiro, \ud835\udc36 também é 
\u2022 ... 
 
8 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 
\uf0a7 Teorema 1: Se x é um inte\ud835\udc56\ud835\udc5f\ud835\udc5c \ud835\udc52 \ud835\udc65 \u2265
4, \ud835\udc52\ud835\udc5b\ud835\udc61ã\ud835\udc5c 2\ud835\udc65 \u2265 \ud835\udc652 
\uf0a7 Prova (informal) 
1. Para \ud835\udc65 = 4, temos que a Conclusão é verdadeira, 
isto é, 24 = 42 = 16 
2. Para \ud835\udc65 > 4, temos que o lado esquerdo da 
Conclusão, 2\ud835\udc65, dobra de valor cada vez que \ud835\udc65 é 
incrementado por 1 
3. Para \ud835\udc65 > 4, o valor do lado direito da Conclusão, 
\ud835\udc652, cresce a uma razão de (\ud835\udc65 + 1) \ud835\udc65 2 
 9 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo (2) 
4. Temos que, se \ud835\udc65 \u2265 4, então (\ud835\udc65 + 1) \ud835\udc65 \u2264 1.25 e, 
portanto, (\ud835\udc65 + 1) \ud835\udc65 2 \u2264 1.5625 
5. Como 1.5625 < 2, cada vez que \ud835\udc65 aumenta de 
valor acima de 4, o valor do lado esquerdo da 
Conclusão, 2\ud835\udc65, cresce mais que o valor do lado 
direito, \ud835\udc652 
6. Portanto, iniciando-se de \ud835\udc65 = 4, onde 2\ud835\udc65 \u2265 \ud835\udc652 é 
satisfeita, nós podemos incrementar 
\ud835\udc65 arbitrariamente que e a inequalidade 
continuára sendo satisfeita 
10 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercício 
\uf0a7 Prove por dedução o seguinte teorema: 
\u2022 Teorema 2: Se x é a soma dos quadrados de 4 
inteiros positivos, então 2\ud835\udc65 \u2265 \ud835\udc652 
\uf0a7 Dica: 
\u2022 Use Teorema 1 que já foi provado 
\u2022 Observe que Teorema 1 e Teorema 2 possuem a 
mesma Conclusão 
11 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exercício (2) 
12 
Passo Justificativa 
1 \ud835\udc65 = \ud835\udc4e2 + \ud835\udc4f2 + \ud835\udc502 + \ud835\udc512 Dado pela hipótese 
2 \ud835\udc4e \u2265 1; \ud835\udc4f \u2265 1; \ud835\udc50 \u2265 1; \ud835\udc51 \u2265 1 Dado pela hipótese 
3 \ud835\udc4e2 \u2265 1; \ud835\udc4f2 \u2265 1; 
 \ud835\udc502 \u2265 1; \ud835\udc512 \u2265 1 
(2) e propriedades da aritmética 
4 \ud835\udc65 \u2265 4 (1), (3) e propriedades da 
aritmética 
5 2\ud835\udc65 \u2265 \ud835\udc652 (4) e Teorema 1 
 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Teoremas \u201cSe e Somente Se\u201d 
\uf0a7 Corresponde a duas implicações: 
\u2022 \ud835\udc3b \u2192 \ud835\udc36: Parte \u201cSe\u201c ou Se 
\u2022 \ud835\udc36 \u2192 \ud835\udc3b: Parte \u201cSomente se\u201c 
\uf0a7 Corresponde a equivalência 
\u2022 \ud835\udc3b \u2194 \ud835\udc36 
\uf0a7 Requer duas provas, uma para cada parte 
 
13 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Provando a 
Equivalência de Conjuntos 
\uf0a7 Seja \ud835\udc38 e \ud835\udc39 dois conjuntos, possivelmente 
contruídos de maneira diferente, provar que 
\ud835\udc38 = \ud835\udc39 
\u2022 Todo elemento em \ud835\udc38 também está em \ud835\udc39 e todo 
elemento em \ud835\udc39 também esta em \ud835\udc38 
\uf0a7 Igualdade de conjuntos pode ser descrita como 
um enunciado Sse. Desta a forma, a prova terá 
duas partes: 
\u2022 Provar que se \ud835\udc65 está em \ud835\udc38, então \ud835\udc65 está em \ud835\udc39 
\u2022 Provar que se \ud835\udc65 está em \ud835\udc39, então \ud835\udc65 está em \ud835\udc38 
 
14 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Prova sobre Conjuntos: Exemplo 
\uf0a7 Teorema (Lei Distributiva da União sobre 
Intersecção): \ud835\udc45 \u222a \ud835\udc46\u22c2\ud835\udc47 = \ud835\udc45 \u222a \ud835\udc46 \u2229
\ud835\udc45 \u222a \ud835\udc47 . 
\uf0a7 Prova (Intuição): Temos \ud835\udc38 = \ud835\udc45 \u222a \ud835\udc46\u22c2\ud835\udc47 e 
\ud835\udc39 = \ud835\udc45 \u222a \ud835\udc46 \u2229 \ud835\udc45 \u222a \ud835\udc47 
\u2022 Parte \u201cSe\u201d: \ud835\udc65 \u2208 \ud835\udc38 \u2192 \ud835\udc65 \u2208 \ud835\udc39 
\u2022 Parte \u201cSs\u201d: \ud835\udc65 \u2208 \ud835\udc39 \u2192 \ud835\udc65 \u2208 \ud835\udc38 
15 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Prova sobre Conjuntos: Parte \u201cSe\u201d 
16 
Passo Justificativa 
1 \ud835\udc65 \ud835\udc52\ud835\udc60\ud835\udc61á \ud835\udc52\ud835\udc5a \ud835\udc45\u22c3 \ud835\udc46\u22c2\ud835\udc47 Dado pela hipótese 
2 \ud835\udc65 \ud835\udc52\ud835\udc60\ud835\udc61á \ud835\udc52\ud835\udc5a \ud835\udc45 \ud835\udc5c\ud835\udc62 \ud835\udc65 \ud835\udc52\ud835\udc60\ud835\udc61á \ud835\udc52\ud835\udc5a \ud835\udc46\u22c2\ud835\udc47 (1) e definição de união 
3 \ud835\udc65 \ud835\udc52\ud835\udc60\ud835\udc61á \ud835\udc52\ud835\udc5a \ud835\udc45 \ud835\udc5c\ud835\udc62 \ud835\udc65 \ud835\udc52\ud835\udc60\ud835\udc61á \ud835\udc52\ud835\udc5a 
\ud835\udc46 \ud835\udc52 \ud835\udc52\ud835\udc5a \ud835\udc47 
(2) e definição de interseção 
4 \ud835\udc65 \ud835\udc52\ud835\udc60\ud835\udc61á \ud835\udc52\ud835\udc5a \ud835\udc45\u22c3S (3) e definição de união 
5 \ud835\udc65 \ud835\udc52\ud835\udc60\ud835\udc61á \ud835\udc52\ud835\udc5a \ud835\udc45\u22c3T (3) e definição de união 
 
6 \ud835\udc65 \ud835\udc52\ud835\udc60\ud835\udc61á \ud835\udc52\ud835\udc5a \ud835\udc45 \u222a \ud835\udc46 \u2229 \ud835\udc45 \u222a \ud835\udc47 
 
(4), (5) e definição de 
interseção 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Prova sobre Conjuntos: Parte \u201cSs\u201d 
17 
Passo Justificativa 
1 \ud835\udc65 \ud835\udc52\ud835\udc60\ud835\udc61á \ud835\udc52\ud835\udc5a \ud835\udc45 \u222a \ud835\udc46 \u2229 \ud835\udc45 \u222a \ud835\udc47 Dado pela hipótese 
2 \ud835\udc65 \ud835\udc52\ud835\udc60\ud835\udc61á \ud835\udc52\ud835\udc5a \ud835\udc45 \u222a \ud835\udc46 (1) e definição de interseção 
3 \ud835\udc65 \ud835\udc52\ud835\udc60\ud835\udc61á \ud835\udc52\ud835\udc5a \ud835\udc45 \u222a \ud835\udc47 (1) e definição de interseção 
4 \ud835\udc65 \ud835\udc52\ud835\udc60\ud835\udc61á \ud835\udc52\ud835\udc5a \ud835\udc45 \ud835\udc5c\ud835\udc62 \ud835\udc65 \ud835\udc52\ud835\udc60\ud835\udc61á \ud835\udc52\ud835\udc5a 
\ud835\udc46 \ud835\udc52 \ud835\udc52\ud835\udc5a \ud835\udc47 
(2), (3) e inferência sobre 
união 
5 \ud835\udc65 \ud835\udc52\ud835\udc60\ud835\udc61á \ud835\udc52\ud835\udc5a \ud835\udc45 \ud835\udc5c\ud835\udc62 \ud835\udc65 \ud835\udc52\ud835\udc60\ud835\udc61á \ud835\udc52\ud835\udc5a \ud835\udc46\u22c2\ud835\udc47 (4) e definição de interseção 
6 \ud835\udc65 \ud835\udc52\ud835\udc60\ud835\udc61á \ud835\udc52\ud835\udc5a \ud835\udc45\u22c3 \ud835\udc46\u22c2\ud835\udc47 
 
(4), (5) e definição de união 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Prova por Contraposição 
\uf0a7 Toda enunciado \u201cse H então C\u201d tem uma forma 
equivalente \u201cse não C, então não H\u201d 
\uf0a7 Chamado de contrapositivo do enunciado \u201cse-
então\u201d 
\uf0a7 Baseada na seguinte equivalência lógica: 
\u2022 \ud835\udc3b \u2192 \ud835\udc36 \u27f7 \u2266\ud835\udc36 \u2192 \u2266\ud835\udc3b 
\uf0a7 Em algumas circunstâncias, o contrapositivo é 
mais fácil de ser provado 
\uf0a7 A regra de inferência relacionada é chamada de 
Modus Tollens 
18 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Prova por Contraposição: Exemplo 
\uf0a7 Se \ud835\udc65 \u2265 4, então 2\ud835\udc65 \u2265 \ud835\udc652 
\uf0a7 Contrapositivo: Se 2\ud835\udc65 < \ud835\udc652 \ud835\udc52\ud835\udc5b\ud835\udc61ã\ud835\udc5c \ud835\udc65 < 4 
\uf0a7 Note que em enunciados \u201cSse\u201d podemos usar 
prova por contradição em apenas uma das 
partes, isto é, apenas na parte \u201cSe\u201d ou apenas 
na parte \u201cSs\u201d 
\u2022 Se \ud835\udc65 \u2208 \ud835\udc38 \u2192 \ud835\udc65 \u2208 \ud835\udc39 (Parte \u201cSe\u201d) 
\u2022 \ud835\udc46\ud835\udc52 \ud835\udc65 \u2209 \ud835\udc39 \u2192 \ud835\udc65 \u2209 \ud835\udc38 (Contraposição da parte \u201cSs\u201d) 
 
 
19 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Prova por Contradição 
\uf0a7 Outra maneira de provar que \ud835\udc3b \u2192 \ud835\udc36 é provar 
que \ud835\udc3b \u2192 \u2266\ud835\udc36 não pode ser satisfeito, isto é, 
\ud835\udc3b \u2192 \u2266\ud835\udc36 é falso em todos os casos 
\uf0a7 A prova demonstra que algo 
reconhecidamente falso pode deduzido de 
\ud835\udc3b \u2192 \u2266\ud835\udc36 
\u2022 Exemplo: P \u2266P 
\uf0a7 Também conhecida como redução ao absurdo 
20 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Prova por Contradição: Exemplo 
\uf0a7 Temos as seguintes definições: 
\u2022 Um conjunto \ud835\udc46 é finito se existe um inteiro \ud835\udc5b tal 
que \ud835\udc46 possui exatamente n elementos, isto é, 
\u2225 \ud835\udc46 \u2225= n, onde \u2225 \ud835\udc46 \u2225 denota número de 
elementos em S (cardinalidade). Se \ud835\udc46 não é finito, 
então \ud835\udc46 é infinito (mais sobre conjuntos infinitos 
mais adiante). 
\uf0a7 Se \ud835\udc46 e \ud835\udc47 são subconjuntos de algum