FMC-Lista3

Prévia do material em texto

UFG - Instituto de Informática Fundamentos de Matemática para Computação
CC / SI / ES Prof.a Juliana Félix1
3a Lista de Exercícios – 2019.2
Local de entrega: em sala
Data de entrega: 07/10/2019.
LEIA ATENTAMENTE AS INSTRUÇÕES:
• A lista é individual.
• A lista deve ser feita a mão. Se você acredita que seu caso deve ser uma exceção por algum motivo, envie um
e-mail para julianafelix@inf.ufg.br ou me procure em sala para discutirmos outra forma de entrega.
• Seu nome e matrícula devem aparecer na primeira folha de soluções.
• Indique de forma organizada a numeração de cada exercício resolvido.
• A lista pode ser feita a lápis.
• JUSTIFIQUE COM CLAREZA OS PASSOS SEGUIDOS PARA RESOLVER CADA UM DOS EXERCÍ-
CIOS.
• APENAS FOLHAS DE PAPEL A4 OU FOLHAS DE PAPEL ALMAÇO (COM OU SEM PAUTA) SERÃO
ACEITAS. Não entregue suas soluções em folha de caderno ou fichário!
Lógica Matemática e Demosntração Direta
1. Utilize as leis de De Morgan para escrever a negação das seguintes declarações. Lembre-se de escrever sua
resposta detalhadamente
(a) Maria é casada e João é solteiro.
(b) Cássio estudará para a prova de FMC ou irá ao cinema.
(c) O ônibus estava atrasado ou o relógio de João estava marcando a hora errada.
(d) x ≥ 0 ou x ≤ −10.
(e) −1 < x ≤ 4.
2. Utilize a tabela de equivalências lógicas (disponibilizada no sigaa) para mostrar as seguintes equivalências.
Respostas utilizando a tabela-verdade NÃO serão aceitas.
(a) ¬(¬p ∧ q) ∧ (p ∨ q) ≡ p
(b) ¬((¬p ∧ q) ∨ (¬p ∧ ¬q)) ∨ (p ∧ q) ≡ p
(c) ((¬p ∧ q) ∧ (q ∧ r)) ∧ ¬q ≡ F
(d) (p ∧ (q ∧ r))→ (p ∨ q) ≡ V
(e) (q ↔ p) ∧ (¬p→ q) ≡ (p ∧ q) (difícil)
3. Considere a seguinte frase: "Se eu tiver uma boa noite de sono, eu me sinto disposto a estudar FMC na manhã
seguinte.". Defina símbolos e escreva uma fórmula lógica que corresponda a esta frase. Depois, escreva a
contrapositiva, inversa e oposta da fórmula obtida, assim como a frase equivalente em português.
4. Escreva utilizando quantificadores e linguagem formal a seguinte frase: "A soma de quaisquer dois números
inteiros é um inteiro."
5. Qual das seguintes afirmações é a negação de "Todos os cachorros são leais."? Basta apontar a(s) letra(s) que
satisfaz(em) a pergunta.
(a) Todos os cachorros são desleais.
(b) Nenhum cachorro é desleal.
(c) Existe um cachorro que é leal.
(d) Nem todos os cachorros são leais.
(e) Nenhum animal que não é cachorro é leal.
(f) Existem animais leais que são cachorros.
1e-mail: julianafelix@inf.ufg.br
6. Para este exercício, considere que D = E = {−2,−1, 0, 1, 2}. Verifique se as seguintes afirmações são verdadeiras
ou falsas. Demonstre ou apresente um contra-exemplo.
(a) ∀x, y ∈ R, se x2 = y2, então x = y.
(b) ∀x ∈ D,∃y ∈ E | x2 − y2 ≤ 2.
(c) ∃x ∈ D | ∀y ∈ E, x+ y = −1.
7. Escreva a negação de cada um dos itens abaixo.
(a) ∀x, y ∈ R, se x2 = y2, então x = y.
(b) ∀x ∈ D,∃y ∈ E | x2 − y2 ≤ 2.
(c) ∃x ∈ D | ∀y ∈ E, x+ y = −1.
8. Sejam a, b, c ∈ Z. Responda verdadeiro ou falso. Justifique suas afirmações (demonstre ou exiba um contraexem-
plo). Obs.: Lembre-se que apenas em casos onde a afirmação é falsa é válido mostrar um exemplo de valores
cuja condição é satisfeita mas a consequência não. Se a afirmação for verdadeira, sua resposta deve trabalhar
com valores a,b,c inteiros que podem assumir quaisquer valores. Um exemplo de solução genérica segue na letra
(a).
(a) Sejam a, b, c ∈ Z. Se a|b e a|c, então a|(b+ c).
Resposta:
Se a | b, então pela definição de divide, ∃k1 ∈ Z tal que b = a · k1.
Se a | c, então pela definição de divide, ∃k2 ∈ Z tal que c = a · k2.
Queremos mostrar que a | (b+ c), ou seja, que ∃k3 ∈ Z tal que (b+ c) = a · k3.
Mas, se b = a · k1 e c = a · k2, então sabemos que
(b+ c) = a · k1 + a · k2
= a · (k1 + k2) (colocando a em evidência)
No entanto, sabemos que a soma de um inteiro k1 com outro inteiro k2 também resultará em um inteiro,
pois os inteiros são fechados para a adição. Assim, ao tomar k3 = k1 + k2, temos:
(b+ c) = a · (k3), (onde k3 = k1 + k2)
que é onde queríamos chegar.
Portanto, foi provado que ∃k3 = k1 + k2, com k1, k2, k3 ∈ Z tal que (b + c) = a · k3 e, consequentemente,
temos que a | (b+ c).
(b) Sejam a, b, c ∈ Z. Se a|b e b|c, então a|c.
(c) Sejam a, b, c ∈ Z. Se a|b e a|c, então a|(5b+ 9c).
(d) Sejam a, b, c ∈ Z. Se a|b e b|c então c|a.
(e) Sejam a, b ∈ Z. Se a|b e b|a então a = b.
(f) Sejam a, b, c ∈ Z. Se b|a e c|a então (b · c)|a.