Lógica - Exercícios Resolvidos UFMG

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Lista1 - Gabarito.pdf
Lista de Exercícios 1: Soluções
Fundamentos da Lógica – Lógica Proposicional
UFMG/ICEx/DCC DCC111 – Matemática Discreta
Ciências Exatas & Engenharias 2o Semestre de 2014
1. Construa a tabela da verdade para a seguinte proposição: E = (p ∨ (¬p ∨ q)) ∧ ¬(q ∧ ¬r)
Resposta:
p q r (p ∨ (¬p ∨ q)) ¬(q ∧ ¬r) E
V V V V V V
V V F V F F
V F V V V V
V F F V V V
F V V V V V
F V F V F F
F F V V V V
F F F V V V
2. Mostre se as expressões E1 e E2 são equivalentes logicamente:
E1 = (s→ (p ∧ ¬r)) ∧ ((p→ (r ∨ q)) ∧ s)
E2 = (p ∧ q ∧ ¬r ∧ s) ∨ ¬(p ∨ s)
Resposta:
p q r s (s → (p ∧ ¬r)) ((p → (r ∨ q)) ∧ s) E1 (p ∧ q ∧ ¬r ∧ s) ¬(p ∨ s) E2
V V V V F V F F F F
V V V F V F F F F F
V V F V V V V V F V
V V F F V F F F F F
V F V V F V F F F F
V F V F V F F F F F
V F F V V F F F F F
V F F F V F F F F F
F V V V F V F F F F
F V V F V F F F V V
F V F V F V F F F F
F V F F V F F F V V
F F V V F V F F F F
F F V F V F F F V V
F F F V F V F F F F
F F F F V F F F V V
Como as duas tabelas da verdade não são idênticas, as expressões E1 e E2 não são equivalentes logicamente.
1
3. Faça a simplificação lógica da seguinte expressão usando apenas as leis da lógica:
(p ∧ (¬(¬p ∨ q))) ∨ (p ∧ q)
Resposta:
(p ∧ (¬(¬p ∨ q))) ∨ (p ∧ q) De Morgan sobre ¬(¬p ∨ q).
(p ∧ (p ∧ ¬q)) ∨ (p ∧ q) Associatividade sobre p ∧ (p ∧ ¬q).
((p ∧ p) ∧ ¬q) ∨ (p ∧ q) Idempotência sobre p ∧ p.
(p ∧ ¬q) ∨ (p ∧ q) Distributividade sobre a expressão.
p ∧ (¬q ∨ q) Negação sobre ¬q ∨ q.
p ∧ t Identidade com a tautologia t.
p
4. Mostre se o seguinte argumento é válido ou não usando as formas válidas de argumentos. Em cada passo,
identifique a razão para se obter a conclusão:
(a) ¬p→ r ∧ ¬s
(b) t→ s
(c) u→ ¬p
(d) ¬w
(e) u ∨ w
(f) ... ¬t ∨ w
Resposta:
Deduções:
(i) u ∨ w (e)
¬w (d)
... u Silogismo Disjuntivo
(ii) u→ ¬p (c)
u (i)
... ¬p Modus Ponens
(iii) ¬p→ r ∧ ¬s (a)
¬p (ii)
... r ∧ ¬s Modus Ponens
(iv) r ∧ ¬s (iii)
... ¬s Simplificação Conjuntiva
(v) t→ s (b)
¬s (iv)
... ¬t Modus Tollens
(vi) ¬t (v)
... ¬t ∨ w Adição Disjuntiva
A forma de argumento é válida.
5. O famoso detetive Percule Hoirot foi chamado para resolver um assassinato misterioso. Ele determinou os
seguintes fatos:
(a) Lord Charles, o homem assassinado, foi morto com uma pancada na cabeça com um castiçal.
2
(b) Ou Lady Camila ou a empregada Sara estavam na sala de jantar no momento do assassinato.
(c) Se o cozinheiro estava na cozinha no momento do assassinato, então o açougueiro matou Lord Charles
com uma dose fatal de arsênico.
(d) Se Lady Camila estava na sala de jantar no momento do assassinato, então o motorista matou Lord
Charles.
(e) Se o cozinheiro não estava na cozinha no momento do assassinato, então Sara não estava na sala de
jantar quando o assassinato ocorreu.
(f) Se Sara estava na sala de jantar no momento do assassinato, então o ajudante pessoal de Lord Charles
o matou.
É possível para o detetive Percule Hoirot deduzir quem matou Lorde Charles? Se sim, quem é o assassino?
Resposta:
Sejam os seguintes argumentos:
p = Lord Charles foi morto com uma pancada na cabeça com um castiçal.
q = Lady Camila estava na sala de jantar no momento do assassinato.
r = Sara estava na sala de jantar no momento do assassinato.
s = Cozinheiro estava na cozinha no momento do assassinato.
t = Açougueiro matou Lord Charles com uma dose fatal de arsênico.
u = Motorista matou Lord Charles.
v = Ajudante pessoal de Lord Charles o matou.
Tradução dos fatos para as proposições:
(a) p
(b) q ∨ r
(c) s→ t
(d) q → u
(e) ¬s→ ¬r
(f) r → v
Deduções:
(i) Suponha que s seja V, i.e., o cozinheiro estava na cozinha no momento do assassinato.
s→ t (c)
s (Suposição)
... t Modus Ponens
(ii) No entanto, t→ “contradição”, já que Lord Charles não foi morto com arsênico e sim por uma pancada
na cabeça (a). Logo, a suposição que o cozinheiro estava na cozinha é falsa. Assim, temos ¬s.
s→ t (c)
t→ “contradição” (i)
... ¬s Silogismo Hipotético e Contradição
(iii) ¬s→ ¬r (e)
¬s (ii)
... ¬r Modus Ponens
(iv) q ∨ r (b)
¬r (iii)
... q Silogismo Disjuntivo
(v) q → u (d)
q (iv)
3
... u Modus Ponens
De onde se conclui que o motorista matou Lord Charles.
6. Construa a tabela da verdade para a seguinte proposição: E = (p⊕ q) ∧ (p⊕ ¬q)
Resposta:
p q (p ⊕ q) (p ⊕ ¬q) E
V V F V F
V F V F F
F V V F F
F F F V F
7. Construa a tabela da verdade para a seguinte proposição: E = (¬p↔ ¬q)→ (p→ ¬r)
Resposta:
p q r ¬p ¬q ¬r (¬p ↔ ¬q) (p → ¬r) E
V V V F F F V F F
V V F F F V V V V
V F V F V F F F V
V F F F V V F V V
F V V V F F F V V
F V F V F V F V V
F F V V V F V V V
F F F V V V V V V
8. Seja a tabela da verdade do operador ⊙:
p q p ⊙ q
V V V
V F F
F V F
F F V
(a) O operador ⊙ segue a lei da associatividade com o operador ∧, i.e., (x ⊙ y) ∧ z ?≡ x ⊙ (y ∧ z).
Resposta:
x y z (x ⊙ y) ∧ z x ⊙ (y ∧ z)
V V V V V
V V F F F
V F V F F
V F F F F
F V V F F
F V F F V
F F V V V
F F F F V
Como as duas colunas da direita não são idênticas, o operador ⊙ não segue a lei da associatividade
com o operador ∧.
(b) O operador ⊙ segue a lei da distributividade com o operador ∧, i.e., x ⊙ (y ∧ z) ?≡ (x ⊙ y) ∧ (x ⊙ z).
Resposta:
4
x y z x ⊙ (y ∧ z) (x ⊙ y) ∧ (x ⊙ z)
V V V V V
V V F F F
V F V F F
V F F F F
F V V F F
F V F V F
F F V V F
F F F V V
Como as duas colunas da direita não são idênticas, o operador ⊙ não segue a lei da distributividade
com o operador ∧.
9. Mostre a equivalência lógica da seguinte proposição usando apenas as leis da lógica:
(p→ r) ∨ (q → r) ≡ (p ∧ q)→ r
Resposta:
(p→ r) ∨ (q → r) ≡ (p ∧ q)→ r
(¬p ∨ r) ∨ (¬q ∨ r) ≡
¬p ∨ ¬q ∨ r ≡
(¬p ∨ ¬q) ∨ r ≡
¬(¬p ∨ ¬q)→ r ≡
(p ∧ q)→ r ≡
10. Mostre se os seguintes requisitos são consistentes ou não. Caso sejam, para que valores esses requisitos são
consistentes.
Se o sistema de arquivos não está travado, então novas mensagens serão enfileiradas. Se o sistema
de arquivos não está travado, então o sistema está funcionando normalmente e vice-versa. Se
novas mensagens não são enfileiradas, então elas serão enviadas para o buffer de mensagens. Se
o sistema de arquivos não está travado, então novas mensagens serão enviadas para o buffer de
mensagens. Novas mensagens não serão enviadas para o buffer de mensagens.
Resposta:
Sejam os seguintes argumentos:
p = O sistema de arquivos não está travado.
q = Novas mensagens serão enfileiradas.
r = O sistema está funcionando normalmente.
s = Mensagens serão enviadas para o buffer de mensagens.
Tradução dos fatos para as proposições:
(a) p→ q
(b) p→ r
(c) r → p
(d) ¬q → s
(e) p→ s
(f) ¬s
Deduções:
(i) ¬q → s (d)
5
¬s (f)
... q Modus Tollens
(ii) p → s (e)
¬s (f)
... ¬p Modus Tollens
(iii) r → p (c)
¬p (ii)
... ¬r Modus Tollens
(iv) p → r (b)
¬r (iii)
... ¬p Modus Tollens
Pelas deduções acima temos que os requisitos são consistentes para os valores:
¬p = V : O sistema de arquivos está travado.
q = V : Novas mensagens serão enfileiradas.
¬r = V : O sistema não está funcionando normalmente.
¬s = V : Mensagens não serão enviadas para o buffer de mensagens.
11. Mostre se o seguinte argumento é válido ou não:
p ∧ ¬q → r
p ∨ q
q → p
... r
Resposta:
Variáveis Aux Premissas Conclusão
p q r p ∧ ¬q p ∧ ¬q → r p ∨ q q → p r
1. → V V V F V V V V
2. → V V F F V V V F
3. → V F V V V V V V
4. V F F V F V V
5. F V V F V V F
6. F V F F V V F
7. F F V F V F V
8. F F F F V F V
Ü A conclusão é verdadeira para as linhas 1 e 3 e falsa para a linha 2. Ou seja, a conclusão não é verdadeira
para todas as linhas críticas. Logo, o argumento é inválido.
12. Mostre se o seguinte argumento é válido ou não usando as formas válidas de argumentos. Em cada passo,
identifique a razão para se obter a conclusão:
(a) p→ q
(b) r ∨ s
(c) ¬s→ ¬t
(d) ¬q ∨ s
(e) ¬s
(f) ¬p ∧ r → u
(g) w ∨ t
(h) ... u ∧ w
6
Resposta:
(i) r ∨ s (b)
¬s (e)
... r Silogismo disjuntivo
(ii) ¬q ∨ s (d)
¬s (e)
... ¬q Silogismo disjuntivo
(iii) p→ q (a)
¬q (ii)
... ¬p Modus Tollens
(iv) ¬p ∧
r → u (f)
¬p ∧ r Adição conjuntiva de (iii) e (i)
... u Modus Ponens
(v) ¬s→ ¬t (c)
¬s (e)
... ¬t Modus Ponens
(vi) w ∨ t (g)
¬t (v)
... w Silogismo disjuntivo
(vii) u (iv)
w (vi)
... u ∧ w Adição conjuntiva
Ü O argumento é válido.
13. Sejam duas variáveis lógicas x e y, ou seja variáveis que podem assumir o valor verdadeiro (V ) ou falso (F ).
Seja ← o comando de atribuição existente em linguagens de programação como C e ⊙ o operador definido
no exercício 8. Qual é o valor dessas variáveis ao final da execução sequencial dos três comandos abaixo.
Apresente a sua resposta independente dos valores iniciais de x e y.
x← ¬(x⊙ y)
y ← ¬(x⊙ y)
x← ¬(x⊙ y)
Resposta:
Reescrevendo os comandos acima com o operador “ou exclusivo” temos (veja exercício 8):
x← (x⊕ y)
y ← (x⊕ y)
x← (x⊕ y)
Executando os comandos e lembrando que o operador “ou exclusivo” segue a lei da associatividade e que 0
é o elemento neutro, temos:
x← (x⊕ y) (1)
y ← (x⊕ y) ≡ ((x⊕ y)⊕ y) ≡ (x⊕ (y ⊕ y)) ≡ (x⊕ 0) ≡ x (2)
x← (x⊕ y) ≡ ((x⊕ y)⊕ y) ≡ ((x⊕ y)⊕ x) ≡ ((x⊕ x)⊕ y) ≡ (0⊕ y) ≡ y (3)
7
No comando (1), a variável x recebe o resultado de x⊕ y. No comando (2), a variável y recebe o resultado
da operação do “ou exclusivo” entre a variável x, que contém o resultado de x⊕y, e a variável y. O resultado
dessa operação é x. No comando (3), a variável x recebe o resultado da operação do “ou exclusivo” entre a
variável x, que contém o resultado de x⊕ y, e a variável y, cujo valor é x. O resultado dessa operação é y.
Ou seja, após a execução desses três comandos a variável x tem o valor inicial de y e a variável y tem o
valor inicial de x.
O texto, a seguir, foi retirado do livro texto, página 19: “Lógicas Fuzzy são utilizadas em inteligência artificial.
Na lógica fuzzy, a proposição tem um valor-verdade que é um número entre 0 e 1 inclusive. Uma proposição com
valor-verdade 0 é falsa e uma com valor-verdade 1 é verdadeira. Valores entre 0 e 1 indicam variantes de grau
de verdade. Por exemplo, o valor-verdade 0,8 pode ser indicado para uma proposição "Fred é feliz", porque ele é
feliz na maior parte do tempo; e o valor-verdade 0,4 pode ser indicado para a proposição "John é feliz", porque
ele é feliz menos que a metade do tempo”.
14. O valor-verdade da negação de uma proposição em lógica fuzzy é 1 menos o valor-verdade da proposição.
Quais são os valores-verdade das proposições "Fred não é feliz" e "John não é feliz"?
Resposta:
pf = 0, 8: "Fred é feliz";
pj = 0, 4: "John é feliz".
¬pf = 1− pf = 1− 0, 8 = 0, 2: "Fred não é feliz";
¬pj = 1− pj = 1− 0, 4 = 0, 6: "John não é feliz";
15. O valor-verdade da disjunção de duas proposições em lógica fuzzy é o máximo dos valores-verdade de duas
proposições. Quais são os valores-verdade das proposições "Fred é feliz ou John é feliz" e "Fred não é feliz
ou John não é feliz"?
Resposta:
Sejam p e q variáveis da Lógica Fuzzy. A disjunção p ∨ q = max(p ; q).
(a) "Fred é feliz ou John é feliz".
pf ∨ pj = max(0, 8; 0, 4) = 0, 8.
(b) "Fred não é feliz ou John não é feliz"
¬pf ∨ ¬pj = max(0, 2; 0, 6) = 0, 6.
16. Cada habitante de uma vila longínqua sempre diz a verdade ou sempre mente. Um habitante dela dará
apenas como resposta um sim ou um não para a pergunta que um turista fizer. Suponha que você seja um
turista que visita essa área e que chegue a uma bifurcação na estrada. Um lado leva até às ruínas que você
quer visitar; o outro, às profundezas de uma floresta. Um habitante dessa vila está parado nessa bifurcação.
Que pergunta você pode fazer ao habitante para determinar qual lado seguir?
Resposta:
Se for perguntado simplesmente qual estrada leva às ruínas e o turista não souber se é um habitante que fala
a verdade ou mente, então não é possível determinar se a resposta é correta ou não. A pergunta não pode
depender do tipo de habitante e, para isso, é necessário formular uma pergunta que envolva duas questões.
Assim, ao invés de perguntar “a bifurcação da direita leva às ruínas?” (pergunta P1), que não resolve o
problema, deve-se perguntar algo similar a “se eu fosse lhe perguntar se a bifurcação da direita me leva
às ruínas, você responderia sim?” (pergunta P2). Naturalmente a mesma estratégia pode ser feita para a
bifurcação da esquerda. Veja que a pergunta P2 pode ser vista como: “se eu fosse lhe perguntar se P1, você
responderia sim?”, o que claramente mostra que a pergunta P2 trata de duas questões.
O habitante que fala a verdade responde corretamente. O habitante que fala mentira deve “mentir duas
vezes” no sentido que se a pergunta fosse simplesmente “a bifurcação da direita leva às ruínas?”, isto é, P1,
ele teria que mentir. No entanto, como há uma segunda questão envolvida “se eu fosse lhe perguntar se P1,
você responderia sim?” então esse habitante deve mentir novamente. Esse raciocínio está representado na
tabela abaixo.
8
P1: A bifurcação da direita leva às ruínas?
P2: Se eu fosse lhe perguntar se a bifurcação da direita me leva às ruínas, você responderia sim?
Tipo de habitante Bifurcação da direita
leva às ruínas?
P1 P2
Fala verdade
Sim Sim Sim
Não Não Não
Fala mentira
Sim Não Sim
Não Sim Não
Se o habitante sempre fala a verdade, ele dirá ao turista se deve seguir pela bifurcação da direita ou esquerda.
Se o habitante sempre fala mentira, ao responder a P2 ele sabe que mentiu ao responder P1 (parte dessa
pergunta). No entanto, ele mente novamente e, no final, ele responde corretamente a bifurcação a ser
seguida. A estratégia é usar uma dupla negativa.
17. Este sistema de especificações é consistente? “O sistema está em um estado de multiuso se e somente se
estiver operando normalmente. Se o sistema está operando normalmente, o núcleo do sistema operacional
(kernel) está funcionando. O kernel não está funcionando ou o sistema está no modo de interrupção. Se o
sistema não está em um estado de multiuso, então está em um modo de interrupção. O sistema não está no
modo de interrupção.”
Resposta:
Sejam os seguintes argumentos:
p = O sistema está em um estado de multiuso.
q = O sistema está operando normalmente.
r = O núcleo do sistema operacional (kernel) está funcionando.
s = O sistema está no modo de interrupção.
Tradução dos fatos para as proposições:
(a) p↔ q ≡ (p→ q) ∧ (q → p)
(b) q → r
(c) ¬r ∨ s
(d) ¬p→ s
(e) ¬s
Deduções:
(i) ¬r ∨ s (c)
¬s (e)
... ¬r Silogismo Disjuntivo
(ii) q → r (b)
¬r (i)
... ¬q Modus Tollens
(iii) ¬p → s (d)
¬s (e)
... p Modus Tollens
(iv) (p → q) ∧ (q → p) (a)
... p → q Simplificação Conjuntiva
(v) p → q (iv)
¬q (ii)
9
... ¬p Modus Tollens
As conclusões (iii) e (v) dizem que p e ¬p devem ser verdadeiros, o que claramente é inconsistente.
18. Este sistema de especificações é consistente? “O roteador pode enviar mensagens para o sistema principal
somente se ele tratar um novo espaço de endereço. Para o roteador tratar o novo espaço de endereço, é
necessário que a última versão do software seja instalada. O roteador pode enviar mensagens ao sistema
principal se a última versão do software estiver instalada. O roteador não trata o novo espaço.”
Resposta:
Sejam os seguintes argumentos:
p = O roteador pode enviar mensagens para o sistema principal.
q = O roteador trata um novo espaço de endereço.
r = A última versão do software seja instalada.
Tradução dos fatos para as proposições:
(a) p somente se q ≡ p→ q
(b) para q é necessário r ≡ r é uma condição necessária para q ≡ q → r
(c) p se r ≡ r → p ≡ ¬p→ ¬r
(d) ¬q
Dedução:
(i) p → q (a)
¬q (d)
... ¬p Modus Tollens
(ii) ¬p → ¬r (c)
¬p (i)
... ¬r Modus Ponens
Pelas deduções acima, as três proposições são falsas: ¬q de acordo com (d), ¬p de acordo com (i) e ¬r de
acordo com (ii). Se todas três proposições são falsas, as quatro especificações são verdadeiras e elas são
consistentes.
19. Um detetive entrevistou quatro testemunhas de um crime. A partir das histórias das testemunhas, o
detetive concluiu que, se o mordomo está dizendo a verdade, então o cozinheiro também está; o cozinheiro
e o jardineiro,
ambos, não podem estar dizendo a verdade; o jardineiro e o zelador, ambos, não estão
mentindo; e se o zelador está dizendo a verdade, então o cozinheiro está mentindo. Para cada uma das
quatro testemunhas, o detetive pode determinar se a pessoa está mentindo ou dizendo a verdade?
Resposta:
As quatro testemunhas podem ser identificadas pelas variáveis C (cozinheiro), J (jardineiro), M (mordomo)
e Z (zelador), que serão usadas para indicar que estão falando a verdade.
Sejam os seguintes argumentos:
(a) M → C [se o mordomo está dizendo a verdade, então o cozinheiro também está]
(b) C ⊕ J [o cozinheiro e o jardineiro, ambos, não podem estar dizendo a verdade]
(c) ¬J ⊕ ¬Z [o cozinheiro e o jardineiro, ambos, não podem estar dizendo a verdade]
(d) Z → ¬C [se o zelador está dizendo a verdade, então o cozinheiro está mentindo]
Pelos quatro argumentos acima, não é possível aplicar uma regra de inferência. Se fizermos uma tabela da
verdade, podemos identificar o cenário no qual as quatro premissas supostamente são verdadeiras, conforme
mostrado a seguir.
10
Variáveis Premissas
C J M Z (a) (b) (c) (d)
1. V V V V V F F F
2. V V V F V F V V
3. V V F V V F F F
4. V V F F V F V V
5. V F V V V V V F
6. V F V F V V F V
7. V F F V V V V F
8. V F F F V V F V
9. F V V V F V F V
10. F V V F F V V V
11. F V F V V V F V
12. → F V F F V V V V
13. F F V V F V V V
14. F F V F F F F V
15. F F F V V F V V
16. F F F F V F F V
Ü As premissas são verdadeiras para a linha 12, ou seja, o jardineiro fala a verdade e as outras testemunhas
não.
O texto, a seguir, foi retirado do livro texto, página 29: “O dual de uma proposição composta que contém apenas
os operadores lógicos ∨, ∧ e ¬ é a proposição composta obtida pela troca de cada ∨ por ∧, cada ∧ por ∨, cada
V por F e cada F por V . O dual de s é representado por s∗”.
20. Encontre o dual de cada uma das seguintes proposições compostas:
(a) s1 : p ∧ ¬q ∧ ¬r
Resposta:
s∗1 : p ∨ ¬q ∨ ¬r
(b) s2 : (p ∧ q ∧ r) ∨ s
Resposta:
s∗2 : (p ∨ q ∨ r) ∧ s
(c) s3 : (p ∨ F ) ∧ (q ∨ V )
Resposta:
s∗3 : (p ∧ V ) ∨ (q ∧ F )
(d) Apresente um exemplo de proposição composta formada por pelo menos duas variáveis tal que s ≡ s∗.
Resposta:
s4: (p ∨ F ) ∧ (q ∨ V )
p ∧ V
p
s∗4: (p ∧ V ) ∨ (q ∧ F )
p ∨ F
p
11
Lista1.pdf
Lista de Exercícios 1
Fundamentos da Lógica – Lógica Proposicional
UFMG/ICEx/DCC DCC111 – Matemática Discreta
Ciências Exatas & Engenharias 2o Semestre de 2014
1. Construa a tabela da verdade para a seguinte proposição: E = (p ∨ (¬p ∨ q)) ∧ ¬(q ∧ ¬r)
2. Mostre se as expressões E1 e E2 são equivalentes logicamente:
E1 = (s→ (p ∧ ¬r)) ∧ ((p→ (r ∨ q)) ∧ s)
E2 = (p ∧ q ∧ ¬r ∧ s) ∨ ¬(p ∨ s)
3. Faça a simplificação lógica da seguinte expressão usando apenas as leis da lógica:
(p ∧ (¬(¬p ∨ q))) ∨ (p ∧ q)
4. Mostre se o seguinte argumento é válido ou não usando as formas válidas de argumentos. Em cada passo,
identifique a razão para se obter a conclusão:
(a) ¬p→ r ∧ ¬s
(b) t→ s
(c) u→ ¬p
(d) ¬w
(e) u ∨ w
(f) ... ¬t ∨ w
5. O famoso detetive Percule Hoirot foi chamado para resolver um assassinato misterioso. Ele determinou os
seguintes fatos:
(a) Lord Charles, o homem assassinado, foi morto com uma pancada na cabeça com um castiçal.
(b) Ou Lady Camila ou a empregada Sara estavam na sala de jantar no momento do assassinato.
(c) Se o cozinheiro estava na cozinha no momento do assassinato, então o açougueiro matou Lord Charles
com uma dose fatal de arsênico.
(d) Se Lady Camila estava na sala de jantar no momento do assassinato, então o motorista matou Lord
Charles.
(e) Se o cozinheiro não estava na cozinha no momento do assassinato, então Sara não estava na sala de
jantar quando o assassinato ocorreu.
(f) Se Sara estava na sala de jantar no momento do assassinato, então o ajudante pessoal de Lord Charles
o matou.
É possível para o detetive Percule Hoirot deduzir quem matou Lorde Charles? Se sim, quem é o assassino?
6. Construa a tabela da verdade para a seguinte proposição: E = (p⊕ q) ∧ (p⊕ ¬q)
7. Construa a tabela da verdade para a seguinte proposição: E = (¬p↔ ¬q)→ (p→ ¬r)
8. Seja a tabela da verdade do operador �:
p q p � q
V V V
V F F
F V F
F F V
1
(a) O operador � segue a lei da associatividade com o operador ∧, i.e., (x � y) ∧ z ?≡ x � (y ∧ z).
(b) O operador � segue a lei da distributividade com o operador ∧, i.e., x � (y ∧ z) ?≡ (x � y) ∧ (x � z).
9. Mostre a equivalência lógica da seguinte proposição usando apenas as leis da lógica:
(p→ r) ∨ (q → r) ≡ (p ∧ q)→ r
10. Mostre se os seguintes requisitos são consistentes ou não. Caso sejam, para que valores esses requisitos são
consistentes.
Se o sistema de arquivos não está travado, então novas mensagens serão enfileiradas. Se o sistema
de arquivos não está travado, então o sistema está funcionando normalmente e vice-versa. Se
novas mensagens não são enfileiradas, então elas serão enviadas para o buffer de mensagens. Se
o sistema de arquivos não está travado, então novas mensagens serão enviadas para o buffer de
mensagens. Novas mensagens não serão enviadas para o buffer de mensagens.
11. Mostre se o seguinte argumento é válido ou não:
p ∧ ¬q → r
p ∨ q
q → p
... r
12. Mostre se o seguinte argumento é válido ou não usando as formas válidas de argumentos. Em cada passo,
identifique a razão para se obter a conclusão:
(a) p→ q
(b) r ∨ s
(c) ¬s→ ¬t
(d) ¬q ∨ s
(e) ¬s
(f) ¬p ∧ r → u
(g) w ∨ t
(h) ... u ∧ w
13. Sejam duas variáveis lógicas x e y, ou seja variáveis que podem assumir o valor verdadeiro (V ) ou falso (F ).
Seja ← o comando de atribuição existente em linguagens de programação como C e � o operador definido
no exercício ??. Qual é o valor dessas variáveis ao final da execução sequencial dos três comandos abaixo.
Apresente a sua resposta independente dos valores iniciais de x e y.
x← ¬(x� y)
y ← ¬(x� y)
x← ¬(x� y)
O texto, a seguir, foi retirado do livro texto, página 19: “Lógicas Fuzzy são utilizadas em inteligência artificial.
Na lógica fuzzy, a proposição tem um valor-verdade que é um número entre 0 e 1 inclusive. Uma proposição com
valor-verdade 0 é falsa e uma com valor-verdade 1 é verdadeira. Valores entre 0 e 1 indicam variantes de grau
de verdade. Por exemplo, o valor-verdade 0,8 pode ser indicado para uma proposição "Fred é feliz", porque ele é
feliz na maior parte do tempo; e o valor-verdade 0,4 pode ser indicado para a proposição "John é feliz", porque
ele é feliz menos que a metade do tempo”.
14. O valor-verdade da negação de uma proposição em lógica fuzzy é 1 menos o valor-verdade da proposição.
Quais são os valores-verdade das proposições "Fred não é feliz" e "John não é feliz"?
15. O valor-verdade da disjunção de duas proposições em lógica fuzzy é o máximo dos valores-verdade de duas
proposições. Quais são os valores-verdade das proposições "Fred é feliz ou John é feliz" e "Fred não é feliz
ou John não é feliz"?
2
16. Cada habitante de uma vila longínqua sempre diz a verdade ou sempre mente. Um habitante dela dará
apenas como resposta um sim ou um não para a pergunta que um turista fizer. Suponha que você seja um
turista que visita essa área e que chegue a uma bifurcação na estrada. Um lado leva até às ruínas que você
quer visitar; o outro, às profundezas de uma floresta. Um habitante dessa vila está parado nessa bifurcação.
Que pergunta você pode fazer ao habitante para determinar qual lado seguir?
17. Este sistema de especificações é consistente? “O sistema está em um estado de multiuso se e somente se
estiver operando normalmente. Se o sistema está operando normalmente, o núcleo do sistema operacional
(kernel) está funcionando. O kernel não está funcionando ou o sistema está no modo de interrupção. Se o
sistema não está em um estado de multiuso, então está em um modo de interrupção. O sistema não está no
modo de interrupção.”
18. Este sistema de especificações é consistente? “O roteador pode enviar mensagens para o sistema principal
apenas se ele tratar um novo espaço de endereço. Para o roteador
tratar o novo espaço de endereço, é
necessário que a última versão do software seja instalada. O roteador pode enviar mensagens ao sistema
principal se a última versão do software estiver instalada. O roteador não trata o novo espaço.”
19. Um detetive entrevistou quatro testemunhas de um crime. A partir das histórias das testemunhas, o
detetive concluiu que, se o mordomo está dizendo a verdade, então o cozinheiro também está; o cozinheiro
e o jardineiro, ambos, não podem estar dizendo a verdade; o jardineiro e o zelador, ambos, não estão
mentindo; e se o zelador está dizendo a verdade, então o cozinheiro está mentindo. Para cada uma das
quatro testemunhas, o detetive pode determinar se a pessoa está mentindo ou dizendo a verdade?
O texto, a seguir, foi retirado do livro texto, página 29: “O dual de uma proposição composta que contém apenas
os operadores lógicos ∨, ∧ e ¬ é a proposição composta obtida pela troca de cada ∨ por ∧, cada ∧ por ∨, cada
V por F e cada F por V . O dual de s é representado por s∗”.
20. Encontre o dual de cada uma das seguintes proposições compostas:
(a) s1 : p ∧ ¬q ∧ ¬r
(b) s2 : (p ∧ q ∧ r) ∨ s
(c) s3 : (p ∨ F ) ∧ (q ∨ V )
(d) Apresente um exemplo de proposição composta formada por pelo menos duas variáveis tal que s ≡ s∗.
3
Lista2 - Gabarito.pdf
Lista de Exercícios 2: Soluções
Proposições Quantificadas – Cálculo de Predicados
UFMG/ICEx/DCC DCC111 – Matemática Discreta
Ciências Exatas & Engenharias 2o Semestre de 2014
1. Determine o conjunto verdade para o predicado
n2 ≤ 30
e domínio Z.
Resposta:
O conjunto verdade D para o predicado acima é {−5, . . . , 5}.
2. Diga se a seguinte afirmação é verdadeira ou falsa. Se for falsa apresente um contra-exemplo:
∀a ∈ Z, (a− 1)
a
não é um inteiro.
Resposta:
A afirmação é falsa para a = 1, já que
a− 1
a
=
1− 1
1
=
0
1
= 0
que é um inteiro.
3. Escreva a negação da afirmação:
∀n ∈ Z, se n é primo então n é ímpar ou n = 2.
Resposta:
A negação é dada por:
∃n ∈ Z,¬( se (n é primo)=[p] então ((n é ímpar)=[q] ou (n = 2)=[r]) ≡
∃n ∈ Z,¬(p→ (q ∨ r)) ≡
∃n ∈ Z,¬(¬p ∨ (q ∨ r)) ≡
∃n ∈ Z, p ∧ (¬q ∧ ¬r) ≡
∃n ∈ Z, p ∧ ¬q ∧ ¬r ≡
∃n ∈ Z, n é primo e n é par e n 6= 2.
Observe que a afirmação original é verdadeira e sua negação é falsa.
4. Qual é o contrapositivo da afirmação:
∀ inteiros a, b e c, se a− b é par e b− c é par, então a− c é par.
Resposta:
∀ inteiros a, b e c, se (a− b é par e b− c é par)=[p], então (a− c é par)=[q] ≡
∀ inteiros a, b e c, se ¬q então ¬p ≡
∀ inteiros a, b e c, se ¬(a− c é par) então ¬(a− b é par e b− c é par) ≡
∀ inteiros a, b e c, se a− c não é par então a− b não é par ou b− c não é par
5. Seja P (x) um predicado tal que x ∈ R e os seguintes predicados:
– R(x) : ∀x ∈ Z, P (x);
1
– S(x) : ∀x ∈ Q, P (x);
– T (x) : ∀x ∈ R, P (x).
Encontre uma definição para P (x) que não use “x ∈ Z” de modo que R(x) seja verdadeiro e S(x) e T (x)
sejam falsos. Note que o domínio do predicado R(x) é mais restritivo que o domínio de P (x) já que o tipo
de número que pode ser aplicado ao predicado R é apenas do tipo inteiro. Uma observação similar vale para
o predicado S, mas nesse caso apenas para números racionais.
Resposta:
Possível resposta: Seja P (x) : 2x 6= 1. O predicado R(x) é verdadeiro (conjunto dos números inteiros)
enquanto os predicados S(x) e T (x) são falsos. O contra-exemplo é x = 12 para o conjunto dos números
racionais e reais.
6. Considere o string de números 0204. Seja a seguinte afirmação: “∀x, se x = 1 e x é um caractere no string
0204, então x está à esquerda de todos os 0’s no string”. Essa afirmação é verdadeira?
Resposta:
A negação dessa afirmação é “∃x tal que x = 1 e x é um caractere no string 0204 e x está à esquerda de
todos os 0’s no string”. A negação é falsa porque o string não contém o caractere 1. Assim, a afirmação é
verdadeira por default.
7. Reescreva cada afirmação na forma se–então.
(a) Obter conceito D nesta disciplina é condição suficiente para um estudante ser aprovado.
Resposta:
Se um estudante obtém conceito D nesta disciplina então ele é aprovado.
(b) Chegar no horário todo o dia é uma condição necessária para uma pessoa manter o emprego.
Resposta:
Se uma pessoa mantém o emprego então ela chega no horário todo o dia.
(c) Ser divisível por 8 não é uma condição necessária para um número ser divisível por 4.
Resposta:
Não é caso que se um número é divisível por 4 então o número é divisível por 8. Em outras palavras,
existe um número que é divisível por 4 e o número não é divisível por 8.
(d) Ter um grande rendimento não é uma condição suficiente para uma pessoa ser feliz.
Resposta:
Não é o caso que se uma pessoa tem um grande rendimento, então a pessoa é feliz. Em outras palavras,
existe uma pessoa que tem um grande rendimento e não é feliz.
8. Escreva cada uma das proposições abaixo na forma “p se e somente se q” em português.
(a) Se está calor lá fora, você compra um sorvete e se você compra um sorvete é porque está calor lá fora.
Resposta:
Você compra um sorvete se e somente se está calor lá fora.
(b) Para que você ganhe na loteria, é necessário e suficiente que você tenha o único bilhete premiado.
Resposta:
Você ganhe na loteria se e somente se você tem o único bilhete premiado.
(c) Você será promovido apenas se você tiver contatos, e você só terá contatos se for promovido.
Resposta:
Você será promovido se e somente se você tiver contatos.
(d) Se você assistir à televisão sua mente se deteriorará, e vice-versa.
Resposta:
Sua mente se deteriorará se e somente se você assistir à televisão.
(e) Os trens atrasam exatamente naqueles dias em que eu viajo neles.
Resposta:
Os trens atrasam se e somente se é um dia em que viajo neles.
2
9. Uma brochura de um clube para passageiros frequentes de vôos diz o seguinte: “você pode selecionar a
companhia aérea somente se se elas oferecem a mesma tarifa mais baixa”. Assumindo que “somente se”
tem o seu significado formal (significado lógico), este anúncio garante se duas ou mais companhias aéreas
oferecem a mesma tarifa mais baixa, o cliente poderá escolher entre elas? Explique.
Resposta:
Formalmente não. Sabemos que “somente se” significa “condição suficiente”. Assim, formalmente temos:
‘se você pode selecionar a companhia aérea então elas oferecem a mesma tarifa mais baixa”. O que foi
perguntado foi a proposição oposta, ou seja, “se duas ou mais companhias aéreas oferecem a mesma tarifa
mais baixa então o cliente poderá escolher entre elas”.
10. Sejam os predicados P (x) e Q(x) e suponha que D é o domínio de x. Determine se as seguintes proposições
são equivalentes logicamente ou não:
∀x ∈ D, (P (x) ∧Q(x)) ?≡ (∀x ∈ D,P (x)) ∧ (∀x ∈ D,Q(x))
Resposta:
Seja o domínio D = {x1, . . . , xn}. Assim, temos que
(P (x1) ∧Q(x1)) . . . ∧ . . . (P (xn) ∧Q(xn)) ≡ (P (x1) ∧Q(x1)) ∧ . . . ∧ (P (xn) ∧Q(xn))
que são equivalentes logicamente.
11. Diga se a forma do argumento abaixo é válida ou não, apresentando a justificativa.
Todas as pessoas saudáveis comem um banana por dia.
João não é uma pessoa saudável.
... João não come uma banana por dia.
Resposta:
∀ p, p é uma pessoa saudável, p come um banana por dia.
p não é uma pessoa saudável.
... p não come uma banana por dia.
Forma inválida: erro inverso, que tem a seguinte versão geral:
∀ x, se P (x) então Q(x);
¬P (a) para a em particular;
... ¬Q(a).
12. Diga se a forma do argumento abaixo é válida ou não, apresentando a justificativa.
Se uma série infinita converge, então os termos da série vão para 0.
Os termos da série infinita
∑∞
n=1
1
n vão para 0.
... A série infinita
∑∞
n=1
1
n converge.
Resposta:
∀ série infinita s, se s converge então os termos da série vão para 0.
Os termos da série infinita
∑∞
n=1
1
n vão para 0.
... A série infinita
∑∞
n=1
1
n converge.
Forma inválida: erro recíproco, que tem a seguinte versão geral:
∀ x, se P (x) então Q(x);
Q(a) para a em particular;
... P (a).
3
Lista2.pdf
Lista de Exercícios 2
Proposições Quantificadas
– Cálculo de Predicados
UFMG/ICEx/DCC DCC111 – Matemática Discreta
Ciências Exatas & Engenharias 2o Semestre de 2014
1. Determine o conjunto verdade para o predicado
n2 ≤ 30
e domínio Z.
2. Diga se a seguinte afirmação é verdadeira ou falsa. Se for falsa apresente um contra-exemplo:
∀a ∈ Z, (a− 1)
a
não é um inteiro.
3. Escreva a negação da afirmação:
∀n ∈ Z, se n é primo então n é ímpar ou n = 2.
4. Qual é o contrapositivo da afirmação:
∀ inteiros a, b e c, se a− b é par e b− c é par, então a− c é par.
5. Seja P (x) um predicado tal que x ∈ R e os seguintes predicados:
– R(x) : ∀x ∈ Z, P (x);
– S(x) : ∀x ∈ Q, P (x);
– T (x) : ∀x ∈ R, P (x).
Encontre uma definição para P (x) que não use “x ∈ Z” de modo que R(x) seja verdadeiro e S(x) e T (x)
sejam falsos. Note que o domínio do predicado R(x) é mais restritivo que o domínio de P (x) já que o tipo
de número que pode ser aplicado ao predicado R é apenas do tipo inteiro. Uma observação similar vale para
o predicado S, mas nesse caso apenas para números racionais.
6. Considere o string de números 0204. Seja a seguinte afirmação: “∀x, se x = 1 e x é um caractere no string
0204, então x está à esquerda de todos os 0’s no string”. Essa afirmação é verdadeira?
7. Reescreva cada afirmação na forma se–então.
(a) Obter conceito D nesta disciplina é condição suficiente para um estudante ser aprovado.
(b) Chegar no horário todo o dia é uma condição necessária para uma pessoa manter o emprego.
(c) Ser divisível por 8 não é uma condição necessária para um número ser divisível por 4.
(d) Ter um grande rendimento não é uma condição suficiente para uma pessoa ser feliz.
8. Escreva cada uma das proposições abaixo na forma “p se e somente se q” em português.
(a) Se está calor lá fora, você compra um sorvete e se você compra um sorvete é porque está calor lá fora.
(b) Para que você ganhe na loteria, é necessário e suficiente que você tenha o único bilhete premiado.
(c) Você será promovido apenas se você tiver contatos, e você só terá contatos se for promovido.
(d) Se você assistir à televisão sua mente se deteriorará, e vice-versa.
(e) Os trens atrasam exatamente naqueles dias em que eu viajo neles.
1
9. Uma brochura de um clube para passageiros frequentes de vôos diz o seguinte: “você pode selecionar a
companhia aérea somente se se elas oferecem a mesma tarifa mais baixa”. Assumindo que “somente se”
tem o seu significado formal (significado lógico), este anúncio garante se duas ou mais companhias aéreas
oferecem a mesma tarifa mais baixa, o cliente poderá escolher entre elas? Explique.
10. Sejam os predicados P (x) e Q(x) e suponha que D é o domínio de x. Determine se as seguintes proposições
são equivalentes logicamente ou não:
∀x ∈ D, (P (x) ∧Q(x)) ?≡ (∀x ∈ D,P (x)) ∧ (∀x ∈ D,Q(x))
11. Diga se a forma do argumento abaixo é válida ou não, apresentando a justificativa.
Todas as pessoas saudáveis comem um banana por dia.
João não é uma pessoa saudável.
... João não come uma banana por dia.
12. Diga se a forma do argumento abaixo é válida ou não, apresentando a justificativa.
Se uma série infinita converge, então os termos da série vão para 0.
Os termos da série infinita
∑∞
n=1
1
n vão para 0.
... A série infinita
∑∞
n=1
1
n converge.
2
Lista3 - Gabarito.pdf
Lista de Exercícios 3: Soluções
Métodos de Prova
UFMG/ICEx/DCC DCC111 – Matemática Discreta
Ciências Exatas & Engenharias 2o Semestre de 2014
1. Identifique o erro na prova do teorema abaixo.
Teorema: Para todos inteiros k, se k > 0 então k2 + 2k + 1 é um número composto.
Prova: Suponha que k é um número inteiro tal que k > 0. Se k2+2k+1 é composto, então k2+2k+1 = r ·s,
para inteiros r e s tal que 1 < r < (k2 + 2k + 1) e 1 < s < (k2 + 2k + 1). Já que k2 + 2k + 1 = r · s e
ambos r e s estão necessariamente entre 1 e k2 + 2k + 1, então k2 + 2k + 1 não é primo. Assim, k2 + 2k + 1
é composto, o que devia ser mostrado.
Resposta:
A partir do ponto
Já que k2+2k+1 = r ·s e ambos r e s estão necessariamente entre 1 e k2+2k+1, então k2+2k+1
não é primo. Assim, k2 + 2k + 1 é composto, o que devia ser mostrado.
é usada a questão a ser provada. Nesse ponto na prova, não foi mostrado ainda que k2 +2k+1 é um número
composto, o que devia ser provado.
2. Identifique o erro na prova do teorema abaixo.
Teorema: A soma de quaisquer dois inteiros pares é igual a 4k para algum inteiro k.
Prova: Suponha que m e n são dois inteiros pares quaisquer. Pela definição de par m = 2k para algum
inteiro k e n = 2k para algum inteiro k. Por substituição, m + n = 2k + 2k = 4k, o que devia ser provado.
Resposta:
O erro na “prova” é que o mesmo símbolo k é usado para representar dois números diferentes. Ao supor
que m e n são iguais a 2k, temos que m = n e, assim, a prova é válida apenas para o caso onde m = n. Se
m 6= n, a conclusão é, em geral, falsa. Por exemplo, 6 + 4 = 10 mas 10 6= 4k para qualquer inteiro k.
3. Identifique o erro na prova do teorema abaixo.
Teorema: Seja n um número inteiro ímpar. Sabe-se que bn/2c = (n− 1)/2.
Prova: Suponha que n é um número inteiro ímpar. Sabe-se que n = 2k + 1 para algum inteiro k. Conse-
quentemente, ⌊
2k + 1
2
⌋
=
(2k + 1)− 1
2
=
2k
2
= k.
Como n = 2k + 1, temos que k = (n− 1)/2. Assim, por substituição temos que bn/2c = (n− 1)/2.
Esta prova incorreta usa a questão a ser provada. A igualdade bn2 c é o que deve ser provado. Ao substituir
2k+1 por n nos dois lados da igualdade e assumindo que o resultado é verdadeiro, a prova assume a verdade
da conclusão a ser provada.
Resposta:
Prova “correta” : Suponha que n é um número inteiro ímpar. Sabe-se que n = 2k + 1 para algum inteiro
k. Consequentemente, ⌊
2k + 1
2
⌋
=
⌊
k +
1
2
⌋
= k.
Note que bk + 12c = k pela definição da função “chão”, já que k é o maior inteiro menor ou igual a k +
1
2 .
Ao substituirmos n por 2k + 1 no lado direito da equação proposta, temos:(
(2k + 1)− 1
2
)
=
(
2k
2
)
= k.
Assim, os lados esquerdo e direito da equação a ser provada são idênticos.
1
4. Prove se a seguinte afirmação é verdadeira ou não. Para todos inteiros n, 4(n2 +n+1)−3n2 é um quadrado
perfeito.
Resposta:
Prova: Suponha que n seja um número inteiro. Então 4(n2 + n + 1) − 3n2 = 4n2 + 4n + 4 − 3n2 =
n2 + 4n + 4 = (n + 2)2, que é um quadrado perfeito já que n + 2 é um inteiro.
5. Prove se a seguinte afirmação é verdadeira ou não. Existe um inteiro k tal que k ≥ 4 e 2k2−5k +2 é primo.
Resposta:
Para provar que a afirmação é falsa, devemos mostrar que a negação é verdadeira. A negação é “para todos
inteiros k, para k ≥ 4, 2k2 − 5k + 2 não é primo”.
Prova da negação: Suponha que k seja um inteiro tal que k ≥ 4. [Devemos mostrar que 2k2 − 5k + 2 não
é primo]. Ao fatorarmos 2k2 − 5k + 2 obtemos (2k − 1)(k − 2). Como k ≥ 4, podemos fazer as seguintes
afirmações sobre cada termo: (i) o termo (2k− 1) ≥ 7 já que 2k− 1 ≥ 2 · 4− 1 = 7 e (ii) o termo (k− 2) ≥ 2
já que 2k − 2 ≥ 2 · 4− 2 = 2. Assim, cada fator desse número é um inteiro positivo maior ou igual a dois e,
assim 2k2 − 5k + 2 não é primo.
6. Prove se a seguinte afirmação é verdadeira ou não. Para todos inteiros n e m, se n−m é par então n3−m3
é par.
Resposta:
Prova: Suponha que m e n são quaisquer inteiros tais que m − n é par. [Devemos mostrar que n3 −m3
é par.] Note que n3 −m3 = (n −m)(n2 + nm + m). Sabemos que (n −m) é par pela suposição. Temos
que (n2 + nm + m) é um número inteiro já que potenciação, multiplicação e soma são operações fechadas
no conjunto dos números inteiros. Assim, (n −m)(n2 + nm + m) é o produto de um número par por um
inteiro. A multiplicação de um inteiro por um número par pode ser representada pela soma desse inteiro
uma quantidade par de vezes, o que resulta em um número par. Isso é o que devia ser provado.
7. Prove se a seguinte afirmação é verdadeira ou não. O quociente de dois números racionais é um número
racional.
Resposta:
Reescrevendo a afirmação: ∀ números racionais r e s, rs é um número racional.
Prova: Seja r um número racional
qualquer e s = 0, que é um número racional. O quociente de r por s é
indefinido e, assim, não é necessariamente um número racional. Assim, a afirmação é falsa.
8. Prove se a seguinte afirmação é verdadeira ou não sem usar manipulação algébrica, ou seja, sem “resolver”
a equação. Suponha que m seja um número inteiro. Prove se 17|m na equação:
8 · 7 · 6 · 5 · 4 · 3 · 2 ·m ?= 17 · 16 · 15 · 14 · 13 · 12 · 11 · 10
Resposta:
Prova: O número 17 é um fator primo do número do lado direito da equação e é um fator primo do número
do lado esquerdo (pelo Teorema Único da Fatorização). Mas 17 não é um fator primo de 8, 7, 6, 5, 4, 3 e
2. Assim, 17 deve ocorrer como um fator primo de m e 17|m.
9. Prove se a seguinte afirmação é verdadeira ou não:
∀ inteiros a, b e c, se a|b e a|c então a|(b + c)
Resposta:
Prova: Suponha que a, b e c são inteiros tal que a|b e a|c. Pela definição de divisibilidade b = a ·r e c = a ·s
para inteiros r e s. Então b + c = a · r + a · s = a(r + s). Logo, a|(b + c) = a|a(r + s).
10. Suponha que você está participando de uma promoção de uma loja que dá um cartão com números quando
um cliente faz uma compra. Se existem números nesse cartão que somam 100, então o cliente ganha um
prêmio de R$100,00. Um cliente recebe um cartão com os números
72 21 15 36 69 81 9 27 42 63
2
Sem fazer combinações de somas, mostre se o cliente irá ganhar o prêmio ou não.
Resposta:
Cada um dos números anteriores é divisível por 3. Qualquer soma com esses números provê como resultado
um número que é divisível por 3. Como 100 não é divisível por 3, qualquer soma não será igual a 100.
Assim, o cliente não ganhará o prêmio com esse cartão.
11. Prove se a seguinte afirmação é verdadeira ou não: A soma de quatro números inteiros consecutivos não é
divisível por 4.
Resposta:
Reescrevendo a afirmação: ∀ números inteiros n, n + 1, n + 2 e n + 3, 4 6 |[n + (n + 1) + (n + 2) + (n + 3)].
Prova: Sejam n, n + 1, n + 2 e n + 3 quatro números inteiros consecutivos. Essa soma S vale 4n + 6 =
4n + 4 + 2 = 4(n + 1) + 2, que pode ser representada como S = 4t + 2. Quando S é dividido por 4 temos 2
como resto. Assim, essa soma não é divisível por 4.
12. Prove que para qualquer inteiro ímpar n, bn
2
4 c = (
n−1
2 )(
n+1
2 ).
Resposta:
Prova: Seja n um inteiro ímpar qualquer. Pela definição de ímpar, n = 2k +1 para algum inteiro k. Assim,
temos que ⌊
n2
4
⌋
=
⌊
(2k + 1)2
4
⌋
=
⌊
4k2 + 4k + 1
4
⌋
=
⌊
k2 + k +
1
4
⌋
= k2 + k.
Note que bk2 + k + 14c = k
2 + k pela definição da função “chão”, já que k2 + k é o maior inteiro menor ou
igual a k2 + k + 14 .
Ao substituirmos n por 2k + 1 no lado direito da equação proposta, temos:(
n− 1
2
)(
n + 1
2
)
=
(
(2k + 1)− 1
2
)(
(2k + 1) + 1
2
)
=
(
2k
2
)(
2k + 2
2
)
= k(k + 1) = k2 + k.
Assim, os lados esquerdo e direito da equação a ser provada são idênticos.
13. O resultado de 10 é um número irracional? Explique.
Resposta:
Sabe-se que um número irracional é um número real que não é um número racional. Assim, o resultado
de 10 não é um número irracional já que não é um número real (divisão por zero não está definida para o
conjunto dos números reais).
14. Prove por contradição que para todos os números primos a, b e c, a2 + b2 6= c2.
Resposta:
Prova: Suponha que não, ou seja, suponha que existam números primos a, b e c tais que a2 + b2 = c2.
Temos que a2 = c2 − b2 = (c− b)(c + b). Sabemos que c− b = 1 ou c− b > 1 já que c + b > 0 e a2 > 0, i.e.,
c− b deve ser positivo. Assim, temos dois casos:
Caso 1 (c − b = 1): Os únicos valores possíveis para b e c são c = 3 e b = 2 para a diferença entre esses
números primos ser 1, o que implica que b = 2. Logo, a2 = c2 − b2 = (3− 2)(3 + 2) = 5, i.e., a =
√
5. Mas
isto contradiz a suposição que a seja um número primo.
Caso 2 (c − b > 1): Devemos ter que ambos (c − b) > 1 e (c + b) > 1. Como a é primo, os únicos fatores
positivos de a2 são 1, a e a2. Como ambos (c − b) e (c + b) são maiores que 1, a única possibilidade é que
ambos sejam iguais a a. Mas isto implica que c − b = c + b, i.e., −b = b e assim b = 0. Isto contradiz a
suposição que b seja um número primo.
Nos dois casos a contradição é falsa e, assim, a suposição é falsa e a afirmação original é verdadeira.
15. Prove por contraposição que se a soma de dois números reais é menor que 50 então pelo menos um dos
números é menor que 25.
Resposta:
Reescrevendo formalmente temos: ∀x, y ∈ R, se x + y < 50 então x < 25 ou y < 25. A forma contrapositiva
dessa afirmação é ∀x, y ∈ R, se x ≥ 25 e y ≥ 25 então x + y ≥ 50.
Prova: Suponha que x e y sejam números reais específicos mas escolhidos arbitrariamente tais que x ≥ 25
e y ≥ 25. Consequentemente, a + b ≥ 25 + 25 = 50. Assim, se x + y < 50 então x < 25 ou y < 25.
3
16. Apresente um teorema cuja prova seja na forma geométrica.
Resposta:
Veja a prova para o Teorema de Pitágoras.
17. Prove que se x2 + y = 13 e y 6= 4, em que x, y ∈ R, então x 6= 3.
Resposta:
Prova: Sejam x e y números reais arbitrários. Suponha o contrário, isto é, x = 3. Substituindo-se x por 3
em x2 + y = 13, obtém-se 32 + y = 13. Assim, y = 13− 9 = 4, o que resulta em uma contradição. Portanto,
se x2 + y = 13 e y 6= 4, então x 6= 3.
18. Prove que se x > 0 e x < y, em que x, y ∈ R, então x2 < y2.
Resposta:
Prova: Sejam x e y números reais arbitrários tais que x > 0 e x < y. Ou seja, temos que 0 < x < y e,
portanto, y > 0. Consequentemente, x2 < xy < y2. De onde se conclui que x2 < y2.
19. Prove que min(x, y) + max(x, y) = x + y para quaisquer números reais x e y.
Resposta:
Prova: Sejam x e y números reais arbitrários. Sabe-se que x < y, x = y ou x > y. Serão considerados cada
um dos três casos:
– x < y: tem-se que min(x, y) = x e max(x, y) = y;
– x = y: min(x, y) = max(x, y) = x = y;
– x > y: min(x, y) = y e max(x, y) = x.
Em qualquer um dos três casos, min(x, y) + max(x, y) = x + y. Portanto, min(x, y) + max(x, y) = x + y
para quaisquer números reais x e y.
20. Prove por contradição que há uma infinidade de números primos.
Resposta:
Prova: Suponha que há uma quantidade limitada de números primos p1, p2, . . . , pn para algum natural n.
Seja k = (p1p2 . . . pn) + 1. Deste modo, k não é divisível por nenhum dos números primosp1, p2, . . . , pn.
Portanto, k é divisível por algum outro número primo diferente de p1, p2, . . . , pn ou k é primo. Em qualquer
dos dois casos, tem-se a existência de um primo diferente de p1, p2, . . . , pn. Isto contradiz a suposição de
que existe uma quantidade limitada de números primos.
21. Prove que se n = ab, sendo a, b ∈ Z+, então a ≤
√
n ou b ≤
√
n.
Resposta:
Prova: Sejam a e b dois inteiros positivos tais que a >
√
n e b >
√
n. Multiplicando-se as duas desigualdades,
obtém-se ab >
√
n
√
n, o que implica em ab > n. Isso mostra que ab 6= n. Portanto, a proposição é verdadeira.
4
Lista3.pdf
Lista de Exercícios 3
Métodos de Prova
UFMG/ICEx/DCC DCC111 – Matemática Discreta
Ciências Exatas & Engenharias 2o Semestre de 2014
1. Identifique o erro na prova do teorema abaixo.
Teorema: Para todos inteiros k, se k > 0 então k2 + 2k + 1 é um número composto.
Prova: Suponha que k é um número inteiro tal que k > 0. Se k2+2k+1 é composto, então k2+2k+1 = r ·s,
para inteiros r e s tal que 1 < r < (k2 + 2k + 1) e 1 < s < (k2 + 2k + 1). Já que k2 + 2k + 1 = r · s e
ambos r e s estão necessariamente entre 1 e k2 + 2k + 1, então k2 + 2k + 1 não é primo. Assim, k2 + 2k + 1
é composto, o que devia ser mostrado.
2. Identifique o erro na prova do teorema abaixo.
Teorema: A soma de quaisquer dois inteiros pares é igual a 4k para algum inteiro k.
Prova: Suponha que m e n são dois inteiros pares quaisquer. Pela definição de par m = 2k para algum
inteiro k e n = 2k para algum inteiro k. Por substituição, m + n = 2k + 2k = 4k, o que devia ser provado.
3. Identifique o erro na prova do teorema abaixo.
Teorema: Seja n um número inteiro ímpar. Sabe-se que bn/2c = (n− 1)/2.
Prova: Suponha que n é um número inteiro ímpar.
Sabe-se que n = 2k + 1 para algum inteiro k. Conse-
quentemente, ⌊
2k + 1
2
⌋
=
(2k + 1)− 1
2
=
2k
2
= k.
Como n = 2k + 1, temos que k = (n− 1)/2. Assim, por substituição temos que bn/2c = (n− 1)/2.
Esta prova incorreta usa a questão a ser provada. A igualdade bn2 c é o que deve ser provado. Ao substituir
2k+1 por n nos dois lados da igualdade e assumindo que o resultado é verdadeiro, a prova assume a verdade
da conclusão a ser provada.
4. Prove se a seguinte afirmação é verdadeira ou não. Para todos inteiros n, 4(n2 +n+1)−3n2 é um quadrado
perfeito.
5. Prove se a seguinte afirmação é verdadeira ou não. Existe um inteiro k tal que k ≥ 4 e 2k2−5k +2 é primo.
6. Prove se a seguinte afirmação é verdadeira ou não. Para todos inteiros n e m, se n−m é par então n3−m3
é par.
7. Prove se a seguinte afirmação é verdadeira ou não. O quociente de dois números racionais é um número
racional.
8. Prove se a seguinte afirmação é verdadeira ou não sem usar manipulação algébrica, ou seja, sem “resolver”
a equação. Suponha que m seja um número inteiro. Prove se 17|m na equação:
8 · 7 · 6 · 5 · 4 · 3 · 2 ·m ?= 17 · 16 · 15 · 14 · 13 · 12 · 11 · 10
9. Prove se a seguinte afirmação é verdadeira ou não:
∀ inteiros a, b e c, se a|b e a|c então a|(b + c)
10. Suponha que você está participando de uma promoção de uma loja que dá um cartão com números quando
um cliente faz uma compra. Se existem números nesse cartão que somam 100, então o cliente ganha um
prêmio de R$100,00. Um cliente recebe um cartão com os números
1
72 21 15 36 69 81 9 27 42 63
Sem fazer combinações de somas, mostre se o cliente irá ganhar o prêmio ou não.
11. Prove se a seguinte afirmação é verdadeira ou não: A soma de quatro números inteiros consecutivos não é
divisível por 4.
12. Prove que para qualquer inteiro ímpar n, bn
2
4 c = (
n−1
2 )(
n+1
2 ).
13. O resultado de 10 é um número irracional? Explique.
14. Prove por contradição que para todos os números primos a, b e c, a2 + b2 6= c2.
15. Prove por contraposição que se a soma de dois números reais é menor que 50 então pelo menos um dos
números é menor que 25.
16. Apresente um teorema cuja prova seja na forma geométrica.
17. Prove que se x2 + y = 13 e y 6= 4, em que x, y ∈ R, então x 6= 3.
18. Prove que se x > 0 e x < y, em que x, y ∈ R, então x2 < y2.
19. Prove que min(x, y) + max(x, y) = x + y para quaisquer números reais x e y.
20. Prove por contradição que há uma infinidade de números primos.
21. Prove que se n = ab, sendo a, b ∈ Z+, então a ≤
√
n ou b ≤
√
n.
2
Lista4 - Gabarito.pdf
Lista de Exercícios 4: Soluções
Sequências e Indução Matemática
UFMG/ICEx/DCC DCC111 – Matemática Discreta
Ciências Exatas & Engenharias 2o Semestre de 2014
1. O conjunto dos números racionais Q é enumerável, ou seja, é possível atribuir (associar) a cada número
racional um número natural. Abaixo, os números racionais positivos estão representados na forma de um
par ordenado onde o primeiro número representa o numerador e o segundo o denominador. Começando do
número racional 1 — par ordenado (1, 1) — é possível associar o número natural 1 e, seguindo o sentido das
setas, atribuir o próximo número natural definindo assim uma sequência de enumeração. Dado o número
racional positivo pq , qual é o número natural correspondente?
↑
...
...
...
...
... . . .
(1, 6) (2, 6) (3, 6) (4, 6) (5, 6) (6, 6). . .
↖
(1, 5) (2, 5) (3, 5) (4, 5) (5, 5) (6, 5). . .
↑ ↘ ↖
(1, 4) (2, 4) (3, 4) (4, 4) (5, 4) (6, 4). . .
↖ ↘ ↖
(1, 3) (2, 3) (3, 3) (4, 3) (5, 3) (6, 3). . .
↑ ↘ ↖ ↘ ↖
(1, 2) (2, 2) (3, 2) (4, 2) (5, 2) (6, 2). . .
↖ ↘ ↖ ↘ ↖
(1, 1)→(2, 1) (3, 1)→(4, 1) (5, 1)→(6, 1). . .
Resposta:
De acordo com o enunciado acima, a enumeração dos números racionais irá ocorrer da forma apresentada a
seguir (o número natural associado a cada número racional está entre colchetes):
↑
...
...
...
...
... . . .
(1, 6) (2, 6) (3, 6) (4, 6) (5, 6) (6, 6). . .
[21]
↖
(1, 5) (2, 5) (3, 5) (4, 5) (5, 5) (6, 5). . .
[11] [20]
↑ ↘ ↖
(1, 4) (2, 4) (3, 4) (4, 4) (5, 4) (6, 4). . .
[10] [12] [19]
↖ ↘ ↖
(1, 3) (2, 3) (3, 3) (4, 3) (5, 3) (6, 3). . .
[4] [9] [13] [18]
↑ ↘ ↖ ↘ ↖
(1, 2) (2, 2) (3, 2) (4, 2) (5, 2) (6, 2). . .
[3] [5] [8] [14] [17]
↖ ↘ ↖ ↘ ↖
(1, 1)→(2, 1) (3, 1)→(4, 1) (5, 1)→(6, 1). . .
[1] [2] [6] [7] [15] [16]
1a 2a 3a 4a 5a 6a
Diagonais
Pontos a observar:
• O número racional positivo pq é representado pelo par ordenado (p, q);
1
• A soma dos índices p e q dos pares ordenados ao longo de cada diagonal é a mesma. Na primeira
diagonal temos apenas um par ordenado, i.e., (1, 1), e a soma vale 2. A partir da segunda diagonal, as
somas dos índices valem 3, 4, 5, etc;
• Na primeira diagonal temos um par ordenado, na segunda dois, na terceira três e assim sucessivamente.
Isso significa que em cada diagonal temos (p + q)− 1 pares ordenados;
• Quando a soma p + q é um número ímpar, a enumeração ocorre de baixo para cima e, quando é par,
ocorre de cima para baixo;
• Para calcular o número natural k associado ao número racional (p, q) temos que saber quantos pares
ordenados existem nas diagonais anteriores à diagonal onde se encontra o par (p, q). Essa é a soma de
1 a (p + q)− 2, representada por S:
S ← [(p + q)− 2]× [(p + q)− 1]
2
.
• Finalmente, deve-se determinar o sentido da enumeração (de baixo para cima, ou vice-versa) para o
par (p, q):
se (p + q) mod 2 = 0 // (p + q) é um número par, i.e., a diagonal é de descida?
então k ← S + p // Sim, devemos somar a S o valor de p, que é o termo que cresce.
senão k ← S + q // Não, devemos somar a S o valor de q, que é o termo que cresce.
fimse
Observe que quando o sentido da enumeração é de cima para baixo ao longo da diagonal, o número
p deve ser somado a S para determinar a posição correta da enumeração. Quando o sentido da
enumeração for o contrário, o número q deve ser somado.
2. Prove por indução matemática que
12 + 22 + . . . + n2 =
n(n + 1)(2n + 1)
6
, n ≥ 1.
Resposta:
Prova (por indução matemática):
(a) Passo base: Para n = 1, 12 = 1 e n(n+1)(2n+1)6 =
1·2·3
6 = 1. O passo base é verdadeiro.
(b) Passo indutivo: se a fórmula é verdadeira para n = k, k ≥ 1 então deve ser verdadeira para n = k+1.
– Hipótese indutiva:
12 + 22 + . . . + k2 =
k(k + 1)(2k + 1)
6
, k ≥ 1
– Deve-se mostrar que:
12 + 22 + . . . + k2 + (k + 1)2 =
(k + 1)(k + 2)(2k + 3)
6
Sabe-se que:
12 + 22 + . . . + k2 + (k + 1)2 =
k(k + 1)(2k + 1)
6
+ (k + 1)2
=
k(k + 1)(2k + 1) + 6(k + 1)2
6
=
(k + 1)[k(2k + 1) + 6(k + 1)]
6
=
(k + 1)[2k2 + k + 6k + 6]
6
=
(k + 1)(2k2 + 7k + 6)
6
=
(k + 1)(k + 2)(2k + 3)
6
2
3. Prove por indução matemática que
1 + 3 + 5 + . . . + (2n− 1) = n2, n ≥ 1.
Resposta:
Prova (por indução matemática):
(a) Passo base: Para n = 1, 1 = 12. O passo base é verdadeiro.
(b) Passo indutivo: se a fórmula é verdadeira para n = k, k ≥ 1 então deve ser verdadeira para n = k+1.
– Hipótese indutiva:
1 + 3 + 5 + . . . + (2k − 1) = k2, k ≥ 1
– Deve-se mostrar que:
1 + 3 + 5 + . . . + (2k − 1) + (2k + 1) = (k + 1)2, k ≥ 1
Sabe-se que:
1 + 3 + 5 + . . . + (2k − 1) + (2k + 1) = k2 + (2k + 1)
= (k + 1)2
4. Prove por indução matemática que
13 + 23 + . . . + n3 = (1 + 2 + . . . + n)2, n ≥ 1.
Resposta:
Essa prova pode ser dividida em duas partes: (i) prova do somatório do lado direito e substituição pela
fórmula fechada, e (ii) prova do somatório do lado esquerdo. Sabe-se que a soma 1 + 2 + . . . + n, n ≥ 1, vale
n(n+1)
2 (esta prova pode ser obtida por indução matemática). Assim, temos que
13 + 23 + . . . + n3 =
n2(n + 1)2
4
, n ≥ 1.
Prova (por indução matemática):
(a) Passo base: Para n = 1, 13 = 1
2(1+1)2
4 . O passo base é verdadeiro.
(b) Passo indutivo: se a fórmula é verdadeira para n = k, k ≥ 1 então deve ser verdadeira para n = k+1.
– Hipótese indutiva:
13 + 23 + . . . + k3 =
k2(k + 1)2
4
, k ≥ 1
– Deve-se mostrar que:
13 + 23 + . . . + k3 + (k + 1)3 =
(k + 1)2(k + 2)2
4
, k ≥ 1
Sabe-se que:
13 + 23 + . . . + k3 + (k + 1)3 =
k2(k + 1)2
4
+ (k + 1)3
=
k2(k + 1)2
4
+ (k + 1)(k + 1)2
=
k2(k + 1)2
4
+
4(k + 1)(k + 1)2
4
=
(k + 1)2(k2 + 4k + 4)
4
=
(k + 1)2(k + 2)2
4
3
5. Prove por indução matemática que
2 · 1 + 2 · 2 + 2 · 3 + . . . + 2n = n2 + n, n ≥ 1.
Resposta:
Prova (por indução matemática):
(a) Passo base: Para n = 1, 2 · 1 = 2 e 12 + 1 = 2. O passo base é verdadeiro.
(b) Passo indutivo: se a fórmula é verdadeira para n = k, k ≥ 1 então deve ser verdadeira para n = k+1.
– Hipótese indutiva:
2 · 1 + 2 · 2 + 2 · 3 + . . . + 2k = k2 + k
= k(k + 1), k ≥ 1
– Deve-se mostrar que:
2 · 1 + 2 · 2 + . . . + 2k + 2(k + 1) = (k + 1)2 + (k + 1)
= (k + 1)[(k + 1) + 1]
= (k + 1)(k + 2), k ≥ 1
Sabe-se que:
2 · 1 + 2 · 2 + . . . + 2k + 2(k + 1) = k(k + 1) + 2(k + 1)
= k2 + k + 2k + 2
= k2 + 3k + 2
= (k + 1)(k + 2)
6. Prove por indução matemática que
n−1∑
i=1
i(i + 1) =
n(n− 1)(n + 1)
3
,∀ inteiros n ≥ 2.
Resposta:
Prova (por indução matemática):
(a) Passo base: Para n = 2,
∑n−1
i=1 i(i + 1) =
∑1
i=1 i(i + 1) = 1(1 + 1) = 2 e
n(n−1)(n+1)
2 =
2·1·3
3 = 2. O
passo base é verdadeiro.
(b) Passo indutivo: se a fórmula é verdadeira para n = k, k ≥ 2 então deve ser verdadeira para n = k+1.
– Hipótese indutiva:
k−1∑
i=1
i(i + 1) =
k(k − 1)(k + 1)
3
– Deve-se mostrar que:
k∑
i=1
i(i + 1) =
k(k + 1)(k + 2)
3
Sabe-se que:
k∑
i=1
i(i + 1) =
k−1∑
i=1
i(i + 1) + k(k + 1)
=
k(k − 1)(k + 1)
3
+ k(k + 1)
4
=
k(k − 1)(k + 1) + 3k(k + 1)
3
=
k(k + 1)[(k − 1) + 3]
3
=
k(k + 1)(k + 2)
3
7. Ache a fórmula fechada para a soma
1
1 · 2
+
1
2 · 3
+
1
3 · 4
+ . . . +
1
n(n + 1)
∀ inteiros n ≥ 1 e prove o seu resultado por indução matemática.
Resposta:
Prova (por indução matemática):
Somando os primeiros termos e simplificando temos que:
1
1 · 2
+
1
2 · 3
=
2
3
1
1 · 2
+
1
2 · 3
+
1
3 · 4
=
3
4
1
1 · 2
+
1
2 · 3
+
1
3 · 4
+
1
4 · 5
=
4
5
o que leva a conjectura que para todos os inteiros positivos n,
1
1 · 2
+
1
2 · 3
+
1
3 · 4
+ . . . +
1
n(n + 1)
=
n
n + 1
(a) Passo base: Para n = 1, 11·2 =
1
2 , que é o valor da fórmula fechada. O passo base é verdadeiro.
(b) Passo indutivo: se a fórmula é verdadeira para n = k, k ≥ 1 então deve ser verdadeira para n = k+1.
– Hipótese indutiva:
1
1 · 2
+
1
2 · 3
+
1
3 · 4
+ . . . +
1
k(k + 1)
=
k
k + 1
– Deve-se mostrar que:
1
1 · 2
+
1
2 · 3
+
1
3 · 4
+ . . . +
1
k(k + 1)
+
1
(k + 1)(k + 2)
=
k + 1
k + 2
Sabe-se que:
1
1 · 2
+
1
2 · 3
+
1
3 · 4
+ . . . +
1
k(k + 1)
+
1
(k + 1)(k + 2)
=
k
k + 1
+
1
(k + 1)(k + 2)
=
k(k + 2) + 1
(k + 1)(k + 2)
=
k2 + 2k + 1
(k + 1)(k + 2)
=
(k + 1)2
(k + 1)(k + 2)
=
k + 1
k + 2
8. Ache a fórmula fechada para o produto(
1− 1
2
)(
1− 1
3
)(
1− 1
4
)
. . .
(
1− 1
n
)
5
∀ inteiros n ≥ 2 e prove o seu resultado por indução matemática.
Resposta:
Seja a suposição que (
1− 1
2
)(
1− 1
3
)(
1− 1
4
)
. . .
(
1− 1
n
)
=
n∏
i=2
(
1− 1
i
)
=
1
n
∀ inteiros n ≥ 2. Deve-se provar que de fato essa suposição é verdadeira.
Prova (por indução matemática):
(a) Passo base: Para n = 2,
∏2
i=2(1 −
1
i ) = (1 −
1
2 ) =
1
2 e a fórmula fechada vale
1
2 . O passo base é
verdadeiro.
(b) Passo indutivo: se a fórmula é verdadeira para n = k, k ≥ 2 então deve ser verdadeira para n = k+1.
– Hipótese indutiva: (
1− 1
2
)(
1− 1
3
)(
1− 1
4
)
. . .
(
1− 1
k
)
=
k∏
i=2
(
1− 1
i
)
=
1
k
– Deve-se mostrar que:(
1− 1
2
)(
1− 1
3
)(
1− 1
4
)
. . .
(
1− 1
k
)(
1− 1
k + 1
)
=
k+1∏
i=2
(
1− 1
i
)
=
1
k + 1
Sabe-se que:
k+1∏
i=2
(
1− 1
i
)
=
k∏
i=2
(
1− 1
i
)
·
(
1− 1
k + 1
)
=
(
1
k
)
·
(
1− 1
k + 1
)
=
(
1
k
)
·
(
(k + 1)− 1
k + 1
)
=
1
k + 1
9. Ache a fórmula fechada para a soma
1
1 · 3
+
1
3 · 5
+ . . . +
1
(2n− 1) · (2n + 1)
∀ inteiros n ≥ 1 e prove o seu resultado por indução matemática.
Resposta:
Seja a suposição que
1
1 · 3
+
1
3 · 5
+ . . . +
1
(2n− 1) · (2n + 1)
=
n
2n + 1
∀ inteiros n ≥ 1.
Prova (por indução matemática):
(a) Passo base: Para n = 1, 1(2n−1)·(2n+1) =
1
(2·1−1)·(2·1+1) =
1
1·3 =
1
3 e a fórmula fechada vale
1
2·1+1 =
1
3 .
O passo base é verdadeiro.
(b) Passo indutivo: se a fórmula é verdadeira para n = k, k ≥ 1 então deve ser verdadeira para n = k+1.
– Hipótese indutiva:
1
1 · 3
+
1
3 · 5
+ . . . +
1
(2k − 1) · (2k + 1)
=
k
2k + 1
6
– Deve-se mostrar que:
1
1 · 3
+
1
3 · 5
+ . . . +
1
(2(k + 1)− 1) · (2(k + 1) + 1)
=
k + 1
2(k + 1) + 1
ou equivalentemente,
1
1 · 3
+
1
3 · 5
+ . . . +
1
(2k + 1) · (2k + 3)
=
k + 1
2k + 3
Sabe-se que:
1
1 · 3
+ . . . +
1
(2k − 1)(2k + 1)
+
1
(2k + 1)(2k + 3)
=
k
2k + 1
+
1
(2k + 1)(2k + 3)
=
k(2k + 3)
(2k + 1)(2k + 3)
+
1
(2k + 1)(2k + 3)
=
2k2 + 3k + 1
(2k + 1)(2k + 3)
=
(2k + 1)(k + 1)
(2k + 1)(2k + 3)
=
k + 1
2k + 3
10. Ache a fórmula fechada para a soma
n∑
i=2
1
(i− 1)i
,
∀ inteiros n ≥ 2 e prove o seu resultado por indução matemática.
Resposta:
Seja a suposição que
n∑
i=2
1
(i− 1)i
= 1− 1
n
∀ inteiros n ≥ 2. Deve-se provar que de fato essa suposição é verdadeira.
Prova (por indução matemática):
(a) Passo base: Para n = 2, os dois lados da equação valem 12 . O passo base é verdadeiro.
(b) Passo indutivo: se a fórmula é verdadeira para n = k, k ≥ 2 então deve ser verdadeira para n = k+1.
– Hipótese indutiva:
k∑
i=2
1
(i− 1)i
= 1− 1
k
, k ≥ 2.
– Deve-se mostrar que:
k+1∑
i=2
1
(i− 1)i
= 1− 1
k + 1
, k ≥ 2.
Sabe-se que:
k+1∑
i=2
1
(i− 1)i
=
k∑
i=2
1
(i− 1)i
+
1
k(k + 1)
= 1− 1
k
+
(
1
k
− 1
k + 1
)
= 1− 1
k + 1
7
11. Prove o seguinte predicado P (n) usando indução matemática:
P (n): Qualquer número inteiro positivo n ≥ 8 pode ser escrito como a soma de 3’s e 5’s.
Resposta:
Prova (por indução matemática fraca):
(a) Passo base: P (n0) = P (8): Para n0 = 8, temos que 8 = 3 + 5 e o predicado P é verdadeiro.
(b) Passo indutivo: se a fórmula é verdadeira para n = k então deve ser verdadeira para n = k + 1, i.e.,
P (k)→ P (k + 1).
– Suponha que a fórmula seja verdadeira para n = k, i.e.,
P (k) : k = 3a + 5b,
para a ≥ 0 e b ≥ 0. [hipótese indutiva]
– Deve-se mostrar que
P (k + 1) : k + 1 = 3a′ + 5b′,
para a′ ≥ 0 e b′ ≥ 0.
Dois casos a considerar para k + 1:
(i) b 6= 0: É possível substituir um 5 por dois 3’s quando é feita a soma de:
k + 1 = 3a + 5b + 1
= 3a + 5(b− 1) + 5 + 1
= 3a + 2·3 + 5(b− 1)
= 3a′ + 5b′
(ii) b = 0: Neste caso, deve haver pelo menos três 3’s para termos valores de n ≥ 9. Assim, temos:
k + 1 = 3a + 1
= 3(a− 3) + 3·3 + 1
= 3a′ + 2·5
= 3a′ + 5b′
[Isto era o que devia ser provado.]
12. Suponha que temos selos de 4 e 7 centavos. Prove que é possível ter qualquer valor de postagem de 18
centavos ou mais usando somente esses selos.
Resposta:
Prova (por indução matemática forte):
(a) Passo base: Para os seguintes valores de postagem p é possível usar apenas selos de 4 e 7 centavos.
p Selos
18 7 + 7 + 4
19 7 + 4 + 4 + 4
20 4 + 4 + 4 + 4 + 4
21 7 + 7 + 7
Assim, o passo base é verdadeiro.
(b) Passo indutivo: Vamos supor que para todos inteiros p, 18 ≤ p < k, p seja um valor de postagem
que pode ser obtido apenas com selos de 4 e 7 centavos. Vamos provar que a proposição também é
verdadeira para k.
Ao dividirmos k por 4 temos um quociente q e um resto entre 0 e 3. Ao dividirmos os valores de
postagem p ∈ [18, 21] temos também como resto os valores entre 0 e 3. Ou seja, k pode ser expresso
como um valor de postagem p entre 18 e 21 somando de um fator múltiplo de 4. Formalmente temos
que k ≡ p mod 4 para um valor de p ∈ [18, 21]. Isto é lido como: k é congruente com p módulo 4, o
que significa que existe um valor de p ∈ [18, 21] que quando dividido por 4 deixa o mesmo resto
que k
quando dividido por 4.
8
13. Prove por indução matemática que n2 < 2n, para todos inteiros n ≥ 5.
Resposta:
Prova (por indução matemática):
(a) Passo base: Para n = 5, a desigualdade 52 < 25 é verdadeira. Assim, o passo base é verdadeiro.
(b) Passo indutivo: se a afirmação é verdadeira para n = k, k ≥ 5 então deve ser verdadeira para n =
k + 1.
– Hipótese indutiva:
k2 < 2k
para todos inteiros k ≥ 5.
– Deve-se mostrar que:
(k + 1)2 < 2k+1
para todos inteiros k ≥ 5.
Sabe-se que:
(k + 1)2 = k2 + 2k + 1 < 2k + 2k + 1
pela hipótese indutiva. Sabe-se também que
2k + 1 < 2k
para k ≥ 3. Colocando estas desigualdades juntas, temos;
(k + 1)2 < 2k + 2k + 1 < 2k + 2k
14. Seja a seqüência a1, a2, a3, . . . definida como
a1 = 3
ak = 7ak−1,∀ inteiros k ≥ 2
Prove por indução matemática que an = 3 · 7n−1 para todos os inteiros n ≥ 1.
Resposta:
Prova (por indução matemática):
(a) Passo base: Para n = 1, an = a1 = 3 · 71−1 = 3 · 1 = 3. O passo base é verdadeiro.
(b) Passo indutivo: se a afirmação é verdadeira para n = k, k ≥ 1 então deve ser verdadeira para n =
k + 1.
– Hipótese indutiva:
ak = 3 · 7k−1
para todos inteiros k ≥ 1.
– Deve-se mostrar que:
ak+1 = 3 · 7(k+1)−1 = 3 · 7k
para todos inteiros k ≥ 1.
Sabe-se que:
ak+1 = 7ak, ∀ inteiros k ≥ 2
= 7 · (3 · 7k−1) Hipótese indutiva
= 3 · 7k
15. Seja a seqüência a1, a2, a3, . . . definida como
a1 = 1
a2 = 3
ak = ak−2 + 2ak−1,∀ inteiros k ≥ 3
Prove por indução matemática que an é ímpar para todos os inteiros n ≥ 1.
Resposta:
Prova (por indução matemática forte):
9
(a) Passo base: A propriedade é verdadeira para n = 1 e n = 2, já que a1 = 1 e a2 = 3, que são ímpares.
(b) Passo indutivo: Se k > 2 e a propriedade é verdadeira para todos i, 1 ≤ i < k, então deve ser verdadeira
para n = k.
– Hipótese indutiva: Seja k > 2 um inteiro e suponha que ai é ímpar para todos os inteiros i, 1 ≤ i < k.
– Deve-se mostrar que ak é ímpar. Sabe-se pela definição de
a1, a2, a3, . . . , an = ak−2 + 2ak−1
Sabe-se também que ak−2 é ímpar pela hipótese indutiva, já que 1 ≤ k − 2 < k e k > 2, e 2ak−1 é
par, pela definição de número par. Assim,
ak−2 + 2ak−1
é a soma de um número ímpar e um número par, que dá como resultado sempre um número ímpar.
16. Seja a seqüência g0, g1, g2, . . . definida como
g0 = 12
g1 = 29
gk = 5gk−1 − 6gk−2,∀ inteiros k ≥ 2
Prove por indução matemática que gn = 5 · 3n + 7 · 2n para todos os inteiros n ≥ 0.
Resposta:
Prova (por indução matemática forte):
(a) Passo base: Para n = 0, temos que g0 = 5 · 30 + 7 · 20 = 5 · 1 + 7 · 1 = 12 e para n = 1, temos que
g1 = 5 · 31 + 7 · 21 = 5 · 3 + 7 · 2 = 29. Logo, o passo base é verdadeiro.
(b) Passo indutivo: Se k > 1 e a propriedade é verdadeira para todos i, 1 ≤ i < k, então deve ser verdadeira
para n = k.
– Hipótese indutiva: Seja k > 1 um inteiro e suponha que gk = 5 · 3k + 7 · 2k para todos os inteiros i,
1 ≤ i < k.
– Deve-se mostrar que gk = 5 · 3k + 7 · 2k para n = k.
Sabe-se que:
gk = 5gk−1 − 6gk−2
= 5(5 · 3k−1 + 7 · 2k−1)− 6(5 · 3k−2 + 7 · 2k−2)
= 25 · 3k−1 + 35 · 2k−1 − 30 · 3k−2 − 42 · 2k−2
= 3k−2(25 · 3− 30) + 2k−2(35 · 2− 42)
= 3k−2 · 45 + 2k−2 · 28
= 3k−2(9 · 5) + 2k−2(4 · 7)
= 5 · 3k + 7 · 2k
17. Seja a seqüência h0, h1, h2, . . . definida como
h0 = 1
h1 = 2
h2 = 3
hk = hk−1 + hk−2 + hk−3,∀ inteiros k ≥ 3
Prove por indução matemática que hn ≤ 3n para todos os inteiros n ≥ 0.
Resposta:
Prova (por indução matemática forte):
10
(a) Passo base: A propriedade é verdadeira para
n hn 3n
0 h0 = 1 30 = 1
1 h1 = 2 31 = 3
2 h2 = 3 32 = 9
(b) Passo indutivo: Se k > 2 e a propriedade é verdadeira para todos i, 1 ≤ i < k, então deve ser verdadeira
para n = k.
– Hipótese indutiva: Seja k > 2 um inteiro e suponha que hi ≤ 3i para todos os inteiros i, 1 ≤ i < k.
– Deve-se mostrar que hk ≤ 3k. Sabe-se pela definição de
hk = hk−1 + hk−2 + hk−3
Sabe-se também que
hk−1 ≤ 3k−1
hk−2 ≤ 3k−2
hk−3 ≤ 3k−3
Logo,
hk = hk−1 + hk−2 + hk−3
≤ 3k−1 + 3k−2 + 3k−3
≤ 3k−3(32 + 31 + 1)
≤ 3k−3(3 · 4)
≤ 4 · 3k−2 ≤ 3k
já que 4 < 32.
18. Seja a seqüência x0, x1, x2, . . . definida como
x0 = 0
x1 = 1
xk = 5x3k−1 + 7xk−2,∀ inteiros k ≥ 2
Prove por indução matemática que se k é múltiplo de 3 então xk é par.
Resposta:
Prova (por indução matemática forte):
(a) Passo base:
Ao observarmos essa sequência temos:
i xi Número
0 0 par
1 1 ímpar
2 5 · 13 + 7 · 1 = 5 ímpar
3 5 · 53 + 7 · 0 = 632 par
...
...
...
Para os índices 0 e 3, múltiplos de 3, a proposição está correta e, assim, o passo base é verdadeiro. (Se
continuarmos a calcular os próximos valores de xi veremos que ambos x4 e x5 sáo números ímpares e
x6 é par.
(b) Passo indutivo: Se k ≥ 2 e a propriedade é verdadeira para todos i, 1 ≤ i < k, então deve ser verdadeira
para n = k.
11
– Hipótese indutiva: seja k = 3k′, ou seja, k é um múltiplo de 3. Os números x3k′−1 e x3k′−2 são
ímpares.
– Deve-se mostrar que x3k′ é par.
Sabe-se que
x3k′ = 5x33k′−1 + 7x3k′−2.
O primeiro termo terá como resultado um número ímpar já que x3k′−1 é ímpar que quando elevado a
uma potência cúbica multiplicado por um fator ímpar, fornece um número ímpar. O segundo termo
terá como resultado um número ímpar já que x3k′−2 é ímpar que quando multiplicado por um fator
ímpar, fornece um número ímpar. Assim, como x3k′ é o resultado da soma de dois números ímpares,
temos que x3k′ é par.
19. Seja a seqüência a0, a1, a2, . . . definida como
a0 = 0
a1 = 0
ak = ak−1 + 3k(k − 1),∀ inteiros k ≥ 2
Ache a fórmula fechada para o k-ésimo termo e prove por indução matemática.
Resposta:
Ao observarmos essa sequência temos:
i ai
0 0
1 0
2 0 + 1 · 32
3 1 · 32 + 2 · 33
4 1 · 32 + 2 · 33 + 3 · 34
...
...
ou seja, o termo
ak =
k∑
i=2
(i− 1)3i =
k∑
i=2
i3i −
k∑
i=2
3i.
Calcule essa soma sabendo que:
n−1∑
i=0
ixi =
x− nxn + (n− 1)xn+1
(1− x)2
.
Dica: transforme a soma
∑n−1
i=0 ix
i em uma soma
∑n
i=2 ix
i, ou seja, acrescente o termo para i = n e remova
os termos para i = 0 e i = 1.
20. Seja a seqüência a0, a1, a2, . . . definida como
a0 = 0
a1 = 1
ak = k − ak−1,∀ inteiros k ≥ 1
Ache a fórmula fechada para o k-ésimo termo e prove por indução matemática.
12
Resposta:
Ao observarmos essa sequência temos:
i ai
0 0
1 1
2 2− 1 = 1
3 3− 1 = 2
4 4− 2 = 2
5 5− 2 = 3
6 6− 3 = 3
7 7− 3 = 4
8 8− 4 = 4
...
...
ou seja, o termo
ak =
⌈
k
2
⌉
.
Se k é par então ak = k2 ; se k é ímpar então ak =
k+1
2 .
Prova (por indução matemática forte):
(a) Passo base: A propriedade é verdadeira para i = 0..8.
(b) Passo indutivo: Se k > 2 e a propriedade é verdadeira para todos i, 0 ≤ i < k, então deve ser verdadeira
para n = k.
– Hipótese indutiva: Se i é par então ai = i2 ; se i é ímpar então ai =
i+1
2 , para 0 ≤ i < k.
– Deve-se mostrar que essa proposição é verdadeira para k.
Sabe-se que ak = k − ak−1. Temos dois casos:
(i) k é par: ak = k − ak−1 = k − k2 =
k
2 , já que k − 1 é ímpar e ak−1 =
k−1+1
2 .
(ii) k é ímpar: ak = k − ak−1 = k − k−12 =
k+1
2 , já que k − 1 é par e ak−1 =
k−1
2 .
21. Prove por indução matemática que ∀n ≥ 1, 3n − 2 é ímpar.
Resposta:
Prova (por indução matemática):
(a) Passo base: Para n = 1, 31 − 2 = 1 é ímpar. O passo base é verdadeiro.
(b) Passo indutivo: se a afirmação é verdadeira para n = k, k ≥ 1 então deve ser verdadeira para n =
k + 1.
– Hipótese indutiva: ∀k ≥ 1, 3k − 2 é ímpar.
– Deve-se mostrar que: 3k+1 − 2 é ímpar.
Sabe-se que: 3k+1 − 2 = 3 · 3k − 2 = 3 · 3k − 6 + 4 = 3(3k − 2) + 4.
Pela hipótese indutiva 3k − 2 é um número ímpar que quando multiplicado por 3 e somado com 4
continua sendo um número ímpar.
13
Lista4.pdf
Lista de Exercícios 4
Sequências e Indução Matemática
UFMG/ICEx/DCC DCC111 – Matemática Discreta
Ciências Exatas & Engenharias 2o Semestre de 2014
1. O conjunto dos números racionais Q é enumerável, ou seja, é possível atribuir (associar) a cada número
racional um número natural. Abaixo, os números racionais positivos estão representados na forma de
um
par ordenado onde o primeiro número representa o numerador e o segundo o denominador. Começando do
número racional 1 — par ordenado (1, 1) — é possível associar o número natural 1 e, seguindo o sentido das
setas, atribuir o próximo número natural definindo assim uma sequência de enumeração. Dado o número
racional positivo pq , qual é o número natural correspondente?
↑
...
...
...
...
... . . .
(1, 6) (2, 6) (3, 6) (4, 6) (5, 6) (6, 6). . .
↖
(1, 5) (2, 5) (3, 5) (4, 5) (5, 5) (6, 5). . .
↑ ↘ ↖
(1, 4) (2, 4) (3, 4) (4, 4) (5, 4) (6, 4). . .
↖ ↘ ↖
(1, 3) (2, 3) (3, 3) (4, 3) (5, 3) (6, 3). . .
↑ ↘ ↖ ↘ ↖
(1, 2) (2, 2) (3, 2) (4, 2) (5, 2) (6, 2). . .
↖ ↘ ↖ ↘ ↖
(1, 1)→(2, 1) (3, 1)→(4, 1) (5, 1)→(6, 1). . .
2. Prove por indução matemática que
12 + 22 + . . . + n2 =
n(n + 1)(2n + 1)
6
, n ≥ 1.
3. Prove por indução matemática que
1 + 3 + 5 + . . . + (2n− 1) = n2, n ≥ 1.
4. Prove por indução matemática que
13 + 23 + . . . + n3 = (1 + 2 + . . . + n)2, n ≥ 1.
5. Prove por indução matemática que
2 · 1 + 2 · 2 + 2 · 3 + . . . + 2n = n2 + n, n ≥ 1.
6. Prove por indução matemática que
n−1∑
i=1
i(i + 1) =
n(n− 1)(n + 1)
3
,∀ inteiros n ≥ 2.
7. Ache a fórmula fechada para a soma
1
1 · 2
+
1
2 · 3
+
1
3 · 4
+ . . . +
1
n(n + 1)
∀ inteiros n ≥ 1 e prove o seu resultado por indução matemática.
1
8. Ache a fórmula fechada para o produto(
1− 1
2
)(
1− 1
3
)(
1− 1
4
)
. . .
(
1− 1
n
)
∀ inteiros n ≥ 2 e prove o seu resultado por indução matemática.
9. Ache a fórmula fechada para a soma
1
1 · 3
+
1
3 · 5
+ . . . +
1
(2n− 1) · (2n + 1)
∀ inteiros n ≥ 1 e prove o seu resultado por indução matemática.
10. Ache a fórmula fechada para a soma
n∑
i=2
1
(i− 1)i
,
∀ inteiros n ≥ 2 e prove o seu resultado por indução matemática.
11. Prove o seguinte predicado P (n) usando indução matemática:
P (n): Qualquer número inteiro positivo n ≥ 8 pode ser escrito como a soma de 3’s e 5’s.
12. Suponha que temos selos de 4 e 7 centavos. Prove que é possível ter qualquer valor de postagem de 18
centavos ou mais usando somente esses selos.
13. Prove por indução matemática que n2 < 2n, para todos inteiros n ≥ 5.
14. Seja a seqüência a1, a2, a3, . . . definida como
a1 = 3
ak = 7ak−1,∀ inteiros k ≥ 2
Prove por indução matemática que an = 3 · 7n−1 para todos os inteiros n ≥ 1.
15. Seja a seqüência a1, a2, a3, . . . definida como
a1 = 1
a2 = 3
ak = ak−2 + 2ak−1,∀ inteiros k ≥ 3
Prove por indução matemática que an é ímpar para todos os inteiros n ≥ 1.
16. Seja a seqüência g0, g1, g2, . . . definida como
g0 = 12
g1 = 29
gk = 5gk−1 − 6gk−2,∀ inteiros k ≥ 2
Prove por indução matemática que gn = 5 · 3n + 7 · 2n para todos os inteiros n ≥ 0.
17. Seja a seqüência h0, h1, h2, . . . definida como
h0 = 1
h1 = 2
h2 = 3
hk = hk−1 + hk−2 + hk−3,∀ inteiros k ≥ 3
Prove por indução matemática que hn ≤ 3n para todos os inteiros n ≥ 0.
2
18. Seja a seqüência x0, x1, x2, . . . definida como
x0 = 0
x1 = 1
xk = 5x3k−1 + 7xk−2,∀ inteiros k ≥ 2
Prove por indução matemática que se k é múltiplo de 3 então xk é par.
19. Seja a seqüência a0, a1, a2, . . . definida como
a0 = 0
a1 = 0
ak = ak−1 + 3k(k − 1),∀ inteiros k ≥ 2
Ache a fórmula fechada para o k-ésimo termo e prove por indução matemática.
20. Seja a seqüência a0, a1, a2, . . . definida como
a0 = 0
a1 = 1
ak = k − ak−1,∀ inteiros k ≥ 1
Ache a fórmula fechada para o k-ésimo termo e prove por indução matemática.
21. Prove por indução matemática que ∀n ≥ 1, 3n − 2 é ímpar.
3
Lista5- Gabarito.pdf
Lista de Exercícios 5: Soluções
Teoria dos Conjuntos
UFMG/ICEx/DCC DCC111 – Matemática Discreta
Ciências Exatas & Engenharias 2o Semestre de 2014
1. Escreva uma negação para a seguinte afirmação: ∀ conjuntos A, se A ⊆ R então A ⊆ Z. O que é verdadeira:
a afirmação ou sua negação? Justifique a sua resposta.
Resposta:
Negação: ∃ um conjunto A tal que A ⊆ R e A 6⊆ Z.
A negação é verdadeira. Por exemplo, seja A = {x ∈ R|0 < x < 2}. Então A ⊆ R mas A 6⊆ Z, já que, por
exemplo, 12 ∈ A.
2. Sejam os seguintes conjuntos:
A = {m ∈ Z|m = 2i− 1, para algum inteiro i}
B = {n ∈ Z|n = 3j + 2, para algum inteiro j}
Prove se A = B.
Resposta:
Tem-se que A 6= B. Por exemplo, 1 ∈ A, já que a = 2 · 1 − 1, mas 1 6∈ B. Se 1 fosse um elemento de B,
então teríamos 1 = 3j + 2, para algum inteiro j, o que daria:
3j + 2 = 1
3j = −1
j = −1
3
o que não é um número inteiro, ou seja, 1 6∈ B. Assim, existe um elemento em A que não está em B.
Conseqüentemente, A 6= B.
3. Seja A = {1, 2, 3}, B = {u, v} e C = {m, n}. Liste os elementos do conjunto A× (B × C).
Resposta:
A× (B × C) = {(1, (u, m)), (2, (u, m)), (3, (u, m)),
(1, (u, n)), (2, (u, n)), (3, (u, n)),
(1, (v, m)), (2, (v, m)), (3, (v, m)),
(1, (v, n)), (2, (v, n)), (3, (v, n))}
4. Prove que para todos os conjuntos A e B, B −A = B ∩Ac.
Resposta:
Prova que B −A ⊆ B ∩Ac:
– Suponha x ∈ B −A.
– Pela definição de diferença de conjuntos, x ∈ B e x 6∈ A.
– Pela definição de complemento, x ∈ B e x ∈ Ac.
– Pela definição de intersecção x ∈ B ∩Ac.
– Assim, pela definição de subconjunto, B −A ⊆ B ∩Ac.
1
Prova que B ∩Ac ⊆ B −A:
– Suponha x ∈ B ∩Ac.
– Pela definição de intersecção, x ∈ B e x ∈ Ac.
– Pela definição de complemento, x ∈ B e x 6∈ A.
– Pela definição de diferença de conjuntos, x ∈ B e x 6∈ A.
– Assim, pela definição de subconjunto, B ∩Ac ⊆ B −A.
Como B −A ⊆ B ∩Ac e B ∩Ac ⊆ B −A temos que B −A = B ∩Ac.
5. Prove por indução matemática que para todo inteiro n ≥ 1 e todos os conjuntos A1, A2, . . . , An e B,
(A1 −B) ∪ (A2 −B) ∪ . . . ∪ (An −B) = (A1 ∪A2 ∪ . . . An)−B
Resposta:
Prova (por indução matemática):
(a) Passo base: Para n = 1, a fórmula é expressa como A1 − B = A1 − B, que é claramente verdadeira.
Logo, o passo base é verdadeiro.
(b) Passo indutivo: se a fórmula é verdadeira para n = k, k ≥ 1 então deve ser verdadeira para n = k+1.
– Hipótese indutiva:
(A1 −B) ∪ (A2 −B) ∪ . . . ∪ (Ak −B) = (A1 ∪A2 ∪ . . . Ak)−B
– Deve-se mostrar que:
(A1 −B) ∪ (A2 −B) ∪ . . . ∪ (Ak+1 −B) = (A1 ∪A2 ∪ . . . Ak+1)−B
Tem-se que:
(A1 −B) ∪ (A2 −B) ∪ . . . ∪ (Ak+1 −B)
Que pode ser reescrito como:
[(A1 −B) ∪ (A2 −B) ∪ . . . ∪ (Ak −B)] ∪ (Ak+1 −B) =
Pela hipótese indutiva temos:
[(A1 ∪A2 ∪ . . . Ak)−B] ∪ (Ak+1 −B)
Pela propriedade de diferença, ou seja, (X − Z) ∪ (Y − Z) = (X ∪ Y )− Z, para conjuntos X, Y e Z,
tem-se que:
(A1 ∪A2 ∪ . . . Ak ∪Ak+1)−B
6. Prove que para todos os conjuntos A, B e C, (A−B)− (B − C) = A−B.
Resposta:
A expressão (A−B)− (B − C) pode ser expressa como
(A ∩Bc) ∩ (B ∩ Cc)c Representação alternativa para diferença
(A ∩Bc) ∩ (Bc ∪ C) De Morgan
((A ∩Bc) ∩Bc) ∪ ((A ∩Bc) ∩ C) Distributividade
(A ∩ (Bc ∩Bc)) ∪ (A ∩ (Bc ∩ C)) Associatividade
(A ∩Bc) ∪ (A ∩ (Bc ∩ C)) Lei da interseção
(A ∩Bc) ∪ (A ∩ (C ∩Bc)) Comutatividade
(A ∩Bc) ∪ ((A ∩ C) ∩Bc) Associatividade
(Bc ∩A) ∪ (Bc ∩ (A ∩ C)) Comutatividade
Bc ∩ (A ∪ (A ∩ C)) Distributividade
Bc ∩A Absorção
A ∩Bc Comutatividade
A−B Representação alternativa para diferença
2
7. Dados dois conjuntos A e B, defina a “diferença simétrica” de A e B, representada por A⊕B, como
A⊕B = (A−B) ∪ (B −A)
Prove se A⊕B = B ⊕A.
Resposta:
– Sejam A e B conjuntos quaisquer.
– Pela definição de ⊕, mostrar que A⊕B = B ⊕A é equivalente a mostrar que
(A−B) ∪ (B −A) = (B −A) ∪ (A−B)
– Esta igualdade é obtida diretamente da comutatividade da ∪.
8. Prove se para todos os conjuntos A, B e C, (A−B) e (C −B) são necessariamente disjuntos.
Resposta:
Não, ou seja, (A−B) ∩ (C −B) 6= ∅.
– Sejam os conjuntos A = {1, 2}, B = {3} e C = {1, 4}.
– Tem-se que A−B = {1, 2}.
– Tem-se que C −B = {1, 4}.
– No entanto, (A−B) ∩ (C −B) = {1} 6= ∅, ou seja, a intersecção não é um conjunto vazio.
9. Sejam os conjuntos A = {1} e B = {u, v}. Determine o conjunto potência de A×B, i.e., P(A×B).
Resposta:
A×B = {(1, u), (1, v)}
P(A×B) = {∅, {(1, u)}, {(1, v)}, {(1, u), (1, v)}}
10. Determine P(P(P(∅))).
Resposta:
O conjunto potência do conjunto