Lógica Proposicional - Fórmulas Atômicas e Complexas

Lógica Proposicional - Fórmulas Atômicas e Complexas

No artigo Lógica Proposicional - Conectivo e Tabela-Verdade foi apresentando os seis conectivos e as seis tabelas-verdade da lógica proposicional, e foi citado que a Teoria dos Conjuntos é a linguagem universal da lógica.

Índice

1. Criação de fórmulas
2. O que você aprendeu

Neste artigo apresentaremos as fórmulas atômicas e "complexas" a partir de outras sentenças mais "simples".

Como observamos no artigo anterior, Lógica Proposicional - Conectivo e Tabela-Verdade, através dos conectivos lógicos $$\neg$$, $$\wedge$$, $$\vee$$, $$\veebar$$, $$\rightarrow$$ e $$\leftrightarrow$$, podemos construir sentenças mais "complexas" a partir de outras sentenças mais "simples". Entretanto este procedimento possui uma regra de formação de sentenças.

Partimos de certas sentenças denominadas fórmulas atômicas.

As sentenças, ou fórmulas, em geral são obtidas pela seguinte definição indutiva generalizada:

1. Todas as fórmulas atômicas são fórmulas.
2. Se $$\text{A}$$ e $$\text{B}$$ são fórmulas, então $$(\neg$$$$\text{A})$$, $$(\text{A}$$ $$\wedge$$ $$\text{B})$$, $$(\text{A}$$ $$\vee$$ $$\text{B})$$, $$(\text{A}$$ $$\veebar$$ $$\text{B})$$, $$(\text{A}$$ $$\rightarrow$$ $$\text{B})$$ e $$(\text{A}$$ $$\leftrightarrow$$ $$\text{B})$$ são fórmulas.
3. Uma dada expressão é uma fórmula se e somente se foi obtida pela aplicação da regra 1 ou 2.

Observação importante: os símbolos $$\text{A}$$ e $$\text{B}$$ introduzidos na definição se tratam de variáveis que denotam sentenças quaisquer da linguagem proposicional. Devemos estar atento para o fato de que tais símbolos não são propriamente símbolos da linguagem, mas sim símbolos que estão "fora" da linguagem proposicional. Tais variáveis denominam-se metas-variáveis e podem ser representadas por quaisquer letras maiúsculas do alfabeto.

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

A regra 3 é também conhecida como cláusula maximal e, juntamente com as demais, permite-nos reconhecer quando uma dada expressão se trata de uma fórmula ou não.

Maximal: contém os elementos do conjunto, deste que nenhum elemento do conjunto seja superconjunto próprio.

Segue alguns exemplos de fórmula:

1. $$(\text{A}$$$$\neg$$$$\vee)$$
2. $$\vee$$$$\wedge$$$$\text{D}($$$$\neg)$$
3. $$\text{P}$$
4. $$(\neg$$$$\text{C})$$
5. $$(\text{A}$$ $$\wedge$$ $$\text{B})$$
6. $$(\text{B}$$ $$\vee$$ $$\text{A})$$
7. $$(\text{C}$$ $$\rightarrow$$ $$\text{D})$$
8. $$(\text{A}$$ $$\leftrightarrow$$ $$\text{D})$$
9. $$((\neg($$$$\text{A}$$ $$\leftrightarrow$$ $$\text{B})$$ $$\rightarrow$$ $$\text{A})$$
10. $$((\text{A}$$ $$\rightarrow$$ $$\text{C})$$ $$\vee$$ $$(\text{B}$$ $$\leftrightarrow$$ $$\text{C})$$
11. $$((\text{A}$$ $$\rightarrow$$ $$\text{B})$$ $$\leftrightarrow$$ $$(\text{G}$$ $$\rightarrow$$ $$(\neg$$$$\text{A})))$$
12. $$((\text{A} \rightarrow \text{B}) \rightarrow ((\text{C} \rightarrow (\neg\text{B})) \leftrightarrow (\neg\text{D})))$$

Intuitivamente as duas primeiras expressões dadas são destituídas de sentido, ao passo que as demais constitui uma expressão "bem formada", também conhecidas como fórmulas bem formuladas ou wffs (de well-formed formulas). Usaremos as expressões "bem formadas".

Daqui em diante, usaremos a seguinte terminologia:

1. $$(\neg$$$$\text{A})$$ é do tipo não.
2. $$(\text{A}$$ $$\wedge$$ $$\text{B})$$ é do tipo e.
3. $$(\text{A}$$ $$\vee$$ $$\text{B})$$ é do tipo ou inclusivo.
4. $$(\text{A}$$ $$\veebar$$ $$\text{B})$$ é do tipo ou exclusivo.
5. $$(\text{A}$$ $$\rightarrow$$ $$\text{B})$$ é do tipo implicação.
6. $$(\text{A}$$ $$\leftrightarrow$$ $$\text{B})$$ é do tipo bi-implicação.

Criação de fórmulas

Agora que você sabe o que é uma fórmula e as suas definições, vamos aprender como se cria uma.

Com base na primeira definição que diz: "todas fórmulas atômicas são fórmulas". Concluímos que qualquer meta-variável isolada é uma fórmula. Exemplos:

1. $$\text{A}$$
2. $$(\text{G})$$

Seja $$\text{R} \equiv$$ "A terra é quadrada" e $$\text{P} \equiv$$ "A lua é um satélite". São fórmulas:

1. $$\text{R}$$
2. $$(\text{R})$$
3. $$\text{P}$$
4. $$(\text{P})$$

Observação importante: as letras maiúsculas do alfabeto romano são usadas para representar sentenças na fórmula, como já foi explicado anteriormente.

A segunda definição diz: "se $$\text{A}$$ e $$\text{B}$$ são fórmulas, então $$(\neg$$$$\text{A})$$, $$(\text{A}$$ $$\wedge$$ $$\text{B})$$, $$(\text{A}$$ $$\vee$$ $$\text{B})$$, $$(\text{A}$$ $$\veebar$$ $$\text{B})$$, $$(\text{A}$$ $$\rightarrow$$ $$\text{B})$$ e $$(\text{A}$$ $$\leftrightarrow$$ $$\text{B})$$ são fórmulas". Concluímos que qualquer meta-variável ligada a um conectivo é uma fórmula. Exemplos:

1. $$\rightarrow$$ $$\wedge$$ $$\text{A}$$ $$\text{B}$$ $$\text{C}$$
2. $$\vee$$ $$\text{A}$$ $$\text{B}$$
3. $$\text{A}$$ $$\vee$$ $$\neg$$$$\text{B}$$ $$\rightarrow$$ $$\text{C}$$ $$\leftrightarrow$$ $$\text{A}$$ $$\wedge$$ $$\text{D}$$
4. $$((\text{A}$$ $$\vee$$ $$\text{D})$$ $$\wedge$$ $$(\text{B}$$ $$\rightarrow$$ $$\text{C}))$$

Todas as fórmulas acima querem dizer algo. Mais para frente você aprenderá sobre eliminação de parênteses e notação polonesa, mas no momento fique sabendo que os parênteses, colchetes e chaves são utilizados para nos auxiliarem no entendimento da mesma.

Assim como na matemática, na lógica os conectivos também possuem uma hierarquia. Tal hierarquia (ou ordem de precedência) é a seguinte:

1. $$( )$$, $$[ ]$$, $$\{ \}$$
2. $$\neg$$
3. $$\wedge$$, $$\vee$$, $$\veebar$$
4. $$\rightarrow$$
5. $$\leftrightarrow$$

Em caso de empate, é resolvida a operação da esquerda para a direita.

Com base na ordem de precedência concluímos que $$(\text{P}$$ $$\wedge$$ $$(\text{Q}$$ $$\rightarrow$$ $$\text{R}))$$ é diferente de $$(\text{P}$$ $$\wedge$$ $$\text{Q}$$ $$\rightarrow$$ $$\text{R})$$, assim como na matemática que $$2$$ $$+$$ $$4$$ $$\times$$ $$3$$ é diferente de $$(2$$ $$+$$ $$4)$$ $$\times$$ $$3$$. Então não basta apenas seguir as definições de fórmula, temos que ficar atentos à hierarquia.

Concluímos que para formular sentenças válidas devemos seguir as definições de fórmula, mas sempre visando as sentenças "bem formadas" e obedecendo a hierarquia dos conectivos. Caso seja necessário priorizar os "subordinados", faça-se o uso dos símbolos auxiliares.

O que você aprendeu

Este artigo serviu para vislumbrar o leitor com o conceito de fórmulas atômicas e complexa, a precedência dos conectivos e com a criação de fórmulas. Especificamente, você aprendeu:

• O que é fórmula.
• O que é meta-variável.
• O que é cláusula maximal.
• O que é fórmula complexa.
• O que é fórmula atômica.
• Qual a diferença entre fórmula atômica e complexa.
• Hierarquia dos conectivos lógicos.

Continua em

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

Continuação de

Lógica Proposicional - Conectivo e Tabela-Verdade

Veja todos os artigos em
Lista de Artigos sobre Lógica Proposicional

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.

IME-USP. Máximo versus maximal. Disponível em: <http://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/guloso.html>. Acesso em: 07 jul. 2016.

Para citar esse artigo: