Студопедия
Новини освіти і науки:
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах


РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання


ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ"


ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ


Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків


Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні


Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах


Гендерна антидискримінаційна експертиза може зробити нас моральними рабами


ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ


ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів



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

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

Позначимо стану вовка, кози, капусти і фермера змінними О, С і Б відповідно і присвоїмо їм значення «істина» або логічна одиниця, якщо вони знаходяться на лівому березі, і «брехня» або 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 рядків:

 

 

  О С Б ОІ СІ БІ
І І І І І І І
І І І І І
І І І І І І
І І І І
І І І І
І І І І
І І І І
І І І І
І І І
І0 І І

 

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


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

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




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

<== попередня сторінка | наступна сторінка ==>
Низька здатність формувати колектив | Знаходимо рядок з вихідним станом змінних (у нашому випадку - перший рядок).

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

  

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


Генерація сторінки за: 0.007 сек.