MC358 - Lista 01

MC358 - Lista 01
Questão 1)
A proposição 𝑎 → 𝑏 equivale a ¬𝑎 ∨ 𝑏
Por De Morgan:
¬𝑎 ∨ 𝑏 ⇔ ¬(¬(¬𝑎 ∨ 𝑏)) ⇔ (¬(¬¬𝑎 ∧ ¬𝑏)) ⇔ ¬(𝑎 ∧ ¬𝑏)
Por definição 𝑝 ↓ 𝑞 ⇔ ¬𝑝 ∨ ¬𝑞
Então:
¬(𝑎 ∧ ¬𝑏) ⇔ 𝑎 ↓ ¬ 𝑏 (i)
Para expressar ¬𝑏 em função de ↓:
¬𝑏 ⇔ ¬𝑏 ∨ ¬𝑏
¬𝑏 ⇔ 𝑏 ↓ 𝑏 (ii)
Substituindo (ii) em (i):
𝑎 ↓ ¬ 𝑏 ⇔ 𝑎 ↓ (𝑏 ↓ 𝑏)
Portanto,
𝑎 → 𝑏 ⇔ 𝑎 ↓ (𝑏 ↓ 𝑏)
Questão 2)
∃x (P(x) ∨ Q(x))
= ¬¬∃x (P(x) ∨ Q(x))
= ¬∀𝑥¬(P(x) ∨ Q(x))
= ¬∀𝑥(¬P(x) ∧ ¬Q(x))
= ¬(∀𝑥¬P(x) ∧ ∀𝑥¬Q(x))
= ¬∀𝑥¬¬P(x) ∨ ∀𝑥¬¬Q(x)
= ∃xP(x) ∨ ∃xQ(x)
cqd
Questão 3)
¬((∀x.(K(x) ↔ ∀z.¬A(x, z))) ∧ (∀x.(H(x) → ∃y.(B(x, y) ∧ D(x, y)))))
Por De Morgan:
¬(∀x.(K(x) ↔ ∀z.¬A(x, z))) ∨ ¬(∀x.(H(x) → ∃y.(B(x, y) ∧ D(x, y))))
Negando a primeira parte:

¬(∀x.(K(x) ↔ ∀z.¬A(x, z))) ⇔ ∃x.¬(K(x) ↔ ∀z.¬A(x, z))
Para a equivalência:
¬(P↔Q)⇔(P∧¬Q)∨(¬P∧Q)
Assim:
¬(K(x) ↔ ∀z.¬A(x, z)) ⇔(K(x)∧¬(∀z.¬A(x, z)))∨(¬K(x)∧(∀z.¬A(x, z)))
A negação de:
¬(∀z.¬A(x, z)) ⇔ ∃z.¬¬A(x, z) ⇔ ∃z.A(x, z)
Logo:
(K(x)∧¬(∀z.¬A(x, z)))∨(¬K(x)∧(∀z.¬A(x, z))) ⇔ (K(x)∧∃z.A(x, z))∨(¬K(x)∧(∀z.¬A(x,
z)))
Negando a segunda parte:
¬(∀x.(H(x) → ∃y.(B(x, y) ∧ D(x, y)))) ⇔ ∃x.¬(H(x) → ∃y.(B(x, y) ∧ D(x, y)))
Agora, negamos a implicação H(x)→∃y.(B(x,y)∧D(x,y))
¬(H(x) → ∃y.(B(x, y) ∧ D(x, y))) ⇔ H(x)∧¬∃y.(B(x,y)∧D(x,y))
Negando ∃y.(B(x,y)∧D(x,y))
¬∃y.(B(x,y)∧D(x,y)) ⇔ ∀y¬(B(x,y)∧D(x,y)) ⇔ ∀y( ¬B(x,y) ∨ ¬D(x,y))
Portanto:
¬(∀x.(H(x) → ∃y.(B(x, y) ∧ D(x, y)))) ⇔ ∃x H(x)∧¬ ∀y( ¬B(x,y) ∨ ¬D(x,y))
Combinando as equações:
∃x(K(x)∧∃z.A(x, z))∨(¬K(x)∧(∀z.¬A(x, z)))∨∃x[H(x)∧∀y.(¬B(x,y)∨¬D(x,y))]
Questão 4
∃p∃g[(∀p’(P(p’)∧p’≠p→¬M(p’,g))∧M(p,g)∧¬W(p,g))∧P(p)∧G(g)]
∃p∃g: Existe uma pessoa p e um portão g.

∀p’ (P(p’)∧p’≠p→¬M(p’,g)): Para qualquer pessoa p’ diferente de p, p’ não tem permissão
para passar por g.
M(p,g): A pessoa p tem permissão para passar por g.
¬W(p,g): A pessoa p nunca passará por g.
Questão 5
Podemos escrever:
x ∈ A → x ∈ B ⇔ ¬ (x ∈ A) ∨ x ∈ B
¬(x ∈ A → x ∈ B) ⇔ ¬(¬ (x ∈ A) ∨ x ∈ B)
Por De Morgan:
¬(¬ (x ∈ A) ∨ x ∈ B) ⇔ x ∈ A ∧ ¬(x ∈ B)
Portanto:
S={x∣x ∈ A ∧ ¬(x ∈ B)}
Logo, S contém todos os elementos de A que não estão em B. O que seria a diferença entre
os conjuntos A e B. Assim,
S=A\B= A∩𝐵
Questão 6
a) A \ B é o conjunto dos elementos que estão em A e não estão em B
A∖B={x∣x∈A e x∉B}
O complemento de B é:
𝐵 ={x∣x∉B}
A interseção de A ∩ 𝐵 portanto é:
A ∩ 𝐵 = {x∣x∈A e x∉B}
Logo, as duas definições são equivalentes. Portanto:
A\B= A∩𝐵
b) Diferença simétrica:
AΔB=(A∪B)∖(A∩B)
Pela definição de anteriormente provada, onde C \ D = C ∩ 𝐷 :

(A∪B)∖(A∩B) = (A∪B)∩(𝐴 ∩ 𝐵)
Usando De Morgan:
(𝐴 ∩ 𝐵) = 𝐴 ∪ 𝐵
Assim: AΔB=(A∪B)∩(𝐴 ∪ 𝐵)
c) A partir da definição anteriormente provada, AΔB=(A∪B)∩(𝐴 ∪ 𝐵), vamos distribuir a

intersecção sobre a união:
(A∪B)∩(𝐴 ∪ 𝐵) = [(A∩𝐴)∪(A∩ 𝐵)]∪[(B∩𝐴)∪(B∩𝐵)]
Lembrando que A∩𝐴 = ⊘ e, da mesma forma, B∩𝐵 = ⊘:
(A∪B)∩(𝐴 ∪ 𝐵) = (A∩ 𝐵)∪(B∩𝐴)
Assim: AΔB = (A∩ 𝐵)∪(B∩𝐴)
d) Da definição: AΔB=(A∪B)∖(A∩B) e BΔC=(B∪C)∖B∩C)
(AΔB)ΔC = [(A∪B)∖(A∩B)]ΔC
(AΔB)ΔC = {[(A∪B)∖(A∩B)]∪C} \ {[(A∪B)∖(A∩B)]∩C} (i)
AΔ( BΔC) = AΔ[(B∪C)∖B∩C)]
AΔ(BΔC) = {A∪[(B∪C)∖B∩C)]} \ {A∩[(B∪C)∖B∩C)]} (ii)
(AΔB)ΔC resulta nos elementos que estão em exatamente um dos conjuntos A, B ou

C. Da mesma forma, AΔ(BΔC) também resulta nos elementos que estão em
exatamente um dos conjuntos A, B ou C. Portanto, mostramos que:
(AΔB)ΔC=AΔ(BΔC)
Questão 7)
𝑝
Se 𝑥 = 𝑞
:
𝑝 2
𝑎( )𝑞
+𝑏 ( )+ 𝑐
𝑝
𝑞
= 0 (× 𝑞²)
𝑎𝑝² + 𝑏𝑝𝑞 + 𝑐𝑞² = 0
Como a, b e c são ímpares, vamos analisar os casos de p e q:
Caso 1: p é ímpar e q é ímpar
➢ p² será ímpar.
➢ q² será ímpar.
➢ ap² será ímpar, pois o produto de dois ímpares é ímpar.
➢ bpq será ímpar, pois o produto de três ímpares é ímpar.
➢ cq² será ímpar.
Logo, todos os termos são ímpares e a soma de três ímpares é ímpar, mas temos que igual
a zero, que é par, o que é absurdo.
Caso 2: p é ímpar e q é par
● p² será ímpar.
● q² será par.
● ap² será ímpar.
● bpq será par, pois pq é par.
● cq² será par.
Logo, temos a soma de um ímpar (ap²) com dois pares (bpq e cq²), a soma de um ímpar
com pares é ímpar, mas temos que igual a zero, que é par, o que é absurdo.
Caso 3: p é par e q é ímpar
● p² será par.
● q² será ímpar.
● ap² será par.
● bpq será par, pois pq é par.
● cq² será ímpar.
Logo, temos a soma de dois pares (ap² e bpq) com um ímpar (cq²), a soma de pares e
ímpares é ímpar, mas temos que igual a zero, que é par, o que é absurdo.
Assim, em todos os casos possíveis, tivemos absurdo. Portanto, não é possível que a
equação tenha raízes racionais se a, b e c são todos inteiros ímpares.
Questão 8)
(𝑥 − 3)𝑦² ⇔ (∃𝑘 ∈ 𝑍 | 𝑦 = 2𝑘) ∨ (∃𝑙 ∈ 𝑍 | 𝑥 = 2𝑙 + 1)
Primeiro vamos analisar a volta da proposição acima:
Caso 1:
𝑦 = 2𝑘
𝑦 ² = (2𝑘)² = 4𝑘²
De tal forma que (𝑥 − 3)𝑦² = (𝑥 − 3)4𝑘, assim (𝑥 − 3)𝑦² será múltiplo de 4 e,

portanto, par.
Caso 2:
𝑥 = 2𝑙 + 1
𝑥 − 3 = (2𝑙 + 1) − 3 = 2𝑙 − 2 = 2(𝑙 − 1)
De tal forma que (𝑥 − 3)𝑦² = 2(𝑙 − 1)𝑦², assim (𝑥 − 3)𝑦² será múltiplo de 2 e,
portanto, par.
Provando portanto a volta.
Agora, vamos analisar a ida:
Supondo (𝑥 − 3)𝑦² temos que mostrar que x é ímpar ou y é par:
Se y fosse ímpar, y² seria ímpar de forma que para termos a equação par, x–3 deverá ser
par, então o x deverá ser ímpar. Se y fosse par, então y² seria par e a equação seria par
independente do x. O que prova a ida.
Questão 9)
Para a equação 𝑥! = 𝑥³ − 𝑥, vamos testar alguns valores onde 𝑥 ∈ 𝑁:
Para x = 1:
1! = 1³ − 1
1 = 0 , o que é absurdo, portanto 1 não é solução.
Para x = 2:
2! = 2³ - 2
2 = 6, o que é absurdo, portanto 2 não é solução.
Para x = 3:
3! = 3³ - 3
6 = 24, o que é absurdo, portato 3 não é solução.
Para x = 4:
4! = 4³ - 4
24 = 60, o que é absurdo, portanto 4 não é solução
Para x = 5:
5! = 5³ - 5
120 = 120, o que é válido, portanto 5 é uma solução.
Para valores maiores de x, o crescimento de x! é bem mais rapido que o de x³ - x. Por

exemplo:
Para x = 6:
6! = 6³ - 6
720 = 210, absurdo!
Para x = 7:
7! = 7³ - 7
5040 = 336, absurdo!
Ou seja, para valores em que x ≥ 6, x! >> x³ - x, de forma que a única solução possível
onde 𝑥 ∈ 𝑁 é x = 5.
Questão 10)
Cada movimento do cavalo altera a cor da casa ocupada.O tabuleiro possui 64 casas, um
caminho que cobre todas as casas do tabuleiro terá exatamente 63 movimentos, o que é
ímpar. Assim, se o cavalo começa em uma casa preta, ele terminará em uma casa branca
após 63 movimentos, e vice-versa. No tabuleiro de xadrez, a1 e h8 têm a mesma cor
(preta). Como o cavalo alterna a cor das casas a cada movimento, ele não pode terminar
em uma casa da mesma cor que a casa inicial após um número ímpar de movimentos.

MC358 - Lista 01

Enviado por

Direitos autorais:

Formatos disponíveis

MC358 - Lista 01

Enviado por

Dados do documento

Direitos autorais

Formatos disponíveis

Compartilhar este documento

Compartilhar ou incorporar documento

Opções de compartilhamento

Você considera este documento útil?

Este conteúdo é inapropriado?

Direitos autorais:

Formatos disponíveis

MC358 - Lista 01

Enviado por

Direitos autorais:

Formatos disponíveis

MC358 - Lista 01

Negando a primeira parte:

∃p∃g: Existe uma pessoa p e um portão g.

Pela definição de anteriormente provada, onde C \ D = C ∩ 𝐷 :

c) A partir da definição anteriormente provada, AΔB=(A∪B)∩(𝐴 ∪ 𝐵), vamos distribuir a

(A∪B)∩(𝐴 ∪ 𝐵) = [(A∩𝐴)∪(A∩ 𝐵)]∪[(B∩𝐴)∪(B∩𝐵)]

Lembrando que A∩𝐴 = ⊘ e, da mesma forma, B∩𝐵 = ⊘:

(A∪B)∩(𝐴 ∪ 𝐵) = (A∩ 𝐵)∪(B∩𝐴)

Assim: AΔB = (A∩ 𝐵)∪(B∩𝐴)

d) Da definição: AΔB=(A∪B)∖(A∩B) e BΔC=(B∪C)∖B∩C)

(AΔB)ΔC = {[(A∪B)∖(A∩B)]∪C} \ {[(A∪B)∖(A∩B)]∩C} (i)

AΔ( BΔC) = AΔ[(B∪C)∖B∩C)]

AΔ(BΔC) = {A∪[(B∪C)∖B∩C)]} \ {A∩[(B∪C)∖B∩C)]} (ii)

(AΔB)ΔC resulta nos elementos que estão em exatamente um dos conjuntos A, B ou

𝑎𝑝² + 𝑏𝑝𝑞 + 𝑐𝑞² = 0

Como a, b e c são ímpares, vamos analisar os casos de p e q:

Caso 1: p é ímpar e q é ímpar

Caso 2: p é ímpar e q é par

Caso 3: p é par e q é ímpar

(𝑥 − 3)𝑦² ⇔ (∃𝑘 ∈ 𝑍 | 𝑦 = 2𝑘) ∨ (∃𝑙 ∈ 𝑍 | 𝑥 = 2𝑙 + 1)

Primeiro vamos analisar a volta da proposição acima:

De tal forma que (𝑥 − 3)𝑦² = (𝑥 − 3)4𝑘, assim (𝑥 − 3)𝑦² será múltiplo de 4 e,

Provando portanto a volta.

Agora, vamos analisar a ida:

Supondo (𝑥 − 3)𝑦² temos que mostrar que x é ímpar ou y é par:

Para a equação 𝑥! = 𝑥³ − 𝑥, vamos testar alguns valores onde 𝑥 ∈ 𝑁:

1 = 0 , o que é absurdo, portanto 1 não é solução.

6 = 24, o que é absurdo, portato 3 não é solução.

24 = 60, o que é absurdo, portanto 4 não é solução

120 = 120, o que é válido, portanto 5 é uma solução.

Para valores maiores de x, o crescimento de x! é bem mais rapido que o de x³ - x. Por

720 = 210, absurdo!

5040 = 336, absurdo!

Você também pode gostar