Lógica Proposicional e de Primeira Ordem: Fundamentos e Computabilidade

Lógica proposicional e de primeira ordem

Imagine um interruptor de luz na parede da sua sala. Ou ele está ligado e a lâmpada acende, ou ele está desligado e o quarto fica no escuro. Não existe meio-termo, estado morno ou talvez. A computação inteira foi erguida sobre essa ideia simples: afirmações que só podem ser verdadeiras ou falsas, combinadas de forma rigorosa para que uma máquina nunca precise adivinhar o que fazer.

Esta aula ensina os dois sistemas lógicos que fundamentam a arquitetura de processadores, a escrita de condicionais em código, consultas a bancos de dados relacionais e a verificação formal de algoritmos. Primeiro veremos a lógica proposicional (seções 1 a 4), que trata de sentenças completas e conectivos booleanos. Em seguida, avançaremos para a lógica de primeira ordem (seções 5 a 8), que desmonta essas sentenças para enxergar objetos, propriedades e quantificadores. As seções finais reúnem erros clássicos de implementação, exercícios com resolução comentada, glossário e fontes de estudo.

1. O que é uma proposição

Uma proposição é qualquer frase declarativa que afirma um fato sobre o mundo e que pode ser classificada de forma absoluta como verdadeira (V) ou falsa (F). Dois princípios da lógica clássica proíbem qualquer zona cinzenta: o princípio da não-contradição (uma sentença não pode ser verdadeira e falsa ao mesmo tempo) e o princípio do terceiro excluído (não há uma terceira alternativa além de verdadeiro ou falso).

Na prática, isso separa claramente o que um computador consegue avaliar do que pertence à ambiguidade humana. Considere as frases a seguir:

• “O servidor respondeu com status HTTP 200”: proposição válida. O evento aconteceu ou não aconteceu.
• “O número 13 é primo”: proposição válida e verdadeira.
• “2 + 2 = 5”: proposição válida, ainda que seja falsa.
• “Feche a conexão com o banco de dados”: não é proposição. Trata-se de uma ordem imperativa, sem valor-verdade.
• “Esta frase é mentira”: não é proposição. É um paradoxo auto-referencial que quebra os princípios da lógica.
• “x > 10”: sentença aberta. Enquanto não dissermos quem é x, o computador não sabe se é verdadeiro ou falso. Para lidar com esse caso, inventaram a lógica de predicados, que estudaremos na segunda metade desta aula.

2. Conectivos e álgebra booleana

Proposições atômicas, representadas por letras como p, q e r, ganham poder quando são unidas por conectivos lógicos. Na arquitetura de computadores, cada conectivo desses corresponde a uma porta lógica feita de transistores na CPU. No seu editor de código, eles aparecem como operadores booleanos.

A negação (¬p ou !p) simplesmente inverte o valor-verdade. A conjunção (p ∧ q ou p && q) exige que ambas as partes sejam verdadeiras para que o conjunto seja verdadeiro. A disjunção inclusiva (p ∨ q ou p || q) exige que ao menos uma seja verdadeira. A disjunção exclusiva (p ⊕ q ou p ^ q) exige que os valores sejam diferentes entre si: ou um ou outro, nunca os dois ao mesmo tempo.

O mistério da implicação: por que falso implica qualquer coisa?

A linha mais contraintuitiva da tabela-verdade é a condicional (p → q, lida como “se p, então q”). Quando p é falso, a sentença inteira é classificada como verdadeira, não importa se q é verdadeiro ou falso. Para a maioria das pessoas, isso soa absurdo à primeira vista: como uma afirmação que começa com uma premissa falsa pode ser considerada uma verdade lógica?

Existem três maneiras muito simples e complementares de entender esse mecanismo sem decorar regras arbitrárias.

1. A analogia da promessa (o teste do mentiroso)

Imagine que um pai diga ao filho: “se chover no sábado (p), eu te levo ao cinema (q)”.

Quando é que você pode apontar o dedo para esse pai e dizer que ele mentiu?

• Sábado choveu (p = V) e ele levou o filho ao cinema (q = V). Ele cumpriu o que disse. Sentença verdadeira.
• Sábado choveu (p = V) e ele se recusou a ir ao cinema (q = F). Ele quebrou a promessa. Sentença falsa.
• Sábado fez um sol radiante (p = F) e eles ficaram em casa (q = F). O pai mentiu? Não. Ele nunca disse o que faria se fizesse sol. A promessa não foi violada. Sentença verdadeira.
• Sábado fez sol (p = F), mas ele resolveu levar o filho ao cinema mesmo assim (q = V). O pai mentiu? Também não. Ele prometeu levar se chovesse, mas não proibiu um passeio no sol. A promessa continua intacta. Sentença verdadeira.

Em lógica clássica, uma condicional só é declarada falsa se existir um flagrante de quebra de promessa, isto é, quando a condição acontece (p = V) e a consequência prometida deixa de ser entregue (q = F). Se a condição de partida nunca aconteceu (p = F), o contrato não foi violado. Na falta de uma prova de culpa, a sentença é considerada verdadeira por vacuidade (ou presunção de inocência).

2. O teste da matemática com números reais

Considere a seguinte regra matemática sobre números inteiros:

“Para qualquer número x, se x for divisível por 4 (p), então x é par (q).”

Todo mundo concorda que essa afirmação é uma verdade matemática universal. Agora vamos testar essa regra escolhendo o número 6:

• 6 é divisível por 4? Falso (p = F).
• 6 é par? Verdadeiro (q = V).

Se a lógica classificasse falso implicando verdadeiro (F → V) como uma falsidade, a presença do número 6 no universo tornaria a regra inteira mentirosa. O número 6 não desmente que “quem é divisível por 4 é par”. Para que teoremas e regras gerais continuem válidos sobre elementos que não atendem ao gatilho de entrada, F → V e F → F precisam ser obrigatoriamente verdadeiros.

3. A visão de contrato no código de software

No desenvolvimento de software, funções e APIs operam pelo princípio de pré-condições (Design by Contract).

Considere uma especificação de regra de pagamento: “se o pagamento for confirmado em cartão de crédito (p), gere o comprovante fiscal imediatamente (q)”.

Se o cliente pagar com Pix ou boleto bancário (p = F), o código que gerencia a fila de cartão de crédito sequer executa. Ele não quebrou sua garantia contratual se não gerou comprovante de cartão, e nem se uma rotina paralela de notas gerou o recibo para o Pix. A rotina só estaria com bug (falsa) se o pagamento no cartão entrasse com sucesso e o sistema falhasse em emitir a nota.

Por todas essas razões, a condicional possui uma equivalência direta que elimina qualquer mágica:

p → q ≡ ¬p ∨ q

Dizer “se p, então q” significa exatamente o mesmo que dizer: “ou o evento p não aconteceu, ou a promessa q foi cumprida”. Se p não aconteceu (¬p é verdadeiro), a expressão inteira já é verdadeira pelo primeiro termo, sem sequer olhar para q.

3. Avaliação de expressões e circuitos de decisão

Quando várias condições são encadeadas numa regra de negócio, o compilador avalia a árvore lógica para decidir o fluxo de execução. Veja o diagrama abaixo, que ilustra um middleware de autorização de publicação em uma plataforma web:

O olhar percorre a figura da esquerda para a direita. Na entrada, o sistema recebe três proposições atômicas sobre o usuário requisitante: se ele possui papel de administrador (p), se ele é o autor original do texto (q) e se a conta dele está suspensa por moderação (r).

A primeira camada processa a permissão combinando p e q em uma disjunção (p ∨ q). Como o usuário é administrador, essa saída já é verdadeira. Em paralelo, o estado de suspensão passa por uma negação (¬r). Como a conta não está suspensa (r é falso), ¬r torna-se verdadeiro. O nó central combina esses dois resultados intermediários por uma conjunção: verdadeiro E verdadeiro resulta em verdadeiro. O pacote verde segue até o nó de autorização e a requisição recebe HTTP 200. Se qualquer ramo essencial falhasse, a conjunção final barraria o pacote e dispararia o ramo de bloqueio HTTP 403.

Linguagens modernas implementam a chamada avaliação de curto-circuito (short-circuit evaluation). Em uma conjunção (A && B), se A for falso, a máquina sequer lê B, porque nada salvará a conjunção. Em uma disjunção (A || B), se A for verdadeiro, B é ignorado pelo mesmo motivo. Escrever código sabendo disso evita checagens de ponteiro nulo (como usuario != null && usuario.ativo).

4. As leis de De Morgan e simplificação de código

Na década de 1840, Augustus De Morgan formalizou como a negação interage com a conjunção e a disjunção. No desenvolvimento de software, essas leis são a ferramenta mais eficiente para faxinar estruturas condicionais ilegíveis.

¬(p ∧ q) ≡ ¬p ∨ ¬q

¬(p ∨ q) ≡ ¬p ∧ ¬q

A intuição cotidiana é direta: se não é verdade que alguém é rico E bonito, significa que essa pessoa ou não é rica, OU não é bonita (ou nenhum dos dois). Se não é verdade que hoje é sábado OU domingo, significa que hoje não é sábado E hoje não é domingo.

O diagrama compara os dois estados de um mesmo fluxo. No grupo da esquerda, a verificação original agrupa termos dentro de parênteses e nega o bloco todo: !(isWeekend || isHoliday). O cérebro do programador que lê isso é obrigado a guardar o resultado da soma lógica para só então inverter o sinal.

No grupo da direita, a regra de De Morgan distribui a negação para dentro dos termos e inverte o operador central de OU para E: !isWeekend && !isHoliday. Agora, cada teste é independente, legível e aproveita o curto-circuito do compilador. Se a primeira checagem acusar que é fim de semana, o segundo teste sequer consome ciclos de CPU.

5. Por que a lógica proposicional é insuficiente

Apesar de poderosa para circuitos e ifs, a lógica proposicional é cega para a estrutura interna dos dados. O exemplo clássico vem da Grécia Antiga:

Premissa 1: Todo ser humano é mortal. Premissa 2: Sócrates é um ser humano. Conclusão: Sócrates é mortal.

Se tentarmos modelar esse argumento com lógica proposicional, seremos forçados a atribuir uma letra isolada para cada frase: p, q e r. Mas a fórmula (p ∧ q) → r não é uma tautologia. Ela não garante nada, porque a lógica proposicional enxerga as frases como caixas-pretas lacradas. Ela não sabe que “Sócrates” é um elemento específico e que “humano” e “mortal” são propriedades compartilhadas por um grupo.

Para resolver essa limitação, matemáticos como Gottlob Frege e Charles Sanders Peirce desenvolveram a lógica de primeira ordem (também chamada de cálculo de predicados). Ela abre a caixa-preta e introduz quatro peças fundamentais:

• Constantes: objetos individuais bem identificados no sistema, como socrates, id_42 ou 'usuario_admin'.
• Variáveis: marcadores genéricos que podem assumir o valor de qualquer elemento do conjunto, normalmente escritos como x, y e z.
• Predicados: funções que recebem objetos e devolvem um valor booleano. Por exemplo, Humano(x) é verdadeiro se x for humano; Mortal(x) é verdadeiro se x for mortal.
• Funções: mapeamentos que recebem objetos e produzem outro objeto do domínio, como pai(x) ou saldo(conta).

Com essas peças, o raciocínio ganha estrutura matemática precisa: ∀x (Humano(x) → Mortal(x)) ∧ Humano(socrates) ⟹ Mortal(socrates)

6. Quantificadores e o universo de discurso

Toda afirmação na lógica de primeira ordem só faz sentido dentro de um universo de discurso (ou domínio), que é o conjunto de coisas sobre as quais estamos falando. Pode ser o conjunto de todos os números inteiros, todos os registros da tabela users, ou todos os arquivos de um diretório.

Para falar sobre a quantidade de elementos que satisfazem um predicado, usamos dois quantificadores:

O quantificador universal (∀)

O símbolo ∀ lê-se “para todo”, “para cada” ou “qualquer que seja”. A afirmação ∀x P(x) sustenta que a propriedade P é verdadeira para absolutamente todos os elementos do domínio. Se um único elemento falhar, a sentença inteira desmorona.

Em código, ∀ equivale a métodos como every() em JavaScript, all() em Python ou All() em C# LINQ:

# ∀x (x > 0)
todos_positivos = all(numero > 0 for numero in lista)

O quantificador existencial (∃)

O símbolo ∃ lê-se “existe pelo menos um” ou “para algum”. A afirmação ∃x P(x) exige apenas que você aponte um único exemplo no domínio para o qual P seja verdadeiro.

Em código, ∃ equivale a some() em JavaScript, any() em Python ou Any() em C#:

# ∃x (x == 0)
possui_zero = any(numero == 0 for numero in lista)

Veja como esses dois acumuladores operam sobre um conjunto real de dados:

O diagrama ilustra o processamento de uma consulta sobre a base de usuários. O domínio contém três entidades: Alice, Bob e Carlos. O predicado Ativo(x) é calculado para cada um deles. Alice e Bob retornam verdadeiro, mas Carlos retorna falso.

Ao propagar os resultados para os quantificadores à direita, as naturezas de cada um ficam evidentes. O quantificador universal (∀) funciona como uma grande conjunção: precisa que todos digam sim. A falha de Carlos barra a linha e força o resultado geral a ser falso. Já o quantificador existencial (∃) atua como uma grande disjunção: bastou a confirmação de Alice ou Bob para que a condição fosse plenamente satisfeita como verdadeira.

7. Negação de quantificadores e consultas SQL

Negar uma frase com quantificadores é uma das maiores armadilhas em entrevistas técnicas e na escrita de testes de software.

Se alguém diz “todos os testes da suíte passaram”, qual é a negação dessa frase? Quem responde “nenhum teste passou” erra feio. A negação lógica de que todos passaram é que pelo menos um falhou. Da mesma forma, negar que “existe algum erro na fila” significa afirmar com certeza absoluta que todos os itens da fila estão livres de erro.

As leis de De Morgan para a lógica de predicados estabelecem essa transição formalmente:

¬(∀x P(x)) ≡ ∃x ¬P(x)

¬(∃x P(x)) ≡ ∀x ¬P(x)

No dia a dia com bancos de dados relacionais, essa equivalência afeta diretamente a performance das suas queries. Quando você precisa saber se um cliente não possui faturas atrasadas, você pode escrever a consulta de duas formas equivalentes:

-- Forma 1: usando NOT EXISTS (¬∃)
SELECT c.id, c.nome 
FROM clientes c
WHERE NOT EXISTS (
    SELECT 1 FROM faturas f 
    WHERE f.cliente_id = c.id AND f.status = 'atrasada'
);

-- Forma 2: verificando se todas as faturas são não-atrasadas (∀)
-- que em SQL relacional é modelada verificando se o total de faturas
-- bate com o total de faturas pagas/em dia.

O otimizador de consultas do banco reescreve internamente essas relações lógicas para usar índices da forma mais barata possível.

8. A ordem dos quantificadores importa

Quando misturamos quantificadores universais e existenciais na mesma fórmula, a ordem em que eles aparecem altera completamente o significado da declaração.

Considere o predicado Gosta(x, y), significando que a pessoa x gosta da pessoa y:

• ∀x ∃y Gosta(x, y): Para toda pessoa x, existe alguém y de quem x gosta. Cada pessoa no mundo tem o seu próprio interesse amoroso ou amigo favorito. A escolha de y depende de quem é x.
• ∃y ∀x Gosta(x, y): Existe uma pessoa específica y tal que todas as pessoas x do mundo gostam dela. Agora estamos falando de uma única celebridade universalmente querida por toda a humanidade.

Trocar a ordem dos quantificadores em um algoritmo é o erro clássico que transforma uma busca independente de complexidade O(n) em um laço dependente com gargalo de memória.

9. Erros comuns e boas práticas

1. Confundir condicional material com causa e efeito. Na lógica matemática, p → q só analisa a combinação de valores booleanos, não se p causou q no tempo. Dizer “se a Terra gira, então o céu é azul” é uma proposição verdadeira na lógica, mesmo que um fato não cause o outro.
2. Esquecer de isolar negações em operadores relacionais. Negar x >= 10 vira x < 10, e não x <= 10. O sinal de igualdade migra ou desaparece durante a negação.
3. Não prever o domínio vazio. Dizer “todos os elementos da lista são pares” (∀x Par(x)) quando a lista está vazia resulta em verdadeiro por vacuidade. Na lógica formal, uma condição universal sobre um conjunto vazio é sempre verdadeira, porque não existe nenhum contraexemplo que possa refutá-la. Isso causa bugs frequentes em validações de formulários.
4. Parênteses insuficientes em expressões lógicas. Em quase todas as linguagens de programação, a conjunção (&&) tem precedência de operadores superior à disjunção (||), exatamente como a multiplicação tem precedência sobre a adição na aritmética. Escrever a || b && c é interpretado pelo compilador como a || (b && c). Deixar sem parênteses cria armadilhas silenciosas de manutenção.

10. Exercícios de fixação

Exercício 1: Simplificação booleana

Dada a expressão condicional abaixo, aplique as leis de De Morgan e a dupla negação para simplificá-la ao menor número possível de operadores:

E = ¬(¬a ∧ (b ∨ ¬c))

Resolução:

1. Aplica-se De Morgan na conjunção principal: ¬(¬a) ∨ ¬(b ∨ ¬c).
2. Pela regra da dupla negação, ¬(¬a) torna-se a.
3. Aplica-se De Morgan no segundo termo: ¬(b ∨ ¬c) torna-se ¬b ∧ ¬(¬c), que se reduz a ¬b ∧ c.
4. Resultado simplificado: a ∨ (¬b ∧ c). No código, isso troca um teste com três níveis de inversão por uma condicional direta e limpa: if (a || (!b && c)).

Exercício 2: Formalização em primeira ordem

Traduza para a lógica de primeira ordem a seguinte regra de segurança de um sistema hospitalar: “Todo médico tem acesso ao prontuário de qualquer paciente que esteja sob seus cuidados.”

Predicados:

• Medico(x): x é médico.
• Paciente(y): y é paciente.
• Cuida(x, y): x cuida de y.
• Acesso(x, y): x tem permissão de leitura sobre o prontuário de y.

Resolução: ∀x ∀y ((Medico(x) ∧ Paciente(y) ∧ Cuida(x, y)) → Acesso(x, y))

11. Glossário

• Tautologia: Fórmula proposicional que resulta sempre em verdadeiro para qualquer combinação de valores de suas variáveis (exemplo: p ∨ ¬p).
• Contradição: Fórmula proposicional que resulta sempre em falso (exemplo: p ∧ ¬p).
• Contingência: Fórmula cujo valor depende dos valores das variáveis que a compõem.
• Vacuidade: Verdade lógica obtida quando uma afirmação sobre todos os membros de um grupo é verdadeira simplesmente porque o grupo não contém membros para contestá-la.
• Isomorfismo de Curry-Howard: Teorema da ciência da computação teórica que estabelece que tipos de dados em programas correspondem exatamente a proposições lógicas, e programas correspondem a demonstrações formais dessas proposições.

12. Fontes e referências

• Rosen, Kenneth H. Discrete Mathematics and Its Applications, 8ª edição, McGraw-Hill, 2019 (Capítulos 1 e 2: The Foundations - Logic and Proofs).
• Lehman, Eric; Leighton, F. Thomson; Meyer, Albert R. Mathematics for Computer Science, MIT OpenCourseWare, 2018 (Capítulo 3: Logical Formulas). Consulta em novembro de 2026.
• Cormen, Thomas H. et al. Introduction to Algorithms, 4ª edição, MIT Press, 2022 (Apêndice A e B: Fundamentos matemáticos e notação lógica).

Relacionados

• Tempo logarítmico
• Big O
• PostgreSQL
• Representação da informação/Álgebra booleana e portas lógicas