Редактирование: Основы Кибернетики, Алгоритмы решения задач/Задачи на ДНФ
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 356: | Строка 356: | ||
Далее, определим ядровые точки, то есть те α<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> |