Supongamos que hay dos fórmulas, X e Y. Estas fórmulas se conocerán como equivalencia si X ↔ Y es una tautología. Si dos fórmulas X ↔ Y son una tautología, entonces también podemos escribirla como X ⇔ Y, y podemos leer esta relación como X es equivalencia con Y.
Nota: Hay algunos puntos que debemos tener en cuenta al realizar la equivalencia lineal de la fórmula, que se describen a continuación:
- ⇔ se usa para indicar solo símbolo, pero no es conectivo.
- El valor de verdad de X e Y siempre será igual si X ↔ Y es una tautología.
- La relación de equivalencia contiene dos propiedades, es decir, simétrica y transitiva.
Método 1: método de la tabla de verdad:
En este método, construiremos las tablas de verdad de cualquier fórmula de dos enunciados y luego comprobaremos si estos enunciados son equivalentes.
Ejemplo 1: En este ejemplo, tenemos que demostrar X ∨ Y ⇔ ¬(¬X ∧ ¬Y).
Solución: La tabla de verdad de X ∨ Y ⇔ ¬(¬X ∧ ¬Y) se describe a continuación:
| X | Y | X ∨ Y | ¬X | ¬Y | ¬X ∧ ¬Y | ¬(¬X ∧ ¬Y) | X ∨ Y ⇔ ¬(¬X ∧ ¬Y) |
|---|---|---|---|---|---|---|---|
| t | t | t | F | F | F | t | t |
| t | F | t | F | t | F | t | t |
| F | t | t | t | F | F | t | t |
| F | F | F | t | t | t | F | t |
Como podemos ver, X ∨ Y y ¬(¬X ∧ ¬Y) es una tautología. Por tanto X ∨ Y ⇔ ¬(¬X ∧ ¬Y).
Ejemplo 2: En este ejemplo, tenemos que demostrar (X → Y) ⇔ (¬X ∨ Y).
Solución: La tabla de verdad de (X → Y) ⇔ (¬X ∨ Y) se describe a continuación:
| X | Y | X → Y | ¬X | ¬X ∨ Y | (X → Y) ⇔ (¬X ∨ Y) |
|---|---|---|---|---|---|
| t | t | t | F | t | t |
| t | F | F | F | F | t |
| F | t | t | t | t | t |
| F | F | t | t | t | t |
Como podemos ver, X → Y y (¬X ∨ Y) son una tautología. Por tanto (X → Y) ⇔ (¬X ∨ Y)
Fórmula de equivalencia:
Existen diversas leyes que se utilizan para probar la fórmula de equivalencia, la cual se describe a continuación:
Ley idempotente: Si hay una fórmula de declaración, tendrá las siguientes propiedades:
X ∨ X ⇔ X X ∧ X ⇔ X
Ley asociativa: Si hay tres fórmulas de declaración, tendrá las siguientes propiedades:
(X ∨ Y) ∨ Z ⇔ X ∨ (Y ∨ Z) (X ∧ Y) ∧ Z ⇔ X ∧ (Y ∧ Z)
Ley conmutativa: Si hay dos fórmulas de declaración, tendrá las siguientes propiedades:
X ∨ Y ⇔ Y ∨ X X ∧ Y ⇔ Y ∧ X
Ley distributiva: Si hay tres fórmulas de declaración, tendrá las siguientes propiedades:
programación dinámica
X ∨ (Y ∧ Z) ⇔ (X ∨ Y) ∧ (X ∨ Z) X ∧ (Y ∨ Z) ⇔ (X ∧ Y) ∨ (X ∧ Z)
Ley de identidad: Si hay una fórmula de declaración, tendrá las siguientes propiedades:
(a) (i) X ∨ F ⇔ X (ii) X ∨ T ⇔ T (b) (i) X ∧ T ⇔ X (ii) X ∧ F ⇔ F
Ley complementaria: Si hay una fórmula de declaración, tendrá las siguientes propiedades:
(a) (i) X ∨ ¬X ⇔ T (ii) X ∧ ¬X ⇔ F (b) (i) ¬(¬X) ⇔ X (ii) ¬T ⇔ F , ¬F ⇔ T
Ley de absorción: Si hay dos fórmulas de declaración, tendrá las siguientes propiedades:
X ∨ (X ∧ Y) ⇔ X X ∧ (X ∨ Y) ⇔ X
De la ley de Morgan: Si hay dos fórmulas de declaración, tendrá las siguientes propiedades:
¬(X ∨ Y) ⇔ ¬X ∧ ¬Y ¬(X ∧ Y) ⇔ ¬X ∨ ¬Y
Método 2: proceso de reemplazo
En este método, asumiremos una fórmula A: X → (Y → Z). La fórmula Y → Z puede conocerse como parte de la fórmula. Si reemplazamos esta parte de la fórmula, es decir, Y → Z, con la ayuda de la fórmula de equivalencia ¬Y ∨ Z en A, obtendremos otra fórmula, es decir, B : X → (¬Y ∨ Z). Es un proceso sencillo verificar si las fórmulas A y B dadas son equivalentes entre sí o no. Con la ayuda del proceso de reemplazo, podemos obtener B de A.
Ejemplo 1: En este ejemplo, tenemos que demostrar que {X → (Y → Z) ⇔ X → (¬Y ∨ Z)} ⇔ (X ∧ Y) → Z.
Solución: Aquí, tomaremos la parte del lado izquierdo e intentaremos conseguir la parte del lado derecho.
X → (Y → Z) ⇔ X → (¬Y ∨ Z) [∵ Y → Z ⇔ ¬Y ∨ Z] ⇔ ¬X ∨ (¬Y ∨ Z) [∵ X → Y ⇔ ¬X ∨ Y]
Ahora usaremos la ley asociativa así:
⇔ (¬X ∨ ¬Y) ∨ Z
Ahora usaremos la ley de De Morgan así:
⇔ ¬(X ∧ Y) ∨ Z ⇔ (X ∧ Y) → Z [∵ X → Y ⇔ ¬X ∨ Y]
Por lo tanto demostrado
{X → (Y → Z) ⇔ X → (¬Y ∨ Z)} ⇔ (X ∧ Y) → Z Ejemplo 2: En este ejemplo, tenemos que demostrar que {(X → Y) ∧ (Z → Y)} ⇔ (X ∨ Z) → Y.
Solución: Aquí, tomaremos la parte del lado izquierdo e intentaremos conseguir la parte del lado derecho.
(X→ Y) ∧ (Z → Y) ⇔ (¬X ∨ Y) ∧ (¬Z ∨ Y) ⇔ (¬X ∧ ¬Z) ∨ Y ⇔ ¬(X ∨ Z) ∨ Y ⇔ X ∨ Z → Y
Por lo tanto demostrado
{(X → Y) ∧ (Z → Y)} ⇔ (X ∨ Z) → Y
Ejemplo 3: En este ejemplo, tenemos que demostrar que X → (Y → X) ⇔ ¬X → (X → Y).
Solución: Aquí, tomaremos la parte del lado izquierdo e intentaremos conseguir la parte del lado derecho.
X → (Y → X) ⇔ ¬X ∨ (Y → X) ⇔ ¬X ∨ (¬Y ∨ X) ⇔ (¬X ∨ X) ∨ ¬Y ⇔ T ∨ ¬Y ⇔ T and ¬X → (X → Y) ⇔ ¬(¬X) ∨ (X → Y) ⇔ X ∨ (¬X ∨ Y) ⇔ (X ∨ ¬X) ∨ Y ⇔ T ∨ Y ⇔ T
Por lo tanto demostrado
Java instanciado
X → (Y → X) ⇔ ¬X → (X → Y)
Ejemplo 4: En este ejemplo, tenemos que demostrar que (¬X ∧ (¬Y ∧ Z)) ∨ (Y ∧ Z) ∨ (X ∧ Z) ⇔ Z.
Solución: Aquí, tomaremos la parte del lado izquierdo e intentaremos conseguir la parte del lado derecho.
(¬X ∧ (¬Y ∧ Z)) ∨ (Y ∧ Z) ∨ (X ∧ Z)
Ahora usaremos las leyes asociativa y distributiva así:
⇔ ((¬X ∧ ¬Y) ∧ Z) ∨ ((Y ∨ X) ∧ Z)
Ahora usaremos la ley de De Morgan así:
⇔ (¬(X ∨ Y) ∧ Z) ∨ ((Y ∨ X) ∧ Z)
Ahora usaremos la ley Distributiva así:
⇔ (¬(X ∨ Y) ∨ (X ∨ Y)) ∧ Z ⇔ T ∧ Z [∵ ¬X ∨ X ⇔ T ⇔ R
Por lo tanto demostrado
(¬P ∧ (¬Q ∧ R)) ∨ (Q ∧ R) ∨ (P ∧ R) ⇔ R
Ejemplo 5: En este ejemplo, tenemos que demostrar que ((X ∨Y) ∧ ¬(¬X ∧ (¬Y ∨ ¬Z))) ∨ (¬X ∧ ¬Y) ∨ (¬X ∧ ¬Z) es una tautología.
Solución: Aquí tomaremos pequeñas partes y las resolveremos.
Primero, usaremos la ley de De Morgan y obtendremos lo siguiente:
¬X ∧ ¬Y ⇔ ¬(X ∨ Y) ¬X ∨ ¬Z ⇔ ¬(X ∧ Z)
Por lo tanto,
(¬X ∧ ¬Y) ∨ (¬X ∧ ¬Z) ⇔ ¬(X ∨ Y) ∨ ¬(X ∧ Z) ⇔ ¬((X ∨ Y) ∧ (X ∨ Z))
También
¬(¬X ∧ (¬Y ∨ ¬Z)) ⇔ ¬(¬X ∧ ¬(Y ∧ Z)) ⇔ X ∨ (Y ∧ Z) ⇔ (X ∨ Y) ∧ (X ∨ Z)
Por eso
((X ∨ Y) ∧ ¬(¬X ∧ (¬Y ∨ ¬Z))) ⇔ (X ∨ Y) ∧ (X ∨ Y) ∧ (X ∨ Z) ⇔ (X ∨ Y) ∧ (X ∨ Z)
De este modo
((X ∨ Y) ∧ ¬(¬X ∧ (¬Y ∨ ¬Z))) ∨ (¬X ∧ ¬Y) ∨ (¬X ∧ ¬Z) ⇔ [(X ∨ Y) ∧ (X ∨ Z)] ∨ ¬[(X ∨ Y) ∧ (X ∨ Z)] [∵ ¬X ∨ X ⇔ T] ⇔ T
Por tanto podemos decir que la fórmula dada es una tautología.
Ejemplo 6: En este ejemplo, tenemos que demostrar que (X ∧ Y) → (X ∨ Y) es una tautología.
Solución: (X ∧ Y) → (X ∨ Y)
⇔ ¬(X ∧ Y) ∨ (X ∨ Y) [∵ X → Y ⇔ ¬X ∨ Y]
Ahora usaremos la ley de De Morgan así:
⇔ (¬X ∨ ¬Y) ∨ (X ∨ Y)
Ahora usaremos la ley asociativa y la ley conmutativa así:
⇔ (¬X ∨ X) ∨ (¬Y ∨ Y)
Ahora usaremos la ley de Negación así:
⇔ (T ∨ T) ⇔ T
Por tanto podemos decir que la fórmula dada es una tautología.
Ejemplo 7: En este ejemplo, tenemos que escribir la negación de algunas declaraciones, que se describen a continuación:
- Casarse completará su educación o aceptará la carta de incorporación a la empresa XYZ.
- Harry irá a dar un paseo o a correr mañana.
- Si saco buenas notas, mi prima se pondrá celosa.
Solución: Primero, resolveremos el primer enunciado así:
1. Supongamos X: Casarse completará su educación.
Y: Aceptar la carta de incorporación de la empresa XYZ.
Podemos utilizar la siguiente forma simbólica para expresar esta afirmación:
X ∨ Y
La negación de X ∨ Y se describe de la siguiente manera:
¬(X ∨ Y) ¬(X ∨ Y) ⇔ ¬X ∧ ¬Y
En conclusión, la negación del enunciado dado será:
¬X ∧ ¬Y: Marry will not complete her education, and she will not accept the joining letter of XYZ Company.
2. Supongamos X: Harry irá a dar un paseo.
Y: Harry correrá mañana
Podemos utilizar la siguiente forma simbólica para expresar esta afirmación:
X ∨ Y
La negación de X ∨ Y se describe de la siguiente manera:
¬(X ∨ Y) ¬(X ∨ Y) ⇔ ¬X ∧ ¬Y
En conclusión, la negación del enunciado dado será:
¬X ∧ ¬Y: Harry will not go for a ride, and he will not run tomorrow
3. Supongamos X: Si obtengo buenas notas.
Y: Mi prima se pondrá celosa.
Podemos utilizar la siguiente forma simbólica para expresar esta afirmación:
X → Y
La negación de X → Y se describe de la siguiente manera:
¬(X → Y) ¬(X → Y) ⇔ ¬(¬X ∨ Y) ⇔ X ∧ ¬Y.
En conclusión, la negación del enunciado dado será:
X ∧ ¬Y: I get good marks, and my cousin will not be jealous.
Ejemplo 8: En este ejemplo, tenemos que escribir la negación de algunos enunciados con la ayuda de la ley de De Morgan. Estas declaraciones se describen a continuación:
- Necesito un juego de diamantes y vale un anillo de oro.
- Consigues un buen trabajo o no conseguirás una buena pareja.
- Tomo mucho trabajo y no puedo manejarlo.
- Mi perro se va de viaje o hace un desastre en la casa.
Solución: La negación de todos los enunciados con la ayuda de la ley de De Morgan se describe uno por uno así:
- No necesito un juego de diamantes ni un anillo de oro que no valga.
- No puedes conseguir un buen trabajo y conseguirás un buen socio.
- No tomo mucho trabajo o puedo manejarlo.
- Mi perro no sale de viaje y no ensucia la casa.
Ejemplo 9: En este ejemplo, tenemos algunas declaraciones y tenemos que escribir la negación de esas declaraciones. Las declaraciones se describen a continuación:
- Si llueve, entonces se cancela el plan de ir a la playa.
- Si estudio mucho, obtendré buenas notas en el examen.
- Si voy a una fiesta nocturna, mi padre me castigará.
- Si no quieres hablar conmigo, entonces tienes que bloquear mi número.
Solución: La negación de todas las afirmaciones se describe una por una así:
- Si se cancela el plan de ir a la playa, entonces está lloviendo.
- Si obtengo buenas notas en el examen, estudio mucho.
- Si mi padre me castiga, entonces iré a una fiesta nocturna.
- Si tienes que bloquear mi número, entonces no querrás hablar conmigo.
Ejemplo 10: En este ejemplo, tenemos que comprobar si (X → Y) → Z y X → (Y → Z) son lógicamente equivalentes o no. Tenemos que justificar nuestra respuesta con la ayuda de tablas de verdad y con la ayuda de reglas de lógica para simplificar ambas expresiones.
Solución: Primero, usaremos el método 1 para verificar si (X → Y) → Z y X → (Y → Z) son lógicamente equivalentes, que se describe a continuación:
protocolos de capa de enlace de datos
Método 1: Aquí asumiremos lo siguiente:
(X → Y) → Z ⇔ (¬X ∨ Y) → Z ⇔ ¬(¬X ∨ Y) ∨ Z ⇔ (X ∧ ¬Y) ∨ Z ⇔ (X ∧ Z) ∨ (¬Y ∧ Z)
Y
X → (Y → Z) ⇔ X → (¬Y ∨ Z) ⇔ ¬X ∨ (¬Y ∨ Z) ⇔ ¬X ∨ ¬Y ∨ Z X → Y) → Z and X → (Y → Z)
Método 2: Ahora usaremos el segundo método. En este método, usaremos la tabla de verdad.
| X | Y | CON | X → Y | (X → Y) → Z | Y → Z | X → (Y → Z) |
|---|---|---|---|---|---|---|
| t | t | t | t | t | t | t |
| t | t | F | t | F | F | F |
| t | F | t | F | t | t | t |
| t | F | F | F | t | t | t |
| F | t | t | t | t | t | t |
| F | t | F | t | F | F | t |
| F | F | t | t | t | t | t |
| F | F | F | t | F | t | t |
En esta tabla de verdad, podemos ver que las columnas de (X → Y) → Z y X → (Y → Z) no contienen valores idénticos.