Повна версія

Головна arrow Природознавство arrow ІНТЕЛЕКТУАЛЬНІ СИСТЕМИ

  • Увеличить шрифт
  • Уменьшить шрифт


<<   ЗМІСТ   >>

АВТОМАТИЗАЦІЯ РІШЕННЯ ЗАДАЧ. ЛОГІЧНИЙ ПІДХІД

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

З цієї тематики може бути рекомендована книга [42].

З.1 Обчислення висловлювань

З.1.1 Мова логіки висловлювань

При завданні формального логічного мови зазвичай йдуть наступною схемою:

  • а) Вказується кінцевий або нескінченний набір символів, що утворюють алфавіт мови; при описі алфавіту можуть вводитися ті чи інші характеристики його символів, зокрема визначатися розбиття їх на підкласи.
  • б) Вводиться індуктивне опис безлічі правильних виразів мови - кінцевих послідовностей символів алфавіту.
  • в) Індуктивним чином визначається інтерпретація мови (або множин допустимих інтерпретацій), що зіставляє кожному виразу мови позначається їм функцію, або об'єкт з деякою "області інтерпретації".

Пункти а) і 6) задають синтаксис логічного мови, пункт в) - його семантику

У разі мови логіки висловлювань ця загальна схема реалізується в такий спосіб:

  • а) Алфавіт мови логіки висловлювань складається з рахункового списку змінних хьвд, двох логічних констант І, Л; заданого набору логічних зв'язок (наприклад, зв'язок V, &, * -?), а також дужок (,).
  • б) Правильні вирази мови логіки висказиваухій , звані формулами логіки висказиваухій , вводяться за допомогою наступного визначення:
    • 1) однобуквеним слово, що складається із змінної, є формула логіки висловлювань.
    • 2) Якщо слова А і В суть формули логіки висловлювань, то

слова (-'Л), V В) ) (AScB) } (А - ? В)> ( А В) суть формули

логіки висловлювань.

в) При завданні інтерпретації формул логіки висловлювань можливі два різних підходи - ці формули можуть розглядатися або як позначення функції алгебри логіки, або як позначення одиничних висловлювань, що мають певне истинностное значення. В обох випадках визначається формулою об'єкт (функція або истинностное значення) вводиться індуктивним чином, по кроках побудови формули, з використанням добре відомих таблиць істинності для основних логічних зв'язок. У першому випадку базис індукції зіставляє кожній однобуквеним формулою т, тотожну функцію; у другому випадку - деяке конкретне значення з безлічі І, Л.

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

Таким чином, інтерпретацією мови логіки висловлювань ми називаємо відображення /, певне на безлічі змінних х % ХГ, ... і зіставляє кожній змінній х, деяку істиннісну константу а ,; а * G {І, Л}. Значення ( F) r формули F в інтерпретації I визначаємо індукцією по побудові формули F:

  • 1) Якщо F є змінна х *, то ( F) i є / (х <);
  • 2) Якщо F має вигляд - »( (G) j = 6, то (F) [ є істиннісне константа, відмінна від 6;
  • 3) Якщо F має вигляд G V G 2 і вже визначені (G) i = 61, (G 2 ) / = 62, то ( F) j є константа І, якщо хоча б одне з Ь , 62 одно І, інакше ( F) j є Л;
  • 4) Якщо F має вигляд GkG 2 і вже визначені (G) j = 61, (^ 2) / = 62, то (F) j є константа І, якщо 61,62 рівні І, інакше (F) j є Л;
  • 5) Якщо F має вигляд G -? G 2 і вже визначені (Сч) / = 61, (С? 2) / = 62, то (F) / є константа Л, якщо 61 одно І, а 62 одно Л; інакше (F) i є І;
  • 6) Якщо F має вигляд G <-> (7 2 і вже визначені (Сч) / = 6 ' ь (С? Г) / = 6 2 , то (F) / є константа І, якщо 61 = 62, інакше ( F) / є Л.

Введемо для логіки висловлювань кілька загальних понять, пов'язаних з інтерпретацією формул і є типовими для логічних мов.

Моделлю формули / називатимемо довільну інтерпретацію мови логіки висловлювань в якій / має значення І.

Формулу має хоча б одну модель назвемо здійсненним.

Формулу не має жодної моделі назвемо нездійсненним.

Формулу, для якої кожна інтерпретація мови логіки висловлювань є моделлю, назвемо загальнозначущої.

Як приклади відзначимо, що формула ((xi Vx 2 ) - * х 2 ) - здійсненна, але не общезначима, формула ((xi & x 2 ) -? Х 2 ) - общезначима, а формула (- '(xi -? (Х 2 -? xi))) - нездійсненна.

Надалі часто ми будемо опускати дужки, маючи на увазі, що - "- пріоритетна операція, і в разі, коли порядок розставляння дужок не суттєвий.

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

  • 1) Знаходження індуктивного опису класу всіх загальнозначущих формул. Такий опис визначає в базисі індукції деяку підмножину загальнозначущих формул (кінцеве або нескінченне), званих аксіомами, і вказує в індуктивному кроці перелік допустимих правил виводу, що дозволяють отримувати нові загальнозначущі формули виходячи з раніше знайдених. Логічний мову разом з індуктивним описом такого роду утворює дедуктивну систему.
  • 2) Знаходження алгоритму, яке перераховує все загальнозначущі формули - фактично, забезпечується при побудові дедуктивної системи.
  • 3) Знаходження алгоритму, що розпізнає загальнозначущі формули в класі всіх правильних виразів мови. На відміну від пунктів 1 і 2, опис такого типу вдається знайти лише для дуже небагатьох логічних мов, до числа яких належить і мова логіки висловлювань.
 
<<   ЗМІСТ   >>