• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Пошук на основі логіки (булева логіку).

У попередніх лекціях ми розглядали рішення задачі про вовка, козу і капусту методом пошуку в просторі станів. Між тим, в літературі ця задача називається логічною. Отже, її рішення повинно бути отримано шляхом умовиводів. Спробуємо застосувати пропозіціонную логіку (булеву логіку) для знаходження рішення.

Позначимо стану вовка, кози, капусти і фермера змінними О, С і Б відповідно і присвоїмо їм значення «істина» або логічна одиниця, якщо вони знаходяться на лівому березі, і «брехня» або 0, якщо на правому. Тоді стартове стан буде "= 1, О = 1, С = 1, Б = 1, а кінцеве -" = 0, О = 0, С = 0, Б = 0. Забороненими станами будуть наступні:

"О-Б - вовк і коза на лівому березі, фермер - на правом;

ОС-Б - коза і капуста на лівому березі, фермер - на правом;

- "-ПРО - вовк і коза на правому березі, фермер - на лівому;

- "-ПРО - коза капуста на правому березі, фермер - на лівому.

Для вирішення цього завдання потрібні вхідні і вихідні змінні. Позначимо "1, О1, С1 і Б1 в якості вихідних змінних. Рішення задачі в логіці першого порядку має виглядати наступним чином: ^, О, С, Е) => (" 1, О1, С1, Б1) = (0,0 , 0,0).

На жаль, ця задача не вирішується за один крок, тому рішення буде полягати в послідовності перетворень змінних ", О, С, Б в" 1, О1, С1, Б1.

При переміщенні з лівого на правий берег не повинні бути істинними вирази "1О1 або О1С1.

(Б & "&-О-С) => (Б1 = 0, = 0, О1 = О, С1 = С) - фермер везе вовка;

(Б & О) => (Б1 = 0, "1 = О1 = 0, С1 = С) - фермер везе козу. Конфлікту бути не може в принципі, так як вовк не їсть капусту;

(Б & З & - "-О) => (Б1 = 0, С1 = 0," 1 = "" О1 = О) - фермер везе капусту.

Спробуємо тепер виразити у вигляді булевої функції умова переміщення фермера з правого берега на лівий без вантажу. Це можливо в тому випадку, якщо фермер знаходиться на правому березі (-Б), і з його відходом звідти вовк не з'їсть козу (- "-О), а коза - капусту (-О-С):

(-Б & - "-О &-О-С) => (" 1 = О1 = О, С1 = С, Б1 =-Б).

Таким же чином можна написати булеві функції для вирішення конфліктів на правому березі. Об'єднавши всі ці імплікації за допомогою диз'юнкції, отримаємо універсальну функцію для одного кроку вирішення цього завдання, щоправда, без усунення повторюваних станів.

Зауважимо, що написання цих функцій є досить копітку роботу, причому для іншої задачі ці функції повинні бути написані заново. Формалізація вирішення подібних завдань може бути досягнута використанням таблиць істинності. Випишемо всі можливі комбінації змінних:

Тепер видалимо з таблиці рядки, відповідні забороненим комбінаціям. До таких відносяться вищеперелічені "ІОІ-РІ, ОЮ-БІ, -" І-ОІРІ, - "І-ОІРІ, а також такі, в яких змінюється стан більш, ніж одній із змінних О, С (за умовою завдання на борт можна взяти більше одного вантажу), або не змінюється стан змінної Б (без човна переправитися не можна), або човен і вантаж рухаються в протилежному напрямку (одна з змінних змінюється з 0 на І, а Б - з І на 0 і навпаки). Також з таблиці можна видалити рядки, що не відповідають кінцевої мети (рух човна порожняком з лівого берега на правий). Таким чином, вихідна таблиця з 256 рядків перетворюється в таблицю з І0 рядків:

Пошук рішення на основі таблиці істинності полягає в наступному:

Читайте також:

1. Абсолютизація формально-технічних пошуків у мистецтві ХХ ст.
2. Адгезиви на основі латексів у взуттєвій промисловості
3. Адміністративний примус застосовують на основі адміністративно-процесуальних норм.
4. Алюміній і сплави на його основі
5. Аналіз ризикованості підприємства на основі показників фінансового стану.
6. Аналогія - спосіб отримання знань про предмети та явища на основі їхньої подібності з іншими.
7. Аналогія права - вирішення справи або окремого юридичного питання на основі принципів права, загальних засад і значення законодавства.
8. Багатомовна пошукова система
9. Бібліографія. Інформаційно-пошукові мови бібліографічних фондів. Види каталогів: систематичні, предметні, абеткові.
10. Біокомпозити та композиційні матеріали на основі відходів переробки деревини
11. Будівельний підряд. Підряд на проектні та пошукові роботи.
12. Бюджетні установи отримують кошти на своє функціонування з бюджету виключно на основі фінансових документів, які називаються кошторисами.

Переглядів: 692