1
Matemática Discreta
Prof. Nilson Costa
[email protected]
2014
Definições Importantes
2
Proposição:
É qualquer afirmação, verdadeira ou falsa, mas que
faça sentido.
Exemplos:
A: Todo número maior e que 2 é impar. (V)
B: A soma dos ângulos internos de qualquer triângulo
é 180.(V)
C: Todo número impar é primo. (F)
Teorema: É uma proposição verdadeira do tipo
“P=>Q” , onde P e Q são proposições.
Definições Importantes
3
P é a Hipótese do teorema. (Conjectura, Suposição,
Presunção, Prognostico, etc.)
É um condição suficiente de Q
Q é a Tese do teorema.
Exemplos:
(1) D: n é um número primo maior do que 2.
E: n é um número ímpar.
(2) Se duas frações a/b e c/d são iguais então
𝑎 𝑐 𝑎+𝑐
= =
𝑏 𝑑 𝑏+𝑑
𝑎 𝑐
𝑎 𝑐 𝑎+𝑐
= ⇒ = =
𝑑 𝑏 𝑑 𝑏+𝑑
ou 𝑏
Definições Importantes
4
Lema: É um teorema preparatório para a
demonstração de outro teorema.
Colorário: É um teorema que segue como
consequência natural de outro teorema.
Atenção:
Num teorema “P=>Q” (Vale Q se vale P) e (Vale P
somente se valer Q)
P(Hipótese) é uma condição suficiente de Q( Tese)
e
Q(Tese) é uma condição necessária de P(Hipótese)
Definições Importantes
5
Recíproca de um teorema “P=>Q” : É proposição
Q=>P ou P<=Q que pode ser verdadeira ou não.
Ex: Todo número primo maior que 2 é ímpar.
Recíproca
Ex: Se ABC é um triângulo retângulo em B, então
AC 2=AB2+BC2
Recíproca
Definições Importantes
6
Atenção: PQ(P se e somente se Q)(Proposições
equivalentes)
A condição necessária e suficiente para que a
proposição P seja verdadeira é que a proposição Q
também seja verdadeira.
Ex: Existe várias maneiras de de se juntar o teorema
anterior e sua recíproca.
1- A condição necessária e suficiente para que um
triângulo ABC seja retângulo em B é que
AC 2=AB2+BC2
Definições Importantes
7
2- Dados três pontos distintos A,B e C, a condição
necessária e suficiente para que AC 2=AB2+BC2 é que
o triângulo ABC seja triângulo em B.
3- Seja ABC um triângulo. Então, ABC é um triângulo
em B  AC 2=AB2+BC2.
4- Um triângulo ABC é retângulo em B se e somente
se AC 2=AB2+BC2.
Exercícios Propostos
1-Escreva a recíproca para cada sentença:
a. O crescimento sadio das plantas é consequência da
quantidade suficiente de água.
Exercícios Propostos
Recíproca:
b. O crescimento da oferta de computadores é uma
condição necessária para o desenvolvimento
científico.
Recíproca:
c. Haverá novos erros apenas se o programa for
alterado.
Recíproca:
Exercícios Propostos
d. A economia de combustível implica um bom
isolamento, ou todas as janelas são janelas para
tempestades.
Recíproca:
e. Se a chuva continuar, o rio vai transbordar.
Rec:
Exercícios Propostos
f. Uma condição suficiente para a falha de uma rede é
que a chave geral pare de funcionar.
Rec:
g. Os abacates só estão maduros quando estão escuros
e macios.
Rec:
h. Uma boa dieta é uma condição necessária para um
gato saudável.
Rec:
Definições Importantes
11
Princípios Lógicos
Principio da não contradição
Afirma que uma proposição não pode ser verdadeira e
falsa ao mesmo tempo.
Em outras palavras denotando a negativa de uma
proposição por Ã, se A for verdadeira, então à é falsa
Principio do Terceiro Excluído
Afirma que qualquer proposição A ou é verdadeira ou
é falsa.
Em outras palavras , ou A é verdadeira, ou à é
verdadeira, não existindo uma terceira alternativa.
Técnicas de Demonstração
Tipos de Raciocínios
Indutivo: Parte do
(Construindo
uma
experiência).
particular
conclusão
12
para o geral
baseada
em
Ex: Examinando sete ou oito inteiros divisíveis por 6,
e constado que estes inteiros também são divisíveis
por 3.
Podemos conjecturar: Se P, então Q (se um inteiro é
divisível por 6, então ele também é divisível por 3).
Ex: Sistemas baseados em agentes(abordagem de
aprendizado)
Técnicas de Demonstração
Ex: O ferro conduz eletricidade
O ferro é metal
O ouro conduz eletricidade
O ouro é metal
O cobre conduz eletricidade
O cobre é metal
Logo os metais conduzem eletricidade.
13
Técnicas de Demonstração
14
Dedutivo: Parte do geral para o particular (Você
tenta verificar se sua conjectura é verdadeira ou
falsa).
Usado na lógica predicativa para provar que uma wff
é um teorema, ou encontramos uma interpretação na
qual a wff é falsa.
ex: Sistemas especialistas(abordagem declarativa)
Duas
abordagens
Demonstrar
a conjectura
Negar a
conjectura
Técnicas de Demonstração
15
Demonstração por contra exemplo (Negar a
conjectura)
Exemplo 0: Examinando sete ou oito inteiros
divisíveis por 6, foi constado que estes inteiros
também são divisíveis por 3.
Para encontrar um contra exemplo basta
simplesmente encontrando um inteiro divisível por 6
mas não por 3.
Exemplo 1: Considere a sentença "Todo inteiro menor
que 10 é maior que 5" ou, expresso em uma
implicação "Se um inteiro é menor que 10, então ele é
maior que 5".
Técnicas de Demonstração
16
Um contra exemplo para esta implicação é o inteiro
4.
PRÁTICA 1: Forneça contra exemplos para as
seguintes sentenças:
a. Todos os animais que vivem nos oceanos são peixes.
b. As entradas para um programa de computador são
sempre fornecidas através do teclado.
Exercícios Propostos
2- Encontre contra exemplos para cada uma das
seguintes afirmações:
a. Toda figura geométrica plana com quatro ângulos
retos é um quadrado.
Sol:
b. Se um número real não é positivo, então ele deve
ser negativo.
Sol:
c. Todas as pessoas ruivas têm olhos verdes ou são
altas.
Sol:
Exercícios Propostos
d. Todas as pessoas ruivas têm olhos verdes e são
altas.
Sol:
Técnicas de Demonstração
19
Demonstração Direta: No caso geral, como podemos
demonstrar que P=>Q é verdadeira?
Assume-se a hipótese P como verdadeira e deduz-se a
tese Q.
Exemplo 2: "Se um inteiro é divisível por 6, então ele
também é divisível por 3." O teorema faz uma
afirmação sobre um inteiro arbitrário, sua forma é:
(∀ x) ( x divisível por 6→ x divisível por 3)
Técnicas de Demonstração
Hipótese: x é divisível por 6 (verdadeiro)
Conclusão: x é divisível por 3 (definição de
divisibilidade) (verdadeiro)
PRÁTICA 2: Demonstre de forma direta o Teorema
"Se um inteiro é divisível por 6, então duas vezes o
inteiro é divisível por 4".
Técnicas de Demonstração
Solução:
Técnicas de Demonstração
Exemplo 3: demonstre de forma direta de que o
produto de dois números pares é par.
Solução:
Técnicas de Demonstração
Demonstração por Contraposição
É uma variante da técnica de prova direta.
Se você pode demonstrar o teorema P’→Q’ ,pode
concluir que P→Q pelo uso da tautologia
(Q’→ P’ ) → (P→ Q).
(Q’→P’ ) é a contrapositividade de P→Q.
A técnica para demonstrar que P →Q construindo
uma prova direta de Q’→ P’ é chamada
de
demonstração por contraposição.
Técnicas de Demonstração
Exemplo 4: Qual a contrapositiva do teorema “Se um
inteiro é divisível por 6, então ele também é divisível
por 3"
Sol:
Técnicas de Demonstração
PRÁTICA 3- Escreva a contraposição para cada
sentença:
a. Se a chuva continuar, o rio vai transbordar.
Sol:
b. Uma condição suficiente para a falha de uma rede é
que a chave geral pare de funcionar.
Sol:
Técnicas de Demonstração
c. Os abacates só estão maduros quando estão escuros
e macios.
Sol:
d. Uma boa dieta é uma condição necessária para um
gato saudável.
Sol:
Exercícios Propostos
27
1-Escreva a contrapositiva para cada sentença:
a. O crescimento sadio das plantas é consequência da
quantidade suficiente de água.
Contrapositiva:
b. O crescimento da oferta de computadores é uma
condição necessária para o desenvolvimento
científico.
Contrapositiva:
Exercícios Propostos
28
c. Haverá novos erros apenas se o programa for
alterado.
Contrapositiva:
d. A economia de combustível implica um bom
isolamento, ou todas as janelas são janelas para
tempestades.
Contrapositiva:
Técnicas de Demonstração
Exemplo 6 - A implicação "Se a > 5 então a >
2" é verdadeira, no entanto a sua recíproca "Se
a > 2 então a > 5" é falsa.
30
Atenção: Lembre-se de que qualquer teorema
do tipo "se e somente se" requer uma
demonstração em ambas as direções.
Técnicas de Demonstração
Exemplo 7- Demonstre que o produto xy é ímpar se, e
somente se, x e y são inteiros ímpares.
Solução:
Técnicas de Demonstração
Técnicas de Demonstração
Parte da demonstração do Exemplo 7 utiliza a técnica
conhecida como demonstração por exaustão( ou por
casos) que algumas vezes é muito útil.
Técnicas de Demonstração
Demonstração por contradição ou absurdo
Suponhamos que estamos tentando demonstrar que
P→Q.
Por construção da tabela-verdade, veremos que
(P ᴧ Q’ →0) →(P →Q)é uma tautologia,
então para demonstrar que o teorema P →Q é
suficiente demonstrar que P ᴧ Q’ →0
Técnicas de Demonstração
Exemplo 8- Use a prova por contradição para a
sentença "Se um número somado a ele próprio resulta
no próprio número, então o número é 0 (zero)".
Solução:
Técnicas de Demonstração
Exemplo 9- Mostra que 2 não é um número
racional. Lembrando que um número racional é um
número que pode ser escrito na forma p/q onde p e q
são inteiros, q≠ 0 e p e q não têm fatores comuns
(além de ±1).
Técnicas de Demonstração
Sol:
Técnicas de Demonstração
Pratica 5- Prove por contradição que o produto de
dois inteiros pares é par.
Sol:
Técnicas de Demonstração
Técnica de Demonstração
Abordagem para provar
P→Q
Observações
Demonstração por Exaustão
Demonstre P→Q para todos
os casos possíveis
Pode ser usada apenas para
provar um número finito de
casos
Demonstração Direta
Suponha P, deduza Q
Abordagem padrão—o que
se deve tentar, em geral.
Demonstração por
Contraposição
Suponha Q’, deduza P’
Use essa técnica se Q’
parece dar mais munição do
que P.
Demonstração por absurdo
Suponha PᴧQ’, deduza uma
contradição.
Use essa técnica quando Q
disser que alguma coisa não
é verdade
Exercícios Propostos
39
As definições a seguir podem ser úteis na resolução de
alguns dos exercícios.
• Um quadrado perfeito é um inteiro n tal que n = k2
para algum inteiro k.
• Um número primo é um inteiro n > 1 tal que n não
é divisível por nenhum inteiro além de 1 e n.
• Para dois números x e y, x < y significa y - x > 0.
5- Prove que se n = 25, 100 ou 169 então n é um
quadrado perfeito e é a soma de dois quadrados
perfeitos.
Exercícios Propostos
40
Solução:
6- Prove que se n é um inteiro par, 4 ≤ n ≤ 12, então n
é a soma de dois números primos.
Solução:
Exercícios Propostos
41
4. Dê contra exemplos para as proposições a seguir:
a. O número n é um inteiro se, e somente se, 3n+5 é
um inteiro par.
Solução:
Exercícios Propostos
42
18. Prove que o número n é um número impar se, e
somente se, 3n+5=6k+8 para algum inteiro k.
Solução:
Exercícios Propostos
43
b. O número n é um inteiro par se, e somente se, 3n+2
é inteiro par.
Solução:
Exercícios Propostos
44
19. Prove que o número n é um número par se, e
somente se, 3n+2=6k+2 para algum inteiro k.
Solução:
Exercícios Propostos
45
07. Prove que para qualquer inteiro positivo n ≤ 3,
n! < 2n.
Solução:
08. Prove que para 2≤ n ≤4, 2n ≤ n2.
Solução:
Exercícios Propostos
47
9. Forneça uma demonstração direta de que a soma
de inteiros pares é par.
Sol:
10. Forneça uma demonstração por absurdo de que a
soma de inteiros pares é par. Sol:
Exercícios Propostos
11. Prove que a soma de dois inteiros ímpares é par.
Solução:
47
Exercícios Propostos
48
12. Prove que a soma de um inteiro par e um inteiro
ímpar é ímpar.
Solução:
15. Prove que o quadrado de um número par é
divisível por 4.
Solução:
Exercícios Propostos
49
20. Sejam x e y números positivos, prove que x < y se,
e somente se, x2 < y2.
Solução :
Exercícios Propostos
50
23. Prove que se dois inteiros são ambos divisíveis por
um inteiro n, então a sua soma é divisível por n.
Solução:
Exercícios Propostos
51
28- Prove que o quadrado de um inteiro ímpar pode
ser escrito como 8k + 1 para algum inteiro k.
Solução:
29- Prove que o produto dos quadrados de dois
inteiros é um quadrado perfeito.
Solução:
Limites
52
AGORA É A SUA
VEZ BONS
ESTUDOS
BÁSICA
Referências Bibliográficas
53
1. GERSTING, J. Fundamentos Matemáticos para Ciência da Computação.
Rio de Janeiro: LTC, 1995.
2. LOPES, L. Manual de Indução Matemática. Rio de Janeiro: Interciência,
1999.
3. MOLLUZZO, J. C. A First Course in Discrete Mathematics. SpringerVerlag Ny, 2000.
COMPLEMENTAR
1. SCHEINERMAN, Edward R. Matemática Discreta: Uma introdução.
2ª Ed. São Paulo: Cengage Learning, 2011.
2. ALENCAR FILHO, Edgard de. Iniciação à lógica matemática. São Paulo:
Nobel, 1975.
3. YAGLON, I. M. Álgebra Booleana. São Paulo: Atual, 1998.
DE APOIO RECOMENDADA
1. Utilizar os slides enviados se possível na forma impressa em sala de