Notas

Tautologia é uma fórmula cuja tabela de verdade só apresenta o valor V.

Exemplo: .

Contradição é uma fórmula cuja tabela de verdade só apresenta o valor F.

Exemplo: .

implica tautologicamente se é uma tautologia. Escreve-se .

Exemplo: .

é tautologicamente equivalente a se Q é tautologia. Escreve-se .

Exemplo: .

implicam tautologicamente se é tautologia.

Teorema: implicam tautologicamente sse quando os valores de verdade de são todos V, o de também é V.

Argumento é um conjunto de premissas-- -- e uma conclusão, . O argumento é válido se

isto é, se implicam tautologicamente .

Para estabelecer a validade de um argumento recorremos a uma demonstração (ou prova). Um contra-exemplo mostra que um dado argumento não é válido. Um contra-exemplo é uma atribuição de valores de verdade às letras proposicionais de forma a que as premissas sejam todas V e a conclusão seja F.

Para construir demonstrações necessitamos de regras de inferência.

Regra da Tautologia--T Uma fórmula pode deduzir-se das fórmulas se .

Em particular, se é uma tautologia, pode deduzir-se do conjunto vazio.

Alguns casos particulares que saem desta regra (ver também lista das tautologias úteis):

R1 , conclusão: .

R2 , conclusão: .

R3 , conclusão: .

R4 , conclusão: . , conclusão: .

Demonstração formal (versão 1) de com premissas é uma sequência finita de fórmulas , tal que , e é uma premissa ou se pode deduzir dos 's anteriores usando uma regra de inferência.

Notação:

Regra das Premissas--P Uma premissa pode ocorrer em qualquer linha de uma prova.

Nota: De uma "regra de inferência" falsa (ie, que não preserve a verdade) pode deduzir-se uma contradição. De uma contradição tudo se pode deduzir.

Regra da Prova Condicional--PC Se se pode deduzir de e de um conjunto de premissas , então pode deduzir-se de . Isto é, se então .

Prova formal (versão 2) de a partir das premissas é uma sequência finita de pares ordenados onde cada é um conjunto de fórmulas e cada é uma fórmula, verificando:

1. .
2. Cada é uma premissa original ou pode ser deduzida das 's anteriores usando uma regra de inferência.
3. Se é uma premissa então .
4. Se se deduz das anteriores 's usando uma regra de inferência então é definido pela regra ( é o conjunto de fórmulas de que depende).

Regra da Prova Indirecta--PI Se se pode deduzir de um conjunto de premissas e de então pode deduzir-se de .

Em símbolos: Se então .

Cábula Útil para fazer demonstrações:

1. Para provar provar separadamente e e usar
2. Para provar usar como premissa, deduzir e usar a regra PC.
3. Para provar
   1. Provar e usar ou provar e usar .
   2. Tomar como premissa, deduzir , usar regra PC para obter . Usar depois
4. Para provar provar e e usar

   se estas falharem...

5. Prova indirecta: Para provar tomar como premissa e tentar deduzir uma contradição.
6. 1. Para provar tente-se encontrar uma fórmula tal que se deduzam e . Depois usar a regra
   2. Para provar a partir de provar e e usar a regra correspondente à tautologia 8 para obter .