Логика. логіка. Математична логіка та теорія алгоритмів
 Скачать 1.6 Mb.
|
|
Запитання для самоконтролю 1. Дайте визначення машини Тьюрінга. 2. Назвіть основні складові елементи МТ? 3. Як визначається команда МТ. 4. Що таке функціональна схема МТ? 120 5. Що таке конфігурація МТ? 6. Що таке стандартна початкова конфігурація МТ? Фінальна конфігурація МТ? 7. Як змінюється конфігурація МТ при виконанні команди МТ відповідного типу? 8. Дайте визначення еквівалентних МТ. 9. Що такє МТ-обчислювана функція? 10. Сформулюйте гіпотезу Тьюрінга? 11. В чому суть УМТ? ВПРАВИ 4.28. Перевірити, що МТ, яка працює за наведеною нижче ФС, залишає незмінним усяке парне число 2n, а всяке непарне число 2n+1 перетворює в число 2n. Числа на стрічці записуються в алфавіті } {I Початкова конфігурація: 0 n g I . Функціональна схема: Q A 0 g 1 g 2 g I ІП 1 g ІП 0 g Н! Н! Л 2 g 4.29. Побудувати МТ, яка перетворює кожне натуральне число n, записане в алфавіті {I}, в число n+3. 4.30. Скласти ФС машини Тьюрінга, яка потроює натуральні числа. 4.31. Побудувати МТ, яка б перетворювала кожне натуральне число n, записане в алфавіті {І}, в число n+k, де k - фіксоване натуральне число, записане в тому ж алфавіті. 4.32. Скласти ФС такої МТ, яка перетворює будь-яке натуральне число п в частку від ділення цього числа на два. 4.33. Побудувати МТ, яка додавала б раціональні дроби з однаковими знаменниками. 4.34. Побудувати МТ, яка перетворює будь-яке натуральне число n в остачу від ділення цього числа на п'ять. 4.35. Нехай в алфавіті } , { b a A задані слова Р і Q . Скласти ФС МТ, яка слово Q P переробляє в слово Р. 121 4.36. Побудувати МТ, яка будь-яке слово R Q P , де P, Q і R - слова в алфавіті } , , { c b a A , перетворює в слово Р. 4.37. Знайти ФС МТ, що перетворює кожне натуральне число n записане в алфавіті {I} в число: а) 3 2 n ; б) 2 1 3n 4.38. Побудувати МТ, що знаходить n m , де n і m - натуральні числа, записані в алфавіті {I}. 4.39. Скласти ФС МТ, яка реалізує перетворення натуральних чисел, записаних в алфавіті {I}, у запис цих самих чисел у двійковій системі числення. 4.40. Побудувати МТ, яка перетворює слово 1 0 00 11 разів k в слово 11 0 00 1 разів k (перенесення крайньої лівої одиниці в кінець слова). 4.5. МАШИНИ З НАТУРАЛЬНОЗНАЧНИМИ РЕГІСТРАМИ Машина з натуральнозначними регістрами (скорочено МНР) є ідеалізованою моделлю комп'ютера. МНР містить, взагалі кажучи, нескінченну кількість регістрів, вмістом яких є натуральні числа. Регістри нумеруємо натуральними числами, починаючи з 0, позначаючи їх R 0 , R 1 , R 2 , ..., R п ,... Вміст регістру R п позначаємо r п . Послідовність (r 0 , r 1 , ..., r п , ...) вмістів регістрів МНР назвемо конфігурацією МНР. МНР може змінити вміст регістрів згідно виконуваної нею команди. Скінченний список команд утворює програму МНР. Команди програми послідовно нумеруємо натуральними числами, починаючи з 1. Номер команди в програмі називатимемо адресою команди. МНР-програму з командами I 1 , I 2 ,..., I к будемо позначати I 1 I 2 ,...I к Довжину (кількість команд) МНР-програми Р позначимо |Р|. Команди МНР бувають наступних чотирьох типів. Тип 1. Обнулення п-го регістру Z(п): r п := 0. Тип 2. Збільшення вмісту п-го регістру на 1 S(п): r п := r п +1. Тип 3. Копіювання вмісту регістру Т(т,п): r п := r т (при цьому r т не змінюється). Тип 4. Умовний перехід J(т,п,q): якщо r п =r т , то перейти до виконання q-ї команди, інакше виконувати наступну за списком команду програми. 122 Число q в команді J(т,п,q) назвемо адресою переходу. Команди типів 1-3 називають арифметичними. Після виконання арифметичної команди МНР повинна виконувати наступну за списком команду програми. Виконання однієї команди МНР назвемо кроком МНР. Зауважимо, що формальними моделями алгоритмів є саме МНР-програми, поняття МНР використовується для опису функціонування МНР-програм. Виконання програми МНР починає, перебуваючи в деякій початковій конфігурації, з виконання 1-ї за списком команди. Наступна для виконання команда програми визначається так, як описано вище. Виконання програми завершується (програма зупиняється), якщо наступна для виконання команда відсутня (тобто номер наступної команди перевищує номер останньої команди програми). Конфігурація МНР в момент завершення виконання програми називається фінальною, вона визначає результат роботи МНР-програми над даною початковою конфігурацією. МНР-програми, як моделі алгоритмів, є фінітними об’єктами, тому обмежимося розглядом скінченних конфігурацій. Конфігурацію вигляду (a 0 , a 1 ,..., a n , 0, 0, ...), в якій r т = 0 для всіх т>п, назвемо скінченною. Таку конфігурацію позначаємо (а 0 , а 1 , ..., а п ). Зрозуміло, що якщо МНР-програма Р починає роботу над скінченною початковою конфігурацією, то в процесі виконання Р МНР перебуватиме тільки в скінченних конфігураціях. МНР-програми Р та Q назвемо еквівалентними, якщо при роботі над однаковими початковими конфігураціями вони або обидві зупиняються з однаковими фінальними конфігураціями, або обидві не зупиняються. Нехай п {1, 2, 3....}. Кожну програму можна розглядати як алгоритм з множиною можливих початкових даних N n . Застосування такого алгоритму до початкових даних ( х 1 ,..., х n ) полягає в наступному. У початковий момент числа х 1 ,..., х n поміщаються відповідно в регістри R 1, ...,R n при цьому в решті інших регістрів міститься 0. Потім виконуються команди даної програми, починаючи з першої. Один крок роботи алгоритму полягає у виконанні однієї команди. Послідовність кроків роботи алгоритму називається обчисленням. Обчислення завершується, коли в програмі немає команди, яку можна було б виконати. Це може відбутися, якщо 1) виконана остання команда програми, і ця команда була арифметичною; 123 2) при виконанні команди J(т, п, q) виявилось, що r m = r n, але q перевершує число команд в програмі; 3) при виконанні команди J(m, п, q) виявилось, що r m r n , але це була остання команда програми. Завершення роботи алгоритму завжди вважається результативним. Результатом роботи алгоритма є натуральне число, записане в регістрі R 0 у момент завершення обчислення. Таким чином, яким би не було п {1, 2, 3...}, кожна програма обчислює часткову n-місну числову функцію. Означення. Часткова функція f: N n N називається МНР- обчислювальною, якщо існує програма для МНР, яка обчислює цю функцію. Кожна МНР-програма обчислює безліч функцій, заданих на N, але, зафіксовуючи наперед арність функцій (тобто кількість компонент початкових конфігурацій), отримуємо, що кожна МНР-програма обчислює єдину функцію заданої арності. Зауважимо, що кожну функцію, задану на N, можна трактувати як предикат, інтерпретуючи значення 1 та 0 як істинні значення "T" та "F" відповідно. В цьому випадку в ролі предикату виступає його характеристична функція. Приклад 1. МНР-програма для функції : y x 1) 5 , 2 , 1 J 2) 0 S 3) 2 S 4) 1 , 0 , 0 J Приклад 2. МНР-програма для функції : y x 1) 5 , 1 , 0 J 2) 1 S 3) 2 S 4) 1 , 0 , 0 J 5) 0 , 2 T Приклад 3. МНР-програма для функції : 2 / x 1) 7 , 2 , 0 J 2) 2 S 3) 7 , 2 , 0 J 124 4) 2 S 5) 1 S 6) 1 , 0 , 0 J 7) 0 , 1 T Приклад 4. МНР-програма для всюди невизначеної функції : 1) 1 , 0 , 0 J Приклад 5. МНР-програма для функції : , : y x y x f 1) 7 , 1 , 0 J 2) 6 , 2 , 0 J 3) 1 S 4) 2 S 5) 1 , 0 , 0 J 6) 2 Z 7) 0 , 2 T Приклад 6. МНР-програма для функції : , : y x y x f 1) 9 , 1 , 3 J 2) 6 , 2 , 0 J 3) 2 S 4) 4 S 5) 2 , 0 , 0 J 6) 2 Z 7) 3 S 8) 1 , 0 , 0 J 9) 0 , 4 T Запитання для самоконтролю 1. Що таке МНР? 2. Що тако конфігурація МНР? 3. Що таке програма МНР? 4. Опишіть команди МНР. 5. Як виконується програма МНР? 6. Дайте визначення еквівалентних МНР-програм. 7. Як визначаеться конкатенація стандартних МНР-програм? 125 8. Як визначається обчислюваність функції за допомогою МНР- програми Р? 9. Що таке МНР-обчислювана функція? ВПРАВИ 4.41. Скласти МНР-програми для наступних функцій: 1) y x y x f 2 ) , ( ; 2) z y x z y x f ) ( ) , , ( ; 3) ) ( ) , ( y x nsg y x f ; 4) ) ( ) , ( y x sg y x f ; 5) z y x z y x f ) , max( ) , , ( ; 6) ) , min( ) , , ( z y x z y x f ; 7) ) 2 , max( ) , ( y x y x f ; 8) 3 / ) 1 ( ) ( x x f ; 9) ! ) ( x x f ; 10) y x y x f ) , ( 4.42. Доведіть, що для кожної МНР-програми можна збудувати еквівалентну їй МНР-програму без команд T(m,n) (елімінація команд T(m,n)). 126 СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ 1. Алферова 3.В. Теория алгоритмов. -М: Статистика, 1983. 2. Глушков В.М. Введение в кибернетику. -Киев: Изд.АНУССР, 1964. 3. Глушков В.М. Кибернетика. Вопросы теории и практики. -Москва: Наука, 1986. 4. Игошин В.И. Математическая логика и теория алгоритмов.- Изд-во Саратовського ун-та, 1991. 5. Євладенко В.М., Паращук С.Д. Методичні вказівки до практичних занять з математичної логіки.-Кіровоград:КДПІ, 1990. 6. Євладенко В.М., Халецька З.П., Нарадовий В.В. Математична логіка та теорія алгоритмів: Навчально- методичний посібник. - Кіровоград: Вид-во «КОД», 2009. 7. Калужнін Л.A, Королюк B.C. Алгоритми і математичні машини. -К.: Радянська школа, 1964. 8. Клини С. Математическая логика. М.: Мир, 1973. 9. Лісова Т.В. Математична логіка та теорія алгоритмів: [практикум].–Ніжин: Видавець ПП Лисенко М.М., 2011.- Частина 2. 10. Лиман Ф.М. Математична логіка і теорія алгоритмів.-Суми: Слобожанщина, 1998. 11. Мальцев А.И. Алгоритмы и рекурсивные функции. -М.: Наука, 1986. 12. Мендельсон Э. Введение в математическую логику. М.: Наука, 1971. 13. Марков A.A., Нагорный Н.М. Теория алгоритмов.-М.: Наука, 1984. 14. Олійник А.С., Сущанський В.І. Задачі з математичної логіки та теорії алгоритмів. Луганськ: ЛНПУ імені Тараса Шевченка, 2004. 15. Рамский Ю.С. Логічні основи інформатики: Навч посіб. – К.: НПУ імені М.П. Драгоманова, 2003. 16. Чуб О.Т., Коба В.І. Збірник вправ з курсу "Алгоритми і математичні машини". -К.: Вища школа, 1970. 17. Хромой Я.В. Математична логіка.- К.: Вища школа, 1983. 127 ПРЕДМЕТНИЙ ПОКАЗЧИК Аксіоми числення L 1 51 Алгебра висловлень 6 Алгоритм 94 –уточнення 95 Алфавіт 6, 50, 67, 95 Атомарна формула 8, 64 Булева функція 23 Бінарна резольвента 79 Вивід 53 Вивідність із припущень 53 Висловлення 6 Гіпотеза Тюрінга 118 – Черча 111 Диз’юнкція 7, 60 Досконалий одночлен 18 Еквіваленція 7, 60 Заключна підстановка 97 Заперечення 7, 60 Імплікація 7, 60 Інтерпретація формули 69 Істинність висловлень 6 Квантор загальності 62 – існування 62 Клас булевих функцій 28 Комбінаційна схема 31 Кон’юнкція 7, 60 Кон’юнктивний одночлен 18 Конфігурація МТ 114 Категоричні судження 63 Літерал 7, 79 Логіка предикатів 59 Логічний наслідок 38, 43, 73 – критерій 40, 74 Машина Тьюрінга 113 Метасимволи 49, 50 Метатеорема дедукції 54 Метод резолюцій 79 МНР-програма 121 Множина істинності предиката 60 Нормальний алгоритм 95 – схема 96 Нормальні форми 18 – диз’юнктивна 18 – досконала 19 – зведена 76 – кон’юнктивна 18 – пренексна 76 – стандартна сколемівська 77 2 Область дії квантора 63 Обмежені квантори 88 Окремий випадок формули алгебри висловлень 75 Оператор підстановки 95 – розпізнавання 95 Операція суперпозиції 105, 106 – найменшого кореня 110 – примітивної рекурсії 106 Основні рівносильності 14, 75 Поліном Жегалкіна 26 Правила виводу 46, 55 Правило підстановки 51 Правило MP 51 Правило резолюцій 43, 80 Предикат 59 – тотожно істинний 59 – тотожно хибний 60 – виконуваний 60 – спростовний Предметна змінна 67 – вільна 63 – зв’язана 63 – частково зв’язана 63 Принцип нормалізації 98 Рекурсивна функція 104 Рівносильні формули 14, 74 – ознака 14 РК-схема 34 Силогізми Арістотеля 74 Сума Жегалкіна 25 Стрілка Пірса 25 Схеми логічного слідування 40, 41 Таблиця істинності 7, 9 Терм 68 Теорема числення висловлень 52 Уніфікатор 81 Формула алгебри висловлень 8 – виконувана 10, 69 – нейтральна 10 – логіки предикатів 68 – логічно загальнозначуща 69 – суперечність 10, 77 – тавтологія 9, – тотожно хибна 60 Функціональна повнота 26, 29 Функціональна схема МТ 115 Числення висловлень L 1 49 Штрих Шеффера 25 |