- •Історичні етапи розвитку логічного знання, логіка Давньої Греції.
- •3.Історичні етапи розвитку логічного знання: Логіка Давньої Індії
- •4.Логічні сталі. Логічні вирази. Логічні операції. Таблиця істинності. Логічні операції:
- •5. Закони алгебри логіки. Спрощення логічних функцій.
- •6.Принцип двоїстості булевих функцій.
- •7.Мінімізація булевих функцій.
- •Методи доведення в логіці Буля
- •9.Висловлення. Операція над висловленнями.
- •10. Формули алгебри висловлень. Таблиці істинності формул.
- •11. Тавтології.
- •Перевірити , що формула є тавтологією , можна за допомогою таблиці істинності, але і існують інші методи:
- •12. Рівносильність формул алгебри висловлень.
- •13. Алгебра висловлень. Нормальні форми.
- •14. Логічне слідування на базі алгебри висловлень.
- •15. Методи перевірки тотожної істинності формул числення висловлювань.
- •16. Аксіоматичний метод доведення в логіці висловлень.
- •17. Конструктивний метод доведення в логіці висловлень.
- •18. Метод резолюції доведення в логіці висловлень.
- •19. Вивідність з гіпотези . Теорема дедукції.
- •20 . Зв'язок між формулами висловлень і формулами числення висловлень. Несуперечність, повнота і розв’язність числення висловлень.
- •21. Застосування алгебри висловлень в теорії комбінаційних схем.
- •22. Синтез логічних схем.
- •23. Логіка предикатів.
- •24. Предикати, логічні операції над предикатами.
- •25. Квантори . Кванторні операції над предикатами.
- •26. Формули логіки предикатів.
- •Формули, які спираються на квантори:
- •27. Інтерпитація формул логіки предикатів.
- •28. Рівносильність формул логіки предикатів.
- •29. Нормальні форми в логіці предикатів. Визначення
- •Правило введення квантора існування
- •30. Логічне слідування в логіці предикатів.
- •31. Відношення логічного слідування на множині предикатів.
- •32. Метод резолюції і його застосування в логіці предикатів.
- •33. Подання знань за допомогою логіки предикатів.
- •34. Моделі подання знань і логіка предикатів.
- •35. Поняття про міркування і умовиводи.
- •36. Поняття про аксіоматичний метод побудови теорії
- •40. Формальна арифметика. Теорема Геделя про неповноту
- •41. Класифікація логік.
- •42. Поняття про некласичні логіки
- •43. Алгоритми та їх властивості. Алгоритм
- •44. Обчислювальні функції. Частково рекурсивні функції.
- •45. Гіпотези Черча та Тюрінга
- •46. Машина Тьюрінга.
- •47. Нормальні алгоритми Маркова. Принцип нормалізації.
- •48. Алгоритмічно розв’язанні і нерозв’язані проблеми.
46. Машина Тьюрінга.
Машина Тюрінга являє собою абстрактне уявлення, яке складається з нескінченної стрічки, пристрою керування і лічильної головки. МТ задає словесну функціональну стрічку розбиту на регістри. У кожному регістрі в даний дискретний момент часу знаходиться точно один символ із зовнішнього алфавіту А, є символ який називається порожнім. В різних машинах різні позначення λ, #, 0. А регістр у якому в даний момент знаходиться порожній символ називається також порожнім.
МТ – це структура Т=(S,I,f,s0)
S – скінченна множина станів
І – скінченна множина допустимих символів, або алфавіт машини.
f – програма машини.
Машина Тьюрінга може знаходитись у процесі роботи в різних станах, змінюючи її стрибкоподібно. Серед внутрішніх станів МТ окреме місце посідають такі два : початковий та завершальний. Описувана машина є скінченною, але її можна вважати актуально нескінченною у тому розумінні, що після досягнення будь-якого кінця стрічки завжди може бути додана нова комірка. При цьому у будь – який визначений момент часу довжина стрічки залишається скінченною.
47. Нормальні алгоритми Маркова. Принцип нормалізації.
Нормальні алгоритми Маркова
Алгоритми Маркова або нормальними алгоритмами, є ті, які перетворюють рядки, які задані у будь-якому скінченному алфавіті А, у рядки у тому ж самому алфавіті А. Рядок у алфавіті А — це упорядкована скінченна сукупність символів цього алфавіту.
Нормальний алгоритм задається скінченною послідовністю підстановок.
Підстановка — це упорядкована пара рядків, необов'язково однакової довжини, що розділена символом « », ab . Підстановка є застосовною до вихідного рядка, якщо цей рядок містить як підрядок першу компоненту підстановки.
Застосовують нормальний алгоритм до вихідного рядка таким чином:
1) Із списка підстановок обираємо першу підстановку, яка застосовна до вихідного рядка.
2) Якщо жодна підстановка зі списка підстановок не застосовна до вихідного рядка, то алгоритм припиняє роботу.
3) Застосовуємо підстановку з п. 1 до вихідного рядка, одержуємо результуючий рядок.
4) Якщо виконана підстановка є заключною, то алгоритм припиняє роботу. Інакше переходимо до п. 5.
5) Результуючий рядок вважаємо вихідним і переходимо п. 1.
Aлгоритм може не містити заключних підстановок.
Якщо нормальний алгоритм, не припиняє роботу, а працює нескінченно, то вважається, що він не застосовний до цього вихідного рядка, оскільки не видає результату.
Принцип нормалізації алгоритму, полягає в тому, що будь-який алгоритм в алфавіті А еквівалентний деякому нормальному алгоритму в алфавіті А. Коротко формулюють так: будь-який алгоритм в А нормалізується.
48. Алгоритмічно розв’язанні і нерозв’язані проблеми.
Принцип нормалізації, з одного боку, стверджує існування нормального алгоритму для розв'язку кожної задачі, для якої існує алгоритм в А. З іншого боку, він дозволяє стверджувати, що якщо для розв'язку якої-небудь задачі нормальний алгоритм неможливий (його не існує), то не має сенсу шукати будь-який інший алгоритм, тобто принцип нормалізації є засобом дослідження питання алгоритмічної розв'язності або нерозв'язності задачі.