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

Prévia do material em texto

Universidade Federal de Viçosa 
Centro de Ciências Exatas e Tecnológicas 
Departamento de Informática 
INF130 – Teoria da Computação 
22/03/13 
 
Exercíc io 
 
(Adaptado	de	Barwise	&	Etchemendy	(1993))	
Dado	o	seguinte	texto,	a	partir	dele,	podemos	provar	que	o	unicórnio	é	mítico?	É	mágico?	Tem	
chifre?	
	
“Se	o	unicórnio	é	mítico,	então	ele	é	imortal,	mas,	se	ele	não	for	mítico,	então	é	um	mamífero	
mortal.	Se	o	unicórnio	é	imortal	(e/)ou	mamífero,	então	ele	tem	chifre.	O	unicórnio	é	mágico,	
se	ele	tem	chifre.”	
	
Solução 
 
Sejam	as	proposições:	
	
P:	O	unicórnio	é	mítico.	
Q:	O	unicórnio	é	mortal.	
R:	O	unicórnio	é	mamífero.	
S:	O	unicórnio	tem	chifre.	
T:	O	unicórnio	é	mágico.	
	
Simbolicamente,	o	texto	pode	ser	expresso	pelas	seguintes	fórmulas	proposicionais:	
	 𝑃 ⇒ ¬𝑄,¬𝑃 ⇒ 𝑅 ∧ 𝑄 , ¬𝑄 ∨ 𝑅 ⇒ 𝑆, 𝑆 ⇒ 𝑇	
	
Passando	as	fórmulas	para	a	notação	clausal	(forma	normal	disjuntiva),	obtemos:	
	𝑃 ⇒ ¬𝑄 ≡ ¬𝑃 ∨ ¬𝑄	
	¬𝑃 ⇒ 𝑅 ∧ 𝑄 ≡ 𝑃 ∨ 𝑅 ∧ 𝑄 ≡ 𝑃 ∨ 𝑅 ∧ 𝑃 ∨ 𝑄 ≡ 𝑃 ∨ 𝑅,𝑃 ∨ 𝑄	
	¬𝑄 ∨ 𝑅 ⇒ 𝑆 ≡ ¬ ¬𝑄 ∨ 𝑅 ∨ 𝑆 ≡ 𝑄 ∧ ¬𝑅 ∨ 𝑆 ≡ 𝑄 ∨ 𝑆 ∧ ¬𝑅 ∨ 𝑆 ≡ 𝑄 ∨ 𝑆,¬𝑅 ∨ 𝑆	
	𝑆 ⇒ 𝑇 ≡ ¬𝑆 ∨ 𝑇	
	
Em	notação	clausal,	o	texto	equivale	a:	
	
1. ¬𝑃 ∨ ¬𝑄	
2. 𝑃 ∨ 𝑅	
3. 𝑃 ∨ 𝑄	
4. 𝑄 ∨ 𝑆	
5. ¬𝑅 ∨ 𝑆	
6. ¬𝑆 ∨ 𝑇	
	
	
	
	
O	unicórnio	é	mítico?	
	
Pelo	procedimento	de	resolução,	não	conseguimos	responder	a	pergunta.	De	toda	forma,	para	
a	interpretação	I[P]	=	F,	I[Q]	=	V,	I[R]	=	V,	I[S]	=	V,	I[T]	=	V,	a	forma	de	argumento	não	é	válida:	
	
De	 𝑃 ⇒ ¬𝑄,¬𝑃 ⇒ 𝑅 ∧ 𝑄 , ¬𝑄 ∨ 𝑅 ⇒ 𝑆, 𝑆 ⇒ 𝑇	
	
não	concluímos	P.	
	
O	unicórnio	é	mágico?	
	
O	unicórnio	tem	chifre?