lista 1 - Questões

Prévia do material em texto

Resumo e Lista 1 - Números Inteiros e
Criptografia - Axiomas, Definições, Teoremas e
Provas
Obs: As referências dos Axiomas, Teoremas e Definições são ”clicáveis” no
pdf e pode te ajudar na leitura.
1 Problema de lógica
Um grupo de pessoas está organizando um crime. A poĺıcia já possui algumas
pistas e reuniu um grupo de suspeitos. No entanto, é preciso determinar entre os
suspeitos quem de fato faz parte do bando. Vocês são detetives especialistas em
lógica e, como a poĺıcia está precisando de ajuda, os contrataram para solucionar
o problema. Essas são as pistas (dicas) que a poĺıcia já tem.
1.1 Dicas - Axiomas
Todas as dicas são verdadeiras.
Suspeitos: Oscar, Felipe, Daniel, Patŕıcia, David, Nicolas, Marta, Andréia,
Tom.
Axioma 1.1. O grupo tem no mı́nimo 3 pessoas.
Axioma 1.2. Felipe e David não estão ambos no grupo.
Axioma 1.3. Se Marta ou Patŕıcia estão no grupo, então todos estão.
Axioma 1.4. Se Felipe está no grupo, David também está.
Axioma 1.5. Se Daniel está no grupo, Marta também está.
Axioma 1.6. Se Oscar ou Nicolas estão no grupo, Tom não está.
Axioma 1.7. Se Oscar ou David estão no grupo, Andréia não está.
1.2 Teoremas
Teorema 1.8. Marta e Patŕıcia não estão no grupo.
1
Prova. (Prova por contradicão)
Marta ou Patŕıcia estão no grupo
=⇒ { Axiom 1.3 }
Todos estão no grupo.
=⇒ { Fazer depois }
Felipe e David estão ambos no grupo.
=⇒ { Axioma 1.2 }
Falso
Teorema 1.9. Felipe não está no grupo.
Prova. (Prova por contradicão)
Felipe está no grupo
=⇒ { Axioma 1.4 }
David e Felipe estão no grupo
=⇒ { Axioma 1.2 }
Falso
Teorema 1.10. Daniel não está no grupo.
Prova. (Prova por contradicão)
Daniel está no grupo
=⇒ { Axioma 1.4 }
Marta está no grupo.
=⇒ { Teorema 1.8 }
Falso
Teorema 1.11. Se Tom está no grupo, Nicolas e Oscar não estão.
Prova.
Verdade
=⇒ { Axioma 1.6 }
Se Nicolas ou Oscar estão no grupo, então Tom não está no grupo.
=⇒ { Contrapositiva }
Se Tom está no grupo, então Nicolas e Oscar não estão.
2
Teorema 1.12. Se Andréia está no grupo, então Oscar e David não estão.
Prova.
Verdade
=⇒ { Axioma 1.7 }
Se Oscar ou David estão no grupo, então Andréia não está no grupo.
=⇒ { Contrapositiva }
Se Andréia está no grupo, então Oscar e David não estão.
Teorema 1.13. Se Tom está no grupo, Andréia e David estão no grupo.
Prova.
Tom está no grupo
=⇒ { Teorema 1.11 }
Nicolas e Oscar não estão.
=⇒ { Teoremas anteriores }
Oscar, Felipe, Daniel, Patŕıcia, Marta, e Nicolas não estão no grupo.
=⇒ { Axioma 0 - ”Tem nove suspeitos” }
O grupo tem no máximo 3 pessoas.
=⇒ { O grupo tem no mı́nimo 3 pessoas. }
O grupo tem exatamente 3 pessoas.
=⇒ { Fazer depois }
Andréia e David estão no Grupo.
Teorema 1.14. Se Andréia está no grupo, Tom e Nicolas estão no grupo.
Prova.
Andréia está no grupo
=⇒ { Teorema 1.12 }
David e Oscar não estão.
=⇒ { Teorema anteriores }
Oscar, Felipe, Daniel, Patŕıcia, Marta,e David não estão no grupo.
=⇒ { Dica 0 - ”Tem nove suspeitos” }
O grupo tem no máximo 3 pessoas.
=⇒ { O grupo tem no mı́nimo 3 pessoas. }
O grupo tem exatamente 3 pessoas.
=⇒ { Fazer depois }
3
Tom e Nicolas estão no Grupo.
Teorema 1.15. Andréia e David não estão ambos no grupo.
Prova. (Prova por contradicão)
Andréia e David estão ambos no grupo
=⇒ { Dica 7 }
Falso.
Teorema 1.16. Tom não está no grupo.
Prova. (Prova por contradicão)
Tom está no grupo.
=⇒ { Teorema 1.13 }
Andréia e David estão no grupo.
=⇒ { Teorema 1.15 }
Falso.
Teorema 1.17. Nicolas e Tom não estão no grupo.
Prova. (Prova por contradicão)
Nicolas e Tom não estão no grupo.
=⇒ { Dica 6 }
Falso.
Teorema 1.18. Andréia não está no grupo.
Prova. (Prova por contradicão)
Andréia está no grupo.
=⇒ { Teorema 1.14 }
Tom e Nicolas estão no grupo.
=⇒ { Teorema 1.17 }
Falso.
Teorema 1.19 (Teorema Principal). Oscar, Nicolas e David estão organizando
o crime.
Prova. Teoremas anteriores.
4
2 Teoremas da Lógica e Tabela Verdade
Teorema 2.1. Seja P uma afirmação. P ou FALSO =⇒ P .
Teorema 2.2. Sejam A,B, e C afirmações. A ou (B e C) ⇐⇒ (A ou B) e
(A ou C).
Teorema 2.3. Sejam A,B, e C afirmações. A ou A =⇒ A.
Teorema 2.4. Sejam A,B, e C afirmações. ¬(A ou B) ⇐⇒ (¬A) e (¬B)
3 Exemplos de provas com álgebra
Teorema 3.1. Seja a e b números reais. Se a · b = 0, então a = 0 ou b = 0.
Axioma 3.2. Seja x número real. Se x2 = −1, é falso.
Teorema 3.3. Seja x um número real. Se (x− 1)(x2 + 1) = 0, então x = 1.
Prova.
(x− 1)(x2 + 1) = 0
=⇒ { Teorema 3.1 }
(x− 1) = 0 ou (x2 + 1) = 0
=⇒ { Álgebra }
x = 1 ou x2 = −1
=⇒ { Axioma 3.2 }
x = 1 ou FALSO
=⇒ { Teorema 2.1 }
x = 1
4 Números Inteiros
Definição 4.1 (Numéros Inteiros ). O conjunto de números inteiros Z =
{. . . ,−3,−2,−1, 0, 1, 2, 3, . . .}.
Axioma 4.1. Se x é inteiro e y é inteiro, então x + y é inteiro, x− y é inteiro,
e x · y é inteiro,
Axioma 4.2. Seja x é inteiro. x + 0 = x é verdadeiro.
Axioma 4.3. Seja x é inteiro. x− x = 0 é verdadeiro.
5
5 Par e Ímpar
Definição 5.1 (Par). Seja a um inteiro. a é par ⇐⇒ existe um inteiro k tal
que a = 2k.
Definição 5.2 (́Impar). Seja a um inteiro. a é ı́mpar ⇐⇒ existe um inteiro k
tal que a = 2k + 1.
Teorema 5.1. Seja a um inteiro. Se a é par, então a2 é par.
Prova.
a é par
=⇒ { Definição 5.1 }
Existe um inteiro k tal que a = 2k.
=⇒ { Álgebra }
Existe um inteiro k tal que a2 = (2k)2 = 4k2 = 2(2k2).
=⇒ { n = 2k2 é inteiro pelo Axioma 4.1 }
Existe um inteiro n tal que a2 = 2n.
=⇒ { Definição 5.1 }
a2 é par
Teorema 5.2. Seja a um inteiro. Se a é ı́mpar, então a2 é ı́mpar.
Prova. Exercićıo
Teorema 5.3. Seja a e b inteiros. Se a é par e b é par, então a + b é par.
Prova. Exercićıo
Teorema 5.4. Seja a e b inteiros. Se a é ı́mpar e b é ı́mpar, então a + b é par.
Prova. Exercićıo
Teorema 5.5. Seja a e b inteiros. Se a é ı́mpar e b é ı́mpar, então a · b é ı́mpar.
Prova. Exercićıo
6 Conjuntos
Definição 6.1 (⊆). Seja x um elemento no conjunto universal. Se x ∈ A, então
x ∈ B ⇐⇒ A ⊆ B.
Axioma 6.1 (União). x ∈ A ∪B ⇐⇒ x ∈ A ou x ∈ B.
Axioma 6.2 (Interseção). x ∈ A ∩B ⇐⇒ x ∈ A e x ∈ B.
6
Teorema 6.3. Sejam A,B e C conjuntos. Se x ∈ A ∪ (B ∩ C), então x ∈
(A ∪B) ∩ (A ∪ C).
Prova.
x ∈ A ∪ (B ∩ C)
=⇒ { Axioma 6.1 }
x ∈ A ou x ∈ (B ∩ C)
=⇒ { Axioma 6.2 }
x ∈ A ou (x ∈ B e x ∈ C).
=⇒ { Teorema 2.2 }
(x ∈ A ou x ∈ B) e (x ∈ A ou x ∈ C).
=⇒ { Axioma 6.1 }
(x ∈ A ∪B) e (x ∈ A ∪ C).
=⇒ { Axioma 6.1 }
x ∈ (A ∪B) ∩ (A ∪ C).
Teorema 6.4. Sejam A,B e C conjuntos. A ∪ (B ∩ C) ⊆ (A ∪B) ∩ (A ∪ C).
Prova.
x ∈ A ∪ (B ∩ C) =⇒ x ∈ (A ∪B) ∩ (A ∪ C)
=⇒ { Definição 6.1 }
A ∪ (B ∩ C) ⊆ (A ∪B) ∩ (A ∪ C)
Teorema 6.5. Sejam A,B e C conjuntos. Se A ⊆ B e B ⊆ C, então A ⊆ C.
7 Conjecturas e contra-exemplos
Aonde está o erro na prova do próximo conjectura?
Conjectura 7.1. 2=1
Prova.
Verdadeiro
=⇒ { ??? }
−2 = −2
=⇒ { ??? }
4− 6 = 1− 3
=⇒ { ??? }
7
4− 6 + 94 = 1− 3 +
9
4
=⇒ { ??? }
(2− 32 )
2 = (1− 32 )
2
=⇒ { ??? }
2− 32 = 1−
3
2
=⇒ { ??? }
2 = 1
Conjectura 7.2. Seja x e y números reais. Se x2 = y2, então x = y.
Contra-exemplo: Seja x = 2 e y = −2 que são números reais. Temos que
x2 = (2)2 = 4 = (−2)2 = y2, mas x = 2 6= −2 = y.
Conjectura 7.3. Seja n um número natural. Se n é primo, então 2n − 1 é
primo.
Contra-exemplo: Seja n = 11 que é um número natural. Temos que 11 é
primo, mas 211 − 1 = 2047 = 23 · 89 não é primo.
Conjectura 7.4. Conjectura de Collatz
Vı́deo no Numberphile https://www.youtube.com/watch?v=5mFpVDpKX70&
ab_channel=Numberphile
7.1 Mudando o contexto - ”consertando uma conjectura”
Teorema 7.5 (Ráız quadrada dos dois lados). Seja x e y números reais posi-
tivos. Se x2 = y2, então x = y.
8 Prova por casos
Seja n um número natural. Queremos provar que n2 + n é par. Vamos quebrar
a prova em dois casos: quando n é par (Teorema 5.1) ou quando o n é ı́mpar
(Teorema 5.2).
Teorema 8.1. Seja n um númeronatural. Se n é par, então n2 + n é par.
Prova.
n é par
=⇒ { Definição de Par (5.1) }
Existe um inteiro k tal que n = 2k.
=⇒ { Álgebra }
8
https://www.youtube.com/watch?v=5mFpVDpKX70&ab_channel=Numberphile
https://www.youtube.com/watch?v=5mFpVDpKX70&ab_channel=Numberphile
Existe um inteiro k tal que n2 + n = (2k)2 + 2k = 4k2 + 2k = 2(2k2 + k).
=⇒ { l = 2k2 + k é inteiro pelo Axioma 4.1 }
Existe um inteiro l tal que n2 + n = 2l.
=⇒ { Definição de Par (5.1) }
n2 + n é par
Prova Alternativa:
Prova.
n é par
=⇒ { Aula passada - Teorema 5.1 }
n2 é par e n é par
=⇒ { ”Par + Par = Par” - Teorema 5.3 }
n2 + n é par
Teorema 8.2. Seja n um número natural. Se n é ı́mpar, então n2 + n é par.
Prova.
n é ı́mpar
=⇒ { Teorema 5.2 (Se n é ı́mpar, então n2 é ı́mpar.) }
n2 é ı́mpar e n é ı́mpar
=⇒ { Teorema 5.4 - ”́ımpar + ı́mpar = par” }
n2 + n é par
Agora podemos provar o teorema que queŕıamos:
Teorema 8.3. Seja n um número natural. n2 + n é par.
Prova.
Verdadeiro
=⇒ { n é um número natural }
n é ı́mpar ou n é par.
=⇒ { Teoremas 8.1 e 8.2 }
n2 + n é par ou n2 + n é par
=⇒ { Teorema 2.3 }
n2 + n é par
9
9 Máximos e mı́nimos
Definição 9.1 (Máximo(a,b)). Definição da função máximo(a, b): dada em
aula.
Teorema 9.1 (Especificação do máximo). Seja a, b, x números inteiros. Se
max(a, b) ≤ x, então a ≤ x e b ≤ x.
Prova. Dica: quebre a prova em dois casos como no Teorema 8.3.
10 Positivos e Negativos
Definição 10.1 (Numéros Inteiros Positivos). O conjunto de números inteiros
positivos = {0, 1, 2, 3, . . .}.
Definição 10.2 (Numéros Inteiros Negativos). O conjunto de números inteiros
negativos = {. . . ,−3,−2,−1, 0}.
Esse próximo teorema nós fizemos informalmente na aula, mas detalhei um
pouco mais aqui.
Teorema 10.1. Seja x inteiro. Se x é positivo e negativo, então x = 0.
Prova.
x é positivo e negativo
= { Definições 10.1 e 10.2 }
x ∈ {0, 1, 2, 3, . . .} e x ∈ {. . . ,−3,−2,−1, 0}
= { Axioma 6.2 }
x ∈ {0, 1, 2, 3, . . .} ∩ {. . . ,−3,−2,−1, 0}
= { {0, 1, 2, 3, . . .} ∩ {. . . ,−3,−2,−1, 0} = {0} }
x ∈ {0}
= { 0 é o único elemento. }
x = 0
11 Desigualdades
Definição 11.1 (≤). a ≤ b ⇐⇒ b− a é positivo.
Definição 11.2 (≥). a ≥ b ⇐⇒ b− a é negativo.
Teorema 11.1 (Transitividade do ≤). Seja a, b e c inteiros. Se a ≤ b e b ≤ c,
então a ≤ c.
10
Prova.
a ≤ b e b ≤ c
= { Definição 10.1 }
b− a é positivo e c− b é positivo.
= { Positivo + Positivo = Positivo }
(b− a) + (c− b) é positivo
= { Álgebra }
c− a é positivo.
= { 0 é o único elemento }
a ≤ c
Teorema 11.2. Seja a e b inteiros. Se a ≤ b e b ≥ a, então a = b.
Prova.
a ≤ b e b ≥ a
= { Definições 10.1 e 10.2 }
b− a é positivo e b− a é negativo.
= { Teorema 10.1 }
b− a = 0
= { 0 é o único elemento }
a = b
Teorema 11.3. Seja a e b inteiros. a ≤ a.
Teorema 11.4. Seja a e b inteiros. 0 ≤ a.
Conjectura 11.5. Seja x, y e z inteiros. Se x ≥ y, então x · z ≥ y · z.
12 Exerćıcios
1. Três meninas que frequentam a mesma escola possuem mochilas de cores
diferentes e gostam de sucos e matérias distintas. Tente identificar a cor
da mochila e o gosto de cada uma delas.
Dicas - ”axiomas”
• A menina que gosta de português gosta de suco de abacaxi.
• A mochila de Manuela não é laranja.
• A garota de mochila vermelha gosta de suco de limão.
11
• Aline gosta de história e não gosta de suco de uva.
• Flávia não gosta de matemática.
Formalize sua resolução com teoremas e provas como fizemos no problema
de lógica na primeira seção.
2. Prove com tabela-verdade os Teoremas 2.2, 2.1, 2.3 e 2.4.
3. Prove os Teoremas 5.2, 5.3, 5.4 e 5.5.
4. Prove o Teorema 6.5.
5. Compare e contraste as duas provas do Teorema 8.1. Quais são as vanta-
gens e desvantages para você de cada uma das provas? Qual prova você
prefere? Por quê?
6. Prova o Teorema 9.1. Dica: quebre a prova em dois casos como no Teorema
7. Prove os Teoremas 11.3 e 11.4.
8. (a) Mostre com um contra-exemplo que a Conjectura 11.5 é falsa.
(b) Mude o contexto da Conjectura 11.5 para que ela seja verdadeira e
prove-a.
12
	Problema de lógica
	Dicas - Axiomas
	Teoremas
	Teoremas da Lógica e Tabela Verdade
	Exemplos de provas com álgebra
	Números Inteiros
	Par e Ímpar
	Conjuntos
	Conjecturas e contra-exemplos
	Mudando o contexto - "consertando uma conjectura"
	Prova por casos
	Máximos e mínimos
	Positivos e Negativos
	Desigualdades
	Exercícios