БУЛЕВЫ ФУНКЦИИ (2). Булевы функции
![]()
|
Аналитическая запись булевых функций в булевом базисе. Определение: конституентой единицы булевой функции называют произведение всех ее аргументов, записанных с отрицанием или без него. Пример: если рассмотреть функцию трех аргументов ![]() ![]() ![]() ![]() ![]() ![]() ![]() Следствие: любая конституента единицы равна единице только на одном наборе аргументов, на остальных наборах эта конституента равна нулю. Для того чтобы определить набор на котором конституента единицы равна 1 следует найти такие значения аргументов, которые дают значение 1 каждому члену произведения. Пример: ![]() ![]() Теорема: Любая булева функция может быть записана в виде дизъюнкции конституент единицы, соответствующих тем наборам на которых функция равна 1. Доказательство. Выберем в таблице истинности произвольный набор. При этом возможны два случая: Если на данном наборе функция равна 1, то из множества конституент выберем конституенту равную 1 на этом наборе (на остальных наборах она будет равна нулю) и записываем ее в формулу. Учитывая свойство дизъюнкции 1+…=1, мы обеспечиваем единичное значение функции на этом наборе. Если на этом наборе функция равна нулю, то конституента равная 1 на этом наборе в формулу не вписывается, а значит на этом наборе функция будет равна 0. После рассмотрения всех наборов мы получим аналитическую запись булевой функции в дизъюнктивной совершенной нормальной форме (ДСНФ). Алгоритм перехода к ДСНФ: - Выбрать в таблице истинности все наборы на которых функция равна единице. - Записать конституенты 1 равные единице на этих наборах. При этом, если аргумент в наборе равен 1, то в конституенту единицы этого набора он записывается без отрицания. Если же аргумент в наборе равен нулю, то он записывается с отрицанием. - Полученные конституенты соединить операцией дизъюнкции. ![]() ![]() Пример:
Определение: конституентой нуля называют дизъюнкцию всех переменных, записанных с отрицанием или без него. Любая конституента нуля равна нулю только на одном наборе, на остальных наборах она равна 1. Теорема. Любая булева функция может быть записана как конъюнкция конституент нуля, записанных для наборов, где функция равна нулю. Доказательство. Выбираем в таблице истинности произвольный набор. Если на этом наборе функция равна нулю, то записываем конституенту нуля равную нулю на этом наборе. Поскольку свойство конъюнкции ![]() Алгоритм перехода к КСНФ: -Выбрать в таблице истинности наборы на которых функция равна нулю. -Записать конституенты нуля равные нулю на этих наборах. Для этого, если аргумент набора равен нулю, то он входит в конституенту без отрицания, если же аргумент входит в набор как 1, то в соответствующую конституенту нуля вписывается его отрицание. -Все записанные конституенты нуля соединяем знаком конъюнкции. Запишем КСНФ для функции из предыдущего примера: ![]() Дешифраторы. При работе с дискретными устройствами приходится решать задачи анализа схем и задачи синтеза схем. При решении задачи синтеза после получения технического задания на проектирование устройства составляется математическая модель устройства, а затем разрабатывается схема устройства. Задача анализа обратная задаче синтеза. Решим задачу анализа, рассматривая схему простейшего дешифратора с прямыми выходами. ![]() В схеме два входа ![]() ![]() ![]() ![]() ![]() ![]()
Итак, если на вход дешифратора подать аргументы булевой функции, то на выходах дешифратора можно получить все конституенты единицы. Число входов дешифратора ![]() ![]() ![]() Приведем условные графические обозначения ( УГО) дешифраторов с 2 и 3 входами: ![]() ![]() Пример: реализовать систему булевых функций на дешифраторе с прямыми выходами.
Функции ![]() ![]() Доопределение проводят таким образом, чтобы получить наиболее простую схему. Для данного примера выгодно доопределить эти наборы нулями. ![]() Существуют дешифраторы с инверсными выходами. Схема такого дешифратора имеет вид: ![]() Запишем уравнения для этого дешифратора: ![]() ![]() ![]() ![]() Построим таблицы истинности для этих уравнений:
Условные графические обозначения дешифраторов с инверсными выходами отличаются от дешифраторов с прямыми выходами наличием значков инверсии на выходах: ![]() ![]() Такие дешифраторы являются генераторами конституент нуля и позволяют реализовывать булевы функции путем перемножения конституент нуля. Если реализовать функции из предыдущего примера на таких дешифраторах, то получим схему: ![]() |