Lógica_Básica_Prova_2

Prévia do material em texto

1	
Lógica	básica																																																																																																Prova	2	
Prof.	Mattia	Petrolo																																																																													07/12/2020	
	
1. (2	pontos)	
Dadas	as	tabelas,	encontrar	a	fórmula	correspondente	a	cada	tabela.	(Cada	fórmula	
α,	β,	γ	e	δ	deve	conter	A,	B	e	C.)	
	
A	 B	 C	 Fórmula	α	
V	 V	 V	 V	
V	 V	 F	 V	
V	 F	 V	 F	
V	 F	 F	 F	
F	 V	 V	 V	
F	 V	 F	 F	
F	 F	 V	 F	
F	 F	 F	 F	
	
A	 B	 C	 Fórmula	γ	
V	 V	 V	 V	
V	 V	 F	 F	
V	 F	 V	 F	
V	 F	 F	 F	
F	 V	 V	 V	
F	 V	 F	 F	
F	 F	 V	 F	
F	 F	 F	 F	
	
	
2. (3	pontos)	
Considere	uma	linguagem	L	=	{a,	b,	c,	P,	Q,	R,	S}	e	uma	estrutura	M =	(B,	IM)	onde:	
-	B	=	{0,1,2,3,4}	
-	A	função	interpretação	IM é	como	segue:	
IM (a)	=	0	
IM (b)	=	3	
IM (c)	=	4	
IM (P)	=	{0,	1,	2,	3}	
IM (Q)	=	{0,	3,	4}	
IM (R)	=	{(0,	1),	(0,	2),	(0,	3),	(1,	1),	(3,	4),	(4,	3)}	
IM (S)=	{(0,	1,	2),	(1,	2,	3),	(0,	3,	4),	(4,	1,	3)}	
	
A	 B	 C	 Fórmula	β	
V	 V	 V	 F	
V	 V	 F	 V	
V	 F	 V	 V	
V	 F	 F	 F	
F	 V	 V	 F	
F	 V	 F	 F	
F	 F	 V	 F	
F	 F	 F	 V	
A	 B	 C	 Fórmula	δ	
V	 V	 V	 F	
V	 V	 F	 F	
V	 F	 V	 F	
V	 F	 F	 F	
F	 V	 V	 V	
F	 V	 F	 V	
F	 F	 V	 V	
F	 F	 F	 V	
	 2	
Diga	se	as	fórmulas	abaixo	são	verdadeiras	ou	falsas	em	M,	e	por	quê.		
(i) S	(a,	b,	c)	
(ii) ¬Q	(b)	
(iii) ∃xR(x,	y)	
(iv) ∀x(Q(x)	→	P(x))	
(v) ∃x∃yS(x,	y,	b)	
(vi) ¬∀x	P(x)	↔	¬∃x∀yR(x,	y)	
	
3. (3	pontos)	
Seja	uma	linguagem	L	=	{a,	b,	c,	d,	P,	Q},	e	uma	estrutura	M =	(B,	IM)	onde:	
-	B	=	{Yoda,	Darth	Vader,	Luke,	Leia}	
-	A	função	interpretação	IM é	como	segue:	
IM (a)	=	Yoda	
IM (b)	=	Darth	Vader	
IM (c)	=	Luke	
IM (d)	=	Leia	
IM (P)	=	{Darth	Vader,	Luke}	
IM (Q)	=	{(Yoda,	Leia),	(Yoda,	Darth	Vader),	(Luke,	Leia),	(Leia,	Yoda),	(Luke	,	Darth	
Vader)}	
	
Com	relação	a	essa	estrutura,	dê	exemplos	de:	
	
(i) Uma	fórmula	que	seja	verdadeira;	
(ii) Uma	fórmula	com	uma	negação	e	uma	conjunção	que	seja	verdadeira;	
(iii) Uma	fórmula	universalmente	quantificada	que	seja	falsa;	
(iv) Uma	fórmula	com	um	quantificador	universal	e	um	existencial	que	seja	
verdadeira.	
	
4. (2	pontos)	
As	fórmulas	abaixo	são	todas	inválidas.	Mostre	isso,	construindo	para	cada	uma	delas	
uma	estrutura	onde	a	fórmula	seja	falsa.	
	
(i) P(a)	→	∀xP(x)	
(ii) ∃xP(x)	→	P(a)	
(iii) (∃xP(x)	∧	∃xQ(x))	→	∃x(P(x)	∧Q(x))	
(iv) ∀x(P(x)	∨	Q(x))	→	(∀xP(x)	∨	∀xQ(x))	
	
	
	
Conceitos	:	10	pontos	
A	:	9	–	10	
B	:	7,50	–	8,99	
C	:	6	–	7,49	
D	:	5	–	5,99	
F	:	0	–	4,99