R. Equivalencia PDF

Preview

Summary

Equivalencia...

Description

CAPÍTULO 4 RELACIÓN DE EQUIVALENCIA 4.1. INTRODUCCIÓN En general, se llama equivalencia a la expresión mediante la cual se indica que dos o más objetos matemáticos tienen el mismo valor de verdad o numérico. Dos o más proposiciones son equivalentes cuando tiene el mismo valor de verdad, o igual significado. Por ejemplo, “el triángulo ABC es equilátero” y “el triángulo ABC es equiángulo” son afirmaciones equivalentes, pues todo triángulo equilátero es equiángulo y viceversa. Dos fracciones son equivalentes cuando tienen igual valor numérico, es decir, dan lugar a la misma fracción irreducible. Por ejemplo, 6/8 y 12/16 son equivalentes porque ambas se pueden simplificar a 3/4. La relación de equivalencia es un concepto fundamental de la matemática, por lo mismo, a continuación, se analizan algunos de sus elementos y aplicaciones más importantes. 4.2. RELACIÓN DE EQUIVALENCIA (  , ≡ ; ... equivale a ...) Un polinomio booliano P(p,q, ...) tiene una relación de equivalencia con el polinomio Q(p,q, ...) si se verifica que los casos excluidos son (V,F) y (F,V), y si el polinomio P(p,q, ...)  Q(p,q, ...) es una tautología. Se representa por: P(p,q, ...) Q(p,q, ...) o P(p,q, ...) ≡ Q(p,q, ...), y se lee "p equivale a q ".

La relación de equivalencia se determina, por extensión y diagrama sagital, de la siguiente manera: P(p,q)

Q(p,q)

V

V

F

F

R8 = {(V,V),(F,F)}

Ejemplo 1. Determine si en el siguiente polinomio existe una relación de equivalencia: (p→q)  (~p v q): 1. Se construye la tabla de verdad del polinomio dado: p V V F F

q V F V F

(p V V F F

→ V F V V

q) V F V F

 V V V V

(~ F F V V

p V V F F

v V F V V

q) V F V F

P(p,q)

Q(p,q)

V

V

F

F

2. Los casos excluidos, en la tabla y diagrama sagital, son: (V,F) y (F,V). 3. El polinomio es una tautología, en la columna resultado, para el operador lógico . 4. Luego: (p → q)  (~ p v q) o (p → q) ≡ (~ p v q) Msc. Paco Bastidas Romo & Otros

61

Relación de equivalencia

4.3. TEOREMA TAUTOLOGÍA / CONTRADICCIÓN (T/C) Si los polinomios booleanos P(p,q, ...) y Q(p,q, ...) son ambos tautologías o bien ambos contradicciones, entonces P(p,q, ...)  Q(p,q, ...). En consideración del teorema anterior se tiene que: 1.

P(p, q, ...)  Q(p,q, ...), si se presenta sólo el caso (V,V), y si P(p,q, ...)  Q(p,q, ...) es una tautología.

La relación de equivalencia se determina, por extensión y diagrama sagital, de la siguiente manera: P(p,q)

Q(p,q)

V

V

F

F

R2 = {(V,V)}

2. P(p,q, ...)  Q(p,q, ...), si se presenta sólo (F,F), y si P(p,q, ...)  Q(p,q, ...) es una tautología. La relación de equivalencia se determina, por extensión y diagrama sagital, de la siguiente manera: P(p,q)

Q(p,q)

V

V

F

F

R5 = {(F,F)}

Ejemplo 1: Determine sí (p v ~ p) ≡ V 1. 2. 3. 4.

Construimos la tabla de verdad: Se presenta el caso (V,V). (p v ~ p)  V es una tautología Luego, (p v ~ p)  V, por el teorema T/C

p

(p

V F

V F

V V V

~

p)



F V

V F

V V

V V V

Ejemplo 2. Determine sí (p  F)  F 1. 2. 3. 4.

Construimos la tabla de verdad. Se presenta el caso (F.F). (p  F)  F es una tautología Por lo tanto: (p  F)  F, por el teorema T/C.

p V F

(p V F

 F F

F) F F

 V V

F F F

EJERCICIOS 1. Verificar el teorema T /C en las siguientes relaciones de equivalencia: 1. p  ~ p ≡ F 4. q v ~ q ≡ V 7. (p v q)  ~ (p v q) ≡ F 10. (qq) v ~ q ≡ V Msc. Paco Bastidas Romo & Otros

2. p v V ≡ V 5. (pq)  ~ (pq) ≡ F 8. (p  q) v V ≡ V 11. (p →q)  ~ (p→q) ≡ F 62

3. q  F ≡ F 6. (pq) v V ≡ V 9. (q v p)  F ≡ F 12. (p v q) v V ≡ V Relación de equivalencia

4.4. TEOREMA: SUSTITUCIÓN DE VARIABLES (SV) Si las variables p1, p2, p3, ... , de una relación de equivalencia, se sustituyen por cualquier proposición, entonces la proposición resultante es también equivalente.

Ejemplo 1: Verificar el teorema SV en p1  q2 ≡ q2  p1, si p1: p → q y q2: p v q. 1.

Construimos la tabla de verdad: (p1  q2)  (q2  p1). p1 V V F F

q2 V F V F

(p1



V V F F

V F F F

q 2)



V F V F

V V V V

(q2



p1)

V F V F

V F F F

V V F F

2. Los casos excluidos son: (V,F) y (F,V) 3. El polinomio es una tautología para el bicondicional ( ), en la columna resultado. 4. Por lo tanto: p1  q2 ≡ q2  p1 Luego, se sustituye los polinomios p1: p → q y q2: p v q, en (p1  q2)  (q2  p1): Observación: la palabra sustitución significa poner una proposición en lugar de otra (reemplazar). 1.

Construimos la tabla de verdad: [(p → q)  (p v q)]  [(p v q)  (p → q)] p V V F F

q V F V F

[ (p V V F F

→ V F V V

q) V F V F

 F F V F

(p V V F F

v F V V F

q) ] V F V F

 V V V V

[ (p V V F F

v F V V F

q) V F V F

 F F V F

(p V V F F

→ V F V V

q) ] V F V F

2. Los casos excluidos son: (V,F) y (F,V). 3. El polinomio es una tautología para el bicondicional (), en la columna resultado. 4. Luego: [(p → q)  (p v q)] ≡ [(p v q)  (p → q)] Ejemplo 2. Verificar el teorema SV en p1  q2 ≡ q2  p1, si se conoce que p1: p v q. 1.

Construimos la tabla de verdad de: (p1  q2)  (q2  p1). p1 V V F F

q2 V F V F

(p1 V V F F

 V F F F

q 2) V F V F

 V V V V

(q2 V F V F

 V F F F

p1) V V F F

2. Se excluyen los caso (V,F) y (F,V). 3. El polinomio es una tautología para el bicondicional, en la columna resultado. 4. Por lo tanto: p1  q2 ≡ q2  p1 Luego, se sustituye (remplazar) el polinomio p1: p v q en (p1  q2)  (q2  p1), y; Msc. Paco Bastidas Romo & Otros

63

Relación de equivalencia

1.

Construimos la tabla de verdad de: [(p v q)  q2 ]  [q2  (p v q)] p V V V V F F F F

q V V F F V V F F

q2 V F V F V F V F

[ (p V V V V F F F F

v V V V V V V F F

q) V V F F V V F F

 V F V F V F F F

q2 ] V F V F V F V F

[ q2 V F V F V F V F

 V V V V V V V V

 V F V F V F F F

(p V V V V F F F F

v V V V V V V F F

q) ] V V F F V V F F

2. Se excluyen los caso (V,F) y (F,V). 3. El polinomio es una tautología para el bicondicional, en la columna resultado. 4. Por lo tanto: [(p v q)  q2 ] ≡ [q2  (p v q)] Ejemplo 3. Sea (p1  p1)  p1. Determine si (pvq)  p1  p1, al efectuar la sustitución parcial de p1 por pvq. 1.

Construimos la tabla de verdad de: [(p v q)  p1]  p1 p V V V V F F F F

q V V F F V V F F

p1 V F V F V F V F

[ (p V V V V F F F F

V V V V V V V F F

q) V V F F V V F F

p1] V F V F V F V F

 V F V F V F F F

 V V V V V V F V

p1 V F V F V F V F

2. Se excluyen el caso (V,F). 3. El polinomio es una contingencia para el bicondicional, en la columna resultado. 4. Por lo tanto: (p v q)  p1 ≡p1 Observación: No se obtiene una equivalencia porque se efectuó una sustitución parcial de p 1 por (p v q). La sustitución debe ser en todas las variables. EJERCICIOS 1. Verificar el teorema sustitución de variables (SV) en las siguientes relaciones de equivalencia: 1. 3. 5. 7.

p1  V ≡ p1; si p1: p → q p  V ≡ p; si p: p v q p v F ≡ p; si p: p → q p  ~ p ≡ F; si p: p v q

2. 4. 6. 8.

p2 v p2 ≡ p2; si p2: p  q p  F ≡ F; si p: p v q p v V ≡ V; si p: ~(p v q) p v ~ p ≡ V; si p: p  q

4.5. TEOREMA: SUSTITUCIÓN DE EQUIVALENCIAS (SE) Si en una equivalencia se sustituyen algunas de sus variables y operadores, por proposiciones equivalentes, entonces las proposiciones resultantes también son equivalentes. Msc. Paco Bastidas Romo & Otros

64

Relación de equivalencia

Ejemplo 1. Verificar el teorema SE en p1  q2 ≡ q 2  p1 si p1  q2 ≡ ~ (p1  q2 ) 1. p1 V V F F

Construimos la tabla de verdad de (p1  q2)  (q2  p1) y de (p1  q2)  ~ (p1  q2). q2 V F V F

(p1 V V F F

 V F F F

q 2)  V V V F V V V F

(q2 V F V F

P1 ) V V F F

 V F F F

p1 V V F F

q2 V F V F

(p1 V V F F

q 2) V F V F

 V F F F

 V V V V

~ V F F F

(p1 V V F F

 F V V V

q 2) V F V F

Las dos fórmulas son equivalentes, por lo tanto: p1  q2 ≡ q2  p1 y p1  q2 ≡ ~ (p1  q2). 2. Al sustituir la equivalencia: p1  q2 ≡ ~ (p1  q2 ), en (p1  q2)  (q2  p1) se tiene: p1 V V F F

q2 V F V F

~ V F F F

(p1 V V F F

q 2) V F V F

 F V V V

 V V V V

(q2 V F V F

p1) V V F F

 V F F F

Por lo tanto: ~(p1q2) ≡ (q2  p1) Ejemplo 2. Verificar el teorema SE en: ~(p  q) ≡ (~ p v ~q), si (~ p v ~q) ≡ p  q 1.

Se construyen las tablas de verdad de las fórmulas dadas.

p

q

V V F F

V F V F

~ F V V V

(p



V V F F

V F F F

q)  V V F V V V F V

(~ p F F V V

V V F F

v F V V V

~

q)

p

q

(~

p

F V F V

V F V F

V V F F

V F V F

F F V V

V V F F

v F V V V

~ F V F V

q)  V V F V V V F V

(p  V F V V F V F V

q) V F V F

Son equivalencias, por lo tanto: ~(p  q) ≡ (~ p v ~q) y (~ p v ~q) ≡ (p  q). 2. Al reemplazar la equivalencia (~ p v ~q)  (p  q) en ~(p  q)  (~ p v ~q) se tiene: p V V F F

q V F V F

~ F V V V

(p V V F F

 V F F F

q) V F V F

 V V V V

(p V V F F

 F V V V

q) V F V F

Por lo tanto: ~(p  q) ≡ p  q

EJERCICIOS 1. Verificar el teorema sustitución de equivalencias (SE) en las siguientes relaciones: 1. 3. 5. 7. 9.

~(p  q)  ~p v ~q, si ~p v ~q ≡ p→ ~q p → q  ~ p v q, si p→q  ~q→ ~p pq ≡ ~(p v q), si pq ≡ ~p  ~ q (pq)(p→q)(q→p), si ~(pvq)(p→q)(q→p) ~(~ p v ~q)  (p  q), si p  q ≡ ~ (p  q)

Msc. Paco Bastidas Romo & Otros

65

2. ~(p v q)  ~p  ~q, si ~p  ~q ≡ pq 4. pq ≡ ~(p  q), si (~p v ~q) ≡ ~(p  q) 6. (p↙q) ≡ ~(p  q), si p  V ≡ p 8. (p v q) ≡ ~(p  q), si q v F ≡ q 10. ~(~ p  ~q)  (p v q), p v q ≡ ~ (p  q) Relación de equivalencia

4.6. PROPIEDADES DE LA RELACIÓN DE EQUIVALENCIA LÓGICA La relación entre proposiciones definida por P(p,q, ...)  Q(p,q, ...), donde P y Q representan polinomios booleanos, cumple con las siguientes propiedades: Reflexiva, simétrica y transitiva. 1.- REFLEXIVA. Toda proposición es equivalente a si misma. En forma simbólica se escribe de la siguiente manera: U = P. ∀P(p,q, …): P( p,q, ...) ≡ P(p,q, ...) U = P. ∀P: P ≡ P U = P se lee “El universo es el conjunto de todos los polinomios booleanos. ∀: se lee, “para todo” Ejemplo: Verificar la propiedad reflexiva entre ~(p  q) y ~(p  q) 1. Se construyen las tablas de verdad de las fórmulas dadas. p V V F F

q V F V F

~ F V V V

(p V V F F

 V F F F

q) V F V F

 V V V V

~ F V V V

(p V V F F

 V F F F

q) V F V F

P(p,q)

Q(p,q)

V

V

F

F

2. Los casos excluidos, en la tabla y diagrama sagital, son: (V,F) y (F,V). 3. El polinomio es una tautología, en la columna resultado, para el bicondicional. 4. Entonces, ~(p  q) es equivalente a ~ (p  q), simbólicamente se indica de la siguiente manera: ~(p  q)  ~ (p  q)

o

~(p  q) ≡ ~ (p  q)

2. SIMÉTRICA. Si una proposición P(p,q, ...) es equivalente a Q( p,q, ...), se tiene que Q(p,q, ...) es equivalente a P(p,q, ...). Simbólicamente se indica de la siguiente manera: U = P.

∀P(p,q, …), ∀Q(p,q, …): U = P.

P(p,q, ...)  Q(p,q, ...) ≡ Q(p,q, ...)  P( p,q, ...)

∀P, Q: P  Q ≡ Q  P

Ejemplo: Verificar la propiedad simétrica entre ~(p  q) y (~ p v ~q). A continuación se verifica que: P(p,q, ...)  Q(p,q, ...). 1. Se construyen las tablas de verdad para los polinomios dados: p

q

V V F F

V F V F

~ F V V V

(p



q)



(~

p

V V F F

V F F F

V F V F

V V V V

F F V V

V V F F

v F V V V

~

q)

F V F V

V F V F

P(p,q)

Q(p,q)

V

V

F

F

2. Los casos excluidos, en la tabla y diagrama sagital, son: (V,F) y (F,V). 3. El polinomio es una tautología, en la columna resultado, para el bicondicional. 4. Por lo que, ~(p  q) es equivalente a (~p v ~q), es decir: ~(p  q)  (~p v ~q) Msc. Paco Bastidas Romo & Otros

66

Relación de equivalencia

Del mismo modo, se verifica que: Q(p,q, ...)  P(p,q, ...). 1. Se construye la tabla de verdad, intercambiando el orden de los polinomios dados. p V V F F

q V F V F

(~ F F V V

p V V F F

v F V V V

~ F V F V

q) V F V F

~ F V V V

 V V V V

(p V V F F

 V F F F

q) V F V F

P(p,q)

Q(p,q)

V

V

F

F

2. Los casos excluidos, en la tabla y diagrama sagital, son: (V,F) y (F,V). 3. El polinomio es una tautología, en la comuna resultado, para el bicondicional. 4. Luego, (~ p v ~q) es equivalente a ~(p  q), es decir: (~ p v ~q)  ~(p  q) Por lo tanto: ~(p  q)  (~ p v ~q) ≡ (~ p v ~q)  ~(p  q) 3.-TRANSITIVA Si una primera proposición es equivalente a una segunda y esta es equivalente a una tercera, implica que la primera es equivalente a la tercera. Es decir: U = P. ∀P(p,q, …), ∀Q(p,q, …), ∀R(p,q, …): P(p,q,…)Q(p,q, …)  Q(p,q, …) R(p,q, …)  P(p,q, …)  R(p,q, …). U = P. ∀P, Q, R: PQ  QR  P  R Ejemplo. 1. Verificar que p  q  q  r  p  r. p V V V V F F F F

q V V F F V V F F

r V F V F V F V F

(p V V V V F F F F

 V V F F F F V V

q) V V F F V V F F

 V F F F F F F V

(q V V F F V V F F

 V F F V V F F V

r) V F V F V F V F

→ V V V V V V V V

(p V V V V F F F F

 V F V F F V F V

r) V F V F V F V F

2. Verificar que en la siguiente expresión se presenta el caso (V,V) de la propiedad transitiva de la relación de equivalencia: {(~ p v ~q)  ~(p  q)}  { ~(p  q)  (p  q)} → {(~ p v ~q)  (p  q)} Se construyen las tablas de verdad de las fórmulas dadas. 1. {(~ p v ~q)  ~(p  q)} p

q

(~

p

V V F F

V F V F

F F V V

V V F F

Msc. Paco Bastidas Romo & Otros

v F V V V

~

q)



F V F V

V F V F

V V V V

67

~ F V V V

(p



q)

V V F F

V F F F

V F V F

Relación de equivalencia

2. { ~(p  q)  (p  q)} P V V F F

q V F V F

~ F V V V

(p V V F F

q) V F V F

 V F F F

(p V V F F

 V V V V

q) V F V F

 F V V V

3. {(~ p v ~q)  (p  q)} P V V F F

q V F V F

(~ F F V V

p V V F F

v F V V V

~ F V F V

q) V F V F

 V V V V

(p V V F F

 F V V V

q) V F V F

Considerando la columna resultado de los tres polinomios y los respectivos operadores lógicos, se tiene: p

q

(1



2)

→

3

V V F F

V F V F

V V V V

V V V V

V V V V

V V V V

V V V V

Por lo tanto, en la expresión {(~p v ~q)  ~(p  q)}  {~(p  q)  (p  q)} → {(~p v ~q)  (p  q)} se presenta el caso (V,V) de la propiedad transitiva de la relación de equivalencia: EJERCICIOS 1.

Verificar las siguientes propiedades: 1. 3. 5. 7.

Reflexiva : p  q ≡ p  q Simétrica : p v q  ~(p  q) ≡ ~(p  q)  p v q Simétrica : p→q  ~ p v q ≡ ~ p v q  p→q Reflexiva : ~(p  q) ≡ ~(p  q)

2. Reflexiva : p v q ≡ p v q 4. Reflexiva : q ≡ q 6. Reflexiva : ~ p v q ≡ ~ p v q 8. Simétrica : p v q ≡ qvp  qvp ≡ pvq

2. Determinar el caso que se presenta, de la propiedad transitiva, en los siguientes polinomios booleanos: 1. Transitiva: {(~ p v ~q)  ~ (p  q)} {~ (p  q)  (pq)} → (~ p v ~q)  (pq). 2. Transitiva: {( p v q)  ~ (p  q)} {~ (p q)  ~ [(p→q)  (q→p)]} → {(p v q)  ~ [(p→q)  (q→p)]} 3. transitiva: {(~ p v ~q)  (p ۸ q)}  {(p  q)  (p  q)} → {(~ p v ~q)  ( p  q)} 4.7. ÁLGEBRA DE PROPOSICIONES Hasta fines del siglo XIX, se consideraba al álgebra como la generalización de la aritmética, mediante la simbolización de los números por letras. En la actualidad, se llama álgebra al estudio de estructuras abstractas no necesariamente numéricas ni sometidas a las operaciones aritméticas fundamentales. En general, se llama Álgebra de proposiciones a las operaciones: conjunción, disyunción inclusiva y negación; a sus propiedades y los teoremas que se deducen de las mismas. Para la demostración de los teoremas se requiere de estas leyes y sólo de ellas. Tanto las leyes como los teoremas son relaciones de equivalencia. Msc. Paco Bastidas Romo & Otros

68

Relación de equivalencia

4.7.1. LEYES DEL ÁLGEBRA PROPOSICIONES (, v, , ~) Las siguientes leyes se cumplen para las operaciones conjunción ( ), disyunción inclusiva (v) y negación (~): NOMBRE 1. Idempotencia

CONJUNCIÓN

DISYUNCIÓN INCLUSIVA

pp≡p

pvp≡p

2. Conmutativa.

pq≡qp

pvq≡qvp

3. Asociativa.

(p  q)  r ≡ p  (q  r)

(p v q) v r ≡ p v (q v r)

4. Distributiva

p (q v r) ≡ (p  q) v (p  r)

p v (q  r) ≡ (p v q)  (p v r)

5. Identidad

pV≡p

pF≡F

pvV≡V

6. Complemento

p  ~p ≡ F

~(~ p) ≡ p