lunes, 19 de diciembre de 2011

TABLAS DE VERDAD


Estas tablas pueden construirse haciendo una interpretación de los signos lógicos,Ø, Ù, Ú, ®, «,como: no, o, y, si…entonces, sí y sólo si, respectivamente. La interpretación corresponde al sentido que estas operaciones tienen dentro del razonamiento.
Puede establecerse una correspondencia entre los resultados de estas tablas y la deducción lógico matemática. En consecuencia, las tablas de verdad constituyen un método de decisión para chequear si una proposición es o no un teorema.
Para la construcción de la tabla se asignará el valor 1(uno) a una proposición cierta y 0 (cero) a una proposición falsa.
Negación: El valor de verdad de la negación es el contrario de la proposición negada.
P
Ø P
1
0
0
1

 
Disyunción: La disyunción solamente es falsa si lo son sus dos componentes.
P
Q
P Ú Q
1
1
1
1
0
1
0
1
1
0
0
0

 
Conjunción: Solamente si las componentes de la conjunción son ciertas, la conjunción es cierta.
P
Q
Ù Q
1
1
1
1
0
0
0
1
0
0
0
0

 
Condicional:  El condicional solamente es falso cuando el antecedente es verdadero y el consecuente es falso. De la verdad no se puede seguir la falsedad.
P
Q
P®Q
1
1
1
1
0
0
0
1
1
0
0
1

 
Bicondicional: El bicondicional solamente es cierto si sus componentes tienen el mismo valor de verdad.
P
Q
P« Q
1
1
1
1
0
0
0
1
0
0
0
1

 
Se denomina tautología una proposición que es cierta para cualquier valor de verdad de sus componentes. Por tanto, laúltima columna de su tabla de verdad estará formada únicamente por unos.

Contradicción es la negación de una tautología, luego es una proposición falsa cualesquiera sea el valor de verdad de sus componentes. La última columna de la tabla de verdad de una contradicción estará formada únicamente por ceros.

Ejercicios 1.3

1. Sean P, Q, R y S fórmulas. Si se sabe únicamente que P es verdadero, ¿Qué puede afirmarse del valor de verdad de cada una las proposiciones siguientes?
  • P Ù Q           R ® P                   S ®Ø P
  • R Ú P       P ® Q             R® (S® P)
  • Ù P       P ® P Ú S        P Ú S ® (Q Ù Ø P)
  • S ÚØ P       Ø P ® Q Ù R     Q Ù Ø P ® R Ù Q

2. ¿Qué puede concluirse de cada una de las proposiciones anteriores, en los siguientes casos?
  • Si P es falsa.
  • Si P es falsa, Q es verdadera y R es verdadera.

3. Sean P, Q y R fórmulas , entonces:
  • Si R Ú P ® Q Ù P es falsa y P es falsa; ¿Qué puede afirmarse de R y de Q?.
  • Si Q Þ Q Ù P es verdadera y P es falsa; ¿Qué puede afirmarse de Q?.
  • Si R Ù P Þ Ù P es falsa; ¿Qué puede afirmarse de P, Q y R?.
  • Si (Q Ú R) ® (P Ù Q) Ú R es falsa; ¿Qué puede afirmarse de P, Q y R?.
  • Si (P Þ Q) Þ ( R Ú P Þ R Ú Q) es verdadera; ¿Qué puede afirmarse de P, Q y R?

4. Sean P, Q y R fórmulas. Determinar cuales de las siguientes proposiciones son tautologías:
  • P Ù Q ® P Ù R                  (P ® Q ) ® ( Ø Q ® P )
  • P ® P Ù Q                       (P « Q) Ù (P Ù Ø Q)
  • P Ù Ø (Q Ú P)                    P Ù Ø ((P Ú Q) Ú R)
  • (P ® (Q Ú Ø P)) ® Ø Q       P Ú (Ø P Ú R)
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í:
  • Se supone que el antecedente R es verdadero. A R se le llama hipótesis auxiliar.
  • A partir de la hipótesis, se construye un argumento lógico en el cual se pueden utilizar los axiomas y los teoremas ya probados, mediante la aplicación de las reglas de validez, para llegar a la fórmula S como conclusión o tesis.
  • En este punto concluye la prueba y queda establecida la verdad de R ÞS.

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.

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

    Solución:

    1. Þ Q (hipótesis auxiliar)
    2. Þ R (hipótesis auxiliar)
    3. P (Hipótesis auxiliar)
    4. Q (RV1 en 1 y 3)
    5. R (RV1 en 2 y 4)
    6. Þ 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.

  1. 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 = 2k+ 1, con ky kenteros.

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

    Ahora (2k1k+ k+ k
    Î Z, luego, 2k1k+ k+ k= 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 
Ú Þ Ú 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. 
Ø Ú 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) Þ Ø Ú Þ Ø Ú R) A4.
4. (
Ø Ú Q) Þ (Ø Ú 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 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) medio excluido.

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


1.4.7.2 
ØØÞP es verdadera .

Justificación:

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

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

3. 
ØØØ Ú 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:
  • Þ P llamada implicación reciproca.
  • Ø Q Þ Ø P llamada implicación contrarrecíproca.
  • Ø P Þ Ø Q llamada implicación contraria.

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 dedemostració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 mes 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:
m= (2k1 + 1)= 4k12 + 4k1 + 1 =
http://huitoto.udea.edu.co/SistemasDiscretos/contenido/imagenes/Image1.gif2(2k12 + 2k1) + 1,
con (2k12 + 2k1
ΠZ.

Sea n = 2k12 + 2k1.
Luego, m2 = 2n + 1. Esto es, mes 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 Þ ØÚØ 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 http://huitoto.udea.edu.co/SistemasDiscretos/contenido/imagenes/r2.gifes irracional.

Solución:

Suponga que 
http://huitoto.udea.edu.co/SistemasDiscretos/contenido/imagenes/r2.gifno es irracional, luego es racional y por tanto http://huitoto.udea.edu.co/SistemasDiscretos/contenido/imagenes/r2.gif = p/q, q ¹ 0, p, q Î Z y p, q primos relativos.

2 = p2/q2, 2q= p2, de donde pes número par y por lo tanto lo es p, esto es p = 2k, k 
ΠZ, entonces p= 4k2. Se concluye, entonces, que 2q= 4k2; q= 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,
http://huitoto.udea.edu.co/SistemasDiscretos/contenido/imagenes/r2.gif 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, x> 0.

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

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

Luego, x>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:
Ù (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)).
  • ® (Q ® P Ù Q).
  • (P ® (Q ® R)) http://huitoto.udea.edu.co/SistemasDiscretos/contenido/imagenes/Image2.gif« ((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.
®Ø S                                                                 P Ù Q ® R
®Ø T                                                                 S ÚØ R
Ú F http://huitoto.udea.edu.co/SistemasDiscretos/contenido/imagenes/Image3.gif Ø T                                                           T Ù Ø S http://huitoto.udea.edu.co/SistemasDiscretos/contenido/imagenes/Image3.gifØ (P Ù Q)

Ø(P Ù Q) ® R                                                         P Ú (Q Ù R)
Ø(R Ú S) http://huitoto.udea.edu.co/SistemasDiscretos/contenido/imagenes/Image3.gifP                                                           S Ú T
                                                                           S ®Ø(P Ú Q)  http://huitoto.udea.edu.co/SistemasDiscretos/contenido/imagenes/Image3.gifT

Ø(P Ú Ø Q)                                                             Ø Q ®Ø P
R                                                                           Q ® (R Ù S)
® (R ® S) http://huitoto.udea.edu.co/SistemasDiscretos/contenido/imagenes/Image3.gifS                                                     Ø R http://huitoto.udea.edu.co/SistemasDiscretos/contenido/imagenes/Image3.gif Ø P

® R                                                                    P ® S
® Q                                                                    P Ù Q
Ø Q Ú Ø R http://huitoto.udea.edu.co/SistemasDiscretos/contenido/imagenes/Image3.gif Ø P                                                      S Ù R ® Ø T
                                                                            Q ® R http://huitoto.udea.edu.co/SistemasDiscretos/contenido/imagenes/Image3.gif Ø 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 + http://huitoto.udea.edu.co/SistemasDiscretos/contenido/imagenes/r2.gifes 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.
  • Ú P Û R Ú Q.
  • Ù 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 (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).
  • Ú Q Û Q Ú P. (ley conmutativa).
  • Ù Q Û Q Ù P. (ley conmutativa)
  • Ù (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).