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

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

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

Έστω ότι έχουμε δίτιμες μεταβλητές, που έχουν δηλαδή πεδίο τιμών δισύνολο, (για παράδειγμα {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	α$\oplus$β = α’β + αβ’	Αποκλειστικό Ή	α XOR β
f7	α + β	Ή	α OR β
f8	(α + β)’ = α’β’ = α$\downarrow$β	ΟΧΙ-Ή	α NOR β
f9	α’β’ + αβ = ( α≈β )	Ισοδυναμία
f10	β’	ΟΧΙ-Β, Συμπλήρωμα του β	NOT β
f11	α + β’ = ( β$\Rightarrow$α )	β συνεπάγεται α
f12	α’	ΟΧΙ-Α, Συμπλήρωμα του α	NOT α
f13	α’ + β = ( α$\Rightarrow$β )	α συνεπάγεται β
f14	(αβ)’ = α’ + β’ = α$\uparrow$β	ΟΧΙ-ΚΑΙ	α 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.

α $\uparrow$ β = α NAND β = NOT (α AND β)
NOT α = NOT (α AND 1) = α $\uparrow$ 1
NOT α = NOT (α AND α) = α $\uparrow$ α
α OR β = NOT (NOT (α OR β)) = NOT ((NOT α) AND (NOT β)) = (NOT α) $\uparrow$ (NOT β) = (α $\uparrow$ 1) $\uparrow$ (β $\uparrow$ 1) = (α $\uparrow$ 1) $\uparrow$ (β $\uparrow$ β) = (α $\uparrow$ α) $\uparrow$ (β $\uparrow$ 1) = (α $\uparrow$ α) $\uparrow$ (β $\uparrow$ β)
α AND β = NOT (NOT (α AND β)) = NOT (α $\uparrow$ β) = (α $\uparrow$ β) $\uparrow$ 1 = (α $\uparrow$ β) $\uparrow$ ( α $\uparrow$ β)

α $\downarrow$ β = α NOR β = NOT (α OR β)
NOT α = NOT (α OR 0) = α $\downarrow$ 0
NOT α = NOT (α OR α) = α $\downarrow$ α
α OR β = NOT (NOT (α OR β)) = NOT (α $\downarrow$ β) = (α $\downarrow$ β) $\downarrow$ 0 = (α $\downarrow$ β) $\downarrow$ (α $\downarrow$ β)
α AND β = NOT (NOT (α AND β)) = NOT((NOT α) OR (NOT β)) = (NOT α) $\downarrow$ (NOT β) = (α $\downarrow$ 0) $\downarrow$ (β $\downarrow$ 0) = (α $\downarrow$ 0) $\downarrow$ (β $\downarrow$ β) = (α $\downarrow$ α) $\downarrow$ (β $\downarrow$ 0) = (α $\downarrow$ α) $\downarrow$ (β $\downarrow$ β)

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

(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.
• Chao, C. (2023). 数理逻辑：形式化方法的应用 [Mathematical Logic: Applications of the Formalization Method] (στα Chinese). Beijing: Preprint. σελίδες 15–28. 
• Enderton, Herbert (2001). A Mathematical Introduction to Logic (2nd έκδοση). Boston, MA: Academic Press. ISBN 978-0-12-238452-3. 
• Gamut, L.T.F (1991). «Chapter 2». Logic, Language and Meaning. 1. University of Chicago Press. σελίδες 54–64. OCLC 21372380. 
• Rautenberg, W. (2010). A Concise Introduction to Mathematical Logic (3rd έκδοση). New York: Springer Science+Business Media. doi:10.1007/978-1-4419-1221-3. ISBN 978-1-4419-1220-6. .
• Humberstone, Lloyd (2011). The Connectives. MIT Press. ISBN 978-0-262-01654-4.