Teoremas de Compacidade e Löwenheim-Skolem

Um problema de sim ou não é decidível quando existe um procedimento mecânico que, para toda entrada, termina e responde corretamente. A entrada deste tópico é uma fórmula: validade pergunta se ela vale em toda interpretação; satisfatibilidade, se vale em alguma.

Tabela, enumeração de provas e reconhecimento de fórmulas deste tópico — e sintaxe, completude e prova automática nos tópicos vizinhos — partem dessa exigência de parada.

As páginas se agrupam em quatro blocos. O primeiro fixa o critério de decisão e reduz validade de φ a insatisfatibilidade de ¬φ.

O segundo esgota as 2ⁿ valorações proposicionais. A última coluna toda V decide tautologia; o teste de satisfatibilidade em ¬φ responde a mesma pergunta.

O terceiro trata da primeira ordem: não há lista finita de estruturas, e nenhum procedimento decide validade de uma sentença qualquer.

O quarto enumera provas quando elas existem e reconhece fórmulas por análise da cadeia. O enumerador pode não parar no inválido; o reconhecedor sintático pára nas duas saídas.

Tabelas Verdade preenche as colunas de uma fórmula proposicional. Ler o término das 2ⁿ linhas como algoritmo de tautologia está em Decidibilidade.

Completude liga ⊨φ a ⊢φ. O enumerador de derivações que isso autoriza, e a falta de parada quando prova não existe, estão em Decidibilidade.

Sintaxe da Lógica de Primeira Ordem define termo e fórmula. O procedimento que, dada uma cadeia, pára com pertinência ou não está em Decidibilidade.

Classificar sentenças arbitrárias de primeira ordem como válidas ou inválidas está em Decidibilidade. Não existe procedimento que termine em todo caso.