Aula 08 de Lógica

Tableaux Semânticos na Lógica Proposicional

Um tableaux semântico na Lógica Proposicional é uma sequência de fórmulas construída de acordo com certas regras e geralmente apresenta a forma de uma árvore. Os elementos básicos que compõem esta árvore são definidos a seguir.

Definição (elementos básicos de um tableaux semântico)
Os elementos básicos de um tableaux semântico na Lógica Proposicional são definidos pela composição dos elementos:

O alfabeto da Lógica Proposicional;
O conjunto das fórmulas da Lógica Proposicional
Um conjunto de regras de dedução.
O tableau semântico contém apenas regras de dedução, que definem o mecanismo de inferência, permitindo a dedução de conhecimento. As regras são definidas a seguir.

Definição (regras de inferência do tableaux semântico)
Sejam A e B duas fórmulas da Lógica Proposicional. As regras de inferência do tableau semântico na Lógica Proposicional são R1, …, R9 indicadas a seguir.

O método de prova nos tableaux é feita utilizando o método da negação ou absurdo. Assim, para provar uma fórmula A, é considerada inicialmente a sua negação ¬A. Em seguida, o tableaux semântico associado a ¬A é construído. Devido a este fato, tal sistema também é denominado como um sistema de refutação. O tableau semântico é construído a partir de ¬A utilizando as regras de dedução, cuja aplicação decompõe a fórmula ¬A em subfórmulas.

E o que estas regras dizem? O entendimento de cada uma destas inferências derivadas de proposições lógicas são a base para o domínio do método. Então vamos analisar cada uma das regras.

O significado da regra R1.

Na montagem da árvore semântica o método a regra R1 diz que devemos fazer a seguinte operação:

Quando encontramos a proposição A∧B (A e B), devemos escrever logo abaixo o A e depois, em outra linha o B. Esta forma de escrita traduz o significado semântico, ou seja, dada a fórmula A∧B, deduzimos A e B. Detalhando, se A∧B = V então se deduz o valor lógico de A e B.

O significado da regra R2.

Na montagem da árvore semântica o método a regra R2 diz que devemos fazer a seguinte operação:

Ao se encontrar a operação A∨B (A ou B), deve-se derivar para uma operação que coloca A e B na linha abaixo da operação lógica de disjunção, com setas partindo do operador ∨. Isso é a representação de disjunção na árvore que levará a solução do problema, esta simbologia mostra que se A∨B = V então é possível achar o valor de A ou B. É importante salientar que é possível que A e B sejam verdadeiros, visto que, a disjunção que se está tratando aqui não é a disjunção exclusiva.

O significado da regra R3.

Na montagem da árvore semântica o método a regra R3 diz que devemos fazer a seguinte operação:

A proposição A→B (A implica B) deve ser traduzida para a árvore semântica da seguinte forma, a partir do sinal de implicação → se desenha duas setas apontando para linha abaixo da preposição lógica de implicação, escreve-se abaixo destas setas ¬A(não A) e B. Novamente temos o sinal que representa a disjunção na árvore semântica, e o motivo disso é que na proposição A→B = V pode-se deduzir ¬A ou B, pois tendo A→B = V, ou ¬A = V ou B = V.

O significado da regra R4.

Na montagem da árvore semântica o método a regra R4 diz que devemos fazer a seguinte operação:

Já se sabe que as setas em uma árvore semântica simboliza a disjunção e a regra 4 diz que uma vez deduzida a fórmula A↔B (a bicondiciona B), então pode-se deduzir a fórmula A e B (A∧B) ou não A e não B (¬A∧¬B). A título de exercício de revisão prove que (A↔B) ≡ (A∧B)∨(¬A∧¬B).

O significado da regra R5.

Na montagem da árvore semântica o método a regra R5 diz que devemos fazer a seguinte operação:

A mais simples e a mais evidente de todas. Esta regra diz que ¬¬A (não não A) deve ser resolvido colocando-se, na linha abaixo da proposição a derivação A. Já vimos anteriormente que semanticamente, a dupla negação de uma proposição, equivale a proposição.

O significado da regra R6.

Na montagem da árvore semântica o método a regra R6 diz que devemos fazer a seguinte operação:

Essa regra pode gerar surpresa visto que a regra R1 onde (A∧B) A e B geram duas linhas abaixo da proposição com as derivações A e abaixo o B, então por que não teríamos o mesmo aqui? Repare que a solução de  ¬(A∧B) não A e B é demonstrada abaixo:

¬(A∧B) = (¬A∨ ¬B) e ¬ (A∨B) = (¬A∧¬B) (conhecidas com leis de De Morgan).

Devido essa equivalência entre ¬(A∧B) e (¬A∨ ¬B) a solução da regra 6 é a ilustrada pois se (¬A∨ ¬B) = V pode-se deduzir ¬A ou ¬B.

O significado da regra R7.

Na montagem da árvore semântica o método a regra R7 diz que devemos fazer a seguinte operação:

Novamente temos a equivalência  ¬(A∨B) = (¬A∧¬B) não A ou B equivalente a não A e não B sendo assim temos que a regra 7 faz com se escreva abaixo da proposição ¬A e na linha abaixo ¬B. Semanticamente temos que ¬ (A∨B) = V então se deduz os valores de ¬A e ¬B.

O significado da regra R8.

Na montagem da árvore semântica o método a regra R8 diz que devemos fazer a seguinte operação:

Mais uma vez termos que usar os nossos conhecimentos de equivalência entre proposições lógicas. Sabe-se que ¬(A→B) não A implica B é equivalente a (A∧¬B) A e não B. Então aplicamos a regra 1 em (A∧¬B) e tem-se na linha abaixo da proposição lógica, a derivação A e abaixo dessa derivação, o ¬B.

O significado da regra R9.

Na montagem da árvore semântica o método a regra R9 diz que devemos fazer a seguinte operação:

A regra 9 diz que uma vez deduzido ¬(A↔B) não A bicondiciona B, pode-se deduzir (¬A∧B) não A e B ou (A∧B) A e não B. Sabe-se que ¬(A↔B) ≡ (¬A∧B)∨(A∨¬B) e a regra 9 faz exatamente isso colocando a proposições (¬A∧B) e (A∨¬B) na linha a abaixo da proposição (¬A∧B) com setas indicando a disjunção. Reforçando, se (¬A∧B) = V se deduz (¬A∧B) ou (A∨¬B).

 

Em geral, a aplicação de uma regra a um tableau é feita considerando qualquer uma das fórmulas. Entretanto, uma boa heurística na construção do tableau é aplicar inicialmente regras que não bifurcam a árvore. Aplique preferencialmente as regras R1, R5, R7 e R8.

A construção de um tableau semântico é definida recursivamente a seguir.

Definição (construção de um tableaux)
Um tableaux semântico, na Lógica Preposicional, é construído como se segue. Seja {A1, …, An} um conjunto de fórmulas.

• A árvore a seguir, com apenas um ramo, é um tableaux associado a {A1, …, An}.

• Seja T um tableaux associado a {A1, …, An}. Se T* é a árvore resultante da aplicação de uma das regras R1, …, R9 à árvore T, então T* é também um tableau associado a {A1, …, An}.

Aplicando as regras do tableaux semântico.

A partir de uma ou mais preposições começamos a aplicar as regras estudadas para se montar o tableaux semântico. Na montagem da árvore, surge logo duas dúvidas:

1. Dada uma fórmula H, qual é a regra adequada para ser aplicada em H?
2. Dada uma fórmula H, como aplicar a regra adequada?

Vamos ver a primeira questão. Dada uma fórmula H consulta-se a lista de regras para identificar qual derivação será utilizada e a sugestão de boa prática para a montagem da árvore que é a de começar por derivações que não bifurquem a árvore, visto que a ordem que se aplica as derivações não altera o resultado.

Para demonstrar o procedimento, a demonstração abaixo será feita de maneira detalhada. Acompanhe atentamente.

Demonstração 01

H1 = (¬¬P)^(Q˅(R→(S↔P)))

Pode-se observar que H1 é do tipo (A∧B), fazendo A=(¬¬P) e B=(Q˅(R→(S↔P))), então aplica-se a regra R1 e escrevemos a árvore da seguinte maneira:

Agora pode-se aplicar  R3 na linha 5 ou R9 na linha 6. Observa-se que não é possível aplicar nenhuma regra na linha 7.

Percebe-se que não é possível aplicar nenhuma regra nas 7 e 8. Sobra apenas a linha 6 para aplicar a regra 9 na linha 6

Repare que o resultado da regra 9 aplicada sobre a linha seis e escrita sob os dois ramos da bifurcação gerada na árvore pela regra 3 aplicada na linha 5. As proposições da linha 9 podem ser derivadas e assim teremos a tabela abaixo.

Finalmente

Definição (tableaux fechado)
Um tableau é fechado quando todos os seus ramos são fechados. Caso contrário, ele é aberto. Exemplos:

• Tableaux semântico fechado.

 

• Tableaux semântico aberto.