2. Основные понятия логики первого порядка
Логика первого порядка (исчисление предикатов) – формальное исчисление, то есть это совокупность абстрактных объектов, не связанных с внешним миром, в котором представлены правила оперирования множеством символов в строго синтаксической трактовке без учета смыслового содержания.
Язык логики первого порядка строится на основе сигнатуры, состоящей из следующих символов:
1) логические
– символы
логических операций ¬,
,
,
↔, →;
– символы кванторных операций , ;
– служебные символы: скобки и запятая.
2) нелогические
– множество предикатных символов, с которым связана арность, то есть число возможных аргументов P(n), Q(m), …, P1(n), P2(n);
– символы пропозициональных переменных X, Y, Z, …, X1, X2, … (можно считать, что символы пропозициональных переменных – это нульместные предикатные символы);
– символы предметных переменных x, y, z, …, x1, x2,…;
– символы предметных констант a, b, c, …, a1, a2, …
n-местным предикатом P (x1, x2,…, xn) называется функция P: M1ЧM2Ч…ЧMn → {1,0}, определенная на наборах длины n элементов некоторого множества M= M1ЧM2Ч…ЧMn и принимающая значения в области {1,0}. Множество М называется предметной областью предиката, его элементы – предметными константами.
Отрицанием
предиката
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).