Логіки першого порядку, Детальна інформація

Приклад 2. Мова теорiї множин Lset визначається сигнатурою \xF073set={(, =}, де ( та = \xF02D бiнарнi предикатнi символи.

Наприклад, z(x \xF02D атомарна формула, (z(z(x(z(y) \xF02D формула, \xF024x\xF0D8(y(y(x) \xF02D замкнена формула мови Lset . Зауважимо, що останні дві формули відповідно означають "x(y" та "існує ("

Приклад 3. Мова теорiї впорядкованих множин Lord визначається сигнатурою \xF073ord={<, =}, де < та = \xF02D бiнарнi предикатнi символи.

Наприклад, x
Зв’язанi iмена в формулах можна замiнювати iншими предмет-ними іменами, але при цьому може виникнути колiзiя \xF02D ситуацiя, коли вiльнi імена стали зв’язаними. Наприклад, iз формули \xF024z(x+z=y) можна отримати формулу \xF024t(x+t=y), коли колiзiї нема, та формулу \xF024x(x+x=y), коли колiзiя змiнила смисл формули.

[t1, ..., tn]

В загальному випадку формули (x,y[a, b] та ((x[a])y[b] рiзнi. Наприклад, якщо ( \xF02D це формула x(y, то (x,y[y, z] \xF02D це формула y(z, ((x[y])y[z] \xF02D це формула z(z.

При замiнi вiльних входжень предметних імен термами можливi колiзiї, коли вiльне ім’я стає зв’язаним. Наприклад, нехай ( \xF02D це формула \xF024z(x+z=y). Тоді (x[u] \xF02D це формула \xF024z(u+z=y); (x[z] \xF02D це формула \xF024z(z+z=y); отже, маємо колiзiю. Звідси терм t допустимий для замiни вiльного імені x в формулi (, якщо t не лежить в обла-стi дiї нiякого квантора по деякому імені, яке входить до складу t.

Інтерпретацiєю, або моделлю мови L сигнатури ( будемо називати АС з доданою сигнатурою вигляду A=(A, I, (). Множину A називають областю iнтерпретацiї.

Значення символiв та виразiв мови L задамо на A таким чином.

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

Таким чином, конкретна інтерпретація мови L на АС A=(A, I, () визначається відображенням I: ((FnA(PrA. Значення символiв с, f та p позначаємо відповідно сA , fA та pA : I(c)=cA , I(f)=fA , I(p)=pA .

Для інтерпретації термів і формул мови L задамо відображення J: Tr (Fr(FnA,(PrA,, яке індуктивно визначається за допомогою I.

Для термiв маємо:

\xF02D J(х)=’x;

\xF02D J(ft1...tn) =I(f)(J(t1), ..., J(tn)) = fA (J(t1), ..., J(tn)).

Для атомарних формул маємо

\xF02D J(рt1...tn) =I(р)(J(t1), ..., J(tn)) = рA (J(t1), ..., J(tn)).

Для формул маємо:

\xF02D нехай J(\xF046\xF029\xF03DP. Тодi J(\xF0D8\xF046)=\xF0D8P, J(\xF024x\xF046)=\xF024xP.

\xF02D нехай J(\xF046\xF029\xF03DP та J(\xF059\xF029\xF03DQ. Тодi J(\xF0DA\xF046\xF059)=P\xF0DAQ .

(fA , g1, ..., gn).

Кожний терм з вільними іменами v1, ..., vn інтерпретується як {v1, ..., vn}-арна функція на А, кожна формула з вільними іменами v1, ..., vn інтерпретується як {v1, ..., vn}-арна функція на А. Зокрема, кожний замкнений терм інтерпретується як функція-константа на А, кожна замкнена формула \xF02D як предикат-константа на А.

Функцію, що є значенням терма t на АС A=(A, I, (), позначаємо tA ; предикат, що є значенням формули \xF046 на АС A=(A, I, (), позначаємо \xF046A . Це означає, що J(t)=tA , J(\xF046)=\xF046A .

Формулу \xF046 назвемо істинною при інтерпретації A, або істинною на A, або A-істинною, якщо предикат \xF046A є істинним. Це означає: Х-арний предикат \xF046A такий, що \xF046A(d)=T для всіх d(AХ.

Те, що формула \xF046 істинна на AC A, позначаємо A\xF07C\xF03D\xF046.

Формула \xF046 називається всюди iстинною, якщо вона iстинна при кожнiй iнтерпретацiї. Те, що \xF046 всюди істинна, позначимо \xF07C\xF03D\xF046.

Формулу \xF046 назвемо виконуваною при інтерпретації A, або виконуваною на AC A, або A-виконуваною, якщо предикат \xF046A є виконуваним. Це означає: Х-арний предикат \xF046A такий, що для деякого d(AХ маємо \xF046A(d)=T.

Формула \xF046 називається виконуваною, якщо вона виконувана при деякiй iнтерпретацiї.

Приклад 4. Формула x=x всюди iстинна.