A maior rede de estudos do Brasil

Grátis
109 pág.
Lógica e Demonstraçoes

Pré-visualização | Página 50 de 50

→	p1 e p1	→	p2	são	válidas?	Se	não,	mostre	outro	
conjunto de condicionais que podem ser usados para mos-
trar que as 4 sentenças são equivalentes.
13. a) Suponha que uma sentença da forma ∀xP(x)	 é	 falsa.	
Como isso pode ser demonstrado?
b) Mostre que a sentença “Para todo inteiro positivo n,	n2 
≥	2n” é falsa.
14. Qual a diferença entre uma demonstração de existência cons-
trutiva e uma não construtiva? Dê um exemplo de cada.
15. Quais são os elementos de uma demonstração para a 
existência de um único elemento x, tal que P (x),	em	que	
P (x)	é	uma	função	proposicional?
16. Explique como uma demonstração por casos pode ser 
usada para demonstrar um resultado sobre valores abso-
lutos,	 tal	como	o	fato	de	que	 |xy| = |x| |y| para todos os 
reais x e y.
Exercícios Complementares
1. Seja p a proposição “Eu vou fazer todo exercício deste 
livro” e q a	 proposição	 “Eu	 vou	 tirar	 ‘A’	 neste	 curso”.	
Expresse cada uma delas como uma combinação de p e q.
a) Eu	vou	tirar	“A”	neste	curso	somente	se	eu	fizer	todos	
os exercícios deste livro.
b) Eu vou tirar “A”	neste	curso	e	vou	fazer	todos	os	exer-
cícios deste livro.
c) Ou	eu	não	vou	tirar	“A”	neste	curso	ou	eu	não	vou	fazer	
todos os exercícios deste livro.
d) Para	eu	 tirar	“A”	neste	curso	é	necessário	e	suficiente	
que eu faça todos os exercícios deste livro.
2. Faça	a	tabela-verdade	da	proposição	composta	(p ∨ q) → 
(p ∧ ÿ r).
3. Mostre que estas proposições compostas são tautologias.
a) (ÿ q ∧	(p	→	q))	→	ÿ p
b) ((p ∨ q)	∧ ÿ p)	→	q
4. Dê	a	oposta,	a	contrapositiva	e	a	inversa	dessas	sentenças	
condicionais.
a) Se	está	chovendo,	então	eu	vou	de	carro	para	o	trabalho.
b) Se |x| = x,	então	x ≥	0.
c) Se n é	maior	que	3,	então	n2 é maior que 9.
5. Dada uma sentença condicional p →	q,	encontre	a	oposta	
de	sua	 inversa,	a	oposta	de	sua	oposta	e	a	oposta	de	sua	
contrapositiva.
6. Dada uma sentença condicional p →	q,	encontre	a	inversa	
de	sua	inversa,	a	inversa	de	sua	oposta	e	a	inversa	de	sua	
contrapositiva.
7. Encontre uma proposição composta que envolva as variáveis 
proposicionais p,	q,	r e s que é verdadeira quando exatamente 
três dessas variáveis proposicionais são verdadeiras e é 
falsa,	caso	contrário.
8. Mostre que estas sentenças são inconsistentes: “Se Sergei 
aceitar	o	trabalho	oferecido,	então	ele	terá	mais	tempo	em	
casa”,	 “Se	 Sergei	 aceitar	 o	 trabalho	 oferecido,	 então	 ele	
receberá	um	salário	maior”,	“Se	Sergei	terá	mais	tempo	em	
casa,	então	ele	não	receberá	um	salário	maior”.
9. Mostre que estas sentenças são inconsistentes: “Se Miranda 
não	tiver	o	curso	de	matemática	discreta,	então	ela	não	se	
formará”,	“Se	Miranda	não	se	formar,	então	ela	não	obterá	
um	 bom	 trabalho”,	 “Se	Miranda	 ler	 este	 livro,	 então	 ela	
obterá	 um	 bom	 trabalho”,	 “Miranda	 não	 tem	 o	 curso	 de	
matemática	discreta,	mas	leu	este	livro”.
10. Suponha que você encontre três pessoas A,	B e C,	na	ilha	
dos cavaleiros e dos bandidos descrita no Exemplo 18 da 
Seção 1.1. O que são A,	B e C se A diz “Eu sou um bandido 
e B é um cavaleiro” e B diz “Exatamente um de nós três é 
um cavaleiro”?
11. (Adaptado	de	[Sm78])	Suponha	que	em	uma	ilha	existem	
três	tipos	de	pessoas:	cavaleiros,	bandidos	e	normais.	Ca-
valeiros	sempre	dizem	a	verdade,	bandidos	sempre	men-
tem	e	normais	às	vezes	mentem,	às	vezes	dizem	a	verdade.	
Detetives que investigam um crime questionaram três ha-
bitantes	—	Ana,	Bela	e	Clarice.	Os	detetives	sabiam	que	
uma	das	três	teria	cometido	o	crime,	mas	não	sabiam	qual.	
Eles também sabiam que a criminosa era uma cavaleira e 
as	outras	duas	não.	Adicionalmente,	os	detetives	gravaram	
estas	sentenças:	Ana:	“Eu	sou	inocente”,	Bela:	“O	que	Ana	
diz	é	verdade”,	Clarice:	“Bela	não	é	normal”.	Depois	de	
analisar	essas	informações,	os	detetives	identificaram	po-
sitivamente o culpado. Quem era?
12. Mostre que se S é	uma	proposição,	em	que	S é a sentença 
condicional “Se S é	verdadeira,	então	unicórnios	existem”,	
então “Unicórnios existem” é verdadeira. Mostre que 
disso segue que S não	 pode	 ser	 uma	 proposição.	 (Esse	
paradoxo é conhecido como paradoxo de Löb.)
13. Mostre que o argumento com premissas “O saci-pererê é 
uma	personagem	real”,	“O	saci-pererê	não	é	uma	persona-
gem	real”	e	a	conclusão	“Você	pode	encontrar	ouro	no	fi-
nal do arco-íris” é um argumento válido. Isso mostra que a 
conclusão é verdadeira?
14. Seja P (x)	a	sentença	“O	estudante	x sabe cálculo” e seja 
Q (y)	 a	 sentença	 “A	 classe	 y contém um estudante que 
sabe	cálculo”.	Expresse	cada	uma	das	quantificações	de	
P (x)	e	Q (y).
a) Algum	estudante	sabe	cálculo.
b) Nenhum estudante sabe cálculo.
c) Toda classe tem um estudante que sabe cálculo.
d) Todo estudante em toda classe sabe cálculo.
e) Existe ao menos uma classe sem algum estudante que 
sabe cálculo.
15. Seja P (m, n)	a	sentença	“m divide n”,	em	que	o	domínio	
para as variáveis consiste em todos os inteiros positivos. 
(Por	“m divide n”,	entendemos	que	n = km para algum 
inteiro k.)	 Determine	 o	 valor-verdade	 de	 cada	 uma	
destas sentenças.
a) P (4, 5)		 b) P (2, 4)
c) ∀m ∀nP (m, n)	 d) ∃m ∀nP (m, n)
e) ∃n ∀mP (m, n) f) ∀n P (1,	n)
16. Encontre	 um	 domínio	 para	 os	 quantificadores	 em	
∃x∃y (x  y ∧ ∀z	((z  x)	∧	(z  y)),	tal	que	essa	sen-
tença seja verdadeira.
17. Encontre um domínio para os quantificadores em 
∃x∃y (x  y ∧ ∀z	 ((z 5 x)	∨	 (z 5 y))),	 tal	 que	 essa	
sentença seja falsa.
18. Use	quantificadores	existencial	e	universal	para	expressar	
a sentença “Ninguém tem mais que três avós” usando a 
função proposicional G (x, y),	que	representa	“x é a avó 
de y”.
19. Use quantificadores	existencial	e	universal	para	expressar	
a sentença “Todos têm exatamente dois pais biológicos” 
usando a função proposicional P (x, y),	que	representa	“x é 
pai	(ou	mãe)	biológico	de	y”.
20. O	quantificador	∃n denota “existem exatamente n”,	portanto	
∃nx P (x)	significa	que	existem	exatamente	n elementos do 
domínio,	 tal	 que	P(x)	 é	 verdadeira.	 Determine	 o	 valor-
verdade	destas	sentenças,	em	que	o	domínio	consiste	em	
todos os números reais.
a) ∃0x(x2 = 2	1)	 b) ∃1x(|x| =	0)
c) ∃2x(x2 =	2)	 d) ∃3x(x = |x|)
21. Expresse	cada	uma	destas	sentenças	usando	quantificado-
res	universal	e	existencial	e	lógica	proposicional,	em	que	
∃n	é	definido	no	Exercício	20.
a) ∃0x P (x)
b) ∃1x P (x)
c) ∃2x P (x)
d) ∃3x P (x)
22. Seja P (x, y)	uma	função	proposicional.	Mostre	que	∃x ∀y 
P (x,	y)	→	∀y ∃x P (x,	y)	é	uma	tautologia.
23. Sejam P (x)	e	Q (x)	funções	proposicionais.	Mostre	que	∃x 
(P (x)	→	Q (x))	e	∀x P (x)	→	∃x Q (x)	sempre	têm	o	mesmo	
valor-verdade.
24. Se ∀y ∃x P (x,	y)	é	verdadeira,	segue	que,	necessariamente,	
∃x ∀y P (x,	y)	é	verdadeira?
25. Se ∀x ∃y P (x,	y)	é	verdadeira,	segue	que,	necessariamente,	
∃x ∀y P (x,	y)	é	verdadeira?
26. Encontre as negações destas sentenças.
a) Se	nevar	hoje,	então	eu	vou	esquiar	amanhã.
b) Toda pessoa nesta classe entende indução matemática.
c) Algum	estudante	desta	classe	não	gosta	de	matemática	
discreta.
d) Em toda classe de matemática existe algum estudante 
que está com sono durante as aulas.
27. Expresse	 esta	 sentença	 usando	 quantificadores:	 “Todo	
estudante nesta classe teve algum curso de ciências ma-
temáticas em todo o departamento da escola”.
28. Expresse	 esta	 sentença	 usando	 quantificadores:	 “Existe	
um	prédio	no	campus	de	alguma	faculdade	brasileira,	tal	
que todas as suas salas são pintadas de branco”.
29. Expresse a sentença: “Existe exatamente um estudante 
nesta classe que teve exatamente um curso de matemática 
nesta	 faculdade”	 usando	 quantificadores	 de	 unicidade.	
Depois	 expresse	 essa	 sentença	 usando	 quantificadores,	
sem	o	uso	dos	quantificadores	de	unicidade.
30. Descreva uma regra de inferência que pode ser usada para 
demonstrar que existem exatamente dois elementos x e y 
em	um

Crie agora seu perfil grátis para visualizar sem restrições.