Редактирование: Основы Кибернетики, Алгоритмы решения задач/Задачи на ДНФ
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 60: | Строка 60: | ||
* (− 0 1) → <span style="border-top:solid 1px">''x''</span><sub>2</sub>''x''<sub>3</sub> | * (− 0 1) → <span style="border-top:solid 1px">''x''</span><sub>2</sub>''x''<sub>3</sub> | ||
- | В | + | В реузльтате получим сокращённую ДНФ ''x''<sub>1</sub> ∨ ''x''<sub>2</sub><span style="border-top:solid 1px">''x''</span><sub>3</sub> ∨ <span style="border-top:solid 1px">''x''</span><sub>2</sub>''x''<sub>3</sub> |
==== Метод Блейка ==== | ==== Метод Блейка ==== | ||
Строка 162: | Строка 162: | ||
нужно обьединить в прямоугольник единицу (с координатами [1;1]) с единицей ,у которой координаты [4;1] | нужно обьединить в прямоугольник единицу (с координатами [1;1]) с единицей ,у которой координаты [4;1] | ||
- | нужно обьединить в прямоугольник единицу (с координатами [4;1]) с единицей ,у которой координаты [4;4] | ||
прокомментировал getbraine e-mail v000du@gmail.com | прокомментировал getbraine e-mail v000du@gmail.com | ||
Строка 171: | Строка 170: | ||
xK v (not x)K = xK v (not x)K v K | xK v (not x)K = xK v (not x)K v K | ||
2)пока возможно поглощение | 2)пока возможно поглощение | ||
- | 3) i++; if (i<=n) goto | + | 3) i++; if (i<=n) goto 0 |
=== Построение ДНФ Квайна === | === Построение ДНФ Квайна === | ||
Строка 356: | Строка 355: | ||
Далее, определим ядровые точки, то есть те α<sub>i</sub>, у которых в столбце только одна единица. Таковыми являются α<sub>1</sub>, α<sub>3</sub>, α<sub>5</sub>, α<sub>7</sub>, α<sub>9</sub>, α<sub>10</sub>. Соответственно, ядровыми гранями являются те грани, которые соответствуют конъюнкциям, которым принадлежат ядровые вершины (смотрим на строки, в которых хотя бы для одного из выбранных столбцов α<sub>i</sub> стоит единица), то есть K<sub>1</sub>, K<sub>2</sub>, K<sub>4</sub>, K<sub>5</sub>, K<sub>7</sub>. Дизъюнкция этих конъюнкций есть пересечение тупиковых. | Далее, определим ядровые точки, то есть те α<sub>i</sub>, у которых в столбце только одна единица. Таковыми являются α<sub>1</sub>, α<sub>3</sub>, α<sub>5</sub>, α<sub>7</sub>, α<sub>9</sub>, α<sub>10</sub>. Соответственно, ядровыми гранями являются те грани, которые соответствуют конъюнкциям, которым принадлежат ядровые вершины (смотрим на строки, в которых хотя бы для одного из выбранных столбцов α<sub>i</sub> стоит единица), то есть K<sub>1</sub>, K<sub>2</sub>, K<sub>4</sub>, K<sub>5</sub>, K<sub>7</sub>. Дизъюнкция этих конъюнкций есть пересечение тупиковых. | ||
- | Для нахождения всех тупиковых ДНФ построим КНФ, элементарныё дизъюнкции которой будут состоять из БП, соответствующих тем конъюнкциям, в которые входит рассматриваемая точка α<sub>i</sub> (то есть, всего дизъюнкций столько же, сколько есть точек, где | + | Для нахождения всех тупиковых ДНФ построим КНФ, элементарныё дизъюнкции которой будут состоять из БП, соответствующих тем конъюнкциям, в которые входит рассматриваемая точка α<sub>i</sub> (то есть, всего дизъюнкций столько же, сколько есть точек, где фугкция принимает единичное значение, причём первая дизъюнкция будет содержать те БП, которые соответствуют тем ЭК, которым принадлежит α<sub>1</sub> (в данном примере это K<sub>1</sub>), вторая — те, которые соответствуют ЭК, которым принадлежит α<sub>2</sub> (K<sub>1</sub>, K<sub>2</sub>, K<sub>3</sub>), и так далее): |
K<sub>1</sub> & (K<sub>1</sub> ∨ K<sub>2</sub> ∨ K<sub>3</sub>) & K<sub>2</sub> & (K<sub>3</sub> ∨ K<sub>6</sub>) & K<sub>4</sub> & (K<sub>4</sub> ∨ K<sub>5</sub> ∨ K<sub>7</sub>) & K<sub>5</sub> & (K<sub>6</sub> ∨ K<sub>7</sub>) & K<sub>7</sub> & K<sub>7</sub> | K<sub>1</sub> & (K<sub>1</sub> ∨ K<sub>2</sub> ∨ K<sub>3</sub>) & K<sub>2</sub> & (K<sub>3</sub> ∨ K<sub>6</sub>) & K<sub>4</sub> & (K<sub>4</sub> ∨ K<sub>5</sub> ∨ K<sub>7</sub>) & K<sub>5</sub> & (K<sub>6</sub> ∨ K<sub>7</sub>) & K<sub>7</sub> & K<sub>7</sub> |