Типы оградительных сооружений в морском порту: По расположению оградительных сооружений в плане различают волноломы, обе оконечности...
Таксономические единицы (категории) растений: Каждая система классификации состоит из определённых соподчиненных друг другу...
Топ:
Эволюция кровеносной системы позвоночных животных: Биологическая эволюция – необратимый процесс исторического развития живой природы...
Марксистская теория происхождения государства: По мнению Маркса и Энгельса, в основе развития общества, происходящих в нем изменений лежит...
Установка замедленного коксования: Чем выше температура и ниже давление, тем место разрыва углеродной цепи всё больше смещается к её концу и значительно возрастает...
Интересное:
Распространение рака на другие отдаленные от желудка органы: Характерных симптомов рака желудка не существует. Выраженные симптомы появляются, когда опухоль...
Лечение прогрессирующих форм рака: Одним из наиболее важных достижений экспериментальной химиотерапии опухолей, начатой в 60-х и реализованной в 70-х годах, является...
Принципы управления денежными потоками: одним из методов контроля за состоянием денежной наличности является...
Дисциплины:
2017-12-12 | 541 |
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 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!