Η μέθοδος απλοποίησης λογικών συναρτήσεων με χρήση χαρτών Karnaugh είναι μια γραφική μέθοδος που βασίζεται σε μια διαφορετική αναπαράσταση των Πινάκων Αληθείας των λογικών συναρτήσεων και χρησιμοποιείται με ευκολία για απλοποίηση λογικών συναρτήσεων δυο, τριών και τεσσάρων μεταβλητών.

Ελαχιστόρος μιας λογικής συνάρτησης Boole n μεταβλητών, ονομάζεται κάθε γινόμενο όλων των μεταβλητών της συνάρτησης, όπου κάθε μεταβλητή που μετέχει εμφανίζεται στην κανονική ή στην συμπληρωματική της μορφή.

Μια συνάρτηση n μεταβλητών έχει 2ⁿ ελαχιστόρους. Στον ακόλουθο πίνακα παρουσιάζονται οι οκτώ ελαχιστόροι μιας συνάρτησης τριών μεταβλητών.

Από τον άνω πίνακα παρατηρούμε ότι κάθε ελαχιστόρος αντιστοιχεί και σε ένα συνδυασμό 0 και 1 των μεταβλητών της συνάρτησης.  Αν η τιμή μιας μεταβλητής της συνάρτησης είναι 1, η αντίστοιχη μεταβλητή στον ελαχιστόρο εμφανίζεται με την κανονική της μορφή και αν η τιμή της μεταβλητής της συνάρτησης είναι 0, η αντίστοιχη μεταβλητή στον ελαχιστόρο εμφανίζεται με την συμπληρωματική της μορφή.

Η τιμή ενός ελαχιστόρου παίρνει το λογικό 1 μόνο για ένα συνδυασμό τιμών που δίνουμε στις μεταβλητές που σχηματίζουν τον ελαχιστόρο και μάλιστα εκείνο τον συνδυασμό 0 και 1 που “αντιστοιχούν” στον ελαχιστόρο. Δηλαδή αν δώσουμε τιμές στις μεταβλητές ενός ελαχιστόρου, αυτές για τις οποίες αντιστοιχίστηκαν για τον ορισμό του, τότε η τιμή του ελαχιστόρου είναι 1, ενώ για τις υπόλοιπες ο ελαχιστόρος παίρνει τιμή 0. Ο ελαχιστόρος δίνει τιμή 0 για τις τιμές που δίνουμε στις μεταβλητές του, για τις οποίες είναι διαφορετικές από εκείνες που προέρχεται ο ελαχιστόρος.

Παράδειγμα: Να εκφραστεί ως άθροισμα ελαχιστόρων, η συνάρτηση Υ τριών μεταβλητών, ο πίνακας της οποίας παρουσιάζεται ακολούθως:

Λύση: Η συνάρτηση Υ παίρνει το λογικό 1 όταν οι μεταβλητές της παίρνουν τιμές για τις οποίες είναι:
(A, B, C) = (0, 0, 1) ο αντίστοιχος ελαχιστόρος είναι A’‧B’‧C
(A, B, C) = (1, 0, 0) ο αντίστοιχος ελαχιστόρος είναι A‧B’‧C’
(A, B, C) = (1, 1, 1) ο αντίστοιχος ελαχιστόρος είναι A‧B‧C

Επομένως η συνάρτηση Y(A, B, C) γράφεται ως άθροισμα ελαχιστόρων ως εξής:
Y(A, B, C) = A’‧B’‧C + A‧B’‧C’ + A‧B‧C

Παράδειγμα: Να εκφραστεί η συνάρτηση τριών μεταβλητών Y(A, B, C) = A‧B + A’‧C ως άθροισμα ελαχιστόρων.

Λύση: Η συνάρτηση δίνεται σε μορφή αθροίσματος γινομένων. Όμως σε κάθε γινόμενο δεν υπάρχουν όλες οι μεταβλητές. Για τις μεταβλητές που λείπουν από κάθε γινόμενο του αθροίσματος, πολλαπλασιάζουμε το γινόμενο αυτό με το άθροισμα της μεταβλητής, που λείπει και του συμπληρώματος της.

Αν για παράδειγμα, λείπει η μεταβλητή A από ένα γινόμενο, τότε πολλαπλασιάζουμε το γινόμενο αυτό με το (A + A’). Έτσι, όλα τα γινόμενα μετατρέπονται σε ελαχιστόρους. Επομένως, η συνάρτηση εκφράζεται ως άθροισμα ελαχιστόρων. Αυτή η διαδικασία εφαρμόζεται παρακάτω:
Y(A, B, C) = A‧B + A’‧C=
= A‧B‧(C+C’) + A’‧(B+B’)‧C =
= A‧B‧C+A‧B‧C’+A’B‧C+A’‧B’‧C

Αναπαράσταση λογικών συναρτήσεων με χάρτες Karnaugh

Οι χάρτες Karnaugh είναι ένας τρόπος αναπαράστασης των λογικών συναρτήσεων. Ο χάρτης Karnaugh αποτελείται από τετράγωνα, το κάθε ένα από τα οποία αντιστοιχεί σε έναν ελαχιστόρο της λογικής συνάρτησης που αναπαριστά.

Η αναπαράσταση μιας λογικής συνάρτησης με χάρτη Karnaugh γίνεται θέτοντας «1» σε κάθε τετράγωνο του χάρτη Karnaugh που αντιστοιχεί σε ελαχιστόρο όπου η συνάρτηση παίρνει την τιμή «1» και στα υπόλοιπα τετράγωνα του χάρτη βάζουμε «0» ή τίποτα στα οποία αντιστοιχούν σε ελαχιστόρο στον οποίο η συνάρτηση δεν παίρνει την τιμή «1».

Τώρα η συνάρτηση μπορεί να γραφεί σαν άθροισμα εκείνων των ελαχιστόρων που στα αντίστοιχα τετράγωνα του χάρτη Karnaugh που έχουμε σημειώσει με «1».

Παράδειγμα: Να αναπαρασταθεί με χάρτη Karnaugh η λογική συνάρτηση δυο μεταβλητών: Υ(Α, Β) = ΑΒ’ + Α’Β

Λύση: Η συνάρτηση γράφεται σε μορφή αθροίσματος ελαχιστόρων, επομένως μπορεί να αναπαρασταθεί με τον χάρτη Karnaugh του σχήματος

Παράδειγμα: Να αναπαρασταθεί με χάρτη Karnaugh η λογική συνάρτηση τριών μεταβλητών: Υ(Α, Β, C) = A’BC’ + A’BC +AB’C’ + AB’C

Λύση: Η συνάρτηση είναι σε μορφή αθροίσματος ελαχιστόρων, επομένως μπορεί να αναπαρασταθεί με τον χάρτη Karnaugh του σχήματος.

Παράδειγμα: Να αναπαρασταθεί με χάρτη Karnaugh η λογική συνάρτηση τριών μεταβλητών: Y(A, B, C) = A’BC+AC

Λύση: Η συνάρτηση γράφεται σε μορφή αθροίσματος ελαχιστόρων:
Υ(Α, Β, C) = A’BC + AC = A’BC + A(B + B’)C = A’BC + ABC + AB’C
Επομένως η συνάρτηση μπορεί να αναπαρασταθεί με το χάρτη Karnaugh του σχήματος.

Παρατηρούμε ότι:
α] ο όρος A’BC της συνάρτησης αντιστοιχεί στο μπλε τετράγωνο του χάρτη Karnaugh του σχήματος και αντιστοιχεί για Α=0, Β=1 και C=1
β] ο όρος AC της συνάρτησης αντιστοιχεί στα δυο κόκκινα τετράγωνα του χάρτη Karnaugh και αντιστοιχεί για Α=1 και C=1

Παράδειγμα: Να αναπαρασταθεί με χάρτη Karnaugh η λογική συνάρτηση τριών μεταβλητών: Y(A, B, C, D) = ABCD + A’BC + C’D’

Λύση: Η συνάρτηση γράφεται σε μορφή αθροίσματος ελαχιστόρων:
Y(A, B, C, D) = ABCD + A’BC + C’D’ = ABCD + A’BC(D+D’) + (A+A’)(B+B’)C’D’=A’B’C’D’+A’BC’D’+A’BCD’+A’BCD+AB’C’D’+ABC’D’+ABCD
Επομένως, η συνάρτηση μπορεί να αναπαρασταθεί με τον χάρτη Karnaugh του σχήματος

Παρατηρούμε ότι:
α] ο όρος ABCD της συνάρτησης αντιστοιχεί στο μπλε τετράγωνο του χάρτη Karnaugh που αντιστοιχεί για Α=1, Β=1, C=1 και D=1
β] ο όρος A’BC της συνάρτησης αντιστοιχεί στα δυο κόκκινα τετράγωνα του χάρτη Karnaugh, που αντιστοιχούν για A=0, B=1 και C=1
γ] ο όρος C’D’ της συνάρτησης αντιστοιχεί στα τέσσερα πράσινα τετράγωνα του χάρτη Karnaugh, που αντιστοιχούν για C=0 και D=0

Παρατηρούμε ότι θα μπορούσαμε να είχαμε αποφύγει τις πράξεις και να τοποθετούσαμε τους «1» της συνάρτησης κατευθείαν στο χάρτη Karnaugh.

Η μέθοδος απλοποίησης λογικών συναρτήσεων με χάρτες Karnaugh

Ο τρόπος για την απλοποίηση μιας λογικής συνάρτησης χρησιμοποιώντας χάρτες Karnaugh  είναι η ακόλουθη:

Γειτονικά τετράγωνα σε ένα χάρτη Karnaugh ονομάζονται τα τετράγωνα που είναι σε συνεχόμενες οριζόντιες ή κάθετες θέσεις, αλλά όχι σε διαγώνιες θέσεις. Έτσι το πλήθος των γειτονικών τετραγώνων πρέπει να είναι δύναμη του 2 δηλαδή 2, 4, 8

Έτσι στο χάρτη Karnaugh του παρακάτω σχήματος των τεσσάρων μεταβλητών, τα 2 τετράγωνα που περιέχουν τους ελαχιστόρους m0 (A’B’C’D’) και m1(A’B’C’D) είναι γειτονικά. Επίσης γειτονικά είναι τα 2 τετράγωνα που περιέχουν τους ελαχιστόρους m11(AB’CD) και m15(ABCD), επίσης γειτονικά είναι τα 4 τετράγωνα που περιέχουν τους ελαχιστόρους m4(A’BC’D’), m5(A’BC’D), m7(A’BCD) και m6(A’BCD’). Δεν είναι γειτονικά τα 2 τετράγωνα που περιέχουν τους ελαχιστόρους m5(A’BC’D) και m15(ABCD).

Ένα χαρακτηριστικό των χαρτών Karnaugh είναι ότι είναι αναδιπλούμενοι. Η αναδίπλωση μπορεί να γίνει γύρω από την περίμετρο του χάρτη Karnaugh.

Έτσι στο χάρτη Karnaugh του παραπάνω σχήματος, τα 2 τετράγωνα που περιέχουν τους ελαχιστόρους m0(A’B’C’D’ ) και m8(AB’ ) είναι γειτονικά. Επίσης, γειτονικά είναι τα 2 τετράγωνα που περιέχουν τους ελαχιστόρους m4(A’BC’D’ ) και m6(A’BCD’ ), τα 4 τετράγωνα που περιέχουν τους ελαχιστόρους m2(A’B’CD’), m3(A’B’CD), m10(AB’CD’) και m11(AB’CD), καθώς και τα 4 τετράγωνα που περιέχουν τους ελαχιστόρους m4(A’BC’D’), m6(A’BCD’), m12(ABC’D’) και m14(ABCD’).

Δυο γειτονικά τετράγωνα σε ένα χάρτη Karnaugh αντιστοιχούν σε ελαχιστόρους που διαφέρουν κατά μια μόνο μεταβλητή (η οποία εμφανίζεται με την πραγματική τιμή της στον ένα ελαχιστόρο και με τη συμπληρωματική τιμή της στον άλλο ελαχιστόρο). Αυτή η μεταβλητή μπορεί να απομακρυνθεί αν και στα δυο γειτονικά τετράγωνα έχει τεθεί «1». Αν λοιπόν ομαδοποιήσουμε 2 γειτονικά τετράγωνα στα οποία έχει τεθεί «1» τότε απομακρύνουμε μια μεταβλητή.

Με την ίδια λογική, αν ομαδοποιήσουμε 4 γειτονικά τετράγωνα στα οποία έχει τεθεί «1», τότε απομακρύνουμε 2 μεταβλητές, αν ομαδοποιήσουμε 8 γειτονικά τετράγωνα στα οποία έχει τεθεί «1», τότε απομακρύνουμε 3 μεταβλητές.

Αν λοιπόν ομαδοποιήσουμε γειτονικά τετράγωνα στα οποία έχει τεθεί «1», επιτρέποντας να συμπεριληφθεί ένα τετράγωνο σε πολλές ομάδες γειτονικών τετραγώνων, τότε απομακρύνουμε μεταβλητές. Επομένως, επιτυγχάνεται απλοποίηση της λογικής συνάρτησης που αναπαρίσταται με το χάρτη Karnaugh.

Η μέθοδος απλοποίησης λογικών συναρτήσεων με χάρτες Karnaugh αποτελείται από τα ακόλουθα βήματα:
α] Γράφουμε τη συνάρτηση με μορφή αθροίσματος γινομένων και τοποθετούμε τους «1» της συνάρτησης στο χάρτη Karnaugh.
β] Δημιουργούμε ομάδες με «1» των 2, 4, 8 μελών από γειτονικά τετράγωνα (οριζόντια, κάθετα και αναδιπλούμενα αλλά όχι διαγώνια). Προσπαθούμε να δημιουργούμε όσο το δυνατόν μεγαλύτερες ομάδες. Κάθε «1» μπορεί να συμμετάσχει σε περισσότερες από μια ομάδες. Όταν όλοι οι «1», που μπορούν να ομαδοποιηθούν, έχουν συμπεριληφθεί σε κάποια ομάδα, τότε δεν δημιουργούμε νέες ομάδες.
γ] Ξαναγράφουμε τη συνάρτηση με όρους που αντιστοιχούν στις ομάδες (παραλείποντας τις μεταβλητές που μέσα στην ομάδα αλλάζουν τιμή) και τους όρους που δεν έχουν ομαδοποιηθεί.

Παράδειγμα: Να απλοποιηθεί η λογική συνάρτηση δυο μεταβλητών: Y(A,B)=AB’+AB

Λύση: Η συνάρτηση είναι σε μορφή αθροίσματος ελαχιστόρων. Τοποθετούμε τους «1» της συνάρτησης στον χάρτη Karnaugh όπως φαίνεται στο σχήμα:

Οι ελαχιστόροι ΑΒ’ και ΑΒ δικαιολογούν την απομάκρυνση της μεταβλητής Β. Πράγματι, οι δυο «1» της συνάρτησης ομαδοποιούνται σε μια δυάδα: τα δυο γειτονικά τετράγωνα του χάρτη Karnaugh που βρίσκονται μέσα σε κόκκινο περίγραμμα, αντιστοιχούν στον όρο Α. Η ομαδοποίηση των δυο τετραγώνων έχει ως αποτέλεσμα την απομάκρυνση μιας μεταβλητής (της μεταβλητής Β) και την απλοποίηση της συνάρτησης ως εξής: Υ=Α.

Παράδειγμα: Να απλοποιηθεί η λογική συνάρτηση τριών μεταβλητών:
Y(A, B, C)=A’BC’+A’BC+AB’C’+AB’C

Λύση: Τοποθετούμε τους «1» της συνάρτησης στο χάρτη Karnaugh, όπως φαίνεται στο σχήμα.

Οι «1» της συνάρτησης ομαδοποιούνται σε δυο δυάδες:
– τα δυο γειτονικά τετράγωνα του χάρτη Karnaugh, που βρίσκονται μέσα σε κόκκινο περίγραμμα, αντιστοιχούν στον όρο ΑΒ’
– τα δυο γειτονικά τετράγωνα του χάρτη Karnaugh, που βρίσκονται μέσα σε μπλε περίγραμμα, αντιστοιχούν στον όρο Α’Β
Η ομαδοποίηση έχει ως αποτέλεσμα την απλοποίηση της συνάρτησης ως εξής: Y=AB’+A’B

Παράδειγμα: Να απλοποιηθεί η λογική συνάρτηση τριών μεταβλητών:
Y(A, B, C)=A’BC+AB’C’+ABC’+ABC

Λύση: Η συνάρτηση μπορεί να απλοποιηθεί χρησιμοποιώντας το χάρτη Karnaugh του σχήματος

Οι «1» της συνάρτησης ομαδοποιούνται ως εξής:
– τα δυο γειτονικά τετράγωνα του χάρτη Karnaugh, που βρίσκονται μέσα σε κόκκινο περίγραμμα, αντιστοιχούν στον όρο: BC
– τα δυο γειτονικά τετράγωνα του χάρτη Karnaugh,που βρίσκονται μέσα σε μπλε περίγραμμα (αναδίπλωση) αντιστοιχούν στον όρο AC’
Επειδή όλοι οι «1», που μπορούν να ομαδοποιηθούν, έχουν συμπεριληφθεί σε κάποια ομάδα, δεν δημιουργούμε νέες ομάδες (οι «1» της συνάρτησης στα δυο γειτονικά τετράγωνα του χάρτη Karnaugh, που αντιστοιχούν στους όρους ABC και ABC’ δεν ομαδοποιούνται)

Η ομαδοποίηση έχει ως αποτέλεσμα την απλοποίηση της συνάρτησης ως εξής: Y=AC’+BC

Παράδειγμα: Να απλοποιηθεί η λογική συνάρτηση τριών μεταβλητών:
Y(A, B, C)=AB’C+BC’+B’C’

Λύση: Η συνάρτηση γράφεται σε μορφή αθροίσματος ελαχιστόρων ως εξής:
Y(A, B, C)=AB’C+BC’+B’C’ = A’B’C’+A’BC’+AB’C’+AB’C+ABC’
Η συνάρτηση μπορεί να απλοποιηθεί χρησιμοποιώντας το χάρτη Karnaugh του σχήματος:

Οι «1» της συνάρτησης ομαδοποιούνται ως εξής:
– τα δυο γειτονικά τετράγωνα του χάρτη Karnaugh που βρίσκονται μέσα στο κόκκινο περίγραμμα, αντιστοιχούν στον όρο AB’
– τα τέσσερα γειτονικά τετράγωνα του χάρτη Karnaugh που βρίσκονται μέσα σε μπλε περίγραμμα (αναδίπλωση) αντιστοιχούν στον όρο C’
Η ομαδοποίηση έχει ως αποτέλεσμα την απλοποίηση της συνάρτησης ως εξής:
Y = AB’ + C’

Παράδειγμα: Να απλοποιηθεί η λογική συνάρτηση τριών μεταβλητών:
Y(A, B, C)=A’C+A’B+AB’C+BC

Λύση: Η συνάρτηση μπορεί να απλοποιηθεί χρησιμοποιώντας το χάρτη Karnaugh του σχήματος:

Οι «1» της συνάρτησης ομαδοποιούνται ως εξής:
– τα δυο γειτονικά τετράγωνα του χάρτη Karnaugh, που βρίσκονται μέσα σε κόκκινο περίγραμμα αντιστοιχούν στον όρο A’B
– τα τέσσερα γειτονικά τετράγωνα του χάρτη Karnaugh, που βρίσκονται μέσα σε μπλε περίγραμμα, αντιστοιχούν στον όρο C
Η ομαδοποίηση έχει ως αποτέλεσμα την απλοποίηση της συνάρτησης ως εξής:
Υ=A’B+C

Παράδειγμα: Να απλοποιηθεί η λογική συνάρτηση τεσσάρων μεταβλητών:
Y(A, B, C, D) = A’B’C’D’ + A’B’C’D + A’B’C’D + A’B’CD’ + A’BC’D’ + A’BC’D + A’BCD’ + AB’C’D’ + AB’C’D + ABC’D’ + ABC’D + ABCD’

Λύση: Η συνάρτηση μπορεί να απλοποιηθεί χρησιμοποιώντας το χάρτη Karnaugh του σχήματος:

Οι «1» της συνάρτησης ομαδοποιούνται ως εξής:
– τα τέσσερα γειτονικά τετράγωνα του χάρτη Karnaugh, που βρίσκονται μέσα σε κόκκινο περίγραμμα (αναδίπλωση) αντιστοιχούν στον όρο A’D’
– τα τέσσερα γειτονικά τετράγωνα του χάρτη Karnaugh, που βρίσκονται μέσα σε πράσινο περίγραμμα (αναδίπλωση) αντιστοιχούν στον όρο ΒD’
– τα οκτώ γειτονικά τετράγωνα του χάρτη Karnaugh, που βρίσκονται μέσα σε μπλε περίγραμμα αντιστοιχούν στον όρο C’
Η ομαδοποίηση έχει ως αποτέλεσμα την απλοποίηση της συνάρτησης ως εξής: Y=A’D’+BD’+C’