2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу Пред.  1, 2, 3  След.
 
 
Сообщение26.11.2008, 09:03 
Я не спорю, могла и напутать, а хотя-бы образцов решений типовых задач ни у кого нет?

webfile.ru/2421302

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

 
 
 
 
Сообщение26.11.2008, 17:59 
Неужели ни у кого нет примерных задач хотя-бы? очень нужно

 
 
 
 
Сообщение26.11.2008, 18:24 
Аватара пользователя
См. 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

 
 
 
 
Сообщение07.05.2009, 22:51 
Помогите, пожалуйста, разобраться в тот как надо находить минимальные ДНФ и ядровые ДНФ.
Допустим, у меня функция заданная вектором $\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$. Вот никак в голову не могу взять, как находить минимальные и ядровые ДНФ данной функции. Помогите разобраться. Или ссылки привести на источники, где это доходчиво объясняется.

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

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

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

 
 
 
 
Сообщение08.05.2009, 11:51 
GAA писал(а):
Тогда у меня получается другой результат при минимизации на кубе --- "более минимальный".

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

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

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

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

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

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

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

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

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

 
 
 
 
Сообщение08.05.2009, 14:14 
$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$. Правильно?

 
 
 
 
Сообщение08.05.2009, 14:25 
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$. Правильно?
Нет, в обоих вариантах неправильно. Ваши ребра в обоих случаях не покрывают все пять точек.

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

 
 
 
 
Сообщение08.05.2009, 15:10 
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. Записать результат в виде дизъюнкции трех конъюнктов (т.е. трех элементарных конъюнкций).

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

 
 
 
 
Сообщение08.05.2009, 15:15 
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$. Установите самостоятельно вершину, которая оказалась покрыта лишь благодаря ей.

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

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

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

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

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

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

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

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

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

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


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

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


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

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

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

 
 
 [ Сообщений: 33 ]  На страницу Пред.  1, 2, 3  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group