Lógica proposicional

Conectivos e a condicional: como proposições atômicas se combinam em moleculares.

A lógica é a gramática do raciocínio — assim como uma língua tem regras que determinam quais sentenças são bem-formadas, a lógica determina quais inferências são válidas independentemente do conteúdo. A lógica clássica fixa o terreno semântico: toda proposição é verdadeira ou falsa, nunca ambas. A lógica proposicional é a primeira camada que opera dentro desse compromisso — tratamos cada proposição como uma unidade indivisível e estudamos como elas se combinam em proposições maiores via conectivos.

§0. Onde a intuição falha

§1. A lógica lida somente com proposições

Trabalhamos com um tipo específico de enunciado: proposições — sentenças que podem ser avaliadas como verdadeiras ou falsas, mas nunca ambas. O sol está brilhando é uma proposição: existe um fato sobre o mundo que decide. 7 é maior que 3 é uma proposição: existe um fato matemático que decide.

Por outro lado, Feche a porta não é uma proposição. É uma ordem. Uma ordem pode ser obedecida ou ignorada, útil ou inconveniente, mas não pode ser verdadeira ou falsa. Que horas são? é uma pergunta; mesmo problema. Que filme incrível! também não, porque depende do gosto subjetivo de quem avalia.

Vale separar sentença de proposição. A sentença é o veículo: a frase, as palavras, a forma escrita ou falada. A proposição é a carga: a afirmação sobre o mundo, independente de como é expressa. Veículos diferentes podem carregar a mesma carga. Está chovendo e It is raining são sentenças distintas — em línguas distintas — que expressam a mesma proposição. O sol está brilhando e O sol emite luz neste momento são sentenças distintas que expressam a mesma proposição. Quando dois falantes concordam sobre o conteúdo apesar de discordarem sobre a formulação, é a proposição que coincide. A lógica trabalha com proposições; sentenças são o meio pelo qual chegamos a elas, mas o objeto formal é o conteúdo.

Proposições vêm em duas escalas. As atômicas são indivisíveis do ponto de vista lógico — está chovendo, $2 + 2 = 4$. As moleculares são construídas combinando atômicas com conectivos — está chovendo e estou em casa, se chove, então a rua fica molhada. Passar de umas para as outras é o que os conectivos fazem.

Os compromissos da lógica clássica

Todo o trabalho que se segue opera dentro de três compromissos. Eles não são demonstráveis dentro do sistema — são as regras do jogo.

Mundos

O valor-verdade de uma proposição depende do caso em que a avaliamos. Está chovendo é verdadeiro em alguns casos e falso em outros. Brasília é a capital do Brasil é verdadeiro no nosso mundo. Mas se voltássemos no tempo, a mesma proposição seria falsa — afinal, no passado a capital do Brasil realmente foi o Rio, e Brasília não havia sido construída.

Chamamos cada caso que estamos avaliando de mundo. Um mundo fixa os fatos: o que está acontecendo, o que não está, quais objetos existem. Uma proposição, portanto, tem seu valor-verdade determinado pelo mundo em que a avaliamos.

O valor-verdade segue o mundo, mas a sentença não. A maior parte das confusões lógicas vem de colapsar a proposição e o mundo em que ela é avaliada.

§2. Conectivos

Conectar sentenças expande o alcance da lógica. São cinco conectivos básicos. Três — não, e, ou — espelham palavras da linguagem natural quase sem distorção. Os outros dois, a condicional e a bicondicional, exigem mais cuidado: é onde a precisão lógica se separa do uso cotidiano.

Negação

Está chovendo e NÃO está chovendo são opostos: uma é verdadeira exatamente quando a outra é falsa. Esse é o padrão da negação — inverte o valor-verdade da sentença que modifica.

Representamos com o símbolo $\neg$, uma barra de cancelamento estilizada. $\neg P$ lê-se "não $P$": é falso quando $P$ é verdadeiro, e verdadeiro quando $P$ é falso.

not p   # ¬P

Conjunção

Quando dizemos Fui à padaria E comprei pão, estamos afirmando duas coisas:

• Fui à padaria
• Comprei pão

Se em algum momento constatarmos que não fomos à padaria, a sentença inteira deixa de ser verdadeira — mesmo que tenhamos de algum modo comprado o pão. Esse é o padrão da conjunção: o "E" exige que ambas as partes sejam verdadeiras.

Escrevemos $P \wedge Q$ — verdadeiro somente quando $P$ e $Q$ são ambos verdadeiros. O símbolo $\wedge$ ecoa um $A$ sem a barra horizontal: o conectivo com forma de A é o and.

p and q   # P ∧ Q

Em teoria dos tipos, $\wedge$ é uma tupla — a prova de $P \wedge Q$ é o par (p, q), onde p é uma prova de $P$ e q é uma prova de $Q$:

proof: tuple[P, Q] = (p, q)   # prova de P ∧ Q

Disjunção

Quando dizemos Está chovendo OU a rua está molhada, estamos afirmando que pelo menos uma destas é verdadeira:

• Está chovendo
• A rua está molhada

Basta uma das duas para a sentença inteira valer. Esse é o padrão da disjunção: o "OU" exige pelo menos uma das partes.

Detalhe: na linguagem natural, ou às vezes significa exatamente um ("café ou chá?"), mas em lógica significa pelo menos um, incluindo o caso em que ambos valem.

Escrevemos $P \vee Q$ — verdadeiro sempre que ao menos um dos dois é verdadeiro; falso só quando ambos são falsos. O símbolo $\vee$ é $\wedge$ invertido, da raiz latina vel (ou inclusivo).

p or q   # P ∨ Q

Condicional

A condicional é escrita com a seta $\rightarrow$ (também $\Rightarrow$). O visual é direto: uma direção, de antecedente para consequente. $P \rightarrow Q$ lê-se se $P$, então $Q$.

É falsa em um único caso — $P$ verdadeiro e $Q$ falso — e verdadeira em todos os outros. As duas linhas em que $P$ é falso são contraintuitivas: a condicional vale independentemente de $Q$. Por que, é o assunto da próxima seção.

not p or q   # P → Q  (equivalente a ¬P ∨ Q)

Bicondicional

Quando ambas $P \rightarrow Q$ e $Q \rightarrow P$ valem, escrevemos $P \leftrightarrow Q$ — $P$ se e somente se $Q$. A bicondicional é a conjunção das duas direções: $(P \rightarrow Q) \wedge (Q \rightarrow P)$. Verdadeira quando $P$ e $Q$ têm o mesmo valor-verdade; falsa quando diferem. O símbolo é uma seta dupla, indicando direção nos dois sentidos — graficamente honesto sobre o que significa.

p == q   # P ↔ Q

Definições matemáticas são quase sempre bicondicionais: um inteiro é primo se e somente se é maior que 1 e divisível apenas por 1 e por si mesmo. A bicondicional é o conectivo da definição — exige que as duas sentenças se sustentem ou caiam juntas.

A tabela-verdade

Uma tabela-verdade lista cada combinação possível de valores-verdade das entradas e mostra o que cada composta avalia. Para duas entradas, quatro linhas. Para três, oito. Para $n$, $2^n$.

A tabela-verdade é o modo de força bruta de verificar o que qualquer composta diz.

§3. Verdade vacuosa

A condicional tem duas linhas estranhas — as duas em que $P$ é falso:

Quando $P$ é falso, $P \rightarrow Q$ é verdadeira independentemente de $Q$. A forma da convenção fica óbvia num único exemplo.

Para todo número natural $n$, se $n$ é par, então $n^2$ é par.

Essa é uma afirmação universal verdadeira.

• Seja $n$ = 3
• $n$ é par? Falso
• $n^2$ é par? Falso (9 é ímpar)

A sentença inteira "se $n$ é par, então $n^2$ é par" deveria ser verdadeira sobre 3 — porque a regra não se aplica a 3. Ela não diz nada sobre números ímpares. Se a condicional com antecedente falso fosse ela mesma falsa, todo número ímpar contaria como contraexemplo — e toda afirmação universal da matemática quebraria no primeiro caso negativo.

A convenção, portanto, é que quando $P$ é falso, $P \rightarrow Q$ não diz nada nem a favor nem contra. É vacuosamente verdadeira — verdadeira porque nada foi acionado.

A condicional afirma uma promessa. Se chover, levo guarda-chuva só é quebrada se chover E eu sair sem guarda-chuva. Se não chover, a promessa nunca foi acionada — e portanto não foi violada.

Há outra maneira de ver, que antecipa a conexão com conjuntos:

Se lemos $P$ como "o conjunto de mundos onde $P$ vale" e $Q$ da mesma forma, então $P \rightarrow Q$ diz: todo elemento que está em $P$ também está em $Q$. Essa é a relação de subconjunto. E o conjunto vazio é subconjunto de todo conjunto. Logo, quando $P$ é falso ($P$ é o conjunto vazio), $P \subseteq Q$ vale trivialmente — não há nada a verificar.

A condicional como função

A condicional é onde a similaridade entre lógica e código aparece mais diretamente. Uma prova de $P \rightarrow Q$ é uma função que transforma evidência para $P$ em evidência para $Q$.

def implies[P, Q](p: P) -> Q: ...   # condicional como função

Uma prova de "se está chovendo, então a rua está molhada" é um procedimento: dada uma confirmação de que está chovendo, produz-se uma confirmação de que a rua está molhada. Modus ponens — a regra que permite concluir $Q$ a partir de $P \rightarrow Q$ e $P$ — é literalmente aplicação de função:

q = implies(p)   # P → Q aplicado a P produz Q

Daí decorre uma leitura que reaparece em fundamentos da matemática: provar é construir, não verificar. Provar $P \rightarrow Q$ não é checar uma tabela-verdade — é exibir a função, a receita que recebe $P$ e devolve $Q$. A prova é o programa. (Essa formulação tem raiz na interpretação BHK — Brouwer-Heyting-Kolmogorov — da lógica intuicionista, refinada na correspondência de Curry-Howard e na teoria de tipos de Martin-Löf. Numa leitura estritamente clássica, a tabela-verdade basta; a leitura construtiva é o que dá à equivalência lógica-código sua força computacional.)

O caso vacuoso tem um análogo em programação. Se $P$ é o tipo vazio — um tipo sem valores — então uma função $P \rightarrow Q$ é satisfatível para qualquer $Q$, porque nenhum chamador pode produzir um valor de $P$ para testar a função. A função é definida mas nunca executa. A promessa é mantida porque a condição para invocá-la nunca surge.

§4. Negação

Negar uma proposição atômica é simples — inverte o valor-verdade. Negar uma composta é onde o erro mora. A regra geral: a negação não se distribui ingenuamente sobre as partes; ela empurra para dentro, trocando cada conectivo pelo seu dual.

Conjunção e disjunção

Negar uma sentença composta com $\wedge$ ou $\vee$ não é negar suas partes — é trocar o conectivo.

A regra estrutural: a negação distribui sobre os dois conectivos, trocando $\wedge$ por $\vee$ e vice-versa. Essas são as leis de De Morgan, nomeadas em homenagem ao lógico britânico Augustus De Morgan (1806–1871). Aparecem em prova matemática constantemente — toda vez que se nega uma sentença composta, é uma delas que está em ação.

A condicional

A condicional segue a mesma lógica. O único caso em que $P \rightarrow Q$ é falso é a segunda linha: $P$ verdadeiro, $Q$ falso. Logo a negação é exatamente esse caso:

negar uma condicional é afirmar o antecedente e negar o consequente

Leia: $P$ é verdadeiro e $Q$ é falso. Essa é a única combinação que quebra a promessa. Note que a conversão é congruente — a ordem dos símbolos coincide com a ordem das palavras, e cada peça da negação mapeia uma peça da original.

Um erro padrão — comum o bastante para ser quase universal em provas — é pensar que a negação de $P \rightarrow Q$ é $Q \wedge \neg P$. Não é. Essa é a negação de $Q \rightarrow P$, que é a conversa da original, uma proposição diferente.

§5. Conversa, inversa, contrapositiva

Três sentenças derivadas vivem ao redor de toda condicional, e causam confusão sistemática.

Essa é a fonte de uma quantidade absurda de equívocos, tanto em conversas casuais quanto no debate público. Quando ouvimos se você estuda, você passa, frequentemente deslizamos para se você passou, deve ter estudado (a conversa) ou se você não estuda, não vai passar (a inversa). Ambos os movimentos inventam uma restrição que a sentença original nunca ofereceu. Estudar pode ser suficiente para passar, mas não é necessariamente a única forma. Ela nada diz sobre o que acontece se não estudamos.

A contrapositiva é a única troca que preserva significado. Se você estuda, você passa e se você não passou, você não estudou falham e valem nos mesmos casos. Matemáticos dependem disso constantemente: quando uma prova direta de $P \rightarrow Q$ é difícil, às vezes provar $\neg Q \rightarrow \neg P$ é fácil, e as regras garantem que é a mesma sentença.

Note a conversão ao ler a contrapositiva: a ordem se inverte. Na original, $P$ vem primeiro e $Q$ vem segundo. Na contrapositiva, $Q$ vem primeiro (negado) e $P$ vem segundo (negado). Duas inversões — ordem e polaridade. A inversão dupla é o que torna a contrapositiva equivalente. Inversões simples não preservam.

§6. De volta às cartas

As quatro cartas agora fazem sentido.

Se uma carta tem uma vogal de um lado, tem um número par do outro.

Traduzindo: $P$ é vogal deste lado, $Q$ é número par do outro lado. A regra é $P \rightarrow Q$. A única condição de falha: $P$ verdadeiro, $Q$ falso — uma carta com uma vogal de um lado e um número ímpar do outro. Esse é o único modo de a regra estar errada.

A taxa de erro alta — em torno de 90% na versão abstrata original de Wason (1968) — vem de uma heurística profundamente intuitiva mas incorreta: procuramos cartas que coincidem com a forma da regra (vogal e número par) em vez de cartas que poderiam falsificá-la. A falsificação se importa apenas com a combinação única de $P$ verdadeiro e $Q$ falso. Todo o resto ou confirma a regra ou não tem incidência sobre ela.

Em estudos posteriores, Jonathan Evans nomeou o mecanismo de matching bias — a tendência de selecionar exatamente os itens mencionados na regra, vogal e par, em vez dos que poderiam refutá-la. Em versões com conteúdo familiar (regras sobre idade e bebida alcoólica, por exemplo), a taxa de acerto sobe muito; é a forma abstrata que derruba.

O enigma das cartas é $P \rightarrow Q$ em letras e números — e a maioria das primeiras tentativas falha porque o raciocínio cotidiano não é calibrado para procurar falsificação.

Próximo passo

A próxima camada — lógica de predicados — abre as proposições e olha para dentro. Aparecem variáveis, predicados, e quantificadores que percorrem conjuntos inteiros.