Άλγεβρα Μπουλ

Επιστροφή στη Γραμμική Άλγεβρα.

Η άλγεβρα Χαζού Μπουλ είναι η άλγεβρα δύο καταστάσεων. Συνήθως οι δύο καταστάσεις συμβολίζονται με 0 και 1, ενώ μια ερμηνεία είναι η αντιστοίχιση του διπόλου αληθές-ψευδές. Έτσι, η άλγεβρα Μπουλ έχει άμεση σχέση με τη λογική και τον προτασιακό λογισμό.

Ορισμός και πράξεις

Η άλγεβρα Μπουλ είναι η θεωρία στου σώματος {0,1} με πράξεις την πρόσθεση και τον πολλαπλασιασμό που ορίζονται ως: $0+0=0,0+1=1,1+1=1,1+0=1$ $0\times 0=0,0\times 1=0,1\times 1=1,1\times 0=0$ Επιπρόσθετα, υπάρχει η πράξη συμπλήρωμα που ορίζεται ως εξής: ${\overline {0}}=1,{\overline {1}}=0$

Οι ιδιότητες των πράξεων στην άλγεβρα Μπουλ είναι οι εξής: $a+b=b+a$
$a\times b=b\times a$
$(a+b)+c=a+(b+c)$
$(a\times b)\times c=a\times (b\times c)$
$(a+b)\times c=(a\times c)+(b\times c)$
$(a\times b)+c=(a+c)\times (b+c)$
$a+0=a$
$a+1=1$
$a\times 0=0$
$a\times 1=a$
${\overline {a}}\in {0,1}$
${\overline {a+b}}={\overline {a}}\times {\overline {b}}$
${\overline {a\times b}}={\overline {a}}+{\overline {b}}$

Το 0 είναι ουδέτερο στοιχείο στην πρόσθεση και απορροφητικό στον πολλαπλασιασμό. Το 1 είναι ουδέτερο στοιχείο στον πολλαπλασιασμό και απορροφητικό στην πρόσθεση. Η επιμεριστική ιδιότητα υπάρχει στον πολλαπλασιασμό και την πρόσθεση. Το σύμβολο του πολλαπλασιασμού μπορεί να παραληφθεί, ενώ το συμπλήρωμα συμβολίζεται και με τόνο. Δηλαδή το $x\times y$ και xy συμβολίζουν το ίδιο. Επίσης, το ${\overline {x}}$ και x' συμβολίζουν το ίδιο.

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

Για κάθε συνάρτηση μιας μεταβλητής f το πεδίο ορισμού είναι το Α={0,1}. Το πεδίο τιμών είναι το Β={0,1}. Για κάθε συνάρτηση αρκεί να οριστεί η τιμή της για κάθε στοιχείο του Α, δηλαδή η δυάδα των τιμών της. Αυτή είναι μια δυάδα από σύνολο δύο τιμών. άρα οι πιθανές συναρτήσεις που μπορούν να υπάρξουν είναι 4. Αυτές είναι:

f(x)=0

f(x)=x

f(x)=${\overline {x}}$

f(x)=1

Για κάθε συνάρτηση δύο μεταβλητών f το πεδίο ορισμού είναι το Α={(0,0),(0,1),(1,0),(1,1)}. Το πεδίο τιμών είναι το Β={0,1}. Για κάθε συνάρτηση αρκεί να οριστεί η τιμή της για κάθε στοιχείο του Α, δηλαδή η 4άδα των τιμών της. Αυτή είναι μια τετράδα από σύνολο δύο τιμών. άρα οι πιθανές συναρτήσεις που μπορούν να υπάρξουν είναι 16.

Κάθε συνάρτηση στην άλγεβρα Μπουλ έχει πεπερασμένο πεδίο ορισμού. Μια λογική συνάρτηση περιγράφεται πλήρως από έναν πίνακα που περιέχει σε κάθε γραμμή τις τιμές των ορισμάτων και την αντίστοιχη τιμή της συνάρτησης. Για παράδειγμα η συνάρτηση f(x,y)=x+y περιγράφεται πλήρως από τον πίνακα:

${\begin{matrix}x&y&f\\0&0&0\\0&1&1\\1&0&1\\1&1&1\end{matrix}}$

Επιπλέον, η ισότητα λογικών συναρτήσεων μπορεί να γίνει συγκρίνοντας τους πίνακες. Για παράδειγμα Να αποδειχθεί ότι x'x=0:

Ο πίνακας της x'x: ${\begin{matrix}x&x'&x'x\\0&1&0\\1&0&0\end{matrix}}$, ενώ ο πίνακας του 0: ${\begin{matrix}x&0\\0&0\\1&0\end{matrix}}$

Αφού κάθε η τιμή κάθε στοιχείου της στήλης x'x ισούται με την αντίστοιχη τιμή της στήλης 0 ισχύει x'x=0.

Περισσότερα στο w:Λογικές συναρτήσεις.

Μοναδική πράξη και ελαχιστοποίηση συναρτήσεων

Όλες οι συναρτήσεις μπορούν να συντεθούν από μία μόνο πράξη. Αυτή μπορεί να είναι η άρνηση πρόσθεσης ή η άρνηση πολλαπλασιασμού. Για παράδειγμα, έστω η συνάρτηση της άρνησης πολλαπλασιασμού f: $f(x,y)={\overline {x\times y}}$ Τότε:

${\overline {x}}={\overline {x\times x}}=f(x,x)$

$x\times y={\overline {({\overline {x\times y}})}}={\overline {f(x,y)}}=f(f(x,y),f(x,y))$

$x+y={\overline {({\overline {x}}\times {\overline {y}})}}={\overline {(f(x,x)\times f(y,y))}}=f(f(x,x),f(y,y))$

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

Ελαχιστόρος ν ορισμάτων είναι γινόμενο των ορισμάτων και συμπληρωμάτων ορισμάτων. Για κάθε όρισμα το ίδιο το όρισμα ή το συμπλήρωμα του ορίσματος είναι παράγοντας του γινομένου. Μεγιστόρος ν ορισμάτων είναι το άθροισμα ορισμάτων και συμπληρωμάτων ορισμάτων της συνάρτησης. Για κάθε όρισμα το ίδιο το όρισμα ή το συμπλήρωμα του ορίσματος είναι όρος του αθροίσματος.

Για παράδειγμα στη συνάρτηση:

${\begin{matrix}x&y&f\\0&0&1\\0&1&0\\1&0&0\\1&1&1\end{matrix}}$

Τα ορίσματα είναι τα x και y.

Οι ελαχιστόροι είναι: x'y', x'y, xy', xy

Οι μεγιστόροι: x+y, x+y', x'+y, x'+y'

Η ν-άδα των ορισμάτων είναι ένας δυαδικός αριθμός. Συνήθως ένας ελαχιστόρος συμβολίζεται με e με δείκτη αυτόν τον αριθμό σε δεκαδική μορφή. Συνήθως ένας μεγιστόρος συμβολίζεται με m με δείκτη αυτόν τον αριθμό σε δεκαδική μορφή.

Ένας ελαχιστόρος ισούται με 1 μόνο για μια συγκεκριμένη ν-άδα ορισμάτων.

Ένας μεγιστόρος ισούται με 0 μόνο για μια συγκεκριμένη ν-άδα ορισμάτων.

Για αυτό μια λογική συνάρτηση μπορεί να γραφτεί ως άθροισα ελαχιστόρων, ή ως γινόμενο μεγιστόρων. Στο παραπάνω παράδειγμα: $f(x,y)=e_{0}+e_{3}=m_{1}m_{2}$