Использование бинарных решающих диаграмм для решения логических задач. Курсовик_Борисова. Курсовая работа использование бинарных решающих диаграмм для решения логических задач по дисциплине Математическая логика Выполнила студентка гр. 353090400104
 Скачать 300.49 Kb.
|
|
Санкт-Петербургский политехнический университет Петра Великого Институт компьютерных науки технологий Высшая школа программной инженерии Санкт-Петербург 2022 КУРСОВАЯ РАБОТА Использование бинарных решающих диаграмм для решения логических задач по дисциплине Математическая логика Выполнила студентка гр. 3530904/00104 Борисова Е. А. Руководитель Юсупова О. А. 2 Оглавление Введение Решение задачи Интерпретация на естественном языке Заключение Список литературы 10 3 Введение Многие задачи требуют большое количество хранимой информации. Для таких случаев очень удобно использовать BDD - для представления больших множеств и отношений. Бинарные решающие диаграммы (BDD) — это семантическое дерево без избыточностей, те. двоичный направленный граф с одной корневой вершиной [2]. Хорошие реализации BDD позволяют эффективно производить операции надмножествами. Для работы св среде Visual Studio будем использовать библиотеку BuDDy, исходные файлы которой укажем, как ресурсы [1]. Постановка задачи Наша задача является модифицированной задачей Эйнштейна. Пусть у нас имеется N=9 объектов, каждый из которых обладает M=4 свойствами. Они же могут принимать N различных значений. Каждый объект занимает ячейку на квадрате размером 3*3. Отношения между этими объектами задаются вариантом №4 из методички относительно центрального объекта 0 * * Это значит, что если мы рассмотрим последовательно все объекты, то получим следующие отношения 0 * 0 * * п * 0 * 0 * * п * 0 0 0 Однако, наша задача усложнена некоторым дополнительным условием, склейкой. Это означает, что по параметру, определяемому вариантом, условия соседства для некоторых объектов немного изменены. Для моего варианта склейка производится по правой- левой границе, поэтому у следующих объектов появятся дополнительные соседи 0 * * 0 * * п * * 0 * * п Кроме того, мой вариант включает обязательное кол-во ограничений 𝑛𝑛1, 𝑛𝑛2, 𝑛𝑛3, 𝑛𝑛4: 𝑛𝑛1 𝑛𝑛2𝑛𝑛3 𝑛𝑛4 6 8 3 4 4 Если формализовать типы ограничений по характерным фразам из условия решаемой задачи и сохранять их в функции F, то можно получить следующее 1. Ограничения вида Норвежец живет в первом доме устанавливает, что свойство 𝑘𝑘1 конкретного объекта 𝑖𝑖1 имеет значение 𝑗𝑗1: 𝐹𝐹: = 𝐹𝐹 ∧ 𝑝𝑝(𝑘𝑘1, 𝑖𝑖1, 𝑗𝑗1) 2. Ограничение вида Англичанин живет в красном доме устанавливает соответствие между двумя свойствами какого-либо объекта 𝐹𝐹: = 𝐹𝐹 ∧ (𝑝𝑝(𝑘𝑘1, 𝑖𝑖, 𝑗𝑗1) ↔ 𝑝𝑝(𝑘𝑘2, 𝑖𝑖, 𝑗𝑗2)), для всех 𝑖𝑖 от 0 до N-2 3. Ограничение расположения объектов – расположение слева (справа. Это ограничения типа объекту которого свойство k1 имеет значение j1, расположен слева от объекта, у которого свойство k2 имеет значение j2 (Зеленый дом находится слева от белого 𝐹𝐹: = 𝐹𝐹 ∧ (𝑝𝑝(𝑘𝑘1, 𝑖𝑖, 𝑗𝑗1) ↔ 𝑝𝑝(𝑘𝑘2, 𝑖𝑖 + 1, 𝑗𝑗2)), для всех 𝑖𝑖 от 0 до 𝑁𝑁 − 2 4. Ограничение расположения объектов – расположение рядом - дизъюнкция ограничений слева и справа. 𝐹𝐹: = 𝐹𝐹 ∧ ��𝑝𝑝(𝑘𝑘1, 𝑖𝑖, 𝑗𝑗1) ↔ 𝑝𝑝(𝑘𝑘2, 𝑖𝑖 + 1, 𝑗𝑗2)� ∨ �𝑝𝑝(𝑘𝑘2, 𝑖𝑖, 𝑗𝑗2) ↔ 𝑝𝑝(𝑘𝑘1, 𝑖𝑖 + 1, 𝑗𝑗1)��, для всех 𝑖𝑖 от 0 до 𝑁𝑁 − 2 По умолчанию в задаче Эйнштейна подразумеваются еще следующие ограничения 5. У двух различных объектов значения любого параметра(свойства) не совпадают 𝐹𝐹: = 𝐹𝐹 ∧ �𝑝𝑝(𝑘𝑘, 𝑖𝑖1, 𝑗𝑗) ↔ ¬𝑝𝑝(𝑘𝑘, 𝑖𝑖2, при 𝑖𝑖1 ≠ 𝑖𝑖2 6. Параметры принимают значения только из заданных множеств (значение свойств должно быть меньше N) [ 1 ]. Решение задачи Для решения такой задачи и ей подобных удобно использовать библиотеку BuDDy, реализация которой представлена на языке C++ [ 3 ]. Напишем программу, которая будет учитывать все необходимые ограничения и находить всевозможные решения данной задачи. Сначала решим нашу задачу в общем виде, а потом выполним ее интерпретацию. Зададим необходимое кол-во требуемых ограничений n1: 1. Свойство 0 объекта 0 равно 0 2. Свойство 2 объекта 1 равно 8 3. Свойство 3 объекта 2 равно 4 4. Свойство 1 объекта 4 равно 7 5. Свойство 2 объекта 6 равно 4 6. Свойство 3 объекта 8 равно 6 n2: 1. У некоторого объекта свойство 0 имеет значение 0 и свойство 1 имеет значение 0 2. У некоторого объекта свойство 0 имеет значение 8 и свойство 2 имеет значение 6 3. У некоторого объекта свойство 2 имеет значение 1 и свойство 3 имеет значение 2 4. У некоторого объекта свойство 2 имеет значение 0 и свойство 1 имеет значение 5 5. У некоторого объекта свойство 3 имеет значение 5 и свойство 0 имеет значение 4 6. У некоторого объекта свойство 2 имеет значение 3 и свойство 1 имеет значение 8 7. У некоторого объекта свойство 1 имеет значение 0 и свойство 3 имеет значение 0 8. У некоторого объекта свойство 2 имеет значение 2 и свойство 0 имеет значение 5 5 n3: 1. Объекту которого свойство 3 имеет значение 3 расположен слева снизу от объекта, у которого свойство 0 имеет значение 4 2. Объекту которого свойство 2 имеет значение 2 расположен справа снизу от объекта, у которого свойство 1 имеет значение 3 3. Объекту которого свойство 2 имеет значение 0 расположен справа снизу от объекта, у которого свойство 0 имеет значение 2 Без склейки Объекту которого свойство 0 имеет значение 7 расположен справа снизу от объекта, у которого свойство 3 имеет значение 8) n4: 1. Объекту которого свойство 0 имеет значение 6 расположен рядом с объектом, у которого свойство 2 имеет значение 2 Без склейки Объекту которого свойство 1 имеет значение 4 расположен рядом с объектом, у которого свойство 2 имеет значение 5) 2. Объекту которого свойство 2 имеет значение 1 расположен рядом с объектом, у которого свойство 3 имеет значение 8 3. Объекту которого свойство 1 имеет значение 1 расположен рядом с объектом, у которого свойство 3 имеет значение 1 4. Объекту которого свойство 2 имеет значение 2 расположен рядом с объектом, у которого свойство 2 имеет значение 7 Без склейки Объекту которого свойство 1 имеет значение 7 расположен рядом с объектом, у которого свойство 2 имеет значение 7) В результате мы получим 1080 решений (без склейки - 1248). Добавим некоторые дополнительные условия, чтобы кол-во наших рений было около 10–12. Дополнительные условия 1. Свойство 0 объекта 7 равно 7 2. Свойство 3 объекта 1 равно 1 3. У некоторого объекта свойство 0 имеет значение 3 и свойство 3 имеет значение 8 Без склейки Объекту которого свойство 0 имеет значение 3 расположен слева снизу от объекта, у которого свойство 0 имеет значение 1) 4. Без склейки Объекту которого свойство 0 имеет значение 7 расположен слева снизу от объекта, у которого свойство 3 имеет значение 7) Дополнительные условия были выбраны таким образом Так как в варианте присутствует больше всего условий, которые связывают между собой 2 свойства одного объекта, то самым выгодным вариантом будет привязать у большинства объектов одно свойство к номеру места. Объект 7 был выбран для первого условия, потому что количество неправильных перестановок сего участием было максимальным. Посчитано поиском строк в NotePad++ : Строки Совпадения (из 1080 решений) 0: 0 0 7 0 1080 1: 1 3 8 1 48 2: 2 8 3 4 720 3: 3 5 0 8 72 6 4: 4 7 5 5 576 5: 5 1 2 7 72 6: 6 6 4 3 60 7: 7 2 1 2 44 8: 8 4 6 6 168 Методом подбора стало ясно, что минимум решений будет при добавлении условия для 0 свойства. После добавления го условия решений стало 180. По той же схеме было выбрано второе условие Строки Совпадения (из 180 решений) 0: 0 0 7 0 180 1: 1 3 8 1 12 2: 2 8 3 4 120 3: 3 5 0 8 18 4: 4 7 5 5 96 5: 5 1 2 7 12 6: 6 6 4 3 20 7: 7 2 1 2 44 8: 8 4 6 6 28 После добавления го условия получено 24 решения Строки Совпадения (из 24 решений) 0: 0 0 7 0 24 1: 1 3 8 1 12 2: 2 8 3 4 24 3: 3 5 0 8 6 4: 4 7 5 5 24 5: 5 1 2 7 12 6: 6 6 4 3 8 7: 7 2 1 2 8 8: 8 4 6 6 8 Проанализировав ответы по 3му объекту можно заметить, что 1 и 2 свойство всегда одинаковы, в то время как 0 и 3 свойство присутствуют в различных комбинациях. Исходя из этого я решила добавить условие го типа. В результате программа выдаст следующие решения Со склейкой We have 6 solutions 0: 0 0 7 0 1: 1 3 8 1 2: 2 8 3 4 3: 3 5 0 8 4: 4 7 5 5 5: 5 1 2 7 6: 6 4 4 3 7: 7 2 1 2 8: 8 6 6 6 0: 0 0 7 0 1: 1 3 8 1 2: 2 8 3 4 3: 3 5 0 8 4: 4 7 5 5 5: 5 1 2 7 6: 6 4 4 3 7: 7 6 1 2 8: 8 2 6 6 0: 0 0 7 0 1: 1 3 8 1 2: 2 8 3 4 3: 3 5 0 8 4: 4 7 5 5 5: 5 1 2 7 6: 6 2 4 3 7: 7 4 1 2 8: 8 6 6 6 7 0: 0 0 7 0 1: 1 3 8 1 2: 2 8 3 4 3: 3 5 0 8 4: 4 7 5 5 5: 5 1 2 7 6: 6 2 4 3 7: 7 6 1 2 8: 8 4 6 6 0: 0 0 7 0 1: 1 3 8 1 2: 2 8 3 4 3: 3 5 0 8 4: 4 7 5 5 5: 5 1 2 7 6: 6 6 4 3 7: 7 4 1 2 8: 8 2 6 6 0: 0 0 7 0 1: 1 3 8 1 2: 2 8 3 4 3: 3 5 0 8 4: 4 7 5 5 5: 5 1 2 7 6: 6 6 4 3 7: 7 2 1 2 8: 8 4 6 6 Без склейки We have 8 solutions 0: 0 0 7 0 1: 1 3 8 1 2: 2 8 3 4 3: 3 5 0 8 4: 4 7 5 5 5: 5 1 2 7 6: 6 2 4 3 7: 7 6 1 2 8: 8 4 6 6 0: 0 0 7 0 1: 1 3 8 1 2: 2 8 3 4 3: 3 5 0 8 4: 4 7 5 5 5: 5 1 2 7 6: 6 6 4 3 7: 7 2 1 2 8: 8 4 6 6 0: 0 0 7 0 1: 1 3 8 1 2: 2 5 0 4 3: 3 8 3 8 4: 4 7 5 5 5: 5 1 2 7 6: 6 2 4 3 7: 7 6 1 2 8: 8 4 6 6 0: 0 0 7 0 1: 1 3 8 1 2: 2 5 0 4 3: 3 8 3 8 4: 4 7 5 5 5: 5 1 2 7 6: 6 6 4 3 7: 7 2 1 2 8: 8 4 6 6 0: 0 0 7 0 1: 1 3 8 1 2: 6 8 3 4 3: 3 5 0 8 4: 4 7 5 5 5: 5 1 2 7 6: 2 2 4 3 7: 7 6 1 2 8: 8 4 6 6 0: 0 0 7 0 1: 1 3 8 1 2: 6 8 3 4 3: 3 5 0 8 4: 4 7 5 5 5: 5 1 2 7 6: 2 6 4 3 7: 7 2 1 2 8: 8 4 6 6 0: 0 0 7 0 1: 1 3 8 1 2: 6 5 0 4 3: 3 8 3 8 4: 4 7 5 5 5: 5 1 2 7 6: 2 2 4 3 7: 7 6 1 2 8: 8 4 6 6 0: 0 0 7 0 1: 1 3 8 1 2: 6 5 0 4 3: 3 8 3 8 4: 4 7 5 5 5: 5 1 2 7 6: 2 6 4 3 7: 7 2 1 2 8: 8 4 6 6 Интерпретация на естественном языке Как-то раз, Пупа и Лупа решили устроиться работать в библиотеку, что естественно решили отметить компанией на рабочем месте, но как обычно все перепутали. Чтобы их не уволили, им срочно нужно расставить все 9 книги табличек с 9 разными авторами, жанрами и языками текста в нужном порядке. Так как читать они не умеют, они могут различать книги только по цвету обложки. На их счастье, у Пупы и Лупы есть друг с хорошей памятью, который примерно помнит расположение табличек и книг, который сразу бросается подругам на помощь. Однако библиотека непростая, а волшебная – для оптимального расположения книг (или запутывания Пупы и Лупы) у книг присутствует особая ментальная связь (а как же, книги тоже волшебные) – слева снизу и справа снизу. Помогите Пупе и Лупе не вылететь с работы (а то придется идти в бухгалтерию за расчетом, а там опять все перепутается. 8 Схема стеллажа может быть задана с помощью таблицы 3 на 3. Например 0 1 2 3 4 5 6 7 8 Где цифра – это номер книги. А отношения между книгами задано в соответствии со схемой 0 * * Кроме следующих объектов 0 * * 0 * * п * * 0 * * п Кроме того, после разговора с умным другом, удалось выяснить, что n1: 1. Нулевая книга написана Лениным 2. Первая книга – роман 3. Вторая книга в зеленой обложке 4. Четвертая книга на Иврите 5. Шестая книга – фантастика 6. Восьмая книга в черной обложке n2: 1. Ленин писал на русском языке 2. Стивен Кинг писал ужасы 3. Книга со стихами в белой обложке 4. Сказки написаны на итальянском языке 5. Фиолетовая книга написана Юваль Ной Харари 6. Фентези книга написана на польском 7. Книга на русском красного цвета 8. Детектив написан Конан-Дойлем n3: 1. Книга в желтой обложке находится слева снизу от книги Харари 2. Книга детектив находится справа снизу от книги на немецком 3. Книга со сказками находится справа снизу от книги Сапковского 9 Без склейки книга Шарля Бодлера находится справа снизу от книги в розовой обложке n4: 1. Книга Цысинь рядом с детективом Без склейки книга на американском рядом с научпопом) 2. Книга со стихами рядом с книгой в розовой обложке 3. Книга в синей обложке рядом с книгой на английском 4. Книга о политике рядом с детективом Без склейки книга на американском рядом с научпопом) Закодируем все свойства книг в соответствии со следующей таблицей Номер Автор Язык Жанр Цвет обложки 0 Ленин Русский Сказки Красный 1 Ремарк Английский Стихи Синий 2 Сапковский Французский Детектив Белый 3 Родари Немецкий Фентези Жёлтый 4 Юваль Ной Харари Американский Фантастика Зелёный 5 Конан-Дойль Итальянский Научпоп Фиолетовый 6 Лю Цысинь Китайский Ужасы Чёрный 7 Шарль Бодлер Иврит Политика Коричневый 8 Стивен Кинг Польский Роман Розовый Номер свойства 0 1 2 3 Однако решить такую задачу однозначно не удастся, так как для такого набора параметров она имеет 1080 решений (Без склейки - 1248). Поэтому Пупа обратилась к заметкам предыдущего работника, в которых сказано, что 1. Книга 7 написана Шарлем Бодлером 2. Книга 1 в синей обложке 3. Книга Родари в розовой обложке Без склейки Книга Родари слева снизу от книги Ремарка) 4. Без склейки Книга Шарля Бодлера слева снизу от книги в коричневой обложке) В результате получим такую интерпретацию решения Номер книги Автор Язык Жанр Цвет обложки 0 Ленин русский Политика Красный 1 Ремарк немецкий Роман Синий 2 Сапковский Польский Фентези Зеленый 3 Родари Итальянский Сказки Розовый 4 Юваль Ной Харари Иврит Научпоп Фиолетовый 5 Конан-Дойль Английский Детектив Коричневый 6 Лю Цысинь Китайский Фантастика Желтый 7 Шарль Бодлер Французский Стихи Белый 8 Стивен Кинг Американский Ужасы Черный Номер свойства 0 1 2 3 10 Заключение В результате выполнения курсовой работы была изучена задача Эйнштейна и решена ее усложнённая версия, со склейкой и с дополнительными условиями, для N объектов, которые имеют M свойств, что принимают N значений. Также были изучены все необходимые для решения средства, а именно библиотека BuDDy, что дает возможность использовать бинарные решающие диаграммы при решения логических задач в программировании. Список литературы 1. Подключение и использование библиотеки BuDDy на С+ URL: https://github.com/jgcoded/BuDDy 2. ЮГ. Карпов. Онлайн-курс "Математическая логика. Открытое образование. URL: https://openedu.ru/course/spbstu/MATLOG/?session=fall_2021 3. Документация по библиотеке BuDDy. URL: http://buddy.sourceforge.net/manual/main.html 4. Шошмина ИВ. Использование бинарных решающих диаграмм для решения логических задач. учебное пособие ИВ Шошмина - СПб.: Издательство Политехнического университета |