A maior rede de estudos do Brasil

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

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

dos	operadores	lógicos, ÿ ,	∧,	∨,	→ e	↔.
Traduzindo Sentenças em Português
Existem muitas razões para traduzir sentenças em português para expressões que envolvem 
variáveis	proposicionais	e	conectivos	 lógicos.	Em	particular,	o	português	(e	muitas	outras	
linguagens	humanas)	é	freqüentemente	ambíguo.	Traduzir	sentenças	como	proposições	com-
postas	(e	outros	tipos	de	expressões	lógicas,	as	quais	vamos	introduzir	mais	tarde	neste	ca-
pítulo)	 acaba	 com	 essa	 ambigüidade.	Note	 que	 isso	 pode	 envolver	 um	 conjunto	 de	 fatos	
assumidos	 com	base	no	 significado	de	 cada	 sentença.	Mais	 ainda,	uma	vez	 traduzidas	do	
português	para	expressões	 lógicas,	podemos	analisar	seus	valores-verdade,	manipulá-las	e	
ainda	usar	regras	de	 inferência	(as	quais	discutiremos	na	Seção	1.5)	para	raciocinar	sobre	
elas.
Para	ilustrar	o	processo	de	tradução	de	uma	sentença	do	português	para	uma	expressão	lógica,	
considere os exemplos 12 e 13.
EXEMPLO 12 Como podemos traduzir esta sentença do português para expressões lógicas?
“Você pode acessar a Internet a partir deste campus somente se você é um expert em ciência 
da computação ou não é um novato.”
Solução: Existem muitas maneiras de traduzir essa sentença para uma expressão lógica. Por 
exemplo,	poderíamos	representá-la	por	uma	simples	variável	proposicional	p,	mas	isso	pode	não	
ser	usual	quando	queremos	analisar	o	significado	dela	ou	raciocinar	sobre	ela.	No	entanto,	pode-
mos usar variáveis proposicionais para cada sentença que forma a proposição e determinar os 
conectivos	lógicos	que	devem	estar	entre	elas.	Em	particular,	podemos	usar	a, c e f representando 
“Você	pode	acessar	a	Internet	a	partir	deste	campus”,	“Você	é	um	expert	em	ciências	da	compu-
tação”	e	“Você	é	um	novato”,	respectivamente.	Note	que	“somente	se”	é	uma	forma	de	a	condi-
cional	ser	expressa,	então	podemos representar a sentença por
a	→	(c ∨ ÿ f ).	 ◄
EXEMPLO 13 Como podemos traduzir esta sentença do português para expressões lógicas?
“Você pode pular de pára-quedas se você tem autorização de seus pais ou se tem mais de 18 
anos.”
TABELA 8
Prioridade do 
Operador Lógico.
Operador Prioridade
ÿ  1
∧
∨
2
3
→
↔
4
5
Exemplos
Extras
1-11 1.1 Lógica Proposicional 11
12	 	1	/	Os	Fundamentos:	Lógica	e	Demonstrações	 1-12
Solução: Sejam q,	r e s	as	representações	de	“Você	pode	pular	de	pára-quedas”,	“Você	tem	auto-
rização	de	seus	pais”	e	“Você	tem	mais	de	18	anos”,	respectivamente.	Então,	a	sentença	pode	ser	
traduzida por 
(r ∧ ÿ s)	→	ÿ q.
É	claro	que	existem	muitas	outras	maneiras	de	traduzir	a	sentença,	mas	essa	já	é	suficiente.	◄
Sistemas de Especificações
A	tradução	de	sentenças	da	linguagem	natural	para	expressões	lógicas	é	uma	parte	essencial	
para	a	especificação	de	sistemas	de	hardware	e	sistemas	de	software.	Sistemas	e	engenheiros	
de	software	tomam	afirmações	em	linguagem	natural	e	produzem	especificações	precisas	e	sem	
ambigüidade que podem ser usadas como base de um sistema de desenvolvimento. O Exemplo 
14 mostra como proposições compostas podem ser usadas nesse processo.
EXEMPLO 14	 Expresse	a	especificação	“A	resposta	automática	não	pode	ser	enviada	quando	o	sistema	está	
sobrecarregado”,	usando	conectivos	lógicos.
Solução: Um meio de traduzir é tomar p	como	“A	resposta	automática	pode	ser	enviada”	e	q 
como	“O	sistema	está	sobrecarregado”.	Então,	ÿ p representa “Não é o caso de a resposta auto-
mática	poder	ser	enviada”	ou	“A	resposta	automática	não	pode	ser	enviada”.	Conseqüentemente,	
nossa	especificação	pode	ser	representada	por	q → ÿ p. ◄
Sistemas	de	especificações	devem	ser	consistentes,	ou	seja,	não	podem	conter	especificações	
conflitantes	que	possam	ser	usadas	para	derivar	uma	contradição.	Quando	as	especificações	não	
são	 consistentes,	 pode	não	haver	 um	meio	de	desenvolver	 um	 sistema	que	 satisfaça	 todas	 as	
especificações.
EXEMPLO 15	 Determine	se	este	sistema	de	especificações	é	consistente:
“A	mensagem	de	diagnóstico	é	armazenada	no	buffer	ou	é	retransmitida.”
“A	mensagem	de	diagnóstico	não	é	armazenada	no	buffer.”
“Se	a	mensagem	de	diagnóstico	é	armazenada	no	buffer,	então	ela	é	retransmitida.”
Solução: Para	determinar	se	esse	sistema	é	consistente,	primeiro	vamos	reescrevê-lo	como	ex-
pressões lógicas. Seja p	“A	mensagem	de	diagnóstico	é	armazenada	no	buffer”	e	q	“A	mensagem	
de	diagnóstico	é	retransmitida”.	As	especificações	podem	ser	escritas	como	p ∨ q, ÿ p e p → q. 
Uma	valoração	que	torna	as	 três	especificações	verdadeiras	deve	ter	p falsa para que ÿ p seja 
verdadeira. Como queremos que p ∨ q seja verdadeira e temos p	falsa,	devemos	ter	q verdadeira. 
Ainda	como		p → q é verdadeira quando p é falsa e q	é	verdadeira,	concluímos	que	essas	especi-
ficações	são	consistentes	porque	são	verdadeiras	quando	p é falsa e q é verdadeira. Poderíamos 
chegar à mesma conclusão analisando as tabelas-verdade e examinando as quatro possibilida-
des de valores-verdade para p e q. ◄
EXEMPLO 16	 O	sistema	de	especificações	do	Exemplo	15	continua	consistente	se	adicionarmos	a	especificação	
“A	mensagem	de	diagnóstico	não	é	retransmitida”?
Solução:	Verificando	o	Exemplo	15,	notamos	que	o	sistema	é	consistente	se	p é falsa e q é verda-
deira,	mas	a	nova	especificação	representa	ÿ q, que somente é verdadeira se q é falsa. Conseqüen-
temente,	esse	novo	sistema	é	inconsistente.	 ◄
Exemplos
Extras
Buscadores Booleanos
Conectivos	lógicos	são	largamente	usados	em	buscadores	de	grandes	conjuntos	de	informações,	
tais como índices de páginas da Internet. Como esses buscadores utilizam técnicas da lógica 
proposicional,	eles	são	chamados	de	buscadores booleanos.
Em	buscadores	booleanos,	o	conectivo	E (AND) é usado para encontrar informações que 
contenham	ambos	os	termos	procurados;	o	conectivo	OU (OR) é usado para encontrar informações 
que	contenham	um	ou	ambos	os	termos	procurados;	e	o	conectivo	NÃO (NOT),	às	vezes	escrito	
E NÃO (AND NOT), é usado para excluir alguma informação que contenha esse termo na procura. 
Um estudo cuidadoso de como são usados os conectivos lógicos é necessário quando buscadores 
booleanos são usados para localizar alguma informação de interesse potencial. O Exemplo 17 
ilustra como funcionam os buscadores booleanos.
EXEMPLO 17 Pesquisando Páginas da Internet	 A	maioria	dos	buscadores	na	Web,	os	quais	usualmente	
podem	nos	ajudar	a	encontrar	páginas	da	Internet	sobre	algum	objeto	específico,	utiliza	técni-
cas	 de	 buscadores	 booleanos.	 Por	 exemplo,	 usando	 um	 buscador	 booleano	 para	 achar	 uma	
página	da	Web	sobre	universidades	em	São	Paulo,	devemos	procurar	por	páginas	que	traba-
lhem com SÃO AND	PAULO	AND	UNIVERSIDADES.	Os	resultados	dessa	busca	incluirão	
as	páginas	que	contêm	as	três	palavras	SÃO,	PAULO	e	UNIVERSIDADES.	Isso	deve	incluir	
todas	as	páginas	de	interesse,	assim	como	páginas	sobre	universidades	que	têm	algum	texto	
sobre	São	Paulo.	(Note	que,	no	Google	e	em	muitos	outros	buscadores,	a	palavra	“AND”	não	
é	necessária;	essa	fica	subentendida	porque	todos	os	termos	são	incluídos.)	Segundo,	para	en-
contrar	páginas	de	universidades	em	São	Paulo	ou	Paraná,	devemos	procurar	por	páginas	que	
trabalhem	com	(SÃO	AND	PAULO	OR	PARANÁ)	AND	UNIVERSIDADES.	(Nota:	Aqui	o	
operador AND tem prioridade maior que o operador OR.	Além	disso,	no	Google,	os	termos	usa-
dos	devem	ser	SÃO	PAULO	OR	PARANÁ.)	O	resultado	dessa	busca	deve	incluir	todas	as	pági-
nas	 com	 a	 palavra	 UNIVERSIDADES	 e/ou	 uma	 ou	 ambas	 as	 palavras	 SÃO	 e	 PAULO	 ou	
PARANÁ.	Novamente,	páginas	com	textos	que	incluem	essas	palavras,	mas	que	não	são	de	inte-
resse,	serão	listadas.	Finalmente,	para	encontrar	páginas	sobre	universidades	em	São	Paulo,	não	
públicas,	podemos	primeiro	fazer	uma	busca	com	SÃO	AND	PAULO	AND	UNIVERSIDADES,	
mas	essa	busca	incluirá	as	páginas	sobre	as	universidades	também	públicas;	então,	podemos	buscar	
por	(SÃO	AND	PAULO	AND	UNIVERSIDADES)	NOT	PÚBLICAS.

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