Lleis de De Morgan

De Viquipèdia
Dreceres ràpides: navegació, cerca
Representació gràfica de les lleis de De Morgan

Les lleis de De Morgan són una part de la Lògica proposicional i analítica, i va ser creada per Augustus De Morgan (Madurai, 1806 - Londres, 1871).

Les lleis de De Morgan[modifica | modifica el codi]

Les lleis de De Morgan declaren que la suma de n variables globalment negades (o invertides) és igual al producte de les n variables negades individualment, i que inversament, el producte de n variables globalment negades és igual a la suma de les n variables negades individualment.


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

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

Prova[modifica | modifica el codi]

Cal utilitzar les taules de valors de veritat

 \lnot (A \cup B) \leftrightarrow (\lnot A) \cap (\lnot B)
 A  B  A \cup B  \lnot (A \cup B)  \lnot A  \lnot B  (\lnot A) \cap (\lnot B)
V V V F F F F
V F V F F V F
F V V F V F F
F F F V V V V

Demostració formal[modifica | modifica el codi]

 \overline{A \cap B}= \overline{A}\cup \overline{B} si i només si  \overline{A \cap B}\subseteq \overline{A}\cup \overline{B} i  \overline{A \cap B}\supseteq \overline{A}\cup \overline{B}.

per a qualsevol x:

 \subseteq inclusió:

 x \in \overline{A \cap B}

 x \notin{A \cap B}

 x \notin A o  x \notin B

 x \in \overline A o  x \in \overline B

 x \in \overline A \cup \overline B

Per tant  \overline{A \cap B}\subseteq \overline{A}\cup \overline{B}

 \supseteq inclusió:

 x \in \overline A \cup \overline B

 x \in \overline A o  x \in \overline B

 x \notin A o  x \notin B

 x \notin{A \cap B}

 x \in \overline{A \cap B}

Per tant  \overline{A \cap B}\supseteq \overline{A}\cup \overline{B}


 \overline{A \cap B}\subseteq \overline{A}\cup \overline{B} i  \overline{A \cap B}\supseteq \overline{A}\cup \overline{B} per tant  \overline{A \cap B}= \overline{A}\cup \overline{B} Q.E.D.


per  \overline{A \cup B}= \overline{A}\cap \overline{B} es pot utilitzar un mètode similar.

Amb proposicions[modifica | modifica el codi]

La prova utilitza l'associativitat i la distributivitat de les lleis  \cap i  \cup .

  • Veritat
  • Si veritat per 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})