Шпаргалка по "Программированию и компьютерам"

 3) Перестановка одноимённых кванторов: "x"y A(x, y) º "y"x A(x, y); $x$y A(x, y) º $y$x A(x, y);

 4) Переименование  связанной переменной: "x P(x) º "y P(y);

 5) А также  основные равносильности алгебры  логики.

13. Приведённая и нормальная формы формул
1. Приведённая форма формулы

 Приведённая формула – формула, в которой  из логических связок используются только отрицание ( Ø ), конъюнкция ( & ) и дизъюнкция ( Ú ), причём отрицание стоит только над предикатными символами.

 Для любой  формулы алгебры предикатов можно  построить равносильную ей приведённую формулу, причём множества свободных и связанных переменных этих формул будут совпадать.

 Алгоритм  получения приведённой формы  формулы:

 Шаг 1. С помощью  основных равносильностей избавиться от импликации ( ® ) и эквиваленции ( « );

 Шаг 2. С помощью законов де Моргана, снятия двойного отрицания и переноса квантора через отрицание получить приведённую формулу.

 Пример: "x$y P(x, y) ® $x"y Q(x, y) º Ø("x$y P(x, y)) Ú $x"y Q(x, y) º $x"y ØP(x, y) Ú $x"y Q(x, y).

2. Нормальная форма формулы

 Нормальная  формула – формула, которая не содержит кванторов, или все кванторы вынесены в начало формулы.

 Для любой  формулы алгебры предикатов можно  построить равносильную ей нормальную формулу, имеющую ту же самую длину, что и исходная формула.

 Алгоритм  получения нормальной формы формулы(Привожу свою реализацию (она неоптимальная, но очень простая)):

 Шаг 1: Построить  приведённую форму формулы;

 Шаг 2: Для  каждой подформулы, содержащей связанные  переменные, осуществить переименование этих переменных, добившить их уникальности в пределах всей формулы;

 Шаг 3: Вынести  все кванторы в начало формулы.

 Пример: $x"y ØP(x, y) Ú $x"y Q(x, y) º $a"b ØP(a, b) Ú $c"d Q(c, d) º $a"b$c"d (ØP(a, b) Ú Q(c, d)). 
 
 
 
 
 
 

 3. Вычислимые функции.  Простейшие функции.  Операции над функциями: суперпозиция функций, схема примитивной рекурсии, оператор минимизации. Примитивно-рекурсивные функции. Частично-рекурсивные и общерекурсивные функции.

14. Вычислимые функции

 Функция f (x₁, …, x_n) является эффективно-вычислимой, если существует алгоритм, т.е. некоторая механическая процедура, которая позволяет найти значение функции f, если известны значения её аргументов.

15. Простейшие функции

 Их 3:

 1) оператор  сдвига: l (x) = x + 1;

 2) оператор  аннулирования (0-функция): 0 (x) = 0;

 3) оператор  проецирования (функция тождества): I_n^m (x₁, …, x_n) = x_m (служит для введения фиктивных переменных) (Например, I₃² (x, y, z) = y).

 Простейшие  функции определены для любого натурального x и являются интуитивно вычислимыми.

16. Операции над функциями: суперпозиция функций, схема примитивной рекурсии, оператор минимизации
1. Суперпозиция функций

 Пусть даны функции  f₁ (x₁, …, x_n), …, f_m (x₁, …, x_n) и j (x₁, …, x_m). Тогда функция y (x₁, …, x_n) = j (f₁ (x₁, …, x_n), …, f_m (x₁, …, x_n)) является суперпозицией функции j (f₁, …, f_m). Операцию суперпозиции можно записать в виде оператора: y (x₁, …, x_n) = S_mⁿ (j, f₁, …, f_m). Если функции f_i и j интуитивно вычислимы, то их суперпозиции также интуитивно вычислимы.

 Пример: Необходимо получить y (x, y)  = j (f₁ (x₁, x₂), f₂ (x), y). Используя операторы аннулирования, проецирования и суперпозиции, получаем: y (x, y) = S₃² (j (x, y, z), f₁ (x, y), S₂¹ (I₂¹ (x, y), f₂ (x), 0 (x)), I₂² (x, y)).

2. Схема примитивной рекурсии

 Пусть даны n-местная функция j (x₁, …, x_n), n+2-местная функция y (x₁, …, x_n, y, z) и n+1-местная функция f (x₁, …, x_n, y). Тогда функция f получена из функций j и y по схеме примитивной рекурсии, если f (x₁, …, x_n, 0) = j (x₁, …, x_n) [т.е. базис рекурсии] и f (x₁, …, x_n, y+1) = y (x₁, …, x_n, y, f (x₁, …, x_n, y)). Если функции j и y интуитивно вычислимы, то функция f также интуитивно вычислима.

 Пример: Записать по схеме примитивной рекурсии функцию  f (x, y) = x + y. Получаем: f (x, 0) = x и f (x, y+1) = f (x, y) + 1 [т.е. y (x, y, y, f(x, y)) = f (x, y) +1].

3. Оператор минимизации

 Для функции  f (x₁, …, x_n, y) зафиксируем значения x₁, …, x_n и найдём минимальное значение y, для которого f (x₁, …, x_n, y) = 0. Для этого служит оператор минимизации (m-оператор): j (x₁, …, x_n) = m_y [f (x₁, …, x_n, y) = 0]. Процедура работы оператора заключается в последовательном вычислении значений f (x₁, …, x_n, i) для i от 0 до ¥, а именно, до тех пор, пока f (x₁, …, x_n, i) не обратится в 0.

17. Примитивно-рекурсивные функции

 Функция называется примитивно-рекурсивной, если она получена из простейших функций с помощью конечного числа операций суперпозиции и примитивной рекурсии.

18. Частично-рекурсивные и общерекурсивные функции

 Функция f (x₁, …, x_n) называется частично-рекурсивной, если она может быть получена из множества простейших функций с помощью конечного числа операций суперпозиции, примитивной рекурсии и m-оператора. Функция f (x₁, …, x_n) называется общерекурсивной, если она частично-рекурсивная и определена при всех значениях аргумента из множества натуральных чисел. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

 4. Функционирование  машины Тьюринга. Конструирование  машин Тьюринга. Композиция  машин. Вычислимые  по Тьюрингу функции.

19. Функционирование машины Тьюринга

 Машина Тьюринга состоит из ленты, управляющего устройства и головки. Лента представляет собой потенциально бесконечный в обе стороны массив, в ячейках которого содержатся символы внешнего алфавита A с выделенным пустым символом a₀ [т.е. символом, находящимся внутри каждой пустой ячейки]. Управляющее устройство управляет работой машины Тьюринга и может находиться в одном из состояний, определённых внутренним алфавитом Q с выделенными начальным состоянием q₁ и конечным состоянием q₀ (попав в q₀, машина останавливается). Головка в каждый момент времени указывает на одну из ячеек ленты и может изменить её содержимое на другой символ алфавита A, переместиться по ленте на одну ячейку влево ( < ) или вправо ( > ), либо остаться на месте ( = ). На каждом шаге работы машина Тьюринга, находясь в некотором состоянии q_s, считывает содержимое текущей ячейки a_i, записывает туда символ a_j, осуществляет сдвиг s и переходит в состояние q_r. В таком случае говорят, что была выполнена команда a_i q_s ® a_j s q_r.

20. Конструирование машин Тьюринга

 Сконструировать машину Тьюринга – значит задать внешний алфавит A, внутренний алфавит Q и составить для неё программу П. Программа машины Тьюринга – совокупность всех её команд, причём у каждой команды пара a_i q_s должна быть уникальна(Для детерминированной машины Тьюринга). Программа может быть представлена в виде таблицы.

 Пример: На ленте  записано натуральное десятичное число. Необходимо сконструировать машину Тьюринга, увеличивающую это число  на 1. Изначально головка указывает  на первую цифру числа. Получаем: A = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a₀}, Q = {q₁, q₂, q₀}. П – см. таблицу.

 Общая идея –  переместить головку на последнюю  цифру числа, и если эта цифра  не 9, то увеличить её на единицу, иначе обратить в ноль и перейти к предыдущей ячейке.

21. Композиция машин

 Композицией машин Тьюринга M₁ = <A₁, Q₁, П₁> и M₂ = <A₂, Q₂, П₂> при условии, что Q₁ Ç Q₂ = Æ, называется машина Тьюринга M = M₁ · M₂ = <A₁ È A₂, Q₁ È Q₂ \ {q₁₀}(q₁₀ – заключительно состояние M₁), П₁ + П₂>, реализующая последовательное выполнение M₁ и M₂. Все вхождения q₁₀ в П₁ заменяются на q₂₁ (q₂₁ – начальное состояние M₂)[т.е. программа второй машины Тьюринга начинает работу в момент окончания работы первой, происходит передача управления].