Логіки першого порядку

На рівні логік предикатів 1-го порядку функції та предикати в загальному випадку розглядаються як квазиарні, композиціями таких логік є логічні зв’язки, операції квантифікації та суперпозиції. Назва “логіка 1-го порядку” зв’язана з тим, що квантори застосовуються тiльки до імен компонентів даних (предметних iмен). Обмежимося розглядом логік з фінарними функціями та предикатами, яка по суті є класичною логікою предикатів 1-го порядку. При цьому операції суперпозиції задаваються неявно, в стилі класичної логіки. Моделями такої логіки предикатів 1-го порядку є математичні структури дуже загального вигляду алгебраїчні системи (скорочено АС).

1. АЛГЕБРАЇЧНІ СИСТЕМИ

Алгебраїчною системою назвемо об’єкт вигляду A=(A, FnA PrA), де A непорожня множина, яку називають носiєм, або основою АС, FnA та PrA множини функцiй та предикатiв, заданих на A.

Нехай довільна множина така, що існує тотальне однозначне відображення I: FnA,PrA. Елементи множини трактуватимемо як імена деяких функцій та предикатів із FnAPrA. Такі імена нази-вають функціональними символами (ФС) та предикатними символами (ПС), іменовані ними функції та предикати називають базовими. Множину функціональних та предикатних символів називають сигнатурою. Нехай Fs – множина функціональних символів, Ps – множина предикатних символів. Тоді сигнатура FsPs.

АС iз носiєм A та сигнатурою FsPs назвемо АС з доданою сигнатурою [18]. Такі АС позначатимемо у вигляді A = (A, I, ), або A = (A, ), якщо I. мається на увазі.

Для кожного gFs функцію GFnA таку, що I(g)=G, назвемо значенням ФС g при інтерпретації I на АС A=(A, FnA PrA), та позначатимемо таку функцію gA Предикат PPrA такий, що I(p)=P, назвемо значенням ПС p при інтерпретації I на АС A, та позначатимемо такий предикат pA . Якщо функція gA є функція-константа на A, ФС g називають константним символом.

Обмежимося розглядом алгебраїчних систем фінарних функцій та предикатів, причому базові функції та предикати п-арні. Тому вважаємо, що з кожним ФС та ПС зв’язане натуральне число арність такого символа. При цьому для кожного h арність hA pівна арності символу h.

АС B=(B, I,) назвемо розширенням АС A=(A, I,), якщо AB і для всіх h та аА маємо hA hВ . В цьому випадку АС A називають підсистемою АС B, а B називають підсистемою АС A. Цей факт позначатимемо A B.

Нехай A=(A,). Множина СА утворює підсистему C=(C, ) алгебраїчної системи A = (A, ), якщо C замкнена відносно базових функцій fA , де f.

Hе для кожної СА можна говорити про підсистему (C, ).

Наприклад, для АС (N, ), де {+, =}, а символи + та інтерпретуються природним чином, множина непарних чисел Nн N незамкнена відносно +, тому Nн не утворює підсистеми. В той же час множина парних чисел Nп N утворює власну підсистему (Nп , ) системи (N, ).

2. МОВИ 1-го ПОРЯДКУ

Для опису алгебраїчних систем використовуються мови логіки предикатів 1-го порядку, або просто мови 1-го порядку.

Алфавiт мови 1-го порядку складається iз таких символiв:

 предметнi імена (змiннi) x, y, z,...;

 функцiональнi символи f0, f1, f2,... заданої арностi;

 предикатнi символи p0, p1, p2,... заданої арностi;

 символи логiчних операцiй та .