1.4 REGLAS DE PRUEBA. (MÉTODOS DE DEMOSTRACIÓN).

Teóricamente, todos los teoremas de la lógica proposicional se pueden demostrar utilizando solamente los axiomas y las reglas de validez; sin embargo, se establecen reglas de prueba y métodos de demostración con el fin de abreviar el proceso deductivo.
A continuación se presentan los principales métodos de demostración y reglas de prueba del cálculo proposicional.


1.4.1 Método directo o de Hipótesis auxiliar. Este método se utiliza para la demostración de implicaciones, y dice así: Sean R y S fórmulas. Si el suponer que R es verdadera, se puede hacer una demostración de que S es verdadera, entonces la implicación R Þ S es una fórmula verdadera.

Justificación: La tabla de verdad del condicional muestra que con antecedente verdadero, hay implicación, sólo en el caso en el que el consecuente es verdadero.

Esquema Operativo General: Para demostrar que una fórmula del tipo
R ÞS es teorema, se procederá así:


Ejemplos


  1. Demuestre que: si a y b son números pares, entonces a + b es número par.
    Solución:

    Suponga que a y b son números pares, (Hipótesis auxiliar) luego, a = 2n y b = 2m con n, m Î Z . Entonces, a + b = 2n+ 2m =2(n + m); (n + m) ÎZ (enteros). Por tanto, si n + m = k; a + b = 2k, es decir, a + b es un número par.


  2. Dadas P, Q y R fórmulas, pruebe que:
    (P ÞQ) Þ ((Q Þ R) Þ (P Þ R)) es un teorema.

    Solución:


    1. P Þ Q (hipótesis auxiliar)
    2. Q Þ R (hipótesis auxiliar)
    3. P (Hipótesis auxiliar)
    4. Q (RV1 en 1 y 3)
    5. R (RV1 en 2 y 4)
    6. P Þ R (método directo en 3 y 5)
    7. (Q Þ R) Þ (P ÞR) (método directo en 2 y 6)
    8. (P Þ Q) Þ ((Q Þ R) Þ (P Þ R)) (método directo en 1 y 7)

    La anterior solución, muestra el esquema de la demostración, donde se hace una aplicación reiterada del método directo ya que lo que se debe probar es una cadena de implicaciones.
    A medida que se toman las hipótesis auxiliares, se va desplazando la demostración hacia la derecha, para mostrar que las siguientes afirmaciones están subordinadas a las hipótesis anteriores. Cuando se comienza a establecer conclusiones se vuelve a desplazar la demostración hacia la izquierda, hasta establecer la conclusión definitiva en la teoría original, es decir, aquella donde no hay hipótesis auxiliares.


  3. Si m y n son números enteros impares, entonces su producto mn es un entero impar.

    Solución:

    Suponga que m y n son enteros impares (hipótesis auxiliar), entonces:

    m = 2k1 + 1 y n = 2k2 + 1, con k1 y k2 enteros.

    Por tanto, mn = ( 2k1 + 1 ) ( 2k2+ 1 ) =
    =4k1k2 + 2k1+2k2 +1 = 2(2k1k2 + k1 + k2 ) + 1.

    Ahora (2k1k2 + k1 + k2 ) Î Z, luego, 2k1k2 + k1 + k2 = k.

    Esto es: mn = 2k + 1, k ÎZ.

    Luego mn es impar y por tanto, se concluye que: Si m y n son impares, mn también es impar.


1.4.2 Adjunción. Si P es verdadera, entonces P Ú Q es verdadera.

Justificación:

1. P (hipótesis).
2. P Þ P Ú Q A2
3. P ÚQ RV1 entre 1. y 2.

1.4.3 Conmutatividad de la Ú. Si P Ú Q es verdadera, entonces Q Ú P es verdadera.

Justificación:
1. P Ú Q (hipótesis)
2. P Ú Q Þ Q Ú P A3
3. Q Ú P RV1 entre 1. y 2.

1.4.4 Leyes de la implicación.

1.4.4.1 Si Q es verdadera, entonces P Þ Q es verdadera, cualquiera que sea P.

Justificación:

1. Q (hipótesis).
2. Q Ú Ø P (adjunción).
3. Ø P Ú Q conmutativa.
4. P Þ Q def. de Þ

1.4.4.2 Si Ø P es verdadera, entonces P Þ Q es verdadera.

1.4.5 Silogismo.Si P Þ Q y Q Þ R son verdaderas, entonces P Þ R es verdadera.
Justificación:

1. P Þ Q hipótesis.
2. Q Þ R hipótesis.
3. (Q Þ R) Þ ( Ø P Ú Q Þ Ø P Ú R) A4.
4. (Ø P Ú Q) Þ (Ø P Ú R) RV1 2. y 3.
5. (P Þ Q) Þ (P Þ R) def. de Þ .
6. P Þ R   Rv1 1. y 5.

1.4.6 Medio excluido. P Ú Ø P es verdadera, cualquiera que sea P.

Justificación:

1. PÞ P Ú P A2.

2. P Ú P Þ P A1.

3. PÞ P Silogismo 1. 2.

4.Ø P Ú P def. de Þ

5. PÚ Ø P conmutativa.

1.4.7 Doble Negación.


1.4.7.1
P Þ Ø Ø P es verdadera.

Justificación:

1.ØP Ú Ø(Ø P) medio excluido.

2. P ÞØ Ø P def. deÞ .


1.4.7.2 ØØP ÞP es verdadera .

Justificación:

1. ØP Þ Ø Ø (Ø P) por 1.4.7.1.

2. Ø P Ú P Þ Ø ØØ P Ú P adic. con Ú a 1.

3. ØØØ P Ú P RV1 en 2.

4. Ø Ø P Þ P def. de Þ.


Implicaciones asociadas a P Þ Q. Considerando P Þ Q como implicación directa, están asociadas las siguientes implicaciones:


1.4.8 Leyes del contrarrecíproco.

1.4.8.1 Si PÞ Q es verdadera, entonces Ø Q Þ ØP es verdadera.

Justificación:

1. P ÞQ hipótesis.

2. Q Þ Ø Ø Q doble neg.

3. Q ÚØ P ÞØ Ø Q ÚØ P adic. conÚ a 2.

4. (PÞ Q) Þ (Ø Q Þ Ø P) def. de Þ .

5. Ø Q Þ ØP  RV1 en 1. y 4.

1.4.8.2 Si Ø Q Þ Ø P es verdadera, entonces P Þ Q es verdadera.

Estas leyes fundamentan un método de demostración muy utilizado en matemáticas, conocido como método de demostración por el contrarrecíproco y consiste en demostrar la implicación contrarrecíproca para poder afirmar que la implicaión directa es teorema.

Ejemplo: Demostrar que si m2 es un número par, entonces m es un número par.

Para establecer la verdad de la proposición se puede demostar su contrarrecíproca:

Si m no es un número par, entonces m2 no es un número par.

En efecto:

Suponga que m es impar, luego, m = 2k1 + 1, con k1 Î Z.

Por tanto:
m2 = (2k1 + 1)2 = 4k12 + 4k1 + 1 =2(2k12 + 2k1) + 1,
con (2k12 + 2k1) Î Z.

Sea n = 2k12 + 2k1.
Luego, m2 = 2n + 1. Esto es, m2 es impar.

En consecuencia, si m es impar, entonces m2 es impar y por tanto, si m2 es par entonces m es par.


1.4.9 Propiedades de la conjunción.

1.4.9.1
Si P Ù Q es verdadera, entonces:

  • P es verdadera.
  • Q es verdadera.

Justificación:
1. PÙ Q Hipótesis.

2. Ø P Þ ØP ÚØ Q A2.

3. Ø (Ø P Ú Ø Q) Þ Ø Ø P contrarrecíproco.

4. Ø Ø P Þ P Doble negación.

5. Ø (Ø P ÚØ Q) Þ P Silogismo 3 y 4.

6. P Ù Q Þ P Def. de Ù en 5.

7. P RV1 en 1 y 6.

1.4.9.2
Si P y Q son verdaderas, entonces P Ù Q es verdadera.
Justificación:

1. P Hipótesis.

2. Q Hipótesis.

3. P Þ Q Ley de Þ.

4. Ø Q Þ Ø P contrar.

5. Ø P Ú Ø Q ÞØ P ÚØ P Adic con Ú

6. Ø P Ú Ø P ÞØ P A1.

7. Ø P Ú Ø Q ÞØ P Silogismo.

8. P Þ Ø ( Ø P Ú Ø Q) contrar.

9. P Þ P Ù Q Def. de Ù.

10. P Ù Q RV1. 1 y 9

1.4.10 Método de demostración por reducción al absurdo. Una de las condiciones que debe verificar el conjunto de axiomas, dado para la teoría, es la consistencia. Es decir, a partir de ellos no pueden derivarse, por aplicación de las reglas lógicas, contradicciones, o sea, fórmulas de la forma R Ù Ø R. Esto constituye la fundamentación del método de demostración por reducción al absurdo, el cual puede enunciarse así:

"Si al suponer que la proposición Ø P es un teorema, se puede establecer como teorema una proposición contradictoria, entonces el supuesto Ø P es falso, es decir, la proposición P es un teorema".
Justificación:

1. Ø P Þ R Ù Ø R método dir.

2. Ø P Þ Ø (Ø R Ú Ø Ø R) def. de Ù en 1.

3. Ø R Ú Ø Ø R Þ P contrar. en 2.

4. P RV1 en 3.



Procedimiento para la Aplicación del Método. Suponga que se va a demostrar que P es teorema por aplicación del método de reducción al absurdo, entonces, se siguen los siguientes pasos:

  • Suponga que Ø P es verdadero.
  • A partir de esta hipótesis se razona lógicamente hasta obtener como conclusión la conjunción de una fórmula con su negación.
  • Por el método de reducción al absurdo, se concluye que P es teorema.


Ejemplo: Utilizando el método de reducción al absurdo, demostrar que el número real es irracional.

Solución:

Suponga que no es irracional, luego es racional y por tanto = p/q, q ¹ 0, p, q Î Z y p, q primos relativos.

2 = p2/q2, 2q2 = p2, de donde p2 es número par y por lo tanto lo es p, esto es p = 2k, k Î Z, entonces p2 = 4k2. Se concluye, entonces, que 2q2 = 4k2; q2 = 2k2, q2 es número par, luego q es un número par.

Luego p y q tienen factor común 2. ¡Absurdo! puesto que p y q son primos relativos. Por tanto, es número irracional.

1.4.11 Método de Demostración por Disyunción de Casos (Ley del Silogismo disyuntivo).

Sean P, Q, R y T fórmulas. Si P Ú Q, P Þ R, Q Þ T son verdaderas, entonces, R Ú T es verdadera.

Justificación:

1. P Ú Q hipótesis.

2. P Þ R hipótesis.

3. Q Þ T hipótesis.

4. P Ú Q Þ R Ú T adic. de Þ 2 y 3.

5. R Ú T RV1 entre 1 y 4.

Casos Particulares.

1.4.11.1
Si P Ú Q, P Þ R y Q Þ R son verdaderas, entonces R es verdadera.

1.4.11.2 Si P Þ R y Ø P Þ R son verdaderas, entonces R es verdadera.

Ejemplo: Demostrar que si x es un númeo real, entonces x2 ³ 0

Solución. Suponga que x es un número real, luego, x < 0 Ú x = 0 Ú
x < 0.

Si x < 0, entonces - x > 0 y (-x)(-x) > 0, x2 > 0.

Si x = 0, entonces x.x = 0.0 = 0, x2 = 0.

Si x > 0, entonces x.x > 0, x2> 0.

Luego, x2 >0 Ú x2 = 0, o sea, x2 ³ 0.

Por tanto, si x es un número real, entonces x2 ³ 0.


Manejo de la Equivalencia.Para probar que una equivalencia, P Û Q, es teorema, se puede usar el siguiente procedimiento:
  • Probar independientemente cada una de las implicaciones, P Þ Q y Q Þ P, y mediante la conjunción obtener la equivalencia.
  • Ejemplo: Demuestre que P Ù (Q Ù R) Û (P Ù Q) Ù R.

Solución.

1. P Ù (Q Ù R) hipótesis auxiliar.

2. P simplificación en 1.

3. Q Ù R simplificación en 1.

4. Q simplificaicón en 3.

5. R simplificación en 3.

6. P Ù Q conjunción 2 y 4.

7. (P Ù Q) Ù R conjunción 6 y 5.

8. P Ù (Q Ù R) Þ ( P Ù Q) Ù R método directo 1 y 7.

Ahora, se establece la otra implicación

1. (P Ù Q) Ù R hipótesis auxiliar.

2. P Ù Q simplificación en 1.

3. R simplificación en 1.

4. P simplificación 2.

5. Q simplificación en 2.

6. Q Ù R conjunción de 5 y 3.

7. P Ù (Q Ù R) conjunción de 4 y 6.

8. (P Ù Q) Ù R Þ P Ù (Q Ù R) método directo 1 y 7.

 

De las dos demostraciones anteriores, se concluye que:

P Ù (Q Ù R) Û (P Ù Q) Ù R


Ejercicios 1.4

  1. Simbolizar los siguientes enunciados:
  • No hace frio pero llueve.
  • O se protege la flora y la fauna, o se quebrará el equilibrio ecológico.
  • La deserción escolar disminuirá si y sólo sí se mejoran las condicones de la población y se moderniza la educación.

 

2. Para cada enunciado escriba su recíproco, contrarrecíproco y contrario.

  • si una función es derivable en un punto, entonces es continua en dicho punto.
  • Si una figura plana es un cuadrado, entonces es un rectángulo.
  • si una matriz cuadrada tiene inversa, entonces su determinante es distinto de cero.

 

3. Demuestre que los siguientes enunciados son teoremas:

  • ((P ® Q) Ù ((R ® Q)) « ((P Ú R) ® Q).
  • ((P ® Q) Ù (P ® R)) « (P ® (Q Ù R)).

 

4. justifique cada regla de prueba:

  • Si P ® Q es verdadera, entonces, R Ù P ® Q es verdadera.
  • Si P Ú Q ® R es verdadera, entonces, Q ® R es verdadera.
  • Si Q ÙØ Q es verdadera, entonces, P es verdadera.
  • Si P Ú Q y Ø P son verdaderas, entonces, Q es verdadera.

5. demuestre los suguientes teoremas:

  • (P ® (Q Ú R) « ((P Ù Ø vQ) ® R).
  • (P ® Q) ® ((Q ® R) ® (P ® R)).
  • P ® (Q ® P Ù Q).
  • (P ® (Q ® R)) « ((P Ù Q) ® R)
  • ((P ® Q) Ù (P ® R)) « (P ® (Q Ù R)).

6. En cada numeral se dá una lista de premisas, escriba los pasos, que conducen a la conclusión, justificando cada uno de ellos.

T ®Ø S                                                                 P Ù Q ® R

F ®Ø T                                                                 S ÚØ R

S Ú Ø T                                                           T Ù ØØ (P Ù Q)

 

Ø(P Ù Q) ® R                                                         P Ú (Q Ù R)

Ø(R Ú S) P                                                           S Ú T

                                                                           S ®Ø(P Ú Q)  T

 

Ø(P Ú Ø Q)                                                             Ø Q ®Ø P

R                                                                           Q ® (R Ù S)

Q ® (R ® S) S                                                     Ø Ø P

 

P ® R                                                                    P ® S

P ® Q                                                                    P Ù Q

Ø Q Ú Ø Ø P                                                      S Ù R ® Ø T

                                                                            Q ® Ø T

7. Demuestre que los siguientes conjuntos de premisas son inconsistentes, deduciendo una contradicción para cada caso.

 

Ø Q ® R                             T ® P                              T Ú Ø R

Ø R Ú S                               T Ù R                               Ø (R ® S)

Ø(P Ú Q)                             Q ®Ø R                            T ® S

Ø P ® Ø S                           (P Ú S) ® Q

 

x =1 ® y < x                                                            R ® (R Ù Q)

y < x ® y = 0                                                         Ø S Ú R

Ø(y = 0 Ú x ¹ 1)                                                       Ø T ÚØ Q

                                                                             S Ù T

8. Simbolice el siguiente razonamiento y demuestre la conclusión dada a partir de las siguientes premisas:

  • Si el partido A gana las elecciones, tendrá mayoría en el congreso.
  • Sí tiene mayoría en el congreso, el presidente podrá cumplir el programa de gobieno propuesto.
  • O el presidente no podrá cumplir el programa propuesto o la oposición lo atacará duramente.
  • Pero la oposición no lo atacará duramente.
Conclusión: El partido A no ganará las elecciones
 
9. Use cualquier método de demostración para probar los siguientes teoremas:
  • El producto de un número par, por otro impar es un número par.
  • Se dice que el entero t divide al entero a y se escribe t½ a si y sólo si a =kt para algún K Î Z. Demuestre que si t½ a y t½ b entonces t½ (ma + nb), siendo m y n enteros arbitrarios.
  • Si q es un número racional demuestre que q + es un número irracional.

10. Demuestre que si, P Þ Q es verdadera, entonces:

P Ú R Þ Q Ú R

P Ú R Þ R Ú Q

R Ú P Þ R Ú Q

R Ú P Þ Q Ú R

son verdaderas.

11. Demuestre que si, P Þ Q y R Þ S son verdaderas, entonces:

P Ú R Þ Q Ú S
P Ù R Þ Q Ù S

son verdaderas.
 

12. Demuestre que :

a. Si P Û Q es verdadera, entonces, son verdaderas:

  • Ø P Û ØQ.
  • R Ú P Û R Ú Q.
  • R Ù P Û R Ù Q.
  • (R Þ P) Û (R Þ Q).
  • (P Þ R) Û (Q Þ R).
  • (P Û R) Û (Q Û R).
  • Q Û P.

b. Si P Û Q y Q Û R son verdaderas, entonces, P Û R es verdadera.

13. Demuestre los siguientes teoremas:
 

  • P Û P
  • P ÛØ ØP (doble negación).
  • P Ù P Û P (idempotencia).
  • P Ú P Û P (idempotencia).
  • P Ú (Q Ú R) Û ( P Ú Q) Ú R (ley asociativa).
  • P Ù (Q Ù R) Û ( P Ù Q) Ù R (ley asociativa).
  • (P Þ Q) Û (Ø Q Þ Ø P). (ley del contrarecíproco).
  • P Ú Q Û Q Ú P. (ley conmutativa).
  • P Ù Q Û Q Ù P. (ley conmutativa)
  • P Ù (Q Ú R) Û (P Ù Q) Ú (P Ù R) (distributivitividad).
  • P Ú (Q Ù R) Û (P Ú Q) Ù (P Ú R) (distributivitividad).
  • Ø(P Ú Q) ÛØ P Ù ØQ (ley de Morgan).
  • Ø(P Ù Q) ÛØ P Ú ØQ (ley de Morgan).
  • Ø(P Þ Q) Û P Ù Ø Q.
  • P Ú Q Û (Ø P Þ Q).