sexta-feira, 7 de março de 2014

Regras de Inferência e Provas Lógicas

Rules of Inference and Logic Proofs
Bruce Ikenaga


Bruce Ikenaga é professor de Matemática na Millersville University – Pennsylvania - USA. Este texto, faz parte de uma coleção de notas de aulas sobre técnicas de provas matemáticas, que podem ser acessadas na página  Notes on Math Proof (traduzido e publicado com a permissão do autor).


Uma prova é uma argumentação a partir das hipóteses ( suposições ) até uma conclusão. Cada passo da argumentação segue as leis da lógica. Em matemática, uma declaração não é aceita como válida ou correta se não for acompanhada de uma prova. Esta insistência na prova é uma das características que diferenciam a matemática de outros assuntos.


Escrever provas é difícil, não há procedimentos que você possa seguir que garantam o sucesso. Os padrões que as provas seguem são complicados, e há um monte deles. Você não pode esperar conseguir fazer as provas seguindo regras, memorizando fórmulas ou olhando alguns exemplos em um livro.


Por este motivo, vou começar por discutir as provas lógicas. Uma vez que elas são mais padronizadas do que a maioria das provas, elas são um bom lugar por onde começar. Elas devem ser escritas em formato de coluna, com cada passo justificado por uma regra de inferência. A maioria das regras de inferência virá de tautologias. Uma vez que uma tautologia é uma afirmação que é "sempre verdadeira" , faz sentido usá-las para tirarmos conclusões.


Como a maioria das provas, as de lógica geralmente começam com as premissas, que são declarações que você está autorizado a assumir como sendo verdadeiras. A conclusão é a afirmação que você precisa provar. A ideia é operar sobre as premissas, utilizando as regras de inferência até chegar à conclusão.


Regra das Premissas. Você pode escrever uma premissa em qualquer ponto de uma prova.


A segunda regra de inferência você vai usar na maioria das provas de lógica. Às vezes é chamada de modus ponendo ponens, mas usarei um nome mais curto.


Modus Ponens (do Latim e significa modo de afirmarSe você sabe $P$ e $P \rightarrow Q$, então você pode escrever $Q$ (considerar Q verdadeira).


Nas regras de inferência, é entendido que símbolos como "P" e "Q" podem ser substituídos por quaisquer declarações, incluindo sentenças compostas.


Exemplo. Aqui está um exemplo simples de modus ponens. Suponha que $P$ e $P \rightarrow Q$ são premissas. Então eu posso usar modus ponens para derivar $Q$:


$$\begin{matrix}
1. & P & \text{Premissa} \\
2. & P \rightarrow Q & \text{Premissa}  \\
3. & Q & \text{Modus Ponens (1,2)}
\end{matrix}$$

Vou escrever as provas de lógica em 3 colunas. As demonstrações em provas lógicas são numeradas para que você possa referenciá-las, e os números vão na primeira coluna. As demonstrações reais ficam na segunda coluna. A terceira coluna contém a sua justificativa para a sentença escrita na coluna 2.

Assim, as declarações 1 $(P)$ e 2 $(P \rightarrow Q)$ são premissas, então a regra das premissas me permitem escrevê-las. O Modus ponens diz que, se eu já escrevi $P$ e $P \rightarrow Q$ em quaisquer das linhas anteriores, em qualquer ordem, então eu posso escrever $Q$. Eu fiz isso na linha 3 , citando a regra ("Modus ponens") e as linhas ( 1 e 2 ) , que continham as declarações que eu precisava para aplicar o modus ponens.

Aqui está outro exemplo.

$$\begin{matrix}
1. & (A \vee \neg B) \rightarrow \neg C & \text{Premissa} \\
2. & \neg D  & \text{Premissa} \\
3. & (A \vee \neg B) & \text{Premissa} \\
4. & \neg C & \text{Modus Ponens (1,3)} \\
\end{matrix}$$

Há várias coisas a serem observadas aqui. Em primeiro lugar, $(A \vee \neg B)$ está tomando o lugar de $P$ na regra modus ponens, e $\neg C$ está tomando o lugar de $Q$. Como comentei antes deste exemplo, "P" e "Q" podem ser quaisquer sentenças, incluindo declarações compostas.


Observe também que a sentença se-então, $(A \vee \neg B) \rightarrow \neg C$ , é listada primeiro e a $\neg C$ é listada em segundo lugar. Não importa qual tenha sido escrita em primeiro lugar, desde que ambas foram escritas antes de aplicar modus ponens.


Finalmente, a declaração $ \neg D $ não participou no passo do modus ponens. Talvez seja parte de uma prova maior, e $ \neg D $ será utilizada mais tarde . O fato de $ \neg D $ ficar entre as duas peças modus ponens não faz diferença.


Dupla negação. Em qualquer declaração, você pode substituir $P$ por $ \neg \neg P $ ou $ \neg \neg P $ por $ P $ e escrever abaixo a nova sentença.


Exemplo. Neste exemplo, eu estou aplicando dupla negação com $P$ substituído por $ A \rightarrow \neg C $:


$$\begin{matrix}
1. & \neg [ \neg ( A \rightarrow \neg C ) ] & \text{Premissa} \\
2. & A \rightarrow \neg C  & \text{Dupla negacao (1)}
\end{matrix}$$

A Dupla negação surge muitas vezes, o suficiente para que, como um atalho, eu vou muitas vezes pular uma etapa e usá-la sem mencionar isso nos exemplos de algumas das outras regras de inferência .


Modus tollens (do Latim e significa modo que negaSe você souber $ \neg Q $ e $ P \rightarrow Q $, você pode escrever $ \neg P $.


Exemplo. Aqui está um exemplo simples de Modus tollens:


$$\begin{matrix}
1. & \neg Q & \text{Premissa}\\
2. & P \rightarrow Q & \text{Premissa}\\
3. & \neg P & \text{Modus tollens (1,2)}\\
\end{matrix}$$

No próximo exemplo, eu estou aplicando modus tollens com $ P $ substituído por $ C $ e $ Q $ substituído por $ A \rightarrow B $:

$$\begin{matrix}
1. & \neg (A \rightarrow B) & \text{Premissa}\\
2. & C \rightarrow (A \rightarrow B) & \text{Premissa}\\
3. & \neg C & \text{Modus tollens (1,2)}\\
\end{matrix}$$

Silogismo disjuntivo. Se você souber $ \neg P $ e $ P \vee Q $, você pode escrever $ Q $.


Exemplo. Aqui está a forma mais simples de silogismo disjuntivo:


$$\begin{matrix}
1. & \neg P & \text{Premissa}\\
2. & P \vee Q & \text{Premissa}\\
3. & Q & \text{Silogismo disjuntivo (1,2)}\\
\end{matrix}$$


No próximo exemplo, estou aplicando silogismo disjuntivo, com $ A \vee B $ substituindo $ P $ e $ D $ substituindo $ Q $ na regra:

$$\begin{matrix}
1. & \neg (A \vee B) & \text{Premissa}\\
2. & (A \vee B) \vee D & \text{Premissa}\\
3. & D & \text{Silogismo disjuntivo (1,2)}\\
\end{matrix}$$



No próximo exemplo, observe que $ P $ é o mesmo que $ \neg \neg P $, por isso é a negação de $ \neg P $.


$$\begin{matrix}
1. & P & \text{Premissa}\\
2. & \neg P \vee (Q \rightarrow R) & \text{Premissa}\\
3. & Q \rightarrow R & \text{Silogismo disjuntivo (1,2)}\\
\end{matrix}$$






Este foi um caso onde eu saltei o passo da dupla negação. Sem pular o passo, a prova ficaria assim:



$$\begin{matrix}
1. & P & \text{Premissa}\\
2. & \neg P \vee (Q \rightarrow R) & \text{Premissa}\\
3. & \neg \neg P & \text{Dupla negacao}\\
4. & Q \rightarrow R & \text{Silogismo disjuntivo (1,2)}\\
\end{matrix}$$



Lei de DeMorgan. Em qualquer declaração, você pode substituir:

$$\begin{matrix}
1. & \neg (P \vee Q) & \text{por} & \neg P \wedge \neg Q \\
2. & \neg P \wedge \neg Q & \text{por} & \neg (P \vee Q) \\
3. & \neg(P \wedge Q) & \text{por} & \neg P \vee \neg Q \\
4. & \neg P \vee \neg Q & \text{por} & \neg (P \wedge Q) \\
\end{matrix}$$


Como de costume, depois de ter substituído, você anota a nova declaração.



A lei de DeMorgan nos diz como distribuir $\neg$ através de $\vee$ ou $ \wedge $, ou como retirar $\neg$ de $ \vee $ ou $ \wedge $ . Para distribuir, você anexa $\neg$ em cada termo, em seguida, troca $ \vee $ por $ \wedge $ ou $ \wedge $ por $ \vee $. Para retirar, você tira $\neg$ de cada termo , em seguida, troca $\vee$ por $ \wedge $ ou $ \wedge $ por $\vee$.


Exemplo.




$$\begin{matrix}
1. & \neg ( \neg P \vee \neg Q) & \text{Premissa}  \\
2. & P \wedge Q & \text{DeMorgan (1)}
\end{matrix}$$


Observe que a aplicação literal de DeMorgan teria dado $ \neg \neg P \wedge \neg \neg Q $. Eu mudei isso para $ P \wedge Q $, suprimindo a etapa da dupla negação.



Construindo uma conjunção. Se você sabe que $ P $ e $ Q $, você pode escrever $ P \wedge Q $.


Exemplo. Neste exemplo, observe que eu coloquei as peças em parênteses para agrupá-las após construir a conjunção.


$$\begin{matrix}
1. & P \iff Q & \text{Premissa} \\
2. & P \vee Q & \text{Premissa} \\
3. & (P \iff Q) \wedge (P \vee Q) & \text{Construindo uma Conjuncao (1,2)}
\end{matrix}$$

Regra do Silogismo. Se você souber $ P \rightarrow Q $ e $ Q \rightarrow R $, então você pode escrever $ P \rightarrow R $.


Exemplo. A Regra do Silogismo diz que você pode encadear os silogismos. Por exemplo:


$$\begin{matrix}
1. & P \rightarrow ( Q \vee R) & \text{Premissa} \\
2. & (Q \vee R) \rightarrow \neg S & \text{Premissa} \\
3. & P \rightarrow \neg S & \text{Regra do Silogismo (1,2)}
\end{matrix}$$



Definição de Bicondicional. Se você sabe $ P \iff Q $, você pode escrever $P \rightarrow Q $ e você pode escrever $ Q \rightarrow P $. Se você sabe $ P \rightarrow Q $ e $ Q \rightarrow P $, você pode escrever $ P \iff Q $.


Exemplo.

$$\begin{matrix}
1. & P \iff Q & \text{Premissa} \\
2. & Q & \text{Premissa} \\
2. & Q \rightarrow P & \text{Def. de Bicondicional (1)} \\
3. & P  & \text{Modus Ponens (2,3)}
\end{matrix}$$

Decompondo uma conjunção. Se você souber $ P \wedge Q $, você pode escrever $ P $ e você pode escrever $ Q $.


Exemplo. Você pode decompor uma conjunção para obter as peças individuais:


$$\begin{matrix}
1. & P \wedge (Q \iff \neg R) & \text{Premissa} \\
2. & P & \text{Decompondo uma conjuncao (1)} \\
2. & Q \iff \neg R & \text{Decompondo uma conjuncao (1)}
\end{matrix}$$

Note que você não pode decompor uma disjunção!


$$\begin{matrix}
1. & P \vee Q & \text{Premissa} \\
2. & \text{???} & \text{Errado!}
\end{matrix}$$

Sabendo que $ P \vee Q $ é verdade, você sabe que ou $ P $ ou $ Q $ deve ser verdade. O problema é que você não sabe qual é, então você não pode assumir que qualquer uma delas, em especial, seja verdade.


Construindo uma disjunção. Se você sabe $ P $, e $ Q $ é qualquer declaração, então você pode escrever $ P \vee Q $.


Exemplo. Se você sabe que uma sentença é verdadeira, você pode fazer um "ou" dela com “qualquer outra sentença” para construir uma disjunção.


$$\begin{matrix}
1. & P  & \text{Premissa} \\
2. & P \vee (\text{Calvin dorme com a luz acesa}) & \text{Construindo uma disjuncao (1)}
\end{matrix}$$

Note que não importa o que a outra afirmação é!


Comutatividade das Conjunções. Em qualquer declaração, você pode substituir $ P \wedge Q $ por $ Q \wedge P $ ( e escrever a nova declaração ) .


Comutatividade das disjunções. Em qualquer declaração, você pode substituir $ P \vee Q $ por $ Q \vee P $ ( e escrever a nova declaração ) .


Exemplo. As regras de comutatividade são tão fáceis que com freqüência eu as uso sem menção explícita. Elas dizem que você pode escrever os termos em uma sentença "ou" ou numa sentença "e" em qualquer ordem.


Aqui está a comutatividade da conjunção :


$$\begin{matrix}
1. & P \wedge \neg Q & \text{Premissa} \\
2. & \neg Q \wedge P  & \text{Comutatividade (1)}
\end{matrix}$$

Aqui está a comutatividade para uma disjunção :

$$\begin{matrix}
1. & (Q \rightarrow P) \vee R  & \text{Premissa} \\
2. & R \vee (Q \rightarrow P)  & \text{Comutatividade (1)}
\end{matrix}$$

Antes de dar alguns exemplos de provas de lógica, eu vou explicar de onde as regras de inferência vêm. Você provavelmente já percebeu que as regras de inferência correspondem a tautologias. Na verdade, você pode começar com as tautologias e usar um pequeno número de regras simples de inferência para derivar todas as outras regras de inferência .

Três dessas regras simples foram citadas acima: A Regra das Premissas, o  Modus Ponens e Construindo uma conjunção. Aqui estão outras duas:

Equivalência. Você pode substituir uma declaração por outra que lhe seja logicamente equivalente. Lembre-se que $ P $ e $ Q $ são logicamente equivalentes se e somente se $ P \iff Q $ é uma tautologia.

Por exemplo, uma vez que $ P $ e $ \neg \neg P $ são logicamente equivalentes, você pode substituir $ P $ por $ \neg \neg P $ ou $ \neg \neg P $ por $ P $. Esta é a dupla negação.

Substituição. Você pode pegar uma tautologia conhecida e substituir em sentenças simples.

Exemplo. A tautologia Silogismo Disjuntivo diz $ ( \neg P \wedge ( P \vee Q )) \rightarrow Q, suponha que você tenha $ \neg ( A \wedge D ) $ e $ (A \wedge D) \vee C $ como premissas. Veja como você pode aplicar as regras de inferência simples e a tautologia do Silogismo Disjuntivo:

$$\begin{matrix}
1. & \neg (A \wedge D)  & \text{Premissa} \\
2. & (A \wedge D) \vee C  & \text{Premissa} \\
3. & \neg (A \wedge D) \wedge ((A \wedge D) \vee C)  & \text{Constr. conjuncao (1,2)} \\
4. & \neg (A \wedge D) \wedge ((A \wedge D) \vee C) \rightarrow C & \text{Subst. (Silogismo Disjuntivo) (3)} \\
5. & C  & \text{Modus Ponens (3,4)}
\end{matrix}$$

Repare que eu usei quatro das cinco regras de inferência simples: a Regra das Premissas, Modus Ponens, Construindo uma Conjunção, e Substituição . Na linha 4, eu usei a tautologia do silogismo disjuntivo $ (( \neg P \wedge ( P \vee Q )) \rightarrow Q) $ substituindo $ (A \wedge D ) $ por $ P $ e $ C $ por $ Q $. ( Algumas pessoas usam a palavra " instanciação " para este tipo de substituição. )

A vantagem dessa abordagem é que você tem apenas cinco regras simples de inferência. A desvantagem é que as provas tendem a ser mais longas. Com a abordagem que vou usar, o silogismo disjuntivo é uma regra de inferência, e a prova é:

$$\begin{matrix}
1. & \neg (A \wedge D)  & \text{Premissa} \\
2. & (A \wedge D) \vee C  & \text{Premissa} \\
3. & C  & \text{Silogismo Disjuntivo (1,2)}
\end{matrix}$$

A abordagem que eu estou usando transforma as tautologias em regras de inferência de antemão, e por isso você não vai precisar usar as regras de Equivalência e Substituição muitas vezes. Mas você tem permissão para usá-las, e aqui é onde elas podem ser úteis. Suponha que você está escrevendo uma prova e você gostaria de usar uma regra de inferência, mas ela não foi mencionada acima. Anote a declaração lógica correspondente, em seguida, construa uma tabela verdade para provar que é uma tautologia (se ela não estiver na lista de tautologias ). Em seguida, faça uma Substituição para usar sua nova tautologia.

Se você fosse fazer uma pizza, uma abordagem seria comprar os ingredientes, a massa, o molho, o queijo, as coberturas, etc., levar tudo para casa, montar a pizza, e colocá-la no forno. Usando tautologias juntamente com as cinco regras de inferência simples é como fazer a pizza a partir do zero. Mas você também pode ir ao mercado e comprar uma pizza congelada, levá-la para casa e colocá-la no forno. Usando muitas regras de inferência que vêm de tautologias, a abordagem que vou usar, é como começar a partir da pizza congelada.

A seguir  estão algumas provas que utilizam as regras de inferência. Em cada caso, algumas premissas, declarações que são assumidas como verdadeiras, são dadas, assim como uma sentença a provar. A prova consiste em utilizar as regras de inferência para produzir a sentença a provar a partir das premissas.
Exemplo.
Premissas:$ \neg A \rightarrow ( C \wedge D ) $, $ A \rightarrow B $, $ \neg B $.
Prove: $ C $.

$$\begin{matrix}
1. & A \rightarrow D & \text{Premissa} \\
2. & \neg B  & \text{Premissa} \\
3. & \neg A  & \text{Modus tollens (1,2)} \\
4. & \neg A \rightarrow ( C \wedge D )  & \text{Premissa} \\
5. & C \wedge D & \text{Modus Ponens (3,4)} \\
6. & C  & \text{Decompondo uma conjuncao  (5)}
\end{matrix}$$

Uma coisa é ver que os passos estão corretos, outra coisa é ver como você pensaria para fazê-los. Eu usei a minha experiência com formas lógicas combinadas com o método de trabalhar para trás ( do fim para o começo ).

Estou tentando provar $ C $, então eu olhei para declarações contendo $ C $. Apenas a primeira premissa contém $ C $. Vi que $ C $ estava contida na conseqüente de um se-então, por modus ponens, a conseqüente segue se você sabe o antecedente.

O antecedente da primeira premissa é $ \neg A $. Por isso, procurei outra premissa contendo um ou $ A $ ou $ \neg A $. A única outra premissa contendo $ A $ é a segunda. Neste caso, $ A $ aparece como o antecedente de um se-então. Por modus tollens, $ \neg A $ decorre da negação do conseqüente $ B $. Mas eu notei que eu tinha $ \neg B $ como premissa, então tudo o que restava era executar todos os passos para a frente e escrever tudo.

A fim de fazer isso, eu precisava ter uma boa familiaridade com as regras básicas de inferência: Modus ponens, modus tollens, e assim por diante. Você vai adquirir essa familiaridade escrevendo provas lógicas.

Você também tem que se concentrar, a fim de lembrar-se onde você está à medida que você trabalha para trás. Você pode precisar rascunhar coisas no papel para evitar confusão. Continue a praticar, e você descobrirá que as provas ficam mais fáceis com o tempo e a prática.

Exemplo.
Premissas: $ P \wedge Q, P \rightarrow \neg (Q \wedge R), S \rightarrow R $
Prove: $ \neg S $.

$$\begin{matrix}
1. & P \wedge Q & \text{Premissa} \\
2. & P  & \text{Decompondo uma conjuncao (1)} \\
3. & Q  & \text{Decompondo uma conjuncao (1)} \\
4. & P \rightarrow \neg (Q \wedge R) & \text{Premissa} \\
5. & \neg (Q \wedge R)  & \text{Modus Ponens (3,4)} \\
6. & \neg Q \vee \neg R & \text{DeMorgan (5)} \\
7. & \neg R & \text{Silogismo Disjuntivo (3,6)} \\
8. & S \rightarrow R & \text{Premissa} \\
9. & \neg S & \text{Modus Tollens (7,8)}
\end{matrix}$$

Exemplo.
Premissas: $ \neg (A \vee B) \rightarrow C, \neg A, \neg C $
Prove: $ B $.

$$\begin{matrix}
1. & \neg ( A \vee B ) \rightarrow C & \text{Premissa} \\
2. & \neg C  & \text{Premissa} \\
3. & A \vee B & \text{Modus tollesn (1,2)} \\
4. & \neg A & \text{Premissa} \\
5. & B & \text{Silogismo Disjuntivo (3,4)}
\end{matrix}$$



Observe que no passo 3, eu poderia ter escrito $ \neg \neg ( A \vee B ) $. Eu omiti o passo da dupla negação, como tenho feito em outros exemplos.


Copyright 2009 by Bruce Ikenaga.

Nenhum comentário:

Postar um comentário