Contato

  • Jean Paulo Martins (jeanmartins utfpr edu br)
  • Sala 105, Bloco S (UTFPR - Campus Pato Branco)

Conteúdo

Árvores de refutação

As tabelas verdade fornecem um teste rigoroso e completo para a validade ou invalidade de formas de argumento. De fato, elas são algoritmos que podem ser implementados para verificar tais formas de argumento. Devido a existência desse algoritmo, diz-se que a lógica proposicional é decidível, pois ele nos permite, em princípio, verificar a validade de qualquer forma de argumento. No entanto, as tabelas-verdade são ineficientes e de difícil utilização por seres humanos. As árvores de refutação são fornecem um algoritmo alternativo, mais eficaz, para o mesmo propósito.

Introdução

O primeiro passo de uma árvore de refutação é criar uma lista constituída das premissas e da negação da conclusão. A cada etapa, tentamos desmembrar as fórmulas em subfórmulas menores, até que restem apenas letras sentenciais, ou a negação das mesmas. Se encontrarmos uma atribuição de valores-verdade que valide todas as fórmulas da lista, então encontramos um caso em que as premissas são verdadeiras e a conclusão falsa: portanto a forma de argumento será inválida.

Exemplo: conjunção

Para exemplificar, considere a forma de argumento a seguir:

A lista de fórmulas consiste das premissas e da negação da conclusão:

Como desmembrar qualquer uma dessas fórmulas? Utilizando a derivação de eliminação da conjunção, temos que $p\land q$ pode ser desmembrado em $p,q$.

Indicamos isso inserindo essas duas subfórmulas abaixo da lista e marcando $p\land q$ como já desmembrada.

A próxima fórmula disponível é $\neg\neg\neg p$, a qual por eliminação da negação é equivalente a $\neg p$. Portanto essa segunda é inserida na lista, enquanto a primeira é marcada como já avaliada.

Neste momento, já não há mais nada a ser desmembrado. Caso a lista inicial contenha apenas fórmulas verdadeiras, a lista restante deve conter apenas elementos verdadeiros. No entanto, chegamos a uma contradição $p \land \neg p$. Isso significa que a lista inicial não pode conter apenas fórmulas verdadeiras. Na prática isso significa que a tentativa de redução ao absurdo (inserindo a conclusão negada na lista inicial) nos levou a uma contradição, portanto a forma de argumento original precisa ser valida.

A árvore de refutação tem esse nome porque por meio é possível descobrir uma refutação para a forma de argumento. No caso acima, existe apenas um ramo, no entanto, nos próximos exemplos veremos que diversos ramos podem ser expandidos, dependendo da forma de argumento inicial.

Exemplo: disjunção

Considere a forma de argumento:

Novamente, a lista de fórmulas inicial consiste das premissas e a negação da conclusão.

A única fórmula que ainda pode ser desmembrada neste caso é a disjunção $p\lor q$. Esta fórmula tem a característica de ser verdadeira em ambos os casos $p$ ou $q$ separadamente. Para representar essa separação, criamos dois ramos, um para cada letra.

Observemos que nessa representação temos $p \land \neg p$ e temos $q \land \neg q$, uma contradição em cada um dos ramos. Como todos os ramos abertos levaram a uma contradição, a lista de fórmulas inicial não pode ser verdadeira, implicando que a forma de argumento original é válida. Ou seja, a refutação falhou em todos os ramos que foram abertos.

Exemplo: invalidade

Consideremos agora a seguinte forma de argumento:

Novamente, a lista de fórmulas inicial consiste das premissas e a negação da conclusão. Desta lista inicial, apenas a primeira e a terceira fórmula podem ser desmembradas.

Como a fórmula $p\lor$ é desmembrada em dois ramos, deixaremos ela pra depois, pois assim economizamos trabalho. Sendo assim, desmembraremos $\neg\neg q$ em sua equivalente $q$.

Agora podemos desmembrar a disjunção em dois ramos, cada um contendo apenas um dos disnjuctos.

Neste ponto, todos as fórmulas foram espandidas, no entanto, nenhuma contradição foi encontrada. Isso significa que a árvore de refutação encontrou um contra-exemplo para a forma de argumento original, o qual diz que quando $p$ e $q$ são verdadeiros, a conclusão será falsa. Portanto $p\lor q, p\vdash \neg q$ é uma forma de argumento inválida.

Um ramo é dito fechado se ele termina em contradição, e dito aberto caso contrário.

Regras de expansão

Fórmulas diferentes requerem diferentes regras para serem desmembradas (expandidas). No entanto, em geral, qualquer fórmula pode ser incluída em uma das seguintes categorias:

Negação Negação negada
Conjunção Conjunção negada
Disjunção Disjunção negada
Condicional Condicional negado
Bicondicional Bicondicional negado

Condicional $(\to)$

Se um ramo aberto contém uma fórmula da forma $\phi\to\psi$, bifurca-se em dois ramos contendo $\neg\phi$ e $\psi$. Isso se deve à equivalência $\phi\to\psi \dashv\vdash \neg\phi \lor \psi$.

Bicondicional $(\leftrightarrow)$

Se um ramo aberto contém um bicondicional $\phi\leftrightarrow\psi$, bifurca-se em dois ramos contendo $\phi\land\psi$, $\neg\phi\land\neg\psi$. Isso se deve à equivalência $\phi\leftrightarrow\psi \dashv\vdash (\phi\land\psi) \lor (\neg\phi\land\neg\psi)$

Conjunção negada $(\neg\land)$

Se um ramo aberto contém a negação de uma conjunção $\neg(\phi\land\psi)$, bifurca-se em dois ramos contendo $\neg\phi$ e $\neg\psi$. Isso se deve à equivalência $\neg(\phi\land\psi) \dashv\vdash \neg\phi \lor \neg\psi$ (lei de De Morgan).

Disjunção negada $(\neg\lor)$

Se um ramo aberto contém a negação de uma disjunção $\neg(\phi\lor\psi)$, adiciona-se $\neg\phi$ e $\neg\psi$ ao fim de cada ramo aberto, abaixo. Isso se deve à equivalência $\neg(\phi\lor\psi) \dashv\vdash \neg\phi \land \neg\psi$.

Condicional negado $(\neg\to)$

Se um ramo aberto contém a negação de um condicional $\neg(\phi\to\psi)$, adiciona-se $\phi$ e $\neg\psi$ ao fim de cada ramo aberto abaixo. Isso se deve à equivalência $\neg(\phi\to\psi) \dashv\vdash \phi \land \neg \psi$.

Bicondicional negado $(\neg\leftrightarrow)$

Se um ramo aberto contém a negação de um bicondicional $\neg(\phi\leftrightarrow\psi)$, bifurca-se cada ramo abaixo em $\phi\land\neg\psi$ e $\neg\phi\land\psi$. Cada uma dessas partes é por sua vez expandida em duas linhas: $\phi$ e $\neg\psi$, no primeiro ramo; e $\neg\phi$ e $\psi$, no segundo ramo. Isso se deve à equivalência $\neg(\phi\leftrightarrow\psi) \dashv\vdash (\phi\land\neg\psi) \lor (\neg\phi\land\psi)$

Satisfazibilidade

Assim como as tabelas-verdade, as árvores de refutação também podem ser utilizadas para verificar as características de fórmulas: satizfazibilidade, insatisfatibilidade, tautologia.

Em geral, uma árvore de refutação nos permite encontrar uma atribuição de valores verdade que satisfaça uma determinada fórmula. No caso de formas de argumento, como visto até então, inserimos a negação da conclusão dentre as premissas. Deste modo se uma atribuição for encontrada, teríamos como demostrar a invalidade da forma de argumento.

Se ignorarmos a negação da conclusão (visto que uma fórmula não possui conclusão), esse tipo de árvore de expansão pode ser utilizada para encontrar uma atribuição de valores-verdade que satisfaça determinada fórmula. Sempre que uma atribuição for encontrada, podemos concluir que a fórmula é então satisfazível, caso contrário ela é insatisfatível.

Como exemplo, vamos procurar uma atribuição de valores-verdade para a fórmula:

Como não há conclusão a ser negada, inserimos apenas a fórmula inicial

A única fórmula disponível pode então ser expandida em dois ramos pela regra de eliminação da disjunção.

Aplicando agora a regra da eliminação da conjunção em $p\land\neg q$ e a eliminação do condicional em $p\to q$, chegaremos a tabela

As duas últimas expansões completam a árvore de refutação. Como nenhuma contradição foi encontrada, então encontramos exemplos de atribuição de valores-verdade a $p$ e $q$ tais que a fórmula $(p\to q) \lor (p\land \neg q)$ é verdadeira. Cada ramo ainda aberto representa uma dessas atribuições, ou seja:

  • $p: F$ e $q: V$ no ramo esquerdo, e
  • $p: V$ e $q: F$ no ramo da direita.

O fato de existir uma atribuição que torne verdadeira a fórmula (ausência de contradição na árvore) implica que a fórmula é satisfazível. O caso oposto, de todos os ramos gerarem uma contradição indicaria que a fórmula é insatisfatível.

A negação de uma fórmula insatisfatível é sempre uma tautologia. Portanto, para demonstrarmos se uma fórmula é uma tautologia basta expandirmos a árvore de refutação para a sua negação. Se todos ramos abertos levarem a uma contradição (se fecharem), então a fórmula original é uma tautologia. Como exercício, demonstre que a fórmula a seguir é uma tautologia.

Exercícios em aula

1. Validade de argumentos

Verifique se as formas de argumento a seguir são válidas ou inválidas utilizando árvores de refutação.

2. Satisfazibilidade de fórmulas

Verifique se as fórmulas a seguir são satifazíveis, caso afirmativo, verifique se são tautologias.

Referências

Capítulo 4: Pgs. 185 - 203, Logica - John Nolt (PDF).