Сегодня мы рассмотрим задачку из схемотехники, цифровой электроники или просто из алгебры логики. Существует множество логических вентилей. Для простоты возьмем два логических входа a и b. Или два цифровых сигнала, каждый из которых может принимать только два значения 1 (наличие напряжения) и 0 (отсутствие напряжение или притянут к земле). В алгебре логики этому соответствуют истина (true) и ложь (false).
Основные логические вентили их обозначения на схемах
Задача
У нас нет элемента исключающего или (XOR). Нужно реализовать его на базе других логических элементов. Как это сделать? Какое минимальное количество элементов придется использовать?
Решение:
Для начала вспомним таблицу истинности для XOR:
Что делать? Нам нужно избавиться от самого оператора XOR. Для этого мы можем расписать нашу функцию по таблице истинности двумя способами. Существуют такие вещи как СКНФ и СДНФ
СКНФ — совершенная конъюнктивная нормальная форма. Формулу можно назвать таковой, когда она — конъюнкция неповторяющихся элементарных дизъюнкций.
Когда функция равна 0, то для всех наборов переменных, при которых это происходит, записывается сумма. Однако переменные, которые имеют значение 1, берутся с отрицанием.
СДНФ — совершенная дизъюнктивная нормальная форма. Данная форма представляет собой дизъюнкцию элементарных конъюнкций, при которых функция достигает показателя «1».
Если функция равна 1, то для всех наборов переменных, при которых это происходит, записывается произведение. Однако переменные, которые имеют значение 0, берутся с отрицанием.
Разобрались в определениях? Смотрите, даже если мы изначально построим дизъюнктивную форму (СДНФ), мы всё равно можем прийти к конъюнктивной форме с помощью логических преобразований, используя только аксиомы алгебры логики.
Итак, у нас есть две формы:
Обратите внимание, что чаще всего везде используется первая формула. Но проблема в том, что для её построения на логических элементах нам нужно 5 логических элементов:
Если же мы возьмем вторую формулу, то нам удастся реализовать XOR, используя только три элемента: NAND, OR, AND. Здесь NAND - это НЕ-И ( сначала выполняется операция И, а потом инвертируется результат, почитать здесь).
И вот уже наша схема становится более компактной.
А что если взять один тип вентиля?
Интересно, что через NAND-вентиль мы можем построить любые другие. То есть теоретически можно собрать нашу схему, используя только NAND-вентили. Давайте подумаем как это сделать.
Например, для нашего второго выражения (СКНФ) мы можем преобразовать NOT, OR и AND через NAND и получить схему, полностью работающую через NAND. Выразим все логические операции через NAND:
Способ 1:
А теперь выражаем XOR через NAND:
Для данной цепочки схема получается следующей:
Способ 2:
Многовато элементов. Можно ли поменьше?
Для такой записи, с учетом повторяемости сигналов, получится следующая схема:
Способ 3:
Преобразуем более кратко и упрощаем схему
Способ 4:
Пробуем сделать еще короче. Возвращаемся к СКНФ нашего выражения и еще более хитро и просто преобразуем его:
Эта схема дает нам максимальное сокращение в реализации исключающего или ( то есть XOR ) через логические вентили И-НЕ ( то есть NAND ). Минимизация схемы связана с наличием общего сигнала not (a and b), который повторяется, а значит мы можем использовать только один вентиль для его просчета, что сокращает общее количество вентилей еще на один, по сравнению с предыдущим способом.
Еще в аналогичных задачах бывает нужна реализация какого-то вентиля (логического элемента) на уровне транзисторов. К примеру, XOR на уровне транзисторов можно выразить так:
Подводим итоги
Для понимания всех преобразований в данной заметке необходимо повторить законы алгебры логики, различные правила, упрощения, законы поглощения, правило де Моргана и другие тождества.
Для полупроводниковой электроники элементы NAND, NOR, NOT, OR, AND являются базовыми логическими элементами, которые реализуются на электрическом уровне. В том числе можно реализовать не только через транзисторы, но и через реле или электровакуумные лампы. XNOR и XOR в нескольких случаях оптимизируются через транзисторные технологии. А уже другие элементы реализовываются на базе описанных выше, с помощью логики разбиения и различных комбинаций.
Понравился разбор? Поддержите лайком и подпиской на канал :)
Если Вам нужен репетитор по физике, математике или информатике/программированию, Вы можете написать мне или в мою группу Репетитор IT mentor в VK
Библиотека с книгами для физиков, математиков и программистов
Репетитор IT mentor в VK
Репетитор IT mentor в Instagram
Репетитор IT mentor в telegram
