2.

{ ~(p  q)  (p  q)}

P q ~ (p  q)  (p  q)
V V F V V V V V F V
V F V V F F V V V F
F V V F F V V F V V
F F V F F F V F V F

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

P q (~ p v ~ q)  (p  q)
V V F V F F V V V F V
V F F V V V F V V V F
F V V F V F V V F V V
F F V F V V F 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 V V V V V
V F V V V V V
F V V V V V V
F F 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. Reflexiva : p  q ≡ p  q 2. Reflexiva : p v q ≡ p v q
3. Simétrica : p v q  ~(p  q) ≡~(p  q)  p v q 4. Reflexiva : q ≡ q
5. Simétrica : pq  ~ p v q ≡ ~ p v q  pq 6. Reflexiva : ~ p v q ≡ ~ p v q
7. Reflexiva : ~(p  q) ≡ ~(p  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 boolianos:
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 CONJUNCIÓN DISYUNCIÓN INCLUSIVA

1. Idempotencia 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 pvF≡p
6. Complemento p  ~p ≡ F ~(~ p) ≡ p p v ~p ≡ V ~V ≡ F ~F ≡ V
7. Morgan ~(p  q) ≡ ~p v ~q ~(p v q) ≡ ~p  ~q

La verificación de las leyes se realiza mediante tablas de verdad, como se indica a continuación:

a. IDEMPOTENCIA.

Construimos las tablas de verdad.

p (p  p)  P p (p v p)  p
V V V V V V V V V V V V
F F F F V F F F F F V F

En ambos casos se obtienen equivalencias, por lo tanto: p  p ≡ p y p v p ≡ p

b. CONMUTATIVA.

Construimos las tablas de verdad:

p q (p  q)  (q  p) p q (p v q)  (q v p)
V V V V V V V V V V V V V V V V V V
V F V F F V F F V V F V V F V F V V
F V F F V V V F F F V F V V V V V F
F F F F F V F F F F F F F F V F F F

En ambos casos se obtienen equivalencias, por lo tanto: p  q ≡ q  p y p v q ≡ q v p.

c. ASOCIATIVA: (p  q)  r ≡ p  (q  r).

P q r [ (p  q)  r]  [p  (q  r) ]
V V V V V V V V V V V V V V
V V F V V V F F V V F V F F
V F V V F F F V V V F F F V
V F F V F F F F V V F F F F
F V V F F V F V V F F V V V
F V F F F V F F V F F V F F
F F V F F F F V V F F F F V
F F F F F F F F V F F F F F

Msc. Paco Bastidas Romo & Otros 69 Relación de equivalencia

d. DISTRIBUTIVA.

Existen dos leyes distributivas: de la conjunción respecto de la disyunción y de la disyunción respecto de la

conjunción. A continuación se verifica la primera:

p q r [p  (q V r)]  [(p  q) v (p  r) ]
V V V V V V V V V V V V V V V V
V V F V V V V F V V V V V V F F
V F V V V F V V V V F F V V V V
V F F V F F F F V V F F F V F F
F V V F F V V V V F F V F F F V
F V F F F V V F V F F V F F F F
F F V F F F V V V F F F F F F V
F F F F F F F F V F F F F F F F

Se obtiene una equivalencia, por lo tanto: p (q v r) ≡ (p  q) v (p  r)

e. IDENTIDAD.

p (p  V)  P p (p  F)  F
V V V V V V V V F F V F
F F F V V F F F F F V F

p (p v F)  P p (p v V)  V
V V V F V V V V V V V V
F F F F V F F F V V V V

En los cuatro casos se obtienen equivalencias, por lo tanto:

pV≡p pF≡F PvV≡V PvF≡P

EJERCICIOS

1. Verifique las siguientes leyes del álgebra de proposiciones, mediante tablas de verdad:

1. Asociativa de la disyunción inclusiva.

2. Distributiva de la disyunción inclusiva respecto de la conjunción
3. Complemento
4. Morgan

4.7.2. DEMOSTRACIÓN DE TEOREMAS.

DEFINICIÓN

En general, se llama demostración al proceso mediante el cual se establece la verdad de una proposición.

En otras palabras, se llama demostración al conjunto de pasos (proceso) explicados en detalle, mediante el
cual se evidencia la verdad de una proposición (teorema).

Msc. Paco Bastidas Romo & Otros 70 Relación de equivalencia

a. DEMOSTRACIÓN DE EQUIVALENCIAS.

Generalmente, se hace necesario convertir uno de los miembros de la equivalencia, en la forma que tiene el
otro miembro. A estas conversiones se les conoce con el nombre de demostración de equivalencias.

En la demostración de equivalencias cada paso es una proposición verdadera. La verdad de cada una de esas
proposiciones, en que se descompone la demostración, se justifica por algunas de las siguientes razones:

1. Por definiciones.
2. Por un axioma, propiedad o ley.
3. Por un teorema demostrado anteriormente.

b. RECOMENDACIONES PARA LAS DEMOSTRACIONES.

No existe una regla general para llevar a efecto estas conversiones, pero las indicaciones siguientes pueden
ser muy útiles en este tipo de operaciones.

1. Inicie la demostración con el miembro que tiene un mayor número de variables y/o operadores. Se
puede trabajar en ambos miembros hasta obtener equivalencias expresadas en las mismas variables
y operadores, es decir, que tengan la misma forma.
2. Registre las conversiones, en la parte izquierda (proposiciones), mediante pasos numerados en orden
sucesivo.
3. Registre las justificaciones, para los pasos anteriores, en la parte derecha (razones: definiciones,
axiomas, propiedades, leyes, teoremas demostrados anteriormente).

Ejemplos.

1.- DEMOSTRAR (p  p) v q  q v p

Se inicia la demostración con el primer miembro, porque tiene un mayor número de variables y/o operadores.
Por lo tanto, se trata de obtener el segundo miembro, a partir del primero.

PROPOSICIONES RAZONES
1. (p  p) v q  (p  p) v q Axi. Reflexivo (≡)
2. (p  p) v q  p v q Idempotencia
3. (p  p) v q  q v p Conmutativa

Observaciones:
1. En el paso 1. Se tiene que el primer miembro es equivalente a sí mismo (axioma reflexivo).
2. En el paso 2. Se repite el primer miembro de la relación de equivalencia. En el segundo miembro, se
tiene que: p  p es equivalente a p (ley de idempotencia), entonces efectuamos dicha sustitución.
3. En el paso 3. Se repite el primer miembro de la equivalencia anotada en el paso 2. Luego, aplicamos la
propiedad conmutativa en el segundo miembro de la equivalencia.

De esta manera se obtiene el segundo miembro a partir del primero.

2. DEMOSTRAR ~(~ p  ~q) ≡ p v q

PROPOSICIONES RAZONES
1. ~(~ p  ~q) ≡ ~(~ p  ~q) Axi. Reflexivo (≡)
2. ~(~ p  ~q) ≡ ~ (~ p) v ~ (~q) Morgan
3. ~(~ p  ~q) ≡ p v q Complemento
Msc. Paco Bastidas Romo & Otros 71 Relación de equivalencia
3. DEMOSTRAR: ~ (~ p v ~q)  p  q

PROPOSICIONES RAZONES
1. ~ (~ p v ~q)  ~ (~ p v ~q) Axi. Reflexivo (≡)
2. ~ (~ p v ~q)  ~(~ p)  ~(~q) Morgan
3. ~ (~ p v ~q)  p  q Complemento

4. DEMOSTRAR: ~p v q ≡ ~(p  ~q)

PROPOSICIONES RAZONES
1. ~ p v q ≡ ~ p v q Axi. Reflexivo (≡)
2. ~ p v q ≡ ~p v ~( ~ q) Complemento
3. ~ p v q ≡ ~(p  ~ q ) Morgan

5. DEMOSTRAR: (p v ~q)  (~ r v p) ≡ p v ~(q v r)

PROPOSICIONES RAZONES
1. (p v ~q)  (~ r v p) ≡ (p v ~q)  (~ r v p) Axi. Reflexivo ()
2. (p v ~q)  (~ r v p) ≡ (p v ~q)  (p v ~ r) Conmutativa
3. (p v ~q)  (~ r v p) ≡ p v (~ q  ~ r) Distributiva
4. (p v ~q)  (~ r v p) ≡ p v ~ (q v r) Morgan

6. DEMOSTRAR: (p v q)  (p v ~q) ≡ p

PROPOSICIONES RAZONES
1. (p v q)  (p v ~q) ≡ (p v q)  (p v ~q) Axi. Reflexivo ()
2. (p v q)  (p v ~q) ≡ p v (q  ~q) Distributiva
3. (p v q)  (p v ~q) ≡ p v F Complemento
4. (p v q)  (p v ~q) ≡ p Identidad

7. DEMOSTRAR: (q  p) v (q  ~p) ≡ q

PROPOSICIONES RAZONES
1. (q  p) v (q  ~ p) ≡ (q  p) v (q  ~ p) Axi. Reflexivo ()
2. (q  p) v (q  ~ p) ≡ q  (p v ~ p) Distributiva
3. (q  p) v (q  ~ p) ≡ q  V Complemento
4. (q  p) v (q  ~ p) ≡ q Identidad

8. DEMOSTRAR: (p  r) v (q  r) ≡ (p v q)  r

PROPOSICIONES RAZONES
1. (p v q)  r ≡ (p v q)  r Axi. Reflexivo (≡)
2. (p v q)  r ≡ r  (p v q) Conmutativa
3.- (p v q)  r ≡ (r  p) v (r  q) Distributiva
4.- (p v q)  r ≡ (p  r) v (q  r) Conmutativa

9. DEMOSTRAR: (p  q) v r  (p v r)  (q v r)

PROPOSICIONES RAZONES
1. (p  q) v r  (p  q) v r Axi. Reflexivo ()
2. (p  q) v r  r v (p  q) Conmutativa
3. (p  q) v r  (r v p)  (r v q) Distributiva
4. (p  q) v r  (p v r)  (q v r) Conmutativa
Msc. Paco Bastidas Romo & Otros 72 Relación de equivalencia
10. DEMOSTRAR: p  (~ p v q) ≡ p  q

PROPOSICIONES RAZONES
1. p  (~ p v q) ≡ p  (~ p v q) Axi. Reflexivo (≡)
2. p  (~ p v q) ≡ (p  ~ p) v (p  q) Distributiva
3. p  (~ p v q) ≡ F v (p  q) Complemento
4. p  (~ p v q) ≡ (p  q) v F Conmutativa
5. p  (~ p v q) ≡ (p  q) Identidad

11. DEMOSTRAR: (p v q)  ~p ≡ ~p  q

PROPOSICIONES RAZONES
1. (p v q)  ~ p ≡ (p v q)  ~ p Axi. Reflexivo (≡)
2. (p v q)  ~ p ≡ ~ p  (p v q) Conmutativa
3. (p v q)  ~ p ≡ (~ p  p) v (~ p  q) Distributiva
4. (p v q)  ~ p ≡ F v (~ p  q) Complemento
5. (p v q)  ~ p ≡ (~ p  q) v F Conmutativa
6. (p v q)  ~ p ≡ (~ p  q) Identidad

4.7.3. TEOREMA DUAL

Si se intercambia la  (conjunción) por la v (disyunción inclusiva), así como V por F, en cualquier

razonamiento sobre proposiciones, el nuevo enunciado resultante (teorema) se llama dual del primero.

Dado cualquier teorema y su demostración, el dual de dicho teorema se puede demostrar del mismo modo,
empleando el dual de cada paso de la primera demostración. Por ejemplo:

PROPOSICIONES RAZONES
1. (p  p) v q  (p p) v q Axi. Reflexivo (≡)
2. (p  p) v q  p v q Idempotencia
3. (p  p) v q  q v p Conmutativa

PROPOSICIONES RAZONES
1. (p v p)  q  (p v p)  q Axi. Reflexivo (≡)
2. (p v p)  q  p  q Idempotencia
3. (p v p)  q  q  p Conmutativa

EJERCICIOS

1. Demostrar los siguientes teoremas (proposiciones deducidas), mediante axiomas y/o definiciones.
1. (p v p)  q  q  p, dual del 1 2. ~ p  q  ~ (p v ~ q), dual del 4
3. (p  ~q) v (~ r  p)  p  ~ (q  r), dual del 5 4. (p  q) v (p  ~ q) ≡ p, dual del 6
5. (q v p)  (q v ~ p) ≡ q, dual del 7 6. (p v r)(q v r) ≡ (p  q) v r, dual del 8
7. (p v q)  r  (p  r) v (q  r), dual del 9 8. p v (~p  q) ≡ p v q, dual del 10
9. (p  q) v ~ p ≡ ~ p v q, dual del 11 10. ~(p  q)(~ p v q)  ~ p
11. ~(p v ~q) ≡ ~ p  q 12. (p  q) v ~ p ≡ ~(p  ~q)
13. (p v q)  ~ p  ~ (p v ~q) 14. ~(p  ~q) ≡ ~ p v q
2. Hallar el teorema dual de las siguientes equivalencias.
1. ~[(p v q) v (p v ~q)] ≡ ~ p 2. ~[(p  q) v (p  ~q)]  ~ p
3. ~[(p  p) v q] ≡ ~q  ~ p 4. ~[(p v p)  q] ≡ ~ q v ~ p
5. ~[~ r  q]  r v ~ q 6. ~[~ r v q] ≡ ~ q  r

Msc. Paco Bastidas Romo & Otros 73 Relación de equivalencia

4.7.4. LEY DE ABSORCIÓN O DE SIMPLIFICACIÓN (L.S).

Las siguientes equivalencias son de uso frecuente en las demostraciones. Se les conoce con el nombre de ley
de simplificación o de absorción.

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

Verificación mediante tablas de verdad:

p q [p v (p  q)]  p
V V V V V V V V V
V F V V V F F V V
F V F F F F V V F
F F F F F F F V F

p q [p  (p v q)]  p
V V V V V V V V V
V F V V V V F V V
F V F F F V V V F
F F F F F F F V F

1. DEMOSTRAR: p v (p  q) ≡ p

PROPOSICIONES RAZONES
1. p v (p  q) ≡ p v (p  q) Axi. Reflexivo (≡)
2. p v (p  q) ≡ (p  V) v (p  q) Identidad
3. p v (p  q) ≡ p  (V v q) Distributiva
4. p v (p  q) ≡ p  V Identidad
5. p v (p  q) ≡ p Identidad

Aplicando la propiedad conmutativa esta propiedad presenta las siguientes formas.

1 2 3 4
p v (p  q) ≡ p p v (q  p) ≡ p (p  q) v p ≡ p (q  p) v p ≡ p

2. DEMOSTRAR: p  (p v q) ≡ p (Teorema dual del 1)

PROPOSICIONES RAZONES
1. p  (p v q) ≡ p  (p v q) Axi. Reflexivo (≡)
2. p  (p v q) ≡ (p v F)  (p v q) Identidad
3. p  (p v q) ≡ p v (F  q) Distributiva
4. p  (p v q) ≡ p v F Identidad
5. p  (p v q) ≡ p Identidad

Aplicando la propiedad conmutativa se tiene:

1 2 3 4
p  (p v q) ≡ p p  (q v p) ≡ p (p v q)  p ≡ p (q v p)  p ≡ p

Msc. Paco Bastidas Romo & Otros 74 Relación de equivalencia

EJEMPLOS:

1. DEMOSTRAR: (q v p)  p ≡ p

PROPOSICIONES RAZONES
1. (q v p)  p ≡ (q v p)  p Axi. Reflexivo (≡)
2. (q v p)  p ≡ p  (q v p) Conmutativa
3. (q v p)  p ≡ p  (p v q) Conmutativa
4. (q v p)  p ≡ p LS.

2. DEMOSTRAR: (q  p) v p ≡ p (Teorema dual del 1).

PROPOSICIONES RAZONES
1. (q  p) v p ≡ (q  p) v p Axi. Reflexivo (≡)
2. (q  p) v p ≡ p v (q  p) Conmutativa
3. (q  p) v p ≡ p v (p  q) Conmutativa
4. (q  p) v p ≡ p LS.

3. DEMOSTRAR. (p v q) v [p  (r v q)] ≡ p v q

PROPOSICIONES RAZONES
1. (p v q) v [p  (r v q)] ≡ (p v q) v [p  (r v q)] Axi. Reflexivo (≡)
2. (p v q) v [p  (r v q)] ≡ [(p v q) v p]  [(p v q) v (r v q)] Distributiva
3. (p v q) v [p  (r v q)] ≡ [(q v p) v p]  [(p v q) v (r v q)] Conmutativa
4. (p v q) v [p  (r v q)] ≡ [q v (p v p)]  [(p v q) v (r v q)] Asociativa
5. (p v q) v [p  (r v q)] ≡ (p v q)  [(p v q) v (r v q)] Idempotencia/Conmutativa
6. (p v q) v [p  (r v q)] ≡ (p v q) L.S

4. DEMOSTRAR. (p  q)  [p v (r  q)] ≡ p  q (Teorema dual del 3)

PROPOSICIONES RAZONES
1. (p  q)  [p v (r  q)] ≡ (p  q)  [p v (r  q)] Axi. Reflexivo (≡)
2. (p  q)  [p v (r  q)] ≡ [(p  q)  p] v [(p  q)  (r  q)] Distributiva
3. (p  q)  [p v (r  q)] ≡ [(q  p)  p] v [(p  q)  (r  q)] Conmutativa
4. (p  q)  [p v (r  q)] ≡ [q  (p  p)] v [(p  q)  (r  q)] Asociativa
5. (p  q)  [p v (r  q)] ≡ (p  q) v [(p  q)  (r  q)] Idempotencia/Conmutativa
6. (p  q)  [p v (r  q)] ≡ (p  q) L.S

EJERCICIOS

1. Demostrar los siguientes teoremas:

1. ~[(p v q)  (p v ~q)] ≡ ~ p 2. ~[(p  q) v (p  ~q)]  ~ p

3. ~[(p  p) v r] ≡ ~r  ~ p 4. ~[(p v p)  r] ≡ ~ r v ~ p
5. ~[~ r  q]  r v ~ q 6. ~[~ r v q] ≡ ~ q  r
7. ~[(p v ~q)  (~ r v p)] ≡ ~ p  (q v r) 8. ~[(p  ~q) v (~ r  p)] ≡ ~p v (q  r)
9. ~[(p  q) v r]  (~ p  ~ r) v (~q  ~ r) 10. ~[(p  q) v ~ p]  p  ~q
11. ~[(p v q)  ~ p] ≡ p v ~q 12. [(p  q)  r] v (p  q)  q  p
13. (r v F)  [q v (F v r) ] ≡ r 14. [(r  V) v q]  (V  r) ≡ r
15. q1  (q2 v q1) ≡ q1 16. (p  q)  [p v (r  q)] ≡ p  q
17. ~ [ (r v q)  q ]  ~ q 18. ~ [ (r  q) v q ]  ~ q
19. ~ [ ( q v r)  q ] ≡ ~ q 20. ~ [ ( q  r) v q] ≡ ~ q

Msc. Paco Bastidas Romo & Otros 75 Relación de equivalencia

4.7.5. SUSTITUCIÓN DE EQUIVALENCIAS.

En la demostración de algunos teoremas, es necesario sustituir las equivalencias estudiadas en el capítulo 3

(reducción de operadores):

E1: (p  q) ≡ ~(p  q) E 2: (p ↖ q) ≡ ~(p  q)

E 3: (p ↙ q) ≡ ~(p  q) E 4: (p  q) ≡ ~(p v q)
E 5: (p v q) ≡ ~(p  q) E 6: (p  q)  p v (p  q)
E 7: (p  q)  (p  q)  (q  p) E 8: (p  q)  ~ p v q
E 9: ~(~ p v ~q)  (p  q) E10: ~(~ p  ~q)  (p v q)
E11: ~p  pp E12: ~p pp
E13: p v (p  q) ≡ p E14: p  (p v q) ≡ p
E15: ~pq≡~qp E16: p ~ q ≡ q ~ p
E17: p  q ≡ ~q  ~ p E18: qp≡~p~q
E19: pq≡qp

Observación: En las equivalencias: 1, 2, 3, 4, 5, 9, 10, 11, 12; la negación puede usarse en el primer miembro
o en el segundo. Por ejemplo: (p v q) ≡ ~(p  q) y ~ (p v q) ≡ (p  q).

1. DEMOSTRAR: ~ [(p v p)  q]  (p  q)

PROPOSICIONES RAZONES
1. ~ [ (p v p)  q] ≡ ~ [ (p v p)  q] Axi. Reflexivo (≡)
2. ~ [ (p v p)  q] ≡ ~ [ p  q] Idempotencia
3. ~ [ (p v p)  q] ≡ (p  q) E1:(p  q) ≡ ~ ( p  q)

2. DEMOSTRAR: (p  q)  (q  p)  ~(p v q)

PROPOSICIONES RAZONES
1. (p  q)  (q  p) ≡ (p  q)  (q  p) Axi. Reflexivo (≡)
2. (p  q)  (q  p) ≡ (p  q) LB
3. (p  q)  (q  p) ≡ ~ (p v q) E5: (p  q) ≡ ~ (p v q)

3. DEMOSTRAR: ~(p v q) v (~ p  q) ≡ pp

PROPOSICIONES RAZONES
1. ~(p v q) v (~ p  q) ≡ ~(p v q) v (~ p  q) Axi. Reflexivo (≡)
2. ~(p v q) v (~ p  q) ≡ (~ p  ~ q) v (~ p  q) Morgan
3. ~(p v q) v (~ p  q) ≡ ~ p  (~ q v q) Distributiva
4.- ~(p v q) v (~ p  q) ≡ ~ p  V Complemento
5. ~(p v q) v (~ p  q) ≡ ~ p Identidad
6. ~(p v q) v (~ p  q) ≡ p  p E12: ~ p  p  p

4. DEMOSTRAR: (q  p) v p ≡ ~(pp)

PROPOSICIONES RAZONES
1. (q  p) v p ≡ (q  p) v p Axi. Reflexivo (≡)
2. (q  p) v p ≡ p v (q  p) Conmutativa
3. (q  p) v p ≡ p v (p  q) Conmutativa
4. (q  p) v p ≡ p LS.
5. (q  p) v p ≡ ~(p  p) E12: p  ~ (p  p)

Msc. Paco Bastidas Romo & Otros 76 Relación de equivalencia

5. DEMOSTRAR: ~ (p  ~q) ≡ ~q  ~ p

PROPOSICIONES RAZONES
1. ~ (p  ~q) ≡ ~ (p  ~q) Axi. Reflexivo (≡)
2. ~ (p  ~q) ≡ ~ p v ~~q) Morgan
3. ~ (p  ~q) ≡ ~ p v q Complemento
4. ~ (p  ~q) ≡ p  q E8: (p  q)  ~ p v q
5. ~ (p  ~q) ≡ ~q  ~ p E16: p  q ≡ ~q  ~ p

EJERCICIOS

1. Demostrar los siguientes teoremas:

1. ~ [ (p v p)  q]  (p  q) 2. ~ [p v (~ p  q) ] ≡ (p  q)
3. (p v r)  ~ p ≡ ~ p  r 4. (p v r)  ~ p ≡ ~ (r  p)
5. [(p  q)  r] v (p  q)  ~(~ p v ~q) 6. ~[~ p  ~ q ] ≡ q  ~ p
7. ~[(~q  ~ p)  (~ r v p)] ≡ ~ p  (q v r) 8. [(p v q)  ~ p] ≡ p ↖ q
9. (r v q) ≡ ~[ (r  V)  (q v F) ] 10. (r  q)  (r  V) v (r  q)

11. ~(p  V)  p  (p  V) 12. ~ (p v F)  (p v F)  p

13. ~[(p v q)  (p v ~q)] ≡ p  p 14. ~[(p  q) v (p  ~q)]  p  p
15. ~[(p  p) v r] ≡ r  p 16. ~[(p v p)  r] ≡ r  p
17. ~[~ r  q]  r  q 18. ~[~ r v q] ≡ (q  q )  r
19. ~[(p v q)  ~ p] ≡ ~ p  ~ q 20. [(p  q)  r] v (p  q)  ~ (p  q)

21. (r v F)  [q v (F v r) ] ≡ ~ (r  r) 22. [(r  V) v q]  (V  r) ≡ ~(r  r)

23. q1  (q2 v q1) ≡ q1 24. (p  q)  [p v (r  q)] ≡ ~ (p  q)
25. ~ [ (r v q)  q ]  q  q 26. ~ [ (r  q) v q ]  q  q
27. ~ [ ( q v r)  q ] ≡ q  q 28. ~ [ ( q  r) v q] ≡ q  q
29. p  q ≡ p  (~ p v q) 30. (p v q)  ~ p ≡ ~ p  q

4.7.6. REDUCCIÓN A NEGACIÓN ALTERNATIVA.

La reducción a un solo operador, negación alternativa (, no … tampoco), se demuestra de la siguiente

manera:

Para la conjunción:

PROPOSICIONES RAZONES
1. p  q  ~(~ p v ~q) E9 : ~(~ p v ~q)  (p  q)
2. p  q  ~[~(p  q)] E9: ~ p v ~ q  ~ (p  q)
3. p  q  ~[p  q] E1: ~ (p  q)  p  q
4. p  q  (p  q)  (p  q) E11 ~p  pp

Para la disyunción inclusiva:

PROPOSICIONES RAZONES
1. p v q  ~(~ p  ~q) E10 : ~(~ p  ~q)  (p v q)
2. p v q  ~ p  ~ q E1: ~ (p  q)  p  q
3. p v q  (p  p)  (q  q) E11: ~ p  p  p

Observación: Verificar los teoremas anteriores mediante tablas de verdad.

Msc. Paco Bastidas Romo & Otros 77 Relación de equivalencia