lista3

Prévia do material em texto

Universidade Federal de Campina Grande
Centro de Engenharia Elétri
a e Informáti
a
Departamento de Sistemas e Computação
Lista de Exer
í
ios 3
1. Traduza para o português as seguintes senteças, para as quais o domínio de 
ada variável 
onsiste de todos os
números reais.
a) ∀ x ∃ y (x < y)
b) ∀ x ∀ y (((x ≥ 0) ∧ (y ≥ 0))→ (xy ≥ 0))
) ∀ x ∀ y ∃ z (xy = z)
2. Seja W (x, y) a sentença "o estudante x visitou o website y", em que o domínio para x 
onsiste de todos os
estudantes em sua es
ola e o domínio para y 
onsiste de todos os websites. Expresse 
ada uma das sentenças
omo uma sentença simples em português:
a) W (Sarah, Smith, www.att.com)
b) ∃ x W (x,www.imdb.org)
) ∃ y W (JosOrez, y)
d) ∃ y ∀ z(y 6= (DavidBelcher) ∧ (W (DavidBelcher, z)→W (y, z)))
3. Seja S(x) o predi
ado "x é um estudante", F (x) o predi
ado "x é um membro do 
orpo do
ente"e A(x, y)
o predi
ado "x fez uma pergunta a y", em que o domínio 
onsiste de todas as pessoas asso
iadas 
om sua
universidade. Use quanti�
adores para expressar 
ada uma das sentenças:
a) Luiz fez uma pergunta ao professor Mar
os.
b) Todo estudante pergunta algo ao professor Goes.
) Algum estudante já perguntou algo a todos os professores.
d) Algum estudante nun
a foi questionado por um professor.
4. Que regras de inferên
ia são usadas em 
ada um dos argumentos:
a) Ali
e é formada em matemáti
a. Portanto, Ali
e é formada em matemáti
a ou é formada em 
iên
ia da
omputação.
b) Se eu for nadar, então �
arei muito tempo no sol. Se eu �
ar muito tempo no sol, então �
arei bronzeado.
Portanto, se eu for nadar eu �
arei bronzeado.
) Nenhum homem é uma ilha. Manhattan é uma ilha. Portanto, Manhattan não é um homem.
5. Para 
ada um dos argumentos, explique quais regras de inferên
ia são usadas para 
ada passo.
a) Doug, um estudante nesta sala, sabe 
omo es
rever programas em JAVA. Todas as pessoas que sabem 
omo
es
rever programas em JAVA podem obter um emprego bem pago. Portanto, alguém nesta sala pode obter
um emprego bem pago.
b) Cada um dos 93 alunos nesta sala possui um 
omputador pessoal. Todas as pessoas que possuem um
omputador pessoal podem usar um programa pro
essador de textos. Portanto, Zeke, um aluno desta
turma, pode usar um programa pro
essador de textos.
6. Use regras de inferên
ia para mostrar que se ∀ x(P (x) ∨ Q(x)), ∀ x(¬ Q(x) ∨ S(x)), ∀ x(R(x) → ¬ S(x)) e
∃ x ¬ P (x) são verdadeiros, então ∃ x ¬ R(x) é verdadeiro.
7. Mostre que a proposição 
omposta (p ∨ q) ∧ (¬ p ∨ q) ∧ (p ∨ ¬ q) ∧ (¬ p ∨ ¬ q) é insatisfatível.
1