questoes - logica

Prévia do material em texto

Universidade Federal de Campina Grande 
Curso: Ciência da Computação 
Disciplina: Matemática Discreta 
Professor: Leandro Balby Marinho 
Monitor: José Robson da Silva Araujo Junior 
Período: 2017.1 
Aluno(a): ____________________________________________________ Matrícula: _________________ 
 
PRIMEIRA LISTA DE EXERCÍCIOS 
 
1. Considere as proposições p: “Ele é fera de computação” e q: “Ele usa break no for” 
para reescrever em notação simbólica (usando conectivos lógicos) as seguintes pro-
posições: 
 
a) Embora ele seja fera de computação, ele não usa break no for. 
b) Ele é fera de computação ou usa break no for. 
c) Se ele usa break no for, então ele é fera de computação. 
d) Ele é fera de computação ou usa break no for, mas não usa break no for se não é 
fera de computação. 
 
2. Ainda considerando p e q da questão anterior, expresse em português as 
proposições a seguir: 
 
a) ¬ 𝑝 
b) ¬ 𝑝 ∧ ¬ 𝑞 
c) ¬ 𝑞 → 𝑝 
d) 𝑝 ↔ 𝑞 
e) 𝑝 ∧ (𝑝 → ¬ 𝑞) 
f) ¬ 𝑝 ∨ (𝑝 ∧ 𝑞) 
 
3. Demonstre que as expressões a seguir são tautologias (use o método de sua 
preferência). 
 
a) 𝑝 ∨ ¬ 𝑝 
b) ¬ (𝑝 ∧ 𝑞) ↔ ¬ 𝑝 ∨ ¬ 𝑞 
c) ¬ (𝑝 ∨ 𝑞) ↔ ¬ 𝑝 ∧ ¬ 𝑞 
d) (𝑝 → 𝑞) ∨ (𝑝 → 𝑟) ≡ 𝑝 → (𝑞 ∨ 𝑟) 
 
4. Use regras de inferência para demonstrar a validade dos argumentos a seguir. 
 
a) (𝑝 → 𝑞) ∧ (𝑟 ∨ ¬ 𝑞) ∧ 𝑝 → 𝑟 
b) 𝑝 ∧ (¬ 𝑞 → ¬ 𝑝) → 𝑞 
c) ¬ 𝑝 ∧ (𝑝 ∨ 𝑞) → 𝑞 
d) [𝑝 → (𝑞 ∨ 𝑟)] ∧ ¬ 𝑞 ∧ ¬ 𝑟 → ¬ 𝑝 
 
5. Considere A(x) como “x é aluno”, E(x) como “x é esforçado” e C(x) como “x está 
cursando Matemática Discreta”. Expresse as sentenças a seguir através de A(x), E(x), 
C(x), quantificadores e conectivos lógicos; o domínio são todas as pessoas. 
 
a) Todos que estão cursando Matemática Discreta são alunos esforçados. 
b) Alguns alunos não esforçados estão cursando Matemática Discreta. 
c) Somente alunos esforçados cursam Matemática Discreta. 
6. Considerando E(x) como “x é aluno esforçado”, C(x) como “x está cursando 
Matemática Discreta” e o domínio como todas as pessoas, faça agora o contrário: 
escreva as sentenças a seguir em português. 
 
a) ∀𝑥[𝐸(𝑥) ∨ 𝐶(𝑥)] 
b) ∀𝑥[𝐸(𝑥) ↔ 𝐶(𝑥)] 
c) ∃𝑥[𝐸(𝑥) ∧ 𝐶(𝑥)] 
d) ∃𝑥[𝐸(𝑥) → 𝐶(𝑥)] 
 
7. A sequência de demonstração a seguir contém um erro. Aponte-o e justifique-o. 
 
 Passo Justificativa 
 1. (∀𝑦)(∃𝑥)𝑄(𝑥, 𝑦) Hipótese. 
 2. (∃𝑥)𝑄(𝑥, 𝑦) Particularização universal em (1). 
 3. 𝑄(𝑎, 𝑦) Particularização existencial em (2). 
 4. (∀𝑦)𝑄(𝑎, 𝑦) Generalização universal em (3). 
 5. (∃𝑥)(∀𝑦)𝑄(𝑥, 𝑦) Generalização existencial em (4). 
 
8. Escreva a negação dos argumentos a seguir em português: 
a) Todos os estudantes se interessam em projetos de extensão. 
b) Todas as pessoas gostam de música country ou gostam de pop. 
c) Algumas pessoas estudam Matemática Discreta. 
d) Certos cachorros são fofos e inofensivos. 
 
9. Considere o argumento “Todo estudante de Hogwarts é bruxo. Existem alunos em 
Hogwarts; portanto, existem alguns bruxos.” Transcreva-o utilizando letras de 
proposição e conectivos lógicos. Em seguida, demonstre sua validade através de 
regras de inferência. 
 
10. Demonstre que se (∃𝑥)[𝑃(𝑥) ∧ 𝑄(𝑥)] e (∀𝑥)[(𝑃(𝑥) → 𝑅(𝑥)], então (∃𝑥)[𝑃(𝑥) ∧
𝑄(𝑥) ∧ 𝑅(𝑥)] usando seus conhecimentos de lógica de predicados e regras de 
inferência.