Lista2 MatDiscreta

Prévia do material em texto

Universidade Federal Rural do Rio de Janeiro
Instituto Multidisciplinar
Departamento de Ciência da Computação
Disciplina: TM403 — Matemática Discreta para Computação
Professora: Lígia Maria Soares Passos (ligia.ufrrj@gmail.com)
Monitora: Lívia de Azevedo da Silva (livia_de_azevedo@yahoo.com.br)
Período: 2016/2
2a Lista de Exercícios
1. Determine o comprimento das fórmulas a seguir:
(a) P → ((Q→ R)→ ((P → R)→ (P → R)))
(b) ((P → ¬P )↔ ¬P ) ∨Q
(c) ¬(P → ¬P )
2. Construa as tabelas-verdade das seguintes fórmulas e identifique se elas
são tautologias, contradições, satisfatíveis ou contingências.
Observação: Para este exercício, utilize a seguinte regra de precedência
dos operadores dos conectivos lógicos:
• ¬
• ∧,∨
• →,↔
Perceba que não há um consenso único sobre a ordem dos conectivos
lógicos.
(a) ¬(p→ ¬q)
(b) ¬(p→ q)→ p ∧ q
(c) ¬(p→ (¬p→ q))
(d) p ∧ q → (p↔ q ∨ r)
(e) p ∧ q → p ∨ q
(f) (p ∧ q → r) ∨ (¬p↔ q ∨ ¬r)
1
(g) (p→ q)→ (((p ∧ q)↔ p) ∨ ((p ∨ q)↔ q))
(h) (r ∧ ¬p)↔ (p ∧ r)
3. Considere as fórmulas a seguir:
• (¬P ∨Q)↔ (P → Q)
• P → ((Q→ R)→ ((P → R)→ (P → R)))
• (P → ¬Q)↔ ¬P
• (P → (Q→ R))↔ ((P ∧Q)→ R)
(a) Determine a tabela verdade associada a cada fórmula.
(b) Seja I uma interpretação tal que I[P ] = T, I[Q] = F e I[R] = F ,
o que se pode concluir a respeito do valor de verdade de cada
fórmula?
4. Escreve as sentenças a seguir utilizando a linguagem da Lógica Pro-
posicional. Utilize símbolos proposicionais para representar sentenças
atômicas.
(a) Se eu sou feliz, você é infeliz e se você é infeliz, eu não sou feliz.
(b) José virá à festa e Maria não gostará ou José não virá a festa e
Maria gostará da festa.
5. Demonstre se são verdadeiras ou falsas as afirmações a seguir:
(a) H é contigência⇒ H é satisfatível
(b) H é contraditória⇒ H é contigência
6. Demonstre se a seguinte fórmula é uma tautologia:
P → (Q→ (R→ (S → (U → (V → (W → P ))))))
7. Considere a fórmula H,
H = ¬((P ∧Q) ∨R ∨ S) ∧ (U ∧ V )
Construa uma árvore semântica associada a H e identifique se H é uma
tautologia, é satisfatível ou contraditória.
8. Demonstre, utilizando o método da negação ou absurdo, se as fórmulas
a seguir são tautologias ou não:
(a) G = (¬P → Q)→ ((¬Q→ P ) ∧ (P ∨Q))
(b) H = (P → (Q→ R))→ ((P ∧Q)→ R)
(c) J = (H ↔ (H ∨G))
2
9. Para cada fórmula abaixo, encontre suas respectivas fórmulas nor-
mais(conjuntiva e disjuntiva):
(a) (H ∧ (G ∨H))↔ ((H ∧G) ∨ (H ∧H))
(b) (H ∨ (G ∧H))↔ ((H ∨G) ∧ (H ∨H))
(c) (r ∧ ¬p)↔ (p ∧ r) (letra (h) do exercício 2)
10. Para cada um das fórmulas do exercício anterior, utilizando a prova
por resolução, demonstre se as fórmulas são ou não tautologias. Em
seguida, converta ¬L para a FNC, utilizando as equivalências entre os
conectivos lógicos, e aplique a prova por resolução:
L = ((H ↔ G) ∧ (G↔ H))→ (H ↔ H)
11. Sendo x uma pessoa qualquer, considere as seguintes interpretações:
• I[p(x)]⇔ x estudante
• I[p1(x)]⇔ x monitor
• I[q(x)]⇔ x artista
• I[r(x)]⇔ x inteligente
• I[r1(x)]⇔ x comunicativo
Traduza a sentença a seguir para a lógica de predicados:
Há monitor que é inteligente, mas não é comunicativo.
Apenas estudantes inteligentes são monitores.
Todo artista é comunicativo.
Portanto, nem todo estudante inteligente é um artista.
12. SejaE a fórmula a seguir: E = (∀w)(∀z)(∀z1)(∀x)(∃y)((∀x)p(x, y, w, z)→
(∀y)q(z, y, x, z1))
(a) Determine todas as subfórmulas de E;
(b) Determine todas as subespressões de E.
13. Seja E uma fórmula e x˘ uma variável. Responda justificando sua
resposta.
(a) É possível haver ocorrências de x˘ em E livre e ligadas?
(b) É possível a variável x˘ ser livre e ligada em E ao mesmo tempo?
14. Calcule as composições θσ e σθ onde:
(a) θ = {x←↩ f(x, y), y ←↩ g(x, y), z ←↩ x} e σ = {x←↩ z, y ←↩ x}
3
(b) θ = {x←↩ y, y ←↩ z, z ←↩ x} e σ = {x←↩ z, y ←↩ x}
15. Considere as substituições θ = {x ←↩ g(x, y, z), z ←↩ w} e σ = {x ←↩
g(f(z), z, z), w ←↩ z, y ←↩ z}. Determine se θ é ou não mais geral que
σ.
16. Aplique, passo a passo, o algoritmo da unificação ao conjunto S.
(a) S = {p(x)→ q(z), p(g(z))→ q(x)}
(b) S = {p(x, h(y), f(g(a))), p(a,w, f(z)), p(y, h(x), f(g(b)))}
(c) S = {p(x, f(y))→ q(z), p(a, f(g(y)))→ q(w)}
(d) S = {p(x, f(y)) → q(z), p(g(z), f(w)) → q(w), p(y, f(g(b))) →
q(g(c))}
(e) S = {p(x, f(g(a))), p(a, f(z)), p(y, f(g(b)))}
17. Considere o seguinte conjunto de cláusulas:
Mamifero(x)← Animal(x), T emPelos(x)
Animal(x)← Urso(x)
TemPelos(x)← Urso(x)
Mamifero(x)← Coelho(x)
← Urso(Kenai)
← Coelho(Bugsbunny)
← Animal(Sylvester)
← TemPelos(Sylvester)
Usando resolução SLD e uma regra de computação que escolhe subs-
tituir o primeiro literal da cláusula objetivo, responda às seguintes
perguntas:
(a) O Kenai é mamífero?
(b) Quem é que tem pelos?
(c) Quais são os mamíferos?
4