Дискретная математика

79 Если некоторое слагаемое не участвует в процедуре склеивания, то его переносим без изменения в столбец результатов рассматриваемой таблицы. Для результатов, полученных в процессе операций склеивания (они записаны во втором столбце), строим аналогичную таблицу. Для этой таблицы вертикальными входами являются результаты склеивания, полученные в первой таблице. Далее осуществляем процедуру склеивания в новой таблице, затем строим следующую таблицу и так повторяем до тех пор, пока происходит склеивание. Если склеивание более невозможно, то результат, полученный во втором столбце последней таблицы, и даёт простые импликанты и, следовательно, сокращенную д.н.ф, Для рассматриваемого примера уже после первой таблицы не происходит склеивание, поэтому сокращенной д.н.ф, является: x&zvx&y vly&zvlx& lyvlx& lzvy& Iz. Слагаемые сокращенной д.н.ф. являются простыми импликантами. Теперь строим импликантную матрицу. Построим таблицу, вертикальными входами которой являются конституенты единицы исходной функции, а горизонтальными входами - полученные простые импликанты. Для каждой импликанты найдем конституенты единицы, собственной частью которых является данная импликанта. Например, импликанта x&z содержится в конституентах x&y&z и х&1 y&z (и поглощает эти конституенты), имликанта ly&z содержится в конституентах х& ly&z и 1х& & 1 y&z и т.д. Клетки импликантной матрицы, образованные пересечением строк с импликантами и столбцов, с содержащими их конституентами, отметим каким-то символом, например, символом «*». Для' того, чтобы получить минимальную д.н.ф. заданной функции, достаточно найти импликанты, которые совместно накрывают звездочками (*) все столбцы и в совокупности содержат наименьшее возможное число вхождений переменных (с отрицаниями или без отрицаний). Для рассматриваемого примера первая построенная таблица является и импликантной матрицей. Из этой матрицы следует, что в минимальную д.н.ф. входят, например, x&z, 1 х&1 у vi у&1 z, ибо они в совокупности накрывают все столбцы символами «*». Форма x&yvl х&1 zv]y&z тоже является минимальной д.н.ф. рассматриваемой функции. Обе эти д.н.ф., очевидно, являются и тупиковыми д.н.ф. рассмафиваемой функции. Если же взять импликанты x&z, 1х& 1у, 1х& Iz, х&у, то среди них не оказывается липшей, следовательно, получим новую тупиковую д.н.ф.: x&zvlx& lyvlx& Izvx&y, которая не является минимальной д.н.ф. Можно построить и другие тупиковые д.н.ф. рассматриваемой функции. Для уменьшения выкладок на этапе получения сокращенной д.н.ф. можно применить метод Мак-Класки. Этот метод является некоторой модификацией метода Квайна. В методе Квайна необходимо проводить попарное сравнение всех слагаемых с.д.н.ф. Число таких сравнений с ростом слагаемых быстро растет.