Τύποι Ντε Μόργκαν

Στα θεωρία συνόλων και την μαθηματική λογική, οι **τύποι Ντε Μόργκαν** (ή αλλιώς **νόμοι Ντε Μόργκαν**) αναφέρονται σε δύο μαθηματικούς τύπους, που μπορούν να εκφραστούν σε απλά ελληνικά, για τα σύνολα ως εξής:
* Το συμπλήρωμα της ένωσης δύο συνόλων είναι η τομή των συμπληρωμάτων τους.
* Το συμπλήρωμα της τομής δύο συνόλων είναι η ένωση των συμπληρωμάτων τους.
και για λογικές προτάσεις ως εξής:
* Η άρνηση της διάζευξης δύο λογικών προτάσεων είναι η σύζευξη των αρνήσεών τους.
* Η άρνηση της σύζευξης δύο λογικών προτάσεων είναι η διάζευξη των αρνήσεων τους.

Πιο αυστηρά, στην θεωρία συνόλων για οποιαδήποτε δύο σύνολα A, B έχουμε ότι:
:\overline{A \cap B} = \overline{A} \cup \overline{B}, \quad και \quad \overline{A \cup B} = \overline{A} \cap \overline{B},
όπου \overline{ A } είναι το συμπλήρωμα ενός συνόλου σχετικά με ένα υπερσύνολο \Omega, \cap η τομή και \cup είναι η ένωση δύο συνόλων.

Στην λογική, για οποιεσδήποτε λογικές προτάσεις P και Q, έχουμε τις εξής ισοδυναμίες:
:\neg (P \wedge Q) \Leftrightarrow \neg P \vee \neg Q, \quad  και \quad \neg (P \vee Q) \Leftrightarrow \neg P \wedge \neg Q,
όπου \neg P είναι η άρνηση της P, \wedge η σύζευξη και \vee η διάζευξη δύο προτάσεων.

Οι τύποι παίρνουν το όνομά τους από τον Βρετανό μαθηματικό Αύγουστο Ντε Μόργκαν.

## Απόδειξη
Θα ξεκινήσουμε αποδεικνύοντας τους τύπους στην λογική και μετά θα τους χρησιμοποιήσουμε για να αποδείξουμε τους τύπους στην θεωρία συνόλων.

### Λογική
Ξεκινάμε με την σχέση 
:\neg(P \wedge Q) \Leftrightarrow \neg P \vee \neg Q.
Γράφοντας τους πίνακες αληθείας για τους όρους των δύο μελών, επιβεβαιώνουμε ότι τα δύο μέλη είναι ίσα για όλες τις τιμές αληθείας του P και του Q:
:
Αντίστοιχα, για την σχέση
:\neg (P \vee Q) \Leftrightarrow \neg P \wedge \neg Q
έχουμε:
:

### Θεωρία συνόλων
Η απόδειξη στην θεωρία συνόλων, μπορεί να προκύψει χρησιμοποιώντας την απόδειξη των τύπων Ντε Μόργκαν στην λογική. Υπενθυμίζουμε ότι εξ ορισμού ισχύουν οι παρακάτω σχέσεις:
* x \in \overline{A} \Leftrightarrow \neg(x \in A),
* x \in A \cap B \Leftrightarrow (x \in A \wedge x \in B), 
* x \in A \cup B \Leftrightarrow (x \in A \vee x \in B).

Έπειτα οι δύο τύπου Ντε Μόργκαν προκύπτουν από τις εξής ισοδυναμίες:
:\begin{align}
x \in \overline{A \cap B} 
  & \Leftrightarrow \neg (x \in A \cap B) \\ 
  & \Leftrightarrow \neg (x \in A \wedge x \in B) \\ 
  & \Leftrightarrow (x \not\in A \vee x \not\in B) \\
  & \Leftrightarrow (x \in \overline{A} \vee x \in \overline{B}) \\
  & \Leftrightarrow (x \in \overline{A} \cup \overline{B}),
\end{align}
και 
:\begin{align}
x \in \overline{A \cup B} 
 & \Leftrightarrow \neg (x \in A \cup B) \\
 & \Leftrightarrow \neg (x \in A \vee x \in B) \\
 & \Leftrightarrow (x \not\in A \wedge x \not\in B) \\
 & \Leftrightarrow (x \in \overline{A} \wedge x \in \overline{B}) \\
 & \Leftrightarrow (x \in \overline{A} \cap \overline{B})
\end{align}.

## Γενικευμένη μορφή
Στην θεωρία συνόλων, οι τύποι γενικεύονται για n \geq 2 σύνολα A_1, A_2, \ldots, A_n ως εξής:
:\overline{\bigcap_{i = 1}^n  A_i} = \overline{A_1 \cap A_2 \cap \ldots \cap A_n} = \overline{A_1} \cup \overline{A_2} \cup \ldots \cup \overline{A_n} = \bigcup_{i=1}^n \overline{A_i}, 
καθώς και 
:\overline{\bigcup_{i = 1}^n  A_i} = \overline{A_1 \cup A_2 \cup \ldots \cup A_n} = \overline{A_1} \cap \overline{A_2} \cap \ldots \cap \overline{A_n} = \bigcap_{i=1}^n \overline{A_i}.

Αντίστοιχα, στην λογική, για n \geq 2 προτάσεις P_1, P_2, \ldots, P_n, ισχύει ότι 
:\neg \bigvee_{i = 1}^n P_i = \neg( P_1 \vee P_2 \vee \ldots \vee P_n ) = (\neg P_1) \wedge (\neg P_2) \wedge \ldots \wedge (\neg P_n) = \bigwedge_{i = 1}^n \neg P_i,
και 
:\neg \bigwedge_{i = 1}^n P_i = \neg( P_1 \wedge P_2 \wedge \ldots \wedge P_n ) = (\neg P_1) \vee (\neg P_2) \vee \ldots \vee (\neg P_n) = \bigvee_{i = 1}^n \neg P_i.

## Ιστορία
Οι τύποι έχουν ονομαστεί προς τιμήν του Αυγούστου Ντε Μόργκαν (1806–1871), που εισήγαγε την μαθηματική τους διατύπωση στην προτασιακή λογική. Η διατύπωση του Ντε Μόργκαν ήταν επηρεασμένη από την αλγεβροποίηση της λογικής που ανέλαβε ο Τζορτζ Μπουλ. Παρ' όλ' αυτά , μία παρόμοια παρατήρηση είχε γίνει από τον Αριστοτέλη, και ήταν γνωστή στους αρχαίους Έλληνες λογικολόγους και στους λογικολόγους του μεσαίωνα. Για παράδειγμα, στον 14ο αιώνα, ο Γουλιέλμος του Όκαμ έγραψε τους νόμους στην καθομιλουμένη γλώσσα στο έργο του *Summa Logicae*. Ο Ζαν Μπουριντάν, στο έργο του *Summulae de Dialectica*, περιγράφει κανόνες μετατροπής που σε γενικές γραμμές προκύπτουν από τους νόμους του Ντε Μόργκαν. Ακόμα και έτσι, στον Ντε Μόργκαν πιστώνεται η διατύπωση των τύπων με σύγχρονους της αυστηρής λογικής, και η ενσωμάτωσή τους στην γλώσσα της λογικής. Οι τύποι του Ντε Μόργκαν μπορούν να αποδειχθούν εύκολα και μπορεί να μοιάζουν τετριμμένοι. Παρ' όλ' αυτά, οι τύποι αυτοί είναι χρήσιμοι σε διάφορες αποδείξεις και επαγωγικά επιχειρήματα. Επίσης βρίσκουν διάφορες εφαρμογές στον σχεδιασμό κυκλωμάτων με λογικές πύλες, καθώς και σε αλγορίθμους προτασιακής λογικής. 

## Δείτε επίσης
* Θεωρία συνόλων
* Προτασιακός λογισμός

## Παραπομπές


Κατηγορία:Θεωρία συνόλων
Κατηγορία:Μαθηματική λογική
Κατηγορία:Θεωρία κατηγοριών
Κατηγορία:Άλγεβρα Μπουλ