Lógica de Primeira Ordem

🔍 lógica de primeira ordem · predicados, quantificadores & axiomas

📌 Definição e exemplos

A lógica de primeira ordem — ou cálculo de predicados de primeira ordem — expande a lógica proposicional ao introduzir quantificadores (\(\forall\), \(\exists\)), variáveis e predicados. Com isso, é possível formalizar sentenças como "todo número natural é maior ou igual a zero" ou "existe um número primo par". É a linguagem padrão para axiomatizar a matemática.

\[ \forall x \, ( \text{Nat}(x) \rightarrow x \ge 0 ) \qquad \exists y \, ( \text{Primo}(y) \land \text{Par}(y) ) \]

Os símbolos lógicos incluem conectivos (\(\land, \lor, \neg, \rightarrow\)) e os quantificadores universal (\(\forall\)) e existencial (\(\exists\)).

⚙️ Estrutura de um cálculo de predicados

Um sistema de primeira ordem é composto por três pilares:

• Regras de formação: Definem indutivamente as fórmulas bem-formadas (FBFs). Ex.: se \(P\) é um predicado de aridade \(n\) e \(t_1,\dots,t_n\) são termos, então \(P(t_1,\dots,t_n)\) é uma fórmula.
• Regras de transformação: Regras de inferência (ex.: modus ponens, generalização universal) que permitem derivar novas fórmulas a partir de axiomas.
• Axiomas lógicos e não-lógicos: Esquemas axiomáticos como \(\forall x P(x) \rightarrow P(t)\) (substituição) mais axiomas específicos da teoria (ex.: axiomas de Peano para aritmética).

Por exemplo, na aritmética de Peano temos axiomas como \(\forall x (Sx \neq 0)\) e o princípio de indução. A lógica de primeira ordem fornece o arcabouço para expressar essas verdades fundamentais.

\[ \forall x \forall y (Sx = Sy \rightarrow x = y) \quad \text{(axioma de Peano)} \]

🧮 princípio fundamental da contagem (análise combinatória)

Embora seja um tópico de combinatória, o princípio multiplicativo dialoga com a lógica ao contar possibilidades. Se um evento A pode ocorrer de \(k_1\) maneiras e, para cada uma, um evento B pode ocorrer de \(k_2\) maneiras, então o número total de modos é \(k_1 \times k_2\).

\[ \#(\text{escolhas totais}) = k_1 \cdot k_2 \cdot \ldots \cdot k_n \]

Exemplo clássico: Alice tem 3 modelos de carro e 5 opções de cor → \(3 \times 5 = 15\) possibilidades. Esse princípio é a base para contagens mais complexas e está presente em problemas de lógica combinatória.

📋 diagrama Representação visual de quantificadores e regras de inferência.

▶️ vídeo Introdução ao cálculo de predicados e quantificadores.

🧠 conexão: lógica & combinatória

Na teoria dos modelos e na computação, usamos lógica de primeira ordem para descrever estruturas finitas. O princípio da contagem surge, por exemplo, ao contar o número de atribuições de verdade que satisfazem uma fórmula (model counting). É uma ponte sutil entre a lógica e a combinatória.

✦ “Lógica é a anatomia do pensamento.” – John Locke ✦ fórmulas em \(\LaTeX\) & design cuidadoso.