Lógica e Demonstraçoes

∨,	∧ e ÿ  é a proposição composta obtida 
pela troca de cada ∨ por ∧,	cada	∧ por ∨,	cada	V por F e cada 
F por V. O dual de s é representado por s*.
34. Encontre o dual de cada uma destas proposições com-
postas.
a) p ∨ ÿ q b) p ∧	(q ∨	(r ∧ V))
c) (p ∧ ÿ q)	∨	(q ∧ F)
35. Encontre o dual de cada uma destas proposições com-
postas.
a) p ∧ ÿ q ∧ ÿ r b)	 (p ∧ q ∧ r)	∨ s
c) (p ∨ F)	∧	(q ∨ V)
36. Quando s* = s,	em	que	s é uma proposição composta?
37.	 Mostre	que	(s*)*	= s quando s é uma proposição composta.
38.	 Mostre	que	as	equivalências	lógicas	da	Tabela	6,	exce-
to	pela	propriedade	da	dupla	negação,	vêm	em	pares,	
em que cada par contém proposições compostas que 
são duais de si próprias.
**39. Por que os duais de duas proposições compostas equiva-
lentes	são	também	equivalentes,	em	que	essas	proposi-
ções compostas contêm apenas os operadores ∧,	∨ e ÿ ?
40. Encontre uma proposição composta que envolva as va- 
riáveis proposicionais p,	q e r,	que	é	verdadeira	quando	p 
e q são verdadeiras e r	é	falsa,	mas	o	contrário	é	falso.	
[Dica: Use uma conjunção de cada variável proposicio-
nal ou sua negação.]
41. Encontre uma proposição composta que envolva as 
variáveis proposicionais p,	q e r,	que	é	verdadeira	quando	
exatamente duas de p, q e r	 forem	 verdadeiras,	 mas	 o	
contrário é falso. [Dica: Forme uma disjunção de conjunções. 
Inclua uma conjunção para cada combinação de valores 
para os quais a variante proposicional for verdadeira. Cada 
conjunção deverá incluir cada uma dessas três variáveis ou 
suas negações.]
42. Suponha que a tabela-verdade em n variáveis proposicionais 
é dada. Mostre que pode ser formada uma proposição 
composta com essa tabela-verdade a partir de uma 
disjunção	das	conjunções	das	variáveis,	ou	suas	negações,	
com uma conjunção formada por cada combinação de 
valores para os quais a proposição composta é verdadeira. 
A	 proposição	 composta	 resultante	 é	 chamada	 de	 forma 
normal disjuntiva.
Um conjunto de operadores lógicos é chamado de funcionalmen-
te completo quando todas as proposições compostas são logica-
mente equivalentes a uma proposição composta que envolva 
apenas esses operadores lógicos.
43. Mostre que ÿ ,	∧ e ∨ formam um grupo de operadores lógicos 
funcionalmente completo. [Dica: Use o fato de que toda 
proposição composta é logicamente equivalente a outra em 
uma	forma	normal	disjuntiva,	como	visto	no	Exercício	42.]
44. Mostre que ÿ  e ∧ formam um grupo de operadores 
lógicos funcionalmente completo. [Dica: Primeiro use a 
lei de De Morgan para mostrar que p ∨ q é equivalente 
a ÿ (ÿ p ∧ ÿ q).]
45. Mostre que ÿ  e ∨ formam um grupo de operadores lógicos 
funcionalmente completo.
Os exercícios subseqüentes envolvem os operadores lógicos 
NAND e NOR.	A	proposição	p NAND q é verdadeira quando ou 
p ou q,	ou	ambas,	forem	falsas;	e	é	falsa	quando	p e q,	ambas,	
forem	verdadeiras.	A	proposição	p NOR q é verdadeira quando 
ambas,	p e q,	forem	falsas,	e	é	falsa	em	qualquer	outro	caso.	As	
proposições p NAND q e p NOR q são indicadas por p | q e p	↓	q,	
respectivamente.	(Os	operadores	|	e	↓	são	chamados	de	conectivo 
de Sheffer e flecha de Peirce,	 recebendo	os	nomes	de	H.	M.	
Sheffer	e	C.	S.	Peirce,	respectivamente.)
46. Construa a tabela-verdade para o operador lógico NAND.
47. Mostre que p | q é logicamente equivalente a ÿ (p ∧ q).
48. Construa a tabela-verdade para o operador lógico NOR.
49. Mostre que p	↓	q é logicamente equivalente a ÿ (p ∨ q).
50.	 Neste	exercício,	mostraremos	que	{↓}	é	um	conjunto	de	
operadores lógicos funcionalmente completo.
a) Mostre que p	↓	p é logicamente equivalente a ÿ p.
b) Mostre	que	(p	↓	q)	↓	(p	↓	q)	é	logicamente	equivalente	
a p ∨ q.
c) Conclua	a	partir	dos	itens	(a)	e	(b)	e	do	Exercício	49	
que	 {↓}	 é	 um	 conjunto	 de	 operadores	 lógicos	
funcionalmente completo.
51. Encontre uma proposição composta logicamente equivalente 
a p	→	q,	usando	apenas	o	operador	lógico	↓.
52.	 Mostre	 que	 {|}	 é	 um	 conjunto	 de	 operadores	 lógicos	
funcionalmente completo.
53. Mostre que p | q e q | p são equivalentes.
54. Mostre que p	 |	 (q | r)	 e	 (p | q)	 |	 r	 não	 são	 equivalentes;	
portanto,	o	operador	lógico	|	não	é	associativo.
☞
*
*
*
1-29 1.2 Equivalências Proposicionais 29
30	 	1	/	Os	Fundamentos:	Lógica	e	Demonstrações	 1-30
55. Quantas formas diferentes de tabelas-verdade de proposi-
ções compostas existem que envolvam as variantes propo-
sicionais p e q?
56. Mostre que se p,	q e r	são	proposições	compostas,	em	que	p e 
q são logicamente equivalentes e q e r são também logicamen-
te	equivalentes,	então	p e r são logicamente equivalentes.
57.	 A	 sentença	 a	 seguir	 foi	 tirada	 das	 especificações	 de	 um	
sistema telefônico: “Se o diretório de dados for do banco 
aberto,	então	o	monitor	é	posto	em	estado	de	fechamento,	
se o sistema não estiver em seu estado inicial”. Essa espe-
cificação	 é	 difícil	 de	 ser	 compreendida	 porque	 envolve	
proposições com duas condicionais. Encontre um equiva-
lente,	uma	especificação	de	fácil	compreensão,	que	envol-
va	 disjunções	 e	 negações,	 mas	 não	 proposições	 condi- 
cionais.
58. Quantas das disjunções p ∨ ÿ q,	ÿ p ∨ q,	q ∨ r,	q ∨ ÿ r e 
ÿ q ∨ ÿ r	podem	ser	verdadeiras	simultaneamente,	a	par-
tir da construção de uma tabela-verdade com valores 
para p,	q e r?
59. Quantas das disjunções p ∨ ÿ q ∨ s,	ÿ p ∨ ÿ r ∨ s,	ÿ p 
∨ ÿ r ∨ ÿ s,	ÿ p ∨ q ∨ ÿ s,	q ∨ r ∨ ÿ s,	q ∨ ÿ r ∨ ÿ s,	
ÿ p ∨ ÿ q ∨ ÿ s,	p ∨ r ∨ s e p ∨ r ∨ ÿ s podem ser ver-
dadeiras	 simultaneamente,	 a	 partir	 da	 construção	 de	
uma tabela-verdade com valores para p,	q, r e s?
 Uma proposição composta é satisfatória se existe uma 
atribuição de valores-verdade para as variáveis na propo-
sição que torna a declaração verdadeira.
60. Quais das proposições compostas abaixo são satisfatórias?
a) (p ∨ q ∨ ÿ r)	∧	(p ∨ ÿ q ∨ ÿ s)	∧	(p ∨ ÿ r ∨ ÿ s)	∧
 (ÿ p ∨ ÿ q ∨ ÿ s)	∧	(p ∨ q ∨ ÿ s)	
b) (ÿ p ∨ ÿ q ∨ r)	∧	(ÿ p ∨ q ∨ ÿ s)	∧	(p ∨ ÿ q ∨ ÿ s)	∧
 (ÿ p ∨ ÿ r ∨ ÿ s)	∧	(p ∨ q ∨ ÿ r)	∧	(p ∨ ÿ r ∨ ÿ s)
c) (p ∨ q ∨ r)	∧	(p ∨ ÿ q ∨ ÿ s)	∧	(q ∨ ÿ r ∨ s)	∧
 (ÿ p ∨ r ∨ s)	∧	(ÿ p ∨ q ∨ ÿ s)	∧	(p ∨ ÿ q ∨ ÿ r)	∧
 (ÿ p ∨ ÿ q ∨ s)	∧	(ÿ p ∨ ÿ r ∨ ÿ s)
61.	 Explique	como	um	algoritmo	para	definir	se	uma	proposi-
ção composta é satisfatória pode ser usado para determi-
nar se uma proposição composta é uma tautologia. [Dica: 
Observe ÿ p,	em	que	p é a proposição composta que está 
sendo examinada.]
*
1.3 Predicados e Quantificadores
Introdução
A	lógica	proposicional,	estudada	nas	seções	1.1	e	1.2,	não	pode	expressar	adequadamente	o	sig-
nificado	das	 proposições	 em	matemática	 e	 em	 linguagem	natural.	Por	 exemplo,	 suponha	que	
saibamos que 
“Todo computador conectado à rede da universidade está funcionando apropriadamente.”
Nenhuma	regra	da	lógica	proposicional	nos	permite	decidir	sobre	a	veracidade	da	afirmação
“MATH3	está	funcionando	apropriadamente,”	
em	que	MATH3	é	um	dos	computadores	conectados	à	rede	da	universidade.	Da	mesma	forma,	
não podemos usar as regras da lógica proposicional para concluir da proposição
“CS2 está sob ataque de um hacker.”
em	que	CS2	é	um	computador	na	rede	da	universidade,	para	concluir	que	é	verdade	que	
“Existe um computador na rede da universidade que está sob ataque de um hacker.”
Nesta	seção,	vamos	 introduzir	uma	 lógica	mais	poderosa	chamada	 lógica de predicados. 
Veremos	como	a	lógica	de	predicados	pode	ser	usada	para	expressar	o	significado	de	um	amplo	
grupo de proposições em matemática e em ciência da computação de modo que nos permita ra-
ciocinar	e	explorar	relações	entre	objetos.	Para	entender	a	lógica	de	predicados,	precisamos	pri-
meiramente	introduzir	o	conceito	de	predicado.	Posteriormente,	vamos	introduzir	o	conceito	de	
quantificadores,	que	nos	permite	raciocinar	com	declarações	sobre	determinada	propriedade	que	
vale para todos os objetos de