1. Основы математической логики и методы упрощения логических выражений
Основы математической логики и методы упрощения логических выражений
Проектирование любых цифровых устройств, от простейших контроллеров до современных процессоров, опирается на строгий математический фундамент. Математическая логика позволяет описывать работу электронных схем с помощью алгебраических уравнений, а затем оптимизировать их, сокращая количество необходимых физических компонентов.
Законы булевой алгебры и упрощение выражений
Основой схемотехники является булева алгебра — раздел математики, оперирующий переменными, которые могут принимать только два значения: логический ноль (ложь) и логическая единица (истина). Для преобразования и упрощения логических функций используются базовые законы и тождества.
Упрощение логических выражений необходимо для того, чтобы итоговая схема содержала как можно меньше элементов. Это снижает стоимость устройства, уменьшает его размер и повышает надежность.
| Название закона | Формула для конъюнкции (И) | Формула для дизъюнкции (ИЛИ) | | :--- | :--- | :--- | | Переместительный | | | | Сочетательный | | | | Распределительный | | | | Правила де Моргана | | | | Закон поглощения | | |
Где , , — логические переменные, — операция логического умножения (конъюнкция), — операция логического сложения (дизъюнкция), а черта над переменной или выражением означает логическое отрицание (инверсию).
Рассмотрим пример аналитического упрощения функции:
Где — результирующая логическая функция, и — входные переменные, — конъюнкция, — дизъюнкция, — инверсия переменной .
Применяя распределительный закон, вынесем общий множитель за скобки: . Поскольку сумма переменной и ее инверсии всегда равна единице (), получаем: . Таким образом, сложная схема из трех логических элементов заменяется прямым проводом от входа .
Построение СДНФ и СКНФ по таблице истинности
Любую логическую функцию можно задать с помощью таблицы истинности, которая показывает результат функции для всех возможных комбинаций входных сигналов. На основе этой таблицы можно составить алгебраическое выражение в стандартной форме.
Совершенная дизъюнктивная нормальная форма (СДНФ) строится по строкам таблицы, где функция равна единице. Для каждой такой строки записывается произведение (конъюнкция) всех переменных, причем если переменная в строке равна нулю, она берется с инверсией.
Совершенная конъюнктивная нормальная форма (СКНФ) строится по строкам, где функция равна нулю. Для них записывается сумма (дизъюнкция) всех переменных, и в этом случае с инверсией берутся переменные, равные единице.
Пример таблицы истинности для функции голосования большинства (три входа):
| | | | | | :--- | :--- | :--- | :--- | | 0 | 0 | 0 | 0 | | 0 | 0 | 1 | 0 | | 0 | 1 | 0 | 0 | | 0 | 1 | 1 | 1 | | 1 | 0 | 0 | 0 | | 1 | 0 | 1 | 1 | | 1 | 1 | 0 | 1 | | 1 | 1 | 1 | 1 |
Для построения СДНФ берем строки, где (это 4-я, 6-я, 7-я и 8-я строки):
Где — функция, , , — входные переменные, — логическое И, — логическое ИЛИ, — инверсия .
Минимизация с помощью карт Карно
Аналитическое упрощение (с помощью формул) требует интуиции и опыта. Для систематической минимизации функций от 2 до 6 переменных применяются карты Карно (Karnaugh maps). Это графический метод, основанный на склеивании соседних термов.
Карта Карно представляет собой двумерную таблицу, где каждая ячейка соответствует одной строке таблицы истинности. Ключевая особенность карты заключается в том, что соседние ячейки (по горизонтали и вертикали) отличаются значением только одной переменной. Это достигается использованием кода Грея для нумерации строк и столбцов.
!Карта Карно для трех переменных
Правила минимизации по карте Карно:
Каждый контур формирует одно слагаемое в итоговой функции. Переменные, которые меняют свое значение внутри контура, исключаются из выражения.
Релейно-контактные схемы
Исторически первые логические автоматы строились на электромеханических реле. Релейно-контактные схемы наглядно демонстрируют физический смысл логических операций.
В таких схемах логическая переменная представляется контактом: нормально разомкнутым (прямое значение) или нормально замкнутым (инверсия).
> Релейно-контактные схемы стали историческим мостом между абстрактной математикой и реальной инженерией, доказав, что логику можно «собрать» из проводов и переключателей.
Базовые правила построения: * Последовательное соединение контактов реализует операцию логического И (конъюнкцию). Ток пройдет только в том случае, если замкнуты все контакты в цепи. * Параллельное соединение контактов реализует операцию логического ИЛИ (дизъюнкцию). Ток пройдет, если замкнут хотя бы один из параллельных путей.
Например, если в цепи последовательно установлены два выключателя и , лампочка загорится только при одновременном нажатии обоих. Это физическая реализация функции .
Теория автоматов: построение логических схем
В современной цифровой электронике вместо реле используются транзисторные логические вентили. Каждый вентиль выполняет определенную логическую операцию.
Интересным фактом теории автоматов является существование универсальных базисов. Это означает, что любую, даже самую сложную логическую схему, можно построить, используя только один тип логических элементов. Такими универсальными элементами являются вентили И-НЕ (NAND) и ИЛИ-НЕ (NOR).
!Реализация базовых функций на элементах И-НЕ
Рассмотрим, как получить базовые операции, используя только элементы И-НЕ (NAND): Операция НЕ (Инверсия): Если соединить оба входа двухвходового элемента И-НЕ* вместе и подать на них сигнал , на выходе мы получим . Операция И (Конъюнкция): Сначала сигналы и подаются на первый элемент И-НЕ, а затем результат пропускается через второй элемент И-НЕ*, работающий как инвертор (с объединенными входами). Двойная инверсия отменяет сама себя. Операция ИЛИ (Дизъюнкция): Согласно правилу де Моргана, . Поэтому сначала каждый сигнал инвертируется отдельным элементом И-НЕ, а затем оба инвертированных сигнала подаются на третий элемент И-НЕ*.
Использование единого базиса (например, только И-НЕ) значительно упрощает и удешевляет производство интегральных микросхем, так как на кремниевой пластине формируются миллионы абсолютно одинаковых транзисторных ячеек.