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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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