2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3  След.
 
 
Сообщение26.11.2008, 09:03 


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

webfile.ru/2421302

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

 Профиль  
                  
 
 
Сообщение26.11.2008, 17:59 


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

 Профиль  
                  
 
 
Сообщение26.11.2008, 18:24 
Заслуженный участник
Аватара пользователя


01/03/06
13626
Москва
См. 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 


04/04/08
481
Москва
Помогите, пожалуйста, разобраться в тот как надо находить минимальные ДНФ и ядровые ДНФ.
Допустим, у меня функция заданная вектором $\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 
Заслуженный участник


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

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

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

 Профиль  
                  
 
 
Сообщение08.05.2009, 11:51 
Заслуженный участник


18/03/07
1068
GAA писал(а):
Тогда у меня получается другой результат при минимизации на кубе --- "более минимальный".

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

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

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

 Профиль  
                  
 
 
Сообщение08.05.2009, 13:33 


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

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

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

 Профиль  
                  
 
 
Сообщение08.05.2009, 14:09 
Заслуженный участник


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

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

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

 Профиль  
                  
 
 
Сообщение08.05.2009, 14:14 


04/04/08
481
Москва
$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 
Заслуженный участник


12/07/07
4522
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 


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

 Профиль  
                  
 
 
Сообщение08.05.2009, 15:10 
Заслуженный участник


12/07/07
4522
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 
Заслуженный участник


18/03/07
1068
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 
Заслуженный участник


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

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

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

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

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

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

 Профиль  
                  
 
 
Сообщение09.05.2009, 00:06 


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


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

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


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

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 33 ]  На страницу Пред.  1, 2, 3  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group