И, ИЛИ, НЕ: математика на „да“ и „не“
През 1854 г. Джордж Бул описва логиката с алгебра, в която има само две стойности: 0 и 1. Близо век по-късно Клод Шанън забелязва, че същата алгебра описва и схемите с ключове. Основните действия са три:
- И (конюнкция, x·y) – 1 само ако и двата входа са 1: „на кино, ако имам пари и време“.
- ИЛИ (дизюнкция, x + y) – 1 ако поне единият е 1: „ще ям, ако има пица или паста“.
- НЕ (отрицание, x̄) – обратното.
С тях се правят и съставните: И-НЕ (NAND), ИЛИ-НЕ (NOR) и изключващо ИЛИ (XOR, x ⊕ y – 1 когато входовете са различни). Функцията се описва най-ясно с таблица на истинност: за всеки от 2ⁿ набора на входовете – какъв е изходът. С n променливи има 2^(2ⁿ) различни функции. За две променливи са 16 и петте горе са най-нужните от тях.
Ключовете тук са A = 0 и B = 1. Щракай ги и гледай кои светодиоди светят.
Зелените жици и светодиоди са 1. Знаците в правоъгълниците са по стандарта (БДС/IEC): & е И, ≥1 е ИЛИ („поне един“), =1 е XOR („точно един“), а кръгчето на изхода е НЕ. Сложи A = 1 и B = 1: И светва, а XOR угасва.
Законите: как формулата се опростява
Булевата алгебра има свои правила – като таблицата за умножение, но за 0 и 1. Част от тях изглеждат като в обикновената алгебра: комутативен, асоциативен и дистрибутивен закон, x(y + z) = xy + xz. Други са нови:
- x + x = x – да кажеш „да“ два пъти е пак „да“;
- x + x̄ = 1 и x·x̄ = 0 – нещо или е, или не е;
- x + yz = (x + y)(x + z) – дистрибутивен закон, който в обикновената алгебра го няма;
- поглъщане x + xy = x – ако x е 1, y не пита никой;
- слепване xy + xȳ = x – y веднъж е 1, веднъж 0, значи няма значение.
Най-важните са двата закона на Де Морган: черта над И става ИЛИ на чертите и обратно. Като огледало: ‾(x·y) = x̄ + ȳ.
Всеки закон се проверява с таблицата: щом лявата и дясната страна дават еднакво на всичките четири реда, те са една и съща функция. Законът тук е Де Морган (И):
| x | y | ¬(x·y) | x̄ + ȳ | |
|---|---|---|---|---|
| 0 | 0 | 1 | 1 | ✓ |
| 0 | 1 | 1 | 1 | ✓ |
| 1 | 0 | 1 | 1 | ✓ |
| 1 | 1 | 0 | 0 | ✓ |
Последният пример: x̄y + xy + xȳ = y(x̄ + x) + xȳ = y + xȳ = x + y. Три члена стават един, а схемата – от шест елемента става един елемент ИЛИ.
Минимизацията е точно това: същата функция с по-малко елементи. Така схемата е по-евтина, по-малка и по-надеждна. И по-бърза, защото сигналът минава през по-малко стъпала. Тук опростихме на ръка, по законите. Графично става с карта на Карно (тема 17), а за много променливи – с алгоритъма на Куайн–МакКласки.
От таблицата до формулата: СДНФ и СКНФ
Функцията може да се зададе по много начини: с думи, с номерата на редовете, в които е 1 (F(1, 2) = 1), с таблица, с формула или с карта. Как от таблицата се стига до формула?
- СДНФ – по единиците. За всеки ред, в който F = 1, пишем произведение: 1 – буквата без черта, 0 – с черта. После събираме произведенията.
- СКНФ – по нулите. За всеки ред, в който F = 0, пишем сума: 0 – без черта, 1 – с черта. После умножаваме сумите.
Стълбището: лампата трябва да сменя състоянието си при всяко щракване на който и да е ключ. Значи свети, когато ключовете са в различни положения. Единиците са на редовете 01 и 10, затова СДНФ е F = A̅B + AB̅, т.е. XOR. По нулите (редове 00 и 11): F = (A + B)(A̅ + B̅) – същата функция.
Всичко от един елемент: базиси И-НЕ и ИЛИ-НЕ
Набор от елементи, с който се строи всяка функция, се казва функционално пълен базис. {И, ИЛИ, НЕ} е такъв, затова СДНФ винаги може да се построи. Но с Де Морган стига и само И-НЕ, или само ИЛИ-НЕ:
- НЕ – И-НЕ със свързани входове: ‾(x·x) = x̄;
- И – И-НЕ, след него още едно като НЕ;
- ИЛИ – И-НЕ на инвертираните входове: ‾(x̄·ȳ) = x + y.
Защо е важно: чипът 74HC00 има четири И-НЕ. Стълбището с И, ИЛИ, НЕ иска три различни чипа, а само с И-НЕ се събира в един. Ключовете са A = 1 и B = 0. Осцилоскопът показва какво стана при последното щракване на A: лампата се смени 20 ns след него, по 10 ns на всяко стъпало.
A A̅ A̅B AB̅ лампа
Двете схеми дават една и съща таблица: всяко щракване сменя лампата. Различават се по броя на елементите и по пътя: в СДНФ сигналът от A минава през 2 или 3 стъпала. С И-НЕ при B = 1 и A от 0 на 1 в n2 се вижда кратък импулс от 10 ns. Той не стига до лампата, но такива импулси могат да бъдат опасни (тема 17).
Задача: Y = (X1 + X2)·(X3 + X4) само с ИЛИ-НЕ. По Де Морган Y = ‾(‾(X1 + X2) + ‾(X3 + X4)): две ИЛИ-НЕ дават инверсните суми, а трето ИЛИ-НЕ върху тях дава Y.
Самопроверка
1. Опрости A·B + A·B̄.
A·(B + B̄) = A·1 = A (слепване).
2. Как се прави ИЛИ само с И-НЕ?
A + B = И-НЕ(И-НЕ(A, A), И-НЕ(B, B)) – по Де Морган ‾(Ā·B̄) = A + B.
3. Колко функции на 3 променливи има?
2^(2³) = 2⁸ = 256.
4. Напиши СДНФ на функцията, която е 1 само за наборите 011 и 111 (x y z).
x̄yz + xyz = yz(x̄ + x) = yz.
5. Защо XOR може да служи за управляем инвертор?
x ⊕ 0 = x, а x ⊕ 1 = x̄: вторият вход решава дали първият ще мине както е или обърнат.