DEMONSTRAÇÃO INDIRETA – ÁRVORE DE REFUTAÇÃO

ÁRVORE DE REFUTAÇÃO é um método para verificar a validade de um argumento, análogo à demonstração por absurdo.Para testarmos a validade de um argumento construímos uma lista de fórmulas consistindo de suas premissas
A1, A2 , A3 ,... ,An e a negação da sua conclusão ~B que formam a RAIZ DA ÁRVORE. A árvore continua abaixo com a construção de seus RAMOS por aplicações de regras, que serão especificadas abaixo, e gerando novas linhas na árvore. A árvore termina quando as fórmulas de seus ramos são: variáveis proposicionais, negações de variáveis proposicionais, ou quando encontrarmos em todos os ramos uma fórmula F.

Se encontrarmos em todos os ramos da árvore uma fórmula F, então a nossa tentativa de refutação falhou ou seja, o argumento é válido. Se em algum ramo da árvore não foi possível encontrar uma fórmula F, então refutamos o argumento, isto é, o argumento não é válido.

Exemplo: Construir uma árvore de refutação para mostrar que: p Ù q |¾ ~~ p

- Escrevemos a premissa e a negação da conclusão:
1. p Ù q
2. ~~~p

- Sabemos que p Ù q é verdadeira se, e somente se, p e q são ambas verdadeiras; daí, podemos substituir
p Ù q por p e q gerando as linhas 3. e 4., respectivamente, e MARCANDO (Ð ) a fórmula p Ù q .
(Uma fórmula marcada não poderá mais ser utilizada na construção da árvore!!!)
1. p Ù q Ð
2. ~~~p
3. p
4. q

- Como ~~~p é verdadeira se e somente se ~p é verdadeira, marcamos ~~~p e substituímos por ~p gerando a linha 5. :
1. p Ù q Ð
2. ~~~p Ð
3. p
4. q
5. ~p

- A árvore terminou pois das premissas e da negação da conclusão obtivemos variáveis proposicionais ou negações de variáveis proposicionais. Por outro lado encontramos nas linhas 3. e 5. uma fórmula F, ou seja, nossa tentativa de refutação falhou e portanto o argumento é válido. Isso será expresso escrevendo um X no final da lista, gerando a linha 6 e fechando o único ramo da árvore.
1. p Ù q Ð
2.~~~p Ð
3. p
4. q
5. ~p
6. X

A árvore de refutação está completa. A nossa busca para uma refutação do argumento dado falhou e, portanto, o argumento é válido.

Exemplo:Construir uma árvore de refutação para mostrar que : p Ú q, ~ p |¾q

- Iniciamos a árvore escrevendo a lista de fórmulas as premissas e a negação da conclusão:
1. p Ú q
2. ~p
3. ~q

- Sabemos que p Ú q é verdadeira se, e somente se, p é verdadeira ou q é verdadeira. Para representar esse fato, marcamos p Ú q e ramificamos a árvore, gerando a linha 4 com dois ramos:
1. p Ú q Ð
2. ~p
3. ~q
     /  \
4. p  q

- A árvore terminou pois das premissas e da negação da conclusão obtivemos variáveis proposicionais ou negações de variáveis proposicionais. Por outro lado encontramos uma fórmula F em um ramo, nas linhas 2. e 4. e no outro ramo, nas linhas 3. e 4., ou seja, nossa tentativa de refutação falhou e portanto o argumento é válido. Isso será expresso escrevendo um X no final de cada ramo da lista gerando a linha 5 e fechando os dois ramos da árvore.
1. p Ú q Ð
2. ~p
3. ~q
     /  \
4. p   q
5. X  X

A árvore de refutação está completa. Como a tentativa de refutação falhou nos dois ramos, o argumento dado é válido.

Exemplo:Construir uma árvore de refutação para verificar a validade do argumento:
p Ú q, p |¾ ~ q
1. p Ú q
2. p
3. ~~q Ð

- Temos que ~~q é equivalente a q; daí, marcamos ~~q e escrevemos q gerando a linha 4. :
1. p Ú q
2. p
3. ~~q Ð
4. q

- Como no exemplo anterior, marcamos p Ú q e ramificamos a árvore gerando a linha 5. com dois ramos:
1. p Ú q Ð
2. p
3. ~~q Ð
4.   q
     /   \
5. p   q

- A árvore terminou e nos dois ramos não há contradições, ou seja, uma fórmula F. Neste caso os ramos não serão fechados e o argumento não é válido.

As regras para a construção de uma árvore de refutação estão relacionadas com as tabelas verdade já conhecidas. Ao aplicar uma regra em uma fórmula da árvore, temos a observar que :

- a fórmula será marcada ( Ð ) para evitar aplicações repetidas de uma regra em uma mesma fórmula.
- a aplicação de uma regra deve gerar : uma ou duas linhas, um ramo ou dois ramos conforme a regra, e será aplicada em todos os ramos abertos (não fechados com X) aos quais a fórmula pertence.

Temos as seguintes regras :

1. REGRA DA DUPLA NEGAÇÃO (~~) : Uma fórmula do tipo ~~A gera uma linha e escrevemos A na linha. Procedemos assim em todos os ramos abertos aos quais a fórmula ~~A pertence pois, ~~ A é verdadeira se e somente se A é verdadeira.

2. REGRA DA CONJUNÇÃO (Ù): Uma fórmula do tipo A Ù B gera duas linhas e escrevemos, em cada linha, as fórmulas A e B. Procedemos assim em todos os ramos abertos aos quais a fórmula A Ù B pertence pois, A Ù B assume valor V se, e somente, as fórmulas A e B são verdadeiras.
1. A Ù B Ð
2. A
3. B

3. REGRA DA DISJUNÇÃO (Ú): Uma fórmula do tipo A Ú B gera uma linha e dois ramos e escrevemos, na linha e, em cada ramo, as fórmulas A e B respectivamente. Procedemos assim em todos os ramos abertos aos quais a fórmula A Ú B pertence pois, A Ú B assume valor V se, e somente, a fórmula A é verdadeira ou a fórmula B é verdadeira.
1.A Ú B Ð
      /   \
2. A   B

4. REGRA DA IMPLICAÇÃO (®): Uma fórmula do tipo A ® B gera uma linha e dois ramos e escrevemos, na linha e, em cada ramo, as fórmulas ~ A e B respectivamente. Procedemos assim em todos os ramos abertos aos quais a fórmula
A ® B pertence pois, A ® B assume valor V se, e somente, a fórmula ~ A é verdadeira ou a fórmula B é verdadeira.
1.   A ® B Ð
          /   \
2. ~ A   B

5. REGRA DA BI- IMPLICAÇÃO («) : Uma fórmula do tipo A«B gera duas linhas e dois ramos e escrevemos nas linhas as fórmulas A e B em um ramo e as fórmulas ~A e~B no outro ramo. Procedemos assim em todos os ramos abertos aos quais a fórmula A«B pertence pois,  A«B assume valor V se, e somente, a fórmula
(A Ù B) é verdadeira ou a fórmula (~ A Ù~ B) é verdadeira.
1.A«B Ð
      /  \
2.A   ~ A
3.B   ~ B

6. REGRA DA NEGAÇÃO DA CONJUNÇÃO (~Ù ): Uma fórmula do tipo
~(A Ù B) gera uma linha e dois ramos e escrevemos, na linha e, em cada ramo, as fórmulas ~A e ~B respectivamente. Procedemos assim em todos os ramos abertos aos quais a fórmula ~(A Ù B) pertence pois, ~(A Ù B) assume valor V se, e somente, a fórmula ~A é verdadeira ou a fórmula ~B é verdadeira.
1.~ (A Ù B)Ð
         /    \
2.  ~A ~B

7. REGRA DA NEGAÇÃO DA DISJUNÇÃO (~Ú ) : Uma fórmula do tipo
~(A Ú B) gera duas linhas e escrevemos, em cada linha, as fórmulas ~A e ~B. Procedemos assim em todos os ramos abertos aos quais a fórmula ~(A Ú B) pertence pois, ~(A Ú B) assume valor V se, e somente, as fórmulas ~Ae~B são verdadeiras.
1.~ (A Ú B) Ð
2. ~ A
3. ~ B

8. REGRA DA NEGAÇÃO DA IMPLICAÇÃO (~®) : Uma fórmula do tipo
~(A ® B) gera duas linhas e escrevemos, em cada linha, as fórmulas A e ~B. Procedemos assim em todos os ramos abertos aos quais a fórmula ~(A® B) pertence pois, ~(A ® B) assume valor V se, e somente, as fórmulas Ae ~B são verdadeiras.
1. ~ (A ® B) Ð
2.   A
3. ~B

9. REGRA DA NEGAÇÃO DA BI- IMPLICAÇÃO (~«): Uma fórmula do tipo
~(A«B) gera duas linhas e dois ramos e escrevemos nas linhas as fórmulas ~A e B em um ramo e as fórmulas A e ~B no outro ramo. Procedemos assim em todos os ramos abertos aos quais a fórmula ~(A«B) pertence pois, ~(A«B) assume valor V se, e somente, a fórmula (~A Ù B) é verdadeira ou a fórmula (A Ù~B) é verdadeira.
1.~(A«B) Ð
         /    \
2.  ~A    A
3.    B   ~B

10. RAMO FECHADO : Um ramo será fechado se nele existem uma fórmula A e sua negação ~A e escrevemos X no final do ramo.
1. ~A
2.   A
3.   X

1.                 p ® r Ú s      ÐPremissa
2.                 r Ù s ® q      ÐPremissa
3.               ~(p ® q)         ÐNegação da Conclusão
4.                         p              3.(~® )
5.                     ~q              3.(~® )
                     /              \
6.           ~p              (r Ú s) Ð1.(® )
7.           X(6.4)      /              \
8.                        r                  s        6. (Ú )
                       /         \        /            \
9.             ~(rÙ s)Р  q  ~(rÙ s) Р q 2.(® )
                     /    \         \        /    \         \
10.            ~r   ~s      X    ~r  ~s     X  (~Ù )
11.              X      ?  (9.5)     X    ?    (9.5)
                 (10.8)                (10.8)

Temos neste caso dois ramos que não fecharam e, portanto, o argumento não é válido.

2.) Construir uma árvore de refutação para verificar se a fórmula
(p ® q) Ú (p Ù~q) é uma tautologia:

1.       ~((p ® q) Ú (p Ù~ q)) ÐNegação da Conclusão
2.             ~(p ® q) Р          1. (~Ú )
3.            ~(p Ù~ q) Р         1. (~Ú )
4.                   p                      2. (~®)
5.                 ~q                      2. (~®)
                    /    \
6.             ~p   ~~q               3. (~Ù )
7.             X       X
              (6.4)     (6.5)
Todos os ramos estão fechados; assim a fórmula é válida, ou seja, é uma tautologia.