ProvasFormais
52 pág.

ProvasFormais


DisciplinaTeoria da Computação567 materiais16.774 seguidores
Pré-visualização3 páginas
conjunto 
\ud835\udc48, então \ud835\udc47 é o complemento de \ud835\udc46 (com 
relação a U) se \ud835\udc46 \u222a \ud835\udc47 = \ud835\udc48 \ud835\udc52 \ud835\udc46 \u2229 \ud835\udc47 =\u2298 
21 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Prova por Contradição: Exemplo 
\uf0a7 Teorema 3: Seja \ud835\udc46 um subconjunto finito de 
algum conjunto infinito \ud835\udc48. Seja \ud835\udc47 o 
complemento de S com relaçãop a \ud835\udc48. Então 
\ud835\udc47 é infinito 
\uf0a7 Exercício: Prove por contradição 
22 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Prova por Contradição: Exemplo 
\uf0a7 Prova (Teorema 3): Temos que \ud835\udc46 \u222a \ud835\udc47 = \ud835\udc48 e 
\ud835\udc46 \u2229 \ud835\udc47 =\u2298, portanto \u2225 \ud835\udc46 \u2225 + \u2225 \ud835\udc47 \u2225=\u2225 \ud835\udc48 \u2225. 
Como S é finito, então \u2225 \ud835\udc46 \u2225=n para algum 
inteiro n e como U é infinito não existe um 
inteiro \ud835\udc5d tal que \u2225 \ud835\udc48 \u2225= \ud835\udc5d. Vamos assumir que 
T é finito, isto é, \u2225 \ud835\udc47 \u2225=m para algum inteiro 
m. Então\u2225 \ud835\udc48 \u2225=\u2225 \ud835\udc46 \u2225 + \u2225 \ud835\udc47 \u2225= \ud835\udc5b +\ud835\udc5a, o que 
contradiz a afirmação de que U é infinito 
23 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Contraexemplo 
\uf0a7 Teoremas são geralmente enunciados a respeito 
de um número infinito de casos 
\u2022 Por exemplo, todos os valores de um ou mais 
parâmetros 
\uf0a7 Portanto, para provar que um teorema é inválido, 
basta mostrar um único caso onde o enunciado 
seja falso 
\uf0a7 Exemplo: Todos números primos são ímpares 
\u2022 Contraexemplo: O inteiro 2 é um primo e, no entanto, 
é par 
 
24 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Prova por Construção 
\uf0a7 Muitos teoremas afirmam que um particular tipo 
de objeto existe 
\uf0a7 A prova consiste em demonstrar como construir 
este objeto 
\uf0a7 Este tipo de prova é frequentemente utilizada 
para demonstrar que modelos computacionais 
são equivalentes 
\u2022 Mostramos como construir um elemento qualquer de 
modelo a partir de um elemento qualquer do outro 
modelo 
25 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Prova por Construção: Exemplo 
\uf0a7 Teorema 4: Para cada número para \ud835\udc5b maior 
que 2, existe um grafo 3-regular (grafo cúbico) 
com \ud835\udc5b vértices 
\u2022 Um grafo é k-regular se todos os vértices possuem 
grau k 
26 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Prova por Construção: Exemplo 
\uf0a7 Prova (Intuição): Imagine os vértices de um grafo 
distribuídos ao longo de um círculo. Conecte todos os 
vértices adjacentes com uma aresta (1). Teremos um 
grafo 2-regular. Conecte então todos os vértices 
opostos entre si com uma aresta (2). Teremos um grafo 
3-regular 
 
27 
1) 2) 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Prova por Construção: Exemplo 
\uf0a7 Prova (Formal): Seja n um número par maior 
que 2. Construa um grafo 3-regular \ud835\udc3a = (\ud835\udc49, \ud835\udc38) 
com \ud835\udc5b vértices da seguinte maneira: 
\u2022 Conjunto de vértices de \ud835\udc3a é o conjunto \ud835\udc49 =
1,\u2026 , \ud835\udc5b 
\u2022 Conjunto de arestas de G é o conjunto 
\ud835\udc38 = \ud835\udc56, \ud835\udc56 + 1 | \ud835\udc5d\ud835\udc4e\ud835\udc5f\ud835\udc4e 1 \u2264 \ud835\udc56 \u2264 \ud835\udc5b \u2212 1 \u22c3 \ud835\udc5b, 1 \u22c3 
 \ud835\udc56, \ud835\udc56 + \ud835\udc5b/2 | \ud835\udc5d\ud835\udc4e\ud835\udc5f\ud835\udc4e 0 \u2264 \ud835\udc56 \u2264 \ud835\udc5b/2 
28 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
 Método de Diagonalização 
\uf0a7 Diversas provas em Teoria 
da Computação usam a 
técnica de diagonalização 
criada pelo matemático 
Georg Cantor em 1873 
\uf0a7 Técnica usada para medir 
o tamanho de conjuntos 
infinitos 
29 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Método de Diagonalização 
\uf0a7 Como determinar se dois conjuntos inifinitos 
possuem o mesmo tamanho? 
\uf0a7 Por exemplo, o conjunto de todos inteiros e o 
conjunto de todas palavras formadas pelo 
alfabeto \u2211= *a, b+ possuem o mesmo 
tamanho 
\uf0a7 Método de contagem utilizado para conjuntos 
finitos obviamente não funciona 
30 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Intuição 
\uf0a7 Dois conjuntos finitos possuem o mesmo tamanho se 
é possível estabelecer uma correspôndencia um-
para-um (1-1) entre entre os elementos de dois 
conjuntos, isto é, uma função bijetiva 
31 
A 
 
C 
D 
E 
F 
A 
B 
C 
D 
 
F 
A 
B 
C 
D 
E 
F 
Injetora Sobrejetora Bijetora 
\uf0a7 Vamos aplicar esta idéia para conjuntos infinitos 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 1 
\uf0a7 Seja \u2115 = *1,2,3+ o conjunto de números 
naturais (sem o zero) e \ud835\udc43 = *2, 4, 6+ o 
conjunto de números naturais pares 
\uf0a7 Ambos conjuntos são infinitos 
\uf0a7 |\ud835\udc43| = \u2115 ? 
32 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 1 (2) 
\uf0a7 |\ud835\udc43| = \u2115 ? Sim! 
\uf0a7 A correpôndencia 1-1 é dada pela função 
\ud835\udc53 \ud835\udc5b = 2\ud835\udc5b 
33 
n f(n) 
1 2 
2 4 
3 6 
n 2n 
\uf0a7 Mesmo que \ud835\udc5b extenda-se 
ao infinito, sempre 
teremos um elemento 
correspondente \ud835\udc53(\ud835\udc5b) 
\uf0a7 A noção de \u201ctamanho\u201d é 
claramente diferente 
para conjuntos infinitos... 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Definições 
\uf0a7 Definição 1: Um conjunto é infinito se o mesmo 
possui subconjunto próprio com o mesmo 
tamanho 
\u2022 \u2115 = \ud835\udc5d \ud835\udc5d \u2208 \u2115 \ud835\udc52 \ud835\udc5d é \ud835\udc5d\ud835\udc4e\ud835\udc5f | 
\u2022 \u2115 = \ud835\udc5d \ud835\udc5d \u2208 \u2115 \ud835\udc52 \ud835\udc5d é \ud835\udc56\ud835\udc5a\ud835\udc5d\ud835\udc4e\ud835\udc5f | 
\u2022 \u2115 = |\u2115 \u2212 1 | 
\uf0a7 Definição 2: \u2115 é infinito e contável (ou 
enumerável) 
\uf0a7 Definição 3: Um conjunto é contável se o mesmo 
é finito ou possui o mesmo tamanho que \u2115 
34 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 2 
\uf0a7 Considere o conjunto dos números racionais 
positivos \u211a =
\ud835\udc5a
\ud835\udc5b
|\ud835\udc5a \ud835\udc52 \ud835\udc5b \u2208 \u2115 
\uf0a7 O conjunto \u211a é infinito 
\uf0a7 \u211a = \u2115 ? 
\u2022 Em outras palavras, o conjunto \u211a é enumerável? 
 
35 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 2 (2) 
\uf0a7 \u211a = \u2115 ? Sim! 
\uf0a7 Para provar que \u211a e \u2115 tem o mesmo tamanho 
precisamos \u201capenas\u201c listar todos elementos 
de \u211a e estabelecer uma correspondência 1-1 
com os elementos de \u2115 
\uf0a7 Como poderiamos listar os elementos de \u211a ? 
36 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 2 (3) 
\uf0a7 Construímos uma matriz infinita contendo 
todos números racionais positivos. 
\u2022 A \ud835\udc56th linha contém todos racionais com 
numerador igual a \ud835\udc56 e a \ud835\udc57th coluna contém todos 
racionais com denominador \ud835\udc57 
\u2022 O racional 
\ud835\udc56
\ud835\udc57
 ocorre na \ud835\udc56th linha e na \ud835\udc57th coluna 
37 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 2 (4) 
38 
1
1
 
1
2
 
1
3
 
1
4
 
1
5
 
\u2026 
2
1
 
2
2
 
2
3
 
2
4
 
2
5
 
\u2026 
3
1
 
3
2
 
3
3
 
3
4
 
3
5
 
\u2026 
4
1
 
4
2
 
4
3
 
4
4
 
4
5
 
\u2026 
5
1
 
5
2
 
5
3
 
5
4
 
5
5
 
\u2026 
\u2026 \u2026 \u2026 \u2026 \u2026 \u2026 
1 
2 
3 
4 
5 
\u2026 
1 2 3 4 5 \u2026 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo (5) 
\uf0a7 Como converter esta matriz em uma lista (que 
será usada posteriormente para estabelecer a 
correspondência 1-1 com \u2115) 
\uf0a7 Se considermarmos os elementos linha por 
linha, jamais chegaremos até a segunda linha 
(comprimento da linha é infinito) 
\uf0a7 Vamos proceder na diagonal 
39 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 2 (6) 
40 
1
1
 
1
2
 
1
3
 
1
4
 
1
5
 
\u2026 
2
1
 
2
2
 
2
3
 
2
4
 
2
5
 
\u2026 
3
1
 
3
2
 
3
3
 
3
4
 
3
5
 
\u2026 
4
1
 
4
2
 
4
3
 
4
4
 
4
5
 
\u2026 
5
1
 
5
2
 
5
3
 
5
4
 
5
5
 
\u2026 
\u2026 \u2026 \u2026 \u2026 \u2026 \u2026 
1 
2 
3 
4 
5 
\u2026 
1 2 3 4 5 \u2026 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 2 (7) 
41 
1
1
 
1
2
 
1
3
 
1
4
 
1
5
 
\u2026 
2
1
 
2
2
 
2
3
 
2
4
 
2
5
 
\u2026 
3
1
 
3
2
 
3
3
 
3
4
 
3
5
 
\u2026 
4
1
 
4
2
 
4
3
 
4
4
 
4
5
 
\u2026 
5
1
 
5
2
 
5
3
 
5
4
 
5
5
 
\u2026 
\u2026 \u2026 \u2026 \u2026 \u2026 \u2026 
1 
2 
3 
4 
5 
\u2026 
1 2 3 4 5 \u2026 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 2 (8) 
42 
1
1
 
1
2
 
1
3
 
1
4
 
1
5
 
\u2026 
2
1
 
2
2
 
2
3
 
2
4
 
2
5
 
\u2026 
3
1
 
3
2
 
3
3
 
3
4
 
3
5
 
\u2026 
4
1
 
4
2
 
4
3
 
4
4
 
4
5
 
\u2026 
5
1
 
5
2
 
5
3
 
5
4
 
5
5
 
\u2026 
\u2026 \u2026 \u2026 \u2026 \u2026 \u2026 
1 
2 
3 
4 
5 
\u2026 
1 2 3 4 5 \u2026 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 2 (9) 
43 
1
1
 
1
2
 
1
3
 
1
4
 
1
5
 
\u2026 
2
1
 
2
2
 
2
3
 
2
4
 
2
5
 
\u2026 
3
1
 
3
2
 
3
3
 
3
4
 
3
5
 
\u2026 
4
1
 
4
2
 
4
3
 
4
4
 
4
5
 
\u2026 
5
1
 
5
2
 
5
3
 
5
4
 
5
5
 
\u2026 
\u2026 \u2026 \u2026 \u2026 \u2026 \u2026 
1 
2 
3 
4 
5 
\u2026 
1 2 3 4 5 \u2026 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 2 (10) 
\uf0a7 Note que 
1
1
=
2
2
 
\uf0a7 Durante a construção da lista temos que 
desconsiderar elementos repetidos 
\uf0a7 Finalmente, desta forma, podemos enumerar 
todos elementos de \u211a e estabelecer uma 
correspondência um-para-um com \u2115 
44 
Prof. Dr.-Ing. Leonardo Andrade Ribeiro 
Exemplo 3 (1) 
\uf0a7 Considere o conjunto dos números reais \u211d 
\u2022 \ud835\udf0b = 3.14155926\u2026