MD - Lista 1

Prévia do material em texto

Primeira lista de exerc´ıcios de Matema´tica Discreta
1. Dados os valores lo´gicos A e´ verdadeira, B e´ falsa e C e´ verdadeira, qual e´ o valor
lo´gico de cada uma das fbfs a seguir?
a. A ∧ (B ∨ C)
b. (A ∧B) ∨ C
c. (A ∧B)′ ∨ C
d. A′ ∧ (B′ ∧ C)′
2. Sejam A,B e C as seguintes proposic¸o˜es:
A. Rosas sa˜o vermelhas.
B. Violetas sa˜o azuis.
C. Ac¸ucar e´ doce.
Escreva as proposic¸o˜es compostas a seguir em notac¸a˜o simbo´lica:
a. Rosas sa˜o vermelhas e violetas sa˜o azuis.
b. Sempre que violetas sa˜o azuis, rosas sa˜o vermelhas e o ac¸ucar e´ doce.
c. Rosas sa˜o vermelhas apenas se violetas forem laranjas ou se o ac¸ucar for salgado.
d. Rosas sa˜o vermelhas e, se o ac¸ucar for amargo, enta˜o ou violetas sa˜o roxas ou o
ac¸ucar e´ doce.
3. Use A,B e C como no exerc´ıcio 2 para escrever as seguintes proposic¸o˜es compostas
em portugueˆs:
a. B′ ∨ (A→ C)
b. (C ∧ A′) ↔ B
c. (B ∧ C ′)′ → A
d. A ∨ (B ∧ C ′)
4. Use lo´gica proposicional para provar que os argumentos abaixo sa˜o va´lidos:
(apenas e´ necessa´rio resolver 5 dos subitens abaixo, a escolha do aluno e´ livre)
a. (A′ → B′) ∧B ∧ (A→ C) → C
b. (A→ B) ∧ [B → (C → D)] ∧ [A→ (B → C)] → (A→ D)
c. [A→ (B → C)] → [B → (A→ C)]
d. (A′ → B′) ∧ (A→ C) ∧ (B → C)
e. (A′ → B) ∧ (B → C) ∧ (C → D) → (A′ → D)
f. (A ∨B) ∧ (A→ C) ∧ (B → C) → C
g. (Y → Z ′) ∧ (X ′ → Y ) ∧ [Y → (X → W )] ∧ (Y → Z) → (Y → W )
h. (P ∨ (Q ∧R)) ∧ (R′ ∨ S) ∧ (S → T ′) → (T → P )
i. (∀x)(∀y)A(x, y) ↔ (∀y)(∀x)A(x, y)
j. (∀x)[A(x) → B(x)] → [(∀x)A(x) → (∀x)B(x)]
5. Usando os s´ımbolos predicados indicados e quantificadores apropriados, escreva cada
declarac¸a˜o em portugueˆs como uma uma fbf predicada.
(apenas e´ necessa´rio resolver 4 dos subitens abaixo, a escolha do aluno e´ livre)
B(x) e´ “x e´ uma bola”.
R(x) e´ “x e´ redondo”.
S(x) e´ “x e´ uma bola de futebol”.
a. Todas as bolas sa˜o redondas.
b. Nem todas as bolas sa˜o bolas de futebol.
c. Todas as bolas de futebol sa˜o redondas.
d. Algumas bolas na˜o sa˜o redondas.
e. Algumas bolas sa˜o redondas, mas as bolas de futebol na˜o sa˜o.
f. Toda bola redonda e´ uma bola de futebol.
g. So´ bolas de futebol sa˜o bolas redondas.
h. Se as bolas de futebol sa˜o redondas, enta˜o todas as bolas sa˜o redondas.
6. Para cada fbf abaixo, classifique como tautologia, contradic¸a˜o ou contingeˆncia. Jus-
tifique utilizando uma prova formal.
a. (∀x)P (x) ∧ (∃x)Q(x) → (∃x)[P (x) ∧ (Q(x)]
b. (∀x)(∃x)Q(x, y) → (∃x)(∀y)Q(x, y)
c. (∃x)[R(x) ∨ S(x)] → (∃x)R(x) ∨ (∃x)S(x)
d. (∃x)[P (x) → Q(x)] ∧ (∀y)[Q(y) → R(y)] ∧ (∀x)P (x) → (∃x)R(x)
2