A maior rede de estudos do Brasil

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

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

de De Morgan,	mostrada	na	Tabela	
2,	demonstradas	pelo	matemático	inglês	Augustus	De	Morgan,	na	metade	do	século	XIX.
EXEMPLO 2 Mostre que ÿ (p ∨ q)	e	ÿ p ∧ ÿ q são logicamente equivalentes.
Solução:	As	tabelas-verdade	dessas	proposições	compostas	estão	na	Tabela	3.	Como	os	valores-
verdade ÿ (p ∨ q)	e	ÿ p ∧ ÿ q coincidem para todas as possibilidades de combinações de valo-
res-verdade de p e q,	segue-se	que	ÿ (p ∨ q)	↔	(ÿ p ∧ ÿ q)	é	uma	tautologia	e,	portanto,	essas	
proposições compostas são logicamente equivalentes. ◄
TABELA 3 Tabelas-Verdade para ÿ (p ∨ q) e ÿ p ∧ ÿ q.
p q p ∨ q ÿ (p ∨ q) ÿ p ÿ q ÿ p ∧ ÿ q
V
V
F
F
V
F
V
F
V
V
V
F
F
F
F
V
F
F
V
V
F
V
F
V
F
F
F
V
Demo
Exemplos
Extras
TABELA 1 Exemplos de uma Tautologia e 
de uma Contradição.
p ÿ p p ∨ ÿ p p ∧ ÿ p
V
F
F
V
V
V
F
F
TABELA 4 Tabela-Verdade para ÿ p ∨ q 
e p → q.
p q ÿ p ÿ p ∨ q p →	q
V
V
F
F
V
F
V
F
F
F
V
V
V
F
V
V
V
F
V
V
EXEMPLO 3 Mostre que p	→	q e ÿ  p ∨ q são logicamente equivalentes.
Solução: Construímos a tabela-verdade dessas proposições compostas na Tabela 4. Como os 
valores-verdade de ÿ  p ∨ q e p →	q	são	idênticos,	eles	são	logicamente	equivalentes.	 ◄
Vamos agora estabelecer uma equivalência lógica entre duas proposições compostas que 
envolvem três variáveis proposicionais diferentes p,	q e r. Para usar a tabela-verdade estabelecen-
do	essa	equivalência	lógica,	precisamos	de	oito	linhas,	uma	para	cada	combinação	de	valores-	
verdade	dessas	três	variáveis.	Simbolicamente,	nós	representamos	essas	combinações	listando	os	
valores de p,	q e r,	respectivamente.	Essas	oito	combinações	de	valores-verdade	são	VVV,	VVF,	
VFV,	VFF,	FVV,	FVF,	FFV	e	FFF;	usaremos	essa	ordem	quando	montarmos	as	linhas	da	tabela-
verdade. Note que precisamos do dobro de linhas de que precisávamos quando tínhamos duas 
variáveis	proposicionais;	essa	relação	continua	sendo	válida	para	cada	nova	variável	proposicio-
nal	que	venha	a	ser	adicionada,	então	precisaremos	de	16	linhas	para	estabelecer	a	equivalência	
entre	duas	proposições	compostas	com	quatro	variáveis	proposicionais,	e	assim	sucessivamente.	
Em	geral,	2n linhas são necessárias quando temos n variáveis proposicionais.
EXEMPLO 4 Mostre que p ∨	(q ∧ r) e	(p ∨ q)	∧	(p ∨ r)	são	logicamente	equivalentes.	Essa	é	a	propriedade 
distributiva da disjunção sobre a conjunção.
Solução: Construímos a tabela-verdade para essas duas proposições compostas na Tabela 5. 
Como os valores-verdade de p ∨	(q ∧ r) e	(p ∨ q)	∧	(p ∨ r) são	iguais,	essas	proposições	são	
logicamente equivalentes. ◄
TABELA 5 Uma Demonstração de que p ∨ (q ∧ r) e (p ∨ q) ∧ (p ∨ r) São Logicamente 
Equivalentes.
p q r q ∧ r p ∨	(q ∧ r) p ∨ q p ∨ r (p ∨ q)	∧	(p ∨ r)
V
V
V
V
F
F
F
F
V
V
F
F
V
V
F
F
V
F
V
F
V
F
V
F
V
F
F
F
V
F
F
F
V
V
V
V
V
F
F
F
V
V
V
V
V
V
F
F
V
V
V
V
V
F
V
F
V
V
V
V
V
F
F
F
1-23 1.2 Equivalências Proposicionais 23
24	 	1	/	Os	Fundamentos:	Lógica	e	Demonstrações	 1-24
TABELA 6 Equivalências Lógicas.
Equivalências Nome
p ∧ V ≡ p
p ∨ F ≡ p
Propriedades dos elementos neutros
p ∨ V ≡ V
p ∧ F ≡ F
Propriedades de dominação
p ∨ p ≡ p
p ∧ p ≡ p
Propriedades idempotentes
ÿ	(ÿ p) ≡ p Propriedade da dupla negação
p ∨ q ≡ q ∨ p
p ∧ q ≡ q ∧ p
Propriedades comutativas
(p ∨ q)	∨ r ≡ p ∨ (q ∨ r)
(p ∧ q)	∧ r ≡ p ∧ (q ∧ r)
Propriedades associativas
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
Propriedades distributivas
ÿ(p ∧ q)	≡ ÿ p ∨ ÿ q
ÿ(p ∨ q)	≡ ÿ p ∧ ÿ q
Leis de De Morgan
p ∨ (p ∧ q)	≡ p
p ∧ (p ∨ q)	≡ p
Propriedades de absorção
p ∨ ÿ p ≡ V
p ∧ ÿ p ≡ F
Propriedades de negação
A	Tabela	6	contém	algumas	equivalências	importantes.*	Nessas	equivalências,	V indica uma 
proposição	composta	que	é	sempre	verdadeira,	uma	tautologia,	e	F indica uma proposição que é 
sempre	falsa,	uma	contradição.	Nós	também	mostramos	algumas	equivalências	importantes	que	
envolvem	condicionais	e	bicondicionais	nas	tabelas	7	e	8,	respectivamente.	Ao	leitor	será	pedido	
que	verifique	a	veracidade	dessas	equivalências	nos	exercícios	no	final	desta	seção.
A	propriedade	associativa	para	a	disjunção	mostra	que	a	expressão	p ∨ q ∨ r é	bem	definida,	no	
sentido	de	que	tanto	faz	qual	disjunção	é	considerada	primeiro,	ou	seja,	tanto	faz	se	fazemos	primeiro	
p ∨ q e posteriormente a disjunção deste com r,	ou	se	fazemos	primeiro	a	disjunção	de	q com r e 
depois com p.	De	maneira	análoga,	p ∧ q ∧ r também	está	bem	definida.	Estendendo	esse	racio-
cínio,	segue-se	que p1 ∨ p2 ∨  ∨ pn e p1 ∧ p2 ∧  ∧ pn	também	são	bem	definidas	sempre	que		p1, 
p2, … pn são	proposições.	Além	disso,	note	que	as	leis	de	De	Morgan	podem	ser	estendidas	para	
ÿ (p1 ∨ p2 ∨  ∨ pn)	≡	(ÿ p1 ∧ ÿ p2 ∧  ∧ ÿ pn)
e
ÿ (p1 ∧ p2 ∧ … ∧ pn)	≡	(ÿ p1 ∨ ÿ p2 ∨ … ∨ ÿ  pn).
(Métodos	para	demonstrar	essas	identidades	serão	analisados	na	Seção	4.1.)
* Leitores familiarizados com os conceitos de álgebra booleana vão notar que essas identidades são um caso especial de 
identidades que valem para qualquer álgebra booleana. Compare-as com o conjunto de identidades da Tabela 1 da Seção 
2.2 e com as identidades booleanas da Tabela 5 na Seção 11.1.
Usando as Leis de De Morgan
As	duas	equivalências	lógicas	conhecidas	como	leis	de	De	Morgan	são	particularmente	impor-
tantes.	 Elas	 nos	mostram	 como	 negar	 conjunções	 e	 como	 negar	 disjunções.	 Em	 particular,	 a	
equivalência ÿ (p ∨ q) ≡ ÿ p ∧ ÿ q nos diz que a negação de uma disjunção é formada tomando 
a	conjunção	das	negações	das	proposições	componentes.	Similarmente,	ÿ (p ∧ q) ≡ ÿ p ∨ ÿ q 
nos diz que a negação de uma conjunção é formada tomando a disjunção das negações das pro-
posições componentes. O Exemplo 5 ilustra o uso das leis de De Morgan.
EXEMPLO 5 Use as leis de De Morgan para expressar as negações de “Miguel tem um celular e um laptop” e 
“Rodrigo vai ao concerto ou Carlos vai ao concerto”.
Solução: Seja p “Miguel tem um celular” e q	“Miguel	tem	um	laptop”.	Então,	“Miguel	tem	um	
celular e um laptop” pode ser representado por p ∧ q.	Contudo,	pela	primeira	lei	de	De	Mor-
gan,	ÿ (p ∧ q)	é	equivalente	a	ÿ p ∨ ÿ q.	Conseqüentemente,	podemos	expressar	a	negação	de	
nossa proposição original por “Miguel não tem um celular ou não tem um laptop”.
TABELA 7 Equivalências Lógicas 
que Envolvem Sentenças 
Condicionais.
p →	q ≡ ÿ p ∨ q
p →	q ≡ ÿ q → ÿ p
p ∨ q ≡ ÿ p → q
p ∧ q ≡ ÿ (p →	ÿ q)
ÿ	(p →	q)	≡ p ∧ ÿ q
(p	→	q)	∧	(p	→	r)	≡ p →	(q ∧ r)
(p	→	r)	∧	(q	→	r)	≡	(p ∨ q) →	r
(p	→	q)	∨	(p	→	r)	≡ p →	(q ∨ r)
(p	→	r)	∨	(q	→	r)	≡	(p ∧ q) →	r
TABELA 8 Equivalências Lógicas 
que Envolvem Bicondicionais.
p ↔ q ≡ (p →	q)	∧	(q →	p)
p ↔ q ≡ ÿ p ↔ ÿ q
p ↔ q ≡ (p ∧ q)	∨	(ÿ p ∧ ÿ q)
ÿ	(p ↔ q)	≡ p ↔ ÿ q
Links
AUGUSTUS	DE	MORGAN	(1806–1871)	 Augustus	De	Morgan	nasceu	na	Índia,	onde	seu	pai	era	coronel	no	exér-
cito	indiano.	A	família	De	Morgan	mudou-se	para	a	Inglaterra	quando	ele	tinha	7	meses	de	idade.	Ele	freqüentou	esco-
las	 particulares,	 onde	 desenvolveu	 um	grande	 interesse	 por	matemática	 na	 sua	 juventude.	De	Morgan	 estudou	 na	
Universidade	de	Trinity,	em	Cambridge,	graduando-se	em	1827.	Embora	pensasse	em	entrar	em	medicina	ou	direito,	
De	Morgan	decidiu	seguir	carreira	em	matemática.	Ele	conquistou	uma	cadeira	na	Universidade	de	College,	em	Lon-
dres,	em	1828,	mas	demitiu-se	quando	a	faculdade	despediu	um	colega	sem	apresentar	as	causas	para	a	demissão.	
Entretanto,	ele	retomou	essa	cadeira	em	1836,	quando	seu	sucessor	morreu,	permanecendo	até	1866.
De Morgan foi um professor notável que dava ênfase aos princípios mais que às técnicas. Entre seus estudantes 
estão	muitos	matemáticos	famosos,	incluindo	Augusta	Ada,	Condessa	de	Lovelace,	que	era	colaboradora	de	Charles	
Babbage	em	seu	trabalho	com	máquinas	computacionais	(veja

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