2.3 DEMONSTRAÇÃO

Nesta etapa da teoria da demonstração, é importante saber:

“O que é necessário demonstrar em matemáticas?”

Isto para estabelecer a diferença entre ``mostrar'' e ``demonstrar''. Existem provas de afirmações que realmente são ``mostras'' no sentido de somente mostrar, para que se veja com o olhos que a afirmação é verdadeira. Tal pode ser ocaso de ``mostrar'' visualmente o teorema de Pitágoras; porém não existe razões que justifiquem a necessidade de demonstrar, no sentido de afastar-se da evidencia visual, no caso que está não seja possível ou clara.

Deste modo devemos ter consciência de “o que é” e “o que não é”' demonstrar, assim como quando uma demonstração esta concluída, também é bastante importante deixar claro a diferença entre o processo de descoberta de uma demonstração (heurística) e a formalização e organização lógica dedutiva de ela, o qual constituem a demonstração propriamente dita.

Praticamente todos os teoremas matemáticos estão compostos por implicações do tipo. (p1  p2 . . .  pn)  q, onde os pi são chamados de premissas ou hipóteses e, q é chamada de conclusão.

“Demonstrar o teorema'' é demonstrar que a implicação é uma tautologia. Note que não estamos tratando de demonstrar que q (a conclusão) é verdadeira, somente que q é verdadeira caso todas as p_i sejam verdadeiras.

Em geral toda demonstração deve começar com as hipóteses, seguidas das tautologias e regras de inferência necessárias, até chegar à conclusão.

Exemplo 2.34

Temos a demonstrar o seguinte: “Dois ângulos estão em planos diferentes, mas cada lado de um deles é paralelo ao lado correspondente do outro e está também na mesma direção. Demonstrar que os dois ângulos são iguais”.

Isto é um teorema fundamental da geometria espacial; a hipótese é:

“Dois ângulos estão em planos diferentes. Cada lado de um é paralelo ao lado correspondente do outro e tem também a mesma direção”.

E sua conclusão é:

“Os dois ângulos são iguais”.

Os principais métodos da teoria da demonstração são:

• Demonstrações diretas.

• Demonstrações indiretas.

2.3.1 Demonstrações diretas.

Toda demonstração direta deve começar com as premissas, seguidas das tautologias e regras de inferência necessárias, até chegar à conclusão; cada passo deve estar acompanhado de sua respectiva justificativa.

Devido à tabela-verdade da implicação, se a proposição p é falsa ( f ), a proposição p  q é verdadeira ( v ), logo não temos nada a demonstrar. Nos estamos interessados no caso que o antecedente p seja verdadeiro ( v ). Nesta seção p e q representam proposições simples ou compostas.

A partir da verdade de p, deduzir a verdade de q, é fazer uma demonstração direta da condicional p  q; isto consiste em uma lista de proposições p1, p2, p3, . . . , pn tais que pn coincide com q e para cada i = 1, 2, 3, 4, . . . , n e pi é evidentemente verdadeira, ou coincide com as premissas, ou é conseqüência imediata de uma ou varias das proposições que lhe precedem na lista.

Exemplo 2.35

Se, trabalhar ou poupar então, comprarei uma casa. Se comprar uma casa, então meu carro guardarei em casa.

Por tanto, se não posso guardar meu carro em casa, então não poupo.

Demonstração.

Sejam p : trabalho, q : poupo, r : comprarei uma casa, s : poderei guardar o carro em casa.

O enunciado anterior podemos escrever na forma:

{[(p  q )  r]  (r  s)}  ( s   q )

Aqui a conclusão é q :  s   q .

1. (p  q )  r . . . premissa.

2. r  s . . . premissa.

3. q  (q  p) . . . tautologia

4. q  (p  q) . (3), comutatividade.

5. q  r . . . (1),(4), silogismo hipotético.

6. q  s . . . (2),(5), silogismo hipotético.

7.  s   q . . . (6), contra-recíproca.

Portanto, o enunciado é válido mesmo que a conclusão seja verdadeira ou falsa.

Exemplo 2.36

Demonstrar que, se x2 + 2x  3 e x = 2a - 1, então a2  1

Demonstrtação.

Considere p: x2 + 2x  3 , r: x = 2a - 1 e q: a2  1. O que temos a demonstrar é que (p  r)  q é proposição verdadeira ( v ).

Com efeito:

1. p: x2 + 2x  3 . . . premissa.

2. r: x = 2a - 1 . . . premissa.

3. p  r: (2a - 1)2 + 2(2a - 1)  3 . . . substituição.

4. p  r: 4a2  4 . . . tautologia.

5. q: a2  1.

6. Portanto, acabamos de mostrar que (p  r)  q .

Assim, a demonstração direta consiste em demonstrar ou deduzir a conclusão q a partir das premissas p1, p2, p3, . . . , pn, aplicando as equivalências tautológicas e as regras de inferência.

Exemplo 2.37

Demonstrar a validade do argumento p, q  r ,  r ├  q.

Demonstrtação.

1. p . . . premissa

2. q  r . . . premissa

3.  r . . . premissa

4.  q . . . (2) e (3), Modus Tollens

Exemplo 2.38

Demonstrar a validade do argumento  p  q , q   r , r  s ├  s  p

Demonstrtação.

Observe que a conclusão q é q :  s  p

1.  p  q . . . premissa

2. q   r . . . premissa

3. r  s . . . premissa

4.  p   r . . . (1), (2), silogismo hipotético

5.  r  s . . . (3), def. de implicação

6.  p  s . . . (4), (5), silogismo hipotético

7.  s    p . . . (6), contra-recíproca

8.  s  p . . . conclusão, (7), negação

Portanto, o argumento é válido.

Exemplo 2.39

Demonstre que se a, b R+ tais que a.b = 1, então a + b  2.

Demonstrtação.

1. a.b = 1 . . . hipótese.

2. 0 < a  1 e 1  b, . . .hipótese auxiliar.

3. 0  (1 - a) e 0  (b - 1) . . . propriedade em R.

4. 0  (1 - a)(b - 1) . . . propriedade em R.

5. 0  b - ab - 1 + a . . . propriedade em R.

6. 0  b - 1 - 1 + a . . . (1), substituição.

7. 2  a + b . . . propriedade em R.

Portanto, a + b  2.

2.3.1.1 Demonstração direta por contra-exemplo.

As demonstrações deste tipo utilizam a equivalência lógica:

“Não é verdade que para todo elemento x, cumpra a propriedade p(x) é logicamente equivalente a; existe algum elemento x que não cumpre a propriedade p(x)”.

isto é, para demonstrar que, não é verdade que se cumpra p(x) para todo x, é necessário e suficiente mostrar que existe pelo menos um x tal que não se cumpra p(x).

Exemplo 2.40

Demonstrar que: Para todo natural n, tem-se n+1 = 5.

Demonstrtação.

Intuímos que o argumento é falso.

Temos que achar um número natural n tal que não cumpra n+1 = 5.

Por exemplo considerar n = 6  N; logo 6 + 1  5 .

Logo, existe um número natural n tal que n + 1  5 .

Portanto, não é verdade que, para todo natural n, tenhamos n+1 =5.

2.3.2 Demonstrações indiretas.

A demonstração indireta estabelece a verdade de uma afirmativa por revelar a falsidade da suposição oposta. Deste modo, ela apresenta certa semelhança com a astúcia do político que procura firmar os méritos de um candidato pela demolição da reputação do seu oponente.

Entre os métodos de demonstrações indiretas, estudaremos os seguintes:

• Por contraposição.

• Por casos.

• Por redução ao absurdo.

• Por árvore de refutação.

2.3.2.1. Demonstração indireta: Por contraposição.

É uma afirmação da forma “se p  q” e consiste em supor  q para mostrar que se cumpre “ p” ; isto é, trata-se de provar que “  q   p” que é logicamente equivalente à afirmação original.

Assim, a proposição ( p  q)  ( q   p) é verdadeiro. Isto é um exemplo da utilidade das verdades lógicas.

Exemplo 2.41

Demonstre que se a, b  R+, tais que a.b = 1, então a + b  2.

Demonstrtação.

1. Suponhamos a + b < 2 . . . hipótese auxiliar.

2. a + b < 2 . . . def. de <.

3. 0 < (a + b)2 < 22 . . . a, b  R+.

4. 2ab + a2+b2 < 4 . . . propriedade em R.

5. 4ab < 2ab + a2+b2 < 4 . . . prop. em R, 2ab  a2+b2.

6. 4ab < 4 (4)- (5), . . . tautologia.

7. ab < 1 . . . propriedade em R.

8. a + b < 2  a.b  1 . . . (1) - (7)

Portanto, a.b = 1  a + b  2.

Observe que temos a tautologia (p  q)  ( q   p), onde p: a.b = 1 e q: a+b  q 2.

Exemplo 2.42

Demonstre que existem infinitos números primos.

Demonstração.

Por definição de número primo, sabemos que são os números naturais maiores do que um (1) e que podemos decompor como o produto de dois fatores: ele mesmo e a unidade. Este são:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, . . .

Sabe-se que em, geral todo número natural podemos escrever como o produto de fatores primos, por exemplo 630=(7)(5)(32)(2).

Suponhamos não existam infinitos números primos; isto é suponhamos exista um último número primo P. Neste caso poderíamos escrever todo o conjunto de números primos na forma:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, . . . , P (2.2)

Com o produto de todos esses números primos, poderíamos escrever um número Q na forma:

Q = (2)(3)(5)(7)(11)(13)(17)(19)(23)(29)(31)(37). . . (P) + 1

este Q é maior do que P. Supostamente Q não pode ser primo, caso contrario um dos qualquer números primos do conjunto (2.2) é um fator de Q, o qual é impossível.

Portanto, supor que existe um último número primo está errado.

2.3.2.2. Demonstração indireta: Por casos.

Para mostrar que uma conclusão q é verdadeira, quando temos uma série premissas (os casos) p1, p2, p3, . . . , pn, n  2 tais que esgotam todas as possibilidades, ou seja que necessariamente se cumpre uma de elas, isto é o enunciado p1  p2  p3  . . .  pn é verdadeira e além disso prova-se que: se p1 implica q, se p2 implica q, . . . , se pn implica q.

Pode então se concluir em forma correta que a proposição q, é verdadeira, já que provou-se o enunciado:

[(p1  p2  p3  . . . pn )  [(p1  q)  (p2  q)  (p3  q) . . .  (pn q)]

e resulta o argumento:

[(p1  p2  p3  . . . pn)  [(p1  q)  (p2  q)  (p3  q) . . . (pn  q)]]  q

é válido.

• Logo, para demonstrar a validade de argumentos cuja conclusão é uma fórmula condicional do tipo p  q, considera-se o antecedente p , como uma premissa adicional e o conseqüente q será a conclusão a ser demonstrada.

De fato, sendo válido o seguinte argumento:

1. p1, p2, p3, . . . , pn, p ├ q

2. ((p1  p2  p3 . . .  pn ) p)  q . . . (1)

3. ((p1  p2  p3 . . .  pn)  p)  q . . . (2), tautologia

4. (p1  p2  p3 . . .  pn)  (p  q) . . . (3), tautologia (exportação).

5. p1  p2  p3 . . .  pn ├ (p  q) é válido . . . (4).

Portanto, a conclusão q é válida.

Exemplo 2.43

Demonstrar a validade do argumento:  ~p  q, q   r , r  s ├  s p.

Demonstração.

Observe que a conclusão q :  s  p.

1. p  q . . . premissa

2. q   r . . . premissa

3.  p   r . . .(1), (2)

4. r  s . . . premissa

1. r  s . . . (4), tautologia.

5.  p  s . . (3), (5) silogismo hipotético.

6.  s  p de (6), tautologia.

7. ( r  s )  ( s  p ) . . . (4)-(7)

Portanto, a conclusão q :  s  p é válida.

2.3.2.3. Demonstração indireta: Por redução ao absurdo.

A demonstração por absurdo mostra a falsidade de uma suposição derivando dela um absurdo flagrante. É um procedimento matemático, mas se assemelha à ironia, que é o procedimento predileto do satirista. A ironia adota, com todas as aparências, uma determinada opinião, que é exagerada e repetida até conduzir a um manifesto absurdo.

Para provar uma conclusão q é verdadeira, temos a supor  q e procedemos de acordo com alguma dos seguintes três casos:

Caso i) Com a suposição extra  q, mostra-se uma afirmação  p contraditória com outra afirmação p mostrada anteriormente.

Isto deve-se ao caso que a afirmação [( q   p)  p]  q é tautologia (Modus Tollens).

Caso ii) Com a suposição extra  q, mostra-se uma afirmação p, logo se prova  p.

Isto deve-se ao caso que a afirmação

[( q  p)  ( q   p)]  q o bem [ q  (p   p)]  q]

é tautologia (Lei do absurdo).

Este modo a demonstrar também é chamado por contradição.

Caso iii) Com a suposição extra  q, mostra-seo valor verdade de q.

Isto deve-se ao fato que a afirmação ( q  q)  q é tautologia.

Então em cada caso podemos concluir corretamente q.

Se bem a definição original de redução ao absurdo é:

“prova da falsidade de um enunciado, ao obter de ele uma conseqüência lógica absurda”.

o que simbolizamos como [q  (p   p)]   q, o usamos em forma positiva para provar a verdade do enunciado q, usando a verdade lógica conhecida como principio do terceiro excluído ( q   q), para inferir corretamente q a partir de   q.

Exemplo 2.44 Caso i)

Demonstrar, que 5  1

Demonstração.

Demonstrarei pelo absurdo.

Seja q : 5  1; a verificar que q é verdadeira.

1. Sabe-se que p : 5 - 1  0 . . . hipótese auxiliar.

2. Suponhamos  q : 5 = 1 . . . hipótese auxiliar.

3. Logo,  p : 5 - 1 = 0 . . .(2).

4.  q   p . . . (2)-(3)

5. ( q   p)  p . . . (1) e (4)

6. q . . . Modus Tollens

Portanto, 5  1 é verdadeiro.

Exemplo 2.45 Caso ii)

Demonstrar, que 5  1

Demonstração.

Demonstrarei pelo absurdo.

Seja q : 5  1; a verificar que q é verdadeira.

1. Seja p : 5 - 1  0 . . . hipótese auxiliar.

2. Suponhamos  q : 5 = 1 . . . hipótese auxiliar.

3. Logo,  p : 5 - 1 = 0 . . .(2).

4. p : 5-1  0 . . . (2).

5.  p  p . . . (3) e (4).

6. q . . . lei do absurdo a:  q  ( p  p).

Portanto, 5  1.

Exemplo 2.46

Temos a mostrar pelo absurdo caso ii) que o argumento p1 , p2 , p3 , . . . , pn ├ q, é verdadeiro.

Demonstração.

Para isto, considera-se a negação da conclusão  q como premissa adicional e conclui-se uma fórmula F (fórmula falsa do tipo r   r).

De fato, sendo q verdadeira tem-ser o seguinte argumento:

1. p1 , p2 , p3 , . . . , ;  q ├F

2. p1 , p2 , p3 , . . . , ├ ( q  F) . . . (1), tautologia (exportação).

3. p1 , p2 , p3 , . . . , ├ (  q  F) . . . (2), implicação material.

4. p1 , p2 , p3 , . . . , ├ (q  F) (3), tautologia (dupla negação).

5. p1 , p2 , p3 , . . . , ├ q . . . propriedade de F.

Portanto, p_1 , p_2 , p_3 , . . . , p_n ; q é válido.

Exemplo 2.47 Caso ii)

Demonstrar, por absurdo, a validade do argumento  p  q , q   r, r  s concluir q :  s  p

Demonstração.

Neste exemplo, podemos considerar q :  s  p , logo:

1. p  q . . . premissa

2. q   r . . . premissa

3. r  s . . . premissa

4.  ( s  p) . . . premissa adicional

5.  p   r . . . (1), (2), silogismo hipotético

6. r  s . . . (3), def. de implicação

7. p  s . . . (5), (6), silogismo hipotético

8.  s  p . . . (7), contraposição

9.  ( s  p)  ( s  p) l . . . de (4), (8), conjunção

10. F isto de (9)

Portanto, a partir das premissas  p  q , q   r, r  s concluir q :  s  p é válido.

A demonstração do seguinte teorema pelo método da contradição é como se indica.

Exemplo 2.48

Demonstrar que: {[p  (p  r)]  [(t  s)  q ]  (p  s)}  q

Demonstração.

1. p  (p  r) . . . premissa.

2. (t  s)  q . . . premissa.

3. (p  s) . . . premissa.

4.  q . . . premissa auxiliar.

5.  (t  s) . . .(2), (4), modus tollens.

6.  t   s . . .(5) lei de Morgan.

7.  t . . .(6) simplificação.

8.  s   t . . .(6) lei comutativa.

9.  s . . .(8) simplificação.

10. s  p . . .(3) lei comutativa.

11. p . .(9), (10) silogismo disjuntivo.

12. t  r . . .(1), (11), modus ponens.

13. t . . .(12) simplificação.

14. t   t . . .(7), (13), conjunção.

15. Contradição.

Portanto, {[p  (p  r)]  [(t  s)  q ]  (p  s)}  q

Itemize.

• Para a demonstração pelo absurdo do Caso iii) apresentamos dois tipos, aquele que estabelece que:

1º. Uma proposição cuja falsidade implica sua verdade é verdadeira; isto é: ( q  q )  q

2º. Uma proposição verdadeira que implica sua própria falsidade é falsa; isto é: (q   q)   q

Exemplo 2.49

Demonstrar que todo número natural, não é menor que si mesmo.

Demonstração.

Temos as proposições p : a número natural, e q :a  a.

A verificar que: p  q

1. Seja p :a número natural . . . hipótese (premissa)

2. a = a . . . propriedade reflexiva

3.  q : a < a . . . hipótese auxiliar

4. a  a . . . . isto de (3)

5. Contradição entre (2) e (4), logo a hipótese auxiliar  q não é certa (é falsa).

6. Então, q é verdadeira.

7. Aplicando ( q  q)  q a (3) e (6) temos q.

8. Como q é verdadeira, temos que p  q é verdadeira.

Portanto, todo número natural, não é menor que si mesmo.

Exemplo 2.50

Escrever números inteiros usando cada um dos dez algarismos uma só vez, de tal modo que a soma desses números seja exatamente 100.

Demonstração.

Suponhamos por exemplo o conjunto de números 19, 28, 37, 46, 50, cada algarismo corresponde só uma vez, sua soma é 180 e não 100.

Poderíamos continuar tentando até obter: 19 +28+30 + 7 +6+5+4 = 99.

Naturalmente a primeira parte do problema é satisfeita, porém não chegamos a obter 100 (segunda parte), porem se escrevemos 19 +28+31 + 7 +6+5+4 = 100. Observe que a primeira parte do problema não é satisfeita, o número 1 repete-se duas vezes.

Observe que se somamos 0+1+2+3+4+5+6+7+8+9 = 45, alguns desses algarismos denotam unidades e outros dezenas.

Suponhamos que o algarismo a seja o das dezenas, então teríamos: 10a+(45- a) = 100 (lembre que a é número natural). Da ultima igualdade segue-se que 9 a = 55, de onde é impossível a existência de a  N.

Supor que as duas partes do problema são simultaneamente satisfeitas, é um flagrante absurdo; assim é impossível satisfazer ao mesmo tempo as duas partes do problema.

Logo, chegamos a demonstrar que as duas partes do problema são incompatíveis.

Nosso raciocínio neste último exemplo foi uma típica demonstração por absurdo [11]. Na demonstração pelo absurdo, podemos aplicar qualquer das formas da lei do absurdo.

2.3.2.4. Demonstração indireta: Árvore de refutação.

Árvore de refutação é um método para verificar a validade de um argumento, análogo à demonstração por absurdo. Para testarmos a validade de um argumento construímos uma lista de fórmulas consistindo de suas premissas p1, p2 , p3 , . . . , pn e a negação de sua conclusão  q que formam a raiz da árvore.

A árvore continua abaixo com a construção de seus ramos por aplicações de regras, que serão especificadas abaixo, e gerando novas linhas na árvore. A árvore termina quando as fórmulas de seus ramos são: variáveis proposicionais, negações de variáveis proposicionais, ou quando encontrarmos em todos os ramos uma fórmula ( f ).

Se encontrarmos em todos os ramos da árvore uma fórmula ( f ), então a nossa tentativa de refutação falhou ou seja, o argumento é válido. Se em algum ramo da árvore não foi possível encontrar uma fórmula ( f ), então refutamos o argumento, isto é, o argumento não é válido.

Regras para a construção de uma árvore de refutação.

As regras para a construção de uma árvore de refutação estão relacionadas com as tabelas verdade já conhecidas. Ao aplicar uma regra em uma fórmula da árvore, temos a observar que.

• A fórmula será marcada ( ) para evitar aplicações repetidas de uma regra em uma mesma fórmula.

• A aplicação de uma regra deve gerar: uma ou duas linhas, um ramo ou dois ramos conforme a regra, e será aplicada em todos os ramos abertos (não fechados com ( X )) aos quais a fórmula pertence.

• A aplicação de uma regra deve gerar: uma ou duas linhas, um ramo ou dois ramos conforme a regra, e será aplicada em todos os ramos abertos (não fechados com ( X ) aos quais a fórmula pertence.

Temos as seguintes regras :

1ª. Regra da dupla negação ()

Uma fórmula do tipo   p gera uma linha e escrevemos na linha. Procedemos assim em todos os ramos abertos aos quais a fórmula   p pertence pois,   p é verdadeira se, e somente se, p é verdadeira.

2ª. Regra da conjunção (  )

Uma fórmula do tipo p  q gera duas linhas e escrevemos, em cada linha, as fórmulas p e q. Procedemos assim em todos os ramos abertos aos quais a fórmula p  q pertence pois, p  q assume valor ( v ) se, e somente, as fórmulas p e q são verdadeiras.

1. p  q

2. p

3. q

3ª. Regra da disjunção (  )

Uma fórmula do tipo p  q gera uma linha e dois ramos e escrevemos, na linha e, em cada ramo, as fórmulas p e q respectivamente. Procedemos assim em todos os ramos abertos aos quais a fórmula p  q pertence pois, p  q assume valor ( v ) se, e somente, a fórmula p é verdadeira ou a fórmula q é verdadeira.

1. p  q

 \

2. p q

4ª. Regra da implicação ( )

Uma fórmula do tipo p  q gera uma linha e dois ramos e escrevemos, na linha e, em cada ramo, as fórmulas  p e q respectivamente. Procedemos assim em todos os ramos abertos aos quais a fórmula p  q pertence pois, p  q assume valor ( v ) se, e somente, a fórmula  p é verdadeira ou a fórmula q é verdadeira.

1. p  q

 \

2.  p q

5ª. Regra da bicondicional ( )

Uma fórmula do tipo p  q gera duas linhas e dois ramos e escrevemos nas linhas as fórmulas p e q em um ramo e as fórmulas  p e  q no outro ramo. Procedemos assim em todos os ramos abertos aos quais a fórmula p  q pertence pois, p  q assume valor ( v ) se, e somente, a fórmula (p  q ) é verdadeira ou a fórmula ( p   q ) é verdadeira.

1. p  q

 \

2. p  p

3. q  q

6ª. Regra da negação da conjunção ( )

Uma fórmula do tipo  (p  q) gera uma linha e dois ramos e escrevemos, na linha e, em cada ramo, as fórmulas  p e  q respectivamente. Procedemos assim em todos os ramos abertos aos quais a fórmula  (p  q) pertence pois,  (p  q) assume valor ( v ) se, e somente, a fórmula  p é verdadeira ou a fórmula  q é verdadeira.

1.  (p  q)

 \

2.  p  q

7ª. Regra da negação da disjunção ( )

Uma fórmula do tipo  (p  q) gera duas linhas e escrevemos, em cada linha, as fórmulas  p e  q . Procedemos assim em todos os ramos abertos aos quais a fórmula  (p  q) pertence pois,  (p  q) assume valor ( v ) se, e somente, as fórmulas  p e  q são verdadeiras.

1.  (p  q)

2.  p

3.  q

8ª. Regra da negação da implicação (  )

Uma fórmula do tipo  ( p  q) gera duas linhas e escrevemos, em cada linha, as fórmulas p e  q. Procedemos assim em todos os ramos abertos aos quais a fórmula  ( p  q) pertence pois,  ( p  q) assume valor ( v ) se, e somente, as fórmulas p e  q são verdadeiras.

1.  (p  q)

2. p

3.  q

9ª. Regra da negação da bicondicional (  )

Uma fórmula do tipo ( (p  q)) gera duas linhas e dois ramos e escrevemos nas linhas as fórmulas  p e q em um ramo e as fórmulas p e  q no outro ramo. Procedemos assim em todos os ramos abertos aos quais a fórmula  (p  q) pertence pois,  (p  q) assume valor ( v ) se, e somente, a fórmula ( p  q) é verdadeira ou a fórmula (p   q) é verdadeira.

1.  (p  q)

 \

2.  p p

3.  q q

10ª. Ramo fechado.

Um ramo será fechado se em ele existem uma fórmula p e sua negação  p e escrevemos ( X ) no final do ramo.

1.  p

2. p

3. ( X )

Observação 2.3

1. As regras dadas para construir árvores de refutação se aplicam em cada linha ao conectivo principal da fórmula e não a sub-fórmulas. Por exemplo:

1. p    q 

2. p  q   (incorreto !)

2. Não importa a ordem em que as regras são aplicadas; no entanto, é mais eficiente aplicar as regras, primeiramente, em fórmulas que não resultam em ramificações.

3. Cada linha gerada deve ser justificada indicando a respectiva linha de origem na qual foi aplicada a regra e também a regra usada.

4. Fórmula na qual foi aplicada alguma regra deve ser marcada (  ) para evitar aplicações repetidas da mesma.

Exemplo 2.51

Construir uma árvore de refutação para mostrar que: p  q ├   p

Solução

Escrevemos a premissa seguidamente a negação da conclusão:

1. p  q

2.    p

Sabemos que p  q é verdadeira se, e somente se, p e q são ambas verdadeiras; daí, podemos substituir p  q por p e q gerando as linhas (3) e (4.), respectivamente, e marcando (  ) a fórmula p  q. (Uma fórmula marcada não poderá mais ser utilizada na construção da árvore!)

1. p  q 

2.    p

3. p

4. q

Como    p é verdadeira se, e somente se,  p é verdadeira, marcamos    p e substituímos por  p gerando a linha (5).

1. p  q 

2.    p 

3. p

4. q

5.  p

A árvore terminou pois das premissas e da negação da conclusão obtivemos variáveis proposicionais ou negações de variáveis proposicionais.

Por outro lado encontramos nas linhas (3) e (5) uma fórmula ( f ), ou seja, nossa tentativa de refutação falhou e portanto o argumento é válido. Isso será expresso escrevendo um ( X ) no final da lista, gerando a linha (6) e fechando o único ramo da árvore.

1. p  q 

2.    p 

3. p

4. q

5.  p

6. ( X )

A árvore de refutação está completa. A nossa busca para uma refutação do argumento dado falhou e, portanto, o argumento p  q ├   p é válido.

Exemplo 2.52

Construir uma árvore de refutação para mostrar que : p  q,  p ├ q

Solução

Iniciamos a árvore escrevendo a lista de fórmulas as premissas e a negação da conclusão:

1. p  q

2.  p

3.  q

Sabemos que p  q é verdadeira se, e somente se, p é verdadeira ou q é verdadeira. Para representar esse fato, marcamos p  q e ramificamos a árvore, gerando a linha 4. com dois ramos:

1. p  q 

2.  p

3.  q

 \

4. p q

A árvore terminou pois das premissas e da negação da conclusão obtivemos variáveis proposicionais ou negações de variáveis proposicionais.

Por outro lado encontramos uma fórmula ( f ) em um ramo, nas linhas (2) e (4) e no outro ramo, nas linhas (3) e (4), ou seja, nossa tentativa de refutação falhou e portanto o argumento é válido. Isso será expresso escrevendo um ( X ) no final de cada ramo da lista gerando a linha (5) e fechando os dois ramos da árvore.

1. p  q 

2.  p

3.  q

 \

4. p q

5. (X) (X)

A árvore de refutação está completa. Como a tentativa de refutação falhou nos dois ramos, o argumento dado é válido.

Exemplo 2.53

Construir uma árvore de refutação para verificar a validade do seguinte argumento: p  q, p ├  q.

1. p  q

2. p

3.   q 

Temos que   q é equivalente a q; daí, marcamos   q e escrevemos q gerando a linha (4).

1. p  q

2. p

3.   q 

4. q

Como no exemplo anterior, marcamos p  q e ramificamos a árvore gerando a linha (5) com dois ramos:

1. p  q 

2. p

3.   q 

4. q

 \

5. p q

A árvore terminou e nos dois ramos não há contradições, ou seja, uma fórmula ( f ). Neste caso os ramos não serão fechados e o argumento não é válido.

Exemplo 2.54

Verificar a validade do argumento: p  r  s, r  s  q , p  q

Solução

1. p  r  s  hipótese.

2. r  s  q  hipótese.

3.  ( p  q )  negação da tese.

4. p (3), negação de 

5.  q (3), negação de 

 \

6.  p r  s  de (4) - (6) e (1), 

7. (X)  \

8. r s (6) 

 \  \

9. (r  s) q  (r  s) q  (2), 

 \  \ \

10.  r  s ( X )  r  s ( X )  

11. (X) ? (9), (5) (X) ? (9),(5) (10), (8)

Temos neste caso dois ramos que não fecharam e, portanto, o argumento não é válido.

Exemplo 2.55

Construir uma árvore de refutação para verificar se a fórmula (p  q)  (p   q) é uma tautologia:

Solução

1.  ((p  q)  (p   q))  negação da tese.

2.  (p  q)  (1.), negação de 

3.  (p   q)  (1.), negação de 

4. p (2), negação de 

5.  q (2), negação de 

 \

6.  p  q (3), negação 

7. ( X ) ( X ) (6), (5)

Todos os ramos estão fechados; assim a fórmula é válida, ou seja, é uma tautologia.