Logica, Tecnicas de Prova e Conjuntos

Prévia do material em texto

2017.2 CB 0661 - MATEMÁTICA DISCRETA (PROF. FABRICIO)
LISTA 1-1
Cada
√
denota um nível de dificuldade:
√
fácil,
√√
médio e
√√√
difícil.
1 Introdução à Lógica Matemática
1.(
√
) Qual o valor das seguintes sentenças lógicas.
(a) Verdadeiro ∧ Verdadeiro ∧ Verdadeiro ∧ Falso
(b) (¬Verdadeiro) ∨ Verdadeiro
(c) ¬(Verdadeiro ∨ Verdadeiro)
(d) Verdadeiro ∨ (A ∧ ¬A)
2.(
√√
) Prove ou desprove que os seguintes pares de fórmulas lógicas são equivalentes.
(a) (x ∨ y)→ z e (x→ z) ∧ (y → z)
(b) (x ∨ y) e (x ∧ ¬y) ∨ (¬x ∧ y)
(c) ((x→ y) ∧ (y → z))→ (x→ z) e Verdadeiro
(d) (x→ y) ∧ (¬x→ y) ∧ ¬y e Falso
3.(
√√√
) Um náufrago chega em uma ilha onde convivem duas tribos A e B. Todos os nativos da tribo A sempre
mentem. Todos os nativos da tribo B sempre falam a verdade. Ao se deparar com um nativo, o náufrago
fez a seguinte pergunta:
“Existe ouro nesta ilha ?”
O nativo respondeu:
“Existe ouro na ilha se e somente se eu falo a verdade.”
Usando lógica matemática para analisar a resposta do nativo, descubra se existe ou não ouro na ilha.
4.(
√√
) Prove as seguintes equivalências lógicas (tente fazer de duas formas, uma usando a tabela verdade, outra
usando equivalências lógicas):
(a) A↔ B ≡ (A ∧B) ∨ (¬A ∧ ¬B)
(b) A↔ B ≡ ¬A↔ ¬B
(c) (x ∨ y)→ z ≡ (x→ z) ∧ (y → z)
5.(
√
) Se P é uma proposição lógica envolvendo n variáveis, então quantas linhas tem a tabela verdade de P ?
6.(
√√
) Uma tautologia é uma proposição que é sempre verdadeira, Prove que as proposições a seguir são tautolo-
gias.
(a) (x ∨ y) ∨ (x ∨ ¬y)
(b) (x ∧ (x→ y))→ y
(c) ((x→ y) ∧ (y → z))→ (x→ z)
7.(
√√
) Uma contradição é uma proposição que é sempre falsa. Prove que as proposições a seguir são contradições.
(a) (x ∨ y) ∧ (x ∨ ¬y) ∧ (¬x)
(b) x ∧ (x→ y) ∧ (¬y)
(c) (x→ y) ∧ ((¬x)→ y) ∧ (¬y)
8.(
√
) Escreva as sentenças abaixo usando linguagem lógica. Em seguida, escreva suas negações.
(a) Todo inteiro é primo.
(b) Há um inteiro que não é primo nem composto.
(c) Existe um inteiro cujo quadrado é 2.
1
(d) Para todo inteiro x, existe um inteiro y tal que xy = 1.
(e) Existe um inteiro que quando multiplicado por qualquer outro inteiro sempre resulta em 0.
9.(
√
) As proposições abaixo são equivalentes? Argumente.
(a) ∀x,∀y, P (x, y) e ∀y, ∀x, P (x, y)
(b) ∃x,∃y, P (x, y) e ∃y, ∃x, P (x, y)
(c) ∀x,∃y, P (x, y) e ∀y, ∃x, P (x, y)
2 Técnicas básicas de prova
10. Dizemos que uma afirmação do tipo A→ B é válida por vacuidade se A é sempre falso (alternativamente,
uma afirmação sobre elementos do conjunto vazio é válida por vacuidade). Quais das afirmações abaixo
são válidas por vacuidade? Argumente.
(a) Se A = ∅, então A ⊆ B, para todo conjunto B.
(b) Se x é um inteiro primo, então x é ímpar.
(c) Se x é um número primo par diferente de 2, então x é ímpar.
(d) Se x é um quadrado perfeito negativo, então x é divisível por 4.
(e) Seja x um número inteiro. Tem-se: x é divisível por 4 se e somente se x é divisível por 2.
(f) Se A e B são conjuntos tais que A ∩B = ∅, então A ∪B tem pelo menos dois elementos.
(g) Se A e B são conjuntos tais que A ∩B = ∅, então todo x ∈ A ∩B é primo.
11. As afirmações da questão anterior que não são válidas devido à vacuidade são falsas. Dê um contra-
exemplo para cada tal afirmação.
12. Prove ou dê um contra-exemplo:
(a) Se a e b são inteiros e a | b, então a ≤ b.
(b) Se a e b são inteiros não-negativos e a | b, então a ≤ b.
(c) Se a, b e c são inteiros positivos e a | (bc), então a | b e a | c.
(d) Dois triângulos retângulos tem mesma área se e somente se os comprimentos de suas hipotenusas
forem iguais.
(e) Se x é ímpar, então x2 é ímpar.
(f) Se a e b são primos e a+ b é primo, então a = 2 ou b = 2.
(g) (A−B) ∩ (B −A) = ∅.
(h) Se a e b são inteiros positivos, então a ≤ b.
(i) Sejam T1, T2 triângulos retângulos cujos catetos e hipotenusas tem valores c1, c′1, c2, c′2, h1, h2, respec-
tivamente. Temos que se h1 = h2, então c1 = c2 e c′1 = c′2.
13. Escreva as primeiras sentenças de uma prova por contradição nas afirmações abaixo.
(a) Se A ⊆ B e B ⊆ C, então A ⊆ C.
(b) A soma de dois inteiros negativos é um inteiro negativo.
(c) Se o quadrado de um número racional é um inteiro, então o número racional deve ser também um
inteiro.
(d) Uma reta não pode interceptar os três lados de um triângulo.
(e) Círculos distintos interceptam-se no máximo em dois pontos.
14. Prove as seguintes afirmações por contradição.
(a) Se |A ∪B| = |A|+ |B|, então |A ∩B| = ∅.
(b) Há um número infinito de números primos.
(c) Se a | b e b | c, então a | c.
(d) Não existe um número que é par e ímpar ao mesmo tempo.
(e) Todo inteiro é par ou ímpar.
2