Лекції з математичної логіки

Математіческая_логіка.doc (11 стор.)
Оригінал


1   2   3   4   5   6   7   8   9   10   11
^

Формальне арифметика


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

, , , V, , , , =, +, *, ', 0, a, b, c, ..., , (,).

Коми в цьому рядку, три крапки і крапка в кінці не відносяться до числа формальних символів: це звичайні знаки пунктуації, використовувані нами для поділу формальних символів при друку символи "a, b, c - це" змінні "; нам потрібно, щоб сукупність була ( потенційно) лічильно-бесконечной.Но оскільки в латинському алфавіті лише 26 букв, ми будемо для визначеності вважати, що змінні - це будь-яка з цих 26, а також будь-яка з них, забезпечена праворуч одним або декількома входженнями символу. Таким чином, змінні, відмінні від 26 рядкових букв латинського алфавіту, - не поодинокі формальні символи, а деякі кінцеві послідовності формальних символів. Всього в алфавіт нашої формальної системи N входить, отже, в точності 41 формальний символ.

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

Визначення "терма".

1. 0 є терм.

2. Змінні a, b, c, ... суть терми.

<Замість термів підстановки результаті виразом формальним стає метамови, вираз а вираз, альное> "r" та "s".

Визначення "формули".

1. Якщо г і s - терми, то (r) = (s) - формула.

2 - 6. Якщо А і В - формули, то (А) ~ (В), (А) Е (В), (А) & (В), (А) V (В) і  (А) - формули.

7 - 8. Якщо А - формула, а х - змінна, то  х (А) і  х (А) - формули.

9. Ніяких формул, крім визначених згідно з 1 - 8, немає.

Так само як "r" та "s" у визначенні терма, тут "А" і "В" суть метаматематіческіе змінні, що представляють (замінюють) довільні формули, а "х"-метаматематіческая змінна, що представляє довільну формальну змінну. Наприклад, вираз " x (А)" стає формулою після заміни "х" довільної-змінної, скажімо а, а "А" - довільною формулою, наприклад (а) = (b), в результаті чого ми отримуємо формулу  a ( (a) = (b)). Якщо ми замість а візьмемо яку-небудь іншу змінну, наприклад b, то отримаємо іншу формулу:  b ((а). == (B)). Сказане пояснює, навіщо в п. 7 нашого визначення формули знадобилося користуватися метаматематіческой змінної "х": якщо б замість неї там стояла, скажімо, змінна а, то ми б могли отримати описаним тут чином лише формулу  а ((а) = (b )) (але не  b ((а) = (b)),  c ((a) = (b)).



^

ПОНЯТТЯ алгебраїчної системи

Загальні зауваження.


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

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

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

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

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

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

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

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

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

В тій чи іншій мірі цим вимогам відповідають так звані операторні алгоритмічні системи.



^

Операторні алгоритми Ван Хао.


Операторний алгоритм Ван Хао задається послідовністю наказів спеціального виду. Кожен наказ має певний номер і містить вказівки: яку операцію слід виконати над заданим об'єктом і наказ з яким номером слід далі виконати над результатом даної операції. Загальний вигляд такого наказу:

i: | w | a | b |

i - номер наказу

w - елементарна операція над об'єктом

a, b - номери деяких наказів

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

Теорема {3). Для того щоб часткова функція f (х) була обчислюваною за допомогою операторного алгоритму, програма якого містить лише частково рекурсивні функції wi (х) з рекурсивної областю визначеності, необхідно і достатньо, щоб f (х) була частково рекурсивної.

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

Теорема Мінського (4). Для кожної частково рекурсивної функції f (х) існує операторний алгоритм, програма якого складається з наказів виду

| Стоп |

| * C | a |

|: D | a | b |

для будь-якого х, переробний 2 в ступені х в 2 в ступені f (x).

Іншими словами, будь-яка частково рекурсивна функція f (х) вичіслімості за допомогою відповідного алгоритму, програма якого складається з наказів наведеного виду, за умови, що значення аргументу і функції кодуються числами 2 в ступені х в 2 в ступені f (x).



Навчальний матеріал
© uadoc.zavantag.com
При копіюванні вкажіть посилання.
звернутися до адміністрації