- •1.Совершенные нормальные формы.Правила приведения к сднф и скнф. Минимизация логических функций.
- •§8. Нормальные формы функций.
- •8.2 Нормальные формы.
- •8.3 Совершенные нормальные формы.
- •8.4 Правила приведения произвольной формулы алгебры логики к совершенной нормальной форме.
- •8.6 Способ составления снф для произвольной формулы алгебры логики по таблице истинности.
- •§ 1. Понятие формулы исчисления высказываний.
- •§ 2. Определение доказуемой (выводимой) формулы.
- •Правила вывода.
- •Определение выводимой (доказуемой ) формулы.
- •Правило сложной (одновременной) подстановки (спп).
- •Правило сложного заключения.
- •Правило силлогизма.
- •Правило контр позиции.
- •Правило снятия двойного отрицания.
- •§4.Понятие выводимости формул из совокупности формул.
- •§5. Понятие вывода.
- •§6. Правила выводимости.
- •H,w├a из совокупности формул : “Если а выводима из н, то она вы- водима из ”.
- •5. Теорема дедукции: h, c├ a .
- •§9.Проблемы аксиоматического исчисления высказываний.
- •2. Проблема непротиворечивости исчисления высказываний.
- •3.Проблема полноты исчисление высказываний.
- •4.Проблема независимости аксиом исчисления высказываний.
- •§1. Недостаточность логики высказываний. Понятие предиката.
- •§2. Логические операции над предикатами.
- •§3. Кванторные операции.
- •Квантор всеобщности.
- •Квантор существования.
- •Отрицание предложений с кванторами.
- •§4.Понятие формулы логики предикатов.
- •§5. Значение формулы логики предикатов.
- •§6. Равносильные формулы логики предикатов.
- •§7. Нормальные формы формул логики предикатов.
- •§8. Общезначимость и выполнимость формул. Проблема разрешимости.
- •§9. Применение языка логики предикатов для записи математических предложений, определений, построения отрицания предложений.
- •9.1 Запись математических предложений и определений в виде формул логики предикатов.
- •9.2. Построение противоположный утверждений.
- •9.3 Прямая, обратная и противоположная теоремы.
- •9.4 Необходимые и достаточные условия.
- •9.5. Доказательство теорем методом от противного.
- •Утверждения о свойствах объектов и отношениях между ними
- •Язык логики предикатов
- •Синтаксис: формулы логики предикатов
- •Семантика: системы и значения формул на их состояниях
- •Реляционные базы данных
- •Реляционная алгебра
- •Теоретико-множественные операции
- •Специальные реляционные операторы
- •Запросы
- •Ограничения целостности
- •Основные определения
- •Тьюрингово программирование
- •Стандартная заключительная конфигурация
- •Односторонние машины Тьюринга
- •Последовательная и параллельная композиции машин Тьюринга
- •Ветвление (условный оператор)
- •Повторение (цикл)
Основные определения
Рассматриваемая в этом разделе модель алгоритмов была предложена английским математиком Тьюрингом в 1937 г. еще до создания современных компьютеров1) Он исходил из общей идеи моделирования работы вычислителя, оперирующего в соответствии с некоторым строгим предписанием. В машине Тьюринга расчленение процессавычисления на элементарные шаги доведено в известном смысле до предела. Элементарным действием является замена одного символа в ячейке на другой и перемещение к соседней ячейке. При таком подходе процесс вычисления значительно удлиняется, но зато логическая структура процесса сильно упрощается и приобретает удобный для теоретического исследования вид.
Машина Тьюринга (м.Т.) состоит из неограниченной в обе стороны ленты, разбитой на ячейки, по которой передвигаетсяголовка машины. Такая "бесконечность" ленты является математической абстракцией, отражающей потенциальную неограниченность памяти вычислителя. Разумеется, в каждом завершающемсявычислении используется только конечная часть этой памяти - конечное число ячеек. В каждой ячейке ленты записан один символ из конечного внешнего алфавита машины . Головка машины представляет конечный автомат, который в каждый момент времени находится в одном из внутренних состояний Q ={q0,q1,... , qn }. На каждом шаге головка в зависимости от своего внутреннего состояния и символа в ячейке, которую она наблюдает, изменяет свое внутреннее состояние и содержимое наблюдаемой ячейки и может сдвинуться на одну ячейку вправо или влево либо остаться на месте.
Дадим более формальное определение.
Определение 9.1. Машина Тьюринга - это система вида
включающая следующие компоненты:
Q ={q0,q1,... ,qn } - внутренний алфавит (алфавит состояний);
- внешний алфавит (алфавит ленты );
P - программа машины, в которой для каждой пары имеется (одна!)команда вида
задает сдвиг головки вправо, влево или на месте;
- начальное состояние;
- заключительное состояние.
Выделим в алфавите специальный пустой символ и будем считать, что во всех ячейкахленты, кроме конечного их числа, в начальный и во все последующие моменты находится пустой символ.
Будем говорить, что некоторый символ стирается, если он заменяется на пустой. Два слова из будем считать равными, если они совпадают после отбрасывания всех пустых символов слева и справа. Например, , но .
Как и для конечных автоматов, программу P можно задавать с помощью таблицы размера n x m, строки которой соответствуют состояниям из Q, а столбцы - символам из входного алфавита в которой на пересечении строки qi и столбца aj стоит тройка qk al C - правая часть команды qi aj -> qk al C.
Определение 9.2. Назовем конфигурацией м.Т. в некоторый момент времени слово K= wл qi ajwп, где - слово на ленте левее текушего положения головки, qi - внутреннее состояние в данный момент, aj - символ, обозреваемый головкой, - слово на ленте правее текушего положения головки.
Будем считать, что слово wл aj wп содержит все значащие символы на ленте. Поэтому, с точностью до описанного выше равенства слов, конфигурация определена однозначно. В частности, если , т.е. пусто, то левее положения головки все ячейки пусты, а если , то правее положенияголовки все ячейки пусты.
Начальная конфигурация - это конфигурация вида q0w, т.е. в начальный момент времени головка в состоянии q0 обозревает первый символ входного слова w. { it Заключительная } конфигурация - этоконфигурация вида w1 qf w2, в которой машина находится в заключительном состоянии qf.
Определение 9.3. Скажем, что конфигурация K= w1 qi aj w2 м.Т. за один шаг (такт) переходит вконфигурацию , если в программе имеется команда qi aj -> qk al Cи при этом,
если С=Н, то w1'=w1, w2'=w2 и a{j'}=al;
если С=Л, то w1=w1' a, a{j'}=a, w2'=al w2 (если то и );
если С=П, то w2=aw2', a{j'}=a, w1'=w1 al (если то и ).
Как обычно, через обозначим рефлексивное и транзитивное замыкание отношения а будет означать, что конфигурация K за n шагов переходит в K'. (Если из контекста ясно, о какой машине идет речь, то индекс будем опускать).
Пример 9.1.
Рис. 9.1. Выполнение команды q3 0 -> q5 1 П
Например, ситуации, представленной на рис.9.1 слева соответствует конфигурация . Предположим, что программа P содержит команду q30 -> q51 П. Тогда после выполнения этойкоманды K перейдет за один шаг в конфигурацию , показанную на этом рисунке справа. Следовательно, .
Определение 9.4. Вычисление м.Т. на входе w - это конечная или бесконечная последовательность конфигураций такая, что K0=q0w - начальнаяконфигурация. Эта последовательность конечна, когда ее последняя конфигурация Kn= v1 qf v2 - заключительная. В этом случае вычисление назовем результативным, а слово v = v1 v2 - его результатом на входе w (всегда будем предполагать, что v не содержит пустых символов слева и справа).
Определение 9.5. Скажем, что м.Т. вычисляет частичную словарную функцию если для каждого слова w из области определения f существует результативное вычисление с результатом , а если f(w) не определена , то вычисление на входе wбесконечно.
Скажем, что две м.Т. и эквивалентны, если они вычисляют одинаковые функции.
Далее мы будем также рассматривать вычисления арифметических функций, т.е. функций с натуральными аргументами, принимающих натуральные значения. Для представления натуральных чисел используем унарное кодирование: число n будет представляться как слово из n палочек |n, а последовательные аргументы будем отделять *.
Определение 9.6. Скажем, что м.Т. вычисляет частичную арифметическую функцию f: Nk -> N, если для любого набора чисел (x1,x2, ... ,xk), на котором f определена, существует результативное вычисление на входе с результатом , а если , то вычисление на соответствующем входе бесконечно.
Аналогичное определение можно дать и для других спосбов кодирования чисел (двоичного, десятичного и др.). Ниже мы покажем, что класс вычислимых функций не зависит от выбора одного из таких кодирований.