Provas por Indução: Regras Generalizadas de De Morgan e Distribuição
RESUMO
Esta aula aborda o tema das provas por indução em matemática e lógica proposicional. São explicados os dois tipos de provas existentes: as provas internas ou dedutivas, que se baseiam nas regras da lógica, e as provas externas ou metamatemáticas, que são necessárias para provar afirmações que se referem à própria lógica. A Indução Matemática é introduzida como um método de demonstração que permite provar que certas afirmações valem para todos os números naturais. Um exemplo é apresentado com a demonstração correspondente, e as formas generalizadas das leis de De Morgan e das leis distributivas em lógica proposicional são explicadas, junto com suas respectivas demonstrações por indução. Esta aula é de grande importância para entender os fundamentos da matemática e da lógica e para aplicá-los em diferentes áreas do conhecimento.
OBJETIVOS DE APRENDIZAGEM:
Ao final desta aula, o aluno será capaz de:
- Reconhecer os dois tipos de provas que devem ser distinguidos: provas internas ou dedutivas e provas externas ou metamatemáticas.
- Aplicar indução matemática para fazer demonstrações sobre os números naturais e na lógica proposicional.
- Utilizar as notações de conjunções e disjunções para escrever expressões da lógica proposicional.
- Compreender a forma generalizada das leis de De Morgan e de Distribuição na Lógica Proposicional.
- Compreender o conceito de hipótese de indução e seu papel na demonstração por indução.
ÍNDICE
PROVAS INTERNAS E EXTERNAS
PROVAS POR INDUÇÃO MATEMÁTICA
PROVAS POR INDUÇÃO NA LÓGICA PROPOSICIONAL
FORMA GENERALIZADA DAS LEIS DE DE MORGAN
FORMA GENERALIZADA DAS LEIS DISTRIBUTIVAS
Provas internas e externas
Existem dois tipos de provas que devem ser distinguidos. Até agora, vimos muitos exemplos de provas formais. Esse tipo de prova emerge das regras da lógica. Tais provas são ditas como ocorrendo “dentro da lógica” e, portanto, também são referidas como “provas internas” ou dedutivas. Essas provas formais têm um escopo limitado, pois só servem para provar afirmações que podem ser escritas na linguagem da lógica. No entanto, podemos querer provar algumas coisas sobre a própria lógica. Podemos querer provar que todas as afirmações da lógica proposicional satisfazem uma certa propriedade. Tais afirmações, que se referem à própria lógica, não podem ser estabelecidas ou provadas dentro da lógica. Para provar tais afirmações, utilizamos uma prova externa. As provas externas às vezes são chamadas de “metamatemáticas” e já nos deparamos com esse tipo de coisa, como quando vimos o (meta)teorema da dedução. É aqui que contextualizamos as provas indutivas.
Provas por Indução Matemática
A Indução Matemática é um método de demonstração que nos permite provar que algumas coisas valem para todos os números naturais.
EXEMPLO: É possível provar que qualquer número da forma 11^n - 4^n, onde n é qualquer número natural, é sempre divisível por 7.
DEMONSTRAÇÃO: Se observarmos o que ocorre com n=1, veremos que:
11^1 - 4^1 = 7
que obviamente é divisível por 7.
Agora, suponha que 11^n - 4^n seja divisível para um n=k. A partir disso, provaremos que essa expressão também será válida para n=k+1. Podemos fazer isso da seguinte forma:
Portanto, se 11^k - 4^k for divisível por 7, consequentemente 11 ( 11^{k} - 4^{k} ) + 7\cdot 4^{k} também será divisível por 7, o que é o mesmo que dizer que 11^{k+1} - 4^{k+1} é divisível por 7. A partir disso, temos que se 11^k - 4^k for divisível para k=1, então será para k=2, k=3, k=4,\cdots e assim por diante, e, portanto, divisível para qualquer n\in\mathbb{N}. Quando isso ocorre, dizemos que a indução está completa. ■
Provas por Indução na Lógica Proposicional
Para as provas por indução que realizaremos a seguir, será necessário introduzir primeiro a seguinte convenção de notação
NOTAÇÃO: Sejam F_1,\cdots, F_n um conjunto finito de expressões quaisquer da lógica proposicional. As conjunções e disjunções dessas expressões são introduzidas da seguinte maneira:
\displaystyle \bigwedge_{i=1}^n F_i := F_1\wedge \cdots \wedge F_n
\displaystyle \bigvee_{i=1}^n F_i := F_1\vee \cdots \vee F_n
Com isso, podemos agora lidar com as seguintes duas formas generalizadas.
Forma Generalizada das Leis de De Morgan
Dado um conjunto finito de expressões da lógica proposicional F_1,\cdots, F_n,, sempre se cumprirão as seguintes duas propriedades:
\displaystyle\neg\left(\bigwedge_{i=1}^n F_i \right) \equiv \left( \bigvee_{i=1}^n \neg F_i \right)
\displaystyle\neg\left(\bigvee_{i=1}^n F_i \right) \equiv \left( \bigwedge_{i=1}^n \neg F_i \right)
DEMONSTRAÇÃO: Primeiro, provaremos por indução sobre n que \neg\left(\bigwedge_{i=1}^n F_i \right) \equiv \left( \bigvee_{i=1}^n \neg F_i \right)
Primeiro, devemos verificar o que acontece com o caso inicial n=1. Neste caso, é claro que \neg F_1 \equiv \neg\left(\bigwedge_{i=1}^1F_i\right)\equiv \left(\bigvee_{i=1}^n \neg F_i \right) \equiv\neg F_1
Agora suponha que a propriedade funcione para algum n=k; ou seja, dado um conjunto finito de expressões F_1, F_2, \cdots, F_k, temos que:
\displaystyle \neg\left(\bigwedge_{i=1}^k F_i\right) \equiv \left(\bigvee_{i=1}^k \neg F_i\right)
Então, provaremos que, consequentemente, vale:
\displaystyle \neg\left(\bigwedge_{i=1}^{k+1} F_i\right) \equiv \left(\bigvee_{i=1}^{k+1} \neg F_i\right)
Usando a definição de conjunção, temos que:
\displaystyle \neg\left(\bigwedge_{i=1}^{k+1} F_i\right) := \neg\left[\left(\bigwedge_{i=1}^{k} F_i\right) \wedge F_{k+1}\right]
Sobre essa expressão, podemos aplicar as leis de De Morgan (a usual sobre dois termos) para obter:
\displaystyle \neg\left(\bigwedge_{i=1}^{k+1} F_i\right)\equiv \left[\neg\left(\bigwedge_{i=1}^{k} F_i\right) \vee \neg F_{k+1}\right]
Agora, se aplicarmos a hipótese de indução, obteremos:
\displaystyle \neg\left(\bigwedge_{i=1}^{k+1} F_i\right)\equiv \left[ \left(\bigvee_{i=1}^k \neg F_i\right) \vee \neg F_{k+1}\right] := \left(\bigvee_{i=1}^{k+1}\neg F_i \right)
E por esse motivo a indução está completa e a propriedade vale para qualquer n em geral. A segunda relação pode ser obtida de forma completamente análoga, por isso deixarei como exercício para o leitor, muahahaha!
Forma Generalizada das Leis Distributivas
De forma semelhante às leis de De Morgan, as leis de distribuição podem ser generalizadas da seguinte maneira. Sejam \{F_1, \cdots, F_n\} e \{G_1,\cdots, G_m\} dois conjuntos finitos de expressões quaisquer, então as seguintes equivalências são válidas:
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^m G_j \right) \right] \equiv \left[\bigwedge_{i=1}^n\left(\bigwedge_{j=1}^m(F_i\vee G_j) \right) \right]
\displaystyle \left[ \left(\bigvee_{i=1}^n F_i \right) \wedge \left(\bigvee_{j=1}^m G_j \right) \equiv \left[\bigvee_{i=1}^n\left(\bigvee_{j=1}^m(F_i\wedge G_j) \right) \right]
DEMONSTRAÇÃO: Para construir esta demonstração, devemos realizar uma dupla indução, sobre n e m. Em seguida, farei a indução primeiro sobre n e depois sobre m para a expressão \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^m G_j \right) \right] \equiv \left[\bigwedge_{i=1}^n\left(\bigwedge_{j=1}^m(F_i\vee G_j) \right) \right]
Se tomarmos m=1, então esta expressão fica escrita como
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^1 G_j \right) \equiv \left[\bigwedge_{i=1}^n\left(\bigwedge_{j=1}^1(F_i\vee G_j) \right) \right].
O que é o mesmo que dizer:
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee G_1 \equiv \left[\bigwedge_{i=1}^n\left( F_i\vee G_1 \right) \right].
Agora, provaremos esta expressão por indução sobre n.
Se tomarmos n=1, então a expressão se reduz a
F_1 \vee G_1 \equiv F_1 \vee G_1.
O que já sabemos que é verdadeiro. Agora, suponha que se cumpra para algum n=k; ou seja, a hipótese de indução será:
\displaystyle \left[ \left(\bigwedge_{i=1}^k F_i \right) \vee G_1 \equiv \left[\bigwedge_{i=1}^k\left( F_i\vee G_1 \right) \right].
Então, a partir disso, mostraremos que, consequentemente, se cumpre para n=k+1.
Pela definição de conjunção, temos que:
\displaystyle \left[\left(\bigwedge_{i=1}^{k+1}F_i \right) \vee G_1 := \left[\left(\left(\bigwedge_{i=1}^{k}F_i \right)\wedge F_{k+1} \right) \vee G_1
Agora, usando a \vee-distribuição, teremos que:
\displaystyle \left[\left(\bigwedge_{i=1}^{k+1}F_i \right) \vee G_1 equiv \left[\left(\left(\bigwedge_{i=1}^{k}F_i \right)\vee G_{1} \right) \wedge \left(F_{k+1} \vee G_1 \right)
E, bem neste ponto, podemos usar a hipótese de indução para obter:
\displaystyle \left[\left(\bigwedge_{i=1}^{k+1}F_i \right) \vee G_1 equiv \left[\left(\bigwedge_{i=1}^k\left( F_i\vee G_1 \right) \right) \wedge \left(F_{k+1} \vee G_1 \right) := \left[\bigwedge_{i=1}^{k+1}(F_{i}\vee G_1
Portanto, provamos por indução que para todo n\in\mathbb{N} se cumpre:
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right)\vee G_1 equival a \left[\bigwedge_{i=1}^n(F_i\vee G_1)
Completando a indução sobre n, verificamos que o caso inicial para m=1, funciona. Agora só precisamos completar a indução sobre m. Para fazer isso, estabelecemos a hipótese de indução para um m=l, ou seja, funciona:
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^l G_j equival a \left[\bigwedge_{i=1}^n\left(\bigwedge_{j=1}^l(F_i\vee G_j
e a partir disso, provaremos que também funciona para m=l+1.
Começando, como sempre, pela definição de conjunção, temos que
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{l+1} G_j := \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\left(\bigwedge_{j=1}^{l} G_j \right) \wedge G_{l+1]
Agora, usando a \vee-distribuição, teremos:
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{l+1} G_j equiv a \left[ \left( \left(\bigwedge_{i=1}^n F_i \right) \vee \left( \bigwedge_{j=1}^l G_j \right) \right) \wedge \left( \left( \bigwedge_{i=1}^n F_i \right)\vee G_{l+1
Consequentemente, usando a hipótese de indução, você pode escrever:
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{l+1} G_j equiv a \left[ \bigwedge_{i=1}^n\left(\bigwedge_{j=1}^l(F_i\vee G_j ) \wedge \left( \left( \bigwedge_{i=1}^n F_i \right)\vee G_{l+1
E se agora tomarmos o resultado da indução sobre n
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{l+1} G_j equiv a \left[ \bigwedge_{i=1}^n\left(\bigwedge_{j=1}^l(F_i\vee G_j ) \wedge \left( \bigwedge_{i=1}^n (F_i \vee G_{l+1 )
Que, finalmente, pela definição de conjunção, temos:
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{l+1} G_j equiv a \left[ \bigwedge_{i=1}^n\left(\bigwedge_{j=1}^{l+1}(F_i\vee G_j )
E, portanto, a indução sobre m está completa e a expressão:
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{m} G_j equiv a \left[ \bigwedge_{i=1}^n\left(\bigwedge_{j=1}^{m}(F_i\vee G_j
é válida para todos os n,m\in\mathbb{N.
Essa exploração das provas por indução demonstrou como técnicas rigorosas de demonstração matemática podem ser aplicadas não apenas no âmbito dos números naturais, mas também na lógica proposicional. Através da indução, estabelecemos a validade das formas generalizadas das leis de De Morgan e das leis distributivas, reforçando assim a compreensão dos fundamentos lógicos subjacentes a diversas áreas do conhecimento matemático. Essa abordagem não é apenas essencial para o desenvolvimento de habilidades de raciocínio abstrato, mas também serve como uma ferramenta poderosa para enfrentar problemas complexos em matemática e além.