Chegamos, em nosso estudo da lógica, a um ponto de inflexão, porque aqui iniciamos a revisão dos Sistemas Dedutivos da Lógica Proposicional. Aqui é onde tudo o que vimos começa a se tornar operativo e o verdadeiro espírito da lógica vem à luz, pois estudaremos a essência das demonstrações. Neste ponto, assume-se que você já viu como escrever expressões e entende sobre o que se trata a lógica proposicional; e, se não estiver totalmente claro, é recomendável que reveja as aulas anteriores a esta.

Feito isso, o que se segue agora é revisar a forma como as expressões da lógica proposicional se relacionam entre si para formar uma dedução. O mecanismo através do qual essas relações são construídas é o sistema dedutivo formal.

O que é um Sistema Dedutivo Formal?

Os sistemas dedutivos formais, ou sistemas de cálculo dedutivo, têm três componentes elementares:

1. Uma Linguagem Formal.
2. Um Esquema Axiomático.
3. Regras de Inferência Elementares.

Já revisamos tudo relacionado às linguagens formais. Agora, é hora de introduzir os esquemas axiomáticos e as regras de inferência elementares.

Para a construção do sistema dedutivo do cálculo proposicional, começaremos montando o sistema dedutivo a partir dos Axiomas de Łukasiewicz, e como regra de inferência elementar usaremos o Modus Ponens.

Os Axiomas de Łukasiewicz para a Lógica Proposicional

Se \alpha, \beta e \gamma são expressões do cálculo proposicional, então os seguintes são axiomas do cálculo proposicional:

O Modus Ponens: O motor dedutivo do cálculo proposicional

Se \alpha e \beta são expressões válidas do cálculo proposicional, então o modus ponens estabelece que a partir de \alpha e (\alpha \rightarrow \beta) se deduz \beta. Em forma de raciocínio, isso se escreve da seguinte maneira:

Aqui, o Modus Ponens é representado entre os passos (1) e (2) através da notação “MP(1,2)”, e a síntese de tudo isso se representa através da notação:

Portanto \{\alpha, (\alpha \rightarrow \beta)\}\vdash \beta

Em breve veremos que, a partir dos axiomas de Łukasiewicz e do Modus Ponens, podem ser construídas todas as técnicas de dedução do cálculo proposicional, que sintetizam as regras básicas do raciocínio usual e servem de base para a lógica clássica.

Raciocínios, teoremas e premissas

Nos sistemas dedutivos da lógica proposicional são executados raciocínios (ou deduções), e esses são qualquer sucessão de expressões onde cada uma delas é ou uma premissa ou uma expressão obtida a partir das premissas, utilizando apenas os axiomas de Łukasiewicz e o modus ponens. Um teorema é o resultado de uma dedução sem premissas. Uma premissa pode ser qualquer expressão que não seja um axioma nem se deduza a partir deles. Em geral, quando temos um conjunto de premissas \Gamma e uma expressão \alpha que é obtida utilizando algum elemento de \Gamma, os axiomas e o modus ponens, escreve-se “\Gamma \vdash \alpha” e dizemos que

de \Gamma deduz-se \alpha

Se \Gamma é um conjunto vazio, então em vez de escrever “\emptyset\vdash \alpha” escreve-se “ \vdash \alpha . ” Isso se lê “\alpha é um teorema”. Essa forma de representar os teoremas pode ser estendida para a representação dos axiomas de modo que, se \alpha e \beta e \gamma são expressões, então os axiomas de Łukasiewicz podem ser escritos da seguinte forma

É a partir disso que se diz que os axiomas são afirmações evidentes por si mesmas, ou que os teoremas são expressões que se inferem a partir do vazio, ou que axiomas e teoremas são propriedades do cálculo proposicional.

Como se executa uma demonstração na lógica proposicional?

Neste ponto, deixaremos de falar de teoria e passaremos à prática. E sobre a execução de uma demonstração pode-se dizer muitas coisas; mas, por mais que se digam coisas brilhantes sobre os sistemas dedutivos e a lógica proposicional, e todas sejam entendidas, isso não implicará necessariamente que se estejam desenvolvendo as competências necessárias para executar uma demonstração. Por isso, para ensinar como fazer demonstrações, revisaremos a demonstração de um teorema simples.

Teorema

Se \alpha é uma expressão da lógica proposicional, então se cumpre que

\vdash (\alpha\rightarrow \alpha)

Demonstração

Portanto \vdash (\alpha\rightarrow\alpha)

Fim da demonstração.

Como se pode ver, nos sistemas dedutivos e na lógica proposicional, as demonstrações não são triviais, mas uma vez construídas são fáceis de replicar.

Agora, antes de nos lançarmos diretamente a fazer deduções com essas técnicas, primeiro vamos desenvolver algumas propriedades e definições que serão extremamente úteis para esta tarefa, pois, se raciocinarmos apenas com isso, enfrentaremos terríveis problemas.

O conceito de equivalência provada

Se \alpha e \beta são quaisquer expressões e se cumpre ao mesmo tempo que \{\alpha\}\vdash \beta e \{\beta\} \vdash \alpha, então se diz que \alpha e \beta são provadas equivalentes, e escreveremos \alpha \dashv \vdash \beta. Isso é resumido simbolicamente como:

\left(\{\alpha\}\vdash\beta \wedge \{\beta\}\vdash\alpha \right) \Leftrightarrow \left(\alpha\dashv\vdash\beta\right)

Isso se lê: de \alpha se infere \beta, e de \beta se infere \alpha se, e somente se, \alpha e \beta são provadas equivalentes.

Isso é uma meta-propriedade da lógica proposicional

O (meta)Teorema da Dedução

Se \alpha e \beta são expressões do cálculo proposicional, e \Gamma é um conjunto de premissas; então temos que, se de \Gamma \cup \{\alpha\} se deduz \beta, então, a partir de \Gamma, deduz-se (\alpha \rightarrow \beta). Simbolicamente, isso seria expresso como:

\left(\Gamma \cup \{\alpha\}\vdash \beta \right) \Rightarrow \left( \Gamma\vdash(\alpha\rightarrow\beta)\right)

Demonstração:

Para que se cumpra \Gamma \cup \{\alpha\}\vdash \beta, é necessário ter uma dedução da seguinte forma

Portanto \Gamma\cup\{\alpha\} \vdash \beta

Para que isso seja possível, é necessário que pelo menos uma das expressões \gamma_1, \cdots \gamma_n,\overline{\gamma_1},\cdots,\overline{\gamma_m} seja da forma (\alpha\rightarrow \beta), mas todas essas linhas envolvem apenas elementos de \Gamma e os axiomas de Łukasiewicz em sua dedução, portanto, deve-se cumprir que \Gamma\vdash (\alpha \rightarrow \beta). Fica, portanto, demonstrado o teorema

Fim da demonstração.

O Recíproco do Teorema da Dedução

Nas mesmas condições que o teorema da dedução, teremos que

\left(\Gamma\vdash(\alpha \rightarrow \beta)\right) \Rightarrow \left( \Gamma \cup \{\alpha\}\vdash \beta \right)

Demonstração:

Se cumpre que \Gamma\vdash (\alpha\rightarrow \beta), então há uma dedução da seguinte forma

Agora, se adicionarmos \alpha como premissa a esse raciocínio, então teremos as seguintes linhas

Portanto \Gamma \cup \{\alpha\} \vdash \beta

Que é o que se queria demonstrar.

Fim da demonstração.

Deduções sobre Expressões e Deduções sobre Deduções

Demonstrações como a que fizemos antes para chegar ao resultado \vdash (\alpha\rightarrow \alpha) são casos de deduções baseadas em expressões, pois cada passo contém uma expressão específica. De forma análoga, é possível fazer deduções baseadas em outras deduções, onde cada passo é uma dedução por si só. Na prática, ambas são feitas de forma similar, mas a segunda permite o uso do teorema da dedução e seu recíproco, dando grande flexibilidade à técnica de raciocínio. Para ver isso, demonstremos novamente que \vdash (\alpha \rightarrow \alpha), mas agora usando deduções em vez de expressões. Uma alternativa para isso é a seguinte:

Observe que este raciocínio não é mais curto que o anterior, mas muito mais fácil de realizar. Basta usar o teorema da dedução, seu recíproco e o esquema axiomático A1 para construir a demonstração.

Na aparência, no desenvolvimento que acabamos de fazer, utilizamos apenas um axioma de Łukasiewicz e nos esquecemos de outros axiomas e do modus ponens. Isso significa que, ao raciocinarmos dessa forma, nos esquecemos dos outros axiomas e do modus ponens? A resposta é sim e não. Podemos fingir que esquecemos de alguns axiomas e do modus ponens, apenas porque não os estamos usando explicitamente. No entanto, deve-se lembrar que tanto o teorema da dedução quanto seu recíproco são consequências dos axiomas de Łukasiewicz e do modus ponens, o que implica que, ao fazer uso deles, estamos fazendo um uso implícito dos mesmos.

Regra de Monotonia

Se \tau é um teorema, então se terá que, dada qualquer expressão \beta, se cumprirá que

\{\beta\}\vdash\tau

Essa é uma regra muito fácil de provar, pois sendo \tau um teorema, se cumpre que \vdash \tau. Ou seja, existe um raciocínio que, sem a necessidade de adicionar premissas, leva à expressão \tau, então adicionar uma expressão adicional às premissas (vazia) não fará diferença.

De forma similar, pode-se apresentar o seguinte resultado: se de um conjunto de premissas \Gamma se infere \gamma, então se cumpre que

\Gamma\cup\{\alpha\}\vdash\gamma

Onde \alpha é uma expressão qualquer.

Síntese e Reflexões sobre Sistemas Dedutivos e a Lógica Proposicional

Quando fornecemos à linguagem da lógica proposicional uma regra de inferência e expressões básicas: O Modus Ponens e os Axiomas de Łukasiewicz, o que fazemos é análogo a montar uma “máquina dedutiva” e um “motor que a faz entrar em movimento”. A partir daí, as regras básicas de dedução começam a surgir naturalmente, e começaremos a revisá-las nas entregas imediatamente após esta.

Outro detalhe importante. As expressões da lógica proposicional são, na verdade, meta-expressões da linguagem de dois símbolos que vimos antes. Lembremos que a utilidade dessas meta-expressões é que nos permitem substituir suas meta-variáveis por qualquer expressão da linguagem para obter uma nova que satisfaça tal estrutura. Quando dotamos a linguagem da lógica proposicional de esquemas axiomáticos e regras de inferência, construímos os Sistemas Dedutivos da lógica proposicional, que permitem gerar deduções que conectam expressões. Como resultado, temos um esquema dedutivo capaz de englobar infinitas deduções: todas as que podemos obter substituindo meta-variáveis pelas expressões que quisermos. O poder da lógica se revela, na verdade, quando nos damos conta de que, além dessas expressões da linguagem de dois símbolos que utilizamos no início, podemos substituir por expressões da nossa língua usual.