Resolução de exercícios de matemática discreta

Primeira Lista de Exerccios
Disciplina: Matematica Discreta I
Logica Proposicional
1. Sejam as proposic~oes P : \Esta chovendo", Q : \O sol esta brilhando e R: \Ha nuvens".
Traduza as sentencas abaixo em notac~ao logica:
a) \se esta chovendo ent~ao ha nuvens. "
b) \o sol brilha quando e apenas quando o ceu ca sem nuvens. "
c) \chovera se o sol brilhar ou se o ceu estiver com nuvens."
d) \a chuva e causa do sol n~ao brilhar."
2. Utilizando o exerccio anterior, determine signicados para as proposic~oes:
(a) P ! R (b) R ! P (c) P ! Q
(d) R ! P (e) P ! R (f)  (P) _ R
3. Detemine os valores-verdade:
(a) se 2+2=4 ent~ao 2+4 =8 (b) se 2+2=5 ent~ao 2+4 =8
(c) se 2+2=4 ent~ao 2+4 =6 (d) se 2+2=5 ent~ao 2+4 =6
4. Suponha que P ! Q seja falsa. E possvel determinar os valores-verdade de: (a) P ^ Q,
(b) P _ Q, (c) Q ! P. E se P ! Q for verdadeira?
5. Assuma que \Darcy e uma menina " e que \Darcy tem dez anos " s~ao ambas sentencas falsas. Quais das seguintes s~ao validas?
a) Se Darcy tem dez anos ent~ao Darcy e menina.
b) Darcy tem dez anos se e somente se e menina.
c) Darcy n~ao e uma menina com dez anos
E se ambas forem verdadeiras?
6. Suponha que \Darcy n~ao e baixa" seja falsa e assuma validas as sentencas: \Darcy ou
Maria t^em dez anos " e \ se Maria tem dez anos, ent~ao Darcy n~ao e baixa ". Quais das seguintes sentencas s~ao verdadeiras?
(a) Darcy n~ao e baixa. (b) Maria tem dez anos.
(c) Darcy tem dez anos. (d) Ou Darcy ou Maria n~ao tem dez anos.
7. Construa tabelas-verdade para:
(a)  (P ^ Q) (b) R ! (P ^ Q)
(c)  (P _ Q) (d) (P ! Q) ! (P_  R)
8. Prove ou disprove as tautologias abaixo: (Note que basta uma linha ser F para falhar uma tautologia.)
(a) (Q ! P) ! (P ^ Q) (b) (P ^  Q) ! (P ! Q)
9. Verique as leis de absorc~ao:
(a) P _ (P ^ Q)]  P (b) [P ^ (P _ Q)]  P
1
10. O conectivo \ou exclusivo " acontece se apenas uma das duas clausulas componentes for verdadeira. Denote tal