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