29 - Conseqüência lógica e quivalência

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

*
Lógica Proposicional
Conseqüência lógica e equivalência
*
Conseqüência lógica
 Uma fórmula B é conseqüência lógica de uma fórmula A, denotando-se A ⊨ B sse 
 Toda interpretação I que satisfaz A também satisfaz B, i.e. tal que I[A] = T implica I[B] = T ;
 De modo similar D é conseqüência lógica de um conjunto de fórmulas (ou teoria) Γ ={A1, A2 … An }, denotando-se por Γ ⊨ B sse 
 Para toda interpretação I que satisfaz todas as fórmulas de Γ também satisfaz B.
*
*
Conseqüência lógica
 Exemplo:
		Modus ponens: P , (P  Q) ⊨Q .
 Teorema da dedução:
		Γ, A ⊨ B sse Γ ⊨ A  B .
 Mais exemplos…
*
*
Prova do Teorema da dedução
 A prova de	Γ, A ⊨ B sse Γ ⊨ A  B é feita em 2 mãos: 
 Γ, A ⊨ B implica Γ ⊨ A  B
 Para toda I[Γ] = T , I[A  B] tem que ser tb T
 Se I[A] = T, então I[B]=T já que Γ, A ⊨ B e I[AB]=T
 Se I[A] = F, então I[A  B] = T
 Γ ⊨ A  B implica Γ, A ⊨ B
 Toda I[Γ] = T faz com que I[A  B] =T
 Por contradição: Suponhamos que 
 I[Γ] = T, I[A]=T e, absurdamente I[B] = F
 I [A B] seria F, o que contradiz a premissa de que
 I[Γ] = T, I[AB]= T
 Portanto I[B]=T!
*
*
Equivalência lógica
 Duas fórmulas A e B são logicamente equivalentes, representando-se por A ≡ B sse 
 A ⊨ B e B ⊨ A
 Na prática para verificar se duas fórmulas são logicamente equivalentes basta construir as tabelas-verdade para A e B e verificar se as colunas para A e para B são idênticas;
 Definição: A ↔ B ≡ (A  B ) ^ (B  A )
 Teorema: A ≡ B sse A ↔ B é tautologia.
*
*
Algumas equivalências notáveis
 ¬¬P ≡ P (dupla negação);
 P  Q ≡¬P V Q (definição de  em função de ¬ e v);
 ¬(P V Q) ≡ (¬P ^ ¬Q) e ¬(P ^ Q) ≡ (¬P V ¬Q) 
 Leis de De Morgan
 P ^ (Q V R) ≡ (P ^ Q) V (P ^ R) 
 Distributividade de ^ sobre v
 P v (Q ^ R) ≡ (P v Q) ^ (P v R)
 Distributividade de v sobre ^
*
*
Equivalência lógica
(Re)definições de conectivos em função de  e  :
 P  Q ≡¬P V Q ≡ ¬(P ^ ¬Q);
 P V Q ≡ ¬(¬P ^ ¬Q)
É possível se definir todos os conectivos em função de um só ?
*
*
Um só conectivo
# (negação conjunta) e
 | (disjunção alternativa), definidos pela seguinte tabela:
		P 		Q 	P # Q 	P | Q
		1 		1 	 0		 0
		1 		0 	 1 		 0
		0 		1 	 1 		 0
		0		0	 1		 1
*
*
NAND
Fazendo:
  P = (P # P), E
 P  Q =((P # Q) # (Q # Q)), pode-se definir os conectivos  e  a partir de #, e obter os demais conectivos a partir desses.
Deve-se comprovar que as tabelas-verdade que são obtidas coincidem com as previamente conhecidas.
Reciprocamente, os conectivos # e | podem ser definidos por: P # Q =  (P  Q) E P | Q =  (P  Q):
*
*
Lógica Proposicional
Exercícios (pg. 27).