1. Синтаксис логіки предикатів. Приклади. Перетворення унарних предикатів в бінарні. Приклади
Синтаксис логіки предикатів. Приклади
Предикатом - мовне вираз, що означає до.-л. властивість або відношення. П., який вказує на властивість окремого предмета (напр., В«зеленийВ», В«теплийВ») Предикатом називається функція, яка повертає логічне значення. За допомогою предикатів часто визначають критерії сортування або пошуку. p> Логіка предикатів - розділ математичної логіки <# "justify"> Логіка предикатів була розроблена котрі три найбільш простого перетворення принципів логічного мислення в записувану форму. У логіці предикатів ви, насамперед, виключаєте зі своїх пропозицій все несуттєві слова. Потім ви перетворюєте ці пропозиції, ставлячи в них на перше місце відношення, а після нього - згруповані об'єкти. Надалі об'єкти стають аргументами, між якими встановлюється це відношення. В якості прикладу в таблиці 1 представлені пропозиції, перетворені у відповідності з синтаксисом логіки предикатів. p align="justify"> Логіка предикатів, звана також логікою першого порядку, допускає чотири типи виразів:
Константи. Вони служать іменами індивідуумів: об'єктів, людей або подій. p align="justify"> Змінні. Позначають імена сукупностей, таких як людина, книга, посилка, подія. p align="justify"> предикатні імена. Вони задають правила з'єднання констант і змінних, наприклад, правила граматики, процедури, математичні операції. Для предикатних імен використовуються символи на зразок таких: Фраза, Посилати, Писати, Плюс, Розділити. Предикатное ім'я інакше називається предикатной константою. p align="justify"> Функціональні імена представляють такі ж правила, як і предикати. Щоб не сплутати з предикативними іменами, функціональні імена пишуть одними малими літерами: фраза, посилати, писати, плюс, розділити. Їх називають також функціональними константами. p align="justify"> Синтаксис логіки предикатів (приклад)
По-російськи: Жак посилає книгу Марі,
Логічно: Посилка (Жак_2, Марі_4, Кніга_22).
Перетворення унарних предикатів в бінарні. Приклади
За допомогою предикатів часто визначають критерії сортування або пошуку. Залежно від способу застосування предикати поділяються на унарні і бінарні. Врахуйте, що не будь-яка унарна або бінарна функція, що повертає логічну величину, є дійсним предикатом. p align="justify"> Унарні предикати
Унарний предикат перевіряє деякий властивість одного аргументу. Типовий приклад - функція, яка використовується в якості критерію пошуку першого простого числа. p align="justify"> Бінарні предикати зазвичай порівнюють деякий властивість двох аргументів. Наприклад, щоб відсортувати елементи по нестандартному критерію, програміст передає алгоритмом просту предикатную функцію. Це може знадобитися, якщо, наприклад, елементи не можуть коректно працювати з оператором чи сортування повинна виконуватися по нестандартному критерію. p align="justify"> Унарні і бінарні предикати мають відповідно один і два аргументи. Фраза В«Сократ є людинаВ» представима унарним предикатом Людина (Сократ), а В«Жак любить МаріВ» - бінарним Любить (Жак_2, Марі_4). Будь унарний предикат можна перетворити в бінарний наступним чином. Унарний предикат складається з предикатного імені і значення свого єдиного аргументу. Отже, його формат такий: Предікатное_імя (значеніе_аргумента). Значення аргументу є конкретизація предикатного імені або змінною. Наприклад, Людина (Сократ) вказує, що ім'я власне В«СократВ» - конкретизація імені сукупності В«людинаВ», а Людина (х) вказує, що х - людина (не що-небудь інше). Фразу В«Сократ - людинаВ» можна представити бінарним предикатом КОНКРІТ (Сократ, людина). br/>В
2. Основні стратегії вирішення завдань. Попередні поняття та приклади
Основні стратегії вирішення завдань
Загальна схема для представлення завдань називається простором станів. Простір станів - це граф, вершини якого відповідають ситуацій, що зустрічаються в задачі ("проблемні ситуації"), а рішення задачі зводиться до пошуку шляху в цьому графі. Процес рішення задачі включає в себе пошук у графі, при цьому, як правило, виникає проблема, як обробляти альтернативні шляхи пошуку. Дві основні стратегії перебору альтернатив, а саме пошук в глибину і пошук в ширину. p align="justify"> Попередні поняття та приклади
Завдання полягає у виробленні плану переупорядочивания кубиків, поставлених один на одного, як показано на малюнку. На кожному кроці дозволяється переставляти тільки один кубик. Кубик можна взяти тільки тоді, коли його верхня поверхня вільна. Кубик можна поставити або на стіл, або на інший куби...
