A maior rede de estudos do Brasil

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

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

seqüência binária: lista de bits
operações binárias: operações	 entre	 seqüências	 de	 bits,	
operando cada um de seus bits correspondentes
tautologia: proposição composta que é sempre verdadeira
contradição: proposição composta que é sempre falsa
contingência: proposição	composta	que	é	às	vezes	verdadeira,	
às vezes falsa
proposições compostas consistentes: proposições compostas 
para as quais existe uma valoração para as variáveis que faz 
todas as proposições verdadeiras
proposições compostas logicamente equivalentes: proposições 
compostas que sempre têm o mesmo valor-verdade
predicado: parte de uma sentença que atribui uma propriedade 
ao sujeito
função proposicional: sentença com uma ou mais variáveis que 
se torna uma proposição quando cada uma das variáveis 
recebe	um	valor	ou	é	fechada	por	um	quantificador
domínio (ou universo) de discurso: valores que uma variável 
em uma função proposicional pode ter
∃x P (x) (quantificação existencial de P (x)): proposição que 
é verdadeira se e somente se existir um x no	domínio,	 tal	
que P(x)	é	verdadeira
∀x P (x) (quantificação universal de P (x)): proposição que é 
verdadeira se e somente se P (x)	for	verdadeira	para	todo	x 
no domínio
expressões logicamente equivalentes: expressões que têm o 
mesmo	valor-verdade,	não	importando	qual	função	proposi-
cional e qual domínio são usados
variável livre: variável não ligada em uma função proposicional
variável ligada: variável	que	é	quantificada
escopo de um quantificador: porção de uma sentença em que 
o	quantificador	liga	suas	variáveis
argumento: seqüência de sentenças
forma de argumento: seqüência de proposições compostas que 
envolve variáveis proposicionais
premissa: sentença,	em	um	argumento,	ou	forma	de	argumento,	
que	não	seja	a	final
conclusão: sentença	 final	 de	 um	 argumento	 ou	 forma	 de	
argumento
forma válida de argumento: seqüência de proposições com-
postas	que	envolve	variáveis	proposicionais,	tal	que	a	verda-
de de todas as premissas implica a verdade da conclusão
argumento válido: argumento com uma forma válida de 
argumento
regra de inferência: forma válida de argumento que pode ser 
usada na apresentação de argumentos válidos
falácia: forma inválida de argumento freqüentemente usado 
incorretamente	como	uma	regra	de	inferência	(ou,	às	vezes,	
mais	geralmente,	um	argumento	incorreto)
raciocínio circular ou que carrega a pergunta: raciocínio 
em que um ou mais passos se baseiam na verdade da 
sentença que está sendo demonstrada
teorema: afirmação	 matemática	 que	 pode	 ser	 demonstrada	
verdadeira
conjectura: afirmação	 matemática	 proposta	 como	 verdade,	
mas que ainda não foi provada
demonstração: modelo de um teorema que é verdadeiro
axioma: sentença que é assumida como verdadeira e que pode 
ser usada como base para demonstrar teoremas
lema: teorema usado para demonstrar outros teoremas
corolário: proposição que pode ser demonstrada como uma 
conseqüência de um teorema que está sendo demonstrado
demonstração por vacuidade: demonstração de que p →	q é 
verdadeira com base no fato de que p é falsa
demonstração por trivialização: demonstração de que p →	q 
é verdadeira com base no fato de que q é verdadeira
demonstração direta: demonstração de que p →	q é verdadei-
ra,	que	procede	mostrando	que	q deve ser verdadeira quan-
do p é verdadeira
demonstração por contraposição: demonstração de que p →	
q é	verdadeira,	que	procede	mostrando	que	p deve ser falsa 
quando q é falsa
demonstração por contradição: demonstração de que p é 
verdadeira com base na verdade do condicional ÿ p	→	q,	na	
qual q é uma contradição
demonstração por exaustão: demonstração que estabelece 
um	resultado,	verificando	uma	lista	de	todos	os	casos
demonstração por casos: demonstração quebrada em casos se-
parados em que esses casos cobrem todas as possibilidades
sem perda de generalidade: quando se assume em uma de-
monstração	que	 é	possível	demonstrar	um	 teorema,	 redu-
zindo o número de casos necessários para a demonstração
contra-exemplo: elemento x, tal que P(x)	é	falsa
demonstração de existência construtiva: demonstração de 
que	 um	 elemento	 com	 uma	 propriedade	 específica	 existe	
que explicitamente encontra um tal elemento
demonstração de existência não construtiva: demonstração 
de	que	um	elemento	com	uma	propriedade	específica	existe	
que não encontra explicitamente um tal elemento
número racional: número que pode ser expresso como a razão 
de dois inteiros p e q, tal que q  0
demonstração de unicidade: demonstração de que existe 
exatamente um elemento que satisfaz uma propriedade es-
pecífica
RESULTADOS
As	equivalências	lógicas	dadas	nas	tabelas	6,	7	e	8	da	Seção	
1.2.
Leis	de	De	Morgan	para	quantificadores.
Regras de inferência para os cálculos proposicionais.
Regras	de	inferência	para	sentenças	quantificadas.
Questões de Revisão
1. a) Defina	a	negação	de	uma	proposição.
b) Qual é a negação de “Este é um curso entediante”?
2. a) Defina	(usando	 tabelas-verdade)	a	disjunção,	conjun-
ção,	ou	exclusivo,	condicional	e	bicondicional	das	pro-
posições p e q.
b) Quais	são:	disjunção,	conjunção,	ou	exclusivo,	condi-
cional e bicondicional das proposições “Eu vou ao ci-
nema esta noite” e “Eu vou terminar minha lição de 
casa de matemática discreta”?
3. a) Descreva pelo menos cinco modos diferentes de 
escrever o condicional p →	q em português.
b) Defina	 a	 oposta	 e	 a	 contrapositiva	 de	 uma	 sentença	
condicional.
c) Dê a oposta e a contrapositiva da sentença condicional 
“Se	amanhã	fizer	sol,	então	eu	vou	fazer	uma	trilha	na	
mata” .
4. a) O	que	 significa	 duas	 proposições	 serem logicamente 
equivalentes?
1-105 Questões de Revisão 105
106	 	1	/	Os	Fundamentos:	Lógica	e	Demonstrações	 1-106
b) Descreva as maneiras diferentes de mostrar que duas 
proposições compostas são logicamente equivalentes.
c) Mostre pelo menos dois modos diferentes em que as 
proposições compostas ÿ p ∨	(r	→	ÿ q)	e	ÿ p ∨ ÿ q ∨ 
ÿ r são equivalentes.
5. (Depende do conjunto de exercícios da Seção 1.2)
a) Dada	uma	tabela-verdade,	explique	como	usar	a	forma	
normal disjuntiva para construir proposições compostas 
com esta tabela-verdade.
b) Explique	por	que	a	parte	(a)	mostra	que	os	operadores	
∧,	∨ e ÿ  são funcionalmente completos.
c) Existe	 um	 operador,	 tal	 que	 o	 conjunto	 com	 apenas	
esse operador seja funcionalmente completo?
6. O	 que	 são	 quantificações	 universal	 e	 existencial	 de	 um	
predicado P (x)?	Quais	são	suas	negações?
7. a) Qual	a	diferença	entre	a	quantificação	∃x∀y P (x,	y)	e	
∀y∃x P (x,	y),	em	que	P (x, y)	é	um	predicado?
b) Dê um exemplo de um predicado P (x, y),	tal	que	∃x∀y 
P (x,	y)	e	∀y∃x P (x,	y)	têm	diferentes	valores-verdade.
8. Descreva o que chamamos de argumento válido em lógica 
proposicional e mostre que o argumento “Se a Terra é 
plana,	então	podemos	navegar	até	a	borda	da	Terra”,	“Você	
não	pode	navegar	até	a	borda	da	Terra”,	portanto	“A	Terra	
não é plana” é um argumento válido.
9. Use as regras de inferência para mostrar que as pre-
missas “Todas as zebras têm listras” e “Mark é uma 
zebra”	são	verdadeiras,	então	a	conclusão	“Mark	tem	
listras” é verdadeira.
10. a) Descreva	 o	 que	 se	 entende	 por	 demonstração	 direta,	
demonstração por contraposição e demonstração por 
contradição de uma sentença condicional p →	q.
b) Dê	uma	demonstração	direta,	uma	demonstração	por	
contraposição e uma demonstração por contradição da 
sentença: “Se n é	par,	então	n + 4 é par”.
11. a) Descreva um modo de provar a bicondicional p ↔	q.
b) Demonstre a sentença: “O inteiro 3n + 2 é ímpar se 
e somente se o inteiro 9n +	5	é	par,	em	que	n é um 
inteiro”.
12. Para demonstrar que as sentenças p1,	p2,	p3 e p4 são equiva-
lentes,	é	suficiente	mostrar	que	as	sentenças	condicionais	p4 
→	p2,	p3

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