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

Lógica Proposicional - Árvore de Composição e Decomposição de uma Fórmula
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
  1. O que é uma árvore?
  2. Árvore binária de uma sentença
  3. 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.
Lógica Proposicional - Árvore de composição e decomposição de uma fórmula
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.
Lógica Proposicional - Árvore de composição e decomposição de uma fórmula
Á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:
  1. Dada uma fórmula qualquer $$\text{P}$$ esta será a raiz da árvore de subfórmulas de $$\text{P}$$.
  2. 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:
    Lógica Proposicional - Árvore de composição e decomposição de uma fórmula
    Fórmula do tipo negação
  3. 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:
    Lógica Proposicional - Árvore de composição e decomposição de uma fórmula
    Fórmula do tipo conjunção
  4. 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:
    Lógica Proposicional - Árvore de composição e decomposição de uma fórmula
    Fórmula do tipo disjunção inclusiva
  5. 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:
    Lógica Proposicional - Árvore de composição e decomposição de uma fórmula
    Fórmula do tipo disjunção exclusiva
  6. 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
    Lógica Proposicional - Árvore de composição e decomposição de uma fórmula
    Fórmula do tipo implicação
  7. 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:
    Lógica Proposicional - Árvore de composição e decomposição de uma fórmula
    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:
  1. $$[\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:
Lógica Proposicional - Árvore de composição e decomposição de uma fórmula
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:
Lógica Proposicional - Árvore de composição e decomposição de uma fórmula
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:
Lógica Proposicional - Árvore de composição e decomposição de uma fórmula
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:
Lógica Proposicional - Árvore de composição e decomposição de uma fórmula
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:
Lógica Proposicional - Árvore de composição e decomposição de uma fórmula
Composição de uma fórmula do tipo implicação
Vejamos mais um exemplo:
  1. $$\{\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:
Lógica Proposicional - Árvore de composição e decomposição de uma fórmula
Composição de uma fórmula do tipo negação
Outros fáceis são os da negação de atômicas:
Lógica Proposicional - Árvore de composição e decomposição de uma fórmula
Composição de uma fórmula do tipo negação
E assim por diante:
Lógica Proposicional - Árvore de composição e decomposição de uma fórmula
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.
Lógica Proposicional - Árvore de composição e decomposição de uma fórmula
Decomposição de uma fórmula do tipo negação
Como o último conectivo é unário, $$\neg$$, fazemos uma aresta na vertical com origem no $$\neg$$ e destino no próximo conectivo que sofrerá a quebra, no caso o $$\leftrightarrow$$. Não podemos esquecer de descer as demais sentenças com os seus respectivos conectivo. Vejamos:
Lógica Proposicional - Árvore de composição e decomposição de uma fórmula
Decomposição de uma fórmula do tipo negação
A aplicação resultou na fórmula $$[[(\neg$$$$\text{B})$$ $$\wedge$$ $$(\neg$$$$(\neg$$$$\text{A}$$$$))]$$ $$\leftrightarrow$$ $$[\neg$$$$(\neg$$$$(\text{B}$$ $$\vee$$ $$\text{C}$$$$))]]$$ e como a aresta está "conectada" no conectivo $$\leftrightarrow$$, aplicaremos a "quebra" nele. Como ele é um conectivo binário, teremos duas arestas Vejamos:
Lógica Proposicional - Árvore de composição e decomposição de uma fórmula
Decomposição de uma fórmula do tipo negação
Antes de descer as demais sentenças, devemos ver qual o conectivo mais externo em cada uma.

Na sentença $$[(\neg$$$$\text{B})$$ $$\wedge$$ $$(\neg$$$$(\neg$$$$\text{A}$$$$))]$$ o conectivo mais externo é $$\wedge$$, enquanto que na sentença $$[\neg$$$$(\neg$$$$(\text{B}$$ $$\vee$$ $$\text{C}$$$$))]$$ o conectivo mais externo é $$\neg$$. Com isso as arestas estão ligadas a eles. Vejamos:
Lógica Proposicional - Árvore de composição e decomposição de uma fórmula
Decomposição de uma fórmula do tipo negação
Observando a imagem acima, vermos que os próximos conectivos a sofrer a quebra são $$\wedge$$ e $$\neg$$. Vejamos:
Lógica Proposicional - Árvore de composição e decomposição de uma fórmula
Decomposição de uma fórmula do tipo negação
Aplicando a mesma lógica, obteremos a seguinte árvore:
Lógica Proposicional - Árvore de composição e decomposição de uma fórmula
Decomposição de uma fórmula do tipo negação

Observação importante: não é necessário que a aresta que tem origem no conectivo $$\neg$$ esteja na vertical, mas é necessário que ela tenha final no próximo conectivo que sofrerá a quebra.

É de suma importância que o leitor tenha compreendido a formação de uma árvore de composição e decomposição de uma fórmula, porque ela será frequentemente usada. Caso tenha dúvida, faça um breve comentário que responderei assim que possível.

E para finalizar, vejamos um exemplo que envolva conjuntos:

Seja P(A) = {{1}, {2}, {3}, {1,2}, {1 ,3}, {2, 3}, {1, 2, 3}, {}}. Represente em um diagrama:
Lógica Proposicional - Árvore de composição e decomposição de uma fórmula
Decomposição de um conjunto
Caso o leitor tenha alguma dúvida sobre teoria dos conjuntos, clique aqui.

O que você aprendeu

Este artigo serviu para demonstrar a criação de uma árvore de composição e decomposição de uma fórmula com três exemplos, mostrou ela sendo aplicada na teoria dos conjuntos e explico o que é uma árvore. Especificamente, você aprendeu:
  • O que é uma árvore.
  • O que é uma árvore binária.
  • Criação de uma árvore binária de composição e decomposição de uma fórmula.
  • Aplicação em teoria dos conjuntos.

Continua em

Continuação de


Referência Bibliográfica
ABE, J. M; SCALZITTI, A; FILHO, J. I. S. Introdução à Lógica para a Ciência da Computação. 2. ed. São Paulo: Arte & Ciência, 2002. 247 p.

GERSTING, A. L. Fundamentos Matemáticos para a Ciência da Computação: um tratamento moderno de matemática discreta. 5. ed. Rio de Janeiro: LTC, 2012. 597 p.

LAFORE, R. Estruturas de dados & algoritmos em Java. 2. ed. Rio de Janeiro: Ciência Moderna, 2004. 702 p.


Para citar esse artigo:

Comentários

  1. Faltou o par não-ordenado {1,3} em P(A).

    ResponderExcluir
    Respostas
    1. Olá Victor Lennon, obrigado pela observação. Seu feedback é muito importante.

      Excluir
  2. Ao autor; realmente um site sensacional, ótimas explicações!

    ResponderExcluir
    Respostas
    1. Olá, muito obrigado pela comentário :) seja bem-vindo!

      Excluir

Postar um comentário