2.2: Introducción a la lógica

En la sección anterior, saltamos de cabeza primero e intentamos probar varios teoremas en el contexto de la teoría de números sin una comprensión formal de lo que estábamos haciendo. Probablemente, muchos problemas burbujearon a la superficie. ¿Qué es una prueba? ¿Qué tipo de declaraciones requieren pruebas? ¿Qué debe implicar una prueba? ¿Cómo debe estructurarse una prueba? Demos un paso atrás y hagamos un examen más cuidadoso de lo que realmente estamos haciendo. En las dos secciones siguientes, presentaremos los fundamentos de la lógica proposicional, también conocida como cálculo proposicional o, a veces, lógica de orden cero.

Definición 2.16. Una proposición es una frase que o bien es verdadera o falsa pero nunca ambas. El valor de verdad (o valor lógico) de una proposición se refiere a su atributo de ser verdadero o falso.

Por ejemplo, la frase “Todos los perros tienen cuatro patas” es una proposición falsa. No obstante, la frase perfectamente buena “x = 1” no es una proposición por sí misma ya que en realidad no sabemos qué es x.

Problema 2.17. Determinar si cada uno de los siguientes es una proposición. Explica tu razonamiento.

(a) Todos los autos son de color rojo.

(b) Toda persona cuyo nombre comience por J tiene el nombre Joe.

(c) x ² = 4.

(d) Existe un número real x tal que x ² = 4.

(e) Para todos los números reales x, x ² = 4.

(f) √2 es un número irracional.

(g) p es primo.

h) ¿Está lloviendo?

(i) Lloverá mañana

(j) Led Zeppelin es la mejor banda de todos los tiempos.

Las dos últimas frases del problema anterior pueden suscitar debate. No es tan importante que lleguemos a un consenso en cuanto a si alguna de estas dos frases es en realidad una proposición o no. La buena noticia es que en matemáticas no encontramos afirmaciones cuyo valor de verdad dependa ni del futuro ni de la opinión.

Dadas dos proposiciones, podemos formar proposiciones más complicadas usando conectivas lógicas.

Definición 2.18. Que A y B sean proposiciones.

(a) La proposición “no A” es verdadera si A es falsa; expresada simbólicamente como\(¬A\) y llamada la negación de A.

(b) La proposición “A y B” es verdadera si tanto A como B son verdaderas; se expresan simbólicamente como\(A∧B\) y se llama la conjunción de A y B.

(c) La proposición “A o B” es verdadera si al menos una de A o B es verdadera; expresada simbólicamente como\(A∨B\) y denominada disyunción de A y B.

d) La proposición “Si A, entonces B” es verdadera si tanto A como B son verdaderas, o A es falsa; expresada simbólicamente como\(A =⇒ B\) y llamada proposición condicional (o implicación). En este caso, A se llama la hipótesis y B se llama la conclusión. Tenga en cuenta que A = siempre que A”. ⇒ B también puede leerse como “A implica B”, “A solo si B”, “B si A” o “B

e) La proposición “A si y sólo si B” (alternativamente, “A es necesaria y suficiente para B”) es verdadera si tanto A como B tienen el mismo valor de verdad; expresado simbólicamente como\(A ⇐⇒ B\) y denominado proposición bicondicional. Si A ⇒ B es cierto, decimos que A y B son lógicamente equivalentes.

Cada una de las proposiciones en caja se llama proposición compuesta, donde A y B son referidos como los componentes de la proposición compuesta.

Cabe señalar que las definiciones en matemáticas suelen escribirse en la forma “B si A” (o “B siempre que A” o “B siempre que A”), donde B contiene el término o frase que estamos definiendo y A proporciona el significado del concepto que estamos definiendo. En el caso de las definiciones, siempre debemos interpretar “B si A” como describir con precisión la colección de “objetos” (por ejemplo, números, conjuntos, funciones, etc.) que deben identificarse con el término o frase que definimos. Es decir, si un objeto no cumple la condición especificada en A, entonces nunca es referido por el término o frase que estamos definiendo. Algunos autores escribirán definiciones en la forma “B si y sólo si A”. Sin embargo, una definición no es en absoluto el mismo tipo de declaración que un bicondicional habitual ya que uno de los dos lados está indefinido hasta que se hace la definición. Una definición es realmente una afirmación de que el término o frase recién definido es sinónimo de un concepto previamente definido.

Podemos formar proposiciones compuestas complicadas con varios componentes mediante la utilización de conectivos lógicos.

Problema 2.19. Que A represente “6 es un número entero par” y B representa “4 divide 6". Expresar cada una de las siguientes proposiciones compuestas en una oración ordinaria en inglés y luego determinar su valor de verdad.

(a) A B

b) A B

(c) ¬A

d) ¬B

e) ¬ (AB)

f) ¬ (AB)

(g) A =⇒ B

Definición 2.20. Una tabla de verdad para una proposición compuesta es una tabla que ilustra todas las combinaciones posibles de valores de verdad para los componentes de la proposición compuesta junto con el valor de verdad resultante para cada combinación.

Ejemplo 2.21. Si A y B son proposiciones, entonces la tabla de verdad para la proposición compuesta A B viene dada por lo siguiente.

A	B	AB
T	T	T
T	F	F
F	T	F
F	F	F

Observe que tenemos columnas para cada una de A y B. Las filas para estas dos columnas corresponden a todas las combinaciones posibles de valores de verdad para A y B. La tercera columna arroja el valor de verdad de A B dados los posibles valores de verdad para A y B.

Cada componente de una proposición compuesta tiene dos posibles valores de verdad, a saber, verdadero o falso. Así, si una proposición compuesta se construye a partir de n proposiciones de componentes, entonces la tabla de verdad requerirá 2n filas.

Problema 2.22. Crear una tabla de verdad para cada una de las siguientes proposiciones compuestas. Debe agregar columnas adicionales a sus mesas según sea necesario para ayudarlo con pasos intermedios. Por ejemplo, es posible que necesites cuatro columnas para la tercera y cuarta proposiciones compuestas a continuación.

(a) ¬A

b) AB

c) ¬ (AB)

(d) ¬A¬B

Problema 2.23. Un entrenador promete a sus jugadores: “Si ganamos esta noche, entonces mañana te compraré pizza”. Determinar los casos en los que los jugadores pueden afirmar acertadamente que han sido mentidos. Si el equipo perdió el juego y el entrenador decidió comprarles pizza de todos modos, ¿estaba mintiendo?

Problema 2.24. Usa la Definición 2.18 (d) para construir una tabla de verdad para A =⇒ B. Compara tu tabla de verdad con Problema 2.23. La combinación a la que debes prestar especial atención es cuando la hipótesis es falsa mientras que la conclusión es verdadera.

De acuerdo con la Definición 2.18 (d), una proposición condicional A =⇒ B sólo es falsa cuando la hipótesis es verdadera y la conclusión es falsa. Quizás te molesta el hecho de que A =⇒ B es cierto cuando A es falso sin importar cuál sea el valor de verdad de B. Lo que hay que tener en cuenta es que el valor de verdad de A =⇒ B se basa en una definición muy específica y puede que no siempre esté de acuerdo con el uso coloquial de “Si., entonces.” afirmaciones que encontramos en el lenguaje cotidiano. Por ejemplo, si alguien dice: “Si rompes las reglas, entonces serás castigado”, el orador probablemente pretende que la declaración se interprete como “Serás castigado si y sólo si rompes las reglas”. En lógica y matemáticas, pretendemos eliminar tal ambigüedad diciendo explícitamente lo que queremos decir exactamente. Para nuestros fines, debemos considerar una proposición condicional como un contrato u obligación. Si la hipótesis es falsa y la conclusión es verdadera, no se viola el contrato. Por otro lado, si la hipótesis es cierta y la conclusión es falsa, entonces se rompe el contrato.

A menudo podemos probar hechos relativos a declaraciones lógicas usando tablas de verdad. Recordemos que dos proposiciones P y Q (ambas de las cuales podrían ser proposiciones compuestas complicadas) son lógicamente equivalentes si P ⇒ Q es verdadera (ver Definición 2.18 (e)). Esto sucede cuando P y Q tienen el mismo valor de verdad. Podemos verificar si P y Q tienen el mismo valor de verdad construyendo una tabla de verdad que incluya columnas para cada uno de los componentes de P y Q, enumerando todas las combinaciones posibles de sus valores de verdad, junto con columnas para P y Q que enumeran sus valores de verdad resultantes. Si los valores de verdad en las columnas para P y Q están de acuerdo, entonces P y Q son lógicamente equivalentes, y de lo contrario no son lógicamente equivalentes. Al construir tablas de verdad para verificar si P y Q son lógicamente equivalentes, debe agregar las columnas intermedias necesarias para ayudar en sus “cálculos”. Use tablas de verdad al intentar justificar los siguientes problemas.

Teorema 2.25. Si A es una proposición, entonces ¬ (¬A) es lógicamente equivalente a A.

El siguiente teorema, referido como Ley De Morgan, proporciona un método para negar una proposición compuesta que involucra una conjunción.

Teorema 2.26 (Ley De Morgan). Si A y B son proposiciones, entonces ¬ (A B) es lógicamente equivalente a ¬A ‖ ¬B.

Problema 2.27 (Ley De Morgan). Que A y B sean proposiciones. Conjetura una afirmación similar al Teorema 2.26 para la proposición ¬ (AB) y luego probarla. A esto también se le llama Ley De Morgan.

Haremos uso de ambas versiones La Ley De Morgan sobre una base regular. A veces, las conjunciones y disyunciones son “enterradas” en una declaración matemática, lo que hace que las declaraciones negativas sean difíciles de hacer negocios. Tenga esto en cuenta cuando se acerque al siguiente problema.

Problema 2.28. Deja que x sea tu número real favorito. Nega cada una de las siguientes afirmaciones. Obsérvese que la declaración de la Parte (b) implica una conjunción.

(a) x < −1 o x ≥ 3.

(b) 0 ≤ x < 1.

Teorema 2.29. Si A y B son proposiciones, entonces A ⇒ B es lógicamente equivalente a (A =⇒ B) (B =⇒ A).

Teorema 2.30. Si A, B y C son proposiciones, entonces (A ‖ B) =⇒ C es lógicamente equivalente a (A =⇒ C) (B =⇒ C).

Ya introdujimos la siguiente noción en la discusión siguiente Teorema 2.11

Definición 2.31. Si A y B son proposiciones, entonces lo contrario de A =⇒ B es B =⇒ A.

Problema 2.32. Proporcionar un ejemplo de una verdadera proposición condicional cuya inversa sea falsa.

Definición 2.33. Si A y B son proposiciones, entonces la inversa de A =⇒ B es ¬A =⇒ ¬B.

Problema 2.34. Proporcionar un ejemplo de una verdadera proposición condicional cuya inversa es falsa.

Con base en Problemas 2.32 y 2.34, podemos concluir que lo contrario y lo inverso de una proposición condicional no necesariamente tienen el mismo valor de verdad que la afirmación original. Además, lo contrario y lo inverso de una proposición condicional no necesariamente tienen el mismo valor de verdad que los demás.

Problema 2.35. Si es posible, proporcione un ejemplo de una proposición condicional cuya inversa sea verdadera pero cuya inversa sea falsa. Si esto no es posible, explique por qué.

¿Y si intercambiamos los roles de la hipótesis y conclusión de una proposición condicional y negamos cada uno?

Definición 2.36. Si A y B son proposiciones, entonces el contrapositivo de A =⇒ B es ¬B =⇒ ¬A.

Problema 2.37. Que A y B representen las declaraciones del Problema 2.19. Expresar cada uno de los siguientes en una oración ordinaria en inglés.

(a) Lo contrario de A =⇒ B.

(b) El contrapositivo de A =⇒ B.

Problema 2.38. Encuentra lo contrario y lo contrapositivo de la siguiente declaración: “Si Dana vive en Flagstaff, entonces Dana vive en Arizona”.

Usa una tabla de verdad para probar el siguiente teorema.

Teorema 2.39. Si A y B son proposiciones, entonces A =⇒ B es lógicamente equivalente a su contrapositivo.

Hasta el momento hemos discutido cómo negar las proposiciones de la forma A, A B, y A ‖ B para las proposiciones A y B. Sin embargo, todavía tenemos que discutir cómo negar proposiciones de la forma A =⇒ B. Demostrar el siguiente resultado con una tabla de verdad.

Teorema 2.40. Si A y B son proposiciones, entonces la implicación A =⇒ B es lógicamente equivalente a la disyunción ¬A B.

El siguiente resultado sigue rápidamente del Teorema 2.40 junto con La Ley De Morgan. También puedes verificar este resultado usando una tabla de verdad.

Corolario 2.41. Si A y B son proposiciones, entonces ¬ (A =⇒ B) es lógicamente equivalente a A ¬B.

Problema 2.42. Que A y B sean las proposiciones “√ 2 es un número irracional” y “Cada rectángulo es un trapecio”, respectivamente.

(a) Expresar A =⇒ B como una oración en inglés que involucra la disyunción “o”.

(b) Expresar ¬ (A =⇒ B) como frase inglesa que involucra la conjunción “y”.

Problema 2.43. Resulta que la proposición “Si .99··· =\(dfrac{9}{10} + dfrac{9}{100} + dfrac{9}{1000} +···\), entonces .99 ≠ 1” es falsa. Escribe su negación como una conjunción.

Recordemos que una proposición es exclusivamente verdadera o falsa, nunca puede ser ambas cosas.

Definición 2.44. Una proposición compuesta que siempre es falsa se llama contradicción. Una proposición compuesta que siempre es verdadera se llama tautología.

Teorema 2.45. Si A es una proposición, entonces la proposición ¬A A es una contradicción.

Problema 2.46. Proporcionar un ejemplo de una tautología usando proposiciones arbitrarias y cualquiera de las conectivas lógicas ¬, y ‖. Demuestra que tu ejemplo es de hecho una tautología.