Реализация булевых функций в виде графов
Автор: Sovetov • Октябрь 17, 2022 • Лабораторная работа • 404 Слов (2 Страниц) • 112 Просмотры
ЛАБОРАТОРНАЯ РАБОТА №3:
“Реализация булевых функций в виде графов”
Выполнил:
студент группы ПР-20.101
Николаев Д.Н.
Проверил: Авдеев Т.Д.
2022
Дана функция с тремя переменными: [pic 1]
Суперпозиция:
[pic 2] | [pic 3] |
[pic 4] | [pic 5] |
[pic 6] | [pic 7] |
[pic 8] |
Таблица истинности:
№ | [pic 9] | [pic 10] | [pic 11] | [pic 12] | [pic 13] | [pic 14] | [pic 15] | [pic 16] | [pic 17] | [pic 18] |
0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 |
1 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 |
2 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 |
3 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 1 |
4 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 1 |
5 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 1 |
6 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 |
7 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 |
51 > 30 => Составим СКНФ - Совершенная конъюнктивная нормальная форма (конъюнкция дизъюнктов)
[pic 19]
[pic 20]
[pic 21]
[pic 22][pic 23]
Проверим полученную функцию на эквивалентность
N | x1 | x2 | x3 | U1 | U2 | U3 | U4 | U5 | U6 | U7 | U8 | U9 | U10 |
0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 |
2 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
3 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
4 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
5 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
6 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 0 |
7 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 0 |
[pic 24]
[pic 25]
[pic 26]
[pic 27]
[pic 28]
[pic 29]
[pic 30]
[pic 31]
[pic 32]
[pic 33]
Замечаем, что таблица истинности полученной СКНФ совпадает с таблицей истинности . Значит, СДНФ эквивалентна [pic 34][pic 35]
Полином Жегалкина
[pic 36]
n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
cn | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
=[pic 37]
...