A maior rede de estudos do Brasil

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

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

a	página	27	nas	notas	biográfi	cas	de	Augusta	Ada).	(De	Morgan	preveniu	a	
condessa	de	que	estudar	matemática	em	excesso,	poderia	interferir	em	suas	habilidades	maternais!)
De	Morgan	foi	um	escritor	extremamente	prolífi	co.	Escreveu	milhares	de	artigos	para	mais	de	15	periódicos.	Também	escreveu	livros	
teóricos	sobre	muitos	assuntos,	incluindo	lógica,	probabilidade,	cálculo	e	álgebra.	Em	1838,	ele	apresentou	o	que	talvez	tenha	sido	a	primei-
ra	explicação	clara	de	uma	importante	técnica	de	demonstração,	conhecida	como	indução matemática	(discutida	na	Seção	4.1	deste	livro),	
termo	que	ele	cunhou.	Na	década	de	1840,	De	Morgan	fez	contribuições	fundamentais	ao	desenvolvimento	da	lógica	simbólica.	Ele	criou	
notações	que	o	ajudaram	a	provar	equivalências	proposicionais,	assim	como	as	leis	que	receberam	seu	nome.	Em	1842,	De	Morgan	apresen-
tou	o	que	talvez	tenha	sido	a	primeira	defi	nição	precisa	de	limite	e	o	desenvolvimento	de	alguns	testes	de	convergência	de	séries	infi	nitas.	
De	Morgan	interessou-se	também	pela	história	da	matemática,	escrevendo	biografi	as	de	Newton	e	Halley.
Em	1837,	De	Morgan	casou-se	com	Sophia	Frend,	que	escreveu	a	biografi	a	do	marido	em	1882.	A	pesquisa,	a	escrita	e	o	ensino	de	De	
Morgan	deixaram	pouco	tempo	para	ele	se	dedicar	a	sua	família	e	vida	social.	No	entanto,	ele	fi	cou	conhecido	pela	sua	bondade,	bom	humor	
e grande inteligência.
1-25 1.2 Equivalências Proposicionais 25
26	 	1	/	Os	Fundamentos:	Lógica	e	Demonstrações	 1-26
Seja r “Rodrigo vai ao concerto” e s	“Carlos	vai	ao	concerto”.	Então,	“Rodrigo	vai	ao	con-
certo ou Carlos vai ao concerto” pode ser representado por r ∨ s.	E,	pela	segunda	lei	de	De	Mor-
gan,	temos	que	ÿ (r ∨ s)	é	equivalente	a	ÿ r ∧ ÿ s.	Logo,	podemos	expressar	sua	negação	por	
“Rodrigo não vai ao concerto e Carlos não vai ao concerto”. ◄
Construindo Novas Equivalências Lógicas
As	equivalências	lógicas	na	Tabela	6,	assim	como	qualquer	outra	que	seja	estabelecida	(como	as	
mostradas	nas	tabelas	7	e	8),	podem	ser	usadas	para	construir	equivalências	lógicas	adicionais.	A	
razão para isso é que uma proposição composta pode ser substituída por outra proposição com-
posta que é logicamente equivalente a essa sem mudar o valor-verdade da proposição original. 
Essa	técnica	é	ilustrada	nos	exemplos	6–8,	em	que	também	usamos	o	fato	de	que	se	p e q são 
logicamente equivalentes e q e r	são	logicamente	equivalentes,	então	p e r também são logica-
mente	equivalentes	(veja	o	Exercício	56).
EXEMPLO 6 Mostre que ÿ (p	→ q)	e	p ∧ ÿ  q são logicamente equivalentes.
Solução: Podemos usar uma tabela-verdade para mostrar que essas proposições compostas são 
equivalentes	(como	no	Exemplo	4).	Inclusive,	não	deve	ser	difícil	fazer	isso.	No	entanto,	quere-
mos ilustrar como usar identidades lógicas que já conhecemos para estabelecer novas identidades 
lógicas,	isso	porque	esse	método	tem	uma	importância	prática	para	estabelecer	equivalências	de	
proposições	compostas	com	um	grande	número	de	variáveis.	Então,	vamos	estabelecer	essa	equi-
valência	desenvolvendo	uma	série	de	equivalências	lógicas,	usando	uma	das	equivalências	da	
Tabela	6	por	vez,	começando	por	ÿ (p	→	q)	e	terminando	com	p ∧ ÿ q.	Temos,	assim,	as	equiva-
lências a seguir. 
ÿ (p	→ q)	≡ ÿ (ÿ p ∨ q)	 pelo Exemplo 3
 ≡ ÿ (ÿ p) ∧ ÿ q pela segunda lei de De Morgan
 ≡ p ∧ ÿ q pela propriedade da dupla negação ◄
EXEMPLO 7 Mostre que ÿ (p ∨	(ÿ p ∧ q))	e	ÿ p ∧ ÿ q são logicamente equivalentes desenvolvendo uma série 
de equivalências lógicas.
Solução:	Vamos	usar	uma	das	equivalências	da	Tabela	6	por	vez,	começando	por	ÿ (p ∨	(ÿ p ∧ q))	
e terminando com ÿ p ∧ ÿ q.	(Nota: Poderíamos estabelecer essa equivalência facilmente usando 
tabelas-verdade.)	Assim,	temos	as	equivalências	a	seguir.
ÿ (p ∨	(ÿ p ∧ q))	≡ ÿ p ∧ ÿ (ÿ p ∧ q)	 pela segunda lei de De Morgan
 ≡ ÿ p ∧ [ÿ (ÿ p) ∨ ÿ q] pela primeira lei de De Morgan
 ≡ ÿ p ∧ (p ∨ ÿ q)	 pela propriedade da dupla negação
 ≡ (ÿ p ∧ p)	∨ (ÿ p ∧ ÿ q)	 pela segunda propriedade distributiva
 ≡ F ∨ 	(ÿ p ∧ ÿ q)	 pois ÿ p ∧ p ≡ F
 ≡ (ÿ p ∧ ÿ q) ∨ F pela propriedade comutativa para disjunções
 ≡ ÿ p ∧ ÿ q pela propriedade dos elementos neutros para F
Em	conseqüência,	ÿ (p ∨	(ÿ p ∧ q))	e	ÿ p ∧ ÿ q são logicamente equivalentes. ◄
Exemplos
Extras
EXEMPLO 8 Mostre	que	(p ∧ q)	→	(p ∨ q)	é	uma	tautologia.
Solução:	Para	mostrar	que	essa	proposição	é	uma	tautologia,	vamos	usar	equivalências	para	demons-
trar que é logicamente equivalente a V.	(Nota:	Isso	poderia	ser	feito	usando	tabelas-verdade.)
(p ∧ q)	→	(p ∨ q)	≡ ÿ (p ∧ q)	∨	(p ∨ q)	 pelo Exemplo 3
 ≡	(ÿ p ∨ ÿ q)	∨	(p ∨ q)	 pela primeira lei de De Morgan
 ≡	(ÿ p ∨ p)	∨	(ÿ q ∨ q)	 pelas propriedades associativas e comutativas
 para a disjunção
 ≡ V ∨ V pelo Exemplo 1 e pela propriedade comutativa 
 para a disjunção
 ≡ V pela propriedade de dominação ◄
Uma tabela-verdade pode ser usada para determinar se uma proposição composta é uma 
tautologia. Isso pode ser feito rapidamente se for uma proposição composta com poucas variá-
veis,	mas,	quando	o	número	de	variáveis	cresce,	isso	pode	fi	car	impraticável.	Por	exemplo,	exis-
tem 220 = 1.048.576 linhas em uma tabela-verdade para uma proposição composta com 20 
variáveis proposicionais. Claramente você precisará de um computador para ajudá-lo a determi-
nar	quando	uma	proposição	composta	é	uma	tautologia.	Quando,	no	entanto,	existem	1.000	va-
riáveis	proposicionais,	um	computador	pode	determinar	em	um	tempo	razoável	se	uma	proposição	
é uma tautologia? Testando todas as 21.000	(um	número	com	mais	de	300	algarismos	decimais)	
possíveis	combinações	de	valores-verdade,	um	computador	não	consegue	terminar	em	menos	de	
alguns	trilhões	de	anos.	Além	disso,	não	existe	um	outro	método	conhecido	que	um	computador	
possa seguir para determinar em um tempo razoável quando uma proposição com muitas variá-
veis	proposicionais	é	uma	tautologia.	Vamos	estudar	questões	como	essas	no	Capítulo	3,	quando	
estudaremos a complexidade de algoritmos.
Links
AUGUSTA	ADA,	CONDESSA	DE	LOVELACE	(1815–1852)	 Augusta	Ada	foi	a	única	fi	lha	do	casamento	do	famo-
so	poeta	Lorde	Byron	e	Lady	Byron,	Annabella	Millbanke,	que	se	separaram	quando	Ada	tinha	1	mês	de	idade,	por	
causa	do	escândalo	amoroso	de	Lorde	Byron	com	sua	meia-irmã.	Lorde	Byron	tinha	uma	reputação,	descrita	por	
uma	de	suas	amantes	como	“louco,	mal	e	perigoso”.	Lady	Byron	era	notável	por	sua	inteligência	e	tinha	paixão	por	
matemática;	ela	era	chamada	por	Lorde	Byron	de	“A	Princesa	dos	Paralelogramos”.	Augusta	foi	criada	por	sua	mãe,	
que	encorajou	seus	talentos	intelectuais,	especialmente	na	música	e	na	matemática,	tendo	em	vista	que	considerava	
perigosas	as	tendências	poéticas.	Naquela	época,	não	era	permitido	que	as	mulheres	freqüentassem	as	universidades	
nem	se	juntassem	a	grupos	de	estudos.	No	entanto,	Augusta	adquiriu	seus	estudos	matemáticos	sozinha	e	com	ma-
temáticos,	incluindo	William	Frend.	Ela	também	tinha	o	apoio	de	outra	matemática,	Mary	Somerville,	e,	em	1834,	
em	um	jantar	na	casa	de	Mary	Somerville,	ela	foi	apresentada	às	idéias	de	Charles	Babbage	sobre	uma	máquina	de	calcular,	chamada	
“Engenho	Analítico”.	Em	1838,	Augusta	Ada	casou-se	com	Lorde	King,	elevado	posteriormente	a	Conde	de	Lovelace.	Juntos,	eles	tive-
ram	três	fi	lhos.
Augusta	Ada	continuou	seus	estudos	em	matemática	depois	do	casamento.	Charles	Babbage	continuou	trabalhando	em	seu	“Engenho	
Analítico”	e	apresentando-o	para	a	Europa.	Em	1842,	Babbage	pediu	a	Augusta	Ada	que	traduzisse	um	artigo	para	o	francês,	descrevendo	sua	
invenção.	Quando	Babbage	viu	a	tradução,	sugeriu	que	ela	começasse	a	escrever	suas	próprias	anotações,	e	o	resultado	fi	nal	foi	três	vezes	o	
original.	Os	relatos	mais	completos	sobre	a	máquina	de	Babbage	estão	nas	anotações	de	Augusta	Ada.	Em	suas	anotações,	ela	comparou	o	tra-
balho	do	“Engenho	Analítico”	ao	tear	de	Jacquard,	com	a	analogia	dos	cartões	perfurados	de	Babbage	aos	usados	para	criar

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