Cálculo Proposicional

Una demostración en el Cálculo Proposicional que veremos en este curso consiste en probar la validez de una fórmula mediante una serie de pasos justificados con axiomas y teoremas del Cálculo.

El cálculo proposicional nos permite demostrar teoremas y propiedades al estilo de un cálculo; como cuando despejamos una \(x\) para resolver una ecuación.

La expresión de un teorema es en esencia una expresión booleana, y su prueba es, en esencia, calcular que esa expresión tiene valor verdadero. La forma más directa de “evaluar” una expresión booleana es someterla a una o varias transformaciones que preserven el valor de verdad hasta que alcancemos una formulación simplificada de la expresión, en el caso de un teorema: \(\; True\).

Por lo tanto una demostración será una serie de formulas, equivalentes entre sí, donde la primera formula es la que queremos demostrar válida y la última es \(\; True\).

Equivalencia, Discrepancia y Negación

A1 Asociatividad equivalencia: \(((P ≡ Q) ≡ R) ≡ (P ≡ (Q ≡ R))\)

A2 Conmutatividad equivalencia: \(P ≡ Q ≡ Q ≡ P\)

A3 Neutro equivalencia: \(P ≡ True ≡ P\)

A4 Definición de Negación: \(¬(P ≡ Q) ≡ ¬P ≡ Q\)

A5 Definición de False: \(False ≡ ¬True\)

A6 Definición de discrepancia: \(P \not\equiv Q ≡ ¬(P ≡ Q)\)

A7 Asociatividad de la discrepancia: \((p \not\equiv (q \not\equiv r)) ≡ ((p \not\equiv q) \not\equiv r)\)

A8 Reflexividad del equivalente: \((p ≡ p) ≡ True\)

A9 Equivalencia y negación: \(p ≡ False ≡ ¬p\)

Ejercicios resueltos - Equivalencia, Discrepancia y Negación

1.

Demostrar la asociatividad de la discrepancia: \((p \not\equiv (q \not\equiv r)) ≡ ((p \not\equiv q) \not\equiv r)\)

Para realizar la demostración, partimos del lado izquierdo:

≡ { Definición de \(\not\equiv Q := (q \not\equiv r)\) }

≡ { Definición de \(\not\equiv(P, Q := q, r)\) }

≡ { Definición de \(¬\) \((P, Q := q, r)\) }

≡ { Definición de \(\not\equiv\) \((P, Q := (p ≡ ¬q), r)\) }

≡ { Conmutatividad de \(≡ (Q := ¬q)\) }

≡ { Definición de \(¬\) \((P, Q := q, p)\) }

≡ { Conmutatividad de ≡ }

≡ { Definición de \(\not\equiv\) }

2.

Demostrar la validez de la doble negación: \(¬¬p ≡ p\):

≡ { Definición de negación \(¬(P ≡ Q) ≡ ¬P ≡ Q, P:= ¬p, Q:=p\) }

≡ {Conmutatividad del ≡ \((P ≡ Q ≡ Q ≡ P, P:= ¬p, Q:=p)\) }

≡ { Definición de negación \((¬(P ≡ Q) ≡ ¬P ≡ Q, P:=p , Q:=¬p)\) }

≡ { Reflexividad del ≡ }

3.

Demostrar la validez de la equivalencia y negación: \(p ≡ False ≡ ¬p\)

{ Definición de conmutatividad \(P ≡ Q ≡ Q ≡ P\) \((P:= False, Q:= ¬P)\) }

{ Definición de negación \(¬(P≡Q)≡¬P≡Q \) \((P:=P, Q:= False)\) }

{ Definición de conmutatividad \(P≡Q≡Q≡P\) \((P:=p, Q:= False)\) }

{ Definición de negación \(¬(P≡Q)≡¬P≡Q\) \((P:= False, Q:=P)\) }

{ Neutro de la equivalencia, reflexividad de \(≡\) }

Disyunción y Conjunción

A7 Asociatividad disyunción: \((P ∨ Q) ∨ R ≡ P ∨ (Q ∨ R) \)

A8 Conmutatividad disyunción: \(P ∨ Q ≡ Q ∨ P\)

A9 Idempotencia disyunción: \(P ∨ P ≡ P\)

A10 Distributividad disyunción con equivalencia: \(P ∨ (Q ≡ R) ≡ (P ∨ Q) ≡ (P ∨ R)\)

A11 Tercero excluido: \(P ∨ ¬P ≡ True\)

A12 Regla dorada: \(P ∧ Q ≡ P ≡ Q ≡ P ∨ Q\)

A13 Distributividad de la disyunción con la disyunción: \(p ∨ (q ∨ r) ≡ (p ∨ q) ∨ (p ∨ r)\)

A14 Elemento absorbente de la disyunción: \(p ∨ True ≡ True\)

A15 Elemento neutro de la disyunción: \(p ∨ False ≡ p\)

A16 Teorema Estrella : \(p ∨ q ≡ p ∨ ¬q ≡ p\)

Ejercicios resueltos - Conjunción y Disyunción

1.

Demostrar la validez de la distributividad de la disyunción con la disyunción: \(p ∨ (q ∨ r) ≡ (p ∨ q) ∨ (p ∨ r)\)

≡{ Asociatividad disyunción \((P ∨ Q) ∨ R ≡ P ∨ (Q ∨ R), P:= p, Q:= q, R:= r\) }

≡{ Idempotencia de la disyunción \(P ∨ P ≡ P, P:= p\) }

≡{ Conmutatividad disyunción \(P ∨ Q ≡ Q ∨ P, P:= p , Q:= q\) }

≡{ Asociatividad disyunción \((P ∨ Q) ∨ R ≡ P ∨ (Q ∨ R), P:= p ∨ q , Q:= p, R:= r\) }

≡{ Reflexividad de \(≡\) }

2.

Demostrar la validez del elemento absorbente de la disyunción: \(p ∨ True ≡ True\)

≡ { Reflexividad de equivalencia \((p ≡ p) ≡ True\) }

≡ { Distributividad disyunción con equivalencia
\((P ∨ (Q ≡ R) ≡ (P ∨ Q) ≡ (P ∨ R), P:= p, Q:= p, R:= p\) }

≡{ Idempotencia de la disyunción \(P ∨ P ≡ P, P:= p\) }

≡{ Conmutatividad de equivalencia }

≡{ Neutro de equivalencia \(P ≡ True ≡ P\) }

3.

Demostrar la validez del Teorema Estrella : \(p ∨ q ≡ p ∨ ¬q ≡ p\):

≡ { Distributividad disyunción con equivalencia
\((P ∨ (Q ≡ R) ≡ (P ∨ Q) ≡ (P ∨ R), P:= p, Q:= q, R:= ¬ q)\)}

≡{ Conmutatividad equivalencia }

≡{ Equivalencia y negación: \((P ≡ ¬P) ≡ False ≡ ¬P, P:= q\) }

≡{ Precedencia }

{ Elemento neutro de la disyunción \(p ∨ False ≡ p\), Reflexividad de \(≡\) }

Nota: Existen más teoremas y axiomas dentro de la lógica proposicional que se pueden encontrar en el digesto proposicional de la materia. Lo importante de esta sección es entender el método para resolver los ejercicios.