 |
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк
[18]
(x v y)(x v z)(y v z)(x v а) .
Полученное выражение является конъюнктивной нормальной формой.
Если исходная формула содержит другие операции, то перед преобразованием они предварительно выражаются через дизъюнкцию, конъюнкцию и отрицание.
2.9. СОВЕРШЕННЫЕ НОРМАЛЬНЫЕ ФОРМЫ
Если в каждом члене нормальной формы представлены все переменные либо в прямом, либо в инверсном виде, то она называется совершенной нормальной формой [2].
Доказано, что любая булева функция имеет одну и только одну совершенную дизъюнктивную (СДНФ) иконъюнктивную (СКНФ) нормальную форму.
Например:
X jX 2Х \/ XjX2Xj Х]Х2Х$ -СДНФ,
(xj v x2)(xl v х2) - СКНФ .
Если какой-нибудь член ф дизъюнктивной или конъюнктивной нормальной формы не содержит какой-либо переменной Xj то она вводится тождественным преобразованием. В СДНФ
(р = <р(xf v xj = <pxi v (pxi .
В СКНФ
tp = <pvxixi =(<pvxt)(<pvx{) .
Правильность такого преобразования основывается на следующем свойстве:
х v х = Л хх = О J
что подтверждается таблицей истинности
Таблица 2.8
Таблица истинности булевых функций X \У X, XX
X | 0 | 1 |
X | 1 | 0 |
X V X | 1 | 1 |
X X | 0 | 0 |
На основании же свойств универсальности верхней и нижней границы
(2.13)
<р = <p(x V х) - ср/ = ср ,
(р = <pv xx = (pvO = (р .
В качестве примера приведения формул к совершенной форме рассмотрим два случая:
Привести к СДНФ
XjX2 / XjXХ ш
Воспользуемся (2.22)
XjX2 (X N/ X N/ XjX23 XjX2Х N/ XjX23 XjX2Х
Привести к СКНФ
(Xj vx2)xj .
Воспользуемся (2.23)
(Xj v x2)xl v х2х3 = (xl v х2)(х1 v х2х2) ,
последняя скобка в соответствии со вторым законом дистрибутивности (2.12) равна
(Xj v х2х3) = (Xj v х2)(х} v х2) ,
с учетом чего окончательно получаем СКНФ
(Xj vx2)(x1 VX2)(Xj VX2) = (Xj vx2)(xj vx2) .
2.10. КОНСТИТУЕНТЫ И ПРЕДСТАВЛЕНИЕ ФУНКЦИЙ Конституентой единицы 1С называют конъюнкцию, содержащую все переменные xj, х2, хз,..., х„ или их инверсии, которая обращается в единицу лишь на одном выборочном наборе переменных.
Конституентой нуля К" называют дизъюнкцию, содержащую все переменные х} v х2 v х3,..., хп или их инверсии, которая обращается в нуль лишь на одном выборочном наборе переменных [2]. Например, конституенте единицы
Ке = х,х2х3х4(2.25)
соответствует набор 10 11.
При этом наборе в 1С входят только 1, что и обеспечивает 1С=1, при других значениях переменных 1С=0, т.к. в наборе 1С появляются нули вместо какой-либо переменной.
Конституенте нуля
К" = x1vx2vx3v х4(2.26)
соответствует набор 10 01.
При этом наборе в 1С входят только 0, что обеспечивает К"=0, при других значениях переменных 1С=1, т.к. в наборе 1С появляются единицы на месте какой-либо переменной.
Так как булева функция, представленная в СДНФ /сднф(х],Х2з,~-п) , является дизъюнкцией конституент единицы 1С , т.е.
/ощф(х1,х3,х3,...,хя) = Ке1 vKe2v...Ken ,(2.27)
то она обращается в единицу только при наборах значений переменных, соответствующих конституентам единицы, а на остальных наборах значений эта функция обращается в нуль.
Появление в (2.27) вместо любой lCt=l приводит к /сднф(х1,х2)хз, ...,хп)=1.
Булева функция, представленная в СКНФ /слнф(х],х2,х3,...,хп), является конъюнкцией конституент нуля 1С, т.е.
/СКНФ(х1,х2,х3,...,хп) = К"1 vK"2v...K"n ,(2.28)
и она обращается в нуль только при наборах значений переменных, соответствующих конституентам нуля, а на остальных наборах значений эта функция принимает значение единицы.