Leyes de De Morgan

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

Las leyes de De Morgan son una parte de la lógica proposicional y álgebra de Boole, y fueron creadas por Augustus De Morgan (1806-1871).

Las leyes de De Morgan[editar]

Las Leyes de De Morgan sirven para declarar que la suma de n variables proposicionales globalmente negadas (o invertidas) es igual al producto de las n variables negadas individualmente y que inversamente, el producto de n variables proposicionales globalmente negadas es igual a la suma de las n variables negadas individualmente.

\lnot(A \cup B) \Leftrightarrow (\lnot A) \cap (\lnot B)

\lnot(A \cap B) \Leftrightarrow (\lnot A) \cup (\lnot B)

Demostración formal[editar]

\overline{A \cap B}=\overline{A} \cup \overline{B} si y solo si \overline{A \cap B}\subseteq\overline{A} \cup \overline{B} y \overline{A \cap B}\supseteq\overline{A} \cup \overline{B}.

para cualquiera x: x \notin A ó x \notin B

x \in \overline A ó x \in \overline B

x \in \overline A \cup \overline B

Por lo tanto \overline{A \cap B}\subseteq\overline{A} \cup \overline{B}

\supseteq inclusión:

x \in \overline A \cup \overline B

x \in \overline A ó x \in \overline B

Con proposiciones[editar]

La prueba utiliza la asociatividad y la distributividad de las leyes \cap y \cup.

  • Verdad
  • Si verdad por n

\lnot(A_1 \cap A_2 \cap ... \cap A_n \cap A_{n+1})

\Leftrightarrow (\lnot ( (A_1 \cap A_2 \cap ... \cap A_n) \cap A_{n+1})

\Leftrightarrow (\lnot (A_1 \cap A_2 \cap ... \cap A_n)) \cup (\lnot A_{n+1})

\Leftrightarrow (\lnot A_1) \cup (\lnot A_2) \cup ... \cup (\lnot A_n) \cup (\lnot A_{n+1})