Universidade Federal de Uberlândia
Bacharelado em Ciência da Computação
Matemática para Ciência da Computação
Profa. Sandra de Amo
Solução da Primeira Prova para Casa : 8-9-2004
Questão 1
Dizer se é falso ou verdadeiro e provar sua afirmação:
1. Sejam x e y inteiros. x + y é impar se e somente se x é impar ou y é impar.
Solução : Precisamos demonstrar duas asserções( a ida e a volta). Somente se as
duas forem verdadeiras podemos concluir que a afirmação acima é verdadeira. Se
uma delas for falsa, já podemos concluir que a afirmação acima é falsa. Vamos então
tentar demonstrar a segunda asserção (a volta), isto é :
(a) se x e y são inteiros e x é impar ou y é impar então x + y é impar.
Isto é falso. Para provar isto precisamos dar um contraexemplo. O contraexemplo é o seguinte:
x = 3, y = 5. Temos que a hipótes é verdadeira : 3 é impar e 5 é impar. Logo a
alternativa “3 é impar OU 5 é impar se verifica (1 ∨ 1 = 1). MAS a conclusão
é FALSA !!! Pois 3 + 5 = 8 não é impar.
Portanto, a afirmação : “x + y é impar se e somente se x é impar ou y é impar.” É
FALSA !!!
2. Sejam x e y inteiros. xy é par se e somente se x é par ou y é par.
Solução : Precisamos demonstrar duas asserções( a ida e a volta). Somente se as
duas forem verdadeiras podemos concluir que a afirmação acima é verdadeira. Se
uma delas for falsa, já podemos concluir que a afirmação acima é falsa. Vamos então
tentar demonstrar a primeira asserção, isto é :
(a) se x e y são inteiros e xy é par então x é par ou y é par.
Vamos provar que isto é verdadeiro, fazendo uma prova por CONTRADIÇÃO:
i. Primeiro construimos a asserção “caminhando de trás para frente negando
tudo”:
Se x é impar E y é impar então xy é impar.
ii. Vamos mostrar de forma DIRETA que esta afirmação (esta última) é VERDADEIRA.
iii. Desenredando a hipótese :
x é impar : x = 2k + 1 para algum inteiro k.
y é impar : y = 2p + 1 para algum inteiro p.
iv. Desenredando a conclusão :
xy é impar : xy = 2m + 1 para algum inteiro m.
v. Encontrando um “elo” que permite passar da HIPOTESE (desenredada)
para a CONCLUSAO (desenredada):
x = 2k + 1, y = 2p + 1. Logo, xy = (2k + 1)(2p + 1) = 4kp + 2k + 2p + 1 =
2(2kp + k + p) + 1. Portanto, é verdade que xy = 2m + 1 para algum m :
basta considerar m = 2kp + k + p. Portanto conseguimos sair da hipotese
e chegar até a conclusão.
3. se x e y são inteiros e x é par ou y é par então xy é par.
Vamos provar que isto é verdadeiro, fazendo uma prova DIRETA:
(a) Desenredando a hipótese :
x é par : x = 2k para algum inteiro k.
y é par : y = 2p para algum inteiro p.
(b) Desenredando a conclusão :
xy é par : xy = 2m para algum inteiro m.
(c) Encontrando um “elo” que permite passar da HIPOTESE (desenredada) para
a CONCLUSAO (desenredada):
Hipótese desenredada : x = 2k OU y = 2p. Para chegar à conclusão, como
se trata de uma hipótese com OU, precisamos mostrar que de cada uma das
opções podemos chegar até a conclusão:
• opção 1 : x = 2k. Neste caso xy = 2ky. Logo xy = 2m, onde m = ky.
Portanto chegamos até a conclusão.
• opção 2 : y = 2p. Neste caso xy = x2p = 2xp. Logo xy = 2m, onde
m = xp. Portanto chegamos até a conclusão.
Questão 2
Suponha que já foi definido o que é distância entre dois pontos A e B no plano. Defina
os seguintes conceitos (marcados em itálico) em termos de distância (isto é complete as
frases abaixo com a definição correta dos termos escritos em itálico).
1. Sejam A, B, C tres pontos no plano. Dizemos que C está entre A e B se .... (complete dando o significado de está entre- utilize a noção distância entre dois pontos
- quanto vale distância (A,C) + distância(C,B) = ???)
Solução : Sejam A, B, C tres pontos no plano. Dizemos que C está entre A e B
se distância(A,C) + distância(B,C) = distância(A,B).
2. Sejam A, B, C tres pontos no plano. Dizemos que A, B, C são colineares, isto é,
estão na mesma linha reta se ... (complete dando o significado de colineares em
termos de distância ...).
Solução : Sejam A, B, C tres pontos no plano. Dizemos que A, B, C são colineares
se uma das condições abaixo se verifica :
(a) C está entre A e B OU
(b) A está entre B e C OU
(c) B está entre A e C.
Questão 3
Diga se é verdadeiro ou falso e prove sua afirmação :
1. A ∪ (B4C) ⊆ (A ∩ B)4(A ∩ C)
Consideremos a árvore de A ∪ (B4C):
x ∈ A ∪ (B4C)
x ∈ (B4C)
x∈A
x ∈ (B − C) ∪ (C − B)
x ∈ (B − C)
x ∈ (C − B)
x ∈ B, x 6∈ C
x ∈ C, x 6∈ B
Consideremos a árvore de (A ∩ B)4(A ∩ C):
x ∈ (A ∩ B)4(A ∩ C)
x ∈ ((A ∩ B) − (A ∩ C)) ∪ ((A ∩ C) − (A ∩ B))
x ∈ (A ∩ B) − (A ∩ C)
x ∈ (A ∩ B), x 6∈ (A ∩ C)
x ∈ (A ∩ B), x 6∈ A
x ∈ A, x ∈ B, x 6∈ A
x ∈ (A ∩ B), x 6∈ C
x ∈ A, x ∈ B, x 6∈ C
x ∈ (A ∩ C) − (A ∩ B)
x ∈ (A ∩ C), x 6∈ (A ∩ B)
x ∈ (A ∩ C), x 6∈ A
x ∈ A, x ∈ C, x 6∈ A
x ∈ (A ∩ C), x 6∈ B
x ∈ A, x ∈ C, x 6∈ B
A primeira e terceira folhas da segunda árvore acima são eliminadas pois correspondem a um absurdo x ∈ A e x 6∈ A.
Considere a primeira folha da primeira árvore x ∈ A. Esta folha não corresponde
nem à segunda folha da árvore 2 nem à quarta folha da árvore 2. Realmente, se
você considerar um caso em que x ∈ (A ∩ B ∩ C) você terá:
primeira folha da árvore 1 é verdadeira, mas :
segunda folha da árvore 2 é falsa
quarta folha da árvore 2 é falsa.
Logo podemos concluir que é falsa a afirmação :
A ∪ (B4C) ⊆ (A ∩ B)4(A ∩ C).
2. (A ∩ B)4(A ∩ C) ⊆ A ∩ (B4C)
A árvore de (A ∩ B)4(A ∩ C) é a segunda árvore do item anterior.
Consideremos a árvore de A ∩ (B4C) :
x ∈ A ∩ (B4C)
x ∈ A, x ∈ (B4C)
x ∈ A, x ∈ (B − C) ∪ (C − B)
x ∈ A, x ∈ (B − C)
x ∈ A, x ∈ B, x 6∈ C
x ∈ A, x ∈ (C − B)
x ∈ A, x ∈ C, x 6∈ B
Chamaremos esta árvore de “árvore 3” e a segunda árvore do item anterior de
“árvore 2”. Fazendo a análise das duas árvores para ver se a segunda está contida
na terceira:
a segunda folha da árvore 2 é idêntica à primeira folha da árvore 3.
a quarta folha da árvore 2 é idêntica à segunda folha da árvore 3.
Como a primeira e terceira folhas da árvore 2 foram eliminadas, podemos concluir
portanto que todas as folhas válidas da árvore 2 correspondem a alguma folha válida
da árvore 3.
Logo, a afirmação de que (A ∩ B)4(A ∩ C) ⊆ A ∩ (B4C) é verdadeira.