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

Предикатом называется любое выражение содерж переменную при подстановке значений которых оно обращается в высказывание которое принимает значение 0 или 1.

Множество различных наборов значений входящих в предикаты называют областью определения предиката.

Предикат принимает значение:

1) Тождеств истинно – это предикат который принимает значение 1 при любых наборах значений входящих в него переменных.

2) Тожд ложн – это предикат который принимает значение 0 при любых наборах значений входящих в него переменных.

3) Выполнимый – это предикат который принимает значение 1 хотя бы на одном наборе значений входящих в него переменных.end

Множество значений на которых предикат равен 1 назыв областью определения истинности предиката.

Предикаты называютcя равносильными если они принимают одинаковое значение при соответствующих значениях переменных.

Над предикатами можно выполнять все действия что и над функциями. (отриц, \/.,/\, =>, <=>)

Конъюнкция двух предикатов тождественно истинна тогда и только тогда, когда оба данных предиката тождественно истинны.(остальные операции аналогично)

Квантор существования можно применять к многомерным предикатам. Однократное применение квантора к одной из n переменных а- мерного предиката порождает (n-1) - мерный предикат.

Пусть А(х,у)=(х+у > 1) двухместный предикат определённый на множестве R.

Тогда из него связыванием переменных х и у можно получить восемь высказываний:

1 " х " у(х + у > 2) – “Для всяких действительных чисел х и у их сумма больше двух”.

2 " у " х(х + у > 2) – “Для всяких действительных чисел у и х их сумма больше двух”.

3 $ х $ у(х + у > 2) – “Существуют действительные числа х и у, сумма которых больше двух”.

4 $ у $ х(х + у > 2) – “Существуют действительные числа у и х, сумма которых больше двух”.

5 " х $ у(х + у > 2) – “Для всякого действительного числа х существует действительное число у, что их сумма больше двух”.

6 " у $ х(х + у > 2) – “Для всякого действительного числа у существует

действительное число х, что их сумма больше двух”.

7 $ х " у (х+у>2) – “Существует действительное число х, что для всякого действительного числа у их сумма больше двух ”.

8 х (х+у>2) – “Существует действительное число у, что для всякого

действительного числа х их сумма больше двух ”.

Законы де Моргана для кванторов

1) ;

2) ;

Законы пронесения кванторов через конъюнкцию

1 ) x(A (x) ·B (x))=( xA (x))·( xB (x));

2) x (A (x)· P)=( xA (x))· P.

Законы пронесения кванторов через дизъюнкцию

1 ) = ;

2 ) = ;

Законы пронесения кванторов через импликацию

1) = ;

2) = ;

3) = ;

4) = ;

Законы коммутативности для кванторов

1) = ;

2) .

Машина Тьюринга

 

Машина Тьюринга есть математическая (вообразимая) машина, а не машина физическая. Машина Тьюринга состоит из ленты, управляющего устройства и считывающей головки.

Лента разбита на ячейки. Во всякой ячейке в каждый момент времени находится в точности один символ из внешнего алфавита А={а₀,а₁,…а_n-1 }, n 2. Некоторый символ алфавита А называется пустым, любая ячейка, содержащая в данный момент пустой символ, называется пустой ячейкой.

Управляющее устройство в каждый момент времени находит в некотором состоянии q_i, принадлежащее множеству Q{q₀,q₁,…,q_r-1}, r 1. Множество Q называется внутренним алфавитом. Работа машины Тьюринга определяется программой. Программа состоит из команд. Каждая команда представляет собой выражение одного из следующего вида:

1) q_i a_j →q_k a_e;

2) q_i a_j →q_k a_e R;

3) q_i a_j →q_k a_e L.

Команда 1 заключается в том, что содержимое a_j обозреваемой на ленте ячейки стирается, а на его место дописывается символ a_e (который может совпадать с a_j), машина переходит в новое состояние q_k (оно может совпадать с предыдущим состоянием q_i). Команда 2 работает аналогично команде 1, и дополнительно сдвигает считывающую головку в соседнюю справа ячейку.Команда 3 работает аналогично команде 1, и дополнительно сдвигает считывающую головку в соседнюю слева ячейку.

Если считывающая головка находится в крайней справа (слева) ячейки ленты и происходит ее сдвиг вправо (влево), то к ленте пристраивается новая ячейка в пустом состоянии.

Машинным словом или конфигурацией называется слово вида

где А, q_k Q.

Если машина Тьюринга выходит на заключительное состояние, то она называется остановившейся.

 

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

 

Композиция машины Тьюринга

Поскольку машина Тьюринга—алгоритм, то операции композиции применимы и к машинам Тьюринга. Рассмотрим основные из них, а именно: произведение, возве-дение в степень, итерацию.

Тезис Тьюринга. Для нахождения значений функции, заданной в некотором алфавите, тогда и только тогда существует какой нибудь алгоритм, когда функция явл вычислимой по Тьюрингу то есть когда она может вычисляться на подходящей машине Тьюрингаю.
Пусть заданы машины Тьюринга Т1 и Т2, имеющие какой-то общий внешний алфавит А = {а0, а1,..., аm} и внутренние алфавиты Q1 = {q0, q1,..., qn} и cоответственно Q2 = {q0,q1,…,qt}. Композитом, или произведением, машины Т1 на машину T2 будем называть машину Т с тем же внешним алфавитом А= {а0, а1,..., аm}, внутренним алфавитом Q = {q0, q1,...,qn, qn+1,...,qn+t} и программой, получающейся следующим образом. Во всех командах Т1 содержащих заключитель-ный символ q0, заменяем его на символ qn+1. Все остальные символы в командах T1 оставляем неизменными. В командах Т2, напротив, символ q0 оставляем неизменным, но зато каждый из остальных символов заменяем символом qn+j. Совокупность всех команд Т1 и Т2, измененных указанным способом, и будет программой композита или произведения машин T1 и T2.
Произведение машины T1 на машину Т2 обозначается через Т = T1 • T2, или
Т = T1 * Т2.
Таким образом, машина Т есть произведение машин Т1 и T2, если последовательная работа этих двух машин эквивалентна работе одной машины Т

Классы рекурсивных функций

В дальнейшем под множеством натуральных чисел N будем понимать множество N = {0,1,2,…,k,…}

Пусть y = f(x₁, x₂,…, x_n) – функция от n переменных. Обозначим D(y) – область определения функции y = f(x₁, x₂,…, x_n), E(y) – область значений функции y = f(x₁, x₂,…, x_n).

Функция y = f(x₁, x₂,…, x_n) называется числовой функцией, если:

1) D(y)=N ×∙ N ∙× …×∙ N = ;

2) E(y) N

Функция y = f(x₁, x₂,…, x_n) называется частично числовой функцией, если:

1) D(y) N ×∙ N∙×…×∙N = ;

2) E(y) N.

Следующие числовые функции мы будем называть простейшими:

1) O(x) = 0 – нуль-функция

2) (x₁, x₂,…, x_n) = x_m, 1 ≤ m ≤ n – функция повторяющая значение своих аргументов;

3) S(x) = x+1 – функция следования.

Определим следующие три операции: суперпозиции, примитивной рекурсии и минимизации.

Операция суперпозиции

Будем говорить, что n – местная функция φ получается из m – местной функции ψ и n – местныхфункций f₁,f₂,…,f_m с помощью операции суперпозиции, если для всех x₁,x₂,…,x_n справедливо равенство:

φ (x₁,x₂,…,x_n) = ψ(f₁(x₁, x₂,…, x_n),…, f_m(x₁, x₂,…, x_n))