Минимизиция булевых функций

[kwirk]

Я не спорю, могла и напутать, а хотя-бы образцов решений типовых задач ни у кого нет?

webfile.ru/2421302

Здесь более наглядно задачи

[kwirk]

Неужели ни у кого нет примерных задач хотя-бы? очень нужно

[Brukvalub]

См. http://www.dvo.sut.ru/libr/himath/w163rabk/5.htm
http://litevv.narod.ru/lekcii/diskret/5.html
http://vuz.exponenta.ru/PDF/book/kv.pdf

[rar]

Помогите, пожалуйста, разобраться в тот как надо находить минимальные ДНФ и ядровые ДНФ.
Допустим, у меня функция заданная вектором $\tilde f=10101101$. С помощью булева куба я нашел сокращенную ДНФ этой функции: $\bar x_1\bar x_3\vee \bar x_2\bar x_3\vee x_1\bar x_2\vee x_1 x_3$. Вот никак в голову не могу взять, как находить минимальные и ядровые ДНФ данной функции. Помогите разобраться. Или ссылки привести на источники, где это доходчиво объясняется.

[GAA]

Я так понял условие упражнения: функция принимает значения 1 на наборах c номерами 0, 2, 4, 5, 7.
Тогда у меня получается другой результат при минимизации на кубе --- "более минимальный".

По поводу минимальных ДНФ посмотрите ссылки, приведенные Выше участником Brukvalub.

// 8.05.09 близкие темы соединены. / GAA

[luitzen]

GAA писал(а):

Тогда у меня получается другой результат при минимизации на кубе --- "более минимальный".

Ну, сокращённая ДНФ не обязана быть минимальной…

rar писал(а):

Или ссылки привести на источники, где это доходчиво объясняется.

Из «ссылок на источники» посоветовал бы Яблонского, наверное.

[rar]

Я все эти материалы перерыл - так и не понял как найти ядровую и все минимальные ДНФ по булеву кубу. Ну не могу понять!

Добавлено спустя 38 минут 14 секунд:

Мне надо по булеву кубу найти минимальные и ядровые ДНФ.

[GAA]

1. По поводу минимальных ДНФ по кубу. Нарисуйте куб и нанесите на него точки — пометьте вершины. В Вашем случае нет граней со всеми помеченными вершинами, но точки можно «покрыть» ребрами. Два определенных ребра войдут в ответ обязательно. А вот точку $x_1\bar x_2 \bar x_3$ можно покрыть ребрами двумя способами. Т.обр. в ответе будет две минимальных ДНФ. Приведите, пожалуйста, эти ДНФ.

Добавлено спустя 8 минут 31 секунду:

2. По поводу ядровой см. приведенную Brukvalubом ссылку .

[rar]

$D_{min}=\bar x_1\bar x_3 \vee \bar x_2 \bar x_3$ и вторая $D_{min}=x_1\bar x_2 \vee x_1 x_3$. Правильно?

[GAA]

rar писал(а):

$D_{min}=\bar x_1\bar x_3 \vee \bar x_2 \bar x_3$ и вторая $D_{min}=x_1\bar x_2 \vee x_1 x_3$. Правильно?

Нет, в обоих вариантах неправильно. Ваши ребра в обоих случаях не покрывают все пять точек.

[rar]

Ну, а не могли бы мне расписать как в моем случае найти. Я видимо совсем не догоняю!

[GAA]

rar писал(а):

Ну, а не могли бы мне расписать как в моем случае найти. Я видимо совсем не догоняю!

1. Нарисовать куб.
2. Пометить вершины, на которых функция принимает значение 1 (их пять штук).
3. Соединить вершины ребрами (будет три ребра, например, ребро, соединяющее вершины $x_1 \bar x_2 \bar x_3$ и $x_1 \bar x_2 x_3$ есть $x_1 \bar x_2$).
4. Записать результат в виде дизъюнкции трех конъюнктов (т.е. трех элементарных конъюнкций).

При редактировании добавлена расшифровка: "т.е. трех элементарных конъюнкций."

[luitzen]

rar писал(а):

Мне надо по булеву кубу найти минимальные и ядровые ДНФ.

Употреблять множественное число в обоих случаях не очень корректно.

Ядровая ДНФ — она единственная. Собственно, фишка в том и состоит, что мы можем ещё чуть-чуть «сократить» сокращённую ДНФ, не начиная строить и перебирать тупиковые.

Что касается минимальных, то обычно тоже довольствуются тем, что отыскивают какую-нибудь одну. Дело в том, что могут иметься минимальные ДНФ, не являвшиеся тупиковыми, и «выцеплять» их сложно.

Вообще, элементарные геометрические соображения не могут много дать для построения минимальной ДНФ. В общем случае мы получим лишь сколько-то тупиковых ДНФ, которые нужно будет просто выписать и сравнить на предмет «длины».

~~~~

Объясню на примере, что такое ядровая ДНФ. Пусть сокращённая ДНФ некоторой формулы имеет такой вид, как указал rar: $\bar x_1\bar x_3\vee \bar x_2\bar x_3\vee x_1\bar x_2\vee x_1 x_3$. Каждому из дизъюнктов соответствует некоторая «грань» куба. В нашем случае все «грани» одномерные, т. е. рёбра.

Отыщем теперь в сокращённой ДНФ «важные» грани, то есть те, единственно благодаря которым оказались покрыты некоторые точки. К примеру, «важной» будет грань $x_1 x_3$: если бы не она, кто из граней сокращённой ДНФ покрыл бы вершину $7_2$? Другая «важная» грань сокращённой ДНФ — это $\bar x_1\bar x_3$. Установите самостоятельно вершину, которая оказалась покрыта лишь благодаря ей.

Других «важных» граней отыскать не удаётся. Собственно, объединение этих «важных» граней и называется ядром. В некоторых источниках и сами эти грани называются ядровыми .

При минимизации сокращённой ДНФ ядровые грани выкинуты из неё быть не могут. Это, конечно, плохо. Но раз уж так, можно попытаться выкинуть из сокращённой ДНФ те грани, которые покрываются объединением ядровых. ДНФ, получаемая из сокращённой выкидыванием всех («неважных») граней, покрываемых ядром, и называется ядровой.

В нашем случае сокращённая ДНФ не имеет «неважных» граней, покрываемых ядром. Значит, ядровая ДНФ совпадает с сокращённой.

[luitzen]

Похоже, в предыдущем сообщении я напутал и рассказал о том, что у Яблонского называется ДНФ Куайна.

А ядровая ДНФ — это просто объединение через дизъюнкцию ядровых граней. Следует иметь в виду, что ядровая ДНФ может быть неэквивалентна исходной формуле.

За это автору термина «ядровая ДНФ» (сам Яблонский его не употребляет) следовало бы объявить строгий выговор. Все прочие «ДНФ» (совершенные, сокращённые, ΣΤ, тупиковые, минимальные) эквивалентны своим исходным формулам, а вот ядровая, видите ли, нет. Как будто просто понятием ядра нельзя было обойтись.

Итак, ядровая ДНФ — некоторое вспомогательное понятие. Его можно использовать чтобы чуть-чуть сократить перебор, поскольку элементарные конъюнкции, в неё входящие, нельзя выбрасывать.

Яблонский же использует понятие ядра (что по сути то же самое) ещё и для того, чтобы попытаться продвинуться немного вперёд на пути однозначной минимизации ДНФ, и только потом начать перебор.

Спасибо GAA, указавшего мне на мою ошибку.

[rar]

luitzen писал(а):

Отыщем теперь в сокращённой ДНФ «важные» грани, то есть те, единственно благодаря которым оказались покрыты некоторые точки. К примеру, «важной» будет грань $x_1 x_3$: если бы не она, кто из граней сокращённой ДНФ покрыл бы вершину $7_2$?

Стоп. Что значит "покрыть"?

luitzen писал(а):

Других «важных» граней отыскать не удаётся. Собственно, объединение этих «важных» граней и называется ядром. В некоторых источниках и сами эти грани называются ядровыми

Хорошо. Объединение "важных" граней - это и есть ядро (ядровая ДНФ)?! Кстати, как правильно - ядро ДНФ или ядро функции?

Если так, то с ядром, пока, разобрались.

Тогда, как отыскать минимальную ДНФ? Алгоритм, если можно приведите, пожалуйста. В том стиле, в котором вы излагали выше.