Логика. логіка. Математична логіка та теорія алгоритмів
 Скачать 1.6 Mb.
|
|
Запитання для самоконтролю 1. Що розуміють під терміном обмежені квантори та як вони використовуються. 2. Які формули логіки предикатів визначають обмежені квантори. 3. Якою формулою логіки предикатів запишеться твердження: «Існує один і тільки один х, що має властивість Р». 4. Якою формулою логіки предикатів запишеться твердження: «Існує не більше однного х, що має властивість Р». 5. Що таке категоричні судження та як вони класифікуються. 6. Якою формулами логіки предикатів запишуться: загальностверджувальне судження, частковозаперечувальне судження, частковостверджувальне судження, загальнозаперечувальне судження. 7. При аналізі теореми типу ) ( ) ( x P x S x що називається достатньою умовою, а що необхідною. 8. Яка теорема називається оберненою до теореми ) ( ) ( x P x S x Наведіть приклад відповідних математичних тверджень. 9. Яка теорема називається протилежною до теореми ) ( ) ( x P x S x Наведіть приклад відповідних математичних тверджень. 92 10. Яка теорема називається протилежною до оберненої. Наведіть приклад прямої та протилежної до оберненої математичних теорем. ВПРАВИ. 3.31. Записати наступні означення за допомогою мови логіки предикатів: a) границі функції; b) збіжного ряду; c) перпендикулярних прямих; d) неперервної функції; e) колінеарних векторів; f) суми векторів в координатах; g) паралелограма; h) рівностороннього трикутника; i) складеного числа; j) НСД двох чисел. 3.32. Записати наведені нижче математичні твердження за допомогою мови логіки предикатів та побудувати для кожного з них обернене твердження, протилежне твердження та обернене до протилежного. Визначити, які з них будуть вірними, а які – ні. a) Якщо діагоналі чотирикутника перетинаються і в точці перетину діляться пополам, то цей чотирикутник паралелограм. b) Якщо функція неперервна в кожній точці відрізка, то вона неперервна і на всьому відрізку. c) Для того, щоб ряд був збіжний необхідно щоб його загальний доданок прямував до нуля. d) Якщо функція неперервна на відрізку і приймає на кінцях цього відрізка значення різних знаків, то на цьому відрізку міститься принаймі один корінь рівняння f(x)=0. e) Якщо дві прямі паралельні деякій третій прямій, то вони паралельні між собою. 3.33. Виділити умову та висновок теореми та сформулювати теореми за допомогою зв’язки «якщо…,то…»: a). Для подільності добутку двох натуральних чисел на деяке число достатньо подільності на це число одного із співмножників. 93 b). Рівність трикутників є достатньою умовою їх рівно великості. c). Необхідною умовою збіжності ряду є те, що його загальний доданок повинен прямувати до 0. d). На 3 діляться ті числа, у яких сума цифр ділиться на 3. e). Для того, щоб послідовність була збіжною, необхідно, щоб вона була обмеженою. 94 4. ОСНОВИ ТЕОРІЇ АЛГОРИТМІВ 4.1. ПОНЯТТЯ АЛГОРИТМУ. Змістовне поняття алгоритму належить до основних понять сучасної математики та інформатики. Це поняття поряд з іншими поняттями (множина, конструктивний об'єкт тощо) не означається через простіші поняття, а описується на прикладах. Під алгоритмом у математиці на змістовному (інтуїтивному) рівні розуміють скінченну впорядковану послідовність точно визначених дій (інструкцій, операцій, команд), виконання яких у вказаному порядку дає можливість розв'язати будь-яку конкретну задачу із деякого даного класу задач. Термін "алгоритм" походить від імені великого середньоазіатського вченого IX століття ал-Хорезмі, який зробив значний внесок у розвиток різних методів обчислень. Значна частина змісту шкільної математичної освіти так чи інакше пов'язана з оволодінням учнями різними алгоритмами. Вузівський курс математики значно розширює алгоритмічні можливості самої математики та її практичного застосування. Не тільки в математиці, а і в інших науках та різних сферах людської діяльності алгоритмічні процеси займають значне, а в багатьох випадках і вирішальне місце. Уважний аналіз відомих алгоритмів дає можливість вказати такі основні загальні характерні риси (властивості) алгоритмів: 1). Фінітність алгоритму – алгоритм є скінченним об’єктом, що є необхідною умовою його реалізації на машині. 2). Дискретність алгоритму – алгоритмічний процес реалізується послідовним виконанням кроків, по одному за одиницю часу (алгоритм виконується в дискретному часі). 3). Масовість алгоритму – кожен алгоритм призначений не для виконання одного завдання, а для певного класу однотипних задач. 4). Елементарність алгоритму - кожна елементарна операція (такт) алгоритму має формальний характер і може виконуватися автоматично (обчислювачем чи машиною) без урахування її змісту. 5). Результативність алгоритму, тобто скінченність процесу перетворення вхідних даних. Застосування алгоритму до конкретного набору 95 вхідних даних завжди завершується одержанням певного результату - розв'язку задачі. За допомогою алгоритму (якщо він реалізований коректно) кожен конкретний результат отримується за певну скінченну кількість кроків для початкових даних, взятих з певної множини. Тоді кажуть, що для таких початкових даних алгоритм застосовний. Якщо, для якихось початкових даних алгоритм працює необмежено, до кажуть, що до такого набору початкових даних він незастосовний. Відкриття алгоритму, як самостійного поняття не можна змішувати з відкриттям формальних моделей алгоритму. Такі моделі утворені для формального уточнення інтуїтивного поняття алгоритму. До таких формальних моделей відносяться: машина Тьюрінга, нормальні алгоритми Маркова, машини з натурально значними регістрами, машини Поста та ін. Іншим підходом до формального уточнення алгоритму є опис певних класів функцій, для яких існує алгоритм знаходження функції за значеннями її аргументів (рекурсивні функції та ін.). 4.2. НОРМАЛЬНІ АЛГОРИТМИ Розглянемо алгоритмічну систему, що задає клас математично точно визначених алгоритмів, які називаються нормальними алгоритмами. Таке уточнення змістовного поняття алгоритму було запропоноване російським математиком А.А. Марковим на початку 50-х років XX ст. Нормальні алгоритми - це окремий клас алфавітних операторів, які задаються конструктивно, а значить нормальний алгоритм переробляє вхідне слово в деякому алфавіті у вихідне слово в тому ж самому чи іншому алфавіті. В нормальних алгоритмах використовується тільки один тип операторів дії - оператори підстановки, і один тип операторів розпізнавання - оператори розпізнавання входження одного слова в інше слово. Для детального опису цих операторів розглянемо ряд понять. Нехай і два слова в деякому алфавіті. Кажуть, що слово входить в слово , якщо слово можна представити у вигляді 2 1 де 1 і 2 - деякі слова (можливо і пусті). Знайдене входження слова в слово називається першим зліва (або просто першим) входженням, якщо в представленні слова у вигляді 2 1 , слово 1 має найменшу можливу довжину серед всіх подібних представлень слова 96 Розпізнавач входження задається фіксацією деякого слова , а зміст його застосування полягає в тому, що для будь-якого заданого слова 1 перевіряється умова - входить чи ні слово 1 в слово Оператор підстановки задається виразом виду: 1 1 . Робота його полягає в тому, що він здійснює підстановку слова 1 замість першого зліва входження 1 в задане слово . Наприклад, якщо 1 є першим зліва входженням в слово q p 1 , то після застосування оператора підстановки 1 1 слово перетворюється в слово q p 1 . Домовимось перше зліва входження виділяти за допомогою круглих дужок. Тоді, наприклад, перше входження слова xy 1 в слово xxxyyxxyy виділимо так: yxxyy xy xx ) ( Якщо ліва частина підстановки 1 1 , тобто слово 1 входить у задане слово , то кажуть, що підстановка 1 1 застосовна до слова . Якщо ж ліва частина підстановки 1 1 не входить у задане слово , то кажуть, що підстановка 1 1 незастосовна до слова Зауважимо, що в нормальних алгоритмах крім звичайних підстановок виду 1 1 можуть використовуватися і так звані заключні підстановки, які записуються у вигляді 1 1 (замість стрілки пишемо стрілку з крапкою). Після виконання будь-якої заключної підстановки дія алгоритму припиняється. Нормальний алгоритм - це алгоритм, що задається впорядкованою скінченною сукупністю підстановок, які застосовуються до вхідного слова у відповідності з такими правилами: 1). Перевірку застосовності підстановок до перетворюваного слова на будь-якому етапі його переробки треба починати з першої підстановки. 2). Якщо вона застосовна до слова, то після її виконання знову переходимо до п.1). 3). Якщо жодна з перших k підстановок незастосовна до слова, а (k+1)- ша застосовна, то після її виконання знову переходимо до п.1). 4). Процес перетворення вхідного слова продовжується доти, поки не дістанемо слово, до якого жодна з підстановок незастосовна або поки до слова не буде застосовна одна з заключних підстановок. Сукупність підстановок, якими визначається алгоритм, називають схемою нормального алгоритму. Підстановки схеми або нумеруються, або послідовно записуються в колонку зверху вниз чи в рядок через кому. 97 1 1 ( ) , : ( ) n n S Зауваження. Будь-який нормальний алгоритм може бути заданий спеціальною граф-схемою, вузли якої, крім вхідного і вихідного, містять тільки оператори підстановки. Функціонування такої граф-схеми здійснюється у відповідності з п.1)-п.4) роботи нормального алгоритму. Слід відмітити, що застосування в схемах нормальних алгоритмів поряд із звичайними і заключних підстановок є необхідною умовою універсальності таких алгоритмів, тобто можливості реалізації ними будь-яких алгоритмів як алфавітних операторів, що задаються скінченним числом правил. Покажемо необхідність використання заключних підстановок. Насамперед відмітимо, що коли нормальний алгоритм U, в схему якого не входять заключні підстановки, застосовний до заданого слова , то виконується умова: ) ( )) ( ( U U U , тобто результат дії такого алгоритму U на вхідне слово є слово ) ( U , до якого уже не застосовна жодна підстановка схеми алгоритму U. Простим прикладом алгоритму, що не задовольняє цій умові, є алгоритм 1 U , який до будь- якого слова приписує зліва лише одну букву a : a U ) ( 1 . Тоді aa a U U U ) ( )) ( ( 1 1 1 і вказана вище умова не виконується. Отже, цей алгоритм не може бути реалізований нормальним алгоритмом, в схемі якого немає заключних підстановок. В той же час легко переконатися, що цей алгоритм реалізується нормальною схемою, яка містить одну заключну підстановку: a . Застосування цієї підстановки до будь-якого слова переводить його в слово a і робота алгоритму на цьому припиняється. Покажемо також, що неможливо обмежитись тільки заключними підстановками. Дійсно, дія нормального алгоритму, в схему якого входять лише заключні підстановки, складається з одноразового застосування тільки однієї з таких підстановок. А тому довжина вихідного слова ) ( U відрізняється від довжини вхідного слова скінченним числом n, що не залежить від довжини вхідного слова . Це число n визначається як максимум модулів різниць між довжинами слів у лівій і правій частинах підстановок алгоритму U. В той же час існують алгоритми, для яких різниця між довжинами вхідного і вихідного слів залежить від довжини вхідного слова і може бути як завгодно великою. Наприклад, таким є алгоритм подвоєння слів ) ( 2 U . Отже, такий алгоритм не 98 можна реалізувати нормальним алгоритмом із схемою, що складається тільки із заключних підстановок (див. вправу 4.18). Отже, якщо до алгоритмічної системи, побудованої на використанні нормальних алгоритмів, пред'являти вимогу універсальності (можливості побудови нормального алгоритму, еквівалентного будь-якому наперед заданому алгоритму), то необхідною умовою такої універсальності є використання обох видів підстановок - як заключних, так і звичайних. Ця умова є також і достатньою, тобто можна сформулювати так званий принцип нормалізації (гіпотеза А.А. Маркова). Принцип нормалізації. Для будь-якого алгоритму в довільному скінченному алфавіті А можна побудувати еквівалентний йому нормальний алгоритм над алфавітом А, або коротко: всякий алгоритм нормалізований. По суті, принцип нормалізації уточнює поняття будь-якого алгоритму через поняття нормального алгоритму. Згідно з принципом нормалізації кожного разу, коли постає питання про можливість алгоритмізувати той чи інший процес, його можна замінити питанням про можливість реалізації цього процесу у вигляді нормального алгоритму. Дати строге математичне доведення принципу нормалізації неможливо, оскільки поняття будь-якого алгоритму не є строго математичним. Тому до його обґрунтування слід підходити так, як це робиться при обґрунтуванні природничих законів, опираючись на практичний досвід та експеримент. Справедливість принципу нормалізації базується на таких ідеях. 1). Всі відомі до цього часу алгоритми є нормалізованими. Оскільки на протязі довгої історії розвитку точних наук було розроблено багато різних алгоритмів, то цей факт є досить переконливим в підтвердження принципу нормалізації. 2). Всі відомі в наш час способи композиції алгоритмів (суперпозиція, об'єднання, розгалуження, ітерація тощо), які дають можливість будувати нові алгоритми із уже відомих, приводять знову до нормалізованих алгоритмів. 3). Виявилось, що всі відомі різні строго математичні універсальні алгоритмічні системи (нормальні алгоритми, рекурсивні функції, машини Тюрінга та ін.) рівносильні між собою, тобто для всякого алгоритму в одній алгоритмічній системі можна побудувати еквівалентний йому алгоритм в іншій алгоритмічній системі. Таким чином, всі відомі алгоритмічні системи приводять, 99 по суті (з точністю до еквівалентності), до одного і того ж класу алгоритмів. Цей факт свідчить про те, що сучасна теорія алгоритмів охоплює надзвичайно широкий клас (якщо не всі) конструктивно визначені алфавітні оператори. Приклад 1. Нормальний алгоритм 1 U в алфавіті } , { b a A заданий схемою: a bb b aa aa bab Знайти результат дії цього алгоритму на слово abaaabb Перша підстановка до незастосовна, а друга - застосовна. Виконавши її, одержимо слово abbabb 1 . До 1 застосовною є перша підстановка. Виконавши її, дістанемо слово abaab 2 . До 2 перша підстановка незастосовна. Застосувавши до 2 другу підстановку, матимемо слово abbb 3 . Перші дві підстановки до слова 3 будуть незастосовні. Виконавши третю підстановку, прийдемо до слова aab 4 . До одержаного слова 4 перша підстановка незастосовна. Виконавши далі послідовно другу, а потім третю підстановки схеми, одержимо результат: a abaaabb U ) ( 1 , бо жодна підстановка до слова a уже незастосовна. Приклад 2. В алфавіті } , , { c b a A нормальний алгоритм 2 U заданий такою системою підстановок: bc cb ac ca ab ba Знайти ) ( 2 acbcab U Коротко роботу алгоритму опишемо наступним чином: 1 2 3 4 5 6 ( ) , ; ( ) , ; ( ) , ; ( ) , ; ( ), ; ( ) , ; acb ca b ca ac ac ba cb ba ab a ca bcb ca ac aa cb cb cb bc aabc cb cb bc aab cb c cb bc aabbcc До слова 6 aabbcc жодна підстановка не застосовна, отже aabbcc acbcab U ) ( 2 Детальний аналіз змісту підстановок цього алгоритму приводить до висновку, що він в будь-якому слові, заданому в алфавіті } , , { c b a , впорядковує його букви в алфавітному порядку. |