Λειτουργική πληρότητα#

Ένα σύνολο λογικών τελεστών είναι λειτουργικά πλήρες όταν καθεμία από τις δεκαέξι δυαδικές συναρτήσεις αληθείας μπορεί να κατασκευαστεί από τελεστές αυτού του συνόλου, μέσω σύνθεσης. Τα κλασικά πλήρη σύνολα που ήδη γνωρίζετε είναι τα {∧, ∨, ¬} και {→, ⊥}. Το εκπληκτικό — και χρήσιμο — αποτέλεσμα είναι ότι ένας μόνο τελεστής αρκεί, αλλά μόνο δύο από τις δεκαέξι δυαδικές συναρτήσεις έχουν αυτή την ιδιότητα: το NAND και το NOR.

Το NAND πήρε το όνομά του από τον Henry M. Sheffer (1913) και γράφεται ↑· το NOR πήρε το όνομά του από τον Charles Sanders Peirce (που το περιέγραψε νωρίτερα) και γράφεται ↓. Είναι οι δύο γραμμές Sheffer.

Δομώντας τα πάντα από NAND#

Το NAND από μόνο του σας δίνει και τις δεκαέξι συναρτήσεις. Οι παρακάτω κατασκευές δείχνουν τις τέσσερις πιο χρήσιμες — NOT, AND, OR, XOR — με όρους του ↑. Σκεφτείτε το a ↑ b ως !($a && $b).

Στόχος

Με όρους NAND

Γιατί

¬a

a ↑ a

Το !(a ∧ a) είναι !a

a ∧ b

(a ↑ b) ↑ (a ↑ b)

NAND και μετά άρνηση του αποτελέσματος, δηλ. !!(a ∧ b) ≡ a ∧ b

a ∨ b

(a ↑ a) ↑ (b ↑ b)

De Morgan: a ∨ b ≡ ¬(¬a ∧ ¬b) ≡ ¬a ↑ ¬b

a ⊕ b

(a ↑ (a ↑ b)) ↑ (b ↑ (a ↑ b))

Το XOR είναι το AND των (a ∨ b) και ¬(a ∧ b) — αφήνεται ως άσκηση

Οι ίδιες κατασκευές υπάρχουν με NOR· είναι τα δυϊκά κατά De Morgan.

Στην Perl#

Δεν θα γράψετε τον κώδικά σας με αυτόν τον τρόπο σε παραγωγή — το (a ↑ a) ↑ (b ↑ b) είναι χειρότερη γραφή του OR από ό,τι είναι το ||. Αλλά αξίζει να δείτε τις κατασκευές να τρέχουν στην πραγματικότητα, επειδή ο αφηρημένος ισχυρισμός («τα πάντα ανάγονται σε έναν τελεστή») γίνεται συγκεκριμένος όταν τον πληκτρολογείτε.

sub nand { !($_[0] && $_[1]) }       # the only primitive

sub not_a { nand($_[0], $_[0]) }                       # ¬a
sub and_  { my $n = nand($_[0], $_[1]); nand($n, $n) } # a ∧ b
sub or_   { nand(nand($_[0], $_[0]), nand($_[1], $_[1])) }   # a ∨ b
sub xor_  {
    my ($a, $b) = @_;
    my $n = nand($a, $b);
    nand(nand($a, $n), nand($b, $n));
}

# Verify across all four input combinations:
for my $a (0, 1) {
    for my $b (0, 1) {
        printf "a=%d b=%d  not=%d and=%d or=%d xor=%d\n",
            $a, $b,
            not_a($a)         ? 1 : 0,
            and_($a, $b)      ? 1 : 0,
            or_($a, $b)       ? 1 : 0,
            xor_($a, $b)      ? 1 : 0;
    }
}

Έξοδος:

a=0 b=0  not=1 and=0 or=0 xor=0
a=0 b=1  not=1 and=0 or=1 xor=1
a=1 b=0  not=0 and=0 or=1 xor=1
a=1 b=1  not=0 and=1 or=1 xor=0

Κάθε γραμμή ταιριάζει με τον πίνακα αληθείας από το προηγούμενο κεφάλαιο.

Γιατί έχει σημασία#

Τρία πράγματα, με σειρά από το πρακτικό προς το βαθύ:

  1. Εξηγεί το πανηγύρι των ταυτοτήτων. Το NAND, το NOR, και οι έντεκα μη απευθείας γραμμές του κεφαλαίου του πίνακα αληθείας δεν είναι ένας ζωολογικός κήπος ξεχωριστών γεγονότων. Όλες είναι εκφράσιμες από έναν μόνο τελεστή· οι έντεκα μη απευθείας γραφές στην Perl είναι απλώς αναγνώσιμες συντομεύσεις για σύντομες συνθέσεις NAND ή NOR.

  2. Έτσι λειτουργεί στην πραγματικότητα το πυρίτιο. Η λογική στατικού CMOS παράγει NAND και NOR φθηνότερα από AND και OR — μια πύλη AND δύο εισόδων κατασκευάζεται ως NAND ακολουθούμενη από αναστροφέα. Κάθε άλλη πύλη σε ένα τσιπ είναι σύνθεση από NAND (ή NOR). Το μοτίβο επαναλαμβάνεται στα εσωτερικά επιλυτών και μηχανών περιορισμών: οι επιλυτές SAT κανονικοποιούν σε CNF ακριβώς επειδή το OR-από-(κυριολεκτικούς) και AND-από-(προτάσεις) είναι το ελάχιστο λεξιλόγιο που χρειάζονται.

  3. Διδάσκει την πειθαρχία της κανονικής μορφής. Κάθε λογική έκφραση έχει πολλές ισοδύναμες μορφές, αλλά μόνο λίγες είναι κανονικές. Η CNF (συζευκτική κανονική μορφή: ένα AND από OR πιθανώς-αρνημένων κυριολεκτικών) και η DNF (διαζευκτική κανονική μορφή: ένα OR από AND) είναι οι δύο πιο συνηθισμένες. Η αναγωγή ενός μπερδέματος σε CNF ή DNF είναι μια καθαρά μηχανική διαδικασία βασισμένη στον De Morgan συν την επιμεριστικότητα, και μόλις η έκφρασή σας είναι σε κανονική μορφή, μπορείτε να τη συγκρίνετε με άλλη έκφραση κανονικής μορφής για να ελέγξετε ισοδυναμία — χωρίς πίνακες αληθείας, χωρίς δοκιμές.

Δεν θα υλοποιήσετε επιλυτή SAT την επόμενη εβδομάδα. Αλλά την επόμενη φορά που θα βρεθείτε να γράφετε if ((!$a && $b) || (!$c && $b) || ($a && !$c)) και θα αναρωτιέστε αν η προηγούμενη έκδοση ήταν ισοδύναμη, έχετε ένα εργαλείο: επιμερίστε, παραγοντοποιήστε, κανονικοποιήστε. Δύο εκφράσεις που ανάγονται στην ίδια DNF υπολογίζουν την ίδια συνάρτηση.

Τι πρέπει να θυμάστε από αυτό το κεφάλαιο#

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

  • Οι κατασκευές είναι σύντομες και μπορείτε να τις επαληθεύσετε στην Perl σε δέκα γραμμές.

  • Το ζητούμενο δεν είναι να γράφετε κώδικα σε NAND, αλλά να γνωρίζετε ότι και οι δεκαέξι δυαδικές συναρτήσεις ζουν πάνω σε ένα θεμέλιο. Οι φαινομενικά ανόμοιες γραμμές του κεφαλαίου του πίνακα αληθείας είναι μια οικογένεια.