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

8 0 •; • Идея Мак-Класки заключается в следующем. Если аредставить слагаемые с.д.н.ф. в виде их двоичных наборов, то эти наборы.можно разбить | по числу единиц в них на непересекающиеся группы. При этом в г-ую группу войдут все наборы, имеющие в своей записи точно / единиц. Попарное сравнение нужно производить только между элементами соседних по номеру групп. Так, вместо с.д.н.ф. вида х&у(& Iz vx&y&LZvx& ly& IzvlxtSi: ly& Iz можно рассмотреть наборы (1 10),(1 1 1), (1 О 0), (О О 0). При склеивании слагаемых в разряды, соответствующие исключенным переменным, пишется .знак тире. Такая модификация позволяет избежать громоздких записей. Рассмотрим метод Мак-Класки на примере. Пусть f(x,y,z,t) равна единице на наборах, записанных в строках с номерами О, 1, 2, 3, 4, 6, 7, 8, 9, 11 и 15. Найдем для этой функции сокращенную д.н.ф. и укажем, как найти минимальную и тупиковые д.н.ф. Разобьем наборы значений переменных х, у, z, и t, на которых f(x,y,z,t)=I, на группы. В результате получим следующие группы: - нулевую: (ООО 0); - первую: (ООО 1), (О О 1 0), (О 1 О 0), (1 0 0 0); - вторую; (0 0 1 1)Х0 1 1 0), (1 О О 1); - третью: (О 1 1 1), (1 О 1 1); - четвертую: (1 1 1 1). В общем случае некоторые из групп могут оказаться пустыми. Сравнивая элементы соседних групп, получаем следующие группы: - нулевую: (ООО -), (О О - 0), (О - О 0), (- 0 0 0); - первую: (О О - 1), (- О 1 0), (О О 1 -), (О - 1 0), (О 1 - 0), (1 О О -); - вторую: (О - 1 1),(- О О 1), (О 1 1 -), (1 О - 1); - третью: (-1 1 1), (1 - 1 1). Приведем еще раз сравнение элементов соседних групп и получим группы: - нулевую; (О О - -), (О - - 0), (- О О -); - первую: (- О - 1), (О - 1 -); - вторую; (--1 1). Для полученных групп склеивание не происходит, поэтом)' получаем результат - сокращенную форм}', которая имеет вид: ]х& ]yv]x& ]tv]y& Izvly&tvlx&zvz&t. Отметим, что если некоторые наборы не участвуют ни в каком склеивании, то они переходят без изменений на следующую итерацию. Дальнейшее нахождение минимальных и тупиковых д.н.ф, совпадает с описанным ранее. Можно только упростить записи в импликантной матрице, записывая вместо переменной число (символ) 1, а вместо отрицания переменной - число (символ) 0. Сокращенную д.н.ф. можно находить и другими способами, например, с помощью с.к.н.ф. Для этого выполняем следующие действия: - для заданной функции строим с.к.н.ф.;