Приведение ДНФ к минимальному виду

forester_200

Есть ДНФ.
Правильно ли я понимаю, что минимальная ДНФ - это равносильная ей ДНФ минимальной длины?
(При этом под длиной ДНФ понимается сумма длин её дизъюнктивных членов, а длина дизъюнктивного члена - суть количество конъюнктивных членов в нём. Верно?)
Напомните, плиз, непросвещённому, как находить минимальную ДНФ по заданной... :crazy:
... Ну или как записать минимальную ДНФ, соответствующую булевой функции N переменных, если известны все N-ки, на которых функция равна 1?
Заранее благодарю.

Waleri58

Есть ДНФ.
Правильно ли я понимаю, что минимальная ДНФ - это равносильная ей ДНФ минимальной длины?
(При этом под длиной ДНФ понимается сумма длин её дизъюнктивных членов, а длина дизъюнктивного члена - суть количество конъюнктивных членов в нём. Верно?)
Напомните, плиз, непросвещённому, как находить минимальную ДНФ по заданной...
определение правильное.
находить можно в лоб. брать слагаемые, у которых все множители одинаковы за исключением одного, который в одном случае берётся с отрицанием, а в другом - без. вместо двух таких слагаемых можно записать одно, в котором нет этого самого множителя.
так итеративно можно получить МДНФ
есть ещё какой-то метод по таблице это делать, но я не помню уже, какой :)

Waleri58

сначала полную записываешь просто ДНФ.
для каждого значения 1 функции, берёшь соответствующую n-ку. строишь слагаемое ДНФ.
для каждого нуля в этой n-ke берёшь соответствующую переменную с отрицанием, а для каждой единицы - без отрицания. из их произведения строишь слагаемые, и складываешь их.
потом минимизируешь полученный ДНФ

forester_200

Папа_Славик, огромное спасибо!
Как записывать полную ДНФ для функции и как "сливать" дизъюнктивные члены, отличные в одной позиции, я помню.
Немного переформулирую вопросы:
1) Верно ли, что после пошагового "слияния" дизъюнктивных членов, отличных в одной позиции (причём неважно, в каком порядке мы это будем делать! всегда в конечном итоге будет получаться минимальная ДНФ?
2) Как выглядит метод с помощью таблиц (даже, если не ошибаюсь, с помощью N-мерных кубов)?

Waleri58

честно сказать, я всё это порядком забыл :)
вот боюсь, всё-таки, что сливанием можно создать такую ситуацию, когда из ветвления уменьшения ДНФ можно выбрать неверную ветвь.

forester_200

вот боюсь, всё-таки, что сливанием можно создать такую ситуацию, когда из ветвления уменьшения ДНФ можно выбрать неверную ветвь.
вот и у меня такие же тревожные мысли
потому и хоцца узнать табличную методу
:confused:

Waleri58

а в табличном методе там вроде так делалось.
сначала нужно записать все значения переменных для каждой единицы.
так например:
0110 , потом уничтожать, если в смежных клетках попадается 0 и 1. так постепенно объединять ячейки таблицы...
не помню большего :(

iri3955

1) Верно ли, что после пошагового "слияния" дизъюнктивных членов, отличных в одной позиции (причём неважно, в каком порядке мы это будем делать! всегда в конечном итоге будет получаться минимальная ДНФ?
Нет, например:
010
110
100
101
111
Это единицы. Токгда слкеив первую пару получим
*10
100
101
111
Далее
*10
10*
111
Но формула
010
1**
Короче

Lokomotiv59

Можно составить оптимизационную задачу линейного программирования,
могу написать подробнее, если интересно.
А вообще это NP-полная задача, по-моему ;)

forester_200

Спасибо. Полезная информация.

forester_200

Большое спасибо, думаю, не стОит.
Мне бы попримитивнее алгоритм, чтобы товарищу объяснить - и желательно так, как ему эту тему рассказывали (а именно, через таблицы или кубы...)

romanenkoroman1

ботаем по ключевому слову "алгоритм Квайна-МакКласки"

forester_200

Большое спасибо!
Кажется, это то, что нужно! :cool:

resident

да
сначала ДНФ квайна, а потом минимальная днф.

forester_200

Учебник Яблонского - рулит!
Вот она - панацея!
Алилуйя!
Оставить комментарий
Имя или ник:
Комментарий: