ΠΛΗΡΟΦΟΡΙΚΗ

Ορισμός άλγεβρας Boole

Η άλγεβρα Boole ορίζεται, ως μία αλγεβρική δομή A, όπου:

(α) Το Α είναι ένα σύνολο στοιχείων που περιέχει δύο τουλάχιστον στοιχεία

(β) Τα σύμβολα (+, *, ') δηλώνουν πράξεις επάνω στα στοιχεία του Α, όπου:

• η πράξη + ονομάζεται λογικό άθροισμα (OR)
• η πράξη * ονομάζεται λογικό γινόμενο (AND)
• η πράξη ' ονομάζεται λογική αντιστροφή (NOT)

(γ) Τα 0 και 1 παριστάνουν ειδικά στοιχεία που ονομάζονται σταθερές

Πίνακας Αλήθειας

Οι πράξεις του αθροίσματος (+), του γινομένου (*) και της αντιστροφής (') ορίζονται σχετικά με το σύνολο Α={0, 1}, από τον ακόλουθο πίνακα αντιστοιχίας ο οποίος ονομάζεται Πίνακας Αλήθειας.

Λογική Έκφραση 

Λογική έκφραση (boolean expression) είναι μία έκφραση της μορφής:

F = a + (b + c) * a + a * b + (b + c) * b, η οποία:

(α) Παραθέτει στη σειρά σύμβολα λογικών μεταβλητών, δηλαδή στοιχεία που παίρνουν τιμές από το σύνολο Α, π.χ. a, b, c και

(β) μεταξύ των μεταβλητών καθορίζει ορισμένες λογικές πράξεις

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

Όταν υπολογίζουμε μία λογική έκφραση, πρέπει να ακολουθούμε την προτεραιότητα των τελεστών:

1. Παρενθέσεις
2. Αντιστροφή (NOT)
3. Γινόμενο (AND)
4. Πρόσθεση (OR)

Π.χ. η έκφραση a * b + a * c ισοδυναμεί με την (a * b) + (a * c).

Παράδειγμα 1

Να υπολογιστούν οι τιμές των ακόλουθων λογικών εκφράσεων για τις τιμές των μεταβλητών a=0, b=1 και c=1:

(α) F = a + b * c

F = 0 + (1 * 1) -προτεραιότητα πράξεων

F = 1 * 1 -True AND True 

F = 1 -True 

(β) F = (a + b) * (a + c)

F = (0 + 1) * (0 + 1) -(false OR true) AND (NOT true OR true)

F = 1 * 1 -true AND true

F = 1 -true

Παράδειγμα - Πίνακας Αλήθειας

Να δημιουργήσετε τον πίνακα αλήθειας για τη λογική έκφραση F = (a + b)'.

Λογικές Πύλες

Οι λογικές πύλες είναι τα βασικά δομικά στοιχεία, τα οποία χρησιμοποιούνται για να κατασκευάσουμε λογικά κυκλώματα. Είναι έτοιμοι ψηφιακοί σχεδιασμοί, οι οποίοι υλοποιούν τις βασικές λογικές πράξεις. Στην έξοδο της πύλης παράγεται ένα σήμα, του οποίου η τιμή είναι το αποτέλεσμα της επεξεργασίας, σύμφωνα με τις παρούσες τιμές των σημάτων εισόδου και το είδος της πύλης.

Οι τιμές αντιπροσωπεύουν πεδία τάσης, π.χ.
high ή 1: 3 με 5V
low ή 0: -0.5 με 2V
Οι λογικές πύλες πρέπει να συμπεριφέρονται σύμφωνα με τον πίνακα αλήθειας τους.

Λογικές Πύλες - Πύλη NOT

Η λειτουργία της είναι η αντιστροφή του λογικού σήματος της εισόδου. Υ = Α'

Λογικές Πύλες - Πύλη AND

Η πύλη AND εκτελεί τη λογική πράξη AND (ΚΑΙ) μεταξύ των εισόδων της. Υ = Α * Β

Λογικές Πύλες - Πύλη OR

Η πύλη OR εκτελεί τη λογική πράξη OR (Η΄) μεταξύ των εισόδων της. Υ = Α + Β

Λογικές Πύλες - Πύλη NAND

Η πύλη NAND (ΟΧΙ-ΚΑΙ) δίνει την αντίθετη έξοδο από την AND. Υ = (Α * Β)'

Λογικές Πύλες - Πύλη NOR

 Η πύλη NΟR (ΟΧΙ-Η') δίνει την αντίθετη έξοδο από την OR. Υ = (Α + Β)'

Λογικές Συναρτήσεις και Λογικά Κυκλώματα

Μία λογική συνάρτηση (boolean function) αποτελείται από:

• μία δυαδική μεταβλητή,
• το σύμβολο ‘=’ και
• μία λογική έκφραση που αποτελείται από λογικές μεταβλητές, τις σταθερές 0, 1, παρενθέσεις και λογικούς τελεστές.

Η λογική έκφραση ορίζει την σχέση μεταξύ των δυαδικών μεταβλητών και η συνάρτηση, για ορισμένες τιμές των μεταβλητών, παίρνει τιμή 1 (true), ή 0 (false). Π.χ. F = A + B' * C

Κάθε λογική συνάρτηση μπορεί να μετατραπεί σε λογικό κύκλωμα.

Για τη σχεδίαση ενός συνδυαστικού λογικού κυκλώματος ακολουθούμε τα εξής βήματα:

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

Έστω ότι μας δίνεται η πιο κάτω λογική συνάρτηση: F = A + B' * C

• Η τιμή της F θα είναι 1, όταν ο όρος A = 1 ή ο όρος B' * C =1.
• Το B' * C = 1 όταν το B' = 1 (B = 0) και το C = 1.

Ο πίνακας αλήθειας μίας συνάρτησης έχει 2^Ν περιπτώσεις εισόδου, όπου Ν το πλήθος των εισόδων. Στο παράδειγμα έχουμε Ν=3 (Α, Β, C), άρα θα έχουμε 2³=8 περιπτώσεις.

Δημιουργούμε τον πίνακα αλήθειας της συνάρτησης F = A + B' * C:

 Σχεδιάζουμε το λογικό κύκλωμα της συνάρτησης F = A + B' * C 

 ...................

Ελαχιστόροι και Μεγιστόροι

 Με τον όρο ελαχιστόρος (minterm) εννοούμε κάθε πιθανό συνδυασμό που μπορεί να σχηματιστεί, χρησιμοποιώντας τις εισόδους της συνάρτησης και το λογικό ΚΑΙ.

Για παράδειγμα, αν έχουμε τις εισόδους Χ και Υ, οι ελαχιστόροι που μπορούν να σχηματιστούν είναι οι ΧΥ, Χ'Υ, ΧΥ' και Χ'Υ'.

Αντιστοίχως, με τον όρο μεγιστόρος (maxterm) εννοούμε κάθε πιθανό συνδυασμό που μπορεί να σχηματιστεί από τις εισόδους και το λογικό Ή.

Για παράδειγμα, αν έχουμε τις εισόδους Χ και Υ, θα έχουμε τους μεγιστόρους Χ+Υ, Χ'+Υ, Χ+Υ' και Χ'+Υ'.

Οι ελαχιστόροι συμβολίζονται με το γράμμα m και οι μεγιστόροι με το γράμμα Μ.

 Κάθε ελαχιστόρος αποτελεί το συμπλήρωμα του αντίστοιχου μεγιστόρου και αντιστρόφως.

Οι µεταβλητές έχουν ανεστραµένες τιµές στους αντίστοιχους ελαχιστόρους / µεγιστόρους

Μία συνάρτηση μπορεί να εκφραστεί ως το άθροισμα των ελαχιστόρων.

• Αν έχουμε, για παράδειγμα, τη συνάρτηση f=x'y'z+xy'z'+xyz, μπορεί να γραφτεί ως f=m₁+m₄+m₇.
• Επίσης, χρησιμοποιείται ο συμβολισμός f=Σ(1, 4, 7).

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

• Οπότε θα έχουμε f=M₀M₂M₃M₅M₆.
• Χρησιμοποιείται ο συμβολισμός f=Π(0, 2, 3, 5, 6).

Χάρτες Karnaugh

Σκοπός ενός χάρτη Karnaugh είναι η απλοποίηση μίας λογικής συνάρτησης. Η απλοποίηση με τη χρήση της άλγεβρας Boole είναι αρκετά δύσκολη, ιδιαίτερα για πολύπλοκες συναρτήσεις. Ο χάρτης Karnaugh αναπαριστά έναν κύβο n διαστάσεων, διατηρώντας τη σχέση «γειτονικότητας» μεταξύ των κορυφών του.

Σε κάθε χάρτη Karnaugh υπάρχουν τόσα τετράγωνα όσοι οι δυνατοί συνδυασμοί τιμών των μεταβλητών του. Κάθε τετράγωνο αντιστοιχεί σε έναν ελαχιστόρο, δηλαδή αν υπάρχουν k μεταβλητές, σχηματίζονται 2k τετράγωνα και αντιστοίχως ελαχιστόροι. Αν ο ελαχιστόρος επαληθεύει τη συνάρτηση, βάζουμε 1 στο αντίστοιχο τετράγωνο, αν όχι, βάζουμε 0. Ομάδες, δηλαδή τετράγωνα ή ορθογώνια 2 ή 4 ή 8 ή 16 επαληθευμένων ελαχιστόρων στον χάρτη, υποδεικνύουν αθροίσματα ελαχιστόρων στα οποία 1 ή 2 ή 3 ή 4 μεταβλητές, αντίστοιχα, παίρνουν όλες τις δυνατές τιμές.

Χάρτης Karnaugh δύο μεταβλητών

Ένας χάρτης Karnaugh δύο μεταβλητών θα έχει 4 ελαχιστόρους. (2²) Αν ονομάσουμε τις μεταβλητές Α και Β, τότε οι ελαχιστόροι που θα έχουμε θα είναι οι Α'Β', Α'Β, ΑΒ' και ΑΒ. Αν αντικαταστήσουμε τις μεταβλητές με το ψηφίο 1 και το συμπλήρωμα τους με το ψηφίο 0, τότε οι ελαχιστόροι γράφονται ως 00, 01, 10 και 11.