Lógica Proposicional

Uma fórmula proposicional é uma FBF: cadeia de átomos e conectivos ¬, ∧, ∨, →, ↔ montada pelas regras de formação. Uma valoração escolhe V ou F para cada átomo; a fórmula herda o valor pelas regras dos conectivos.

Tabelas, reescritas e conjuntos de conectivos deste tópico — e a lógica de predicados, a consequência Γ⊨φ e os sistemas dedutivos nos tópicos seguintes — partem dessa valoração.

As páginas se agrupam em quatro blocos. O primeiro monta a FBF e classifica a fórmula em todas as valorações: tautologia, contradição, contingência e φ⇒ψ.

O segundo enumera as 2ⁿ combinações dos átomos distintos e lê a função booleana na coluna da fórmula.

O terceiro troca φ por ψ que coincide em toda valoração: contraposta de →, De Morgan, e a negação de "exatamente um".

O quarto testa se um conjunto C de conectivos escreve toda função {V,F}ⁿ→{V,F}. O critério negativo é o invariante na linha toda falsa.

Sintaxe e Semântica define tautologia, contradição e o traço φ⇒ψ. Tabelas Verdade monta as 2ⁿ linhas e lê esses rótulos na coluna da fórmula.

Últimas colunas iguais linha a linha está em Tabelas Verdade. Escolher a forma equivalente — p→q ≡ ¬p∨q ≡ ¬q→¬p, e não a recíproca q→p — está em Equivalências Lógicas.

Reconhecer a fórmula a partir de uma tabela já preenchida está em Tabelas Verdade. Decidir se C gera toda função booleana, e reprovar {NIMP}, {NEQ} e {NIMP,NEQ} pela preservação do falso, está em Conectivos Funcionalmente Completos.