3.3: Equivalencia e Implicación

Considera dos proposiciones generadas por\(p\)\(q\text{:}\)\(\neg (p \land q)\) y y\(\neg p \lor \neg q\text{.}\) A primera vista, son proposiciones diferentes. En forma, son diferentes, pero tienen el mismo significado. Una forma de ver esto es sustituyendo propuestas reales por\(p\) y\(q\text{;}\) como\(p\text{:}\) he estado en Toronto; y\(q\text{:}\) he estado en Chicago.

Luego\(\neg (p \land q)\) se traduce como “No he estado tanto en Toronto como en Chicago”, mientras que\(\neg p \lor \neg q\) es “no he estado en Toronto o no he estado en Chicago”. Determinar los valores de verdad de estas proposiciones. Naturalmente, serán ciertas para algunas personas y falsas para otras. Lo importante es que no importa qué valores de verdad tengan,\(\neg (p \land q)\) y\(\neg p \lor \neg q\) tendrán el mismo valor de verdad. La manera más fácil de ver esto es examinando las tablas de verdad de estas proposiciones.

Tabla\(\PageIndex{1}\): Tablas de verdad para\(\neg (p\land q)\) y\(\neg p\lor \neg q\)

\(p\)	\(q\)	\ (\ neg (p\ tierra q)\ 0	\(\neg p\lor \neg q\)
\ (p\) ">\(0\)	\ (q\) ">\(0\)	\ (\ neg (p\ tierra q)\ 0">\ (1\)	\ (\ neg p\ lor\ neg q\) ">\(1\)
\ (p\) ">\(0\)	\ (q\) ">\(1\)	\ (\ neg (p\ tierra q)\ 0">\ (1\)	\ (\ neg p\ lor\ neg q\) ">\(1\)
\ (p\) ">\(1\)	\ (q\) ">\(0\)	\ (\ neg (p\ tierra q)\ 0">\ (1\)	\ (\ neg p\ lor\ neg q\) ">\(1\)
\ (p\) ">\(1\)	\ (q\) ">\(1\)	\ (\ neg (p\ tierra q)\ 0">\ (0\)	\ (\ neg p\ lor\ neg q\) ">\(0\)

En los cuatro casos,\(\neg (p \land q)\) y\(\neg p \lor \neg q\) tienen el mismo valor de verdad. Además, cuando se les aplica el operador bicondicional, el resultado es un valor de true en todos los casos. Una proposición como esta se llama tautología.

Tautologías y Contradicciones

Definición \(\PageIndex{1}\): Tautology

Una expresión que involucra variables lógicas que es verdadera en todos los casos es una tautología. El número 1 se utiliza para simbolizar una tautología.

Ejemplo\(\PageIndex{1}\): Some Tautologies

Todas las siguientes son tautologías porque sus tablas de verdad constan de una columna de 1's.

1. \((\neg (p \land q))\leftrightarrow ( \neg p \lor \neg q)\text{.}\)
2. \(\displaystyle p \lor \neg p\)
3. \(\displaystyle (p \land q)\to p\)
4. \(\displaystyle q\to (p\lor q)\)
5. \(\displaystyle (p \lor q)\leftrightarrow (q \lor p)\)

Definición \(\PageIndex{2}\): Contradiction

Una expresión que involucra variables lógicas que es falsa para todos los casos se llama contradicción. El número 0 se utiliza para simbolizar una contradicción.

Ejemplo\(\PageIndex{2}\): Some Contradictions

\(p \land \neg p\)y\((p\lor q)\land (\neg p) \land (\neg q)\) son contradicciones.

Equivalencia

Definición \(\PageIndex{3}\): Equivalence

Dejar\(S\) ser un conjunto de proposiciones y dejar\(r\) y\(s\) ser proposiciones generadas por\(S\text{.}\)\(r\) y\(s\) son equivalentes si y sólo si\(r\leftrightarrow s\) es una tautología. La equivalencia de\(r\) y\(s\) se denota\(r \iff s\text{.}\)

La equivalencia es con la lógica como la igualdad lo es con el álgebra. Así como hay muchas formas de escribir una expresión algebraica, el mismo significado lógico se puede expresar de muchas maneras diferentes.

Ejemplo\(\PageIndex{3}\): Some Equivalences

Las siguientes son todas las equivalencias:

1. \((p \land q)\lor (\neg p \land q)\iff q\text{.}\)
2. \(\displaystyle p \to q \iff \neg q \rightarrow \neg p\)
3. \(p \lor q \iff q \lor p\text{.}\)

Todas las tautologías son equivalentes entre sí.

Ejemplo\(\PageIndex{4}\): An Equivalence to \(1\)

\(p\lor \neg p\iff 1\text{.}\)

Todas las contradicciones son equivalentes entre sí.

Ejemplo\(\PageIndex{5}\): An Equivalence to \(0\)

\(p\land \neg p\iff 0\text{.}\)

Implicación

Consideremos las dos proposiciones:

Mesa\(\PageIndex{2}\)

\(x\): El dinero está detrás de la Puerta A; y

\(y\): El dinero está detrás de la Puerta A o Puerta B

Imagina que te dijeron que hay una gran suma de dinero detrás de una de las dos puertas marcadas A y B, y que una de las dos proposiciones\(x\) y\(y\) es verdadera y la otra es falsa. ¿Qué puerta elegirías? Todo lo que necesitas darte cuenta es que si\(x\) es verdad, entonces también\(y\) lo será. Ya que sabemos que este no puede ser el caso,\(y\) debe ser la verdadera proposición y el dinero está detrás de la Puerta B.

Este es un ejemplo de una situación en la que la verdad de una proposición conduce a la verdad de otra. Ciertamente,\(y\) puede ser cierto cuando\(x\) es falso; pero no\(x\) puede ser cierto cuando\(y\) es falso. En este caso, decimos que\(x\) implica\(y\text{.}\)

Consideremos la tabla de verdad del\(p \to q\text{,}\) Cuadro 3.1.1. Si\(p\) implica\(q\text{,}\) entonces se puede descartar el tercer caso, ya que es el caso el que hace falsa una proposición condicional.

Definición \(\PageIndex{4}\): Implication

\(S\)Seamos un conjunto de proposiciones y dejemos\(r\) y\(s\) seamos proposiciones generadas por\(S\text{.}\) Nosotros decimos que\(r\) implica\(s\) si\(r \to s\) es una tautología. Escribimos\(r \Rightarrow s\) para indicar esta implicación.

Ejemplo\(\PageIndex{6}\): Disjunctive Addition

Una implicación de uso común llamada “adición disyuntiva” es la\(p \Rightarrow (p \lor q)\text{,}\) cual es verificada por la tabla de verdad Tabla\(\PageIndex{3}\).

Tabla\(\PageIndex{3}\): Tabla de Verdad para verificar que\(p\Rightarrow (p\lor q)\)

\(p\)	\(q\)	\(p\lor q\)	\(p\to o\lor q\)
\ (p\) ">\(0\)	\ (q\) ">\(0\)	\ (p\ lor q\) ">\(0\)	\ (p\ a o\ lor q\) ">\(1\)
\ (p\) ">\(0\)	\ (q\) ">\(1\)	\ (p\ lor q\) ">\(1\)	\ (p\ a o\ lor q\) ">\(1\)
\ (p\) ">\(1\)	\ (q\) ">\(0\)	\ (p\ lor q\) ">\(1\)	\ (p\ a o\ lor q\) ">\(1\)
\ (p\) ">\(1\)	\ (q\) ">\(1\)	\ (p\ lor q\) ">\(1\)	\ (p\ a o\ lor q\) ">\(1\)

Si dejamos\(p\) representar “El dinero está detrás de la Puerta A” y\(q\) representamos “El dinero está detrás de la Puerta B”,\(p \Rightarrow (p \lor q)\) es una versión formalizada del razonamiento utilizado en Ejemplo\(\PageIndex{6}\). Un nombre común para esta implicación es la adición disyuntiva. En la siguiente sección consideraremos algunas de las implicaciones y equivalencias más utilizadas.

Cuando definimos lo que queremos decir con una Proposición Generada por un Conjunto, Definición 3.2.1, no incluimos los operadores condicional y bicondicional. Esto se debió a las dos equivalencias\(p \to q \Leftrightarrow \neg p \lor q\) y\(p \leftrightarrow q \Leftrightarrow (p \land q) \lor (\neg p \land \neg q)\text{.}\) por lo tanto, cualquier proposición que incluya a los operadores condicionales o bicondicionales puede escribirse de manera equivalente usando solo conjunción, disyunción y negación. Incluso podríamos prescindir de la disyunción ya que\(p \lor q\) equivale a una proposición que utiliza sólo conjunción y negación.

Operación Universal

Cerramos esta sección con una operación lógica final, el Stroke Sheffer, que tiene la interesante propiedad de que todas las demás operaciones lógicas se pueden crear a partir de ella. Puedes explorar esta operación en Ejercicio\(\PageIndex{8}\)

Definición \(\PageIndex{5}\): The Sheffer Stroke

El Trazo Sheffer es el operador lógico definido por la siguiente tabla de verdad:

Tabla\(\PageIndex{4}\): Tabla de la verdad para el trazo de Sheffer

\(p\)	\(q\)	\(p\mid q\)
\ (p\) ">\(0\)	\ (q\) ">\(0\)	\ (p\ mediados q\) ">\(1\)
\ (p\) ">\(0\)	\ (q\) ">\(1\)	\ (p\ mediados q\) ">\(1\)
\ (p\) ">\(1\)	\ (q\) ">\(0\)	\ (p\ mediados q\) ">\(1\)
\ (p\) ">\(1\)	\ (q\) ">\(1\)	\ (p\ mediados q\) ">\(0\)

Ejercicios

Ejercicio\(\PageIndex{1}\)

Dadas las siguientes proposiciones generadas por\(p\text{,}\)\(q\text{,}\) y\(r\text{,}\) que son equivalentes entre sí?

1. \(\displaystyle (p \land r) \lor q\)
2. \(\displaystyle p\lor (r\lor q)\)
3. \(\displaystyle r \land p\)
4. \(\displaystyle \neg r \lor p\)
5. \(\displaystyle (p\lor q)\land (r\lor q)\)
6. \(\displaystyle r\to p\)
7. \(\displaystyle r \lor \neg p\)
8. \(\displaystyle p\to r\)

Responder

\(a\Leftrightarrow e, d\Leftrightarrow f, g\Leftrightarrow h\)

Ejercicio\(\PageIndex{2}\)

1. Construye la tabla de la verdad para\(x= (p \land \neg q) \lor (r \land p)\text{.}\)
2. Dar un ejemplo distinto a\(x\) sí mismo de una proposición generada por\(p\text{,}\)\(q\text{,}\) y\(r\) que es equivalente a\(x\text{.}\)
3. Dar un ejemplo de una proposición distinta a la\(x\) que implica\(x\text{.}\)
4. Dé un ejemplo de una proposición distinta a la\(x\) que implica\(x\text{.}\)

Ejercicio\(\PageIndex{3}\)

¿Es una implicación equivalente a su sentido contrario? Verifica tu respuesta usando una tabla de verdad.

Responder

No. En forma simbólica la pregunta es:\((p\to q)\Leftrightarrow (q\to p)\text{?}\)

\(\begin{array}{ccccc} p & q & p\to q & q\to p & (p\to q)\leftrightarrow (q\to p) \\ \hline 0 & 0 & 1 & 1 & 1\\ 0 & 1 & 1 & 0 & 0\\ 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 1 & 1 & 1 \\ \end{array}\)

Esta tabla indica que una implicación no siempre es equivalente a su contrario.

Ejercicio\(\PageIndex{4}\)

Supongamos que\(x\) es una proposición generada por\(p\text{,}\)\(q\text{,}\) y\(r\) que es equivalente a\(p \lor \neg q\text{.}\) Escribir la tabla de verdad para\(x\text{.}\)

Ejercicio\(\PageIndex{5}\)

¿Qué tan grande es el mayor conjunto de proposiciones generadas por\(p\) y\(q\) con la propiedad de que no hay dos elementos equivalentes?

Responder

\(x\)Sea cualquier proposición generada por\(p\) y\(q\text{.}\) La tabla de verdad para\(x\) tiene 4 filas y hay 2 opciones para un valor de verdad\(x\) para cada fila, por lo que hay\(2\cdot 2\cdot 2\cdot 2=2^4\) posibles proposiciones.

Ejercicio\(\PageIndex{6}\)

Encuentra una proposición que sea equivalente\(p \lor q\) y use solo conjunción y negación.

Ejercicio\(\PageIndex{7}\)

Explicar por qué una contradicción implica cualquier proposición y cualquier proposición implica una tautología.

Responder

\(0\to p\)y\(p\to 1\) son tautologías.

Ejercicio\(\PageIndex{8}\)

La importancia del Trazo Sheffer es que es una operación “universal” en que todas las demás operaciones lógicas se pueden construir a partir de ella.

1. Demostrar que\(p | q\) es equivalente a\(\neg (p \land q)\text{.}\)
2. Demostrar que\(\neg p \Leftrightarrow p | p\text{.}\)
3. Construye\(\land\) usando solo el Trazo Sheffer.
4. Construye\(\lor\) usando solo el Trazo Sheffer.