unicamp metodos-de-prova

Prévia do material em texto

MC405 – Teoria dos Grafos
MC878 – Teoria e Aplicac¸o˜es de Grafos
Orlando Lee
Resumo
Na disciplina MO405/MC878 veremos va´rios teoremas e
provas/demonstrac¸o˜es desses. Este texto e´ um pequeno resumo
descrevendo algumas te´cnicas de prova/demonstrac¸a˜o. Ele na˜o
pretende ser abrangente muito menos completo. Suporemos que
o leitor esteja familiarizado com os seguintes conceitos: conjuntos,
func¸o˜es, nu´meros (inteiros, racionais, reais), lo´gica proposicional etc.
Tudo isto e muito mais podem ser encontrados em
K. H. Rosen, Discrete Mathematics and its applications,
McGraw-Hill, 2003.
Se voceˆ na˜o possui familiaridade com esses conceitos, eu recomendo
fortemente (e urgentemente) que voceˆ leia pelo menos o Cap´ıtulo 1
desse livro.
1 Teoremas e demonstrac¸o˜es
Na disciplina MO405/MC878 veremos va´rios teoremas e
provas/demonstrac¸o˜es desses. Algumas provas sera˜o omitidas por
serem complexas, mas de modo geral, um teorema que se preze possui uma
prova.
Um teorema e´ uma afirmac¸a˜o ou sentenc¸a que pode ser
provada/demonstrada (veja abaixo). Teorema e´ um nome chique
para proposic¸a˜o, fato ou resultado. Um lema e´ tipicamente um teorema
cuja prova e´ simples e que serve para demonstrar um teorema mais
complicado. Um corola´rio e´ um teorema que e´ consequ¨eˆncia imediata de
outro teorema. Uma conjectura e´ uma afirmac¸a˜o que no´s na˜o sabemos se
e´ verdadeira ou falsa (no caso, “no´s” quer dizer a comunidade cient´ıfica).
Certo. . .Mas o que e´ uma prova/demonstrac¸a˜o? Eis uma explicac¸a˜o
dada por Paulo Feofiloff [1]:
• Uma prova e´ uma sequ¨eˆncia de sentenc¸as.
1
• Cada sentenc¸a e´ o uma afirmac¸a˜o (por exemplo, “n e´ primo” ou “o
grafo H e´ conexo” ou “existe um caminho com extremos u e v”) ou uma
definic¸a˜o de varia´veis (por exemplo, “seja p um nu´mero primo maior
que 2” ou “seja v um ve´rtice na˜o-isolado” ou “seja X o conjuntos dos
ve´rtices que bla´ bla´ bla´”).
• Cada afirmac¸a˜o e´ uma consequ¨eˆncia lo´gica simples das afirmac¸o˜es an-
teriores (o leitor deve ser capaz de perceber e verificar isso facilmente).
• Cada afirmac¸a˜o ou definic¸a˜o so´ envolve varia´veis que foram definidas
em alguma sentenc¸a anterior.
• A u´ltima sentenc¸a e´ a declarac¸a˜o do fato que voceˆ pretende provar.
Apresentamos va´rios exemplos de prova/demonstrac¸a˜o na pro´xima sec¸a˜o.
Um teorema tem tipicamente a seguinte forma: se A enta˜o B, onde
• A e´ uma afirmac¸a˜o ou conjunto de afirmac¸o˜es que chamamos de
hipo´tese e
• B e´ uma afirmac¸a˜o ou conjunto de afirmac¸o˜es que chamamos de tese
ou conclusa˜o.
Outra forma de dizer isto e´: A implica B. Em linguagem de lo´gica A implica
B e´ equivalente a` expressa˜o ¬A ∨ B. A expressa˜o ¬A significa a negac¸a˜o
de A e ∨ e´ o operador lo´gico “ou” (“or”). Em portugueˆs, isto significa que
para mostrar que A implica B ou que ¬A∨B e´ verdade, temos que mostrar
que se A for verdadeira enta˜o B tambe´m deve ser verdadeira.
Eis alguns exemplos:
1. Se n e´ um inteiro par par enta˜o 3n+ 1 e´ ı´mpar.
2. Se o grafo G tem grau mı´nimo 2 enta˜o G conte´m um circuito.
Em alguns enunciados, a hipo´tese fica impl´ıcita:
1. A equac¸a˜o x2 + bx+ c = 0 possui no ma´ximo duas ra´ızes reais.
2. Existem infinitos nu´meros primos.
2
3. Toda a´rvore tem pelo menos duas folhas.
4. Existem infinitos grafos 3-regulares sem aresta-de-corte.
Alguns teoremas teˆm a forma: A se e somente se B. Neste caso, e´ preciso
provar as duas implicac¸o˜es: se A enta˜o B e se B enta˜o A.
Eis alguns exemplos:
1. Um inteiro n e´ par se e somente se n2 e´ par.
2. Um grafo G e´ bipartido se e somente se na˜o conte´m circuitos ı´mpares.
2 Me´todos de prova
2.1 Prova direta
Como o nome diz, este e´ o me´todo direto. Supomos que vale a hipo´tese
e tentamos chegar na tese/conclusa˜o.
Teorema 2.1. Se n e´ um inteiro ı´mpar enta˜o n2 e´ um inteiro ı´mpar.
Demonstrac¸a˜o. Suponha que n seja um inteiro ı´mpar. Enta˜o existe algum
inteiro k tal que n = 2k + 1. Logo,
n2 = (2k + 1)2 = 4k2 + 4k + 1 = 2(2k2 + 2k) + 1.
Portanto, n2 e´ um inteiro ı´mpar.
2.2 Prova indireta
Este me´todo tambe´m e´ conhecido por prova pela contra-positiva. A ide´ia
do me´todo consiste no seguinte: em vez de provar que se A enta˜o B, prova-
mos que se B na˜o vale enta˜o A na˜o vale. Em linguagem de lo´gica, isto
equivale a provar que se ¬B enta˜o ¬A ou que ¬B implica ¬A.
Teorema 2.2. Se 3n+ 2 e´ ı´mpar enta˜o n e´ ı´mpar.
3
Demonstrac¸a˜o. Suponha que a tese na˜o vale, ou seja, n e´ par. Enta˜o existe
um inteiro k tal que n = 2k. Logo,
3n+ 2 = 3(2k) + 2 = 6k + 2 = 2(3k + 1),
e assim, 3n+ 2 e´ par (ou seja, na˜o e´ ı´mpar). Como chegamos a` negac¸a˜o da
hipo´tese, a implicac¸a˜o original e´ verdadeira.
2.3 Prova por contradic¸a˜o
Este me´todo e´ bastante poderoso, embora seja um tanto confuso para
quem na˜o esta´ acostumado. A ide´ia e´ a seguinte: em vez de provar que
se A enta˜o B, supomos que A vale e B na˜o vale e tentamos chegar a uma
conclusa˜o absurda (por exemplo, conclu´ımos que A na˜o vale ou chegamos
a alguma coisa claramente sem sentido como 0 = 1). Isto mostra que a
afirmac¸a˜o se A enta˜o B tem que ser verdadeira pois verificamos na˜o ser
poss´ıvel A ser verdade e B ser falso (esta e´ a negac¸a˜o de se A enta˜o B).
Teorema 2.3. O nu´mero
√
2 e´ irracional.
Demonstrac¸a˜o. Suponha por contradic¸a˜o (ou por absurdo) que
√
2 seja
racional. Enta˜o existem inteiros p e q sem fatores em comum tais que√
2 = p/q (ou seja, a frac¸a˜o p/q esta´ reduzida). Enta˜o elevando os dois
lados da equac¸a˜o ao quadrado obtemos
2 = p2/q2.
Portanto,
2q2 = p2.
Isto significa que p2 e´ par e portanto p e´ par. Ale´m disso, como p e´ par,
enta˜o existe algum inteiro k tal que p = 2k. Logo,
2q2 = 4k2,
e assim,
q2 = 2k2.
Isto significa que q2 e´ par e portanto q e´ par.
Acabamos de mostrar que tanto p quanto q sa˜o divis´ıveis por 2. Isto
contraria nossa hipo´tese inicial de que
√
2 = p/q com p e q sem fatores em
comum. Portanto,
√
2 e´ irracional.
4
2.4 Prova por ana´lise de casos
A prova de alguns teoremas consiste em particionar o universo de possi-
bilidades em um nu´mero finito de casos e enta˜o provar a veracidade de cada
um desses. Para provar um caso qualquer te´cnica pode ser usada, inclusive
uma nova subdivisa˜o em casos.
Teorema 2.4. Se x e y sa˜o inteiros com mesma paridade enta˜o x+y e´ par.
Demonstrac¸a˜o. Ha´ dois casos que devem ser analisados:
Caso 1: x e y sa˜o pares. Enta˜o existem inteiros m e n tais que x = 2m
e y = 2n. Logo,
x+ y = 2m+ 2n = 2(m+ n),
e assim x+ y e´ par.
Caso 2: x e y sa˜o ı´mpares. Enta˜o existem inteiros p e q tais que x = 2p+1
e y = 2q + 1. Logo,
x+ y = (2p+ 1) + (2q + 1) = 2(p+ q + 1),
e assim x+ y e´ par.
Portanto, se x e y teˆm a mesma paridade, enta˜o x+ y e´ par.
2.5 Prova por construc¸a˜o
Alguns teoremas afirmam a existeˆncia de certos objetos. Um me´todo
para provar um teorema deste tipo e´ simplesmente exibir um objeto da
forma desejada.
Teorema 2.5. Existem inteiros x, y e z tais que x2 + y2 = z2.
Demonstrac¸a˜o. Tome x = 3, y = 4 e z = 5. Enta˜o 32 + 42 = 9 + 16 = 25 =
52.
Teorema 2.6. Existe um nu´mero infinito de inteiros x, y e z tais que x2 +
y2 = z2.
Demonstrac¸a˜o. Basta considerar o conjunto {(3n, 4n, 5n) : n ∈ N}.
5
Prova na˜o-construtiva de existeˆncia. Na˜o veremos muito este
me´todo na disciplina, mas eis um exemplo.
Teorema 2.7. Existem irracionais x e y tais que xy e´ racional.
Demonstrac¸a˜o. Ja´ sabemos que
√
2 e´ irracional. Considere o nu´mero
√
2
√
2
.
Sabemos que ele e´ racional ou irracional. Se ele for racional, enta˜o existem
dois irracionais x e y tais que xy e´ racional, mais exatamente x =
√
2 e
y =
√
2. Por outro lado, se
√
2
√
2
for irracional, enta˜o podemos tomar
x =
√
2
√
2
e y =
√
2 e assim,xy = (
√
2
√
2
)
√
2 =
√
2
(
√
2
√
2)
=
√
2
2
= 2.
Esta prova e´ na˜o-construtiva pois na˜o encontramos irracionais x e y tais
que xy e´ racional. Em vez disso, mostramos que ou o par x =
√
2, y =
√
2
ou o par x =
√
2
√
2
, y =
√
2 tem a propriedade desejada, mas na˜o sabemos
qual!
3 Contra-exemplos
Um modo de mostrar que uma afirmac¸a˜o se A enta˜o B na˜o e´ verdadeira
e´ exibir um contra-exemplo. Ou seja, exibir um objeto que satisfaz A mas
na˜o satisfaz B.
Considere por exemplo a afirmac¸a˜o: para todo n ≥ 1, 22n + 1 e´ primo.
Isto e´ verdade para n = 1, 2, 3, 4 (estou contando apenas, na˜o e´ ta˜o fa´cil de
ver. . . ) mas na˜o vale para n = 5 ja´ que 22
5
+ 1 = 232 + 1 = 4294967297 =
641 × 6700417 na˜o e´ primo. Assim, n = 5 e´ um contra-exemplo para a
afirmac¸a˜o acima. Este exemplo mostra tambe´m que para provar um teorema
na˜o e´ suficiente verificar que vale para alguns casos particulares.
4 Conjecturas
Uma conjectura e´ uma afirmac¸a˜o que na˜o sabemos se e´ verdadeira ou
falsa.
A seguinte conjectura e´ bem famosa e esta´ em aberto ha´ mais de 300
anos!
6
Conjectura 4.1 (Goldbach). Todo inteiro par maior que 2 pode ser escrito
como uma soma de dois primos.
E´ fa´cil testar isso para nu´meros pares pequenos: 4 = 2 + 2, 6 = 3 + 3,
8 = 3 + 5, 10 = 3 + 7 etc. No entanto este me´todo na˜o serve para provar a
conjectura ja´ que ha´ um nu´mero infinito de nu´meros pares. Entretanto, note
que para mostrar que a conjectura e´ falsa bastaria exibir um contra-exemplo.
Refereˆncias
[1] P. Feofiloff. Pa´gina da disciplina de Teoria dos Grafos no IME-USP.
http://www.ime.usp.br/~pf/mac5770-2005/tarefas.html
[2] K. H. Rosen. Discrete Mathematics and its applications, McGraw-
Hill, 2003.
7