Неразрешимость логики первого порядка

Отрицанием предиката P(x1, x2,…, xn), определенного на множестве M1ЧM2Ч…ЧMn называется предикат ¬P(x1, x2,…, xn), определенный на том же множестве, который на наборе (a1, a2,…, an) M1ЧM2Ч…ЧMn

Конъюнкцией предикатов P(x1, x2,…, xn), определенного на множестве M1Ч

M2Ч…ЧMn, и Q(y1, y2,…, ym), определенного на множестве N1ЧN2Ч…ЧNm, называется предикат P Q(x1, x2,…, xn, y1, y2,…, ym) c пердметной областью M1ЧM2Ч…ЧMnЧN1ЧN2Ч…ЧNn, который на наборе (a1, a2,…, an, b1, b2,…, bm) M1ЧM2Ч…ЧMnЧN1ЧN2Ч…ЧNn

Дизъюнкцией предикатов P(x1, x2,…, xn), определенного на множестве M1ЧM2Ч…ЧMn, и Q(y1, y2,…, ym), определенного на множестве N1ЧN2Ч…ЧNm, называется предикат P Q(x1, x2,…, xn, y1, y2,…, yn) c пердметной областью M1ЧM2Ч…ЧMnЧN1ЧN2Ч…ЧNn, который на наборе (a1, a2,…, an, b1, b2,…, bm) M1ЧM2Ч…ЧMnЧN1ЧN2Ч…ЧNn

Импликацией предикатов P(x1, x2,…, xn), определенного на множестве M1ЧM2Ч…ЧMn, и Q(y1, y2,…, ym), определенного на множестве N1ЧN2Ч…ЧNm, называется предикат P → Q(x1, x2,…, xn, y1, y2,…, yn) c пердметной областью M1ЧM2Ч…ЧMnЧN1ЧN2Ч…ЧNn, который на наборе (a1, a2,…, an, b1, b2,…, bm) M1ЧM2Ч…ЧMnЧN1ЧN2Ч…ЧNn

Эквивалентностью предикатов P(x1, x2,…, xn), определенного на множестве M1ЧM2Ч…ЧMn, и Q(y1, y2,…, ym), определенного на множестве N1ЧN2Ч…ЧNm, называется предикат P(x1, x2,…, xn) ↔ Q (y1, y2,…, yn) c пердметной областью M1ЧM2Ч…ЧMnЧN1ЧN2Ч…ЧNn, который на наборе (a1, a2,…, an, b1, b2,…, bm) M1ЧM2Ч…ЧMnЧN1ЧN2Ч…ЧNn

Операцией связывания квантором общности переменной xi в n-местном предикате P(x1, x2,…, xn)), определенном на множестве M1ЧM2Ч…ЧMn, называется операция, в результате которой получается n-1-местный предикат " xi P(x1, x2,…, xi-1, xi+1,…, xn), который при значениях x1 = a1, …, xi-1 = ai-1, xi-1 = ai-1, …, xn = an истинен, если при любых значениях xi = ai высказывание P(a1, a2,…, an) истинно.

Операцией связывания квантором существования переменной xi в n-местном предикате P(x1, x2,…, xn) называется операция, в результате которой получается n-1-местный предикат $ xi P(x1, x2,…, xi-1, xi+1,…, xn), который при значениях x1 = a1, …, xi-1 = ai-1, xi-1 = ai-1, …, xn = an истинен, если при некотором значении xi = ai высказывание P(a1, a2,…, an) истинно.

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

Формулами логики предикатов являются:

– всякая нульместная предикатная переменная;

– P(n) (x1, x2,…, xn), где P(n) – n-местная предикатная переменная, а x1, x2,…, xn – свободные переменные;

– F, где F – формула;

– F1 F2, F1 F2, F1 ↔ F2, F1 → F2, где F1 и F2 – формулы, в которых общие переменные являются одновременно свободными или одновременно связанными;

– " xi P(x1, x2,…, xi-1, xi+1,…, xn) и $ xi P(x1, x2,…, xi-1, xi+1,…, xn), где P(x1, x2,…, xn) – формула, в которой xi – свободная переменная

Определение истинности формул алгебры предикатов вводится с помощью интерпретации. В классическом случае интерпретация определяется следующими данными

1) предметная область;

2) всякой предметной константе ставится в соответствие некоторый предмет, определенный в области;

3) каждому пропозициональному символу ставится в соответствие некоторое значение 1 (истина) или 0 (ложь);

4) каждому предикатному символу языка ставится в соответствие некоторая характеристическая функция.

Классификация формул:

Формула называется

а) выполнимой (опровержимой) на множестве М, если существует ее истинная (ложная) интерпретация на этом множестве;

б) тождественно-истинной (тождественно-ложной) на множестве М, если любая ее интерпретации на этом на этом множестве истина (ложна);

в) выполнимой (опровержимой), если существует предметная область, на которой она выполнима (опровержима);

г) общезначимой (противоречием), если на любой предметной области она тождественно-истинная (тождественно-ложная).

Множеством истинности предиката P(x1, x2,…, xn), заданного на множестве M1ЧM2Ч…ЧMn, называется совокупность всех упорядоченных систем (a1, a2,… an), в которых a1 е M1 a2 е M2,…, an е Mn, таких, что данный предикат обращается в истинное высказывание Р(a1, a2,… an) при подстановке x1 = a1 x2 = a2,…, xn = an. Обозначается P+.

Два n-местных предиката Р(x1, x2,…, xn) и Q(x1, x2,…, xn), заданных на одном и том же множестве M1ЧM2Ч…ЧMn называются равносильными, если набор предметов a1 е M1 a2 е M2,…, an е Mn превращает первый предикат в истинное высказывание Р(a1, a2,… an) тогда же, когда этот набор предметов превращает второй предикат в истинное. Переход от предиката Р(x1, x2,…, xn) к равносильному ему предикату Q(x1, x2,…, xn) называется равносильным преобразованием первого.

Предикат Р(x1, x2,…, xn), заданный на множестве M1ЧM2Ч…ЧMn называется следствием предиката Q(x1, x2,…, xn), если он превращается в истинное высказывание на всех тех наборах значений предметных переменных из соответствующих множеств, на которых в истинное высказывание превращается предикат Q(x1, x2,…, xn).

3. Понятие машины Тьюринга

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

Машины Тьюринга – это совокупность следующих объектов

1) внешний алфавит A={a0, a1, …, an};

2) внутренний алфавит Q={q1, q2,…, qm} – множество состояний;

3) множество управляющих символов {П, Л, С}

4) бесконечная в обе стороны лента, разделённая на ячейки, в каждую из которых в любой дискретный момент времени может быть записан только один символ из алфавита А;

5) управляющее устройство, способное находиться в одном из множества состояний

Символом пустой ячейки является буква внешнего алфавита а0.

Среди состояний выделяются два – начальное q1, находясь в котором машина начинает работать, и заключительное (или состояние остановки) q0, попав в которое машина останавливается.

 Скачать реферат