Λογικές συναρτήσεις

Λογικές συναρτήσεις ονομάζουμε εκείνες για τις οποίες μπορούμε να αποφασίσουμε αν είναι αληθείς ή όχι. Χειριζόμαστε τις λογικές προτάσεις στην συγγραφή λογισμικού και στην προτασιακή λογική.
Οι μεταβλητές που εκπροσωπούν λογικές προτάσεις ονομάζονται λογικές μεταβλητές. 
Οι συναρτήσεις που περιέχουν λογικές μεταβλητές λέγονται λογικές συναρτήσεις ή συναρτήσεις αληθείας.

 Λογικές συναρτήσεις μιας μεταβλητής 

Έστω ότι έχουμε δίτιμες μεταβλητές, που έχουν δηλαδή πεδίο τιμών δισύνολο, (για παράδειγμα {T, F} ή {True, False} ή {Αληθής, Ψευδής} ή {High, Low}). Αντιστοιχούμε αμφιμονοσήμαντα το δισύνολο αυτό και το σύνολο {1, 0}. Μπορούμε να κάνουμε την αντιστοίχηση Αληθής = 1, Ψευδής = 0, (αυτό λέγεται θετική λογική). Μπορούμε να κάνουμε την αντιστοίχηση Αληθής = 0, Ψευδής = 1, (αυτό λέγεται αρνητική λογική). 
Έχουμε τέσσερις διαφορετικές λογικές συναρτήσεις μιας λογικής μεταβλητής:

f0 = 0f1 = αf2 = α’f3 = 1

Η μεταβλητή α και οι συναρτήσεις f0, f1, f2, f3 παίρνουν τιμές στο δισύνολο {0, 1} ή στο {Ψευδής, Αληθής}. Ο πίνακας τιμών και ο αληθοπίνακας για την μεταβλητή και τις συναρτήσεις της είναι οι παρακάτω:

Πίνακας τιμών των συναρτήσεων μιας μεταβλητής

+ α f1 f2 f3 f40001110101

Αληθοπίνακας των συναρτήσεων μιας μεταβλητής

+ α f1 f2 f3 f4ΨευδήςΨευδήςΨευδήςΑληθήςΑληθήςΑληθήςΨευδήςΑληθήςΨευδήςΑληθής

 Λογικές συναρτήσεις δυο μεταβλητών 

Γενικά υπάρχουν Q διαφορετικές s-τιμες συναρτήσεις, με t μεταβλητές r-τιμών, και Q = s^(r^t).
(Το σύμβολο ^ συμβολίζει την ύψωση σε δύναμη).
Εδώ έχουμε δίτιμες συναρτήσεις, (s = 2), με δύο μεταβλητές, (t = 2), δίτιμες (r = 2), άρα Q = 2^(2^2) = 16. Επομένως υπάρχουν δεκαέξι λογικές συναρτήσεις δυο (λογικών) μεταβλητών. Παρακάτω φαίνεται ο πίνακας τιμών όλων αυτών των συναρτήσεων:

+f0f1f2f3f4f5f6f7f8f9f10f11f12f13f14f150000000011111111000011110000111100110011001100110101010101010101

Ο αριθμητικός δείκτης κάθε συνάρτησης είναι το δεκαδικό ισοδύναμο του δυαδικού περιεχόμενου του πίνακα. Δηλαδή, στην f3 αντιστοιχεί το 0011, που στο δυαδικό σύστημα είναι ο αριθμός 3.

Επιλέγουμε f3 = α και f5 = β, όπου α και β είναι δυο δυαδικές μεταβλητές. (Η επιλογή είναι αυθαίρετη. Φροντίσαμε μόνο, αν βάλουμε δίπλα – δίπλα τα αντίστοιχα περιεχόμενα του πίνακα, να έχουμε όλους τους δυνατούς συνδυασμούς τιμών για τις α και β : α = 0 και β = 0, α = 0 και β = 1, α = 1 και β = 0, α = 1 και β = 1). Μετά από την επιλογή αυτή κάθε συνάρτηση μπορεί να περιγραφεί από συνδυασμούς πρόσθεσης, πολλαπλασιασμού και συμπληρωμάτων των α, β, 0 και 1, όπως ορίζονται αυτά στην Άλγεβρα Μπουλ.

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

Πίνακας τύπων των 16 λογικών συναρτήσεων δύο μεταβλητών α και β

+f00 = αα’μηδενική0f1αβΚΑΙα AND βf2αβ’ΚΑΙ-ΟΧΙ, α δεν συνεπάγεται βα AND (NOT β)f3αΜεταβλητή ααf4α’ββ δεν συνεπάγεται αβ AND (NOT α)f5βΜεταβλητή ββf6αβ = α’β + αβ’ Αποκλειστικό Ήα XOR βf7α + βΉα OR βf8(α + β)’ = α’β’ = αβΟΧΙ-Ήα NOR βf9α’β’ + αβ = ( α≈β )Ισοδυναμίαf10β’ΟΧΙ-Β, Συμπλήρωμα του βNOT βf11α + β’ = ( βα )β συνεπάγεται αf12α’ΟΧΙ-Α, Συμπλήρωμα του αNOT αf13α’ + β = ( αβ )α συνεπάγεται βf14(αβ)’ = α’ + β’ = αβΟΧΙ-ΚΑΙα NAND βf151 = α + α’Μοναδιαία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) = α  1NOT α =  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) = α  0NOT α = 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(α, β)00m01101m10110m21111m300

Παρατηρώντας τις περιπτώσεις όπου οι αυθαίρετες συναρτήσεις 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, η μια συνάρτηση του ζεύγους μετασχηματίζεται στην άλλη.

(file)      (file) (zoom in)

Βιβλιογραφία

 Bocheński, Józef Maria (1959), A Précis of Mathematical Logic, translated from the French and German editions by Otto Bird, D. Reidel, Dordrecht, South Holland.



 .


 Παραπομπές 

Κατηγορία:Μαθηματική λογική