rar писал(а):
Мне надо по булеву кубу найти минимальные и ядровые ДНФ.
Употреблять множественное число в обоих случаях не очень корректно.
Ядровая ДНФ — она единственная. Собственно, фишка в том и состоит, что мы можем ещё чуть-чуть «сократить» сокращённую ДНФ, не начиная строить и перебирать тупиковые.
Что касается минимальных, то обычно тоже довольствуются тем, что отыскивают какую-нибудь одну. Дело в том, что могут иметься минимальные ДНФ, не являвшиеся тупиковыми, и «выцеплять» их сложно.
Вообще, элементарные геометрические соображения не могут много дать для построения минимальной ДНФ. В общем случае мы получим лишь сколько-то тупиковых ДНФ, которые нужно будет просто выписать и сравнить на предмет «длины».
~~~~
Объясню на примере, что такое ядровая ДНФ. Пусть сокращённая ДНФ некоторой формулы имеет такой вид, как указал
rar:
. Каждому из дизъюнктов соответствует некоторая «грань» куба. В нашем случае все «грани» одномерные, т. е. рёбра.
Отыщем теперь в сокращённой ДНФ «важные» грани, то есть те, единственно благодаря которым оказались покрыты некоторые точки. К примеру, «важной» будет грань
: если бы не она, кто из граней сокращённой ДНФ покрыл бы вершину
? Другая «важная» грань сокращённой ДНФ — это
. Установите самостоятельно вершину, которая оказалась покрыта лишь благодаря ей.
Других «важных» граней отыскать не удаётся. Собственно, объединение этих «важных» граней и называется ядром. В некоторых источниках и сами эти грани называются ядровыми
.
При минимизации сокращённой ДНФ ядровые грани выкинуты из неё быть не могут. Это, конечно, плохо. Но раз уж так, можно попытаться выкинуть из сокращённой ДНФ те грани, которые покрываются объединением ядровых. ДНФ, получаемая из сокращённой выкидыванием всех («неважных») граней, покрываемых ядром, и называется ядровой.
В нашем случае сокращённая ДНФ не имеет «неважных» граней, покрываемых ядром. Значит, ядровая ДНФ совпадает с сокращённой.