Lógica Proposicional - Árvore de Composição e Decomposição de uma Fórmula

Vimos a definição e aprendemos a criar uma fórmula no artigo Lógica Proposicional - Fórmulas Atômicas e Complexas. Com isso, podemos esquematizá-la no que chamamos árvore de formação de fórmulas.

Índice

O que é uma árvore?
Árvore binária de uma sentença
O que você aprendeu

Inicialmente, observemos a primeira linha (de cima pra baixo) da imagem "Árvore de composição e decomposição de uma fórmula". Partimos das sentenças $$\text{A, B, C}$$ e $$\text{D}$$, que constituem a primeira regra da definição de fórmula.

Observemos a segunda linha e aplicando a segunda regra da definição de fórmula, foi obtido as fórmulas: $$(\neg$$$$\text{A})$$, $$(\text{A}$$ $$\rightarrow$$ $$\text{B})$$, $$(\text{B}$$ $$\wedge$$ $$\text{C})$$, $$(\text{C}$$ $$\vee$$ $$\text{D})$$ e $$(\text{D}$$ $$\leftrightarrow$$ $$\text{D})$$.

A terceira linha recebeu a aplicação da segunda regra da definição, assim como a segunda, e obtemos novas fórmulas: $$(\neg$$$$(\neg$$$$\text{A}))$$, $$((\text{A}$$ $$\wedge$$ $$(\text{B}$$ $$\wedge$$ $$\text{C}))$$, $$((\text{C}$$ $$\vee$$ $$\text{D})$$ $$\rightarrow$$ $$(\text{B}$$ $$\wedge$$ $$\text{C}))$$ e $$(\neg$$$$(\text{D}$$ $$\leftrightarrow$$ $$\text{D}))$$.

Observação importante: é muito importante aplicar corretamente a regra de formação de fórmulas.

A verificação cuidadosa da formação de fórmula, nos permite analisar, imediatamente, como uma fórmula foi obtida.

Vamos exibir um processo gráfico para determinar todas as subfórmulas de uma fórmula. Tal processo faz uso de uma estrutura, muito utilizada na área da computação, chamada árvore.

Subfórmulas: todas as fórmulas que compõe a fórmula em questão.

O que é uma árvore?

Estaremos mais interessados em um certo tipo de árvore chamada árvore binária, mas começaremos analisando árvores em geral antes de entrarmos nela.

Uma árvore consiste em nós (ou vértices) conectados por arestas (segmento de reta que "liga" os nós).

Árvores têm sindo estudadas extensivamente como entidades matemáticas abstratas, portando, há uma grande quantidade de conhecimento teórico sobre elas. Uma árvore é, na verdade, uma instância de uma categoria mais geral chamada grafo, mas não precisaremos nos preocupar com isso.

Grafo

A seguir, apresentamos graficamente os componentes de uma árvore binária qualquer, observamos que tal descrição, não tem nenhum caráter formal, é apenas para nos familiarizarmos com os elementos dessa estrutura.

Árvore Binária

Acima está a representação gráfica de uma árvore binária genérica. Os vértices (ou nós) são de três espécies, o nó a partir da qual toda árvore é gerada é chamado de raiz, o nó terminal chamado de folha e os nós intermediários chamados de nó interior. Toda árvore tem um começo (raiz), meio (interior) e fim (terminal).

Aristóteles define que começo é aquilo que necessariamente não é antecedido por nada, mas que pede ou produz, por natureza, um desdobramento; fim, ao contrário, é aquilo que, por natureza, é antecedido por alguma coisa (da qual decorre), mas que necessariamente não é seguido por mais nada; meio, por sua vez, é aquilo que necessariamente segue e é seguido de outras coisas.

Chamamos de árvore binária, pois cada nó pode ter zero, um ou no máximo dois filhos e podemos também classificar os nós como sucessores, aqueles que vem abaixo, e ancestrais, aqueles que vem acima.

Árvore binária de uma sentença

Utilizaremos árvore binária do seguinte modo:

Dada uma fórmula qualquer $$\text{P}$$ esta será a raiz da árvore de subfórmulas de $$\text{P}$$.
Se $$\text{P}$$ é uma fórmula do tipo não, então ela é composta por uma fórmula $$\text{A}$$, de tal modo que $$\text{P}$$ $$\equiv$$ $$(\neg$$$$\text{A})$$. Logo, teremos:

Fórmula do tipo negação
Se $$\text{P}$$ é uma fórmula do tipo conjunção, então ela é composta por duas fórmulas $$\text{A}$$ e $$\text{B}$$, de tal modo que $$\text{P}$$ $$\equiv$$ $$(\text{A}$$ $$\wedge$$ $$\text{B})$$. Logo, teremos:

Fórmula do tipo conjunção
Se $$\text{P}$$ é uma fórmula do tipo disjunção inclusiva, então ela é composta por duas fórmulas $$\text{A}$$ e $$\text{B}$$, de tal modo que $$\text{P}$$ $$\equiv$$ $$(\text{A}$$ $$\vee$$ $$\text{B})$$. Logo, teremos:

Fórmula do tipo disjunção inclusiva
Se $$\text{P}$$ é uma fórmula do tipo disjunção exclusiva, então ela é composta por duas fórmulas $$\text{A}$$ e $$\text{B}$$, de tal modo que $$\text{P}$$ $$\equiv$$ $$(\text{A}$$ $$\veebar$$ $$\text{B})$$. Logo, teremos:

Fórmula do tipo disjunção exclusiva
Se $$\text{P}$$ é uma fórmula do tipo implicação, então ela é composta por duas fórmulas $$\text{A}$$ e $$\text{B}$$, de tal modo que $$\text{P}$$ $$\equiv$$ $$(\text{A}$$ $$\rightarrow$$ $$\text{B})$$. Logo, teremos

Fórmula do tipo implicação
Se $$\text{P}$$ é uma fórmula do tipo bi-implicação, então ela é composta por duas fórmulas $$\text{A}$$ e $$\text{B}$$, de tal modo que $$\text{P}$$ $$\equiv$$ $$(\text{A}$$ $$\leftrightarrow$$ $$\text{B})$$. Logo, teremos:

Fórmula do tipo bi-implicação

Cada nó representa uma fórmula, em particular, cada nó gera uma sub-árvore. Isto é, cada nó pode ser considerado uma raiz de uma árvore menor que tem como nós os sucessores do respectivo nó raiz.

A construção de uma árvore de subfórmulas, a partir de uma fórmula dada, termina quando todas as folhas contiverem somente letras proposicionais.

É muito importante ter em mente que uma fórmula é definida passo a passo e é única a sua construção. Assim, por exemplo, podemos dizer qual conectivo foi aplicado primeiro, o segundo, etc., até chegarmos ao último. Desse modo, é possível decompor uma fórmula exibindo todas as suas subfórmulas que a compõe.

Este tema é de suma importância para a continuidade do aprendizado, convém familiarizarmos mais de perto.

Analisemos a fórmula:

$$[\text{A}$$ $$\rightarrow$$$$(\text{B}$$ $$\vee$$ $$\text{C})]$$

Para descobrir o último conectivo aplicado à fórmula, basta obedecer a regra da aritmética básica. Na aritmética o operador mais externo será o último a sofrer uma aplicação, no nosso caso o conectivo mais externo é o $$\rightarrow$$, mas ao contrário da aritmética, onde o operado mais interno é o primeiro a sofrer a aplicação, na árvore de composição e decomposição de uma fórmula proposicional é o operador mais externo que sofrerá a aplicação inicial.

Observação importante: sentenças, fórmulas ou proposições representam a mesma coisa. Alguns livros usam sentenças, outros fórmulas e outros proposições, mas no nosso caso usaremos todos para que o leitor vá se familiarizando com as variações.

Após descobrirmos o conectivo mais externo, devemos ver se ele é um conectivo binário ou unário. Entre os seis conectivos da lógica, o único unário é o $$\neg$$, porque os demais ligam duas sentenças, enquanto o $$\neg$$ apenas muda o valor verdade de uma. Como o último conectivo da fórmula em questão é binário, então devermos traçar duas arestas. Logo, teremos:

Decomposição de uma fórmula do tipo implicação

Repare na imagem acima que foi feito duas arrestas e que ambas partem do último conectivo, implicação. É de suma importância que as arestas partam de seus respectivos conectivos para facilitar a compreensão da árvore, já que o objeto da árvore de composição e decomposição de uma fórmula é facilitar a compreensão da formula.

Após traçarmos as arestas devemos "descer" as sentenças restantes, no caso serão descidos as preposições $$\text{A}$$ e $$(\text{B}$$ $$\vee$$ $$\text{C})$$, o par de símbolos auxilares, colchetes, mais externos não descem e nem o conectivo origem, implicação, das arestas. Logo, teremos:

Decomposição de uma fórmula do tipo implicação

Repare que como a "quebra" ocorreu na implicação, apenas as duas fórmulas ligadas por ela desceram e com isso foi resultado duas sentenças para se trabalhar. Em casos assim, começamos, sempre, da esquerda para a direita.

A nossa primeira fórmula é $$\text{A}$$, mas reparem que ela é atômica (desprovida de quaisquer conectivos) e neste caso não se tem o que fazer.

A segunda sentença é $$(\text{B}$$ $$\vee$$ $$\text{C})$$ e ao contrário da primeira, ela é possuidora do conectivo $$\vee$$ e por isso ela sofrerá uma aplicação. Logo, teremos:

Decomposição de uma fórmula do tipo implicação

Repare que a sentença $$(\text{B}$$ $$\vee$$ $$\text{C})$$ sofreu a mesma aplicação que a $$[\text{A}$$ $$\rightarrow$$ $$(\text{B}$$ $$\vee$$ $$\text{A})]$$ e que a aresta que tem origem no conectivo $$\rightarrow$$ está "conectada" no conectivo $$\vee$$, isso ocorre porque sempre devemos conectar as arestas no próximo conectivo que sofrerá a "quebra". Logo, teremos:

Decomposição de uma fórmula do tipo implicação

Após a "quebra" do conectivo $$\vee$$ foram obtidas as sentenças $$\text{A}$$ e $$\text{B}$$ e repare que apenas eles desceram. Outra coisa que deve ser reparada é que as arestas partem do $$\vee$$ e vão para as metas-variáveis e como a árvore possui apenas letras, encerramos a decomposição.

Além de facilitar a compreensão de fórmulas grandes, a árvore nos retorna o tipo da mesma. O tipo da fórmula é determinado pelo conectivo mais externo e como na árvore é ele que sofre a primeira aplicação, então podemos concluir que a fórmula trabalhada é do tipo implicação.

Se virarmos a árvore de cabeça para baixo, iremos adquirir a árvore de composição. Vejamos:

Composição de uma fórmula do tipo implicação

Vejamos mais um exemplo:

$$\{\neg$$$$[[(\neg$$$$\text{B})$$ $$\wedge$$ $$(\neg$$$$(\neg$$$$\text{A}))]$$ $$\leftrightarrow$$ $$[\neg$$$$(\neg$$$$(\text{B}$$ $$\vee$$ $$\text{C}$$$$))]]\}$$

Como saber a sequência em que foram aplicadas os conectivos? Sabemos que um parênteses, colchetes e chaves à esquerda possui sempre um par à sua direita correspondente. Podemos identificar isso de vários modos, porém há alguns pares óbvios. Por exemplo, o par de chaves mais externo da fórmula:

Composição de uma fórmula do tipo negação

Outros fáceis são os da negação de atômicas:

Composição de uma fórmula do tipo negação

E assim por diante:

Composição de uma fórmula do tipo negação

Vemos que o $$\neg$$ foi o último conectivo aplicado a formula, porque ele é o mais externo entre todos. Por conseguinte, o tipo desta fórmula é negação. Com base no último conectivo iniciemos a nossa decomposição.