Cálculo Proposicional - Exemplo

Você pode assitir um vídeo dessa apresentação no Canal "REde Requisitos" do YouTube.

Exercício resolvido com comentários sobre Lógica Matemática para aplicação na Programação Lógica. Solução do pedido apresentado no livro Foundations of Logic Programming de J. W. Lloyd.

1. Fundamentos da Lógica Matemática Cálculo Proposicional rederequisitos.com.br - facebook.com / rederequisitos - [email protected] Roberto Paldês

2. Exercício Demonstre, usando o princípio de resolução no cálculo proposicional, que a fórmula p ^ (q  r) é consequência lógica do conjunto de fórmulas {( p q )r, rp }

3. Fundamentos Cod Proposição Equivale a Regra [R1] p  r ┐p V r Eliminação da Implicação [R2] ┐(p ^ q) ┐p V ┐q De Morgan [R3] ┐(p V q) ┐p ^ ┐q De Morgan [R4] ┐(┐p) p Eliminação da dupla negação [R5] p V (q ^ r) pVq ^ pVr Distributiva de V sobre ^ [R6] p ^ (q V r) p^q V p^r Distributiva de ^ sobre V

4. Solução Para provar que a fórmula F é consequência lógica do conjunto de fórmulas S basta demonstrar que S U { ┐F } é inconsistente

5. Solução 1º Passo: Construir um conjunto de cláusulas proposicionais para ┐F e S Sendo: F = p ^ (q  r) Logo: ┐F = ┐ ( p ^ (q  r))

6. Solução – 1º Passo - ┐F ┐F = ┐( p ^ (q  r)) ┐( p ^ ( ┐ q V r) ) [R1]

7. Solução – 1º Passo - ┐F ┐F = ┐( p ^ (q  r)) ┐( p ^ ( ┐ q V r) ) [R1] ┐ p V ( ┐ ( ┐ q V r) ) [R2]

8. Solução – 1º Passo - ┐F ┐F = ┐( p ^ (q  r)) ┐( p ^ ( ┐ q V r) ) [R1] ┐ p V ( ┐ ( ┐ q V r) ) [R2] ┐ p V ( ┐ ( ┐ q) ^ ┐ r ) [R3]

9. Solução – 1º Passo - ┐F ┐F = ┐( p ^ (q  r)) ┐( p ^ ( ┐ q V r) ) [R1] ┐ p V ( ┐ ( ┐ q V r) ) [R2] ┐ p V ( ┐ ( ┐ q) ^ ┐ r ) [R3] ┐ p V ( q ^ ┐ r ) [R4]

10. Solução – 1º Passo - ┐F ┐F = ┐( p ^ (q  r)) ┐( p ^ ( ┐ q V r) ) [R1] ┐ p V ( ┐ ( ┐ q V r) ) [R2] ┐ p V ( ┐ ( ┐ q) ^ ┐ r ) [R3] ┐ p V ( q ^ ┐ r ) [R4] (┐ p V q ) ^ ( ┐ p V ┐ r ) [R5]

11. Solução – 1º Passo - S S = {( p q )r, rp }

12. Solução – 1º Passo - S S = {( p q )r, rp } {( ┐ p V q ) r , rp } [R1]

13. Solução – 1º Passo - S S = {( p q )r, rp } {( ┐ p V q ) r , rp } [R1] {( ┐ ( ┐ p V q)) V r , rp } [R1]

14. Solução – 1º Passo - S S = {( p q )r, rp } {( ┐ p V q ) r , rp } [R1] {( ┐ ( ┐ p V q)) V r , rp } [R1] {( ┐ ( ┐ p V q)) V r , ┐ r V p} [R1]

15. Solução – 1º Passo - S S = {( p q )r, rp } {( ┐ p V q ) r , rp } [R1] {( ┐ ( ┐ p V q)) V r , rp } [R1] {( ┐ ( ┐ p V q)) V r , ┐ r V p} [R1] {( ┐ ( ┐ p) ^ ┐ q) V r , ┐ r V p} [R3]

16. Solução – 1º Passo - S S = {( p q )r, rp } {( ┐ p V q ) r , rp } [R1] {( ┐ ( ┐ p V q)) V r , rp } [R1] {( ┐ ( ┐ p V q)) V r , ┐ r V p} [R1] {( ┐ ( ┐ p) ^ ┐ q) V r , ┐ r V p} [R3] {( p ^ ┐ q) V r , ┐ r V p} [R4]

17. Solução – 1º Passo - S S = {( p q )r, rp } {( ┐ p V q ) r , rp } [R1] {( ┐ ( ┐ p V q)) V r , rp } [R1] {( ┐ ( ┐ p V q)) V r , ┐ r V p} [R1] {( ┐ ( ┐ p) ^ ┐ q) V r , ┐ r V p} [R3] {( p ^ ┐ q) V r , ┐ r V p} [R4] {( p V r ) ^ ( ┐ q V r ) , ┐ r V p} [R5]

18. Solução 2º Passo: Construir, então, uma refutação para o conjunto de cláusulas.

19. Solução 2º Passo: Construir, então, uma refutação para o conjunto de cláusulas. Ou seja: S U { ┐F } {(┐ p V q ) ^ ( ┐ p V ┐ r ), (p V r ) ^ ( ┐ q V r ) , ┐ r V p} ┐F S {┐ p V q , ┐ p V ┐ r , p V r , ┐ q V r , ┐ r V p} Como o ^ é um conector entre cláusulas, foi trocado por ,

20. Solução – 2º Passo { ┐ p V q , ┐ p V ┐ r , p V r , ┐ q V r , ┐ r V p }

21. Solução – 2º Passo { ┐ p V q , ┐ p V ┐ r , p V r , ┐ q V r , ┐ r V p } ┐ p V q , ┐ q V r ┐ p V r , ┐ p V ┐ r ┐ p V ┐p ┐p p V r , ┐ r V p p V p p Contradição

22. Resposta Ficou provado que S U { ┐F } é inconsistente. Logo, p ^ (q  r) é uma consequência logica de {( p q )r, rp }

23. Fundamentos da Lógica Matemática Cálculo Proposicional Esperamos ter te ajudado!