Lógica Proposicional: Definições, Tabelas de Verdade e Exemplos

A lógica proposicional (também chamada cálculo proposicional ou lógica dos enunciados) constitui o nível fundamental da lógica matemática e fornece o aparelho formal para a análise rigorosa do raciocínio dedutivo. Estuda as proposições — isto é, os enunciados declarativos aos quais se pode associar de modo unívoco um valor de verdade — e as suas combinações por meio de conectivos lógicos.

Apresentamos aqui uma exposição sistemática e completa: linguagem formal, sintaxe, semântica vero-funcional, equivalências e leis fundamentais, tautologias e consequência lógica, formas normais, sistemas dedutivos e os teoremas metalógicos da correção e da completude.

Índice

• Proposições e linguagem formal
• Sintaxe das fórmulas bem formadas
• Semântica e interpretações
• Conectivos lógicos e completude funcional
• Tabelas de verdade
• Equivalências lógicas
• Leis fundamentais
• Tautologias, satisfazibilidade e consequência lógica
• Formas normais (FNC e FND)
• Sistemas dedutivos
• Correção e completude
• Exemplos avançados

Proposições e linguagem formal

Uma proposição (ou enunciado) é uma frase declarativa dotada de sentido que, em virtude do princípio da bivalência, assume de modo unívoco exatamente um dos dois valores de verdade: verdadeiro (\(V\) ou \(1\)) ou falso (\(F\) ou \(0\)).

Uma proposição diz-se atómica (ou enunciado simples) quando não contém em si outras proposições ligadas por meio de operadores lógicos. As proposições obtidas combinando proposições atómicas através de conectivos lógicos dizem-se compostas (ou moleculares).

Fixa-se um conjunto numerável de variáveis proposicionais, geralmente denotadas por letras latinas minúsculas:

\[ \mathcal{P} = \{p_1, p_2, p_3, \dots\} = \{p, q, r, \dots\} \]

A linguagem da lógica proposicional \(\mathcal{L}\) é constituída pelos seguintes símbolos:

• as variáveis proposicionais de \(\mathcal{P}\);
• os conectivos lógicos: \(\neg,\ \land,\ \lor,\ \rightarrow,\ \leftrightarrow\);
• os símbolos auxiliares: parênteses \((,\ )\).

Sintaxe das fórmulas bem formadas

O conjunto \(\mathcal{F}\) das fórmulas bem formadas (fbf) é o menor conjunto de cadeias sobre o alfabeto de \(\mathcal{L}\) definido indutivamente pelas seguintes cláusulas:

1. Cláusula base: toda variável proposicional \(p \in \mathcal{P}\) é uma fbf;
2. Cláusulas indutivas:
   • se \(A \in \mathcal{F}\), então \((\neg A) \in \mathcal{F}\);
   • se \(A, B \in \mathcal{F}\), então \((A \land B),\ (A \lor B),\ (A \rightarrow B),\ (A \leftrightarrow B) \in \mathcal{F}\);
3. Cláusula de fecho: nenhuma outra cadeia é uma fbf.

Em notação BNF, a gramática da linguagem escreve-se:

\[ A ::= p \mid (\neg A) \mid (A \land A) \mid (A \lor A) \mid (A \rightarrow A) \mid (A \leftrightarrow A) \]

Por convenção de precedência, atribui-se aos conectivos a seguinte ordem decrescente de força de ligação, o que permite omitir parênteses sem ambiguidade:

\[ \neg \;>\; \land \;>\; \lor \;>\; \rightarrow \;>\; \leftrightarrow \]

Advertência. Embora a precedência de \(\neg\) sobre todos os demais conectivos e a menor precedência de \(\rightarrow\) e \(\leftrightarrow\) sejam universalmente aceites, a ordem relativa entre \(\land\) e \(\lor\) não é uniforme na literatura: alguns autores (por analogia com \(\cdot\) e \(+\) na álgebra de Boole) atribuem a \(\land\) uma precedência superior à de \(\lor\), enquanto outros (por exemplo, Mendelson) os colocam ao mesmo nível e exigem parênteses explícitos. É, portanto, boa prática, perante qualquer possível ambiguidade, explicitar os parênteses entre \(\land\) e \(\lor\): escreve-se, por exemplo, \( (A \land B) \lor C \) em vez de \( A \land B \lor C \).

O princípio de indução estrutural sobre as fbf afirma que, para demonstrar uma propriedade \(P\) para toda \(A \in \mathcal{F}\), basta estabelecer:

• (caso base) \(P\) vale para toda proposição atómica;
• (passo indutivo) \(P\) é preservada pela aplicação de cada conectivo.

Semântica e interpretações

A semântica da lógica proposicional é vero-funcional: o valor de verdade de uma fórmula composta fica univocamente determinado pelos valores de verdade das suas subfórmulas.

Uma interpretação (ou valoração, ou atribuição de valores de verdade) é uma função:

\[ v : \mathcal{P} \to \{V, F\} \]

que se estende de modo único a uma função \(\hat{v} : \mathcal{F} \to \{V, F\}\) através das seguintes cláusulas recursivas:

• \( \hat{v}(\neg A) = V \iff \hat{v}(A) = F \);
• \( \hat{v}(A \land B) = V \iff \hat{v}(A) = V \text{ e } \hat{v}(B) = V \);
• \( \hat{v}(A \lor B) = V \iff \hat{v}(A) = V \text{ ou } \hat{v}(B) = V \) (eventualmente ambos);
• \( \hat{v}(A \rightarrow B) = F \iff \hat{v}(A) = V \text{ e } \hat{v}(B) = F \);
• \( \hat{v}(A \leftrightarrow B) = V \iff \hat{v}(A) = \hat{v}(B) \).

Se uma fórmula contém \(n\) variáveis proposicionais distintas, o número de interpretações possíveis (restritas a essas variáveis) é \(2^n\).

Observação importante. O conectivo \(\lor\) representa a disjunção inclusiva (correspondente ao vel latino): \(A \lor B\) é verdadeira sempre que pelo menos uma das duas proposições o seja, incluindo o caso em que ambas o são. Importa distingui-la da disjunção exclusiva (correspondente ao aut latino, denotada \(\oplus\) ou XOR), em que \(A \oplus B\) é verdadeira se e somente se \(A\) e \(B\) tiverem valores de verdade diferentes. Em símbolos:

\[ A \oplus B \;\equiv\; (A \lor B) \land \neg(A \land B) \;\equiv\; \neg(A \leftrightarrow B) \]

Na linguagem corrente portuguesa, a conjunção «ou» é ambígua entre as duas leituras; a lógica formal elimina essa ambiguidade adoptando por defeito a leitura inclusiva.

Conectivos lógicos e completude funcional

Os conectivos lógicos são operadores vero-funcionais, isto é, funções \(\{V,F\}^n \to \{V,F\}\):

• a negação \(\neg\) é um operador unário;
• a conjunção \(\land\), a disjunção \(\lor\), o condicional (ou implicação) \(\rightarrow\) e o bicondicional \(\leftrightarrow\) são operadores binários.

Um conjunto de conectivos diz-se funcionalmente completo (ou adequado) quando toda função de verdade \(\{V,F\}^n \to \{V,F\}\) pode exprimir-se mediante combinações desses conectivos. São funcionalmente completos, por exemplo:

\[ \{\neg, \land, \lor\}, \quad \{\neg, \land\}, \quad \{\neg, \lor\}, \quad \{\neg, \rightarrow\} \]

Existem, ainda, conectivos binários funcionalmente completos por si sós: a barra de Sheffer (NAND), denotada \(\uparrow\), e a seta de Peirce (NOR), denotada \(\downarrow\).

As definições semânticas justificam as seguintes reduções, que mostram que \(\rightarrow\) e \(\leftrightarrow\) são definíveis a partir de \(\{\neg, \land, \lor\}\):

\[ A \rightarrow B \equiv \neg A \lor B \]

\[ A \leftrightarrow B \equiv (A \rightarrow B) \land (B \rightarrow A) \equiv (A \land B) \lor (\neg A \land \neg B) \]

Tabelas de verdade

Uma tabela de verdade é a representação tabular da função vero-funcional associada a uma fórmula. Para uma fórmula com \(n\) variáveis distintas, a tabela é constituída por \(2^n\) linhas, uma para cada interpretação possível.

As tabelas de verdade dos conectivos fundamentais são as seguintes:

Note-se que o condicional \(A \rightarrow B\) é falso unicamente quando o antecedente \(A\) é verdadeiro e o consequente \(B\) é falso: trata-se da única linha em que assume o valor \(F\).

Equivalências lógicas

Duas fórmulas \(A\) e \(B\) dizem-se logicamente equivalentes, o que se denota \(A \equiv B\), quando assumem o mesmo valor de verdade em toda interpretação:

\[ A \equiv B \iff \forall v,\ \hat{v}(A) = \hat{v}(B) \]

A relação \(\equiv\) é uma relação de equivalência sobre \(\mathcal{F}\) (reflexiva, simétrica, transitiva) e, além disso, uma congruência: o teorema da substituição afirma que, se \(A \equiv B\) e \(C[A]\) é uma fórmula que contém \(A\) como subfórmula, então \(C[A] \equiv C[B]\), onde \(C[B]\) se obtém substituindo (uma ocorrência de) \(A\) por \(B\) em \(C\).

É essencial distinguir \(\equiv\) (relação metalinguística entre fórmulas) do conectivo \(\leftrightarrow\) (que pertence à linguagem-objecto); de facto,

\[ A \equiv B \iff \models A \leftrightarrow B \]

isto é, \(A\) e \(B\) são logicamente equivalentes se e somente se \(A \leftrightarrow B\) é uma tautologia.

Leis fundamentais

As equivalências seguintes, todas demonstráveis através de tabelas de verdade, constituem as leis fundamentais do cálculo proposicional (\(\top\) denota uma tautologia qualquer, \(\bot\) uma contradição):

• Idempotência: \(A \land A \equiv A\), \(\quad A \lor A \equiv A\)
• Comutatividade: \(A \land B \equiv B \land A\), \(\quad A \lor B \equiv B \lor A\)
• Associatividade: \((A \land B) \land C \equiv A \land (B \land C)\), e analogamente para \(\lor\)
• Distributividade: \(A \land (B \lor C) \equiv (A \land B) \lor (A \land C)\), \(\quad A \lor (B \land C) \equiv (A \lor B) \land (A \lor C)\)
• Dupla negação: \(\neg \neg A \equiv A\)
• Leis de De Morgan: \(\neg(A \land B) \equiv \neg A \lor \neg B\), \(\quad \neg(A \lor B) \equiv \neg A \land \neg B\)
• Absorção: \(A \land (A \lor B) \equiv A\), \(\quad A \lor (A \land B) \equiv A\)
• Elemento neutro: \(A \land \top \equiv A\), \(\quad A \lor \bot \equiv A\)
• Elemento absorvente: \(A \lor \top \equiv \top\), \(\quad A \land \bot \equiv \bot\)
• Terceiro excluído: \(A \lor \neg A \equiv \top\)
• Não contradição: \(A \land \neg A \equiv \bot\)
• Contraposição: \(A \rightarrow B \equiv \neg B \rightarrow \neg A\)
• Exportação: \((A \land B) \rightarrow C \equiv A \rightarrow (B \rightarrow C)\)

Tautologias, satisfazibilidade e consequência lógica

Seja \(A \in \mathcal{F}\). Diz-se que:

• \(A\) é uma tautologia (ou fórmula logicamente válida), o que se denota \(\models A\), se \(\hat{v}(A) = V\) em toda interpretação \(v\);
• \(A\) é uma contradição (ou fórmula insatisfazível) se \(\hat{v}(A) = F\) em toda \(v\);
• \(A\) é satisfazível se existe pelo menos uma interpretação \(v\) tal que \(\hat{v}(A) = V\);
• \(A\) é contingente se é satisfazível mas não é uma tautologia.

As quatro categorias estão ligadas pela dualidade:

\[ A \text{ é tautologia} \iff \neg A \text{ é contradição} \]

Sejam \(\Gamma \subseteq \mathcal{F}\) um conjunto (eventualmente infinito) de fórmulas e \(B \in \mathcal{F}\). Diz-se que \(B\) é consequência lógica (semântica) de \(\Gamma\), e escreve-se

\[ \Gamma \models B \]

se, para toda interpretação \(v\) tal que \(\hat{v}(A) = V\) para todo \(A \in \Gamma\), se tem \(\hat{v}(B) = V\). Equivalentemente: todo modelo de \(\Gamma\) é modelo de \(B\).

Teorema da dedução semântica:

\[ \Gamma \cup \{A\} \models B \iff \Gamma \models A \rightarrow B \]

Em particular, tomando \(\Gamma = \emptyset\), obtém-se \(A \models B\) se e somente se \(\models A \rightarrow B\).

Formas normais (FNC e FND)

Chama-se literal a uma variável proposicional ou à sua negação: \(p\) ou \(\neg p\). Em consequência:

• uma cláusula disjuntiva é uma disjunção de literais: \(\ell_1 \lor \ell_2 \lor \dots \lor \ell_k\);
• uma cláusula conjuntiva é uma conjunção de literais: \(\ell_1 \land \ell_2 \land \dots \land \ell_k\).

Uma fórmula está em:

• Forma Normal Conjuntiva (FNC) se for uma conjunção de cláusulas disjuntivas;
• Forma Normal Disjuntiva (FND) se for uma disjunção de cláusulas conjuntivas.

Teorema (existência das formas normais). Toda fórmula \(A \in \mathcal{F}\) é logicamente equivalente a uma fórmula em FNC e a uma fórmula em FND.

Procedimento de redução:

1. eliminar o bicondicional: \(A \leftrightarrow B \equiv (A \rightarrow B) \land (B \rightarrow A)\);
2. eliminar o condicional: \(A \rightarrow B \equiv \neg A \lor B\);
3. levar as negações até ficarem apenas diante de variáveis (leis de De Morgan e dupla negação), obtendo assim a forma normal negativa (FNN);
4. aplicar a distributividade para alcançar a forma desejada: \(\lor\) sobre \(\land\) para a FND, \(\land\) sobre \(\lor\) para a FNC.

Exemplo:

\[ A \rightarrow (B \lor C) \;\equiv\; \neg A \lor (B \lor C) \;\equiv\; \neg A \lor B \lor C \]

que se encontra simultaneamente em FNC (uma única cláusula disjuntiva) e em FND (disjunção de cláusulas conjuntivas reduzidas a literais isolados).

Sistemas dedutivos

Um sistema dedutivo (ou cálculo lógico) é um aparelho puramente sintáctico, constituído por axiomas e regras de inferência, que permite derivar fórmulas a partir de premissas sem recurso à semântica. A noção central é a de derivabilidade: escreve-se

\[ \Gamma \vdash A \]

para indicar que existe uma derivação da fórmula \(A\) a partir das premissas \(\Gamma\) no sistema considerado.

Os sistemas dedutivos mais difundidos para a lógica proposicional são:

• Sistemas axiomáticos (ao estilo Hilbert-Frege): poucos esquemas axiomáticos e uma única regra de inferência (o modus ponens);
• Dedução natural (Gentzen, Prawitz): regras de introdução e eliminação para cada conectivo;
• Cálculo de sequentes (Gentzen): regras que actuam sobre sequentes \(\Gamma \Rightarrow \Delta\);
• Tableaux semânticos (Beth, Smullyan): método de refutação baseado em árvores.

As regras de inferência mais importantes são:

Modus Ponens (eliminação de \(\rightarrow\)):

\[ \dfrac{A \qquad A \rightarrow B}{B} \]

Modus Tollens (regra da contrarrecíproca):

\[ \dfrac{A \rightarrow B \qquad \neg B}{\neg A} \]

Silogismo hipotético (transitividade do condicional):

\[ \dfrac{A \rightarrow B \qquad B \rightarrow C}{A \rightarrow C} \]

Silogismo disjuntivo:

\[ \dfrac{A \lor B \qquad \neg A}{B} \]

Introdução e eliminação da conjunção:

\[ \dfrac{A \qquad B}{A \land B} \qquad\qquad \dfrac{A \land B}{A} \qquad\qquad \dfrac{A \land B}{B} \]

Redução ao absurdo (demonstração por contradição):

\[ \dfrac{\Gamma, \neg A \vdash \bot}{\Gamma \vdash A} \]

Correção e completude

A relação entre a derivabilidade sintáctica \(\vdash\) e a consequência semântica \(\models\) é expressa pelos dois teoremas metalógicos fundamentais da lógica proposicional.

Teorema da correção. Para todo \(\Gamma \subseteq \mathcal{F}\) e todo \(A \in \mathcal{F}\):

\[ \Gamma \vdash A \;\Longrightarrow\; \Gamma \models A \]

Tudo o que é derivável sintacticamente é, efectivamente, consequência semântica das premissas.

Teorema da completude (Post, 1921). Para todo \(\Gamma \subseteq \mathcal{F}\) e todo \(A \in \mathcal{F}\):

\[ \Gamma \models A \;\Longrightarrow\; \Gamma \vdash A \]

Toda consequência semântica pode efectivamente ser derivada no cálculo.

Combinando os dois resultados, obtém-se a equivalência entre sintaxe e semântica:

\[ \Gamma \vdash A \iff \Gamma \models A \]

A estes teoremas juntam-se outros dois resultados metalógicos de relevo:

• Teorema da compacidade: \(\Gamma\) é satisfazível se e somente se todo subconjunto finito de \(\Gamma\) o for;
• Decidibilidade: existe um algoritmo (por exemplo, o método das tabelas de verdade) que, num número finito de passos, decide se uma dada fórmula é ou não uma tautologia.

Exemplos avançados

A lógica proposicional representa o primeiro nível de formalização do raciocínio matemático. Apesar do seu poder expressivo limitado — não permite descrever a estrutura interna das proposições —, fornece os instrumentos conceptuais fundamentais para abordar a lógica de primeira ordem, as teorias axiomáticas, a metalógica e as estruturas algébricas associadas (álgebras de Boole, reticulados). O seu domínio constitui um pré-requisito imprescindível a qualquer estudo rigoroso da matemática e da informática teórica.