Propiedades y Equivalencias

Aplicamos la distributividad de $\neg$ sobre $\Leftrightarrow$ dos veces. Primero, sustituyendo $q := \neg p$: $\neg(p \Leftrightarrow \neg p) \equiv \neg p \Leftrightarrow \neg p \equiv \top$. Luego $p \Leftrightarrow \neg p \equiv \bot$.

Por otro lado, sustituyendo $q := p$: $\neg(p \Leftrightarrow p) \equiv \neg p \Leftrightarrow p$. Como $p \Leftrightarrow p \equiv \top$, tenemos $\neg \top \equiv \neg p \Leftrightarrow p$, es decir $\neg p \Leftrightarrow p \equiv \bot$.

Ahora: $\neg\neg p \Leftrightarrow p \equiv \neg p \Leftrightarrow \neg p \equiv \top$. Por lo tanto $\neg\neg p \equiv p$.

Usando la distributividad de $\lor$ sobre $\Leftrightarrow$ con $q := p$ y $r := \neg p$:

$p \lor (p \Leftrightarrow \neg p)$

Sabemos que $p \Leftrightarrow \neg p \equiv \bot$ (de la doble negación). Entonces:

$p \lor \bot \equiv p$

Pero también, expandiendo la distributividad:

$(p \lor p) \Leftrightarrow (p \lor \neg p) \equiv p \Leftrightarrow (p \lor \neg p)$

Y por idempotencia, $p \lor p \equiv p$, así que $p \equiv p \Leftrightarrow (p \lor \neg p)$. Por identidad de $\Leftrightarrow$, esto da $p \lor \neg p \equiv \top$.

Para la primera ley, partimos de la regla dorada $p \land q \equiv p \Leftrightarrow q \Leftrightarrow p \lor q$ y negamos ambos lados:

$\neg(p \land q) \equiv \neg(p \Leftrightarrow q \Leftrightarrow p \lor q)$ $\equiv \neg p \Leftrightarrow q \Leftrightarrow p \lor q$

Usando que $\neg p \Leftrightarrow q \equiv \neg p \Leftrightarrow q$ y manipulando con las propiedades de $\Leftrightarrow$, $\lor$ y la regla dorada, se obtiene $\neg p \lor \neg q$.

La segunda ley se demuestra análogamente, o aplicando la primera a $\neg p$ y $\neg q$ y usando doble negación.

Partimos de la regla dorada y las propiedades de la equivalencia. La implicación en el cálculo proposicional se define como:

$p \Rightarrow q \equiv p \lor q \Leftrightarrow q$

De aquí, usando que $p \lor q \Leftrightarrow q$ tiene el mismo valor de verdad que $\neg p \lor q$ (verificable por tabla de verdad), obtenemos el resultado.

$p \Rightarrow q \equiv \neg p \lor q$ $\equiv \neg p \lor \neg\neg q$ $\equiv \neg\neg q \lor \neg p$ $\equiv \neg(\neg q) \lor \neg p$ $\equiv \neg q \Rightarrow \neg p$

Usamos doble negación ($\neg\neg q \equiv q$), conmutatividad de $\lor$ y la definición de implicación.

$p \Rightarrow (q \Rightarrow r) \equiv p \Rightarrow (\neg q \lor r)$ $\equiv \neg p \lor (\neg q \lor r)$ $\equiv (\neg p \lor \neg q) \lor r$ $\equiv \neg(p \land q) \lor r$ $\equiv p \land q \Rightarrow r$

Usamos la definición de implicación, asociatividad de $\lor$ y De Morgan.

Para $p \land q \Rightarrow p$: por definición de implicación, $p \land q \Rightarrow p \equiv \neg(p \land q) \lor p \equiv (\neg p \lor \neg q) \lor p \equiv \top \lor \neg q \equiv \top$.

Para $p \Rightarrow p \lor q$: $p \Rightarrow p \lor q \equiv \neg p \lor (p \lor q) \equiv (\neg p \lor p) \lor q \equiv \top \lor q \equiv \top$.

$p \land (p \Rightarrow q) \equiv p \land (\neg p \lor q)$ $\equiv (p \land \neg p) \lor (p \land q)$ $\equiv \bot \lor (p \land q)$ $\equiv p \land q$

Y como $p \land q \Rightarrow q$ (debilitamiento), tenemos $p \land (p \Rightarrow q) \Rightarrow q$.

Para la primera equivalencia:

$p \lor q \Rightarrow r \equiv \neg(p \lor q) \lor r$ $\equiv (\neg p \land \neg q) \lor r$ $\equiv (\neg p \lor r) \land (\neg q \lor r)$ $\equiv (p \Rightarrow r) \land (q \Rightarrow r)$

Para la segunda: es un caso particular con $q := \neg p$, donde $p \lor \neg p \equiv \top$, así que $\top \Rightarrow r \equiv r$.