Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...
Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций...
Топ:
Особенности труда и отдыха в условиях низких температур: К работам при низких температурах на открытом воздухе и в не отапливаемых помещениях допускаются лица не моложе 18 лет, прошедшие...
Оснащения врачебно-сестринской бригады.
Марксистская теория происхождения государства: По мнению Маркса и Энгельса, в основе развития общества, происходящих в нем изменений лежит...
Интересное:
Наиболее распространенные виды рака: Раковая опухоль — это самостоятельное новообразование, которое может возникнуть и от повышенного давления...
Распространение рака на другие отдаленные от желудка органы: Характерных симптомов рака желудка не существует. Выраженные симптомы появляются, когда опухоль...
Финансовый рынок и его значение в управлении денежными потоками на современном этапе: любому предприятию для расширения производства и увеличения прибыли нужны...
Дисциплины:
2017-12-12 | 543 |
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)= = |
МИНИМИЗАЦИЯ БФ.
|
|
Кормораздатчик мобильный электрифицированный: схема и процесс работы устройства...
Поперечные профили набережных и береговой полосы: На городских территориях берегоукрепление проектируют с учетом технических и экономических требований, но особое значение придают эстетическим...
Адаптации растений и животных к жизни в горах: Большое значение для жизни организмов в горах имеют степень расчленения, крутизна и экспозиционные различия склонов...
Своеобразие русской архитектуры: Основной материал – дерево – быстрота постройки, но недолговечность и необходимость деления...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!