lista1-matematica discreta

Prévia do material em texto

Lista de Matemática Discreta
Demostrações: linguagem
Exercício 1. Sejam P e Q as sentenças “a eleição foi decidida” e “os votos foram contados”, respectivamente. Expresse
cada uma das sentenças simbólicas abaixo como uma sentença em português
(i) ¬P (ii) ¬(P) ∧ Q (iii) (¬P)→ (¬Q) (iv) (¬Q) ∨ ((¬P) ∧ Q)
Exercício 2. Considere que P, ¬Q e R sejam sentenças verdadeiras. Verifique quais das afirmações são verdadeiras.
1. P→ Q
(ii) Q→ P
(iii) P→ (Q ∨ R)
(iv) P↔ Q
(v) P↔ R
(vi) (P ∨ Q)→ P
Exercício 3. Verifique que
(i) há casos em que P→ Q é verdadeira, mas sua recíproca Q→ P é falsa; e vice-versa;
(ii) há casos em que P→ Q é verdadeira, mas sua inversa (¬P)→ (¬Q) é falsa;
(iii) a sentença P→ Q e sua contrapositiva (¬Q)→ (¬P) têm sempre o mesmo valor lógico.
Exercício 4. A sentença (A→ B) ∧ (A→ ¬B) é uma contradição?
Exercício 5. Escreva as afirmações abaixo na forma simbólica, definindo e atribuindo símbolos aos predicados e definido
os domínios dos quantificadores.
(a) Alguns estudantes não gostam de lógica.
(b) Cada pessoa tem uma mãe.
(c) Entre todos os inteiros exitem alguns que são primos.
(d) Um dia do próximo mês é domingo.
(e) Alguns inteiros são pares e divisíveis por 3.
(f) Alguns inteiros são pares ou divisíveis por 3.
(g) x2 − 14 = 0 tem uma solução positiva.
(h) Toda solução de x2 − 14 = 0 é positiva.
(i) Nenhuma solução de x2 − 14 = 0 é positiva.
(j) Todo estudante de direito tem um celular.
(k) Ninguém é perfeito.
(l) Alguém é perfeito.
(m) Todos os nossos amigos são perfeitos.
(n) Algum de nossos amigos é perfeito.
(o) Todos são nossos amigos e são perfeitos.
(p) Ninguém é nosso amigo ou alguém não é perfeito.
Exercício 6. Sejam N o conjunto dos números naturais, e suponha que P(x) significa “ x é par”, Q(x) significa “x e divisível
por 3”, R(x) significa “x e divisível por 4” e S(x, y) é “x + 2 > y”. Escreva em português cada uma das sentenças a seguir,
e determine seu valor-verdade:
(a) (∀x ∈ N)P(x).
(b) (∀x ∈ N)(P(x) ∨ Q(x)).
(c) (∀x ∈ N)(P(x)→ Q(x)).
(d) (∀x ∈ N)(P(x) ∨ R(x)).
(e) (∀x ∈ N)(P(x) ∧ R(x)).
(f) (∀x ∈ N)(R(x)→ P(x)).
(g) (∀x ∈ N)(P(x)→ ¬Q(x)).
(h) (∀x ∈ N)(P(x)→ P(x + 2)).
(i) (∀x ∈ N)(R(x)→ R(x + 4)).
(j) (∀x ∈ N)(Q(x)→ Q(x + 1)).
(k) (∃x ∈ N)R(x)
(l) (∃x ∈ N)(P(x) ∨ Q(x)).
(m) (∃x ∈ N)(P(x)→ Q(x)).
(n) (∃x ∈ N)(Q(x)→ Q(x + 1)).
(o) (∃x ∈ N)(P(x)→ Q(x + 1)).
(p) (∃x ∈ N)(∀y ∈ N)S(x, y).
(q) (∃x ∈ N)(∃y ∈ N)S(x, y).
(r) (∃y ∈ N)(∀x ∈ N)S(x, y).
1
Exercício 7. Para sentenças A, B, C, P, Q, R verifique as equivalências e implicações lógicas:
Leis de identidade
A∧V ⇔ A (1)
B∨ F ⇔ B (2)
Leis de dominação
A∨V ⇔ V (3)
B∧ F ⇔ F (4)
Leis de idempotência
A∨ A ⇔ A (5)
B∧ B ⇔ B (6)
Dupla negação
¬(¬A)⇔ A (7)
Leis distributivas
A∧ (B∨ C) ⇔ (A∧ B) ∨ (A∧ C) (8)
A∨ (B∧ C) ⇔ (A∨ B) ∧ (A∨ C) (9)
Leis comutativas
A∧ B ⇔ B∧ A (10)
A∨ B ⇔ B∨ A (11)
Leis associativas
A∧ (B∧ C) ⇔ (A∧ B) ∧ C (12)
A∨ (B∨ C) ⇔ (A∨ B) ∨ C (13)
Leis de DeMorgan
¬(A∨ B) ⇔ (¬A) ∧ (¬B) (14)
¬(A∧ B) ⇔ (¬A) ∨ (¬B) (15)
Leis de absorção
A∨ (A∧ B) ⇔ A (16)
A∧ (A∨ B) ⇔ A (17)
Leis de inversa
A∨ ¬(A) ⇔ V (18)
A∧ ¬(A) ⇔ F (19)
Equivalências para Provas por contradição
(P→ Q) ⇔ ((P ∧ ¬Q)→ (R ∧ ¬R)) (20)
(P→ Q) ⇔ ((P ∧ ¬Q)→ ¬P) (21)
(P→ Q) ⇔ ((P ∧ ¬Q)→ Q) (22)
2
Negação de quantificadores
¬(para todo x ∈ X, P(x)) ⇔ existe x ∈ X,¬P(x) (23)
¬(existe x ∈ X, P(x)) ⇔ para todo x ∈ X,¬P(x) (24)
Contrapositiva
(A→ B)⇔
(
(¬B)→ (¬A)
)
(25)
Lei da adição
P⇒ (P ∨ Q) (26)
Lei da simplificação
P ∧ Q⇒ P (27)
Silogismo hipotético
((A→ B) ∧ (B→ C))⇒ (A→ C) (28)
Modus Tollens
((A→ B) ∧ ¬B)⇒ ¬A (29)
Silogismo disjuntivo
(P ∨ Q) ∧ ¬P⇒ Q (30)
Exercício 8. Para cada sentença determine o valor verdade e a negação:
1. (∀n ∈ N)(∃m ∈ N)(n2 < m).
2. (∃n ∈ N)(∀m ∈ N)(n < m2).
3. (∀x ∈ R)(∃y ∈ R)(x = y2).
4. (∀n ∈ N)(∃m ∈ N)(n + m = 0).
5. (∃n ∈ N)(∃m ∈ N)(n2 + m2 = 25).
6. (∃n ∈ N)(∃m ∈ N)(n + m = 4 ∧ n −m = 2).
7. (∀n ∈ N)(∀m ∈ N)(∃p ∈ N)(p = n+m
2 ).
8. (∃x ∈ R)(∀y ∈ R)(xy = 0)
9. (∀x ∈ R)(x , 0)→ (∃y ∈ R)(xy = 1).
10. (∃x ∈ R)(∀y ∈ R)(y , 0→ (xy = 1)).
11. (∃x ∈ R)(∃y ∈ R)(x + 2y = 2 ∧ 2x + 4y = 5).
12. (∀x ∈ R)(∃y ∈ R)(x + y = 2 ∧ 2x − y = 1).
Exercício 9. Considere G(x, y) como “x gosta de y”. Expresse em símbolos as sentenças
1. todo mundo gosta de todo mundo
2. todo mundo gosta de alguém
3. alguém gosta de todo mundo
4. alguém gosta de alguém
Exercício 10. A equação (23) diz que a sentença para todo x ∈ X, A(x) é falsa se e somente se existe x ∈ X, ¬A(x) é
verdadeira, ou seja, a sentença para todo x ∈ X, A(x) é falsa se e somente se podemos encontrar um x0 ∈ X tal que A(x0)
é uma sentença falsa. Tal x0 é chamado de contraexemplo para ∀x ∈ X, A(x). Determine um contraexemplo para:
(a) ∀x ∈ R, |x| , 0;
(b) ∀x ∈ R, x2 > x;
(c) ∀x ∈ N, x2 ≥ x;
(d) ∀x ∈ {3, 5, 7, 9}, x + 3 ≥ 7;
(e) ∀x ∈ {3, 5, 7, 9}, x é primo.
3
Exercício 11. Verifique se é um argumento válido:
(a)
A→ B
A→ C
∴ A→ (B∧ C)
(b)
¬R(c)
∀t ∈ D(P(t)→ Q(t))
∀t ∈ D(Q(t)→ R(t))
∴ ¬P(c)
Exercício 12. Uma argumento não é válido se é possível que as premissas sejam verdadeiras e a conclusão falsa. Mostre
que os seguintes argumentos não são válidos exibindo valores-lógicos para as sentenças de modo que as premissas são
verdadeiras mas a conclusão é falsa.
(a)
P↔ Q
Q→ R
R ∨ ¬S
¬(S)→ Q
∴ S
(b)
P
P→ R
P→ (Q ∨ ¬R)
¬(Q) ∨ ¬(S)
∴ S
Exercício 13. Verifique que
1. ∀x ∈ D(P(x) ∧ Q(x))⇔ (∀x ∈ D, P(x)) ∧ (∀x ∈ D, Q(x)).
2. (∀x ∈ D, P(x)) ∨ (∀x ∈ D, Q(x))⇒ ∀x ∈ D(P(x) ∨ Q(x)).
3. ∃x ∈ D, (P(x) ∨ Q(x))⇔ (∃x ∈ D, P(x)) ∨ (∃x ∈ D, Q(x)).
4. ∃x ∈ D, (P(x) ∧ Q(x))⇒ (∃x ∈ D, P(x)) ∧ (∃x ∈ D, Q(x)).
Exercício 14. Dê a justifcativa para cada passo dos argumentos abaixo para que seja válido que
(a) (P ∧ (P→ Q) ∧ (S ∨ R) ∧ (R→ ¬Q))⇒ (S ∨ T)
(b) ((P→ Q) ∧ (¬R ∨ S) ∧ (P ∨ R))⇒ (¬Q→ S)
(a)
passo justificativa
1) P
2) P→ Q
3) Q
4) R→ ¬Q
5) Q→ ¬R
6) ¬R
7) S ∨ R
8) S
9) S ∨ T
(b)
passo justificativa
1) ¬(¬Q→ S)
2) ¬Q ∧ ¬S
3) ¬S
4) ¬R ∨ S
5) ¬R
6) P→ Q
7) ¬Q
8) ¬P
9) P ∨ R
10) R
11) ¬R ∧ R
12) ¬Q→ S
Exercício 15. Escreva o seguinte argumento na forma simbólica, estabeleça sua validade ou dê um contraexemplo para
mostrar que é inválido.
1. “Se Raquel consegue posto de supervisor e trabalha duro, ela ganhará um aumento. Se ela receber o aumento,
então ela vai comprar um carro novo. Ela não comprou um carro novo. Portanto, ou Raquel não conseguiu o posto
de supervisor ou ela não trabalhou duro.”
2. “Se Dominic for para a pista, Helen ficará louca. Se Ralph jogar cartas a noite toda, então Carmela ficará louca. Se
Helen ou Carmela ficarem loucas, então Veronica (a advogada delas) será notificada. Verônica não teve notícias de
nenhum desses dois clientes. Portanto, Dominic não chegou à pista e Ralph não jogou cartas a noite toda.”
3. “Se há uma possibilidade de chuva ou sua camisa vermelho está lavando, Luiz não cortará sua grama. Sempre que
a temperatura é superior a 25ºC, não há chance de chuva. Hoje a temperatura é de 30ºC e Luiz está usando sua
camisa vermelha. Portanto, hoje Luiz cortará a grama.”
4