Aula 07 - Semana 03 - FMC

FUNDAMENTOS MATEMÁTICOS
PARA COMPUTAÇÃO
Técnicas de Demonstração
SUMÁRIO
➢ Demonstrações Informais
➢ Técnicas de Demonstração
○ Direta
○ Contraposição
○ Absurdo
Demonstrações Informais
● Teorema: afirmação que pode ser provada
como verdadeira, por meio de outras
afirmações já demonstradas.
● Dado P → Q, se P for verdadeiro e provarmos
que Q também o será, P → Q torna-se um
teorema.
● Os teoremas são provados de modo menos
formal do que usando lógica proposicional e
lógica de predicados.
Basta um contraexemplo para mostrar que uma
conjectura é falsa.
Exemplo:
● Todos os animais que vivem no oceano são
peixes.
Baleia - Mamífero - CONTRAEXEMPLO!!
● Todo inteiro menor do que 10 é maior do que 5.

2 < 10 e 2 não é maior que 5
CONTRAEXEMPLO!!
Basta um contraexemplo para mostrar que uma
conjectura é falsa.
Exemplo: Para todo inteiro positivo n, n! ≤ n2

n=1 1!=1=12
n=2 2!=2<22=4
n=3 3!=6<23=8
n=4 4!=24≰ 42=16 FALSO - CONTRAEXEMPLO!!
Demonstração por Exaustão
Exemplo: Para qualquer inteiro positivo menor ou
igual a 5, o quadrado do inteiro é menor ou igual à
soma de 10 com 5 vezes o inteiro.
Dem. por exaustão: n2<10 + 5xn
n=1 12=1<10+5x1=15
n=2 22=4<10+5x2=20
n=3 32=9<10+5x3=25
n=4 42=16<10+5x4=30
n=5 52=25<10+5x5=35
Demonstração por Exaustão
Exemplo: Para qualquer inteiro positivo, o
quadrado do inteiro é menor ou igual à soma de
10 com 5 vezes o inteiro.
Dem. por exaustão:

n=6 62=36<10+5x6=40
n=7 72=49<10+5x7=45 X
n=8 82=64<10+5x8=50 X
Direta
Suponha a hipótese P e deduza a conclusão Q.
P→Q
● Estabelece-se uma sequência de
demonstração partindo de P e chegando a Q.
Exemplo: Se x é um inteiro par e y é um inteiro

par, então o produto xy é um inteiro par.
Direta
1o Passo: Identificar a hipótese e tese (conclusão)

● Hipótese: x é um inteiro par
y é um inteiro par
● Tese: xy é um inteiro par.
Direta
2o Passo: Representar matematicamente

● Hipótese: x=2a, para a inteiro
y=2b, para b inteiro.
● Tese: xy=2c, para c inteiro
Direta
3o Passo: Partimos da hipótese para a tese.
Seja x=2a, para a inteiro e y=2b, para b inteiro.
x.y=2a.2b
=2(a.2b)
=2k,
onde k=a.2b é um inteiro. Logo, xy=2k é par.
Provamos usando a demonstração direta!!!
Direta
Exemplo: Se um inteiro for divisível por 6, então
o dobro desse inteiro será divisível por 4
Prova: Usando demonstração direta

Hipótese: x é divisível por 6
x é um múltiplo de 6
x=6a, a é um valor inteiro.
Tese: O dobro desse inteiro é divisível por 4
2x=4b, b inteiro (????)
Direta
Exemplo: Se um inteiro for divisível por 6, então
o dobro desse inteiro será divisível por 4
Prova:
Dado x=6a, temos que:
x=6a
2x=12a
2x=4.3a
2x=4k, k=3a inteiro.
Logo, 2x é divisível por 4.
Contraposição
Dado (P → Q), provamos que Q′ → P′.
(P → Q) ⟺ (Q′ → P′)
Exemplo: Se o quadrado de um inteiro for

ímpar, então o inteiro terá que ser ímpar.
Hipótese P: x2=2a+1
Tese Q: x=2b +1 (Q) P’: x2=2a
a, b inteiros Q’: x=2b
Contraposição
Exemplo: Se o quadrado de um inteiro for ímpar,
então o inteiro terá que ser ímpar.
Dem. por contraposição
Hipótese Q’: x=2b e Tese P’: x2=2a
x=2b
x2=(2b)2
x2=4b2
x2=2.(2b2)
x2=2.k, k=2b2 inteiro
Contraposição
Proposição do tipo “se e somente se” requer
duas demonstrações, uma em cada direção.
(P ↔ Q) ⟺ (P→Q)⋀(Q→P)
Exemplo: Prove que o produto xy será ímpar

se e somente se tanto x quanto y forem
inteiros ímpares.
P: xy=2a+1 Q: x=2b+1 e y=2c+1
a,b,c inteiros
Contraposição
Exemplo: Prove que o produto xy será ímpar
se e somente se tanto x quanto y forem
inteiros ímpares.
Ida: P→Q. P: xy=2a+1 → Q: x=2b+1 e y=2c+1
Vamos usar contraposição: Q’→P’.
Q’: x=2b ou y=2c. x.y=x.2c
x.y=2b.y =2cx
=2k, =2k,
k=by inteiro. k=cx inteiro
Provamos P→Q usando Q’→P’
Contraposição
Exemplo: Prove que o produto xy será ímpar se e
somente se tanto x quanto y forem inteiros ímpares.
Volta: Q→P
(Q: x=2b+1 e y=2c+1 )→ (P: xy=2a+1)
Dem. direta: Q→P, P: x=2b+1 e y=2c+1.
x.y=(2b+1)(2c+1)
=4bc+2b+2c +1
= 2(2bc+b+c)+1=2k+1,
k=2bc+b+c inteiro. Logo, xy é ímpar.
Absurdo
(P ∧ Q′ → 0) ↔ (P → Q)
DICA: Para provar que algo não é verdade, tente
demonstração por absurdo.
Exemplo: Se um número somado a ele mesmo for
igual a ele mesmo, então esse número será 0
P: um número somado a ele mesmo for igual a ele
mesmo
P: x+x=x
Q: esse número será 0
Q: x=0
Absurdo
igual a ele mesmo, então esse número será 0.
Demonstrando por absurdo, temos:
P ∧ Q′ → 0
Hipótese: P ∧ Q′
(x+x=x) ∧ (x ≠0)
Tese: 0 - Falso
Absurdo
igual a ele mesmo, então esse número será 0.
P ∧ Q′ → 0
Hipótese: P ∧ Q′
(x+x=x) ∧ (x ≠0)
Tese: 0 - Falso
x+x=x (Hipótese)
2x=x
2x/x = x/x, pois x ≠0 (Hipótese)
2=1 Absurdo - FALSO!!
Absurdo
Exemplo: Provar que √2 não é um número racional.
Dem. por absurdo
Suponha que √2 é racional.
Logo, √2=p/q, onde p e q são inteiros indivisíveis.
√2=p/q
2=p2/q2
p2=2q2
Absurdo
Exemplo: Provar que √2 não é um número racional.
√2=p/q, onde p e q são inteiros indivisíveis.
√2=p/q
2=p2/q2
p2=2q2
Assim, 2 divide p2 e 2 é um fator de p.
Logo, p=2x e p2=(2x)2=2q2
4x2=2q2 => 2x=q2
Absurdo
Exemplo: √2 não é um número racional.
Logo, p=2x e p2=(2x)2=2q2
4x2=2q2 => 2x=q2
Temos que 2 divide q2, logo 2 divide q.
Isso significa que 2 é um fator comum de q e p, logo,
p e q não são indivisíveis.
Portanto, √2 não é racional!!!
Absurdo
Exemplo: Prove por absurdo que o produto de
dois inteiros ímpares não é par.
Vamos assumir, por absurdo, que o produto de

dois inteiros ímpares é par.
Lembre-se P ∧ Q′ → 0,
Hipóteses: (x=2a+1 e y=2b+1) e (x.y=2k)
Tese: Falso
Absurdo
Exemplo: Prove por absurdo que o produto de
dois inteiros ímpares não é par.
Dem:
xy=2k (Hipótese)
(2a+1)(2b+1)=2k (Hipótese)
4ab+2a+2b+1=2k
2(2ab+a+b)+1=2k
2m+1≠2k FALSO!!!
Os conceitos e exemplos apresentados
nesses slides são baseados no conteúdo da
seção 2.1 do material-base “Fundamentos
Matemáticos para a Ciência da Computação”,
J.L. Gersting, 7a edição, LTC editora.
FUNDAMENTOS MATEMÁTICOS
PARA COMPUTAÇÃO
Técnicas de Demonstração

Aula 07 - Semana 03 - FMC

Enviado por

Direitos autorais:

Formatos disponíveis

Aula 07 - Semana 03 - FMC

Enviado por

Dados do documento

Título original

Direitos autorais

Formatos disponíveis

Compartilhar este documento

Compartilhar ou incorporar documento

Opções de compartilhamento

Você considera este documento útil?

Este conteúdo é inapropriado?

Direitos autorais:

Formatos disponíveis

Aula 07 - Semana 03 - FMC

Enviado por

Direitos autorais:

Formatos disponíveis

FUNDAMENTOS MATEMÁTICOS

● Todo inteiro menor do que 10 é maior do que 5.

Exemplo: Para todo inteiro positivo n, n! ≤ n2

Dem. por exaustão:

Exemplo: Se x é um inteiro par e y é um inteiro

1o Passo: Identificar a hipótese e tese (conclusão)

2o Passo: Representar matematicamente

Prova: Usando demonstração direta

Exemplo: Se o quadrado de um inteiro for

Exemplo: Prove que o produto xy será ímpar

Vamos assumir, por absurdo, que o produto de

Hipóteses: (x=2a+1 e y=2b+1) e (x.y=2k)

Você também pode gostar