Операция минимизации.

Операция минимизации: M_y[f(x₁... x_n-1,y)= x_n] – операция минимизации по последней переменной . f(x₁... x_n-1,y)= x_n Фиксируем x₁... x_n-1, и решаем перебором, подставляя вместо y чисел 0,1,2... Тогда возможны случаи:

1. Если на каком-то шаге получится неопределенное выражение, то считаем, что операция минимизации на наборе x₁...x_n не определена.

2. На каждом шаге значении левой части определено, но из вида уравнения ясно, что равенство никогда не будет выполнено. Значение операции минимизации на данном наборе не определено.

3. При подстановке вместо y чисел 0,1,2…y-1 левая часть определена, но равенство не выполнялось, а при подстановке y стало верным, то y – значение операции минимизации на наборе x₁…x_n.

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

Теорема (о вычислимых функциях): Множество функций, вычислимых по Тьюрингу совпадает со множеством функции, вычислимых по Маркову и совпадает со множеством частично рекурсивных функций.

Док-во: слишком большое для приведения.

Предикаты Основные понятия

Высказывание – предположение, выраженное на некотором языке, которому можно приписать значение истина (1) или ложь (0).

Предикат – функция f(x), с областью прибытия {0,1}.

Если P(x₁..x_n)1, то предикат называется тождественно истинным.

Если Р(x₁..x_n)0, то предикат называется тождественно ложным. Предикат называется выполнимым, если найдется набор аргументов, на котором он принимает значение истина: P(x₁..x_n)=1.

Операции над предикатами

Набор операций:  →  и др.

Пусть дан предикат P(x₁..x_n). Покажем некоторые операции, которые можно выполнить:

• Отрицание предиката. тогда и только тогда, когда предикат P(x₁..x_n)=0;

• Импликация. Пусть даны предикаты P(x₁..x_n) и Q(x₁..x_n). Импликацией P и Q будем­­­­­­ называть предикат PQ, который принимает значение 0 тогда и только тогда, когда P(x₁..x_n)=1, а Q(x₁..x_n)=0;

• Квантификация.  - квантор общности.  - квантор существования. Пусть имеется предикат P(x,y₁,y₂…y_n), зависящий от n+1 переменной. Рассмотрим предикат _xP(x,y₁,y₂…y_n)=Q(y₁,y₂…y_n) Предикат Q(x₁…x_n) принимает значение 1, когда P(y,a₁…a_n)1, т.е Q(a₁…a_n)=1  P(x,a₁…a_n)1. Если на тот же предикат P навесить квантор _х, то _хP(x,y₁,y₂…y_n)=T(y₁,y₂…y_n), T(a₁…a_n)=1  P(х,a₁…a_n) – выполним, T(a₁…a_n)=0 P(x,a₁…a_n)0.

Операция навешивания квантора справедлива для любой переменной.

Пример: _х(xy=-1)=T(y).

T(1): x1=-1 – выполним => T(1)=1;

T(0): x0=-1 – не выполним => T(0)=0;

Теорема (о представлении квантора общности через конъюнкцию): пусть дан предикат P(x,y₁,y₂…y_n), где x{a₁…a_k}. Тогда

_xP(x,y₁,y₂…y_n)=P(a₁,y₁,y₂…y_n)P(a₂, y₁,y₂…y_n)…P(a_k, y₁,y₂…y_n).

Док-во: зафиксируем набор аргументов b₁…b_n так, чтобы левая часть приняла значение истина. Получаем: _хP(х,b₁…b_n)=1  P(х,b₁...b_n)1  P(a₁,b₁...b_n)=1, P(a₂,b₁...b_n)=1… P(a_k,b₁...b_n)=1  P(a₁,b₁...b_n)P(a₂,b₁...b_n)…P(a_k,b₁...b_n)=1. Т.к. все стрелки , то случай P(х,b₁...b_n)не1 можно не рассматривать. ч.т.д.

Теорема (о представлении квантора существования через дизъюнкцию): пусть дан предикат P(x,y₁,y₂…y_n), где x{a₁…a_k}. Тогда

_xP(x,y₁,y₂…y_n)=P(a₁,y₁,y₂…y_n)P(a₂, y₁,y₂…y_n)…P(a_k, y₁,y₂…y_n).

Док-во: зафиксируем набор аргументов b₁…b_n так, чтобы предикат был выполнимый, но не тождественно истинный. Получаем: _хP(х,b₁…b_n)=1  P(х,b₁...b_n) – выполним  P(a₁,b₁...b_n)=0, P(a₂,b₁...b_n)=0…,P(a_i,b₁...b_n)=1,…P(a_k,b₁...b_n)=0  P(a₁,b₁...b_n)P(a₂,b₁...b_n)…P(a_k,b₁...b_n)=1. ч.т.д.

Теорема (о тождественной истинности предиката): пусть дан предикат P(x,y₁…y_n)1  _xP(x,y₁…y_n)1.

Док-во: P(x,y₁…y_n)1 для любого произвольного набора (a₁,…,a_n) P(x,a₁…a_n)1  _xP(x,a₁…a_n)=1  _xP(x,y₁…y_n)1 (по теореме выше) ч.т.д.

Теорема (о тождественной ложности предиката): пусть дан предикат P(x,y₁…y_n)0  _xP(x,y₁…y_n)0.

Док-во: P(x,y₁…y_n)0  существует такой произвольный набор (a₁,…,a_n), что P(x,a₁…a_n)0  _xP(x,a₁…a_n)=0  _xP(x,y₁…y_n)0. ч.т.д.

Теорема (о перестановке одноименных кванторов): пусть дан предикат P(x,y,z₁…z_n). Тогда справедливы следующие формулы:

_x_y P(x,y,z₁…z_n)= _y_х P(x,y,z₁…z_n); (1)

_x_y P(x,y,z₁…z_n)= _y_x P(x,y,z₁…z_n). (2)

Док-во(1): Пусть есть произвольный набор (a₁…a_n). Тогда _x_yP(x,y,a₁…a_n)=1  _yP(x,y,a₁…a_n)≡ P(x,y, a₁…a_n) ≡ _x P(x,y, a₁…a_n) ≡ _x_yP(x,y, a₁…a_n)=1. ч.т.д.

Док-во(2): Возьмем произвольный набор (a₁…a_n) в качестве z_i. Тогда _x_yP(x,y,a₁…a_n)=0  _yP(x,y,a₁…a_n)0  P(x,y,a₁…a_n)0  _xP(x,y,a₁…a_n)0  _x_yP(x,y,a₁…a_n)=0. ч.т.д.

Теорема (о перестановке разноименных кванторов): _x_y P(x,y,z₁..z_n)  _y_x P(x,y, z₁..z_n) ≡.

Док-во: допустим, найдется такой набор (a₁…a_n), что _x_y P(x,y, a₁…a_n)=1  _y P(x,y, a₁…a_n) – выполним  найдется такое x₀, что _y P(x₀,y, a₁…a_n)=1  P(x₀,y, a₁…a_n)1.

Также, если _y_x P(x,y, a₁…a_n)=0  _x P(x,y, a₁…a_n) 1  найдется y₀ _xP(x,y₀,a₁…a_n)=0  P(x₀,y,a₁…a_n)0.

При y=y₀ получаем P(x₀,y₀,a₁…a_n)=1;

При x=x₀ получаем P(x₀,y₀,a₁…a_n)=0;

Таким образом, получаем, что набора a₁…a_n не существует. ч.т.д.

Теорема (об отрицании кванторов): Пусть дан P(x,y₁,y₂…y_n), тогда справедливы формулы:

Док-во(1): Пусть произвольный набор (a₁…a_n) такой, что  _xP(x,a₁…a_n)=1  P(x, a₁…a_n) ≡  =0. ч.т.д.

Док-во(2): Пусть произвольный набор (a₁…a_n) такой, что  _xP(x,a₁…a_n)=1  P(x, a₁…a_n) – выполним - выполнимый, но не тождественно истинный предикат  =0. ч.т.д.

Теорема (о дистрибутивности квантора общности относительно конъюнкции): Пусть даны предикаты P(x, y₁,y₂…y_n) и Q(x, y₁,y₂…y_n). Тогда справедлива формула:

_x (P(x, y₁,y₂…y_n) Q(x, y₁,y₂…y_n)) = _x P(x, y₁,y₂…y_n) _x Q(x, y₁,y₂…y_n).

Док-во: зафиксируем такой набор (a₁..a_n), что _x (P(x, a₁…a_n) Q(x, a₁…a_n)) =1  P(x, a₁…a_n) Q(x, a₁…a_n) ≡при любом x P(x, a₁…a_n)=1 Q(x, a₁…a_n)=1  _x P(x, a₁…a_n)=1, _x Q(x, a₁…a_n)=1  _x P(x, a₁…a_n) _x Q(x, a₁…a_n)=1. ч.т.д.

Теорема (о дистрибутивности квантора существования относительно дизъюнкции): пусть даны предикаты P(x,y₁,.,y_n) и Q(x,y₁,..,y_n). Тогда справедлива формула:

_x ( P(x,y₁,..,y_n)  Q(x,y₁,..,y_n) ) = _x P(x,y₁,..,y_n)  _x Q(x,y₁,..,y_n).

Док-во: Зафиксируем такой набор (a₁..a_n), что _x(P(x,a₁,..,a_n)Q(x,a₁,..,a_n))=0  P(x,a₁,..,a_n)Q(x,a₁,..,a_n)≡0 (относительно переменной x)  при некоторых x P(x,a₁,..,a_n)=0, Q(x,a₁,..,a_n)=0  _xP(x,a₁,..,a_n)=0, $_xQ(x,a₁,..,a_n)=0 – получено навешивание квантора существования  $_xP(x,a₁,..,a_n)Ú$_xQ(x,a₁,..,a_n)=0. ч.т.д.

Теорема (о полудистрибутивности квантора существования относительно конъюнкции): _x[P(x,y₁,..,y_n) Q(x, y₁,..,y_n)]  _x P(x, y₁,..,y_n) _x Q(x, y₁,..,y_n) ≡

Док-во: Зафиксируем набор (a₁..a_n) такой, что _xP(x, a₁..a_n) _x Q(x, a₁..a_n)≡ 0  _x P(x, a₁..a_n)=0 или _xQ(x, a₁..a_n)=0 P(x, a₁..a_n) ≡0 или Q(x, a₁..a_n) ≡0  _x (P(x, a₁..a_n) Q(x, a₁..a_n)) ≡0. ч.т.д.

Теорема (о полудистрибутивности квантора общности относительно дизъюнкции): "_xP(x,y₁,..,y_n)_xQ(x,y₁,..,y_n)  "_x [P(x,y₁,..,y_n) Ú Q(x,y₁,..,y_n)] =1

Док-во: Пусть (a₁…a_n) такой набор, что "_x P(x,a₁…a_n)  "_x Q(x,a₁…a_n)1  "_x P(x,a₁…a_n)=1 или "_x Q(x,a₁…a_n)=1  P(x,a₁…a_n)  1 или Q(x,a₁…a_n)1  P(x,a₁…a_n)Q(x,a₁…a_n)1  "_x [P(x,y₁,..,y_n) Ú Q(x,y₁,..,y_n)] =1. ч.т.д.