ДИСКРЕТНАЯ МАТЕМАТИКА Домашняя работа. Пример. Решение предоставлено в 2009 уч. г. Eduard Shustrov (099443FAY) Alexander Sudnitson Tallinn University of Technology

Задание Найти минимальные ДНФ и КНФ методом Карт Карно. Найти минимальные ДНФ и КНФ методом МакКласки. Преобразовать МКНФ и МДНФ к соответствующим формулам, в которых встречаются только операции конъюнкции и отрицания. Представить данную функцию в базисе, т.е. «штрих Шеффера». Реализовать данную функцию с использованием только 2-х входового элемента И-НЕ. 2

Исходная функция x2 x4x2 x4 x1 x3x1 x x4x4 x2x2 x3x3 x1x1

Отмеченная карта Карно x4x4 x2x2 x3x3 x1x x4x4 x2x2 x3x3 x1x1 Это представление рекомендуется использовать, чтобы лучше понять связь между различными методами минимизации.

Метод карт Карно - МДНФ 5 x4x4 x2x2 x3x3 x1x1 x 1 x 4 x 2 x 3 x 3 x x4x4 x2x2 x3x3 x1x1 Карта Карно соответствующей полностью определенной Булевой функции

Метод карт Карно - МКНФ 6 x4x4 x2x2 x3x3 x1x1 (x 1 x 2 x 3 ) ( x 2 x 4 ) ( x 3 x 4 ) x4x4 x2x2 x3x3 x1x1

Метод Мак-Класки – МДНФ – этап I(1) 7

Метод Мак-Класки – МДНФ – этап I(2) 8

Метод Мак-Класки – МДНФ – этап II 9 Построение импликантной матрицы и решение задачи покрытия. Здесь имеем 2 обязательных импликанта, а третий простой импликант выбран исходя из «разумных» рассуждений.

Метод Мак-Класки – МДНФ (9/11/13/15) 00 (0/1/8/9) 11 (3/7/11/15). Таким образом все «единичные точки» покрываются тремя максимальными интервалами: Соответствующая МДНФ будет: Следует обратить внимание на то, что данное решение совпадает с найденным методом карт Карно.

Метод Мак-Класки – МKНФ – этап I(1) 11

12 Метод Мак-Класки – МKНФ – этап I(2)

Метод Мак-Класки – МKНФ – этап II(1) 13

Метод Мак-Класки – МKНФ – этап II(2) 14 Следует обратить внимание на то, что здесь мы имем два раноценных решения. Одно из них совпадает с рещеннием найденным ранее методом карт Карно. Тем не менее мы должны убедиться, что и второе решение может быть получено методом карт Карно (см. след. слайд).

Получение альтернативного решения 15 x4x4 x2x2 x3x3 x1x x4x4 x2x2 x3x3 x1x1 Здесь мы доопределили функцию на наборе аргументов « 1, 0, 0 » (клетка 8) до 0.

Преобразование к базису &, ~ 16 Преобразование МДНФ: Преобразование МКНФ:

Преобразование к базису 17

18 Представление (реализация) схемой В интересах оптимальности за исходную лучше взять МДНФ.

Верификация методом истинностных таблиц 19