3.Тупиковые нормальные дизъюнктивные формы. Метод импликантных матриц
Тупиковая нормальная диз.форма-диз.всехее простых импликант, ни одну из которых удалить нельзя.
Метод импликантных матриц:
Составляется импликантная матрица: в заголовочную строку зап-ся (А(перевернутое)) канетиту энти α.В столбец -(А(перевернутое)) простые импликанты.
(строка (А(перевернутое)) члены сов норм диз.формы, столбец - (А(перевернутое)) члены сокр.)
Если i-простая импликанта поглощает j- константу, то на ux пересечении ставится крестик.
Тупиковая норм.диз.форма-сост.из тех простых импликант, что соотв.строки в табл. Имеют крестики во всех столбцах и ни одну сторону при этомудалить нельзя(что бы крестики остались во всех (А(перевернутое)) столбцах)
Ft1=x(черта с веху) v_xy_v_
4. Минимизация в классе нормальных конъюнктивных форм (мнкф)
Приведение формулы к МНКФ:
привести к совершенной НКФ (нормальной конъюнктивной форме)
привести к сокращенной НКФ
для этого надо
выполнить все операции неполного
склеивания (
)
и поглощения (
)
получение тупиковой НКФ (метод импликантных матриц)
в заголовочную строку записываются все члены НКФ (т.е. конституенты нуля)
в заголовочный столбец – все члены сокращенной НКФ
если i-ый член сокращенной НКФ поглощает j-ую конституенту нуля, то на пересечении ставим крестик
тупиковая форма состоит из тех строк, ни одну из которых исключить нельзя, так чтобы крестики были во всех столбцах
МНКФ является тупиковой НКФ получение МНКФ сводится к выбору min среди тупиковых НКФ.
5. Основные понятия комбинаторики: выборки, перестановки и сочетания.
Комбинаторика – наука, связанная с размещение объектов по заранее определенным правилами подсчетам числа таких размещений.
Основатель – Лейбниц.
Существуют задачи на существование и задачи на подсчет мест существования. Перечислительная задача более общая, чем задача существования. Если правила сложны, то перечислительная задача практически невыполнима.
Выборки, перестановки, сочетания
Пусть есть одно множество, состоящее из n элементов (n-множество). Из этого n-множества можно выбрать некоторое число элементов. Результатом является выборка, содержащая k элементов.
Выборки могут быть разными:
упорядоченные / неупорядоченные
с / без возвращений (с / без повторений)
с / без учета порядка
Порядок элементов можно принимать или не принимать во внимание.
Выборка с учетом порядка – перестановка.
Выборка без учета порядка – сочетание.
В выборке элементы могут повторяться или нет.
Выборка с повторением – выборка с возвращением.
О выборке без повторений говорят как о множестве.
6.Правила суммы и произведения в комбинаторике.
1.Правило суммы: если обьект А можно выбрать n-способами, В-m-способами, то обьект либо А либо В можно выбрать n+m способами. Надо следить чтобы никакой способ выбора обьекта А влек за собой выбор обьекта В.
2.Правило Произведения: если обьект А можно выбрать n-способами, и после такого выбора обьект В можно выбрать m-способами, то пары (А,В) можно выбрать
n*m-способами.
Если А можно выбрать n-способами, после такого выбора В можно выбрать m-способами,
после выбора такой пары (А,В),
С можно выбрать, выбран k –способами, то (А,В,С)-n*m*k
способами.