OBJETIVOS DE APRENDIZAGEM:
Ao final desta aula, o estudante será capaz de:

1. Compreender o conceito de indução sobre a complexidade das expressões.
2. Aplicar a indução matemática sobre a complexidade das fórmulas na lógica proposicional.
3. Compreender a demonstração por indução sobre a complexidade e como ela é aplicada na lógica proposicional.

ÍNDICE
INDUÇÃO SOBRE A COMPLEXIDADE
UM EXEMPLO SIMPLES: O TEOREMA DE SUBSTITUIÇÃO

Indução sobre a complexidade

Suponha que queremos provar que uma propriedade \mathcal{P} se cumpre para qualquer expressão F. Uma forma de demonstrar isso utilizando a variante da indução matemática conhecida como “indução sobre a complexidade das expressões”. Isso é feito através da seguinte série de passos:

• Primeiro mostramos que todas as expressões atômicas satisfazem essa propriedade (isso corresponde ao caso n=1 de uma indução tradicional).
• Depois, assumindo que se cumpre para expressões quaisquer F e G, provamos que, consequentemente, se cumpre para expressões da forma F\downarrow G; ou, de forma equivalente, para \neg F e algumas das seguintes: F\wedge G, F\vee G, F\rightarrow G.

Se conseguirmos fazer isso, então concluímos que a propriedade \mathcal{P} se cumpre para todas as expressões da lógica proposicional. Isso é o que chamamos de “indução matemática sobre a complexidade das expressões”.

Um Exemplo Simples: O Teorema de Substituição

Para ter uma ideia melhor sobre como se realiza a indução sobre a complexidade das fórmulas, revisaremos o (meta)teorema de substituição

Suponha que F\equiv G. Seja H uma expressão que contém F como sub-expressão e seja H^\prime a expressão obtida ao substituir todas as ocorrências de F por G, então H\equiv H^\prime.

Demonstração por Indução sobre a Complexidade das Fórmulas

Demonstrar por indução sobre a complexidade é mostrar que ocorrem duas coisas: 1) um caso inicial (para fórmulas atômicas) e 2) o passo indutivo (se funciona para expressões quaisquer F e G, então funciona para F\downarrow G, ou de uma forma mais simples: funciona para \neg F e pelo menos algum dos seguintes: F\vee G, F\wedge G, F\rightarrow G ou F\leftrightarrow G).

Suponha que H seja uma expressão atômica, F é sub-expressão de H e F\equiv G. Se H^\prime é o resultado de substituir todas as sub-expressões F de H, como H é atômica, será que H^\prime \equiv G. Por outro lado, como H é atômica e F é sub-expressão de H, então H\equiv F. Finalmente teremos que:

H\equiv F \equiv G \equiv H^\prime

ficando demonstrado o caso inicial para expressões atômicas.

Agora vejamos o caso indutivo.

A hipótese de indução

Suponha que o teorema funcione para duas expressões quaisquer H_1 e H_2, cada uma contendo F como sub-expressão com F \equiv G. Então, se H_1^\prime é o que se obtém ao substituir todas as F por G em H_1 e H_2^\prime é o que se obtém ao substituir todas as F por G em H_2, teremos que H_1\equiv H_1^\prime e H_2\equiv H_2^\prime.

O passo indutivo

Aqui verificaremos se, como consequência da hipótese de indução, o teorema também se aplica para \neg H_1 (ou \neg H_2, qualquer um dos dois) e pelo menos um dos seguintes: H_1 \wedge H_2, H_1 \vee H_2, H_1 \rightarrow H_2.

Se H:= \neg H_1, então, pela hipótese de indução, será que H\equiv \neg H_1^\prime=: H^\prime , onde H^\prime é o resultado de substituir todas as ocorrências de F em H por G. Portanto, H\equiv H^\prime.

De forma semelhante, se H:= H_1 \wedge H_2, então, pela hipótese de indução, será que H\equiv H_1^\prime \wedge H_2 \equiv H_1^\prime \wedge H_2^\prime =: H^\prime , onde H^\prime é o resultado de substituir todas as ocorrências de F em H por G. Portanto, H\equiv H^\prime.

Portanto, a indução está completa e o teorema de substituição vale para todas as expressões da lógica proposicional.

Ao aplicar esta forma de indução, é possível garantir que uma propriedade se mantenha para todas as expressões de um sistema lógico, o que é especialmente útil na lógica proposicional para estruturar demonstrações rigorosas. Além disso, sua utilidade se estende a campos como a inteligência artificial e o desenvolvimento de software, onde a verificação de sistemas lógicos é essencial. Através dessa técnica, é possível automatizar demonstrações e garantir a consistência de expressões complexas, o que reduz o risco de erros e melhora a precisão em ambientes que dependem da validade matemática e lógica.