Λογικές συναρτήσεις
Πρότυπο:Πηγές Λογικές συναρτήσεις ονομάζουμε εκείνες για τις οποίες μπορούμε να αποφασίσουμε αν είναι αληθείς ή όχι. Χειριζόμαστε τις λογικές προτάσεις στην συγγραφή λογισμικού και στην προτασιακή λογική. Οι μεταβλητές που εκπροσωπούν λογικές προτάσεις ονομάζονται λογικές μεταβλητές. Οι συναρτήσεις που περιέχουν λογικές μεταβλητές λέγονται λογικές συναρτήσεις ή συναρτήσεις αληθείας.
Λογικές συναρτήσεις μιας μεταβλητής
Έστω ότι έχουμε δίτιμες μεταβλητές, που έχουν δηλαδή πεδίο τιμών δισύνολο, (για παράδειγμα {T, F} ή {True, False} ή {Αληθής, Ψευδής} ή {High, Low}). Αντιστοιχούμε αμφιμονοσήμαντα το δισύνολο αυτό και το σύνολο {1, 0}. Μπορούμε να κάνουμε την αντιστοίχηση Αληθής = 1, Ψευδής = 0, (αυτό λέγεται θετική λογική). Μπορούμε να κάνουμε την αντιστοίχηση Αληθής = 0, Ψευδής = 1, (αυτό λέγεται αρνητική λογική). Έχουμε τέσσερις διαφορετικές λογικές συναρτήσεις μιας λογικής μεταβλητής:
| f0 = 0 | f1 = α | f2 = α’ | f3 = 1 |
Η μεταβλητή α και οι συναρτήσεις f0, f1, f2, f3 παίρνουν τιμές στο δισύνολο {0, 1} ή στο {Ψευδής, Αληθής}. Ο πίνακας τιμών και ο αληθοπίνακας για την μεταβλητή και τις συναρτήσεις της είναι οι παρακάτω:
Πίνακας τιμών των συναρτήσεων μιας μεταβλητής
| α | f1 | f2 | f3 | f4 |
|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 |
Αληθοπίνακας των συναρτήσεων μιας μεταβλητής
| α | f1 | f2 | f3 | f4 |
|---|---|---|---|---|
| Ψευδής | Ψευδής | Ψευδής | Αληθής | Αληθής |
| Αληθής | Ψευδής | Αληθής | Ψευδής | Αληθής |
Λογικές συναρτήσεις δυο μεταβλητών
Γενικά υπάρχουν Q διαφορετικές s-τιμες συναρτήσεις, με t μεταβλητές r-τιμών, και Q = s^(r^t). (Το σύμβολο ^ συμβολίζει την ύψωση σε δύναμη). Εδώ έχουμε δίτιμες συναρτήσεις, (s = 2), με δύο μεταβλητές, (t = 2), δίτιμες (r = 2), άρα Q = 2^(2^2) = 16. Επομένως υπάρχουν δεκαέξι λογικές συναρτήσεις δυο (λογικών) μεταβλητών. Παρακάτω φαίνεται ο πίνακας τιμών όλων αυτών των συναρτήσεων:
| f0 | f1 | f2 | f3 | f4 | f5 | f6 | f7 | f8 | f9 | f10 | f11 | f12 | f13 | f14 | f15 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
Ο αριθμητικός δείκτης κάθε συνάρτησης είναι το δεκαδικό ισοδύναμο του δυαδικού περιεχόμενου του πίνακα. Δηλαδή, στην f3 αντιστοιχεί το 0011, που στο δυαδικό σύστημα είναι ο αριθμός 3.
Επιλέγουμε f3 = α και f5 = β, όπου α και β είναι δυο δυαδικές μεταβλητές. (Η επιλογή είναι αυθαίρετη. Φροντίσαμε μόνο, αν βάλουμε δίπλα – δίπλα τα αντίστοιχα περιεχόμενα του πίνακα, να έχουμε όλους τους δυνατούς συνδυασμούς τιμών για τις α και β : α = 0 και β = 0, α = 0 και β = 1, α = 1 και β = 0, α = 1 και β = 1). Μετά από την επιλογή αυτή κάθε συνάρτηση μπορεί να περιγραφεί από συνδυασμούς πρόσθεσης, πολλαπλασιασμού και συμπληρωμάτων των α, β, 0 και 1, όπως ορίζονται αυτά στην Άλγεβρα Μπουλ.
Κάθε λογική συνάρτηση έχει το δικό της όνομα, που αναφέρουμε στον επόμενο πίνακα. Οι συναρτήσεις χρησιμεύουν ως συνδετικά ανάμεσα από απλές λογικές μεταβλητές για να σχηματίζονται απλές λογικές προτάσεις, και στην συνέχεια, ανάμεσα από τις απλές λογικές προτάσεις, για να σχηματίζονται σύνθετες λογικές προτάσεις.
Πίνακας τύπων των 16 λογικών συναρτήσεων δύο μεταβλητών α και β
| f0 | 0 = αα’ | μηδενική | 0 |
| f1 | αβ | ΚΑΙ | α AND β |
| f2 | αβ’ | ΚΑΙ-ΟΧΙ, α δεν συνεπάγεται β | α AND (NOT β) |
| f3 | α | Μεταβλητή α | α |
| f4 | α’β | β δεν συνεπάγεται α | β AND (NOT α) |
| f5 | β | Μεταβλητή β | β |
| f6 | αβ = α’β + αβ’ | Αποκλειστικό Ή | α XOR β |
| f7 | α + β | Ή | α OR β |
| f8 | (α + β)’ = α’β’ = αβ | ΟΧΙ-Ή | α NOR β |
| f9 | α’β’ + αβ = ( α≈β ) | Ισοδυναμία | |
| f10 | β’ | ΟΧΙ-Β, Συμπλήρωμα του β | NOT β |
| f11 | α + β’ = ( βα ) | β συνεπάγεται α | |
| f12 | α’ | ΟΧΙ-Α, Συμπλήρωμα του α | NOT α |
| f13 | α’ + β = ( αβ ) | α συνεπάγεται β | |
| f14 | (αβ)’ = α’ + β’ = αβ | ΟΧΙ-ΚΑΙ | α NAND β |
| f15 | 1 = α + α’ | Μοναδιαία | 1 |
Είδαμε στον πίνακα τύπων των λογικών συναρτήσεων δυο μεταβλητών ότι με συνδυασμούς των πράξεων πολλαπλασιασμού (συνάρτηση AND), πρόσθεσης (συνάρτηση OR) και συμπλήρωσης (συνάρτηση NOT) μπορέσαμε να σχηματίσουμε οποιαδήποτε συνάρτηση από τις 16. Δηλαδή συνδυασμοί των τριών αυτών συναρτήσεων αντικαθιστούν κάθε άλλη. Υπάρχουν κάποιες λογικές συναρτήσεις που μπορούν να αντικαταστήσουν όλες τις άλλες. Κάθε λογική συνάρτηση που μπορεί να αντικαταστήσει όλες τις άλλες ονομάζεται γενική (universal) συνάρτηση, (για παράδειγμα η NAND, η NOR, η Συνεπάγεται). Ισχύει ότι η συνάρτηση με δείκτη x είναι το συμπλήρωμα της συνάρτησης με δείκτη (15 - x), για x = 0, 1, …, 15.
Τα ηλεκτρονικά κυκλώματα που λειτουργούν όπως οι λογικές συναρτήσεις τα ονομάζουμε λογικές πύλες. Οι γενικές πύλες, που αντικαθιστούν όλες τις πύλες, έχουν χρησιμέψει στην βιομηχανική παραγωγή ολοκληρωμένων κυκλωμάτων, επειδή διευκολύνεται η διαδικασία κατασκευής από την χρησιμοποίηση ενός μόνο είδους πύλης.
Γενικές πύλες NAND και NOR
Κάθε κύκλωμα λογικών πυλών μπορεί να κατασκευαστεί μόνο με πύλες NAND ή NOR. Για το λόγο αυτό οι πύλες αυτές καλούνται γενικές ή καθολικές (universal).
Παρακάτω δείχνουμε πώς η NAND και η NOR μπορούν να αντικαταστήσουν τις τρεις βασικές πύλες AND, OR και NOT.
| α β = α NAND β = NOT (α AND β) |
|---|
| NOT α = NOT (α AND 1) = α 1 |
| NOT α = NOT (α AND α) = α α |
| α OR β = NOT (NOT (α OR β)) = NOT ((NOT α) AND (NOT β)) = (NOT α) (NOT β) = (α 1) (β 1) = (α 1) (β β) = (α α) (β 1) = (α α) (β β) |
| α AND β = NOT (NOT (α AND β)) = NOT (α β) = (α β) 1 = (α β) ( α β) |
| α β = α NOR β = NOT (α OR β) |
|---|
| NOT α = NOT (α OR 0) = α 0 |
| NOT α = NOT (α OR α) = α α |
| α OR β = NOT (NOT (α OR β)) = NOT (α β) = (α β) 0 = (α β) (α β) |
| α AND β = NOT (NOT (α AND β)) = NOT((NOT α) OR (NOT β)) = (NOT α) (NOT β) = (α 0) (β 0) = (α 0) (β β) = (α α) (β 0) = (α α) (β β) |
Ελάχιστοι όροι συναρτήσεων t μεταβλητών
Θεωρούμε ότι έχουμε μεταβλητές και συναρτήσεις δίτιμες. Σύμφωνα με τα προηγούμενα έχουμε Q = 2^(2^t) διαφορετικές συναρτήσεις t μεταβλητών, και δυο από αυτές τις συναρτήσεις είναι η μηδενική και η μοναδιαία συνάρτηση.
Ελάχιστος όρος (minterm) λέγεται ένα γινόμενο με t παράγοντες, τις t διαφορετικές μεταβλητές (ή αυτές ή τα συμπληρώματά τους). Μια λογική συνάρτηση μπορεί πάντα να εκφραστεί ως άθροισμα ελάχιστων όρων (άθροισμα γινομένων).
Για δυο μεταβλητές, α και β, οι ελάχιστοι όροι είναι m0 = α’β’, m1 = α’β, m2 = αβ’, m3 = αβ. Στον παρακάτω πίνακα δίνονται οι τιμές των μεταβλητών α και β, η θέση των ελάχιστων όρων (εκεί που αληθεύουν), και ακόμη δίνονται οι τιμές δυο (αυθαίρετων) συναρτήσεων, των F(α, β) και G(α, β).
| α | β | ελάχιστοι | F(α, β) | G(α, β) |
|---|---|---|---|---|
| 0 | 0 | m0 | 1 | 1 |
| 0 | 1 | m1 | 0 | 1 |
| 1 | 0 | m2 | 1 | 1 |
| 1 | 1 | m3 | 0 | 0 |
Παρατηρώντας τις περιπτώσεις όπου οι αυθαίρετες συναρτήσεις F και G έχουν τιμή μονάδα, γράφουμε τους τύπους τους έτσι : F = m0 + m2 = α’β’ + αβ’ και G = m0 + m1 + m2 = α’β’ + α’β + αβ’.
Παρατηρώντας τις περιπτώσεις όπου οι αυθαίρετες συναρτήσεις F και G έχουν τιμή μηδέν, γράφουμε τους τύπους τους έτσι : F = NOT( m1 + m3 ) = ( α’β + αβ )’ και G = NOT( m3 ) = ( αβ )’.
Ελαχιστοποίηση λογικής συνάρτησης
Η ελαχιστοποίηση μπορεί να γίνει είτε με έναν ειδικό πίνακα (Karnaugh, Marquand ή Veitch) είτε με κάποια συστηματική μέθοδο (Quine – McCluskey). Οι μέθοδοι με τους πίνακες είναι ισοδύναμες.
Θα περιγράψουμε την διαδικασία ελαχιστοποίησης με χρήση πινάκων Βάιτς (Veitch) :
- Έχουμε ένα ορθογώνιο παραλληλόγραμμο και δίνουμε αυθαίρετα στο περιεχόμενό του την τιμή 1.
- Το χωρίζουμε στη μέση για την πρώτη μεταβλητή. Το ένα μισό έχει την μεταβλητή κανονική και το άλλο μισό έχει το συμπλήρωμά της.
- Το χωρίζουμε στη μέση για την δεύτερη μεταβλητή. Το ένα μισό έχει την μεταβλητή κανονική και το άλλο μισό έχει το συμπλήρωμά της.
- Το χωρίζουμε τελικά σε 2^t ίσα διαμερίσματα, (όσοι και οι ελάχιστοι όροι με τις t μεταβλητές) και μέσα στο κάθε διαμέρισμα παίρνει τιμή μόνο ένας από τους ελάχιστους όρους.
- Σημειώνουμε με 1 τις θέσεις των ελάχιστων όρων στους οποίους αναλύεται η συνάρτηση. (Οι άλλες θέσεις έχουν συνήθως τιμή 0. Σε κάποιες συναρτήσεις μπορεί να υπάρχουν αδιάφορες συνθήκες (do not care, DC) και τις σημειώνουμε στον πίνακα με Χ. Οι αδιάφορες συνθήκες συχνά διευκολύνουν την ελαχιστοποίηση).
- Υποβιβάζουμε την τάξη των όρων όσο είναι δυνατό. Συνδυασμός δυο γειτονικών διαμερισμάτων μπορεί να δώσει όρο (t -1) τάξης. Συνδυασμός τεσσάρων γειτονικών διαμερισμάτων μπορεί να δώσει όρο (t – 2) τάξης, κ.ο.κ. Σημειώνουμε εδώ ότι «γειτονικά» διαμερίσματα θεωρούνται εκείνα της πρώτης και της τελευταίας σειράς, όπως και εκείνα της πρώτης και της τελευταίας στήλης. (Τα γειτονικά διαμερίσματα διαφέρουν κατά μια μεταβλητή μόνο, το ένα την έχει κανονική και το άλλο έχει το συμπλήρωμά της).
- Στην έκφραση της συνάρτησης αντικαθιστούμε τις ομάδες των όρων με τα ισοδύναμά τους μικρότερης τάξης.
- Επιτρέπεται η πολλαπλή χρησιμοποίηση κάποιου όρου.
Με την διαδικασία αυτή ελαχιστοποιούμε την λογική συνάρτηση. Όταν την μετατρέψουμε σε κύκλωμα, αυτό θα είναι πιο απλό, πιο οικονομικό, πιο γρήγορο.
Θετική / αρνητική λογική και λογικές συναρτήσεις
Έχουμε ένα κύκλωμα με δυο εισόδους Α, Β και μια έξοδο Γ. Καθένας από τους ακροδέκτες Α, Β, Γ μπορεί να βρίσκεται σε μια από δυο καταστάσεις : High ή Low, (υψηλή τάση ή χαμηλή τάση, Η ή L). Οι τιμές που μπορούν να έχουν οι ακροδέκτες δίνονται από τον παρακάτω πίνακα:
| Α | Β | Γ |
|---|---|---|
| L | L | H |
| L | Η | H |
| Η | L | H |
| Η | Η | L |
Η λογική συνάρτηση που πραγματοποιείται με το κύκλωμα αυτό εξαρτάται από τον ορισμό που θα δώσουμε στις καταστάσεις Η και L.
- Αν θεωρήσουμε θετική λογική (Η = 1, L = 0) το κύκλωμα εκτελεί την συνάρτηση NAND.
- Αν θεωρήσουμε αρνητική λογική (Η = 0, L = 1) το κύκλωμα εκτελεί την συνάρτηση NOR.
Παρατηρούμε ότι με την αλλαγή της λογικής το ίδιο κύκλωμα εκτελεί άλλη συνάρτηση.
Γενικότερα, με την αλλαγή της λογικής,
- οι συναρτήσεις f3, f5, f10, f12 μένουν αναλλοίωτες
- στα ζεύγη συναρτήσεων f0-f15, f1-f7, f2-f11, f4-f13, f6-f9, f8-f14, η μια συνάρτηση του ζεύγους μετασχηματίζεται στην άλλη.
| <imagemap>
Image:Logical connectives table.svg|380px rect 399 2 542 39 input A rect 400 39 540 73 input B rect 400 128 542 706 output f(A,B) rect 3 128 398 163 X and ¬X rect 3 162 398 199 A and B rect 3 198 398 235 ¬A and B rect 4 234 399 273 B rect 3 273 398 309 A and ¬B rect 2 308 397 344 A rect 2 344 396 379 A xor B rect 2 379 397 415 A or B rect 3 419 396 454 ¬A and ¬B rect 3 453 395 489 A xnor B rect 3 489 396 525 ¬A rect 3 525 396 560 ¬A or B rect 3 563 397 601 ¬B rect 2 600 395 636 A or ¬B rect 2 634 398 671 ¬A or ¬B rect 3 670 397 706 X or ¬X desc none </imagemap> |
<imagemap>
Image:Logical connectives Hasse diagram.svg|350px rect 326 28 416 200 X or ¬X rect 81 233 166 409 ¬A or ¬B rect 260 231 349 409 A or ¬B rect 393 230 481 409 ¬A or B rect 574 232 663 408 A or B rect 13 436 103 617 ¬B rect 147 438 235 617 ¬A rect 279 440 368 616 A xor B rect 375 440 464 617 A xnor B rect 507 439 595 617 A rect 639 438 732 617 B rect 79 647 168 826 ¬A and ¬B rect 260 647 349 826 A and ¬B rect 392 646 482 826 ¬A and B rect 574 646 663 826 A and B rect 327 853 417 1035 X and ¬X desc none </imagemap> | |
| (file) | (file) (zoom in) |
