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

[GAA]

1. По ссылке, приведенной Brukvalubом, на 10.05.09, находится html-версия Конспект лекций «Элементы алгебры логики» 2007–2008 ORSOT (на странице дана ссылка на pdf-файл этих лекций).

Понятие ядровой ФАЛ можно найти в книге
Ложкин С.А. «Лекции по основам кибернетики» (учебное пособие для студентов) — М.: Издательский отдел ф-та ВМиК МГУ, 2004.(pdf).

2. Если в задании есть пункт построения ядровой ФАЛ, то МДНФ надо строить с использованием ядровой ДНФ.
Давайте Вы, rar, укажите, что непонятно в примере по ссылке, указанной Brukvalubом. Для удобства, я воспроизведу этот пример здесь.

Цитата:

Пример:
\begin{array}{| c | c | c | c |} \hline x_1 & x_2 & x_3 & f \\ \hline 0 & 0 & 0 & 0 \\ \hline 0 & 0 & 1 & 1 \\ \hline 0 & 1 & 0 & 0 \\ \hline 0 & 1 & 1 & 1 \\ \hline 1 & 0 & 0 & 1 \\ \hline 1 & 0 & 1 & 0 \\ \hline 1 & 1 & 0 & 1 \\ \hline 1 & 1 & 1 &1 \\ \hline \end{array}
Выделение всех возможных интервалов.
1. Для булева куба размерности 3 интервалом ранга 1 могут быть 4 вершины, лежащие в одной грани.
2. Ранга 2 – любые 2 вершины, соединенные ребром.
3. Ранга 3 – любая отдельная вершина.
В данном примере
1. Нет
2. $I_1 = \{001, 011\} \leftrightarrow \pi_1 = \bar x_1 x_3$; $I_2 = \{011, 111\} \leftrightarrow \pi_2 = x_2 x_3$; $I_3 = \{111, 110\} \leftrightarrow \pi_3 = x_1 x_2$; $I_4 = \{110, 100\} \leftrightarrow \pi_4 = x_1 \bar x_3$.
Ядровые интервалы $I_1$ и $I_4$.
Сокращенная ДНФ = $\pi_1 \vee \pi_2 \vee \pi_3 \vee \pi_4$.
[Ядровая ДНФ $D= \pi_1 \vee \pi_4 = \bar x_1 x_3 \vee x_1 \bar x_3$.]
Тупиковые:
$D_1 = \pi_1 \vee \pi_4 \vee \pi_2$ ($N_f = I_1 \cup I_4 \cup I_2$);
$D_2 = \pi_1 \vee \pi_4 \vee \pi_3$ ($N_f = I_1 \cup I_4 \cup I_3$).
Сосчитаем ранги тупиковых ДНФ
R1 = 6
R2 = 6
Минимальными ДНФ будут $D_1$ и $D_2$.

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

В данной цитате, ребра ($I$) задаются координатами вершин (через запятую), т.е. запись $I_1 = \{001, 011\}$ — означает ребро, соединяющее вершины с координатами $(001)$ и $(011)$. Элементарные конъюнкции ранга 2 обозначаются буквой $\pi$. Ребру соответствует элементарная конъюнкция ранга 2, и наоборот, элементарной конъюнкции ранга 2 соответствует некоторое ребро — это соответствие и обозначено символом $\leftrightarrow$.

[luitzen]

rar в сообщении #212175 писал(а):

В том стиле, в котором вы излагали выше.

:lol1:

ОК, пусть у нас есть сокращённая ДНФ, и наша задача — получить какую-нибудь минимальную.

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

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

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

~~~~

Давайте теперь рассмотрим на Вашем примере.

Сокращённая ДНФ — это $x_1 x_3\vee \bar x_1\bar x_3\vee x_1\bar x_2 \vee \bar x_2\bar x_3$. Ядро — это $x_1 x_3 \vee \bar x_1\bar x_3$. Значит, нужно рассмотреть всего четыре подмножества сокращённой ДНФ, что мы и сделаем.

1. $x_1 x_3 \vee \bar x_1\bar x_3$
   К сожалению, голым ядром покрыть все точки не удалось, и мы даже не будем считать длину этой «ядровой ДНФ».
2. $x_1 x_3\vee \bar x_1\bar x_3\vee x_1\bar x_2$
   Вот это уже лучше. Удалось покрыть все точки, и эта ДНФ является тупиковой: выкидывать $x_1\bar x_2$ мы пробовали, а выкидывать ядровые грани лучше и не пытаться. Запомним длину этой тупиковой ДНФ.
3. $x_1 x_3\vee \bar x_1\bar x_3\vee \bar x_2\bar x_3$
   Ещё одна тупиковая ДНФ. Запомним и её длину тоже.
4. $x_1 x_3\vee \bar x_1\bar x_3\vee x_1\bar x_2 \vee \bar x_2\bar x_3$
   Считать длину этой ДНФ неинтересно, поскольку она не тупиковая: можно ведь выкинуть из неё что-нибудь и получить формулы 2 или 3, длины которых меньше.

Итак, у нас есть две тупиковых ДНФ: 2 и 3. Длины их, в соответствии с принятым способом подсчёта, одинаковы. Значит, они обе минимальные. Но мне почему-то больше нравится 2 .

[rar]

Я вот до сих пор не понял. Попробуйте мне объяснить.

В чем состоит смысл ядровой ДНФ? Зачем она нужна.

И как же все-таки определять ядровые интервала. По какому признаку??? Вот этого вы мне не объяснили. Почему в выше приведенном примере только два ядровых интервала, а не один и не три?

Не понятно по какому признаку выбираются тупиковые ДНФ. Вот объясните эти признаки доходчиво!