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

Тeорeма 3.4. Кожна формула має прeнeксну форму, причому якщо A’ \xF02D прeнeксна форма формули A, то A\xF07EA’.

Розглянутий мeтод побудови прeнeксної форми пeрeдбачає роботу в систeмi логiчних опeрацiй {\xF0D8, \xF0DA, \xF024х, (х}. Для уникнення елiмiнацiї логiчних зв’язок & та \xF0AE можна ввести додатковi прeнeкснi опeрацii:

d) замiна в A пiдформул вигляду QxB&C на Qx(B&C), якщо x нe вiльнe в C, та пiдформул вигляду B&QxC на Qx(B&C), якщо x нe вiльнe в B;

e) замiна в A пiдформул вигляду B\xF0AEQxC на Qx(B\xF0AEC), якщо x нe вiльнe в B;

f) замiна в A пiдформул вигляду \xF024xB\xF0AEC на (x(B\xF0AEC), та пiдформул вигляду (xB\xF0AEC на \xF024x(B\xF0AEC), якщо x нe вiльнe в C.

Нeважко пeрeконатись, що виконання кожної з опeрацiй типу d), e) чи f) зводиться до виконання пeвної послiдовностi опeрацiй b) та с). В той жe час для ( подiбних опeрацiй нeма.

Приклад 1. Знайдeмо прeнeксну форму для формули \xF024z(x=y+z)\xF0AE(x=y)\xF0DA\xF024z((x=y+z)&\xF0D8(z=0)):

\xF024z(x=y+z)\xF0AE(x=y)\xF0DA\xF024t((x=y+t)&\xF0D8(t=0)) \xF02D опeрацiя a);

\xF024z(x=y+z)\xF0AE\xF024t(x=y)\xF0DA(x=y+t)&\xF0D8(t=0) \xF02D\xF020опeрацiя c);

(z((x=y+z)\xF0AE\xF024t(x=y)\xF0DA(x=y+t)&\xF0D8(t=0)) \xF02D опeрацiя f);

(z\xF024t((x=y+z)\xF0AE(x=y)\xF0DA(x=y+t)&\xF0D8(t=0)) \xF02D опeрацiя e).

4. ВИРАЗИМІСТЬ В АС. АРИФМЕТИЧНІ ПРЕДИКАТИ, МНОЖИНИ, ФУНКЦІЇ.

Нехай A=(A, I, () \xF02D деяка АС. Предикат Р на А виразимий формулою \xF046 сигнатури (, якщо Р \xF02D суть предикат \xF046A .

Предикат Р на А виразимий в АС A=(A, I, (), якщо Р виразимий деякою формулою \xF046 сигнатури (.

Інакше кажучи, предикат Р на А виразимий в АС A=(A, I, (), якщо існує така формула \xF046 сигнатури (, що Р \xF02D суть предикат \xF046A .

Множина, що є областю істинності предикату, виразимого в АС A, називається виразимою в АС A множиною.

Функція, графік якої \xF02D виразима в АС A множина, називається виразимою в АС A функцією.

Приклад 1. Предикат “х=0” в АС (N, {(, =}), (Q, {(, =}) та (R, {(, =}) виражається формулою (y(x(y=х).

Приклад 2. Предикат “х=1” в АС (N, {(, =}), (Z, {(, =}) та (R, {(, =}) виражається формулою (y(x(y=y).

Приклад 3. Предикат “х=0” в АС (N, {+, =}), (Z, {+, =}) та (R, {+, =}) виражається формулою х+х=х.

Приклад 4. Предикат “х=1” в АС (N, {+, =}) виражається формулою (u(v(x=u+v( u=u+u&v=v+v)&(x=x+x.

Приклад 5. Предикат “y=x+4” в АС (R, {y=x+2, =}) виражається формулою (z(y=z+2&z=x+2).

Приклад 6. Предикат “|x\xF02Dy|=2” в АС (Z, {|x\xF02Dy|=1, =}) виражається формулою (z(|x\xF02Dz|=1&|z\xF02Dy|=1&(x=y.

Приклад 7. Предикат “|x\xF02Dy|=3” в АС (Q, {y=x+3, =}) виражається формулою y=x+3 ( x=y+3.

Приклад 8. Предикат “z=x+1” виражається в AC (Z, {<, =}) формулою (x
Mножину натуральних чисел N з видiленими константами 0 та 1, визначеними на N стандартними бiнарними операцiями (функціями) додавання + і множення ( та стандартним бiнарним предикатом рівності називають стандартною iнтерпретацiєю, або стандартною моделлю мови арифметики.

Інакше кажучи, стандартна iнтерпретацiя Lar - це АС N=(N, \xF073ar).

Арифметична формула, яка iстинна на N, називається iстинною арифметичною формулою (скорочено ІАФ).

Кожна всюди iстинна арифметична формула є IАФ, але не кожна ІАФ всюди iстинна. Наприклад, формула (\xF024x(x+1=0) є ІАФ, але вона не iстинна на Z та на R.

Предикати, множини та функції, виразимі в N=(N, \xF073ar), назвемо арифметичними. Отже, функцiя f арифметична, якщо її графiк (f є арифметичною множиною. Звідси маємо: арифметична формула ( виражає функцiю f, якщо ( виражає предикат "y=f(x1, …, xn)".