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:

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:

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:

1. Casarse completará su educación o aceptará la carta de incorporación a la empresa XYZ.
2. Harry irá a dar un paseo o a correr mañana.
3. 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:

1. Necesito un juego de diamantes y vale un anillo de oro.
2. Consigues un buen trabajo o no conseguirás una buena pareja.
3. Tomo mucho trabajo y no puedo manejarlo.
4. 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í:

1. No necesito un juego de diamantes ni un anillo de oro que no valga.
2. No puedes conseguir un buen trabajo y conseguirás un buen socio.
3. No tomo mucho trabajo o puedo manejarlo.
4. 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:

1. Si llueve, entonces se cancela el plan de ir a la playa.
2. Si estudio mucho, obtendré buenas notas en el examen.
3. Si voy a una fiesta nocturna, mi padre me castigará.
4. 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í:

1. Si se cancela el plan de ir a la playa, entonces está lloviendo.
2. Si obtengo buenas notas en el examen, estudio mucho.
3. Si mi padre me castiga, entonces iré a una fiesta nocturna.
4. 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.

En esta tabla de verdad, podemos ver que las columnas de (X → Y) → Z y X → (Y → Z) no contienen valores idénticos.