Introdução à Lógica Matemática

Prévia do material em texto

Lógica Matemática
Lógica matemática
Cronograma
Aula 1: Proposições, conectivos e tabela verdade.
Aula 2: Inferência
Aula 3: Quantificadores
Aula 4: Princípio de indução finita 
Prof. Dr. Ricardo Cardoso de Oliveira
PROPOSIÇÕES, CONECTIVOS E TABELA VERDADE
“É verdade!”
SATO, Sabrina
Lógica matemática
1. Proposições
A clássica lógica proposicional estuda relações entre objetos denominados proposições, os quais podem ser usualmente (nem sempre) ser interpretadas como sentenças em Língua Portuguesa. 
As sentenças podem ser de vários tipos:
		i) declarativas (afirmações)
		ii) interrogativas
		iii) modais
		iv) performáticas (ou de comandos)
Lógica matemática
1. Proposições
A princípio, podemos ter a impressão de que toda sentença declarativa é verdadeira ou falsa.
“Esta sentença é falsa”
Paradoxo de Eubulides de Mileto
Lógica matemática
1. Proposições
Definição: Proposição é um sentença declarativa que é verdadeira ou falsa, mas não ambas.
	Uma proposição assume apenas um dos valores: verdadeiro (V) ou falso (F). Adotaremos, três princípios:
Princípio da identidade: Toda proposição é igual a si.
Princípio de não contradição: Uma proposição não pode ser verdadeira e falsa ao mesmo tempo.
Princípio do terceiro excluído: Toda proposição é verdadeira ou falsa, não há terceira possibilidade.
Lógica matemática
Exemplo 1
	Vejamos alguns exemplos de proposições.
A) P: A Lua é feita de chocolate.
B) Q: 4 é um número primo.
C) R: 3 + 3 = 6
D) T: 4 é um número positivo e 3 é ímpar.
E) L: Choveu no Brasil em 12 de Abril de 1523.
Lógica matemática
Exemplo 2
	Vejamos alguns exemplos de sentenças que NÃO são proposições.
A) x = 3
B) Você está bem?
C) Vá embora!
Lógica matemática
2. Conectivos Lógicos
	As proposições podem ser combinadas por meio dos conectivos lógicos, gerando sentenças mais ricas. Alguns conectivos usados são:
negação: 
conjunção: 
disjunção: 
condicional: 
bicondicional: 
Lógica matemática
2. Conectivos Lógicos
Operadores lógicos ou conectivos lógicos efetuam operação sobre as proposições.
Quando um operador lógico é usado para construir uma nova proposição, seu valor-verdade depende da natureza dos operadores lógicos usados e do valor-verdade das proposições.
Lógica matemática
2. Conectivos Lógicos
NEGAÇÃO
		Dada uma proposição P, podemos escrever outra proposição (lê-se “não P”), denominada negação de P. O valor lógico de é o oposto do valor lógico de P.
 
	A tabela verdade da negação é:
	P	
	V	F
	F	V
Lógica matemática
2. Conectivos Lógicos
CONJUNÇÃO
		Sejam P e Q duas proposições, a conjunção das proposições P e Q, denotada por , é uma nova proposição que assume valor lógico verdadeiro somente quando P e Q forem verdadeiras simultaneamente.
	A tabela verdade, do conectivo conjunção, é:
	P	Q	
	V	V	V
	V	F	F
	F	V	F
	F	F	F
Lógica matemática
2. Conectivos Lógicos
DISJUNÇÃO
		Sejam P e Q duas proposições, a disjunção das proposições P e Q, denotada por , é uma nova proposição que assume valor lógico verdadeiro somente quando P ou Q forem verdadeiras simultaneamente, não necessariamente simultâneas.
	A tabela verdade, do conectivo disjunção, é:
	P	Q	
	V	V	V
	V	F	V
	F	V	V
	F	F	F
Lógica matemática
2. Conectivos Lógicos
CONDICIONAL
		Sejam P e Q duas proposições, a condicional das proposições P e Q, denotada por , é uma nova proposição que assume valor lógico falso somente quando P for verdadeira e Q for falsa.
	A tabela verdade, do conectivo condicional, é:
	P	Q	
	V	V	V
	V	F	F
	F	V	V
	F	F	V
Lógica matemática
2. Conectivos Lógicos
BICONDICIONAL
		Sejam P e Q duas proposições, a bicondicional das proposições P e Q, denotada por , é uma nova proposição que assume valor lógico verdadeiro somente quando P e Q forem verdadeiras ou P e Q forem falsas.
A tabela verdade, do conectivo bicondicional, é:
	P	Q	
	V	V	V
	V	F	F
	F	V	F
	F	F	V
Lógica matemática
3. Tabelas-verdade
Faremos uso de sinais: ( ); [ ] e { } para evitar ambiguidades.
Para evitar uso excessivo de sinais vamos convencionar a ordem decrescente de prioridade: 
									
 o conectivo tem prioridade em relação aos outros;
				 representa 
os conectivo e possuem a mesma ordem de prioridade;
		 		 representa 
Lógica matemática
3. Tabelas-verdade
	O valor verdade de proposições compostas obtidas via combinação de conectivos fica completamente determinado pelos valores das proposições componentes e pela natureza dos conectivos.
Lógica matemática
Exemplo 3
Construa a tabela-verdade da proposição 
Solução: Observe que há duas proposições simples: P e Q. Assim, a tabela-verdade terá 4 linhas.
	P		Q			P		Q
								
								
								
								
								
	P	Q
	V	V
	V	F
	F	V
	F	F
	1	1
Lógica matemática
Exemplo 4
Construa a tabela-verdade da proposição 
Solução: Observe que há duas proposições simples: P e Q. Assim, a tabela-verdade terá 4 linhas.
	P	Q	P		Q			P
	V	V						
	V	F						
	V	V						
	V	F						
	1	1						
	Q
	
	
	
	
	
Lógica matemática
3. Tabelas-verdade
Definição: Uma tautologia (T) é uma proposição que assume sempre valor verdade V, independente dos valores das proposições que a compõe. Por outro lado, uma contradição (C) é uma proposição sempre falsa. Uma contingência é uma proposição que assume pelo menos um valor lógico falso e um valor lógico verdadeiro. 
Lógica matemática
Exemplo 5
Construa a tabela-verdade da proposição
Solução: Observe que há duas proposições simples: P e Q. Assim, a tabela-verdade terá 4 linhas.
	P	Q		P					P
									
									
									
									
									
	
	
	
	
	
	
	Q
	
	
	
	
	
Lógica matemática
Exemplo 6
Construa a tabela-verdade da proposição
Solução: Observe que há duas proposições simples: P e Q. Assim, a tabela-verdade terá 4 linhas.
	P	Q		P					P
	V	V							
	V	F							
	F	V							
	F	F							
	1	1							
	
	
	
	
	
	
	Q
	
	
	
	
	
Lógica matemática
4. Equivalências
Definição: Duas proposições P e Q são equivalentes (notação: ou ) se, e somente se for uma tautologia.
Lógica matemática
Tabela – Lista de identidades lógicas
Lógica matemática
Exemplo 7
Prove que .
Solução: De fato,
	P	Q	P		Q		~	P	
	V	V							
	V	F							
	F	V							
	F	F							
	1	1							
	
	
	
	
	
	
Lógica matemática
Tabela – Lista de equivalências lógicas
Lógica matemática
5. Implicações
Definição: Dado duas proposições P e Q, dizemos que “P implica Q” (notação: ) quando a condicional for uma tautologia.
Lógica matemática
Tabela – Lista de implicações lógicas
Lógica matemática
Exemplo 8
Prove que .
Solução: De fato,
	P	Q	P		P		Q		
	V	V							
	V	F							
	F	V							
	F	F							
	1	1							
Lógica matemática
Exemplo 9
(CESGRANRIO) Considere a proposição composta “Se o mês tem 31 dias, então não é setembro”. A proposição composta equivalente é
(A) “O mês tem 31 dias e não é setembro”.
(B) “O mês tem 30 dias e é setembro”.
(C) “Se é setembro, então o mês não tem 31 dias”.
(D) “Se o mês não tem 31 dias, então é setembro”.
(E) “Se o mês não tem 31 dias, então não é setembro”.
Lógica matemática
Exemplo 10
(CESGRANRIO) A negação da declaração: “Paula é alta e não é loira” é
(A) Paula é loira.
(B) Paula é alta e loira.
(C) Paula não é alta e é loira.
(D) Paula não é alta ou é loira.
(E) Paula não é alta e não é loira.
Lógica matemática
Exemplo 12
(FGV) A negação lógica da sentença “Se não há higiene então não há saúde” é:
(A) Se há higiene então há saúde.
(B) Não há higiene e há saúde.
(C) Há higiene e não há saúde.
(D) Não há higiene ou não há saúde.
(E) Se há saúde então há higiene.