Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

Тема 1. Попередні математичні відомості



ВСТУП

Курс «Формальні системи та математичні основи представлення знань» (ФСМОПЗ) є одним з базових під час підготовки студентів за спеціальністю 8.080404 – «Інтелектуальні системи прийняття рішень», закладаючи разом з дисципліною «Дискретна математика» фундамент знань в області комп’ютерної математики і забезпечуючи фундаментальними базовими поняттями, які дозволяють студентам використовувати математику не як метод розрахунку, а як метод мислення, як мову формулювання й організації понять. Теорія алгоритмів і формальних систем займає центральне місце в комп’ютерній математиці, хоча традиційно її відносять до «високої науки», вважаючи мало зв’язаною з практикою та складною для розуміння.

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

Метою викладання курсу «Формальні системи та математичні основи представлення знань» є:

- надання студентам у систематичній формі комплексу математичних результатів, призначених для точного опису і дослідження формально-дедуктивного методу в математиці;

- практичні застосування даної теорії, пов’язані з алгоритмічними мовами програмування, принципами побудови формальних теорій, автоматно-лінгвістичних моделей, баз знань в інтелектуальних системах прийняття рішень.

Курс «Формальні системи та математичні основи представлення знань» включає наступні розділи:

- формальні системи (ФС), в рамках даного розділу розглядуються теми:

1) абстрактні формальні системи. Напівсистеми Туе. Асоціативні числення. Канонічні системи Поста;

2) формальні системі логічного виведення. Числення висловлень як ФС. Аксіоматичні ФС і системи природного виведення. Дедуктивне виведення;

3) числення предикатів і теорії першого порядку;

4) автоматичне доведення теорем. Метод резолюцій у численні висловлень та у численні предикатів першого порядку;

5) метатеорія логічних числень. Повнота, розв’язність і перерахованість логічних числень.

- основи теорії формальних граматик (ФГ) та мов, в рамках якої вивчаються теми:

1) основні поняття теорії ФГ і мов. Властивості формальних мов, операції над формальними мовами. Породні граматики. Ієрархія Хомського;

2) контекстно-залежні граматики (граматики безпосередньо складових(БС));

3) контекстно-вільні (КВ) граматики;

4) класи формальних граматик, проміжні між контекстно залежними та контекстно вільними. Безконтекстні граматики, індексні граматики;

5) трансформаційні граматики. Категоріальні граматики;

6) застосування теорії ФГ і мов у системах штучного інтелекту. Граматики, що використовуються в машинних лінгвістичних аналізаторах. Мережеві граматики Вудса. Формалізм посилених мереж переходів. Кінцеві автомати та діаграми переходів;

7) еквівалентність визначення мов граматиками та автоматами. Автоматно-лінгвістичні моделі. Нерозв’язні проблеми в теорії формальних мов.

Курс «Формальні системи та математичні основи представлення знань» для спеціальності ІСПР передбачає 50 годин лекційних занять, 44 години практичних занять, дві контрольні роботи та 95 годин для самостійної роботи студентів над матеріалом курсу. Курс розбитий на два змістовних модулі, які відповідають таким основним розділам дисципліни:

«Теорія формальних систем» вивчається в обсязі 18 годин лекційних занять, 16 годин практичних занять і 28 години для самостійної роботи студентів;

«Основи теорії формальних граматик і мов» передбачає 18 години лекційних занять, 16 години практичних занять та 28 годин для самостійної роботи студентів.

На практичних заняттях студенти пишуть дві контрольні роботи (кожна розрахована на дві години аудиторної роботи): перша – після вивчення розділу «Формальні системи», друга – після вивчення розділу «Основи формальних граматик і мов». Крім того, протягом п’ятого семестру студенти виконують курсову роботу за матеріалами обраної частини курсу. Робочою програмою з дисципліни передбачається 15 годин самостійної роботи студента для написання курсової роботи. Формою підсумкового контролю є комбінований іспит.

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


Тема 1. Попередні математичні відомості

1.1 Мета занять

Повторити основні математичні відомості, необхідні при вивченні формальних теорій, засвоїти, які саме положення теорії множин та відношень необхідні при побудові формальних систем, граматик та мов.

1.2 Методичні вказівки з організації самостійної роботи студентів

При вивченні даної теми необхідно повторити основні поняття теорії множин та відношень, засвоїти операції над множинами, елементами яких є ланцюжки символів. Використовуйте конспект лекцій, а також літературу: [1; 4, с. 5-6, 12-13, 20-22; 7, с. 9-37; 9; 18, с. 92-163]

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

Об'єднанням множини А та В називається множина

,

тобто

Перерізом множин А та В називається множина

тобто

Різницею множин А та В називається множина

тобто

U – універсум.

Різниця (U \ А) називається доповненням множини А і позначається

Симетричною різницею множин А та В називається множина

Множину всіх підмножин множини А будемо позначати , тобто

.

Наприклад, якщо А={1,2}, то . Інший приклад: .

Декартовим добутком множин А та В називається множина всіляких пар, перші елементи яких належать А, а другі – В:

,

тобто

Зауваження: Декартовий добуток не є комутативною операцією, тобто . В загальному випадку декартовий добуток визначається

.

Якщо має місце , то множина називається ступенем множини А і позначається .

Бінарним відношенням між елементами множин А та В називається будь-яка підмножина R множини . Якщо А=В, то відношення R називається бінарним відношенням на множині А. Можна записувати: або . При цьому множина А називається областю визначення відношення R, а множина В - множиною його значень.

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

При визначенні ФС використовуються поняття мови та компонент, з яких вона складається. Відзначимо, що мова може бути визначена за допомогою ФС. На даному етапі дамо визначення мові з теоретико-множинних позицій. Одне зі складових понять мови – поняття символу, під яким розуміють найменшу неподільну частку мови. Ланцюжок – довільна послідовність символів, розташованих безпосередньо один за одним. Зауваження: терміни слово, рядок, а іноді при лінгвістичних інтерпретаціях речення часто використовується як синонім терміну ланцюжок. В курсі ТАФ розглядатимо такі множини, елементами яких є ланцюжки символів. Важливим є порядок символів у ланцюжку: ланцюжок аb і ba , та, наприклад, abca відрізняється від aabc. Довжина ланцюжка – це число символів у ній, тобто, якщо ланцюжок , де всі - символи, то довжина дорівнює n. Довжину будь-якого ланцюжка можна позначити , наприклад: .

Допускається існування порожнього ланцюжка e, тобто ланцюжка, що не містить жодного символу. |e| = 0. Терміни буква, знак будуть нами використовуватись як синоніми терміну символ для позначення елемента алфавіту.

Будь-яку множину, елементами якої є символи, будемо називати алфавітом. Погодимось позначати алфавіт прописними латинськими буквами, малими латинськими буквами a,b,c,d,... будемо позначати окремі символи, а малими грецькими буквами – ланцюжки (рядки). Ланцюжок, що складається з і символів а, позначають , наприклад: , …, α 0 = e.

Формально ланцюжки в алфавіті визначаються символьним способом:

(1) e – ланцюжок в ,

(2) якщо – ланцюжок в та , то або - також ланцюжок в

(3) – ланцюжок у тоді і тільки тоді, коли він є таким в силу (1) або (2).

Над ланцюжками визначені наступні операції.

Конкатенація. Якщо та - ланцюжки, то ланцюжок називається конкатенацією (або зчепленням) та . Для будь-якого ланцюжка завжди справедливо: ae = ea = a..

Оберненням ланцюжка або інверсією (позначається ) називається ланцюжок, записаний у зворотному порядку. Зазначимо, що e R = e.

Важливим поняттям є також ступінь ланцюжка. Якщо - ланцюжок, то , , . У загальному випадку визначається як результат n –кратної конкатенації ланцюжків . Для n>0: . Нехай - довільні ланцюжки в алфавіті . Назвемо префіксом ланцюжка , - суфіксом ланцюжка . Префікс і суфікс ланцюжка є його підланцюжками. Наприклад, ba – префікс та підланцюжок bac. Порожній ланцюжок e є префіксом, суфіксом і підланцюжком будь-якого ланцюжка. Якщо та – префікс (суфікс) ланцюжка , то називається власним префіксом (суфіксом ланцюжка) . Операція підстановки вказує, що при зустрічі в тексті ланцюжка , необхідно виконати його заміну на ланцюжок .

Необхідно також звернути увагу на операції, які застосовують для множин, елементами яких є символи або ланцюжки символів. Конкатенацією двох множин А та В називається множина

.

Наприклад, якщо , то . Зверніть увагу, що . Зауваження: не слід ототожнювати порожню множину 0, для якої справедливо , з множиною {e}, що містить порожній ланцюжок. Порожня множина відіграє роль нуля, а {e} – одиниці відносно операції конкатенації множин. Ітерація алфавіту V називається також операцією Кліні:

Вона дає можливість побудувати множину, що містить всі можливі ланцюжки в алфавіті, включаючи e. Зрізана (позитивна) ітерація алфавіту має вигляд тобто , а також

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

Процес перекладу з однієї мови на іншу може трактуватися як процес реалізації деякого алфавітного оператора (АО). При цьому транслятор представляється як множина пар (х, у), де х – деяка програма у вхідній мові , у – відповідна програма на машинній мові , тобто . Якщо х – ланцюжок у вхідному алфавіті , а у – ланцюжок у внутрішньому алфавіті , то трансляція – це відображення виду

,

причому , .

Мовою в алфавіті A називається підмножина множини A*. Ми будемо розглядати мови, рядки яких отримані за певними правилами.

Наприклад: правильно побудовані формули (ППФ) логіки висловлень є мова. Будь-який рядок цієї мови може бути отриманий за правилами, що визначають ППФ. Оскільки мова - це множина, до неї можна застосовувати всі теоретико-множинні операції: об'єднання, перетинання, різницю, доповнення. Для мов також визначено операцію конкатенації. Нехай - мова в алфавіті , - мова в алфавіті . Тоді мова називається конкатенацією мов . Досить часто розглядають нескінченну конкатенацію, що називається ітерацією. Ітерація мови , позначається та визначається таким чином:

а)

б) для

в)

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

При розгляді будь-якої мови в ній виділяють синтаксис, семантику та прагматику. Синтаксис задає правильне взаємне розташування символів у рядках мови. Семантика вказує в деякому плані зміст, наприклад, послідовність машинних операцій, що задаються правильним рядком програми.

Прагматика – це найбільш раціональне вираження змісту засобами синтаксису. Для опису конкретної мови використовують так звані метамови. Докладно ознайомимося з метамовами при розгляді формальної системи для породження мов.

Операцію конкатенації часто позначають символом o. Властивості операції конкатенації:

1) властивість замкненості:

О: ;

2) властивість асоціативності:

()

,

де - множина ланцюжків (нескінченна) скінченної множини А базових елементів (символів), включаючи порожній ланцюжок е, X, Y, Z – довільні ланцюжки, що належать . Розглянемо пару . З урахуванням перерахованих властивостей операції o ця пара являє собою напівгрупу з одиничним елементом e, чи моноїд. Напівгрупою в алгебрі називають також тільки множину (в даному випадку ), що скрізь постачається визначеною асоціативною операцією. Множина А також називається алфавітом. Будь-яка множина ланцюжків , де А* - моноїд, називається формальною мовою, визначеною на алфавіті А.

1.3 Контрольні запитання і завдання

1) Нехай А={0,1,2}, В={0,3,4}. Запишіть множини:

а) ;

б) ;

в) ;

г) ;

д) ;

2) Нехай . Запишіть множини, що визначаються наступними предметами:

а) { x | x належить А і х - парне}

б) { x | x належить А і являється квадратом}

в)

3) На множині задано відношення:

а) {(1,2), (2,3), (2,4), (3,2), (5,1)}

б) {(2,1), (3,4), (4,4), (5,3)}

в) {(1,2), (2,3), (3,2), (4,3), (5,1)}

г) {(1,2), (2,3), (4,1), (4,5), (5,5)}

Які з цих відношень - функції?

4) Довести що множини {3,7,5,3} та {3,5,7} рівні між собою.

5) Що таке ланцюжок? Які операції визначені над ланцюжками?

6) Надайте означення конкатенації, інверсії, ступеня ланцюжка. Наведіть приклади.

7) Для ланцюжка визначити довжину , обернення , множину префіксів , множину суфіксів

8) Визначити множину С=АВА, якщо А={a,b}, B={+,*}.

9) Нехай . Випишіть наступні ланцюжки:

.

10)Наведіть приклад конкатенації двох множин.

11)Які основні властивості операції конкатенації?

12)Яка множина називається алфавітом?

13)Які операції застосовують до множин, елементами яких є ланцюжки символів?

14)Що таке операція Кліні?

15)Що таке формальна мова, як вона визначається?

1.4 Приклади аудиторних і домашніх задач

Приклад 1: довести, що .

Розв’язання:

Множина {0} має один елемент 0, а множина 0 не має елементів.

Приклад 2: довести, що {{1,2},{2,3}} не дорівнює {1,2,3}.

Доведення: Дві множини тотожні тоді і тільки тоді, коли кожний елемент А є елементом В та навпаки. В даному випадку ця умова виконується, отже множини рівні.

Приклад 3: задані множини . Декартовий добуток цих множин визначається як .

Приклад 4: якщо задані ланцюжки , то їх конкатенація визначається таким чином .

Приклад 5: якщо заданий ланцюжок , де всі - символи, то обернення цього ланцюжка .

Приклад 6: якщо , то e, , ab, abc – префікси ланцюжка , до того ж всі вони, крім abc – власні префікси заданого ланцюжка.

Приклад 7: задано ланцюжок abba та підстановка для символа . Тоді результат застосування операції підстановки до заданого ланцюжка 101bb101.

Приклад 8: задано множину V={0,1}, застосовуючи операці. Кліні до заданої множини, отримаємо .

Тема 2. Формальні теорії (логічні числення). Абстрактні формальні системи. Напівсистема Туе. Асоціативні числення. Системи продукцій Поста (канонічні ФС)

2.1 Мета занять

Засвоїти основні математичні поняття, що використовуються в практичному вивченні ФС. Ознайомитись з основними поняттями та структурою формальних теорій. Засвоїти принципи побудови формальних теорій, закріпити навички логічного виведення в абстрактних ФС, асоціативних численнях, канонічних системах Поста.

2.2 Методичні вказівки по організації самостійної роботи студентів

При вивченні даної теми необхідно повторити основні поняття теорії ФС, ознайомитися з принципами побудови формальних теорій та структурою абстрактних ФС, асоціативних числень, канонічної системи Поста. Використовуйте конспект лекцій, а також літературу: [6, с. 215 – 246; 17, с. 92 – 163]

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

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

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

Формальна теорія (або числення) будується наступним чином:

1. Визначається множина формул, або правильно побудованих виразів (ППВ), що утворюють мову теорії. Ця множина задається конструктивними засобами (як правило, індуктивним визначенням) і, отже, перерахована. Зазвичай вона й розв’язувана. Вимога можливості розв’язності логічного числення є не обов'язковою, але бажаною.

Логічне числення називається розв’язуваним, якщо існує механічна процедура (алгоритм) виділення теорем із множини різних формул. Відмітимо, що для числення висловлень (ЧВ) існує розв’язувальна процедура Поста, отже, ЧВ розв’язуване.

2. Виділяється підмножина формул, які називаються аксіомами теорії. Ця множина може бути й нескінченною; у будь-якому випадку вона повинна бути розв’язуваною.

3. Задаються правила виведення теорії. Правило виведення – це обчислюване відношення на множині формул. Якщо формули перебувають у відношенні R, то формула G називається такою, що безпосередньо виводиться з за правилом R.

Часто правило записується у вигляді ,

де формули називаються посилками правила R, а G – його висновком.

Виведенням формули B з формул називається послідовність формул така, що , а будь-яка є або аксіома, або одна з вихідних формул , або безпосередньо виводиться з формул (або якоїсь їхньої підмножини) по одному з правил виведення.

Якщо існує виведення В з , то кажуть, що B виводиться з і позначають:

Формули називаються гіпотезами або посилками виведення.

Перехід у виведенні від до називають i -тим кроком виведення.

Доведенням формули B в теорії T називається виведення B з порожньої множини формул, тобто виведення, в якому як вихідні формули використовується тільки аксіоми.

Формула B, для якої існує доведення, називається формулою, що доводиться в теорії T, або теоремою теорії T, факт довідності B позначається

B – «формула B є теорема», «існує виведення B»,або «формула B вивідна».

Очевидно, що приєднання формул до гіпотез не порушує вивідності. Тому, якщо ├ B, то АB, якщо , то для будь-якої і . Порядок гіпотез у списку несуттєвий.

Будемо розглядати ФС не тільки як деякий закінчений математичний об'єкт, але й з погляду раціональної її реалізації. Тобто ми будемо розглядати ефективні алгоритми у ФС. Необхідно бути ознайомленими з алгебраїчним апаратом напівсистем Туе. Розглянемо пари ланцюжків , з . Співвідношеннями Туе (названі так на честь норвезького математика, який вперше їх досліджував) називаються правила, згідно з якими по будь-якому ланцюжку з множини буде ставитись у відповідність ланцюжок з тої ж множини (i=1, 2, … n) і навпаки. Ці співвідношення приводять до так званих асоціативних числень. Якщо ланцюжок Y одержується із ланцюжка X однократним застосуванням одного співвідношення Туе (тобто заміною підланцюжка Pi на підланцюжок Qi), то кажуть, що X і Y є суміжними ланцюжками. Ланцюжок Xn співвідноситься з ланцюжком Xo, якщо існує послідовність ланцюжків , така, що , , є суміжними ланцюжками (I = 1, 2, … n)... Співвідношення Туе є двосторонніми: якщо ланцюжок Х є суміжним по відношенню до ланцюжка Y, і навпаки, ланцюжок Y є суміжним по відношенню до ланцюжка Х.

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

Канонічні системи породження – це в дійсності граматичні правила маніпулювання рядками символів і тому їх іноді називають правилами переписування (rewrite rules). Эміль Пост вивчав властивості систем правил, що базуються на породженнях, які він назвав канонічними системами. Канонічна система – це різновид формальної системи, основаної на наступних компонентах:

· алфавіт А, із символів якого формуються рядки;

· деяка множина рядків, які розглядаються як аксіоми;

· множини породжень у формі,

де

I. Кожне i і i є фіксований рядок;

II. 1 і m часто є нуль;

III. деяке або все з i або i може бути нулем;

IV. кожне $i є змінним рядком, що також може бути нулем;

V. кожне $i заміняється певним $i1.

Приклад канонічної системи: алфавіт А = {a, b, c}; аксіоми (1) а; (2) в; (3) с; (4) аа; (5) вв; (6) сс.

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

Наприклад, одержимо паліндром bacab.

Зверніть увагу, що ця послідовність породжень не має властивості комутативності, тобто якщо застосувати ті ж правила, але в іншому порядку, то отримаємо зовсім інший результат. Наприклад, якщо до аксіоми спочатку застосувати правила P2, а потім P1, то одержимо abcba.

На перший погляд канонічні системи досить тривіальні. Все, що можна зробити в рамках такої системи, – перетворити один рядок символів на інший. Але якщо задуматися, то будь-яке логічне та математичне числення зрештою зводиться до набору правил маніпулювання символами.

Звідси випливає, що будь-яка формальна система може розглядатися як канонічна. Насправді до цього потрібно додати тривіальне застереження, що така система може мати потребу в додатковому алфавіті, букви якого будуть використовуватися як знаки пунктуації в складних доведеннях. Таким чином для перевірки доведення у будь-якій ФС або для того, щоб виконати будь-яку ефективну процедуру, цілком достатньо здатності прочитати рядок символів, розділити його на компоненти та знову впорядкувати (при цьому, можливо, доведеться додати ще якісь символи або видалити існуючі у вихідному рядку).

2.3 Контрольні запитання і завдання

1) Надайте означення формальної системи;

2) Що таке канонічна система? Наведіть приклад.

3) Що таке напівсистема Туе?

4) Наведіть приклад асоціативного числення.

5) Надайте означення продукційного правила. Наведіть приклади.

6) Що таке антецедент?

7) Що таке консеквент?

8) Яке логічне числення називається розв’язним?

9) Побудуйте формальну систему, яка породжує усі правильні скобочні вирази.

2.4 Приклади аудиторних і домашніх задач

Приклад 1: розглянути формалізацію поняття формули у численні висловлень (ЧВ), що дається індуктивним визначенням формули. У ЧВ – алфавіт складається зі змінних висловлень (пропозиціональних літер): А, В, С,..., знаків логічних зв'язок , , і дужок (,).

Формули ЧВ будуються за такими правилами:

а) змінне висловлення є формула;

б) якщо А і В формули, то та A - формули;

в) інших формул немає.

Зовнішні дужки у формулах опускають.

Неважко показати, що множина формул, визначених таким чином, перерахована (і навіть розв’язувана) і, отже, існує алгоритм, що породжує цю множину. Однак конкретний порядок породження формул, що визначив би номер формули в списку формул, тобто конкретний алгоритм, що перераховує, не фіксується цим визначенням. Зафіксувати такий алгоритм можна різними способами, але для точного визначення формули цього не потрібно.

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

Приклад 2: ілюструє визначення й функціонування ФС.

Нехай заданий алфавіт , з якого складені рядки ФС. Множина аксіом ФС має вигляд:

1. ;

2. ;

3. .

Правила виведення:

Одержимо можливе виведення в цій ФС, нумеруючи для зручності кожний рядок виведення:

(1) - аксіома 2;

(2) - аксіома 1;

(3) - безпосередньо виводиться з (1), (2), і ;

(4) - аксіома 3;

(5) - з (1), (3), (4) і .

Таким чином, ФС у даному прикладі виводить як теорему рядок .

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

Приклад 3: розглянемо приклад ФС, рядки якої мають певний зміст, а саме, є правильними формулами логіки висловлень, і будь-який рядок, що є теоремою ФС, це загальнозначуща формула. Однак, відзначимо, що в цьому випадку маніпуляція рядками виконується на чисто формальному рівні за правилами функціонування ФС.

Алфавіт: ={ }.

Множина аксіом: 1. ;

2. ( ) ;

3. ( ).

Ці аксіоми в математичній логіці відомі як аксіоми Лукасевича.

Правила виведення:

У правилах виведення є будь-які правильні формули логіки висловлень (тобто правильні рядки та підрядки ФС), а в правилі отримана з рядка підстановкою рядка замість всіх входжень у неї символу . Покажемо, що є теорема цієї ФС, для чого приведемо виведення рядка :

Отже, щоб довести теорему у ФС, треба спочатку виписати аксіоми та застосувати до них правила виведення.

Всі рядки, отримані таким чином, становлять теореми першого рівня.

Якщо правила виведення застосовують до теорем першого рівня, то одержують теореми наступного рівня і т.д. Іноді аксіоми розглядають як теореми нульового рівня. При такому підході будь-який рядок доведення (виведення) - теорема ФС.

Приклад 4: нехай А – множина букв російського алфавіту. Тоді множина ланцюжків, складених з 5 букв, являє собою формальну мову L1. Інший приклад мови, що визначається на тому ж алфавіті – множина L2 5-буквенних слів російської мови, які можна розшукати в орфографічному словнику, очевидно, що L2 < L1, тому що багато ланцюжків мови 2 не є словами російської мови.

Приклад 5: нехай А – множина букв російського алфавіту, на якій визначимо співвідношення Туе, що полягає в праві заміни будь-якої однієї букви слова на будь-яку іншу. Тоді в послідовності ланцюжків

МУКА, МУЗА, ЛУЗА, ЛОЗА, ПОЗА, ПОРА, ПОРТ, ТОРТ

два будь-які сусідні ланцюжки є суміжними, а ланцюжки МУКА та ТОРТ співвідносяться в змісті заданих співвідношень.

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

Розглянемо мову, що утворюється, якщо із усіх виразів даної мови видалити всі символи, за винятком дужок. Нехай є n різних сортів таких дужок (, [, { і т.д. Ланцюжок Х належить обмеженій мові Діка, якщо вона співвідноситься з порожнім ланцюжком е (Е) у сенсі співвідношень Туе:

де li – ліва дужка i-го сорту,

рi – відповідна до неї права дужка.

Легко побачити, що ланцюжок l1l2p1p2l3p3 належить до обмеженої мови Діка, тому що приводиться до порожнього ланцюжка послідовним застосуванням даних співвідношень:

Приклад 7: побудувати ФС із правилами виведення у формі продукцій, теоремами якої були б парні додатні числа, крім нуля, в унарній системі числення.

Розв’язання: унарна система числення використовує для представлення чисел єдиний символ – 1. Рядки, що представляють собою теореми необхідної ФС: 11, 1111, 111111,....

Отже, алфавіт даної ФС представлений множиною {1}. Далі зауважуємо, що якщо деякий рядок являє собою парне число, то приписавши до цього рядка дві одиниці (праворуч або ліворуч), одержуємо знову парне число. У цьому випадку одержання наступного рядка з попереднього уключається в приєднанні до попереднього фіксованих символів. Якщо попередній рядок позначити , то можна скласти продукцію: Тоді ФС має вигляд:

алфавіт А={1};

аксіоми 1. 11;

продукції 1. (правила)

Покажемо, що число 6 є теорема даної ФС. Виведення:

(1) 11 аксіома 1;

(2) 1111 з (1) і продукції 1;

(3) 111111 з (2) і продукції 1

Таким чином, ми показали, що побудували ФС із заданими властивостями. Відзначимо, що для одержання нового рядка зі старого не потрібно операцій розчленовування та перестановки підрядків у старому рядку. Тут досить приписування фіксованого числа символів.

Приклад 8: побудувати ФС, теоремами якої є правильні твердження щодо результату операції складання двох цілих додатних чисел (крім 0) в унарній системі числення. Уточнимо, що теоремами системи будуть рядки 1+1=11, 1+11=111, 11+111=11111, 111+11=11111,..., що правильно задають операцію складання.

Розв’язання: очевидно, що для породження рядків, які є теоремами, необхідно три символи “1”, “+”, “=”. Зрозуміло також, що символи “+” і “=” можна використовувати як фіксовані, що розбивають рядок на підрядки, і що дозволяють виділити доданки й результат, як підрядки рядка. Позначимо підрядок, що знаходиться перед символом “+” через , підрядок, що знаходиться за символом “+”, - через , а підрядок, що знаходиться за символом “=”, - через . Тоді, якщо рядок є теорема, то і рядки

також є теореми.

Як аксіоми можна взяти один рядок 1+1=11, який є твердженням про суму двох найменших чисел. Всі інші теореми можна одержати виведенням.

З огляду на викладене, маємо ФС:

алфавіт А={1, +, =};

аксіоми 1. 1+1=11;

продукції П.1. ,

П.2.

Покажемо, що 3+2=5 - теорема ФС, для чого зробимо виведення:

(1) 1+1=11 аксіома 1;

(2) 11+1=111 з рядка (1) і продукції 1;

(3) 111+1=1111 з рядка (2) і продукції 1;

(4) 111+11=11111 з рядка (3) і продукції 2;

У продукціях цього приклада необхідно було розділяти рядок на підрядки за допомогою постійних символів (+, =), а також вводити всередину рядка в точно фіксованому місці постійний підрядок 1.

Розглянемо приклад, у якому використовувалися б продукції з поділом рядка на підрядки та перебудова підрядків.

Приклад 9: Побудувати ФС, теоремами якої були б правильні твердження про множення цілих чисел (крім нуля) в унарній системі числення.

Розв’язання:

Теореми системи:

Аналогічно прикладу 8 (попередньому) символи та = є роздільниками між співмножниками та результатом.

Якщо - теорема системи, то й - теореми. Останні два рядки отримані з першого дописуванням символів і в зазначеному місці та перебудовою підрядка . (Нагадаємо, що дописування підрядка – це операція конкатенації).

Таким чином, ФС буде записана:

алфавіт ;

аксіома 1) ;

продукції 1) ;

2) .

Розглянемо виведення рядка: :

(1) - аксіома 1;

(2) - з (1) і продукції 1;

(3) - з (2) і продукції 2.

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

Тема 3. Формальні системи логічного виведення. Числення висловлень як формальна система. Аксіоматичні формальні системи числення висловлень. Система природного виведення в численні висловлень. Теорема дедукції





Дата публикования: 2015-04-07; Прочитано: 1011 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.083 с)...