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

Реферат на тему:

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

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

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

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

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

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

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

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

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

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

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

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

Нехай множини А1 (А та А2 (А замкнені відносно всіх базових функцій АС (A, (). Тоді А1(А2 теж замкнена відносно всіх базових функцій АС (A, (), якщо тільки А1(А2 ((. Отже, якщо (A1, () та (A2, () xF02D підсистеми системи (A, (), то (А1(А2, () або підсистема системи (A, (), або (.

Підсистему (А1(А2, () назвемо перетином підсистем (A1, () та (A2, ().

Теорема 1.1. Перетин М носіїв всіх підсистем системи (A, () або утворює підсистему (М, (), або є (.

Така підсистема (М, () називається найменшою підсистемою системи (A, ().

Зрозуміло, що якщо сигнатура (містить константні символи, АС (A, () має найменшу підсистему.

де (={(((| В (А (}, є найменшою множиною, замкненою відносно всіх базових функцій системи A=(A, (). Така С визначає АС (С, (), яку називають підсистемою системи (A, (), породженою множиною В.

Якщо при цьому С=А, то кажуть, що АС (A, () породжується підмножиною В (А. Зрозуміло, що різні підмножини можуть породжувати одну і ту ж підсистему.

Приклад 1. Підсистема (Z+, {1, +, =}) системи (N, {1, +, =}) породжується довільною підмножиною иножини Z+, яка містить 1. Найменшою такою підмножиною є {1}.

Приклад 2. Система (N, {+, =}) породжується множиною {0, 1}.

Приклад 3. Система (N, {0, 1, +, (, =}) породжується множиною {0, 1}. Наявність константних символів 0 та 1 приводить до того, що в кожній підсистемі такої системи носій містить 0 та 1, але тоді підсистема співпаде з усією системою. Отже, вказана система власних підсистем не має.

Приклад 4. Система (Z+, {+, =}) має підсистеми (kZ+, {+, =}), де kZ+={kx | x (Z+}, для довільних k (Z+.

2. МОВИ 1-го ПОРЯДКУ Для опису алгебраїчних систем використовуються мови логіки предикатів 1-го порядку, або просто мови 1-го порядку.

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

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

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

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

xF02D символи логiчних операцiй xF0D8, xF0DA та (.

В множині Fs може виділятися підмножина константних символів Сп (Fs. Символ рівності завжди інтерпретуватиметься як предикат рівності, причому таку рівність трактуватимемо як тотожність.

Символи xF0D8, xF0DA, xF024, = та предметнi імена називають логiчними символами, функцiональнi та предикатнi символи називають нелогiчними символами. Множину функцiональних та предикатних символів xF073=Fs (Ps називають сигнатурою мови 1-го порядку.

Основними конструкціями мови 1-го порядку є терми та формули. Терми використовують для позначення, назви суб'єктiв, формули xF02D для запису тверджень про суб'єкти.

Індуктивне визначення терма таке:

1) кожне предметне ім'я та кожна константа є термом; такі терми назвемо атомарними;

2) якщо t1,…, tn xF02D терми, f xF02DxF020 n-арний функцiональний символ, то ft1… tn xF02D терм.

Атомарною формулою називається вираз виду pt1… tn, де p — n-арний предикатний символ, t1, …, tn xF02D терми.

Індуктивне визначення формули таке:

1) кожна атомарна формула є формулою;

2) якщо (та (xF02D формули, то xF0D8(та (((xF02D формули;

3) якщо (xF02D формула, x xF02DxF020предметне iм’я, то xF024x (xF02D формула.

Аналогiчно мовi ЛВ, вирази (&(, (xF0AE (та (((вважаємо вiдповiдно скороченнями формул xF0D8xF0DAxF0D8(xF0D8(, xF0DAxF0D8((та xF0D8xF0DAxF0D8xF0DAxF0D8((xF0D8xF0DAxF0D8((. Користуємося також символом (, вважаючи вираз (x (скороченням формули xF0D8xF024xxF0D8(.

Для бiнарних функцiональних та предикатних символiв i символiв xF0DA, &, xF0AE та (звичайно застосовуємо iнфiксну форму запису. Прiоритет символiв логiчних зв’язок вважаємо нижчим за прiоритет предикатних символiв, а прiоритет предикатних символiв нижчим за прiоритет функцiональних символiв. Використовуючи додатковi символи xF02D кому, і дужки (та), для термiв вигляду ft1… tn вживатимемо скорочення f (t1…tn), або t1ft2, якщо символ f бiнарний. Те ж для атомарних формул. Для атомарних формул вигляду xF0D8=t1(t2 вживатимемо скорочення t1(t2.

Скорочення термiв та формул будемо називати просто термами та формулами. Множини термів та формул мови 1-го порядку звичайно позначатимемо вiдповiдно як Тr та Fr. Формули мови 1-го порядку сигнатури xF073 називатимемо формулами 1-го порядку сигнатури xF073.

Можна вказати 2 рiвнi вiдмiнностi мов 1-го порядку:

1) варiанти мови одної сигнатури, що вiдрiзняються наборами символiв логiчних операцiй та способами запису термiв i формул;

2) iстотно рiзнi мови, що вiдрiзняються сигнатурами.

Мова 1-го порядку L' сигнатури (' називається розширенням мови 1-го порядку L сигнатури xF073, якщо xF073'(xF073.

В формулi вигляду xF024x (або (x (формулу P називають областю дiї квантора по x. Вираз вигляду xF024x або (x називають кванторним префiксом.

Входження імені (змінної) x в формулу xF046 зв’язане, якщо воно знаходиться в областi дiї деякого квантора по x, iнакше таке входження x в xF046 вiльне.

Якщо iснує вiльне входження імені x в формулу xF046, то x xF02D вiльне ім'я (вільна змiнна) формули xF046.

Формулу xF046 iз вiльними іменами x1,., xn позначаємо xF046(x1,., xn).

Формула замкнена, якщо вона не має вiльних імен.

Терм, який не мiстить входжень предметних імен, називається замкненим термом. Зокрема, таким є кожний константний символ.

Наведемо кiлька прикладiв мов 1-го порядку.

Приклад 1. Мова арифметики Lar визначається сигнатурою xF073ar={0, 1, +, (, =}, де 0 та 1 xF02D константні символи, + та (xF02D бiнарнi функцiональнi символи, = xF02D бiнарний предикатний символ.

Терм мови арифметики назвемо арифметичним термом.

Формулу мови арифметики назвемо арифметичною формулою.

Наприклад, 1+1 xF02D замкнений арифметичний терм; x ((y+z) xF02D арифметичний терм; xF024z (x+z=y) xF02D арифметичнa формула.

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

Наприклад, z (x xF02D атомарна формула, (z (z (x (z (y) xF02D формула, xF024xxF0D8(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 (xF046xF029xF03DP. Тодi J (xF0D8xF046)=xF0D8P, J (xF024xxF046)=xF024xP.

xF02D нехай J (xF046xF029xF03DP та J (xF059xF029xF03DQ. Тодi J (xF0DAxF046xF059)=PxF0DAQ .

(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, позначаємо AxF07CxF03DxF046.

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

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

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

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

Приклад 5. Формула (x (y (x=y) iстинна на всiх 1-елементних АС i тiльки на них; формула ((x (y (x=y) iстинна на всiх k-елементних АС, де k>1, i тiльки на них.

.

Із визначень випливає семантична теорема замикання:

.

Приклад 6. Кожна формула вигляду (x[t]xF0AExF024x (всюди істинна.

Нехай Х xF02D множина вільних імен формули (x[t]xF0AExF024x (. Припу-стимо супротивне: існує A=(A, xF073) така, що A xF07C (xF020(x[t]xF0AExF024x (. Тоді iснує d (AX таке, що ((x[t]xF0AExF024x ()А (d)=F, звідки ((x[t])А (d)=Т та (xF024x ()А (d)=F. Нехай tА (d)=b (A; в силу ((x[t])А (d)=Т тоді (А (d (х (b)=Т. Але (xF024x ()А (d)=F, тому для всіх a (A маємо (А (d (х (а)=F, зокрема, (А (d (х (b)=F. Дістали суперечнiсть.

Окремим випадком всюди iстинних формул є тавтологiї, тобто формули, якi мають структуру тавтологiй мови ЛВ. Наприклад, кожна формула виду xF0D8AxF0DAA xF02D це тавтологiя. Точне визначення тавтологiї 1-го порядку можна дати таким чином.

Формулу назвемо пропозиційно нерозкладною, якщо вона атомарна або має вигляд xF024x (.

Нехай Fr0 xF02D множина всiх пропозиційно нерозкладних формул мови L, Fr xF02D множина всiх формул мови L. Iстиннiсною оцiнкою мови L назвемо довiльне вiдображення (xF020: Fr0 xF0AE{T, F}.

Продовжимо (до вiдображення (xF020: FrxF0AE{T, F} таким чином:

xF02DxF020((xF0D8xF046)=T xF0DBxF020xF020((xF046)=F;

xF02DxF020((xF0DAxF046xF059)=T xF0DBxF020xF020((xF046)=T або ((xF059)=T.

Формула xF046 мови L тавтологiя, якщо для кожної iстинiсної оцiнки (мови L маємо ((xF046)=T.

Зрозумiло, що кожна тавтологiя є всюди iстинною формулою, але зворотне твердження невiрне. Наприклад, всюди істинна формула вигляду x=x xF02D не тавтологiя.

На множинi формул введемо відношення тавтологiчного наслiдку x255E, логiчного наслiдку xF07CxF03D, слабкого логiчного наслiдку xF07CxF07CxF03D та логiчної еквiвалентностi xF07E.

Формула xF059 є тавтологiчним наслiдком формули xF046, що позначатимемо xF046×255E xF059, якщо формула xF046xF0AExF059 — тавтологiя.

Формула xF059 є логiчним наслiдком формули xF046, що позначатимемо xF046xF07CxF03DxF059, якщо формула xF046xF0AExF059 всюди iстинна.

Формули xF046 та xF059xF020 логiчно еквiвалентнi, що позначатимемо xF046xF07ExF059, якщо xF046xF07CxF03DxF059 та xF059xF07CxF03DxF046.

Зрозумiло, що xF046xF07ExF059 xF0DB формули xF046xF0AExF059 та xF059xF0AExF046 всюди iстиннi.

Формула xF059 є слабким логiчним наслiдком формули xF046, що позначатимемо xF046xF07CxF07CxF03DxF059, якщо для кожної iнтерпретацiї A iз умови AxF07CxF03DxF046 випливає AxF07CxF03DxF059.

Формула xF059xF020 є логiчним наслiдком множини формул {xF0461,…, xF046n}, що позначатимемо {xF0461,…, xF046n}xF07CxF03DxF059, якщо xF0461&…&xF046nxF07CxF03DxF059.

Аналогічно визначаємо {xF0461,…, xF046n}x255E xF059 та {xF0461,…, xF046n}xF07CxF07CxF03DxF059.

Замість (x255E xF046, (xF07CxF03DxF046 та (xF07CxF07CxF03DxF046 писатимемо відповідно x255E xF046, xF07CxF03DxF046 та xF07CxF07CxF03DxF046xF02E.

Вкажемо основні властивості відношень x255E, xF07CxF03D, xF07CxF07CxF03D та xF07E:

1) xF046xF020xF020тавтологія xF020xF0DBxF020×255E xF046xF03B.

2) xF046xF020xF020всюди істинна xF020xF0DBxF020xF07CxF03DxF046 xF020xF0DBxF020 xF07CxF07CxF03DxF046xF03B.

3) якщо xF046×255E xF059, то xF046xF07CxF03DxF059; але не завжди із xF046xF07CxF03DxF059 випливає xF046×255E xF059;

4) якщо xF046xF07CxF03DxF059, то xF046xF07CxF07CxF03DxF059xF03B але не завжди із xF046xF07CxF07CxF03DxF046 випливає xF046xF07CxF03DxF059;

5) xF046xF07ExF059xF020xF0DBxF020xF07CxF03DxF046xF0ABxF059;

6) відношення x255E, xF07CxF03D та xF07CxF07CxF03D рефлексивні і транзитивні;

7) відношення xF07E рефлексивне, транзитивне і симетричне.

Враховуючи 2), той факт, що xF046 всюди істинна, позначаємо xF07CxF03DxF046.

Для 3) та 4) маємо такi контрприклади:

Приклад 7. xF024xxF024y (x=y)xF07CxF03DxF024yxF024x (x=y), але невiрно xF024xxF024y (x=y)x255E xF024yxF024x (x=y).

Приклад 8. (x=0)xF07CxF07CxF03D (x (x=0) але невiрно (x=0)xF07CxF03D (x (x=0).

(x=0)N (0)=T та ((x (x=0))N =F, тому (x=0((x (x=0))N (0)=F, звідки невiрно (x=0)xF07CxF03D (x (x=0). Але (x=0)xF07CxF07CxF03D (x (x=0) за теоремою замикання.

Приклад 9. Якщо х не вільне в xF059, то xF046xF0AExF059xF07CxF07CxF03DxF024xxF046xF0AExF059.

Нехай Х xF02D множина вільних імен формули xF046xF0AExF059. Припустимо супротивне: існує A=(A, xF073) така, що A xF07CxF03DxF020xF046xF0AExF059 та A xF07C (xF020xF024xxF046xF0AExF059. Тоді iснує d (AX таке, що (xF024xxF046xF0AExF059)А (d)=F, звідки (xF024xxF046)А (d)=Т та xF059А (d)=F. В силу (xF024xxF046)А (d)=Т маємо (А (d (х (b)=Т для деякого b (A. Але ім'я х не вільне в xF059, тому xF059А (d (х (b)=xF059А (d)=F. Звiдси дістаємо (xF046xF0AExF059)А (d (х (b)=F, що суперечить A xF07CxF03DxF020xF046xF0AExF059.

Формулу (мови L називають k-iстинною, якщо AxF07CxF03DxF046 для кожної k-елементної iнтерпретацiї A мови L.

Формула (скiнченно-iстинна, якщо xF046 є k-iстинною для кожного k>0. Отже, скiнченно-iстинна формула є iстинною при кожнiй скiнченнiй iнтерпретацiї.

Приклад 10. Формула xF024x1xF024×2…xF024xk ((x1(x2)&…&(x1(xk)&(x2(x3)&…&(xk-1(xk)), яку позначимо Ek, стверджує, що iснує (k рiзних елементiв областi iнтерпретацiї. Отже, Ek є n-істинною для всіх n (k.

Приклад 11. Формула xF024x1xF024×2…xF024xk (y ((y=x1)(…((y=xk)), яку позначимо Gk, cтверджує, що iснує (k рiзних елементiв областi iнтерпретацiї. Отже, Gk є n-iстинною для всiх 1(n (k.

Приклад 12. Формула Ek&Gk k-iстиннa, причому Ek&Gk не є n-iстинною для кожного n (k.

3. ЕКВІВАЛЕНТНІ ПЕРЕТВОРЕННЯ ФОРМУЛ Тeорeма 3.1 (семантична тeорeма єквiвалeнтностi). Нeхай A' отримана iз формули A замiною дeяких входжeнь формул B1, …, Bn на P1, …, Pn вiдповiдно. Якщо B1 xF07EP1, …, Bn xF07EPn, то AxF07EA'. xF020.

Формула A' називається варiантою формули A, якщо A' можна отримати iз A послiдовними замiнами такого типу: пiдформулу xF024xB замiнюємо на xF024yBx [y], дe y нe вiльна в B.

Тeорeма 3.2 (семантична тeорeма про варiанту). Якщо A' xF02D варiанта формули A, то AxF07EA'.

Формула A знаходиться в прeнeкснiй формi, якщо вона має вигляд Qx1… Qxn B, дe Qxk xF02D кванторний прeфiкс xF024xk або (xk, B xF02D бeзкванторна формула, яку називають матрицeю формули A.

Формулу в прeнeкснiй формi називають прeнeксною формулою.

У визначeннi прeнeксної форми насправдi фiгурують формули, для яких така прeнeксна форма є скорочeнням. Алe, коли мовиться про прeнeксну форму, квантор (нe прийнято виражати чeрeз xF0D8 та xF024.

Тeорeма 3.3. 1) (xB xF07ExF024xxF0D8B та xF0D8xF024xB xF07E (xxF0D8B;

2) xF024xBxF0DACxF07ExF024x (BxF0DAC) та (xBxF0DACxF07E (x (BxF0DAC), якщо x нe вiльна в C;

3) BxF0DAxF024xCxF07ExF024x (BxF0DAC) та BxF0DA (xCxF07E (x (BxF0DAC), якщо x нe вiльна в B.

Ввeдeмо прeнeкснi опeрацiї над формулами, якi дозволять кожну формулу пeрeтворити до eквiвалeнтної їй прeнeксної формули. Цi опeрацiї грунтуються на тeорeмах 4.3.2 та 4.3.3.

Пiд прeнeксними опeрацiями над формулою A розумiють такi опeрацiї:

a) замiна A дeякою її варiантою;

b) замiна в A пiдформул вигляду xF0D8xF024xB та xF0D8(xB на (xxF0D8B та xF024xxF0D8B відповідно;

c) замiна в A пiдформул вигляду QxBxF0DAC на Qx (BxF0DAС), якщо x нe вiльне в C;

замiна в A пiдформул вигляду BxF0DAQxC на Qx (BxF0DAC), якщо x нe вiльне в B.

Прeнeксною формою формули A називатимeмо прeнeксну формулу A', утворeну iз A за допомогою прeнeксних опeрацiй.

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

Розглянутий м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дформул вигляду BxF0AEQxC на Qx (BxF0AEC), якщо x нe вiльнe в B;

f) замiна в A пiдформул вигляду xF024xBxF0AEC на (x (BxF0AEC), та пiдформул вигляду (xBxF0AEC на xF024x (BxF0AEC), якщо 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)xF0DAxF024z ((x=y+z)&xF0D8(z=0)):

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

xF024z (x=y+z)xF0AExF024t (x=y)xF0DA (x=y+t)&xF0D8(t=0) xF02DxF020опeрацiя c);

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

(zxF024t ((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. Предикат «|xxF02Dy|=2» в АС (Z, {|xxF02Dy|=1, =}) виражається формулою (z (|xxF02Dz|=1&|zxF02Dy|=1&(x=y.

Приклад 7. Предикат «|xxF02Dy|=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) » .

Приклад 9. Aрифметичними є предикати: «x є парним числом» та «x ділиться на у». Ці предикати виражаються арифметичними формулами xF024y (x=y+y) та xF024z (x=y (z).

Приклад 10. Предикат «x є простим числом» арифметичний. Він ви-ражається арифметичною формулою xF024yxF024z (x=y (z (y=1(z=1)&(x=1.

Приклад 11. Предикати «x (y «та «x.

Використовуючи приклад 11, в записах арифметичних формул надалi вживатимемо скорочення вигляду x (y та x.

Приклад 12. Предикат «х (у «в АС N=(N, xF073ar), R=(R, xF073ar), Z=(Z, xF073ar) виражається рiзними арифметичними формулами. Наприклад, для N маємо xF024z (x+z=y); для R маємо xF024z (x+z (z=y), для Z маємо маємо xF024zxF024uxF024vxF024w (x+z (z+u (u+v (v+w (w=y).

Приклад 13. Арифметичними є наступні функцiї:

1) Функцiя x+y виражається арифметичною формулою z=x+y.

2) Функцiя x (y виражається арифметичною формулою z=x (y.

3) Функцiя x-y виражається арифметичною формулою y+z=x.

4) Функцiя [x/y] виражається арифметичною формулою.

z (y (x & x<(z+1)(y.

5) Функцiя mod (х, у) виражається арифметичною формулою.

xF024u (x=z+u (y & z.

] виражається арифметичною формулою.

z (z (x & z<(z+1)((z+1).

Тeорeма 4.1. Клас арифметичних множин замкнений вiдносно операцiй (, (та доповнення.

виража-ються вiдповiдно арифметичними формулами (xF0DA (, (&(та xF0D8(.

5. ГОМОМОРФІЗМИ АЛГЕБРАЇЧНИХ СИСТЕМ.

Для алгебраїчних систем однієї сигнатури введемо поняття гомоморфізму. Нехай A=(A, I, () та B=(B, I, ().

Гомоморфізмом АС A в АС B будемо називати відображення (: Аx2192 В таке, що:

xF02D для кожного f (Fs арності п для всіх a1, …, an (A маємо.

((fA (a1, …, an))=fВ (((a1), …, ((an)) (HF).

xF02D для кожного р (Рs арності п для всіх a1, …, an (A маємо.

якщо рA (a1, …, an))=Т, то рВ (((a1), …, ((an))=Т (HР) Гомоморфізм (АС A в АС B назвемо повним гомоморфізмом, якщо умова (HP) замінюється сильнішою умовою:

xF02D для кожного р (Рs арності п для всіх a1, …, an (A маємо.

рA (a1, …, an)) = рВ (((a1), …, ((an))=Т (ЕР) Повний гомоморфізм (назвемо сильним гомоморфізмом, якщо відображення (сюр'єктивне.

Повний гомоморфізм (назвемо ізоморфізмом, якщо відобра-ження (бієктивне.

B, якщо існує ізоморфізм (АС A в АС B.

на множині АС одної сигнатури є відношенням еквівалентності.

Ізоморфізм (АС A в АС A назвемо автоморфізмом алгебраїчної системи A.

є бієкцією Bx2192А, причому для + та = викону-ються умови (HF) та (EР). Отже, (є ізоморфізмом A в B.

є бієкцією Аx2192 В, причому для + та = виконуються умови (HF) та (EР). Отже, (є ізоморфізмом B в A.

. Тоді (є гомоморфізмом АС (N, {+, =}) в АС ({0, 1}, {+, =}), бо для + та = виконуються умови (HF) та (НР). Умова (EР) не виконується, бо 0(2, але ((0)=((1). Отже, такий гомоморфізм не є повним.

Приклад 3. Нехай A =(Z, {+, =}). Тоді ((x) = -х є бієкцією Zx2192Z, причому для + та = виконуються умови (HF) та (EР). Отже, (є автоморфізмом АС A =(Z, {+, =}).

Відношення еквівалентності (на множині А називають відношенням конгруентності на АС A=(A, (), якщо (стабільне відносно базових функцій АС A. Це означає: для кожного f (Fs арності п якщо a1 (b1, …, an (bn, то fA (a1, …, an) (fA (b1, …, bn).

Нехай A=(A, (), (xF02D відношення конгруентності на A. Фактор система B=(B, () системи A по відгошенню (задається так.

.

Для кожного f (Fs арності п задамо fB ([a1],…, [an])=[fA (a1 ,…, an)].

Для кожного p (Ps арності п покладемо.

знайдуться c1([a1], …, cn ([an] такі, що pA (c1, …, cn)=T.

Конгруентність відношення (гарантує коректність такого визна-чення функцій fB. Спрaвді, для довільних c1, …, cn таких, що [a1]=[c1], …, [an]=[cn], маємо a1 (c1, …, an (cn, звідки за конгруентні-стю (fA (a1, …, an) (fA (с1, …, сn), тому [fA (a1, …, an)]=. fA (c1, …, cn)].

наступним чином:

для кожного a (A покладемо ((а)=[a].

є гомоморфізмом АС A=(A, () в АС B=(B, (). Такий гомоморфізм називається канонічним.

{[0], [1]}. Тут [0] та [1] є відповідно множиною парних та непарних натуральних чисел.

(ar) наступним чином :

+([0], [0])=[0]; (([0], [0])=[0];

+([0], [1])=[1]; (([0], [1])=[0];

+([1], [0])=[1]; (([1], [0])=[0];

+([1], [1])=[0]; (([1], [1])=[1].

Константні символи 0 та 1 інтерпретуються як [0] та [1].

.

В подальших визначеннях імена & та (x похідних логічних операції & та (x трактуємо як символи розширеного алфавіту. Визначення формули мови розширеного алфавіту цілком зрозуміле.

Формулу, утворену з атомарних формул за допомогою символів логічних операцій (, & та (x, назвемо (-позитивною формулою.

Формулу, утворену з атомарних формул за допомогою допомогою символів логічних операцій (, &, (x та (x, назвемо позитивною формулою.

Кожне відображення (: Аx2192 В можна розширити до відображення (: АХ x2192ВХ таким чином: (([xi (ai] i (() = [xi (((ai)] i ((). Зокрема, (((a1, …, an)) = (((a1), …, ((an)).

Теорема 5.1. Нехай (: Аx2192 В xF02D гомоморфізм АС A=(A, () в АС B=(B, (). Тоді :

1) для кожного терма t сигнатури (з множиною предметних імен Х для довільних d (AХ маємо ((tA (d)) = tB (((d)) ;

2) для кожної (-позитивної формули (сигнатури (з множиною вільних імен Х для довільних d (AХ маємо: якщо (А (d)=Т, то (В (((d))=Т.

Теорема 5.2 Нехай сюр'єктивне відображення (: Аx2192 В є гомо-морфізмом АС A=(A, () в АС B=(B, (). Тоді виконується твердження 1) теореми 4.5.1 та.

2) для кожної позитивної формули (сигнатури (з множиною вільних імен Х для довільних d (AХ маємо: якщо (А (d)=Т, то (В (((d))=Т.

Наслідок. Нехай (xF02D сюр'єктивний гомоморфізм АС A=(A, () в АС B=(B, (). Тоді для кожної позитивної формули (сигнатури (якщо A xF07C ((, то B xF07C ((.

Теорема 5.3. Нехай (: Аx2192 В xF02D сильний гомоморфізм АС A=(A, () в АС B=(B, (). Тоді виконується твердження 1) теореми 4.5.1 та.

2) для кожної формули (сигнатури (з множиною вільних імен Х для довільних d (AХ маємо (А (d)=(В (((d)).

Наслідок 1 (теорема про ізоморфізм). Нехай (: Аx2192 В xF02D ізоморфізм АС A=(A, () в АС B=(B, (). Тоді виконуються твердження 1) теореми 4.5.1 та твердження 2) теореми 4.5.3.

Наслідок 2. Нехай (xF02D сильний гомоморфізм АС A=(A, () в АС B=(B, (). Тоді для кожної формули (сигнатури (A xF07C (((B xF07C ((.

={[0], [1]} є сюр'єктивним гомоморфізмом АС N в АС Nmod2. Розглянемо формулу ((1+1)=0, яку позначимо (. Тоді маємо N xF07C ((, але N mod2 xF07C ((, адже +([1], [1])=[0].

6. ІЗОМОРФІЗМ ТА ЕЛЕМЕНТАРНА ЕКВІВАЛЕНТНІСТЬ АГЕБРАЇЧНИХ СИСТЕМ. МЕТОД АВТОМОРФІЗМІВ.

АС A=(A, () та B=(B, () назвемо елементарно еквівалентними, якщо для кожної формули (сигнатури (A xF07C (((B xF07C ((.

B.

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

(Q; {(, =}). Справді, нехай (xF02D формула (x (y (x=y (y (y). Тоді (R; {(, =}) xF07C ((та (Q; {(, =}) xF07C ((.

(Q; {+, =}). Справді, нехай (xF02D формула (x (y (x=y+y). Тоді (Q; {+, =}) xF07C ((та (Z; {+, =}) xF07C ((.

(Z, {(, =}). Справді, нехай (xF02D формула (m (x (m (x). Тоді (N, {<, =}) xF07C ((та (Z, {<, =}) xF07C ((.

Із теореми про ізоморфізм (наслідок 1 теореми 4.5.3) випливає:

Твердження 1. Нехай (xF02D ізоморфізм АС A=(A, () в АС B=(B, (). Тоді для кожної формули (сигнатури (A xF07C (((B xF07C ((.

Твердження 2. Нехай (xF02D автоморфізм АС A=(A, (). Тоді для кожної формули (сигнатури (з множиною вільних імен Х для довільних d (AХ маємо (А (d)=(А (((d)).

(R, {<, =}), але ці АС неізоморфні, бо множина Q зліченна, а множина R має потужність континууму.

B.

Для доведення виразимості предикату P в АС A достатньо вказати таку формулу (, що P xF02D суть (A. В той же час для дове-дення невиразимості предикатів в АС доводиться використовувати потужніші засоби. Розглянемо метод доведення невиразимості предикатів в АС за допомогою автоморфізмів.

Теорема 6.1. Нехай (xF02D автоморфізм АС A=(A, (). Якщо преди-кат P: AXx2192{T, F} виразимий в A, то P (d)=P (((d)) для всіх d (AХ.

Нехай P виразимий в A деякою формулою (сигнатури (, тобто P xF02D суть (A. Використовуючи твердження 2, маємо P (d)=(А (d)=(А (((d))=Р (((d)) для довільних d (AХ.

Отже, для доведення невиразимості P в A досить знайти авто-морфізм (системи A такий, що порушується умова P (d)=P (((d)).

Приклад 4. Предикат «z=x+y» не виразимий в АС Z<=(Z, {<, =}).

Відображення ((х)=х+1 є автоморфізмом Z<, бо бієктивне і зберігає значення предикатів < та =. Але ((0)=1, тому вірно 0=0+0 та невірно ((0)=((0)+((0).

Приклад 6. Предикат «x<1 та невірно ((0)<((1).

Приклад 7. Предикат «y=x+1» не виразимий в АС (N, {y=x+2, =}).

є автоморфізмом такої АС, бо бієктивне і зберігає значення базових предикатів. Предикат «y=x+1 «позначимо Р (х, у). Тоді маємо Р (1, 0)=T та Р (((0), ((1))=Р (0, 1)=F.

Приклад 8. Предикат «х=2» не виразимий в АС (N, {(, =}).

Відображення, задане умовою ((2a (3b (c)=2b (3a (c, є автоморфізмом такої АС, бо бієктивне і зберігає значення функції (та предикату =. Предикат «х=2 «позначимо Р (х). Тоді Р (2)=T та Р (((2))=Р (3)=F.