Lista de Exercícios 2 - Teoria da computação

Prévia do material em texto

Universidade Federal de Viçosa
Centro de Ciências Exatas e de Tecnologia
Departamento de Informática
INF130 – Teoria da Computação
07/02/07
2ª Lista de Exercícios
Entregar até 26/02/07
Suponha que temos as seguintes sentenças na forma prenex com apenas quantificadores universais (eles foram retirados, mas estão subentendidos):
 
e suponha que foi dada a consulta s(a). Apresente a dedução formal que decida a consulta.
Converta as seguintes afirmativas para lógica proposicional:
Se Ferreirinha está faminto então está comendo.
Se Ferreirinha está bêbado então está satisfeito.
Se Ferreirinha está cantando e rindo então está bêbado.
Se Ferreirinha está comendo e assistindo a TV então está satisfeito.
Se Ferreirinha está feliz e bebendo então está assistindo a TV.
Se Ferreirinha está com dinheiro então está bebendo..
Se Ferreirinha está cantando então está feliz.
Se Ferreirinha está feliz então está com dinheiro.
Ferreirinha está faminto.
Ferreirinha está cantando.
Determine se o fato de Ferreirinha estar cantando pode ser derivado das outras afirmativas. É possível derivar o fato de que Ferreirinha não está bêbado?
Considere as seguintes sentenças em lógica de predicados:
(P(x) ( Q(x)) ( R(x)
S(x, f(y)) ( R(x)
T (x) ( R(x)
U( f( f(x)), y) ( S( f( f(x)), f(y))
U(x, f(y)) ( S(x, f(y))
V( f(x)) ( Q( f(y))
V(x) ( V( f(x))
P( f(x)) ( P( f( f(x)))
W(x) ( T(x)
V(b)
U(a, a)
P( f(a))
W(a)
U( f( f(a)), f(a))
Construa a dedução formal baseada em resolução para as seguintes consultas e determine se elas podem ou não ser derivadas a partir das premissas acima:
	3.1. R(a)
	3.2. R( f(a))
	3.3. R( f( f(a)))
Passe as seguintes sentenças para a linguagem da lógica de primeira ordem, depois para a notação clausal e depois responda: Ana é cruel?
Uma pessoa é ecologista ou caçadora.
Se Pedro é ecologista então Ana é caçadora.
Se é caçadora então é cruel.
Ana é uma pessoa.
Pedro é ecologista.
Seja o seguinte conjunto de cláusulas (o operador de disjunção ( entre os literais está implícito):
chama(a, b)
usa(b, e)
depende(x, y) (chama(x, y)
depende(x, y) (usa(x, y)
depende(x, y) (chama(x, z) (depende(z, y)
Verifique formalmente, por meio de resolução, depende(a, e).
�PAGE �
�PAGE �2�
_1232352688.unknown
_1232352752.unknown
_1232352780.unknown
_1232350969.unknown