Baixe o app para aproveitar ainda mais
Prévia do material em texto
Lógica Proposicional Validade de fórmulas Material baseado no livro Lógica para ciência da computação: fundamentos de linguagem, semântica e sistemas de dedução, João Nunes de Souza. Validade de fórmulas Métodos para determinação de validade de fórmulas Tabela verdade Árvore semântica Negação ou absurdo Tabela verdade Método da força bruta Dada uma fórmula H, suponha P1, P2,..., Pn São consideradas todas as possibilidades de valores de verdade Exemplo: leis de De Morgan Define a regra de distribuição do conectivo ¬ em uma conjunção/disjunção H=¬(P∧Q) ↔ (¬P ∨ ¬Q) G=¬(P∨Q) ↔ (¬P∧¬Q) Tabelas Exemplo: leis de De Morgan H=¬(P∧Q) ↔ (¬P ∨ ¬Q) G=¬(P∨Q) ↔ (¬P∧¬Q) P Q ¬(P∧Q) (¬P ∨ ¬Q) H ¬(P∨Q) (¬P∧¬Q) G T T F F T F F T T F T T T F F T F T T T T F F T F F T T T T T T Tabela verdade A partir da tabela verdade associada a uma fórmula H é possível obter várias propriedades semânticas Se a coluna de H contém apenas o símbolo T, então H é uma tautologia Se a coluna de H contém apenas o símbolo F, então H é uma contradição. Se a coluna de H contém pelo menos um símbolo T, então H é satisfazível. Método aplicável a fórmulas que contém um pequeno número de símbolos proposicionais – tabelas pequenas Uma fórmula que contenha 8 símbolos proposicionais tem tabela verdade associada contendo 256 linhas (2n) Árvore semântica Estrutura de dados – árvore árvore = conjunto de nós (vértices) ligados por arestas. Exemplo Nós: números raiz: 1 folhas: ? 1 7 2 6 3 4 5 Árvore semântica Exemplo: Lei da contraposição H = (P→Q) ↔ ((¬Q) → (¬P)) (tautologia) Quais as possíveis interpretações para P ? O Nó 2 corresponde à fórmula Nó 2 = (P→Q) ↔ ((¬Q) → (¬P)) T T Nó 2 = (P→Q) ↔ ((¬Q) → (¬P)) T FT Nó 3 = (P→Q) ↔ ((¬Q) → (¬P)) F T T T TF 1 2 3 I[P]=T I[P]=F 1 2 3 I[P]=T I[P]=F T P Q P → Q T T T T F F F T T F F T Árvore semântica Exemplo: Lei da contraposição Nó 4 = (P→Q) ↔ ((¬Q) → (¬P)) T T T T FT T FT Nó 5 = (P→Q) ↔ ((¬Q) → (¬P)) T F F T TF F FT Conclusão: Para o caso em que todas as folhas da árvore são rotuladas com F, tem-se fórmula contraditória Se pelo menos uma folha estiver rotulada com T, então fórmula satisfazível Neste caso, temos uma tautologia 1 2 3 I[P]=T I[P]=F 4 5 I[Q]=T I[Q]=F T T T Método da negação ou absurdo Método geral de demonstração empregado aqui para demonstrar a validade de fórmulas Ponto de partida: negação daquilo que se quer demonstrar Se o objetivo é demonstrar que a fórmula H é uma tautologia, então supõe-se que H não é uma tautologia Resultado = absurdo, logo a suposição inicial é falsa Exemplo – Lei da transitividade Lei da transitividade: ((P → Q)∧(Q → R)) →(P → R) Por absurdo: ((P → Q) ∧(Q → R)) →(P → R) F I[(P → Q) ∧(Q → R) ]=T e I[(P → R)]=F ((P → Q) ∧ (Q → R)) →(P → R) T F F ((P → Q) ∧ (Q → R)) →(P → R) T T T F T F F Neste ponto I[P] = T e I[R] = F Assim ((P → Q) ∧(Q → R)) →(P → R) T T T T F F T F F P Q P → Q T T T T F F F T T F F T Exemplo – Lei da transitividade Lei da transitividade: ((P → Q)∧(Q → R)) →(P → R) Assim ((P → Q) ∧ (Q → R)) →(P → R) T T T T F F T F F Para concluir qual a interpretação de Q veja as subfórmulas (P → Q) e (Q → R) I[Q]=F? ou I[Q]=T? ((P → Q) ∧ (Q → R)) →(P → R) T T T T F T F F T F F P Q P → Q T T T T F F F T T F F T Aplicação do método da negação Demonstração da contradição Para provar que H é contraditória Supõe-se que H é satisfazível Existe I[H]=T Fórmulas com o conectivo → Só existe uma possibilidade de absurdo I[Antecedente]=T e I[Consequente]=F Fórmulas com o conectivo ∧, ∨ Supondo a veracidade de A ∧ B: I[A]=T e I[B]=T Supondo a falsidade de A ∨ B: I[A]=F e I[B]=F Ausência de absurdo Se uma asserção é negada, mas o absurdo não aparece, nada se pode concluir sobre a veracidade da asserção Exemplo: (P→Q) ↔((¬P)→(¬Q)) Por absurdo: F Possibilidade 1: T F F Possibilidade 2: F F T Ausência de absurdo Exemplo: H= (P→Q) ↔((¬P)→(¬Q)) Possibilidade 1: T F F F T T F TF F FT OK! Possibilidade 2: F F T T F F F FT T TF OK! Não se pode concluir que H é tautologia Se I[P]=F e I[Q]=T, então I[H]=F P Q P → Q T T T T F F F T T F F T Exercícios Árvore semântica ¬(¬H) ↔ H (P→Q) ↔((¬P)→(¬Q)) Negação ¬(¬H) ↔ H (P→Q) ↔((¬Q)→(¬P)) H=(P∧Q) ↔((¬P∨Q)) é tautologia? Lei da negação (¬(¬H)) ↔ (H) Leis de De Morgan (¬(P∨Q)) ↔ (¬P ∧ ¬Q) (¬(P∧Q)) ↔ (¬P ∨ ¬Q) Leis de eliminação (P→Q) ↔ (¬P ∨ Q) (P ↔ Q) ↔ ((P → Q) ∧(Q → P)) Leis distributivas (F ∨ (G ∧ H)) ↔ ((F ∨ G) ∧(F ∨ H)) (F ∧ (G ∨ H)) ↔ ((F ∧ G) ∨ (F ∧ H))
Compartilhar