Διαγράμματα Βενν για τους τύπους Ντε Μόργκαν
Στα θεωρία συνόλων και την μαθηματική λογική, οι τύποι Ντε Μόργκαν (ή αλλιώς νόμοι Ντε Μόργκαν) αναφέρονται σε δύο μαθηματικούς τύπους, που μπορούν να εκφραστούν σε απλά ελληνικά, για τα σύνολα ως εξής:[1]:18[2]:11,50[3]:6
- Το συμπλήρωμα της ένωσης δύο συνόλων είναι το συμπλήρωμα της τομής τους.
- Το συμπλήρωμα της τομής δύο συνόλων είναι το συμπλήρωμα της ένωσής τους.
και για λογικές προτάσεις ως εξής:
- Η άρνηση της διάζευξης δύο λογικών προτάσεων είναι η σύζευξη των αρνήσεών τους.
- Η άρνηση της σύζευξης δύο λογικών προτάσεων είναι η διάζευξη των αρνήσεων τους.
Πιο αυστηρά, στην θεωρία συνόλων για οποιαδήποτε δύο σύνολα
έχουμε ότι:
και
,
όπου
είναι το συμπλήρωμα ενός συνόλου σχετικά με ένα υπερσύνολο
,
η τομή και
είναι η ένωση δύο συνόλων.
Στην λογική, για οποιεσδήποτε λογικές προτάσεις
και
, έχουμε τις εξής ισοδυναμίες:
και
,
όπου
είναι η άρνηση της
,
η σύζευξη και
η διάζευξη δύο προτάσεων.
Οι τύποι παίρνουν το όνομά τους από τον Βρετανό μαθηματικό Αύγουστο Ντε Μόργκαν.
Θα ξεκινήσουμε αποδεικνύοντας τους τύπους στην λογική και μετά θα τους χρησιμοποιήσουμε για να αποδείξουμε τους τύπους στην θεωρία συνόλων.
Ξεκινάμε με την σχέση
.
Γράφοντας τους πίνακες αληθείας για τους όρους των δύο μελών, επιβεβαιώνουμε ότι τα δύο μέλη είναι ίσα για όλες τις τιμές αληθείας του
και του
:
![{\displaystyle P}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b4dc73bf40314945ff376bd363916a738548d40a) |
![{\displaystyle Q}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8752c7023b4b3286800fe3238271bbca681219ed) |
![{\displaystyle P\wedge Q}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f06f4755cd6448f81c2bfdd46aea759952cdc89a) |
![{\displaystyle \neg (P\wedge Q)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8bda4b9cac97b8efc1a156e6fcfdaedb0343a55d) |
![{\displaystyle \neg P}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5eb0d6c8752f8c7256d69c62e77dfe4c466dbe58) |
![{\displaystyle \neg Q}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fad34798abb0bbbc063c906e459f103a09b1660e) |
|
![{\displaystyle 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2aae8864a3c1fec9585261791a809ddec1489950) |
![{\displaystyle 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2aae8864a3c1fec9585261791a809ddec1489950) |
![{\displaystyle 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2aae8864a3c1fec9585261791a809ddec1489950) |
![{\displaystyle 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf) |
![{\displaystyle 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf) |
![{\displaystyle 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf) |
|
![{\displaystyle 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2aae8864a3c1fec9585261791a809ddec1489950) |
![{\displaystyle 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf) |
![{\displaystyle 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2aae8864a3c1fec9585261791a809ddec1489950) |
![{\displaystyle 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf) |
![{\displaystyle 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf) |
![{\displaystyle 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2aae8864a3c1fec9585261791a809ddec1489950) |
|
![{\displaystyle 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf) |
![{\displaystyle 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2aae8864a3c1fec9585261791a809ddec1489950) |
![{\displaystyle 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2aae8864a3c1fec9585261791a809ddec1489950) |
![{\displaystyle 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf) |
![{\displaystyle 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2aae8864a3c1fec9585261791a809ddec1489950) |
![{\displaystyle 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf) |
|
![{\displaystyle 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf) |
![{\displaystyle 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf) |
![{\displaystyle 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf) |
![{\displaystyle 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2aae8864a3c1fec9585261791a809ddec1489950) |
![{\displaystyle 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2aae8864a3c1fec9585261791a809ddec1489950) |
![{\displaystyle 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2aae8864a3c1fec9585261791a809ddec1489950) |
|
Αντίστοιχα, για την σχέση
![{\displaystyle \neg (P\vee Q)\Leftrightarrow \neg P\wedge \neg Q}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dca655ba7902cf0f9b8ece10f7b79c2ad678ab9e)
έχουμε:
![{\displaystyle P}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b4dc73bf40314945ff376bd363916a738548d40a) |
![{\displaystyle Q}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8752c7023b4b3286800fe3238271bbca681219ed) |
![{\displaystyle P\vee Q}](https://wikimedia.org/api/rest_v1/media/math/render/svg/57892b87b74754882daffcf850dd8b445b0fc436) |
![{\displaystyle \neg (P\vee Q)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/421a030a6227b367104ed9a26fdf0e1b41eb4654) |
![{\displaystyle \neg P}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5eb0d6c8752f8c7256d69c62e77dfe4c466dbe58) |
![{\displaystyle \neg Q}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fad34798abb0bbbc063c906e459f103a09b1660e) |
|
![{\displaystyle 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2aae8864a3c1fec9585261791a809ddec1489950) |
![{\displaystyle 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2aae8864a3c1fec9585261791a809ddec1489950) |
![{\displaystyle 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2aae8864a3c1fec9585261791a809ddec1489950) |
![{\displaystyle 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf) |
![{\displaystyle 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf) |
![{\displaystyle 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf) |
|
![{\displaystyle 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2aae8864a3c1fec9585261791a809ddec1489950) |
![{\displaystyle 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf) |
![{\displaystyle 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf) |
![{\displaystyle 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2aae8864a3c1fec9585261791a809ddec1489950) |
![{\displaystyle 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf) |
![{\displaystyle 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2aae8864a3c1fec9585261791a809ddec1489950) |
|
![{\displaystyle 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf) |
![{\displaystyle 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2aae8864a3c1fec9585261791a809ddec1489950) |
![{\displaystyle 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf) |
![{\displaystyle 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2aae8864a3c1fec9585261791a809ddec1489950) |
![{\displaystyle 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2aae8864a3c1fec9585261791a809ddec1489950) |
![{\displaystyle 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf) |
|
![{\displaystyle 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf) |
![{\displaystyle 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf) |
![{\displaystyle 1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92d98b82a3778f043108d4e20960a9193df57cbf) |
0 |
![{\displaystyle 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2aae8864a3c1fec9585261791a809ddec1489950) |
![{\displaystyle 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2aae8864a3c1fec9585261791a809ddec1489950) |
|
Η απόδειξη στην θεωρία συνόλων, μπορεί να προκύψει χρησιμοποιώντας την απόδειξη των τύπων Ντε Μόργκαν στην λογική. Υπενθυμίζουμε ότι εξ ορισμού ισχύουν οι παρακάτω σχέσεις:
,
,
.
Έπειτα οι δύο τύπου Ντε Μόργκαν προκύπτουν από τις εξής ισοδυναμίες:
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/775cc7d1e350ce6bc087d0d77ce210b4961f6599)
και
.
Στην θεωρία συνόλων, οι τύποι γενικεύονται για
σύνολα
ως εξής:[4]:22
,
καθώς και
.
Αντίστοιχα, στην λογική, για
προτάσεις
, ισχύει ότι
,
και
.
Οι τύποι έχουν ονομαστεί προς τιμήν του Αυγούστου Ντε Μόργκαν (1806–1871),[5] που εισήγαγε την μαθηματική τους διατύπωση στην προτασιακή λογική. Η διατύπωση του Ντε Μόργκαν ήταν επηρεασμένη από την αλγεβροποίηση της λογικής που ανέλαβε ο Τζορτζ Μπουλ. Παρ' όλ' αυτά , μία παρόμοια παρατήρηση είχε γίνει από τον Αριστοτέλη, και ήταν γνωστή στους αρχαίους Έλληνες λογικολόγους και στους λογικολόγους του μεσαίωνα.[6] Για παράδειγμα, στον 14ο αιώνα, ο Γουλιέλμος του Όκαμ έγραψε τους νόμους στην καθομιλουμένη γλώσσα στο έργο του Summa Logicae.[7] Ο Ζαν Μπουριντάν, στο έργο του Summulae de Dialectica, περιγράφει κανόνες μετατροπής που σε γενικές γραμμές προκύπτουν από τους νόμους του Ντε Μόργκαν.[8] Ακόμα και έτσι, στον Ντε Μόργκαν πιστώνεται η διατύπωση των τύπων με σύγχρονους της αυστηρής λογικής, και η ενσωμάτωσή τους στην γλώσσα της λογικής. Οι τύποι του Ντε Μόργκαν μπορούν να αποδειχθούν εύκολα και μπορεί να μοιάζουν τετριμμένοι.[9] Παρ' όλ' αυτά, οι τύποι αυτοί είναι χρήσιμοι σε διάφορες αποδείξεις και επαγωγικά επιχειρήματα. Επίσης βρίσκουν διάφορες εφαρμογές στον σχεδιασμό κυκλωμάτων με λογικές πύλες, καθώς και σε αλγορίθμους προτασιακής λογικής.
- ↑ Βάρσος, Δ. (2023). Θεμελιώδεις Έννοιες των Μαθηματικών. Κάλλιπος, Ανοικτές Ακαδημαϊκές Εκδόσεις. doi:10.57713/kallipos-206.
- ↑ Δημητρακόπουλος, Κ. Ι. «Σημειώσεις για τα μαθήματα 86Κ026. Στοιχεία λογικής και θεωρίας συνόλων 86Υ12. Λογική και θεωρία συνόλων» (PDF).
- ↑ Κοντογεώργης, Αριστείδης. «Σύνολα και αριθμοί» (PDF). Τμήμα Μαθηματικών, Πανεπιστήμιο Αιγαίου. Ανακτήθηκε στις 11 Μαΐου 2024.
- ↑ Κολουντζάκης, Μ.· Παπαχριστόδουλος, Χ. (2015). Διακριτά μαθηματικά. Κάλλιπος, Ανοικτές Ακαδημαϊκές Εκδόσεις. doi:10.57713/kallipos-517.
- ↑ Victor J. Montemayor. «DeMorgan's Theorems». Middle Tennessee State University. Ανακτήθηκε στις 11 Μαΐου 2024.
- ↑ Bocheński, Józef Maria (1956). A History of Formal Logic.
- ↑ William of Ockham. Summa Logicae. σελίδες part II, sections 32 and 33.
- ↑ Buridan, Jean (2001). Summula de Dialectica. Μτφρ. Gyula Klima. New Haven: Yale University Press. σελίδες Δείτε το Treatise 1, Chapter 7, Section 5. ISBN 0-300-08425-0.
- ↑ Augustus De Morgan (1806–1871) Αρχειοθετήθηκε 2010-07-15 στο Wayback Machine. by Robert H. Orr