Exercicios-LPO

Prévia do material em texto

�
Departamento de Computação					Introdução à Lógica
Semestre 1 – BCC & EnC 						Lucia Helena Machado Rino
Introdução à Lógica		Sem 1/2008
Introdução à Lógica
Exercícios de Cálculo de Predicados
Lucia Helena Machado Rino
Você tem aqui exercícios genéricos sobre 
Cálculo de Predicados
Use o conhecimento sobre o Cálculo Proposicional para pensar
 nos exercícios com base nessa álgebra.
Não se esqueça, no entanto, que a semântica da quantificação requer considerações
que não se aplicam ao Cálculo Proposicional
�
�Transforme os seguintes enunciados em fbfs do CalcPredic
Toda cidade tem um caçador de cães que já foi mordido por cada cão na cidade.
Para todo conjunto x, há um conjunto y tal que a cardinalidade de y é maior que a cardinalidade de x.
Todos os blocos no topo de blocos que foram movidos ou que estão acoplados a outros blocos que foram movidos também foram movidos.
Todo objeto fornecido por vidraçarias é de vidro e frágil.
Suponha que representemos “Sam é pai de Bill” por pai(bill, sam) e “Harry é um dos ancestrais de Bill” por ancestral(bill, harry). Sugira uma fbf para:
“Todo ancestral de Bill é ou seu pai, ou sua mãe ou um de seus ancestrais.”
O conectivo ‘ou exclusivo’ – aqui representado por ( – é definido pela seguinte tabela-verdade:
	x
	y
	x ( y
	v
	v
	f
	v
	f
	v
	f
	v
	v
	f
	f
	f
Pergunta-se:
Qual é a fbf que contém somente conectivos de disjunção, conjunção e negação equivalente a
x ( y?
Considere a fórmula F e a estrutura de interpretação J a seguir
F = (y(x p(x, y) ( (x(y p(x, y)
J: D = {a, b}
pJ (a, a) = v; pJ (a, b) = v; pJ (b, a) = f; pJ (b, b) = f
Pergunta-se:
F é válida em J?
F é uma fórmula válida, independentemente de J?
Considere a fórmula G e a estrutura de interpretação J’ a seguir:
G = (x(y eq(plus(x, y), plus(y, x))
J’ : D = N (N = conjunto dos nros. naturais, isto é, maiores ou iguais a 0, inteiros)
plusJ’ = x + 2y
eqJ’ = z, para
z = v se x = y ; z = f, caso contrário
Pergunta-se: G é válida em J’?
�Verifique se do conjunto {F1, F2} é possível deduzir F, ou seja, se {F1, F2} ( F, para F1, F2 e F sendo as seguintes fórmulas (a: símbolo de constante):
F1 = (x(y(z (r(x, y) ( (r(x, z) ( r(y, z)) )
F2 = (w r(w,a)
F = r(a,a)
Seja S o seguinte conjunto de fórmulas:
S = {(x ((y ((z) p(x, y) ( p(x, z) ( p(z, y))))
(x p(x, x),
(x ((y p(x, y) ( ~p(y, x))
Mostre que S ( (x ((y) p(x, y)
Considerando que as formas normais completas disjuntiva e conjuntiva serão identificadas pelas siglas FND e FNC, respectivamente, pede-se:
Para a forma seqüencial abaixo ache equivalentes FND e FNC:
(A ( B) ( (~B ( C )
Essas formas completas são únicas? Justifique sua resposta.
Considere o seguinte alfabeto de primeira ordem:
- símbolos de constantes: a,b;
- símbolos de função: f,g;
- símbolo de predicado: p;
- símbolos de variáveis: x,y,z
Considere, ainda, a estrutura de interpretação J, a seguir definida:
aJ = falso; bJ = verdadeiro;
fJ(n,m) = n ( m; gJ(n,m) = n ( m; 
pJ(n,m) = verdadeiro se e só se n = m.
PEDE-SE: Verifique se as seguintes fórmulas são satisfeitas por J:
(x(y [ p(x, g(y,y)) ( p(x, g(g(y,y),b)) ]
(x(y [ p(f(x, y),a) ( (p(x,a) ( p(y,a)) ]
(x(y(z [ p(g(x,z), y) ]
Considere o seguinte alfabeto de primeira ordem:
- símbolos de predicado: p,q (unários);
- símbolo de variável: x
Mostre que as seguintes implicações lógicas não são válidas:
(x [ p(x) ( (x q(x) ] ( (x [ p(x) ( q(x) ]
(x [ p(x) ( q(x) ] ( (x p(x) ( (x q(x)
�Considere uma situação do mundo dos blocos descrita pelas seguintes fbfs:
�
onTable(a)
onTable(c)
on(d,c)
on(b,a)
heavy(b)
�
clear(e)
clear(d)
heavy(d)
wooden(b)
on(e,b)�
PEDE-SE:
Desenhe a situação acima
As seguintes afirmações fornecem conhecimento geral sobre o mundo desses blocos:
Todo bloco grande e azul está sobre um bloco verde.
Cada bloco pesado e de madeira é grande.
Todos os blocos com topo livre são azuis.
Todos os blocos de madeira são azuis.
Represente-as por um conjunto de condicionais com literais únicos como conseqüentes.
Desenhe um grafo AND/OR para essa base de conhecimento completa (isto é, incluindo as fbfs e as condicionais)
É possível resolver o problema: “Que bloco está sobre um bloco verde?”
Considere as seguintes proposições�:
Todos que podem ler são letrados.
Golfinhos não são letrados.
Alguns golfinhos são inteligentes.
PEDE-SE: Prove a afirmação “Alguns inteligentes não podem ler.” usando o processo de refutação.
Considere o seguinte conjunto de afirmações, que constituirão uma base de conhecimento de um sistema dedutivo.
Tony, Mike e John pertencem ao Clube Alpino.
Todo membro do Clube Alpino que não é esquiador é um escalador de montanhas.
Escaladores de montanhas não gostam de chuva.
Qualquer um que não goste de neve não é esquiador.
Mike não gosta do que Tony gosta e gosta de tudo o que Tony não gosta.
Tony gosta de chuva e neve.
PEDE-SE:
Represente esse conhecimento na forma de proposições lógicas do Cálculo de Predicados.
A partir das proposições lógicas é possível descobrir se “há um membro do Clube Alpino que seja um escalador de montanhas mas não um esquiador?” (chame esta proposição de proposição objetivo)
Formalize a proposição objetivo na LPO.
Usando as propriedades da LPO, justifique sua resposta ao item (b).
�Converta as fbfs abaixo em suas formas clausais:
(x [ p(x) ( p(x) ]
{~ [ (X p(x) ]} ( (x [~p(x)]
~(x { p(x) ( (y [ p(y) ( p(f(x,y)) ] ( ~(y [q(x,y) ( p(y) ] }
(x(y { [ p(x,y) ( q(y,x) ] ( [ q(y,x) ( s(x,y) ] } ( (x(y [ p(x,y) ( s(x,y) ]
Explique porque os conjuntos de literais abaixo não unificam:
{p(f(x,x),a), p(f(y,f(y,a)),a) }
{~p(a),p(x) }
{p(f(a),x), p(x,a) }
Mostre que (z (x [P(x) ( Q(z)] e (z[(x P(x) ( Q(z)] são equivalentes.
� Exercícios 1-2 de Nilsson, p. 139, 156.
� Exercício dado na última aula.
� Capítulos 5 e 6 do Nilsson (exercicio 6.3).
� Nilsson, p. 162
� Exercícios de 1 a 3: do Nilsson, p. 158.
		� PAGE �1�
Exercicios-LPO.doc
	� PAGE �2�	
Exercicios-LPO.doc