Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...
Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют...
Топ:
Характеристика АТП и сварочно-жестяницкого участка: Транспорт в настоящее время является одной из важнейших отраслей народного хозяйства...
Комплексной системы оценки состояния охраны труда на производственном объекте (КСОТ-П): Цели и задачи Комплексной системы оценки состояния охраны труда и определению факторов рисков по охране труда...
Проблема типологии научных революций: Глобальные научные революции и типы научной рациональности...
Интересное:
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Средства для ингаляционного наркоза: Наркоз наступает в результате вдыхания (ингаляции) средств, которое осуществляют или с помощью маски...
Мероприятия для защиты от морозного пучения грунтов: Инженерная защита от морозного (криогенного) пучения грунтов необходима для легких малоэтажных зданий и других сооружений...
Дисциплины:
2017-12-12 | 542 |
5.00
из
|
Заказать работу |
|
|
Данное аналитическое представление называется дизъюнктивной совершенной нормальной формой (ДСНФ).
Рассмотрим примеры ДСНФ.
X | Y | F | F = X0Y1 X1Y0 X1Y1 = |
Основываясь на следствии из теоремы 1, в дснф можно вместо дизъюнкции использовать сумму по модулю два.
В результате получается формула, называемая полиномиальная совершенная нормальная форма (ПСНФ).
X | Y | F | F = |
Конъюнктивная совершенная нормальная форма.
Введем в рассмотрение характеристическую функцию нуля (X n-1,…X i,…X 1,X 0), которая равна 0 на наборе значений переменных (X n-1,…X i,…X 1,X 0), обозначенном a и равна 1 на всех остальных наборах.
Теперь докажем следующую теорему.
Теорема 2.
Любая бф не равная константе 1 может быть представлена в виде
F(X n-1, … X i, … X 1,X 0) = 1& 2& i = i,
где M 0 - множество всех номеров наборов значений переменных, на которых F(X n-1,…X i,…X 1,X 0) равна 0.
Доказательство:
Возьмем произвольный набор с номером a.
Пусть на этом наборе имеет место F(X n-1,…X 1,X 0) = 1. Тогда правая часть равенства будет иметь вид 1&1&…&1 = 1, так как ни одна характеристическая функция не равна 0.
Следовательно, левая и правая части равны.
Если же на этом наборе F = 0, то правая часть будет иметь вид 1&1&…&0&…&1 = 0, так как найдется одна , принимающая значение 0.
В результате мы получаем, что левая и правая части равны.
Рассмотрим метод получения характеристических функций нуля.
X b = 1 только в том случае, если значение Х равно значению b. Дизъюнкция степеней булевых переменных X n-1,…X i,…X 1,X 0 равна 0, если для всех Х значения степеней не равны значениям переменных. Отсюда вытекает правило получения характеристических функций нуля:
|
для набора значений переменных (b n-1 … b 1 b 0) может быть представлена как дизъюнкция степеней переменных X n-1,…X 1,X 0 со значениями степеней соответственно (1 - b n-1) … (1 - b 1)(1 - b 0).
Рассмотрим пример.
2 (X,Y,Z,W) = F 0010 (X,Y,Z,W) = X 1-0 Y 1-0 Z 1-1 W 1-0= X 1 Y 1 Z 0 W 1 =
Зная как получать характеристические функции нуля, можно сформулировать еще один способ получения выражений в алгебре Буля для таблично заданных бф не равных константе «1»:
Для всех наборов значений переменных, на которых бф равна 0, выписываем характеристические функции нуля и объединяем их знаками конъюнкции.
Такое аналитическое представление называется конъюнктивной совершенной нормальной формой (КСНФ).
Таким образом, можно сделать следующий вывод:
FМ1= ДСНФ = М0= КСНФ.
Действительно, основываясь на правилах булевой алгебры можно получить:
Решение о том, каким аналитическим представлением (ДСНФ или КСНФ) описывать булеву функцию принимается исходя из того, каких наборов меньше. Если М1 меньше, чем М0, то функцию лучше описывать с помощью ДСНФ, а если М0 меньше, чем М1, то с помощью КСНФ.
Рассмотрим пример КСНФ.
X | Y | F | F = (X1-0 Y1-1) & (X1-1 Y1-0)&(X1-1 Y1-1)= = |
МИНИМИЗАЦИЯ БФ.
|
|
Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого...
Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют...
Типы сооружений для обработки осадков: Септиками называются сооружения, в которых одновременно происходят осветление сточной жидкости...
Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!