3. Независимость аксиом . Отдельная аксиома теории считается независимой, если эту аксиому нельзя вывести из остальных аксиом. Зависимая аксиома по сути избыточна, и ее удаление из системы аксиом никак не отразится на теории. Вся система аксиом теории называется независимой, если каждая аксиома в ней независима.

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

2. Основные понятия логики первого порядка

Логика первого порядка (исчисление предикатов) – формальное исчисление, то есть это совокупность абстрактных объектов, не связанных с внешним миром, в котором представлены правила оперирования множеством символов в строго синтаксической трактовке без учета смыслового содержания.

Язык логики первого порядка строится на основе сигнатуры, состоящей из следующих символов:

1) логические

– символы логических операций ¬, , , ↔, →;

– символы кванторных операций ", $;

– служебные символы: скобки и запятая.

2) нелогические

– множество предикатных символов, с которым связана арность, то есть число возможных аргументов P^{( n )} , Q^{( m )} , …, P₁ ^{( n )} , P₂ ^{( n )} ;

– символы пропозициональных переменных X, Y, Z, …, X₁ , X₂ , … (можно считать, что символы пропозициональных переменных – это нульместные предикатные символы);

– символы предметных переменных x, y, z, …, x₁ , x₂ ,…;

– символы предметных констант a , b , c , …, a ₁ , a ₂ , …

n -местным предикатом P (x1, x2,…, xn) называется функция P: M₁ ЧM₂ Ч…ЧM_n → {1,0}, определенная на наборах длины n элементов некоторого множества M= M₁ ЧM₂ Ч…ЧM_n и принимающая значения в области {1,0}. Множество М называется предметной областью предиката, его элементы – предметными константами.

Отрицанием предиката P(x₁ , x₂ ,…, x_n ), определенного на множестве M₁ ЧM₂ Ч…ЧM_n называется предикат ¬P(x₁ , x₂ ,…, x_n ), определенный на том же множестве, который на наборе (a ₁ , a ₂ ,…, a _n ) M₁ ЧM₂ Ч…ЧM_n

Конъюнкцией предикатов P(x₁ , x₂ ,…, x_n ), определенного на множестве M₁ ЧM₂ Ч…ЧM_n , и Q(y₁ , y₂ ,…, y_m ), определенного на множестве N₁ ЧN₂ Ч…ЧN_m , называется предикат PQ(x₁ , x₂ ,…, x_n , y1, y2,…, ym) c пердметной областью M₁ ЧM₂ Ч…ЧM_n ЧN₁ ЧN₂ Ч…ЧN_n , который на наборе (a ₁ , a ₂ ,…, a _n , b ₁ , b ₂ ,…, b _m ) M₁ ЧM₂ Ч…ЧM_n ЧN₁ ЧN₂ Ч…ЧN_n

Дизъюнкцией предикатов P(x₁ , x₂ ,…, x_n ), определенного на множестве M₁ ЧM₂ Ч…ЧM_n , и Q(y₁ , y₂ ,…, y_m ), определенного на множестве N₁ ЧN₂ Ч…ЧN_m , называется предикат PQ(x₁ , x₂ ,…, x_n , y1, y2,…, yn) c пердметной областью M₁ ЧM₂ Ч…ЧM_n ЧN₁ ЧN₂ Ч…ЧN_n , который на наборе (a ₁ , a ₂ ,…, a _n , b ₁ , b ₂ ,…, b _m ) M₁ ЧM₂ Ч…ЧM_n ЧN₁ ЧN₂ Ч…ЧN_n

Импликацией предикатов P(x₁ , x₂ ,…, x_n ), определенного на множестве M₁ ЧM₂ Ч…ЧM_n , и Q(y₁ , y₂ ,…, y_m ), определенного на множестве N₁ ЧN₂ Ч…ЧN_m , называется предикат P → Q(x₁ , x₂ ,…, x_n , y1, y2,…, yn) c пердметной областью M₁ ЧM₂ Ч…ЧM_n ЧN₁ ЧN₂ Ч…ЧN_n , который на наборе (a ₁ , a ₂ ,…, a _n , b ₁ , b ₂ ,…, b _m ) M₁ ЧM₂ Ч…ЧM_n ЧN₁ ЧN₂ Ч…ЧN_n

Эквивалентностью предикатов P(x₁ , x₂ ,…, x_n ), определенного на множестве M₁ ЧM₂ Ч…ЧM_n , и Q(y₁ , y₂ ,…, y_m ), определенного на множестве N₁ ЧN₂ Ч…ЧN_m , называется предикат P(x₁ , x₂ ,…, x_n ) ↔ Q (y1, y2,…, yn) c пердметной областью M₁ ЧM₂ Ч…ЧM_n ЧN₁ ЧN₂ Ч…ЧN_n , который на наборе (a ₁ , a ₂ ,…, a _n , b ₁ , b ₂ ,…, b _m ) M₁ ЧM₂ Ч…ЧM_n ЧN₁ ЧN₂ Ч…ЧN_n

Операцией связывания квантором общности переменной xi в n-местном предикате P(x₁ , x₂ ,…, x_n )), определенном на множестве M₁ ЧM₂ Ч…ЧM_n , называется операция, в результате которой получается n-1-местный предикат "x_i P(x₁ , x₂ ,…, x_{i -1} , x_{i +1} ,…, x_n ), который при значениях x₁ = a ₁ , …, x_{i -1} = a _{i -1} , x_{i -1} = a _{i -1} , …, x_n = a _n истинен, если при любых значениях x_i = a _i высказывание P(a ₁ , a ₂ ,…, a _n ) истинно.

Операцией связывания квантором существования переменной xi в n-местном предикате P(x₁ , x₂ ,…, x_n ) называется операция, в результате которой получается n-1-местный предикат $x_i P(x₁ , x₂ ,…, x_{i -1} , x_{i +1} ,…, x_n ), который при значениях x₁ = a ₁ , …, x_{i -1} = a _{i -1} , x_{i -1} = a _{i -1} , …, x_n = a _n истинен, если при некотором значении x_i = a _i высказывание P(a ₁ , a ₂ ,…, a _n ) истинно.

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

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

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