- •Математическая логика и теория алгоритмов
- •11. Понятие об алгоритмах. Схемы алгоритмов
- •11.1. Понятие об алгоритме и теории алгоритмов
- •11.2. Схемы алгоритмов
- •11.3. Рекурсивные функции
- •11.4. Машина Тьюринга
- •11.5. Машина Поста
- •11.6. Нормальные алгорифмы а.А. Маркова
- •11.7. Универсальная абстрактная машина
- •11.8. Разрешимость в теории алгоритмов. Проблема самоприменимости
- •11.9. Сложность алгоритма
- •11.10. Представление схемы алгоритма эквивалентным автоматом
- •11.11. Представление схемы алгоритма микропрограммой с двумя типами микрокоманд
- •12. Элементы формальной логики
- •12.1. Предмет формальной логики
- •12.2. Понятие и его виды
- •12.3. Отношения между понятиями
- •12.4. Операции над понятиями
- •12.5. Суждение и его характеристика
- •Модальные и категорические суждения.
- •Простые категорические суждения.
- •Виды простых категорических суждений.
- •Распределение терминов в простом категорическом суждении.
- •Логический квадрат.
- •13. Умозаключение
- •13.1. Виды умозаключений
- •13.2. Непосредственное умозаключение
- •Умозаключения путем противопоставления предикату.
- •13.3. Опосредованное дедуктивное умозаключение. Фигуры силлогизма
- •Фигуры пкс.
- •Модусы пкс.
- •13.4. Дополнительные виды силлогизмов
- •13.5. Индуктивные умозаключения. Математическая индукция
- •14. Логика высказываний
- •14.1. Семантика логики высказываний
- •I закон – тождества.
- •14.3. Формализация высказываний
- •14.4. Интерпретации, разрешимость, выполнимость, общезначимость
- •14. 5. Логическая равносильность. Законы логики
- •14.6. Формы представления формул логики высказываний
- •14.7. Проблема дедукции в логике высказываний
- •15. Проверка правильности логических выводов. Метод резолюций
- •15.1. Закон контрапозиции
- •15.2. Логическое следование. Проверка правильности логических выводов
- •15.3. Силлогизмы в логике высказываний
- •Разделительно-категоричные силлогизмы.
- •16. Синтаксис и семантика языка логики предикатов
- •16.1. Понятие предиката
- •16.2. Кванторы и связанные переменные
- •16.3. Синтаксис языка логики предикатов. Формулы логики предикатов и формализация суждений
- •16.4. Семантика формул логики предикатов
- •Общезначимость, выполнимость, невыполнимость.
- •17. Тождественные преобразования формул логики предикатов
- •17.1. Операции над предикатами
- •17.2. Основные равносильности логики предикатов
- •Отрицание предложений с кванторами.
- •17.3. Тождественные преобразования формул
- •17.4. Универсум Эрбрана
- •18. Использование метода резолюций в логике предикатов
- •18.1. Подстановка и унификация
- •18.2. Резольвенция и факторизация
- •18.3. Метод резолюций в логике предикатов
- •18.4. Принцип логического программирования
- •19. Логические исчисления
- •19.1. Понятие о формальных теориях
- •19.2. Исчисление высказываний
- •19.3. Исчисление предикатов
- •19.4. Система натурного вывода
- •19.5. Понятие о математической лингвистике
- •19.6. Формальный язык
- •19.7. Формальные грамматики и их свойства
- •19.8. Теоремы Гёделя
- •20. Неклассические логики
- •20.1. Современные модальные логики
- •20.2. Понятие о теории неопределенности
- •20.3. Элементы теории нечетких множеств и нечеткая логика
- •20.4. Нечеткие алгоритмы
- •Литература
- •Приложение 1 Варианты контрольных заданий по дисциплине «Дискретная математика»
- •Приложение 2 Варианты контрольных заданий по дисциплине «Математическая логика»
11.5. Машина Поста
Эмиль Пост – молодой американский математик – в 1936 г. предложил эту модель практически одновременно с А. Тьюрингом
В его машине тоже имеется бесконечная лента и головка. Лента разделена на ячейки. В каждой ячейке записан один символ из фиксированного алфавита. В любой момент времени машина обрабатывает ровно одну ячейку.
Машина Поста работает под управлением программы. Программа состоит из команд. Команды отличаются от команд машины Тьюринга. Если у Тьюринга все команды одного типа и похожи на функции переходов-выходов автомата, то у Поста команды больше напоминают машинные команды современных ЭВМ. Команды машины Поста состоят из трёх частей (полей) [7]:
1. Номер команды.
2. Операция.
3. Отсылка (номер следующей команды).
Команды нумеруются с 1. Первой выполняется команда 1.
Операции:
1. → – движение на одну клетку вправо (R).
2. ← – движение на одну клетке влево (L).
3. S – запись в обозреваемую ячейку, при этом предыдущее значение ячейки теряется (S – произвольный символ алфавита).
4. Ветвление
Si – символ в ячейке, М – номер следующей команды.
5. Стоп: HLT (ЕND).
При ветвлении символы Si должны быть различны, но не обязательно использовать весь алфавит. Если Si есть в ячейке, то выполняется команда Mi, при этом головка не перемещается и в клетку ничего не записывается. Если ни один символ не совпадает – происходит так называемая безрезультатная остановка.
Пример 1. Алфавит А: {1,λ}, где λ – пустой символ, как и в машинах Тьюринга.
1. R,2;
2. 1,1.
Это программа заполнения ленты символами 1, т.е. пустой ленты, в которой во всех ячейках – λ.
Пример 2. Прибавление символа 1 к числу 11...1, А={λ,1}.
1. R,2;
2.
3. 1,4;
4. HLT.
Это программа так называемого инкремента, то есть число, записанное «зарубками», «черточками», увеличивается на одну «черточку» при движении вправо.
Если же после прибавления двигаться влево к началу числа, как это обычно требуется, то:
4. L,5;
5.
6. λ,7;
7. R,8;
8. HLT.
Если работа алгоритма никогда не закончится над некоторыми исходными данными, то алгоритм неприменим к ним (хотя в примере 1 это и не так).
Алгоритм А над исходными данными X обозначим А(Х) – это результат работы алгоритма. Результат не определен, если А неприменим к Х.
Э. Пост выдвинул предположение, что для всякого алгоритма, в котором исходными данными и результатами являются слова, существует эквивалентная ему машина Поста.
Постовые алгоритмы – это алгоритмы, работающие со словами. В принципе, все математические объекты можно закодировать в виде слов.
11.6. Нормальные алгорифмы а.А. Маркова
А.А. Марков (1903-1979 гг.) – советский математик, занимавшийся математической логикой и конструктивной математикой разработал так называемые нормальные алгорифмы (это название используется только применительно к модели Маркова), основанные на полусистемах Туэ (ассоциативное исчисление, разработанное шведским математиком Акселем Туэ). Задаётся конечный алфавит A и конечное множество подстановок P. Работа алгоритма состоит из выполнения двух операторов: распознавателя и подстановки [36].
Оператор-распознаватель находит вхождение левой части подстановки в слово I, а оператор-подстановка заменяет это вхождение правой частью подстановки.
Совокупность всех слов в данном алфавите вместе с системой подстановок – ассоциативное исчисление.
Нормальный алгорифм останавливает процесс в случаях:
1. Подходящая подстановка не найдена.
2. Применена последняя подстановка.
Пример. А={0,1}.
Система подстановок Р:
где – обозначает последнюю подстановку.
Пусть I=0100011.
Тогда с учетом первого вхождения левой части второй подстановки (00→1) в слово I, получаем: 011011. Далее, применяя подстановку (110→1), получим 0111. Наконец, применив подстановку (111→0 ), получаем результат 00. Конец работы алгоритма.
По существу, это универсальная форма задания любого алгоритма. Такая модель послужила основой обработки символьной информации. Это одна из немногих моделей разработанных в нашей стране и получивших признание в мире.
По существу это последовательные преобразования входных слов, составленных из символов конечного алфавита.
Различные формализации понятия алгоритмы, предложенные разными авторами, оказались в точности эквивалентными.