Θεώρημα De Morgan

Ένα σύνολο δύο νόμων που δόθηκαν από έναν Βρετανό μαθηματικό του 19ου αιώνα, τον Augustus De Morgan, αναφέρονται ως θεώρημα του De Morgan. Οι δύο νόμοι χρησιμοποιούν τους κανόνες για τις συναρτήσεις AND, NOT και OR. Χρησιμοποιώντας τις ιδιότητες αυτών των συναρτήσεων, μια Boolean έκφραση μπορεί να μετατραπεί από τη μια μορφή στην άλλη. Το πρώτο θεώρημα δηλώνει ότι η αντιστροφή του γινομένου είναι ίδια με το άθροισμα των αντιστροφών. Το δεύτερο θεώρημα δηλώνει ότι η αντιστροφή του αθροίσματος είναι ίδια με το γινόμενο των αντιστροφών. Το θεώρημα του De Morgan ισχύει για δύο ή περισσότερες μεταβλητές.

Το πρώτο θεώρημα

Σύμφωνα με το πρώτο θεώρημα που έδωσε ο De Morgan, όταν δύο ή περισσότερες μεταβλητές είναι ΚΑΙ και μετά συμπληρώνονται, ισούται με το OR του συμπληρώματος κάθε μεταβλητής ξεχωριστά. Το πρώτο θεώρημα De Morgan μπορεί να γραφτεί ως:

Επαλήθευση του πρώτου θεωρήματος του De Morgan χρησιμοποιώντας έναν πίνακα αλήθειας

Εφαρμογή του πρώτου θεωρήματος

Απόδειξη του πρώτου θεωρήματος

Το δεύτερο θεώρημα

Σύμφωνα με το δεύτερο θεώρημα του De Morgan, όταν δύο ή περισσότερες μεταβλητές είναι OR και μετά συμπληρώνονται, ισούται με το ΚΑΙ του συμπληρώματος κάθε μεταβλητής ξεχωριστά. Το δεύτερο θεώρημα De Morgan μπορεί να γραφτεί ως:

Επαλήθευση του πρώτου θεωρήματος De Morgan με χρήση πίνακα αληθείας

Εφαρμογή του δεύτερου θεωρήματος

Απόδειξη του δεύτερου θεωρήματος

Απλοποίηση χρησιμοποιώντας το θεώρημα του De Morgan

Για να απλοποιήσετε μια έκφραση χρησιμοποιώντας το θεώρημα De Morgan, χρησιμοποιήστε τα ακόλουθα βήματα:

• Αντικαταστήστε το "OR" με το "AND" και το "AND" με το "OR". Με άλλα λόγια, αντικαταστήστε το «+» με το «⋅» και το «⋅» με το «+» που δίνεται στην έκφραση.

• Συμπληρώστε κάθε όρο στην έκφραση

Παράδειγμα 1

Παράδειγμα 2

Ισοδύναμες πύλες χρησιμοποιώντας το θεώρημα του De Morgan

Για να αποκτήσετε ισοδύναμες πύλες χρησιμοποιώντας το θεώρημα του De Morgan, αντικαταστήστε την πύλη ΚΑΙ με την πύλη OR και αντίστροφα. Επίσης, αντιστρέψτε κάθε είσοδο και έξοδο της πύλης. Ας δούμε μερικά παραδείγματα του θεωρήματος του De Morgan.

Παράδειγμα 1

Ας πάρουμε μια βασική πύλη AND ως εξής:

Για να βρείτε μια ισοδύναμη πύλη, αντικαταστήστε την πύλη AND με την πύλη OR και αντιστρέψτε τις δύο εισόδους και μία έξοδο χρησιμοποιώντας μια πύλη NOT ως εξής:

(Οι φυσαλίδες στην είσοδο και στην έξοδο αντιπροσωπεύουν την αντιστροφή.)

Ας επαληθεύσουμε εάν οι παραπάνω εκφράσεις είναι ισοδύναμες χρησιμοποιώντας έναν πίνακα αλήθειας ως εξής:

Παράδειγμα 2

Ας πάρουμε μια βασική πύλη OR ως εξής:

Για να βρείτε μια ισοδύναμη πύλη, αντικαταστήστε την πύλη OR με πύλη AND και αντιστρέψτε τις δύο εισόδους και μία έξοδο χρησιμοποιώντας μια πύλη NOT ως εξής:

(Οι φυσαλίδες στην είσοδο και στην έξοδο αντιπροσωπεύουν την αντιστροφή)

Ας επαληθεύσουμε εάν οι παραπάνω εκφράσεις είναι ισοδύναμες χρησιμοποιώντας έναν πίνακα αλήθειας ως εξής:

Συμπέρασμα