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

Διαγράμματα Βενν για τους τύπους Ντε Μόργκαν

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

• Το συμπλήρωμα της ένωσης δύο συνόλων είναι το συμπλήρωμα της τομής τους.
• Το συμπλήρωμα της τομής δύο συνόλων είναι το συμπλήρωμα της ένωσής τους.

και για λογικές προτάσεις ως εξής:

• Η άρνηση της διάζευξης δύο λογικών προτάσεων είναι η σύζευξη των αρνήσεών τους.
• Η άρνηση της σύζευξης δύο λογικών προτάσεων είναι η διάζευξη των αρνήσεων τους.

Πιο αυστηρά, στην θεωρία συνόλων για οποιαδήποτε δύο σύνολα $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$ η διάζευξη δύο προτάσεων.

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

Απόδειξη

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

Λογική

Ξεκινάμε με την σχέση

${\overline {P\wedge Q}}\Leftrightarrow {\overline {P}}\vee {\overline {Q}}$.

Γράφοντας τους πίνακες αληθείας για τους όρους των δύο μελών, επιβεβαιώνουμε ότι τα δύο μέλη είναι ίσα για όλες τις τιμές αληθείας του $P$ και του $Q$:

$P$	$Q$	$P\wedge Q$	${\overline {P\wedge Q}}$	${\overline {P}}$	${\overline {Q}}$	${\overline {P}}\vee {\overline {Q}}$
$0$	$0$	$0$	$1$	$1$	$1$	$1$
$0$	$1$	$0$	$1$	$1$	$0$	$1$
$1$	$0$	$0$	$1$	$0$	$1$	$1$
$1$	$1$	$1$	$0$	$0$	$0$	$0$

Αντίστοιχα, για την σχέση

${\overline {P\vee Q}}\Leftrightarrow {\overline {P}}\wedge {\overline {Q}}$

έχουμε:

$P$	$Q$	$P\vee Q$	${\overline {P\vee Q}}$	${\overline {P}}$	${\overline {Q}}$	${\overline {P}}\wedge {\overline {Q}}$
$0$	$0$	$0$	$1$	$1$	$1$	$1$
$0$	$1$	$0$	$1$	$1$	$0$	$1$
$1$	$0$	$0$	$1$	$0$	$1$	$1$
$1$	$1$	$1$	$0$	$0$	$0$	$0$

Θεωρία συνόλων

Η απόδειξη στην θεωρία συνόλων, μπορεί να προκύψει χρησιμοποιώντας την απόδειξη των τύπων Ντε Μόργκαν στην λογική. Υπενθυμίζουμε ότι εξ ορισμού ισχύουν οι παρακάτω σχέσεις:

• $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{aligned}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{aligned}}$

και

${\begin{aligned}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{aligned}}$.

Γενικευμένη μορφή

Στην θεωρία συνόλων, οι τύποι γενικεύονται για $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, περιγράφει κανόνες μετατροπής που σε γενικές γραμμές προκύπτουν από τους νόμους του Ντε Μόργκαν. Ακόμα και έτσι, στον Ντε Μόργκαν πιστώνεται η διατύπωση των τύπων με σύγχρονους της αυστηρής λογικής, και η ενσωμάτωσή τους στην γλώσσα της λογικής. Οι τύποι του Ντε Μόργκαν μπορούν να αποδειχθούν εύκολα και μπορεί να μοιάζουν τετριμμένοι. Παρ' όλ' αυτά, οι τύποι αυτοί είναι χρήσιμοι σε διάφορες αποδείξεις και επαγωγικά επιχειρήματα. Επίσης βρίσκουν διάφορες εφαρμογές στον σχεδιασμό κυκλωμάτων με λογικές πύλες, καθώς και σε αλγορίθμους προτασιακής λογικής.

Δείτε επίσης

• Θεωρία συνόλων
• Προτασιακός λογισμός