3.1 Reglas de equivalencia En esta sección estudiarás y aplicarás algunas reglas de equivalencia de proposiciones lógicas. Es decir, vamos a empezar a aplicar algunas reglas que nos permitirán transformar proposiciones compuestas, pero conservando su semántica, o sea, todas sus interpretaciones, o en otras palabras, sin alterar su tabla de verdad. Posteriormente, en la sección siguiente, estudiaremos leyes de inferencia que nos permitan definir implicaciones lógicas. Para darnos una idea de la utilidad de las reglas de equivalencia, veamos la tabla de verdad de las siguientes proposiciones compuestas: p1 = (~x∧~y∧z) ∨ (~x∧y∧z) ∨ (x∧~y) p2 = (x∧~y) ∨ (~x∧z) Ambas son proposiciones compuestas por 3 proposiciones simples, por tanto, hay 8 posibles combinaciones. Su tabla de verdad es la siguiente: x

y

z

x∧~y

p1

x∧~y

~x∧z

p2

V V

V

F

F

F

F

F

F

F

V V

F

F

F

F

F

F

F

F

V

F

V

F

F

V

V

V

F

V

V

F

F

F

F

V

V

V

F

V

F

V

V

F

V

F

V

F

V

V

F

V

F

F

F

F

F

F

F

F

F

F

V

V

F

F

V

F

V

V

F

F

F

F

F

F

F

F

F

F

~x∧~y∧z ~x∧y∧z

Vemos que las dos proposiciones tienen la misma tabla de verdad, es decir, son dos proposiciones equivalentes, pero una es más simple que la otra. De este sencillo ejercicio podemos concluir que es factible encontrar una proposición compuesta equivalente a otra, pero más simple. Para este proceso de simplificación son necesarias las Reglas de equivalencia. 3.1 Reglas de equivalencia La siguiente tabla contiene varias reglas de equivalencia. Algunos autores las llaman tautologías notables. Como podrás observar, estas reglas tienen su nombre .Es importante tenerlas presentes, porque, como ya vimos, pueden ayudarnos a simplificar el manejo de proposiciones compuestas. Regla

Nombre

1 ~~p ⇔ p (se lee no no p equivale a p)

Doble negación o involución

2a (p ∨ q) ⇔ (p ∨ q) (se lee p o q equivale a q o p) 2b (p ∧ q) ⇔ (p ∧ q) 2c (p ↔ q) ⇔ (p ↔ q)

Leyes conmutativas

3a (p ∨ q) ∨ r ⇔ p ∨ ( q ∨ r)

Leyes asociativas

3b (p ∧ q) ∧ r ⇔ p ∧ ( q ∧ r) 4a p ∨ ( q ∧ r) ⇔ (p ∨ q) ∧ (p ∨ r) 4b p ∧ ( q ∨ r) ⇔ (p ∧ q) ∨ (p ∧ r)

Leyes distributivas

5a (p ∨ p) ⇔ p 5b (p ∧ p) ⇔ p

Leyes de idempotencia

6a (p ∨ F) ⇔ p 6b (p ∨ V) ⇔ V 6c (p ∧ F) ⇔ F 6d (p ∧ V) ⇔ p donde F = Falso y V = Verdadero

Leyes de identidad

7a (p ∨ ~p) ⇔ V 7b (p ∧ ~p) ⇔ F

Postulados

8a ~(p ∨ q) ⇔ ~p ∧ ~q 8b ~(p ∧ q) ⇔ ~p ∨ ~q 8c (p ∨ q) ⇔ ~(~p ∧ ~q) 8d (p ∧ q) ⇔ ~(~p ∨ ~q)

Leyes de DeMorgan

9 (p → q) ⇔ ~q → ~p

Contrapositiva

10a (p → q) ⇔ (~p ∨ q) 10b (p → q) ⇔ ~(p ∧ ~q)

Implicación

11a (p ∨ q) ⇔ (~p → q) 11b (p ∧ q) ⇔ ~(p → ~q)

Implicación

12a ((p → r) ∧ (q → r)) ⇔ (p ∨ q) → r 12b ((p → q) ∧ (p → r)) ⇔ p → (p ∧ r)

Implicación

13 p ↔ q ⇔ (p → q) ∧ (q → p)

Equivalencia

14 (p ∧ q)→ r ⇔ (p → (q → r))

Ley de exportación

15 p → q ⇔ ((p ∧ ~q) → F) donde F = Falso

Reducción al absurdo

Comprobación de algunas reglas de equivalencia por medio de tablas de verdad Vamos a construir las tablas de verdad de las reglas 13 (Equivalencia) y 15 (Reducción al absurdo) para demostrar que son reglas válidas. Regla de la equivalencia La regla de equivalencia establece que una doble implicación es igual a la conjunción de las implicaciones de sus componentes: p ↔ q ⇔ (p → q) ∧ (q → p) La tabla de verdad, donde puede verse que esta regla se cumple, o sea, que ambas proposiciones son equivalentes, es la siguiente: p

q

p ↔ q p → q q → p (p → q) ∧ (q → p)

V

V

V

V

V

V

V

F

F

F

V

F

F

V

F

V

F

F

F

F

V

V

V

V

Regla de Reducción al absurdo La regla de reducción al absurdo establece que una implicación es equivalente a la conjunción de su antecedente con la negación del consecuente implica Falso: p → q ⇔ ((p ∧ ~q) → F) La tabla de verdad, donde puede verse que esta regla se cumple, es decir, que ambas proposiciones son equivalentes, es la siguiente: p

q

p → q p ∧ ~q (p ∧ ~q) → F

V

V

V

F

V

V

F

F

V

F

F

V

V

F

V

F

F

V

F

V

Ejemplo de transformación de proposiciones por medio de las reglas de equivalencia Como ya dijimos antes, una de las mejores maneras de mostrar el uso de las reglas de la lógica es por medio de ejemplos. Vamos, pues, a explicar algunos que ilustran el uso de las reglas de equivalencia en proposiciones compuestas. Ejemplo 1 Sea la proposición: (x∧y) ∨ (x∧~y) Comparándola con la regla distributiva 4b, vemos que tenemos la parte derecha de ella si consideramos x = p, y = q, y ~y = r. Por tanto, la proposición es equivalente a: x ∧ (y∨~y) De la regla de identidad 7a tenemos que y∨~y = V, por tanto, la expresión es equivalente a: x ∧V De la regla de identidad 6d, resulta que x ∧V = x, por tanto: (x∧y) ∨ (x∧~y) ⇔ x

Ejemplo 2 Se quiere simplificar la siguiente proposición compuesta: z∧x ∨ z∧~x∧y Aplicando la regla distributiva 4b a los dos términos, tenemos: z∧(x ∨ ~x∧y) Aplicando la regla de identidad 4a al término del paréntesis, se obtiene: z∧((x ∨ ~x)∧(x ∨ y)) Aplicando la regla de identidad 7a al término (x∨~x ⇔ V) , tenemos: z∧(V∧(x∨y)) Aplicando la regla de identidad 6d al término V∧(x∨y) ⇔ (x∨y), resulta: z∧((x∨y)) De la que podemos eliminar los paréntesis externos,resultando: z∧x ∨ z∧~x∧y ⇔ z∧(x∨y) Ejemplo 3 Simplifica la siguiente proposición compuesta: p1 = (~x∧~y∧z) ∨ (~x∧y∧z) ∨ (x∧~y) Aplicando la regla de conmutativa 2b a los primeros dos términos, tenemos: p1' = (~x∧z∧~y) ∨ (~x∧z∧y) ∨ (x∧~y) Donde hemos intercambiado la posición de ~y con z en el primer término y de y con z en el segundo. Si en p1' hacemos los siguiente cambios en los primeros dos términos: ~x∧z = a, ~y = b, y y = c, resulta: p1'' = (a ∧ b) ∨ (a ∧ c) ∨ (x∧~y) Para hacer un poco más clara su aplicación, “parafraseando” la regla distributiva 4b, tenemos: Regla 4b: a ∧ ( b ∨ c) ⇔ (a ∧ b) ∨ (a ∧ c) Vemos que los primeros dos términos de p1'' equivalen al lado derecho de la paráfrasis de la regla 4b, por lo que podemos transformar p1'' de la siguiente manera:

p1''' = a ∧ ( b ∨ c) ∨ (x∧~y) Restableciendo algunos cambios que hicimos antes: b = ~y, y c=y, tenemos: p1''' = a∧ ( ~y ∨ y) ∨ (x∧~y) Aplicando la ley conmutativa 2a al termino ( ~y ∨ y), se obtiene ( y ∨ ~y). Aplicando el postulado 7a a este último término, tenemos ( y ∨ ~y) ⇔ V, por tanto, ahora p1''' equivale a: p1''' = a ∧ V ∨ (x∧~y) Aplicando la ley de identidad 6d al primer término, resulta: p1''' = a ∨ (x∧~y) Por último, deshaciendo el cambio a = ~x∧z, obtenemos: p1''' = ~x∧z ∨ (x∧~y) Es decir, (~x∧~y∧z) ∨ (~x∧y∧z) ∨ (x∧~y) ⇔ ~x∧z ∨ (x∧~y) Que resulta ser la proposición p2 = (~x∧z) ∨ (x∧~y) comentada al inicio de esta sección, salvo por los paréntesis del primer término. Los paréntesis en el cálculo proposicional, al igual que en el caso del álgebra, se utilizan para indicar qué operaciones se hacen primero. En este caso, los paréntesis del primer término son superfluos porque la conjunción tiene precedencia sobre la disyunción. Ejemplo 4 Simplifica la siguiente proposición: (~A∧~B) ∨ (A∧~B) ∨ (A∧B) Aplicando la ley conmutativa 2a a los tres términos, tenemos: (~B∧~A) ∨ (~B∧A) ∨ (B∧A) Aplicando la ley distributiva 4b a los primeros dos términos, resulta: (~B∧(~A∨A)) ∨ (B∧A) Por el postulado 7a ((~A∨A) ⇔ V) y la ley de identidad 6d (~B∧V ⇔ ~B), se obtiene: ~B ∨ (B∧A) Aplicando la ley distributiva 4a a la proposición anterior, resulta: (~B∨B) ∧ (~B∨A)

Aplicando el postulado 7a a la primera expresión tenemos que (~B∨B) ⇔ V, por tanto, se tiene: V ∧ (~B∨A) Que, según la ley de identidad 6d, equivale a: ~B∨A Por tanto, resulta que: (~A∧~B) ∨ (A∧~B) ∨ (A∧B) ⇔ ~B∨A Ejemplo 5 Simplifica la siguiente proposición: (x∧~z) ∨ (~x∧z) ∨ z Aplicando la ley conmutativa, tenemos: z ∨ (z∧~x) ∨ (~z∧x) Dado que (z ∧ V) ⇔ z, por la ley de identidad 6a, se obtiene: (z ∧ V) ∨ (z∧~x) ∨ (~z∧x) Aplicando la ley distributiva 4b, resulta: z ∧ (V∨~x)∨ (~z∧x) Según la ley de identidad 6b, (V ∨ ~x) ⇔ V, por tanto, la expresión resultante hasta este punto es: z ∧ V ∨ (~z∧x) Dado que z ∧ V ⇔ z, de acuerdo con la ley de identidad 6d, la expresión resultante hasta este punto es: z ∨ (~z∧x) Aplicando la ley distributiva 4a, resulta: (z ∨ ~z) ∧ (z∨x) Dado que (z ∨ ~z) ⇔ V, por el postulado 7a, se tiene: V ∧ (z∨x) La ley de identidad 6d establece que V ∧ (z∨x) ⇔ (z∨x), por tanto, resulta: (x∧~z) ∨ (~x∧z) ∨ z ⇔ (z∨x)

Con este ejemplo, terminamos nuestro estudio de las reglas de equivalencia, que son útiles para simplificar proposiciones compuestas. Sigue ahora el estudio de las reglas de implicaciones y de inferencia, con las cuales podremos determinar si un razonamiento es válido o no.