Introdução e Eliminação de Conjunções e Disjunções

Uma das técnicas da lógica clássica é a introdução e eliminação de conectores e disjuntos. Embora essas técnicas sejam executadas de maneira mais ou menos intuitiva, sua justificativa não é inteiramente trivial, mas pode ser obtida a partir das regras da lógica proposicional que já demonstramos em aulas anteriores. Formalmente, as técnicas de introdução e eliminação de conectores e disjuntos são as seguintes:

E suas demonstrações a partir da lógica proposicional são mostradas a seguir:

∨-Introdução

∨-Eliminação

∧-Introdução

∧-Eliminação

Técnicas de Contradições e Tautologias

Regra do Terceiro Excluído ou Tautologia (tau)

Outra característica notável da lógica clássica é a propriedade do terceiro excluído (tertium non datur). Estabelece que se existem duas afirmações onde uma nega a outra, então necessariamente uma das duas deve ser verdadeira; em outras palavras, a conjunção de duas afirmações em que uma nega a outra necessariamente forma uma tautologia. Formalmente, isso é expresso como:

\vdash (\neg\alpha \vee\alpha)

E sua demonstração é fácil de obter.

Outra maneira de enunciar o princípio do terceiro excluído é através da lei da não contradição, que estabelece que uma afirmação não pode ser verdadeira e falsa ao mesmo tempo e que é formalmente enunciada como:

\vdash \neg(\neg\alpha \wedge \alpha)

Esta propriedade não precisa de demonstração, não porque seja autoevidente por si mesma, mas porque é obtida diretamente aplicando a definição de conjunção ao princípio do terceiro excluído.

Regra da Contradição ou Princípio da Explosão

Outra propriedade conhecida da lógica clássica é o princípio da explosão, que geralmente é enunciado através da frase “de premissas contraditórias, qualquer coisa pode ser concluída”. Sua formulação é frequentemente apresentada de uma das duas maneiras a seguir:

\{(\neg\alpha \wedge \alpha)\}\vdash \beta

\{\alpha, \neg\alpha\}\vdash \beta

A demonstração desta regra é simples:

∨-Eliminação3

O modus ponens pode ser escrito de duas maneiras diferentes. Uma forma que já conhecemos é \{\alpha,(\alpha \rightarrow \beta)\}\vdash \beta. A outra é um pouco menos familiar:

\{\alpha\}\vdash\beta \; \wedge \; \vdash \alpha \; \Longrightarrow \; \vdash \beta

Focando nesta segunda forma, é possível visualizar uma expansão para esta regra que chamamos de ∨-Eliminação3, porque se assemelha a uma simplificação obtida a partir de uma disjunção. Diz-nos que se \gamma pode ser inferido a partir de \alpha e de \beta (ambos ao mesmo tempo) e ao mesmo tempo a disjunção entre \alpha e \beta é um teorema, então \gamma é um teorema. Isso é resumido formalmente da seguinte maneira:

\{\alpha\}\vdash\gamma\; \wedge \; \{\beta\}\vdash\gamma \; \wedge \; \vdash (\alpha \vee \beta) \Longrightarrow \vdash \gamma

A demonstração desta técnica da lógica clássica é a seguinte:

Prova por Casos (cas)

Outra técnica da lógica clássica é a prova por casos. Se uma expressão \beta pode ser inferida a partir de outra expressão \alpha e de sua negação, então a expressão \beta é necessariamente um teorema. Isso é representado formalmente como: \alpha \vdash \beta \; \wedge \; \neg\alpha \vdash \beta \Longrightarrow \vdash \beta. Sua demonstração é a seguinte:

\begin{array}{rll} (1) & \alpha \vdash \beta &; Premissa\\ (2) & \neg \alpha \vdash \beta &; Premissa \\ (3) & \vdash \alpha \vee \neg\alpha &; TAU \\ (4) & \vdash \beta &; \vee-Eliminação3(1,2,3) \end{array}

Redução ao Absurdo (absurdo)

Uma das técnicas mais utilizadas da lógica clássica em demonstrações, especialmente na matemática, é a redução ao absurdo. Esta consiste em que se uma contradição (uma afirmação e sua negação) é inferida a partir de uma expressão \alpha, então a negação de \alpha é uma tautologia. Formalmente, é expresso como: \{\alpha\}\vdash \beta \; \wedge \; \{\alpha\}\vdash \neg\beta \Longrightarrow \vdash \neg\alpha. E pode ser demonstrado através do seguinte raciocínio: