BCC101 – Matemática Discreta
Demonstração de Teoremas
Prova de Bicondicional e Equivalência
Prova de ∀ e Prova de ∃
1
Provas de Bicondicional
Para provar uma afirmativa da forma
P ↔︎ Q (P se, e somente se, Q) devemos
provar P → Q e Q → P
Exemplo 1:
Prove que um inteiro n é par se, e
somente se, n2 é par.
2
Provas de Bicondicional
Exemplo 2:
Suponha x,y ∈ 𝐑. Então x3 + x2y = y2 + xy
se, e somente se, y = x2 ou y = -x.
⇒Suponha x3 + x2y = y2 + xy. Então
x2 (x+y) = y (x+y).
Portanto y = x2 ou y = -x
⟸ Suponha y = x2 ou y = -x
Se y = x2: x3+x2y = x3+x4 = x4+x3=y2+xy
Se y = -x: x3+x2y=x3-x3=0 e y2+xy=y2-y2=0
3
Provas de Equivalência
Prove que as seguintes afirmações são
equivalentes:
q) n é impar
b) (n+1) é par
c) n2 é impar
Queremos provar (a) ⇔ (b) ⇔ (c)
Estratégia:
(a)
(b)
(c)
4
Provas de Equivalência
(a)
(b): Suponha n impar, i.e., n=2k+1,
para algum k∈𝐙. Então n+1=2k+2=2(k+1)
ou seja, n+1 é par.
(b)
(c): Suponha (n+1) par, i.e, n+1=2k
para algum k∈𝐙. Então n2=(n+1)2(2n+1)=(2k)2-4k-1=4k2-4k-1=2(2k2-2k)-1,
ou seja, n2 é impar
(c)
(a): Suponha, por contraposição,
que n é par, i.e., n=2k para algum k∈𝐙.
Então n2=4k2, ou seja, n2 é par.
Portanto, se n2 é impar então n é impar 5
Provas envolvendo quantificadores
Para provar uma afirmativa da forma
∀x. f(x), devemos provar que f(x) é
verdadeira, para x arbitrário.
Exemplo:
Prove que, para quaisquer inteiros a,b,c,
se a|b e b|c então a|c.
6
Provas envolvendo quantificadores
Prove que, para quaisquer inteiros a,b,c,
se a|b e b|c então a|c.
Prova: Sejam a,b,c inteiros arbitrários
e suponha a|b e b|c, isto é, b = na e c=mb,
para alguns n,m inteiros.
Então c = mb = m(n a) = (n m) a, isto é,
a|c.
7
Provas envolvendo quantificadores
Para provar uma afirmativa da forma
∃x.f(x), devemos mostrar um valor
para x, digamos a, tal que f(a) seja
verdadeira.
Exemplo:
Prove que, para todo número real x>0,
existe um número real y>0 tal que
y(y+1)=x
8
Provas envolvendo quantificadores
Prove que, para todo número real x>0,
existe um número real y>0 tal que
y(y+1)=x
Prova: Seja x real arbitrário e tome
Então
y(y + 1) =
y=
1 + 4x - 1
1 + 4x - 1
2
2
.
1 + 4x + 1
2
=
1 + 4x - 1
4
=x
9
Erros em provas
Considere a seguinte afirmação
incorreta: ∃x∈R. ∀y∈R. (x y2 = y-x)
O que está errado com a seguinte prova
desta afirmação:
Prova: Seja x = y/(y2+1). Então
y-x = y- y/(y2+1)
= y3/(y2+1)
= (y/(y2+1)) y2 = xy2
10
Prova de existência - construtiva
Prove que existe um número inteiro que
pode ser escrito como a soma de dois
cubos de diferentes maneiras
1729 = 103 + 93 = 123 + 13
11
Prova de existência - não construtiva
Prove que existem números irracionais x e
y tais que xy é racional.
Prova: Considere =√2√2 Temos 2 possíveis
casos:
1)√2√2 é racional, o que conclui a prova
2)√2√2 é irracional. Então, tomando
x = √2√2 e y = √2, temos xy = (√2√2) √2 =
√22 = 2.
12
Prova de existência - construtiva
Prove que existem números irracionais x e
y tais que xy é racional.
Prova: Considere x=√2 e y=log29. Temos
√2log29 = √22log23 = (√22)log23 = 2log23 = 3
Sabemos que √2 é irracional. Para
completar a prova, basta mostrar que log29
é irracional.
(continua…)
13
Prova de existência - construtiva
Provando que log29 é irracional.
Suponha, por contradição, que log29 é
racional, i.e., log29 = a/b, onde a,b ∈𝑍, b≠0
Isso significa que 2(a/b) = 9.
Elevando ambos os lados a b, obtemos
2a = 9b. Mas 2a é par, e 9b é ímpar.
2a = 9b – ABSURDO!
Portanto log29 é irracional.
14
Existência e Unicidade
A prova de uma afirmativa da forma
∃! x. f(x) tem duas partes:
Prova de existência:∃x. f(x)
Prova de unicidade:
 (∀y∀z. f(y) ∧ f(z) ➝ y=z)
Exemplo:
Prove que, para todo número real x>0,
existe um único real y>0 tal que
y(y+1)=x
15