Lógica Proposicional - Construção de Tabela-Verdade de uma Fórmula sem Árvore de Decomposição

Cubo mágico
Cubo de Rubik
(Foto: Sarah Williams / FreeImages) CC BY-NC

No artigo anterior em Lógica Proposicional - Construção de Tabela-Verdade de uma Fórmula com Árvore de Decomposição, aprendemos a construir uma tabela-verdade de uma fórmula dada. É importante entender de várias maneiras este conceito e por isso estarei apresentando outra forma de construir uma tabela-verdade.

Neste artigo será apresentado uma técnica de construção de tabela-verdade e em que não é necessário a construção de uma árvore de composição e decomposição. Ela é conhecida como exemplificação (FILHO, 2002).

Construção da tabela-verdade sem árvore

Construção da tabela-verdade:

Passos
Instruções
01
Trace colunas para cada fórmula atômica e conectivo.
02
Trace $$2 ^ n + 1$$ linhas, sendo $$n$$ o número de atômica.

Preenchimento da tabela-verdade:

Passos
Instruções
01
Olhemos inicialmente todas as colunas e iniciemos pela coluna que possui a atômica com maior precedência, com base na ordem alfabética.
02
Na coluna possuidora da atômica com maior precedência, preenchemos a primeira metade com V e a outra metade com F.
03
Na coluna possuidora da segunda atômica com maior precedência, para cada metade de V da coluna com maior precedência, preenchemos a primeira metade com V e a outra metade com F. Na outra metade F, ainda da coluna com maior precedência, preenchemos a primeira metade com V e a outra metade com F.
04
Nas demais colunas atômicas, repete-se o processo anterior, para cada bloco de V e de F, até chegar à última coluna que deve apresentar-se assim: V, F, V, F, etc..
05
Após a atribuição, preencha a última linha de cada coluna atômica com o número 1.

Preenchimento das demais coluna:

Passos
Instruções
01
A tabela já está pronta para que a primeira coluna do conectivo mais interno da fórmula seja preenchida, olhando as atômicas que o compõe.
02
Caso a fórmula possua dois ou mais conectivos, dentro do mesmo par de símbolo auxiliar, obedeça a precedência.
03
Após o preenchimento da coluna, preencha a última linha da coluna do conectivo atual com um número sucessor ao último número colocado na tabela.
04
Repita os passos até que se chegue ao conectivo mais externo da fórmula.
05
Como a última coluna representa o último conectivo, a tabela-verdade da fórmula está feita.

Observação importante: caso o leitor não se lembre da ordem de precedência e dos símbolos auxiliares, veja o artigo Lógica Proposicional - Fórmulas Atômicas e Complexas.

Tomaremos os mesmos exemplos apresentados anteriormente.

Dada a fórmula $$[\text{A}$$ $$\rightarrow$$ $$(\text{B}$$ $$\vee$$ $$\text{C})]$$. Construa a tabela-verdade.

Primeiro iremos traçar colunas para cada fórmula atômica e conectivo. Logo, teremos:

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

Observação importante: devemos manter os símbolos auxiliares. Caso o leitor não se lembre quais os símbolos auxiliares da lógica proposicional, veja o artigo Lógica Proposicional - Fórmulas Atômicas e Complexas.

Após o primeiro passo, devemos traçar nove linhas, porque possuímos três fórmulas atômicas e a quantidade de linhas de uma tabela é definida pela fórmula $$2 ^ n + 1$$, onde $$n$$ é a quantidade de fórmulas atômicas e $$1$$ é uma linha auxiliar. Logo, teremos:

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

O primeiro passo e no segundo, do preenchimento da tabela, nos instrui a preencher as colunas da meta-variável, de maior precedência, com os possíveis valor verdade que a mesma possa possuir. Logo, teremos:

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

Observação importante: a ordem de precedência das atômicas é a mesma da alfabética.

Meta-variável: símbolos que estão fora da linguagem proposicional.

Como a primeira coluna possui a atômica $$\text{A}$$ e oito linhas, com exceção do cabeçalho e da última, as quatro primeiras são V e as demais são F.

O terceiro passo de preenchimento nos diz que na coluna com a segunda atômica de maior precedência, para cada metade de V da coluna com maior precedência, preenchemos a primeira metade com V e a outra metade com F. Vejamos:

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

Observe que a segunda coluna "pega" a metade composta por V da primeira coluna e preenche a metade da metade com V e a outra metade com F. O procedimento é repetido para a metade composta por F.

Segundo o quarto passo, devemos repetir o processo do terceiro. Logo, teremos:

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

Após o preenchimento das colunas atômicas, devemos preencher a última linha das mesmas com o número 1. Vejamos:

$$[\text{A}$$
$$\rightarrow$$
$$(\text{B}$$
$$\vee$$
$$\text{C})]$$
V
-
V
-
V
V
-
V
-
F
V
-
F
-
V
V
-
F
-
F
F
-
V
-
V
F
-
V
-
F
F
-
F
-
V
F
-
F
-
F
1
-
1
-
1

Após o preenchimento das colunas inicias, podemos iniciar o preenchimento das demais, mas sempre obedecendo a ordem de precedência.

Segundo o primeiro e o segundo passo, devemos preencher a coluna com o conectivo mais interno da fórmula e ao finalizar a mesma, preencheremos ela com o número 2, porque estaremos modificando a segunda coluna. Logo, teremos:

$$[\text{A}$$
$$\rightarrow$$
$$(\text{B}$$
$$\vee$$
$$\text{C})]$$
V
-
V
V
V
V
-
V
V
F
V
-
F
V
V
V
-
F
F
F
F
-
V
V
V
F
-
V
V
F
F
-
F
V
V
F
-
F
F
F
1
-
1
2
1

Repare que a coluna do conectivo $$\vee$$ possui o número 2 e foi aplicada primeiro que a coluna do conectivo $$\rightarrow$$, porque ela está dentro dos símbolos $$[]$$ e $$()$$, enquanto que o conectivo da implicação ($$\rightarrow$$) se encontra dentro, apenas, do par $$[]$$.

Repetimos a mesma lógica para a coluna pertence ao conectivo da implicação ($$\rightarrow$$). Teremos:

$$[\text{A}$$
$$\rightarrow$$
$$(\text{B}$$
$$\vee$$
$$\text{C})]$$
V
V
V
V
V
V
V
V
V
F
V
V
F
V
V
V
F
F
F
F
F
V
V
V
V
F
V
V
V
F
F
V
F
V
V
F
V
F
F
F
1
3
1
2
1

Observe que a coluna de número 3 foi originada com a implicação dos valores verdade da coluna de número 1 e da coluna de número 2.

E com isso concluímos a construção da tabela-verdade da fórmula $$[\text{A}$$ $$\rightarrow$$ $$(\text{B}$$ $$\vee$$ $$\text{C})]$$, porque o quinto passo nos diz: "como na última coluna deve figurar a fórmula complexa, a tabela-verdade da fórmula está feita".

Para determinar o tipo de uma fórmula, sem a aplicação de uma árvore de decomposição, devemos observar a coluna  com o maior número. No exemplo acima, a coluna possuidora do maior número é a do conectivo $$\rightarrow$$. Logo, a sentença usada no exemplo é do tipo implicação.

Dada a fórmula $$\{\neg$$$$[[(\neg$$$$\text{B})$$ $$\wedge$$ $$(\neg$$$$(\neg$$$$\text{A}))]$$ $$\leftrightarrow$$ $$[\neg$$$$(\neg$$$$(\text{B}$$ $$\vee$$ $$\text{C})$$$$)]]\}$$. Construa a tabela-verdade.

Para construir a tabela-verdade do segundo exemplo, seria necessário uma longa explicação escrita e para não deixar o leitor cansado, estive gravando uma explicação e construção da tabela-verdade. Veja o vídeo logo abaixo:


O que você aprendeu

Este artigo teve o objetivo de demostrar a construção de uma tabela-verdade de fórmula sem o uso de uma árvore binária de decomposição, foram usados dois exemplos e uma vídeo aula para facilitar o aprendizado. Especificamente, você aprendeu:
  • Criação de uma tabela-verdade de uma fórmula dada.
  • Técnica de exemplificação.

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.

FILHO, E. A. Iniciação à Lógica Matemática. 1. ed. São Paulo: Nobel, 2002. 204 p.


Para citar esse artigo:

-

Comentários

Postar um comentário