Булева алгебра и минимизация логических функций
Основные законы булевой алгебры, таблицы истинности, СДНФ и СКНФ, минимизация методом карт Карно и Квайна, переход к логической схеме.
Булева алгебра описывает функции, у которых и аргументы, и результат принимают два значения. На ней держится вся цифровая схемотехника: любая логическая функция реализуется набором вентилей, а минимизация напрямую сокращает число микросхем.
Основные операции
| Операция | Обозначение | Читается | Результат 1 когда |
|---|---|---|---|
| Конъюнкция | x ∧ y, x·y | И | Оба аргумента равны 1 |
| Дизъюнкция | x ∨ y, x+y | ИЛИ | Хотя бы один равен 1 |
| Отрицание | ¬x, x̄ | НЕ | Аргумент равен 0 |
| Импликация | x → y | Если ... то | Кроме случая 1 → 0 |
| Эквиваленция | x ↔ y | Тогда и только тогда | Аргументы равны |
| Сумма по модулю 2 | x ⊕ y | XOR | Аргументы различны |
Законы
Коммутативность: x∨y = y∨x x·y = y·x Ассоциативность: (x∨y)∨z = x∨(y∨z) Дистрибутивность: x·(y∨z) = x·y ∨ x·z x∨(y·z) = (x∨y)·(x∨z) Идемпотентность: x∨x = x x·x = x Поглощение: x ∨ x·y = x x·(x∨y) = x Склеивание: x·y ∨ x·ȳ = x Де Моргана: ¬(x∨y) = x̄·ȳ ¬(x·y) = x̄ ∨ ȳ Константы: x∨0 = x, x∨1 = 1, x·0 = 0, x·1 = x Дополнение: x ∨ x̄ = 1 x · x̄ = 0
СДНФ и СКНФ
Любую функцию можно записать канонически прямо по таблице истинности.
- СДНФ — совершенная дизъюнктивная нормальная форма: берут строки, где функция равна 1. Для каждой пишут конъюнкцию всех переменных, причём переменную с нулевым значением берут с отрицанием. Полученные конъюнкции объединяют через ИЛИ.
- СКНФ — совершенная конъюнктивная: берут строки с нулём, пишут дизъюнкции, переменную с единичным значением берут с отрицанием, всё объединяют через И.
- Практическое правило: если единиц в таблице меньше — удобнее СДНФ, если меньше нулей — СКНФ.
Пример для f(x,y,z) = 1 на наборах 001, 011, 111: СДНФ: f = x̄·ȳ·z ∨ x̄·y·z ∨ x·y·z
Минимизация картами Карно
Карта Карно — таблица истинности, перестроенная так, что соседние клетки отличаются значением ровно одной переменной (код Грея). Это позволяет видеть склейки глазами.
- Разметить карту в коде Грея: для двух переменных порядок столбцов 00, 01, 11, 10 — не 00, 01, 10, 11.
- Расставить значения функции по наборам.
- Объединить единицы в прямоугольные области размером 1, 2, 4, 8 клеток — только степени двойки.
- Области берут максимально большими, они могут пересекаться и заворачиваться через края карты — левый край соседствует с правым, верх с низом.
- Каждая область даёт конъюнкцию из переменных, которые внутри неё не меняются.
- Полученные конъюнкции объединить через ИЛИ.
Карта Карно для трёх переменных, f = 1 на 001, 011, 101, 111
yz=00 01 11 10
x=0 0 1 1 0
x=1 0 1 1 0
Выделяется один блок из четырёх единиц — вся колонка z=1.
Внутри блока x и y меняются, постоянна только z.
Ответ: f = z
Проверка через СДНФ:
x̄ȳz ∨ x̄yz ∨ xȳz ∨ xyz = z·(x̄ȳ ∨ x̄y ∨ xȳ ∨ xy) = z·1 = zРазмер области напрямую связан с числом переменных в слагаемом: блок из 2 клеток убирает одну переменную, из 4 — две, из 8 — три. Отсюда правило: чем крупнее области, тем короче итоговая формула.
Что дальше в лабораторной
- Построить логическую схему по минимизированной формуле в базисе И-ИЛИ-НЕ.
- Перевести в базис И-НЕ (Шеффера) или ИЛИ-НЕ (Пирса) двойным отрицанием и законами Де Моргана — эти базисы функционально полны и дешевле в реализации.
- Посчитать число вентилей до и после минимизации — это и есть измеримый результат работы.
- Проверить схему моделированием в Multisim, Logisim или Proteus.
Частые вопросы
До скольких переменных удобны карты Карно?
До четырёх — карта 4×4 читается легко. Для пяти-шести переменных применяют метод Квайна-Мак-Класки, он табличный и алгоритмизируется.
Можно ли объединять нули вместо единиц?
Да, тогда получится минимальная КНФ вместо ДНФ. Иногда она короче — стоит посчитать оба варианта и выбрать тот, где меньше вентилей.