Индивидуальное домашнее задание Математическая логика и теория алгоритмов вар №10

Математическая логика и теория алгоритмов
Вариант 10. Томский политехнический университет
...

работа состоит из заданий!!

Таблично задана .

С данной функцией надо выполнить следующие действия:

а) представить данную функцию в виде СДНФ, СКНФ и СПНФ;
б) минимизировать её в СДНФ и в СКНФ склеиванием;
в) минимизировать в СДНФ методом Квайна;
г) проверить результаты минимизации с помощью диаграмм Эйлера-Венна.

СДНФ – это диъюнкция конъюнкций всех переменных, либо их отрицаний
Впишем в строки таблицы, где конъюнкции всех переменных, либо их отрицаний.
Переменная входит в соответсвтующую конъюнкцию без отрицания, если она в этой строке равна 1, если переменная в этой строке равна 0, она входит в конъюнкцию с отрицанием .
Затем выпишем дизъюнкцию всех получившихся конъюнкций.
Это и есть требуемая СДНФ.
.
Построение СКНФ.
СКНФ – это конъюнкция дизъюнкций всех переменных, либо их отрицаний.
Впишем в строки таблицы, где дизъюнкции всех переменных, либо их отрицаний.
Переменная входит в соответсвтующую дизъюнкцию без отрицания, если она в этой строке равна 0, если переменная в этой строке равна 1, она входит в конъюнкцию с отрицанием .
Затем выпишем конъюнкцию всех получившихся дизъюнкций.
Это и есть требуемая СКНФ.
.
Построение СПНФ.
СПНФ получается из СДНФ следующим образом.
Все отрицания переменных заменяются на , а все дизъюнкции заменяются сложением по модулю 2.
Получаем искомую СПНФ.
.
Минимизация в СДНФ склеиванием.

Выпишем СДНФ и проведём в ней все возможные склеивания.
.
В этой СДНФ можно склеить следующие импликанты: 1и2; 1и5; 2и3; 4и8; 6и8; 7и8.
После склеивания получаем:
.
Теперь проведём возможные поглощения.
Здесь можно провести операцию поглощения только со 2 и 6 импликантами.
Получаем: .
Дальнейшая минимизация получившейся сокращённой ДНФ склеиванием и поглощением невозможна.
Минимизация в СКНФ склеиванием.
Выпишем СКНФ и проведём в ней все возможные склеивания.
.
В этой СКНФ можно склеить следующие сомножители: 1и3; 2и3; 2и4; 2и6; 5и8; 7и8.
После склеивания получаем:
Поглощений провести не удаётся.
Дальнейшая минимизация получившейся сокращённой ДНФ склеиванием и поглощением невозможна.
Минимизация в СДНФ методом Квайна.
Выпишем СДНФ.
.
Выпишем получившуюся сокращённую ДНФ.
.
Составим для неё матрицу Квайна
1
+
+
2
+
+
3
+
+
4
+
+
5
+
+
6
+
+
7
+
В верхней строке матрицы записываем все импликанты, входящие в СДНФ.
В левом столбце матрицы записываем все импликанты, входящие в сокращённую ДНФ.
В клетке на пересечении строки и столбца ставим “+”, если импликанта из сокращённой ДНФ покрывает импликанту из СДНФ.
В противном случае не ставим ничего.
Теперь выбрасываем из этой матрицы максимальное число строк так, чтобы в каждом столбце
оставалось, по крайней мере, по одному «+».
Например, можно выбросить 1-ую и 5-тую строки, или 1-ую и 4-тую строки, или 3-тью и
5-тую строки.
Выбросим 1-ую и 5-тую строки.
Получим следующую матрицу Квайна.
2
+
+