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.