Cómo se encuentra esta forma disyuntiva a través del álgebra proposicional

Question

Estoy aprendiendo sobre la forma normal disyuntiva y el álgebra de las proposiciones. El texto es Discrete Mathematics with Graph Theory, 3ª edición de Goodaire y Parmenter (no estaba muy recomendado en Amazon pero es el que ha elegido la BSU).

En los ejemplos está esta implicación, $p \rightarrow (q \wedge r)$ que utilizan para demostrar cómo mostrar en forma normal disyuntiva utilizando tanto tablas de verdad como álgebra. Estoy perdido con el álgebra. Por favor, ayúdame a entender de dónde viene.

$ \begin{align} [p\rightarrow (q\wedge r)] &\Leftrightarrow [(\neg p) \vee (q \wedge r)] \\ &\Leftrightarrow [((\neg p)\wedge q)\vee ((\neg p)\wedge (\neg q)) \vee (q \wedge r)] \\ &\Leftrightarrow [((\neg p)\wedge q \wedge r) \vee ((\neg p)\wedge q \wedge (\neg r)) \vee \\ & \hspace{20pt}((\neg p )\wedge (\neg q) \wedge r) \vee ((\neg p) \wedge (\neg q) \wedge (\neg r)) \vee \\ & \hspace{20pt} (p \wedge q \wedge r) \vee ((\neg p)\wedge q \wedge r)] \\ &\Leftrightarrow [((\neg p)\wedge q \wedge r) \vee ((\neg p)\wedge q \wedge (\neg r)) \vee \\ & \hspace{15pt}((\neg p )\wedge (\neg q) \wedge r) \vee ((\neg p) \wedge (\neg q) \wedge (\neg r)) \vee (p \wedge q \wedge r)] \end{align} $

Estoy bien hasta la primera equivalencia lógica. Sin embargo, en la segunda, estoy perdido. No estoy seguro de cuál de las propiedades que han discutido se utilizó en este álgebra. ¿Se está utilizando una propiedad distributiva?

Answer 1

Lo que se está haciendo, aquí, en la segunda equivalencia es utilizar la equivalencia de $$\lnot p \equiv \lnot p\land T \equiv (\lnot p \land (\underbrace{q\lor \lnot q}_{\large \text{true}})) \underbrace{\equiv}_{\large \text{DL}} (\lnot p \land q) \lor (\lnot p \land \lnot q)$$

Así que $$\color{blue}{\lnot p} \lor \color{red}{(q\land r)} \equiv \color{blue}{(\lnot p \land q) \lor (\lnot p \land \lnot q)}\lor \color{red}{(q\land r)}$$

Así que sí, en cierto sentido, se está utilizando la ley distributiva (DL), así como las tautologías $\lnot p \equiv (\lnot p \land T)$ y $q \lor \lnot q = T$ .

El mismo enfoque se utiliza en la segunda equivalencia, que hace uso de la tautología $r \lor \lnot r$ etc.

Answer 2

Ha utilizado los siguientes "trucos" (compruébalos con tablas de verdad) :

$$p \equiv (p \land T)$$

y

$$T \equiv (q \lor \lnot q)$$

Así, se tiene la siguiente cadena de equivalencias :

$$[(\lnot p) \lor (q \land r)] \equiv [(\lnot p \land T) \lor (q \land r)] \equiv [(\lnot p \land (q \lor \lnot q)) \lor (q \land r)] $$

Ahora, si "distribuyes" $\lnot p$ se obtendrá la segunda equivalencia.