Использование бинарных решающих диаграммдля решения логических задач
Автор: undefined undefined • Май 25, 2024 • Курсовая работа • 2,157 Слов (9 Страниц) • 89 Просмотры
Санкт-Петербургский политехнический университет Петра Великого
Институт компьютерных наук и кибербезопасности Высшая школа программной инженерии
[pic 1]
КУРСОВАЯ РАБОТА
Использование бинарных решающих диаграммдля решения логических задач
по дисциплине «Математическая логика»
Выполнил
студент гр. 5130904/10105 Савицкий Д. Ю.
Руководитель Юсупова О. А.
« » 2023 г.
Санкт-Петербург
2023
Оглавление Введение 3
Постановка задачи(без склейки) 4
Решение задачи(без склейки) 6
Ограничения типа 1: 6
Ограничения типа 2: 6
Ограничения типа 3: 6
Ограничение типа 4: 1. Если у объекта свойство 2 имеет значение 0, то
соседний объект имеет свойство 1 со значением 8 7
Доп. ограничения типа 1: 7
Интерпретация задачи(без склейки) на естественномязыке 8
Постановка задачи(со склейкой) 11
Решение задачи(со склейкой) 11
Ограничение типа 1 11
Ограничение типа 2 11
Ограничение типа 3 12
Ограничение типа 4 12
Доп. ограничения типа 1: 12
Доп. ограничения типа 4: 12
Интерпретация задачи(со склейкой) на естественномязыке 14
Заключение 15
Список литературы 16
Введение
В 1986 г. Randel Bryant предложил новую очень эффективную форму представления БФ, которую назвал бинарной решающей диаграммой – Binary Decision Diagrams (BDD) [1].
Бинарные диаграммы решений используются как компактная форма представления булевой функции, так как при увеличении количества переменных, количество решений растет экспоненциально, в то же время представление в форме BDD многих используемых на практике булевых функций растет полиномиально или даже линейно [2].
Курсовая работа построена на основе задачи Эйнштейна параметризацией условия.
Для реализации бинарных диаграмм в нашем решении задачи мы воспользовались свободно распространяющейся библиотекой BuDDy, написанной на языке программирования C++ [3].
Постановка задачи(без склейки)
Имеется N = 9 объектов и каждый элемент имеет позицию в матрице 3 на 3, согласно рисунку 1:
0 | 1 | 2 |
3 | 4 | 5 |
6 | 7 | 8 |
- Матрица 3 на 3
Каждый из объектов наделен M=4 свойствами, принимающими N значений. Для получения решения, согласно варианту, требуется задать:
- 6 ограничений типа 1:
Ограничения вида «Норвежец живет в первом доме» устанавливает, что свойство kk1 конкретного объекта ii1 имеет значение jj1:
𝐹𝐹 ∶= 𝐹𝐹 ^ 𝑝𝑝(𝑘𝑘1, 𝑖𝑖1, 𝑗𝑗1)
- 8 ограничения типа 2:
Ограничение вида «Англичанин живет в красном доме» устанавливает соответствие между двумя свойствами какого- либо объекта:
𝐹𝐹 ∶= 𝐹𝐹 ^ (𝑝𝑝(𝑘𝑘1, 𝑖𝑖1, 𝑗𝑗1) ↔ 𝑝𝑝(𝑘𝑘2, 𝑖𝑖, 𝑗𝑗2)), для всех 𝑖𝑖 от 0 до 𝑁 − 2
- 5 ограничений типа 3:
Ограничение расположения объектов – расположение «слева» («справа»). Это ограничения типа объект, у которого свойство k1 имеет значение j1, расположен слева от объекта, у которого свойство k2 имеет значение j2 («Зеленый дом находится слева от белого»)
...