Lógica de predicados

Abrindo a caixa preta: predicados e quantificadores sobre conjuntos inteiros.

A lógica proposicional trata cada proposição como uma unidade atômica. $P$ é uma caixa preta — sabemos que tem um valor-verdade, mas não olhamos seu conteúdo. A lógica de predicados abre essa caixa. Em vez de afirmações sobre proposições inteiras, faz afirmações sobre objetos e suas propriedades.

Todo triângulo tem três lados não cabe na lógica proposicional. Seria preciso uma proposição $P_t$ para cada triângulo $t$ no universo — uma quantidade impraticável, possivelmente infinita. A lógica de predicados resolve isso com predicados — propriedades aplicadas a variáveis — e quantificadores, que dizem quantas variáveis precisam satisfazer o predicado.

§1. Predicados

Um predicado é uma sentença aberta — uma proposição com buracos. $x$ é primo não tem valor-verdade até que $x$ seja fixado. $3$ é primo é proposição (verdadeira); $4$ é primo é proposição (falsa). O predicado em si, escrito $P(x)$, é uma função que recebe um valor e devolve um booleano.

def is_prime(x: int) -> bool: ...

is_prime(3) é uma proposição. is_prime por si só é um predicado.

Predicados podem ter mais de uma variável: $Q(x, y)$ é uma relação. $x$ é maior que $y$ precisa de dois valores para virar proposição. A aridade do predicado é o número de buracos.

§2. Quantificadores

Até aqui, cada sentença era sobre um único caso. Está chovendo. A rua está molhada. 3 é maior que 7. Cada uma é avaliada contra um mundo e sai verdadeira ou falsa.

Mas muitas das sentenças mais úteis percorrem um conjunto inteiro de elementos — todo elemento, ou algum elemento. Todo triângulo tem três lados. Existe um número primo maior que um milhão. Essas sentenças não se reduzem a uma verificação de valor-verdade único; percorrem um conjunto inteiro.

O universal

O quantificador universal é escrito $\forall$ e lido para todo ou para cada. O símbolo é um A invertido — all.

A sentença $\forall x\, P(x)$ diz: escolha qualquer $x$ do conjunto em questão, e $P(x)$ vale. Todo triângulo tem três lados é uma sentença universal sobre o conjunto dos triângulos. Para todo número real $x$, $x^2 \geq 0$ é uma sentença universal sobre os reais.

Em código, $\forall$ é a função que retorna verdadeiro exatamente quando todo elemento de um conjunto satisfaz o predicado:

all(x*x >= 0 for x in reals)   # ∀x: x² ≥ 0

O existencial

O quantificador existencial é escrito $\exists$ e lido existe ou há. O símbolo é um E espelhado — exists.

A sentença $\exists x\, P(x)$ diz: existe pelo menos um $x$ no conjunto para o qual $P(x)$ vale. Existe um número primo maior que um milhão é uma sentença existencial. Algum número natural é par é uma sentença existencial.

any(is_prime(x) for x in range(10**6, 10**7))   # ∃x ∈ [10⁶, 10⁷): primo(x)

Os dois quantificadores são duais — cada um é a negação do outro com o predicado invertido.

Arraste o testador pelos elementos. Observe o contador universal ficar falso na primeira vez que toca uma forma vazia, e permanecer falso; observe o contador existencial ficar verdadeiro na primeira vez que toca uma forma preenchida, e permanecer verdadeiro. O universal se importa se algum elemento falha. O existencial se importa se algum elemento tem sucesso. São sensíveis a tipos opostos de evidência.

Essa sensibilidade importa para a economia de prova:

• Para sustentar um universal, é preciso percorrer todo elemento do conjunto. Frequentemente: infinitos.
• Para refutar um universal, basta um contraexemplo.
• Para sustentar um existencial, basta um exemplo.
• Para refutar um existencial, é preciso eliminar todo elemento do conjunto.

Universais são caros de provar e baratos de quebrar. Existenciais são o oposto.

§3. Domínio do discurso

Quando dizemos $\exists x\, (x^2 = 2)$, a sentença é verdadeira ou falsa? Depende. No conjunto dos racionais ($\mathbb{Q}$), é falsa — $\sqrt{2}$ não é racional. No conjunto dos reais ($\mathbb{R}$), é verdadeira. A mesma sentença, com a mesma sintaxe, troca de valor-verdade dependendo do conjunto sobre o qual interpretamos o quantificador.

Não há sentido perguntar existe $x$ tal que $P(x)$? sem antes responder $x$ percorre o quê?.

Em notação explícita, escrevemos:

A frase para todo $x$ real, $x^2 \geq 0$ torna o domínio explícito. Em código, é o iterável da compreensão:

all(x*x >= 0 for x in reals)   # 'reals' é o domínio

Trocar o domínio muda completamente a sentença. $\exists x\, (x + 1 = 0)$ é falsa em $\mathbb{N}$, verdadeira em $\mathbb{Z}$. O quantificador é uma máquina de varredura; o domínio é o que ele percorre.

§4. Variáveis ligadas e livres

A distinção entre variáveis livres e ligadas é fregeana (Begriffsschrift, 1879); o vocabulário livre/ligada se firmou com Hilbert e Quine.

Na sentença $\forall x\, P(x)$, o $x$ está ligado pelo quantificador. Substituir $x$ por outro símbolo (digamos $y$) — $\forall y\, P(y)$ — não muda nada. A variável ligada é interna ao quantificador; só importa que haja alguma variável servindo de placeholder.

Já em $P(x) \wedge Q(y)$ — sem quantificador — as variáveis $x$ e $y$ estão livres. A sentença não tem valor-verdade até que sejam fixadas. Funciona como predicado: precisa de input.

A regra prática: cada quantificador captura uma variável e deixa de ser livre. Como em programação:

def universal(predicate, domain):
    return all(predicate(x) for x in domain)
    #          ^^^^^^^^^^^^ x está ligada pela compreensão

Quando escrevemos $\forall x \, [P(x) \rightarrow Q(x, y)]$, o $x$ está ligado pelo $\forall$, mas $y$ continua livre — a sentença ainda depende do valor de $y$.

§5. Ordem dos quantificadores

Quando uma sentença mistura $\forall$ e $\exists$, a ordem em que aparecem decide o que ela significa. Trocar a ordem produz uma sentença diferente, com valor-verdade potencialmente diferente.

Compare:

Para todo natural $x$, existe um natural $y$ maior que $x$. Verdadeira: dado qualquer $x$, sempre podemos escolher $y = x + 1$.

Existe um natural $y$ maior que todo natural $x$. Falsa: nenhum natural é maior que todos os naturais — $\mathbb{N}$ é ilimitado superiormente.

A diferença não é estilística. Na primeira, o $y$ pode depender de $x$ — para cada $x$, escolhemos um $y$ diferente. Na segunda, o $y$ vem antes — é fixo, e depois desafiado por todo $x$. A ordem dos quantificadores determina o que depende do quê.

Na linguagem natural, a mesma ambiguidade aparece. Todo mundo ama alguém pode significar:

• $\forall x\, \exists y\, (\text{ama}(x, y))$ — cada pessoa tem alguém que ama (esse alguém varia)
• $\exists y\, \forall x\, (\text{ama}(x, y))$ — existe uma pessoa amada por todos

A primeira é trivial. A segunda é improvável. A linguagem natural deixa essa diferença para o contexto resolver. A lógica de predicados a fixa explicitamente.

§6. Negando quantificadores

Negar um quantificador é a regra estrutural por trás de todo não, isso está errado em prova matemática — e onde a intuição mais escorrega.

A negação de todo $x$ satisfaz $P$ parece ser todo $x$ falha $P$. Não é. A negação correta é existe pelo menos um $x$ que falha $P$. Para refutar um universal, basta um contraexemplo.

Já a negação de existe um $x$ que satisfaz $P$ parece ser existe um $x$ que falha $P$. Também não é. A negação correta é todo $x$ falha $P$. Para refutar um existencial, é preciso eliminar todos os elementos do conjunto.

Em forma simbólica:

negar "todo x satisfaz P" equivale a "existe x que falha P"

negar "existe x que satisfaz P" equivale a "todo x falha P"

A regra é "inverta o quantificador e empurre a negação para dentro" — generalização das leis de De Morgan: o universal $\forall$ é a versão infinita da conjunção $\wedge$; o existencial $\exists$ é a versão infinita da disjunção $\vee$. A regra da negação se preserva — trocar o quantificador é o análogo de trocar o conectivo.

Note que a conversão é não-congruente: $\neg$ move de fora do quantificador para dentro do predicado, e o próprio quantificador muda. Duas edições simultâneas — reorganização estrutural, não reescrita sinal-por-sinal. Faz parte do que torna o movimento escorregadio.

Qualquer pessoa que já tenha dito nem todo mundo tem X querendo dizer alguém não tem X executou esta regra. Do mesmo modo, quem disse ninguém tem X querendo dizer todos carecem de X executou a outra. A regra já operava; a versão formal apenas dá nome.

§7. Ler matemática é metade do trabalho

Sentenças matemáticas reais unem quantificadores e conectivos, às vezes profundamente.

Tome um exemplo familiar:

todo número primo maior que 2 é ímpar

Percorra a estrutura. O movimento externo é universal: para todo $x$. O corpo é uma condicional: se $x$ é primo e maior que 2, então $x$ é ímpar. A hipótese ela mesma é uma conjunção de duas sentenças mais simples sobre $x$. O todo se lê como: escolha qualquer número; se é tanto primo quanto maior que 2, então é também ímpar.

Essa forma — sentença universal, corpo condicional, hipótese estruturada — aparece na maioria dos teoremas matemáticos.

all(is_odd(x) for x in naturals if is_prime(x) and x > 2)

Suponha que buscamos refutar a sentença. A refutação seria existe um $x$ que é primo, maior que 2, e par. Para a refutação ser válida, precisaríamos encontrar um único número com essas características, o que é impossível — afinal, tal número não existe. A sentença original permanece válida.

Note a assimetria. Sustentar um universal exige percorrer o conjunto inteiro — todo primo maior que 2, infinitos deles. Refutar exige um contraexemplo.

Essa assimetria é a razão pela qual a matemática é cheia de teoremas que parecem modestos mas levaram séculos para provar. Todo mapa pode ser colorido com quatro cores de modo que regiões adjacentes não compartilhem cor soa como uma sentença pequena. É uma afirmação universal sobre todo mapa possível, e levou 124 anos da conjectura (Francis Guthrie, 1852) à prova (Kenneth Appel e Wolfgang Haken, 1976) — uma demonstração que no final exigiu análise computacional de 1.936 configurações redutíveis. O quantificador universal é implacável.

Ler sentenças matemáticas bem significa fazer o que acabamos de fazer: identificar o quantificador externo, encontrar o corpo sobre o qual ele opera, reconhecer se o corpo é condicional ou conjunção ou ambos, e perguntar o que refutaria a sentença. Com esses quatro movimentos, a maior parte da matemática publicada se torna analisável. Sem eles, permanece opaca.

§8. A linguagem que a matemática usa

Os mesmos objetos, em quatro registros:

• Linguístico: proposições, conectivos, quantificadores, as regras que obedecem
• Simbólico: $\neg$, $\wedge$, $\vee$, $\rightarrow$, $\leftrightarrow$, $\forall$, $\exists$, e as equivalências entre eles
• Gráfico: mundos, conjuntos, a assimetria visual entre $\forall$ e $\exists$
• Computacional: booleanos, tuplas, uniões, funções, all() e any()

Cada registro permite pensar o mesmo objeto de perspectivas diferentes. A linguagem formal não é uma camada técnica separada adicionada por cima da matemática — é aquilo em que a matemática é escrita. Enunciados de teorema, provas, definições — tudo é construído dessas peças.

Os quatro objetos — proposição, conectivo, quantificador, condicional — reaparecem em todo módulo seguinte. Subconjunto é a condicional: $A \subseteq B$ é $\forall x\, (x \in A \rightarrow x \in B)$. Uma função é um par universal-existencial com unicidade, $\forall \exists!$. Uma transformação linear preserva estrutura por condições universais. A condicional retorna em todos eles.