Lógica para Computação

Prévia do material em texto

18/03/2011
1
Lógica para Computação
Professor Júlio César
Esp. Banco de Dados
jczars@yahoo.com.br
Sistema de Informação/UFPI‐Picos
18/03/2011 1Júlio César
Métodos para determinação da validade 
de fórmulas da Lógica Proposicional
• Método da Tabela Verdade;
• Método da Árvore Semântica;
• Método de Negação ao Absurdo;
18/03/2011 Júlio César 2
Introdução
• Um dos passos freqüentemente utilizados no 
estudo da lógica corresponde à análise  dos 
mecanismos que produzam ou verifiquem os 
argumentos válidos representados na Lógicaargumentos válidos representados na Lógica 
Proposicional  
18/03/2011 Júlio César 3
Método da Tabela Verdade;
• Método da força bruta;
• Neste método são consideradas todas as 
possibilidades de valores de verdades 
associados aos símbolos Proposicionais;associados aos símbolos Proposicionais;
• Este método não é recomendado para 
fórmulas com muitos símbolos Proposicionais. 
18/03/2011 Júlio César 4
Método da Tabela Verdade;
• H = ¬(P˄Q)↔((¬P)˅(¬Q)) – é uma tautulogia;
18/03/2011 Júlio César 5
•Não é recomendável para Fórmulas Grandes
Método da Árvore Semântica
• Determina a validade da formula a partir da 
estrutura de dados Árvore;
• Árvore é um conjunto de nós ou vértices 
ligados por arestas;ligados por arestas;
• Onde os nós são rotulados por números;
• Os nós finais são denominados folhas;
• O primeiro nó é chamado de nó raiz;
18/03/2011 Júlio César 6
18/03/2011
2
Exemplo de Árvore
• 1 é raiz
• 2,6,7 e 5 ‐ folhas
18/03/2011 Júlio César 7
Método da Árvore Semântica
• H=(P→Q)↔((¬Q)→(¬P)) – é uma tautulogia;
18/03/2011 Júlio César 8
Método da Árvore Semântica
18/03/2011 Júlio César 9
Conclusão: á formula é tautulogia, pois aparece T em todas as 
folhas da Árvore 
Método da Negação ou Absurdo
• É um método geral de demonstração;
• É utilizado para demonstrar a validade das 
fórmulas;
• Funciona, inicialmente negando a quilo que se , g q q
pretende demonstrar;
• Supôem‐se que H não é uma tautulogia;
• Deduções para concluir um fato contraditório ou 
absurdo.
• Absurdo – a suposição inicial seja falsa;
18/03/2011 Júlio César 10
Método da Negação ou Absurdo
• Exemplo:
– H=((PÆQ) ˄(QÆR))Æ(PÆR) seja uma tautulogia;
– Suponha por absurdo que esta fórmula não seja 
uma tautulogia;uma tautulogia;
– I[H]=F;
–
18/03/2011 Júlio César 11
Método da Negação ou Absurdo
• Observe que nas sub‐formulas Q tem de assumir dois 
valores é um absurdo;
18/03/2011 Júlio César 12
• Portanto a suposição inicial é falsa;
• Não existe interpretação I tal que I[H]=F;
• Logo H é uma Tautulogia
18/03/2011
3
Método da Negação ou Absurdo
• Conectivo Æ sua negação, obtém uma única 
possibilidade;
• ConecƟvo ˄ ‐ várias possibilidades;
C Ɵ ˅ ibilid d• ConecƟvo ˅ ‐ uma possibilidade; 
• Generalização do Método
– Possui ampla aplicação;
– Após um conjunto de deduções, se obtém um 
absurdo, então a afirmação inicial é verdadeira;  
18/03/2011 Júlio César 13
Método da Negação ou Absurdo
• Ausência de absurdo – podem ocorrer casos 
que o absurdo não é obtido;
• Exemplo: H é uma tautulogia;
• Duas possibilidades:
18/03/2011 Júlio César 14