Esse material apresenta exemplos de como provar que um argumento é válido por dedução natural. Para acompanhar as demonstrações, tenha em mãos as regras de inferência (básicas e derivadas) e as regras de equivalência para consulta. Exemplo 1: A -­‐> (B v C), ~B, ~C |-­‐ ~A Conforme já vimos nos vídeos e no livro, o primeiro passo é listar as hipóteses. 1. A -­‐> (B v C) hip 2. ~B hip 3. ~C hip Agora temos que ver onde queremos chegar, a conclusão é ~A. Onde temos A nas hipóteses? Somente na linha 1. Nesse caso, precisamos montar uma estratégia para liberar o A. Liberar aqui, quer dizer que precisamos eliminar a implicação. Não podemos pensar na regra MP (Modus Ponens) porque ela elimina o consequente (B v C). Passando pelas regras (básicas, derivadas e de equivalência), vimos que a regra MT (Modus Tollens) elimina a implicação e gera o antecedente negado (~A), exatamente o que precisamos. A partir disso, para aplicar a regra MT, precisamos gerar a negação do consequente da linha 1, nesse caso, ~(B v C). Pela estratégia elaborada, podemos aplicar a regra CJ (conjunção) na linha 2 e linha 3 gerando a linha 4, conforme linha abaixo 4. ~B ^ ~C 2, 3, cj Para a linha 5, podemos então inferir a regra DEMOR e gerar a fórmula que nos interessa ~(B v C). Nossa demonstração até o momento é 1. A -­‐> (B v C) hip 2. ~B hip 3. ~C hip 4. ~B ^ ~C 2, 3, cj 5. ~(B v C) 4, demor Finalmente poderemos inferir a regra MT como pensamos no início da demonstração, pois conseguimos gerar a negação do consequente da linha 1. A demonstração completa Demonstração completa: será: 1. A -­‐> (B v C) hip 2. ~B hip 3. ~C hip 4. ~B ^ ~C 2, 3, cj 5. ~(B v C) 4, demor 6. ~A 1, 5, mt Exemplo 2: B <-­‐> A, ( B v C) -­‐> (E v Q), (B ^ A) -­‐> C, ~E, B |-­‐ Q Nosso primeiro passo é identificarmos as hipóteses (B <-­‐> A, ( B v C) -­‐> (E v Q), (B ^ A) -­‐> C, ~E, B) e a conclusão Q. Pelo método, temos que partir das hipóteses, aplicar as regras e gerar fórmulas até chegarmos na conclusão. A partir disso, seguiremos os passos do método para provar que o argumento é válido. 1º passo: listar as hipóteses 1. B <-­‐> A hip 2. (B v C) -­‐> (E v Q) hip 3. (B ^ A) -­‐> C hip 4. ~E hip 5. B hip 2º passo : aplicar as regras de inferência e de equivalência, visando se chegar a conclusão. Lembrando, nesse exemplo a conclusão é Q Para gerar a fórmula B v C da linha 6, devemos aplicar a regra a regra de adição na linha 5 6. B v C 5,ad 7.E v Q 2,6,mp A linha 7 foi gerada porque aplicando a regra modus ponens na linha 2 e na linha 6. Por fim, se aplicarmos SD (silogismo disjuntivo) nas linhas 4 e 7, chegaremos a fórmula Q que será gerada na linha 8. 8.Q 4,7,sd Q é a conclusão a qual queríamos chegar, sendo assim a demonstração foi concluída e o argumento é válido. Demonstração completa: 1. B <-­‐> A hip 2. (B v C) -­‐> (E v Q) hip 3. (B ^ A) -­‐> C hip 4. ~E hip 5. B hip 6. B v C 5,ad 7.E v Q 2,6,mp 8.Q 4,7,sd Exemplo 3: A -­‐> (B v C), ~B, ~C |-­‐ ~A Novamente, pelo método, precisamos listar as hipóteses, aplicar as regras e gerar novas fórmulas para chegarmos a conclusão. A sequência de passos para provar que o argumento é válido é: 1º passo: lembrando que todos argumentos a esquerda do sinal "|-­‐" são hipóteses e devem ser identificadas como segue: 1. A -­‐> (B v C) hip 2. ~B hip 3. ~C hip 2º passo: aplicar as regras de inferência (básicas e derivadas) e regras de equivalência nas hipóteses, com o objetivo de chegarmos na conclusão (argumentos a direita de "|-­‐"). Pelo exemplo dado, precisamos chegar na conclusão ~A Para gerar a fórmula da linha 4, aplica-­‐se a regra CJ (conjunção) nas linhas 2 e 3. 4. ~B ^ ~C 2,3,cj 5. ~(BvC) 4,dmor A linha 5 foi gerada a partir da aplicação da regra DEMOR na linha 4. Para gerar a linha 6, observamos a linha 1 e a linha 5 e aplicamos a regra MT (modus tollens) 6. ~A 1,5,mt A linha 6 é exatamente igual a conclusão (argumento a direita de |-­‐), sendo assim a nossa dedução terminou e provamos que o argumento é válido. Além dos exemplos comentados, está disponibilizado na comunidade vídeos com outros exemplos e vídeos de revisão sobre todo conteúdo estudado até o momento. Demonstração completa: 1. A -­‐> (B v C) hip 2. ~B hip 3. ~C hip 4. ~B ^ ~C 2,3,cj 5. ~(BvC) 4,dmor 6. ~A 1,5,mt Exemplo 4: Nos próximos exemplos utilizaremos as regras hipotéticas (RAA e PC). G -­‐> ~N,~N -­‐> ~P |-­‐ G -­‐> ~P 1º Passo: identificar as hipóteses 1. G-­‐> ~N hip 2. ~N-­‐>~P hip 2º passo: tentar aplicar regras sobre as fórmulas, com o objetivo de se chegar na conclusão (G -­‐> ~P). Nesse caso, não é possível aplicar nenhum regra nas hipóteses da linha 1 e linha 2. 3º passo: como não é possível aplicar regras diretamente, então devemos criar fórmulas. Para criar uma fórmula devemos utilizar as regras hipotéticas, sendo que a regra RAA gera uma fórmula com uma negação e a regra PC gera uma fórmula com uma implicação. Considerando as dicas de construção de demonstrações, em geral, quando se tem na conclusão uma implicação (-­‐>), devemos gerar uma hipótese a partir da regra PC, onde a hipótese que abrirá a prova temporária será o antecedente dessa implicação e a última fórmula antes de fecharmos a prova temporária será o consequente da implicação. Como se trata de regra hipotética (ou seja criada por nós) é preciso identificá-­‐las com uma linha na vertical para mostrar que aquela parte da demonstração é temporária "|" 3. |G hip-­‐pc 4º passo: aplicação de regras utilizando a hipótese recém criada 4. |~N 1,3,mp 5. |~P 2,4,mp 5º passo: eliminação da regra hipotética -­‐ a regra criada deve ser eliminada antes do final da demonstração. No caso da hipótese por PC, isso deve ser feito através da aplicação da regra PC. 6. G -­‐> ~P 3,5,pc Demonstração completa: A linha 6 corresponde a conclusão que queríamos chegar conforme argumento: G-­‐> ~N,~N-­‐>~P|-­‐G-­‐>~P 1. G-­‐> ~N hip 2. ~N-­‐>~P hip 3. |G hip-­‐pc 4. |~N 1,3,mp 5. |~P 2,4,mp 6. G -­‐> ~P 3,5,pc Exemplo 5: Nesse exemplo utilizaremos a regra hipotética RAA. C-­‐>~F|-­‐~(C ^F) 1º passo: identificação das hipóteses: 1. C-­‐>~F hip 2º passo: aplicação de regras sobre as hipóteses, objetivando se chegar a conclusão. Nesse caso não é possível aplicar nenhuma fórmula, uma vez que temos somente uma hipótese. 3º passo: criação de fórmulas a partir de regras hipotéticas. Em geral, considerando as dicas de construção de demonstração, quando se tem uma negação na conclusão: |-­‐ ~(C ^ F), é indicada a criação de uma regra hipotética do tipoRAA: Conforme mencionado em outro exemplo, como se trata de uma regra hipotética, o sinal "|" deve aparecer para identificar que abrirmos uma prova temporária. 2. |C^F hip-­‐raa; A partir desse ponto deve se tentar aplicar as regras visando se chegar a conclusão: ~(C ^F). Para gerar a linha 3, aplicamos a regra SP (simplificação) sobre a linha 2. 3. |C 2,sp; 4. |~F 1,3,mp; Com isso, foi possível aplicar a regra MP (modus ponens) sobre as linhas 1 e 3 e na sequência aplicamos a regra SP (simplificação) sobre a linha 2 para gerar a fórmula F. 5. |F 2,sp; 6. |F ^~F 4,5,cj; 7. ~(C^F) 2-­‐6,raa; A linha 6 foi gerada aplicando a regra CJ (conjunção) sobre as linhas 4 e 5. Por fim, a prova temporária é fechada na linha 6, pois encontramos uma fórmula que é uma contradição e geramos a fórmula da linha 7, que vem a ser a fórmula negada da linha 2, quando abrirmos a prova Demonstração completa: temporária por RAA. Na linha 7 chegamos a 1. C-­‐>~F hip conclusão apresentada no argumento, então a 2. |C^F hip-­‐raa; demonstração pode ser considerada como 3. |C 2,sp; concluída. 4. |~F 1,3,mp; 5. |F 2,sp; 6. |F ^~F 4,5,cj; 7. ~(C^F) 2-­‐6,raa; Exemplo 6: A -­‐> (R <-­‐> (B v T)), C v L, L -­‐> A |-­‐ ~C -­‐> (B -­‐> R) 1º passo: listar as hipóteses (toda informação a esquerda "|-­‐") 1. A -­‐> (R <-­‐> (B v T)) hip 2. C v L hip 3. L -­‐> A hip 2º passo: tentar aplicar as regras de inferência, visando chegar a conclusão (informação a direita "|-­‐") Nesse caso não é possível aplicar nenhuma regra de inferência diretamente, então partimos para a estratégia de utilização de regras hipotéticas. Como temos uma implicação (-­‐>) na conclusão, iniciamos com a regra hip-­‐pc. 4. |~C hip-­‐pc 5. || B hip-­‐pc 6. || L 2,4,sd Como não conseguimos aplicar nenhuma regra nas 4 linhas já existentes, então geramos a linha 5 com mais uma regra hipotética. Após a inserção de duas regras hipotéticas, já é possível utilizar a regra de inferência silogismo disjuntivo (sd) para gerar a fórmula da linha 6. 7. || A 3,6,mp 8. || R <-­‐> (B v T) 1,7,mp A fórmula da linha 7 foi gerada a partir da aplicação da regra MP (modus ponens) nas linhas 3 e 6. Geramos a linha 8 aplicando a regra MP nas linhas 1 e 7, assim temos parte da fórmula que nos interessa da linha 1. A partir da linha 8 podemos aplicar a regra E<-­‐> e liberar um dos lados da implicação, gerando a linha 9. 9. || (B v T) -­‐> R 8,E<-­‐> 10. || B v T 5,ad Ainda temos duas provas temporárias em aberto, no nosso exemplo, as duas são PC (prova condicional). O objetivo é encontrar uma fórmula que será o consequente das hip-­‐pc abertas. A primeira prova a fechar será a hip-­‐pc que tem a fórmula B como antecedente e precisamos gerar a fórmula R como consequente. Nesse caso, para isso, com a linha 5 podemos aplicar a regra de adição (ad), gerando a fórmula B v T da linha 10. Por fim, para fecharmos a primeira prova temporária, aplicamos a regra MP nas linhas 9 e 10 para deduzir R na linha 11. 11. || R 9,10,mp 12. |B -­‐> R 5,11,pc Assim fechamos PC que irá da linha 5 a linha 11, por isso um dos sinais | foi retirado. As fórmulas dentro dessa prova não podem mais ser utilizadas na demonstração. 13. ~C -­‐> (B -­‐> R) 4,12,pc Para finalizar a demonstração, na linha 13 geramos a fórmula que é a conclusão. Com as linhas 4 e 12 podemos aplicar a regra pc e eliminar a primeira regra hipotética criada (por isso o outro sinal | foi retirado). Demonstração completa: 1. A -­‐> (R <-­‐> (B v T)) 2. C v L 3. L -­‐> A 4. |~C 5. || B 6. || L 7. || A 8. || R <-­‐> (B v T) 9. || (B v T) -­‐> R 10. || B v T 11. || R 12. |B -­‐> R 13. ~C -­‐> (B -­‐> R) hip hip hip hip-­‐pc hip-­‐pc 2,4,sd 3,6,mp 1,7,mp 8,E<-­‐> 5,ad 9,10,mp 5,11,pc 4,12,pc Exemplo 7: (A v B ) -­‐> C, C ^ A |-­‐ ( A v B) ^ ( A ^ C ) O primeiro passo para desenvolver a demonstração é listar as hipóteses e identifica-­‐las. No exemplo, as hipóteses são (A v B ) -­‐> C, C ^ A, então temos: 1. (A v B ) -­‐> C hip 2. C ^ A hip A seguir, identifique qual e a conclusão e seus respectivos operadores. Isso irá ajudar a elaborar a estratégia para chegarmos na conclusão, a partir das hipóteses, consideramos a conclusão é ( A v B) ^ ( A ^ C ). A partir das dicas para construção da demonstração indicada no material e no livro, sabemos pela dica que se tivermos uma conjunção na conclusão, a sugestão é procurar gerar as fórmulas separadamente na demonstração e, no final, aplicar a regra de conjuncão (cj). Uma das formas de desenvolvermos a estratégia é esta do exemplo, como chegamos a linha 3? Identificamos que precisávamos da fórmula “A” para gerar o antecedente da fórmula da linha 1. Então, a regra SP (simplicação – regra de eliminação da conjunção) pode ser aplicada na linha 2 para gerarmos a fórmula A. 1. (A v B ) -­‐> C hip 2. C ^ A hip 3. A 2, sp Agora podemos seguir nosso raciocínio que é aplicar a regra AD (adição). Essa regra diz que precisamos ter uma fórmula na demonstração e a partir dela, podemos adicionar qualquer outra fórmula. Nesse caso, temos a fórmula A, então podemos adicionar a fórmula B, gerando a linha 4. 1. (A v B ) -­‐> C hip 2. C ^ A hip 3. A 2, sp 4. A v B 3, ad Pronto, de acordo com a orientação anterior, já temos uma parte da conclusão, agora precisamos gerar a outra. O que precisamos fazer agora? Se formos avaliar a estrutura das hipóteses, podemos pensar em usar alguma para nos ajudar a gerar a fórmula do conclusão? Sim, a linha 2 tem a formula C ^ A, então aplicamos a regra SP( simplificação) e geramos a fórmula C. Esta formula vai estar na linha 5. 1. (A v B ) -­‐> C hip 2. C ^ A hip 3. A 2, sp 4. A v B 3, ad 5. C 2, sp A próxima linha será gerada aplicando a regra CJ (regra da conjunção) para gerar a fórmula A ^ C, nas linhas 3 e 5. 1. (A v B ) -­‐> C hip 2. C ^ A hip 3. A 2, sp 4. A v B 3, ad 5. C 2, sp 6. A ^ C 3, 5, cj Por fim, como pensamos no inicio da estratégia e pela dica de construção, temos as duas partes da formula, então precisamos apenas aplicar a regra de introdução da conjunção. Demonstração completa: 1. (A v B ) -­‐> C hip 2. C ^ A hip 3. A 2, sp 4. A v B 3, ad 5. C 2, sp 6. A ^ C 3, 5, cj 7. (A v B ) ^ (A ^ C) 4, 6, cj