2.2: Cálculo proposicional

La equivalencia lógica nos da algo así como un “signo igual” que podemos usar para realizar “cálculos” y manipulaciones lógicas, similares a los cálculos y manipulaciones algebraicas. Para que podamos hacer tales cálculos, primero necesitamos un “cofre de herramientas” de equivalencias lógicas básicas para usar en el mismo.

Proposición\(\PageIndex{1}\): Rules of Propositional Calculus

Supongamos que\(A,B,C,E,U\) son declaraciones lógicas, donde\(E\) es una contradicción y\(U\) es una tautología. Entonces siempre se mantienen las siguientes equivalencias.

1. Reglas que involucran tautologías.

   1. \(\displaystyle A \lor U \Leftrightarrow U\)
   2. \(\displaystyle A \land U \Leftrightarrow A\)

2. Reglas que involucran contradicciones.

   1. \(\displaystyle A \lor E \Leftrightarrow A\)
   2. \(\displaystyle A \land E \Leftrightarrow E\)

3. Dualidad de tautologías y contradicciones.

   1. \(\displaystyle \neg U \Leftrightarrow E\)
   2. \(\displaystyle \neg E \Leftrightarrow U\)

4. Doble negación.

   \(\displaystyle \neg \neg A \Leftrightarrow A\)

5. Idempotencia.

   1. \(\displaystyle A \lor A \Leftrightarrow A\)
   2. \(\displaystyle A \land A \Leftrightarrow A\)

6. Conmutatividad.

   1. \(\displaystyle A \lor B \Leftrightarrow B \lor A\)
   2. \(\displaystyle A \land B \Leftrightarrow B \land A\)

7. Asociatividad.

   1. \(\displaystyle (A \lor B) \lor C \Leftrightarrow A \lor (B \lor C)\)
   2. \(\displaystyle (A \land B) \land C \Leftrightarrow A \land (B \land C)\)

8. Distributividad.

   1. \(\displaystyle A \land (B \lor C) \Leftrightarrow (A \land B) \lor (A \land C)\)
   2. \(\displaystyle A \lor (B \land C) \Leftrightarrow (A \lor B) \land (A \lor C)\)
   3. \(\displaystyle (A \lor B) \land C \Leftrightarrow (A \land C) \lor (B \land C)\)
   4. \(\displaystyle (A \land B) \lor C \Leftrightarrow (A \lor C) \land (B \lor C)\)

9. Leyes de DeMorgan.

   1. \(\displaystyle \neg (A \lor B) \Leftrightarrow \neg A \land \neg B\)
   2. \(\displaystyle \neg (A \land B) \Leftrightarrow \neg A \lor \neg B\)

10. Construyendo lo condicional y bicondicional.

    1. \(\displaystyle A \rightarrow B \Leftrightarrow \neg A \lor B\)
    2. \(\displaystyle A \leftrightarrow B \Leftrightarrow (A \rightarrow B) \land (B \rightarrow A)\)

OBSERVACIÓN\(\PageIndex{1}\)

Cada una de estas equivalencias básicas se puede establecer con una tabla de verdad. Ver Ejercicio 2.5.4.

Ejemplo\(\PageIndex{1}\): DeMorgan

Utilizando la Regla 9.b de la Proposición\(\PageIndex{1}\), las siguientes son declaraciones equivalentes.

1. El triángulo no puede ser tanto derecho como equilátero.
2. El triángulo no es recto o no es equilátero.

Para ver cómo se aplica la regla, vamos a\(p\) representar la declaración “el triángulo es recto” y vamos a\(q\) representar la declaración “el triángulo es equilátero”. Entonces la primera declaración anterior es\(\neg (p \land q)\text{,}\) mientras que la segunda declaración anterior es\(\neg p \lor \neg q\text{.}\)

Ahora necesitamos algunas reglas de sustitución nuevas que nos permitan utilizar las reglas de la Proposición\(\PageIndex{1}\) en los cálculos lógicos.

Teorema\(\PageIndex{1}\): Substitution Rules

1. Sustituir una subdeclaración por una equivalente.

Supongamos que\(A\) es una sentencia lógica y\(X\) es una subdeclaración de\(A\text{.}\) If sentencia\(Y\) es equivalente a\(X\text{,}\) entonces la nueva sentencia\(A'\) obtenida de\(A\) reemplazando subdeclaración\(X\) por\(Y\) es equivalente a Es\(A\text{.}\) decir, si\(Y \Leftrightarrow X\) entonces\(A' \Leftrightarrow A\text{.}\)

2. Sustituir en una equivalencia conocida.

Supongamos\(A\) y\(B\) son sentencias lógicas, cada una de las cuales involucra variables de subinstrucción\(p_1, p_2, \ldots, p_m\text{.}\) Si\(A\) y\(B\) son equivalentes, entonces también lo son las sentencias nuevas\(A'\) y\(B'\) se obtienen aplicando la sustitución\(p_i = C_i\) a ambos\(A\) y \(B\text{,}\)por cada colección de declaraciones\(C_1, C_2, \ldots, C_m\text{.}\)

Idea de Prueba.

Piense en\(X\) como una columna intermedia en el cálculo de la tabla de verdad de\(A\text{.}\) Reemplazar\(X\) por\(Y\) no cambia esta columna, ya que las tablas de verdad de\(X\) y\(Y\) son las mismas. Dejamos esta declaración para que usted, el lector, la considere. (Una vez más, piense en las columnas\(C_i\) como intermedias en los cálculos de las tablas de verdad de\(A'\) y\(B'\text{.}\))

 

Ejemplo\(\PageIndex{2}\)

Una de las Leyes de DeMorgan (Regla 9.a de la Proposición\(\PageIndex{1}\)) dice que\(\neg (p \lor q) \Leftrightarrow \neg p \land \neg q\text{.}\) Por lo tanto,

\ comenzar {ecuación*}\ neg ((r\ fila derecha t)\ lor (t\ fila derecha r))\ fila izquierda\ neg (r\ fila derecha t)\ tierra\ neg (t\ fila derecha r),\ fin {ecuación*}

usando la Regla 2 de nuestras nuevas Reglas de Sustitución, con sustituciones\(p = r \rightarrow t\text{,}\)\(q = t \rightarrow r\text{.}\)

Aquí hay un ejemplo de una cadena de manipulaciones lógicas. También demuestra el uso de la Regla 10.a de la Proposición\(\PageIndex{1}\) para manipular una expresión que involucra a un condicional.

Ejemplo\(\PageIndex{3}\): DeMorgan with a Conditional

Considera la afirmación\((p_1 \lor p_2) \rightarrow q\text{.}\) Podemos leerla como “si cualquiera\(p_1\) o\(p_2\) es verdad, entonces también lo\(q\) será”. Entonces parece que cada uno de\(p_1\) y\(p_2\) debe implicar\(q\) por sí solo. Veamos qué dice el cálculo proposicional sobre esto:

\ begin {align*} (p_1\ lor p_2)\ fila derecha q &\ Leftrightarrow\ neg (p_1\ lor p_2)\ lor q & &\ text {(i)}\\ &\ Leftrightarrow (\ neg p_1\ land\ neg p_2)\ lor q & &\ text {(ii)}\\ &\ Izquierda Tarrow (\ neg p_1\ lor q)\ tierra (\ neg p_2\ lor q) &\ texto {(iii)}\\ &\ Leftrightarrow ( p_1\ fila derecha q)\ tierra (p_2\ fila derecha q) & &\ texto {(iv)},\ end {alinear*}

con justificaciones

1. Regla 2 de nuestras nuevas Reglas de Sustitución, donde sustituimos\(A = p_1 \lor p_2\) en ambos lados de la construcción del condicional (Regla 10.a de la Proposición\(\PageIndex{1}\));
2. Regla 1 de nuestras nuevas Reglas de Sustitución, utilizando DeMorgan (Regla 9.a de la Proposición\(\PageIndex{1}\)) en el subestado\(\neg (p_1 \lor p_2)\text{;}\)
3. distributividad (Regla 8.d de la Proposición\(\PageIndex{1}\)); y
4. Regla 1 de nuestras nuevas Reglas de Sustitución, utilizando la construcción del condicional (Regla 10.a de Proposición\(\PageIndex{1}\)) sobre cada uno de los dos “factores” de la conjunción.

Entonces nuestra intuición sobre la lógica de una disyunción en un condicional de esta manera era correcta.

Una mirada hacia el futuro

Esta observación será útil — ver Sección 6.4 y Sección 6.5.