Тупиковые днф и алгоритм наискорейшего спуска
Этот метод основан на двух преобразованиях, упрощающих ДНФ: удаление конъюнкции и удаление множителя.
Первое преобразование возможно тогда, когда исходная ДНФ и ДНФ, получающаяся после удаления некоторой элементарной конъюнкции, совпадают на всех наборах значений переменных {x1, x2, … , xn}.
Аналогично второе преобразование возможно в тех случаях, когда получающаяся после удаления множителя из некоторой элементарной конъюнкции ДНФ, продолжает реализовывать исходную функцию.
ДНФ, которую нельзя упростить с помощью этих двух преобразований, называют тупиковой ДНФ (ТДНФ) относительно удаления конъюнкции и множителей в конъюнкциях. Например, ДНФ= является тупиковой.
Важно, что указанные преобразования уменьшают сложность ДНФ, одна и та же функция может иметь несколько различных тупиковых ДНФ, среди которых всегда содержатся и минимальные, хотя не обязательно все.
Опишем алгоритм по шагам.
Шаг 1. Для функции f(x1, x2, … , xn), заданной таблицей, записывается СДНФ, которая считается исходной ДНФ.
Шаг 2. Исходная ДНФ просматривается слева направо. Для текущей конъюнкции исходной ДНФ пытаются применить первое преобразование – удаление конъюнкции. Если это преобразование возможно, то переходят к следующей конъюнкции и т.д.. В противном случае переходят к шагу 3.
Шаг 3. Поочередно (слева направо) рассматривают каждый множитель текущей элементарной конъюнкции с целью применения преобразования «удаление множителя». После просмотра всех множителей этой конъюнкции текущей становится следующая конъюнкция, и процесс возвращается к шагу 2.
После того, как будут рассмотрены все элементарные конъюнкции исходной ДНФ, приступают к выполнению шага 4.
Шаг 4. Полученную в результате выполнения предыдущих шагов ДНФ снова исследуют слева направо, поочередно рассматривая каждую элементарную конъюнкцию. Однако на этот раз пытаются применить только первое преобразование, не переходя ко второму.
ДНФ, полученная в итоге, является тупиковой относительно введенных преобразований.
Для получения других ТДНФ той же функции в исходной СДНФ переупорядочивают множители в элементарных конъюнкциях. Число таких переупорядочиваний в общем случае не превышает (n!)s, где s – число элементарных конъюнкций в исходной СДНФ, а n – число переменных функции. Но s2n, поэтому (n!)s(n!)2n. Для каждой СДНФ необходимо выполнить не менее s операций по проверке удаления конъюнкций на втором шаге и не более s таких же операций на четвертом шаге. Кроме того, в каждой конъюнкции возможно выполнение n операций по проверке удаления множителя на третьем шаге. Так что общее число проверок для одной СДНФ не больше, чем s+s+n·s = s·(n+2) 2n·(n+2). Тем самым трудоемкость построения минимальных ДНФ по этому алгоритму не превышает (n!)2n·(n+2)·2n, что меньше, чем 23n. Таким образом, трудоемкость метода «наискорейшего спуска» меньше трудоемкости тривиального алгоритма, но для «ручного» просчета слишком велика. Однако алгоритм легко программируется для решения задачи на компьютере.
x | y | z | f(x,y,z) |
0 | 0 | 0 | 0 |
0 | 0 | 1 | 1 |
0 | 1 | 0 | 0 |
0 | 1 | 1 | 1 |
1 | 0 | 0 | 1 |
1 | 0 | 1 | 1 |
1 | 1 | 0 | 1 |
1 | 1 | 1 | 0 |
Таблица 21 |
Пусть функция трех переменных f(x, y, z) задана таблицей 21. Запишем СДНФ этой функции: СДНФ(f) =
Оформим все вычисления в виде таблицы 22.
Таблица 22 |
|
|
|
ДНФ | Текущая конъюнкция | Текущий множитель | Примечание |
1. |
|
| не удаляется |
2. |
|
| удаляется |
|
|
| не удаляется |
|
| z | не удаляется |
|
|
| не удаляется |
|
|
| не удаляется |
3. |
| y | удаляется |
|
| z | не удаляется |
|
|
| не удаляется |
|
| x | не удаляется |
4. |
|
| удаляется |
|
|
| не удаляется |
5. |
|
| удаляется |
6. |
|
| удаляется |
|
|
| не удаляется |
|
|
| не удаляется |
|
|
| не удаляется |
Таким образом, ТДНФ1(f) =
Теперь переставим в третьей конъюнкции исходной ДНФ множитель вперед, тогда новый ход вычислений представится таблицей 23:
Таблица 23
ДНФ | Текущая конъюнкция | Текущий множитель | Примечание |
|
| не удаляется | |
2. |
|
| удаляется |
|
|
| не удаляется |
|
| z | не удаляется |
|
|
| не удаляется |
|
|
| не удаляется |
3. |
| y | удаляется |
|
| z | не удаляется |
|
|
| не удаляется |
4. |
|
| удаляется |
|
| x | не удаляется |
|
|
| не удаляется |
5. |
|
| удаляется |
|
|
| не удаляется |
|
| x | не удаляется |
6. |
| y | удаляется |
|
|
| не удаляется |
7. |
|
| удаляется |
|
|
| не удаляется |
|
|
| не удаляется |
|
|
| не удаляется |
Таким образом, ТДНФ2(f) =
В данном примере другие перестановки множителей в конъюнкциях СДНФ уже не приведут к новым результатам. Кроме того, обе найденные тупиковые ДНФ являются также и минимальными для этой функции.
Yandex.RTB R-A-252273-3- Часть II
- Алгебра двузначной логики
- Функции алгебры логики
- Способы задания функций алгебры логики
- Эквивалентность функций
- Реализация функций формулами
- Эквивалентность формул и тождества
- Упрощение формул
- Двойственные функции и принцип двойственности
- Применение принципа двойственности
- Аналитическая запись функций алгебры логики
- Аналитическое построение сднф и скнф
- Теорема о тройке связок
- Полные системы функций и полиномы Жегалкина
- Замыкание систем функций алгебры логики
- Важнейшие замкнутые классы
- Теорема Поста о полноте
- Минимизация булевых функций
- Основные понятия
- Метод неопределенных коэффициентов
- Тупиковые днф и алгоритм наискорейшего спуска
- Геометрическое представление функций алгебры логики
- Аналитическое построение сокращенной днф
- Локальные алгоритмы
- Алгоритм Куайна
- Диаграммы Вейча–Карно
- Построение днф по карте Карно
- Задачи и упражнения
- Список литературы
- Часть II
- 400131, Волгоград, просп. Им. В.И.Ленина, 28
- 400131, Волгоград, ул. Советская, 35