Определяне на истината

44. Какъв е естественият подпис за теорията на полето? Възможно ли е да напишете под формата на формула на този подпис твърдението, че полето има характеристика 2? крайната характеристика? алгебрично затворена?

3.2. Определяне на истината

От примерите, дадени по-горе, значението на формулата вероятно е ясно, тоест е ясно при кои интерпретации на този подпис и за кои елементи формулата е вярна. Въпреки това, за любителите на строгостта, ние даваме формално определение на истината. (Подробностите му ще са необходими, когато проверим истинността на получените формули, вижте раздел 4.3.)

На първо място, нека дефинираме формално концепцията за параметър на формула (променлива, от стойността на която може да зависи истинността на формула). Според тази дефиниция, да речем, формулата x y A (x; y) няма параметъра-

trov, а формулите y A (x; y) и (A (x) x B (x; x)) имат

единственият параметър x. Ето как изглежда дефиницията:

• Параметрите на даден термин са всички отделни променливи, включени в него.

• Параметрите на атомната формула са параметрите на всички членове, включени в нея.

• Параметрите на формулата ¬ 'са същите като тези на формулата'.

• Параметри на формули ('), (') и ('→)

са всички параметри на формулата ", както и всички параметри на формулата .

• Параметрите на формулите 'и' са всички параметри на формулата ', с изключение на променливата .

Параметрите понякога се наричат ​​безплатни променливи на формула. Имайте предвид, че формула може да има както параметъра x, така и да използва (другаде) квантора x. Както се казва в случая, едно и също

94 Езици от първи ред [гл. 3]

същата променлива има свободни и свързани събития. Безплатно въвеждане на променлива | това е запис, който не е включен в обхвата на едноименния квантор. Ако внимателно дефинирате този обхват, е лесно да проверите дали параметрите на формулата | това са само променливи, които имат безплатни записи.

Сега искаме да дефинираме концепцията за формула, която е вярна в тази интерпретация за дадените стойности на параметрите. Технически е по-лесно да се приеме, че някои стойности са присвоени на всички отделни променливи, и след това да се докаже, че променливите, които не са параметри, не влияят на истинността на формулата.

Така че, нека подписът и някои тълкувания на този подпис бъдат фиксирани. Оценката е картографиране, което присвоява на всяка отделна променлива някакъв елемент от множеството, който е носител на интерпретацията. Този елемент ще се нарича стойността на променливата за тази оценка.

Нека дефинираме индуктивно стойността на члена t за тази оценка, която ще обозначим с [t] ().

• За променливи вече е дефиниран.

• Ако t е константа (функция с нулево място-

рационален символ), тогава [t] () не зависи и е равна на стойността на тази константа за дадена интерпретация (припомнете, при интерпретацията всяка константа е свързана с някакъв елемент на носителя).

• Ако t има формата f (t 1;::; t m), където f | функция-

националният символ на валентност m и t 1;::; t m | термини, тогава [t] () е [f] ([t 1] ();::; [tm] ()), където [f] е функцията, съответстваща на символа f в нашата интерпретация, и [ti ] () е стойността на термина ti при оценка .

Сега можете да определите стойността на формулата 'за дадена оценка в тази интерпретация, която се обозначава с ['] () и може да бъде равна на AND или L; В първия

случай формулата се нарича true, във втория | невярно. Това определение също е индуктивно:

• Определя се стойността на атомната формула A (t 1;::; t m)-

се представя като [A] ([t 1] ();::; [t m] ()), където [A] | предикатът, съответстващ на предикатния символ А в разглежданата интерпретация. Ако формулата е предикатен символ с нулево място, тогава нейната стойност не зависи от оценката и е стойността на този символ.

• [¬ '] () се дефинира като ¬ [' ()], където ¬ се разбира като операция в Б. С други думи, формулата ¬ '

е вярно при оценката, ако и само ако формулата 'е невярна при тази оценка.

• ['] () се дефинира като ['] () [] (), където от дясната страна се разбира като операция в Б. (С други думи, формула (') е вярна, когато се оценява дали и само ако и двете формули

и са верни при тази оценка.) По подобен начин-

• Formula 'е вярно при оценяването само и само-

до когато формулата 'е вярна за всяка оценка на 0, което съвпада с навсякъде, с изключение на стойността-

променливата (която в резултата 0 може да бъде

всякакви). С други думи, ако обозначим с + (7 → m) оценката, при която стойността на промените-

е равно на m, а останалите променливи приемат същите стойности като в оценката, тогава

(От дясната страна има безкрайна връзка, което е вярно, ако всички негови термини са верни.)

Езици от първи ред

• Формула 'е вярна на оценката, ако и само

тогава, когато формулата 'е вярна при някаква оценка 0, която съвпада с навсякъде, освен със стойността

променлива (която в оценката 0 може да бъде всяка-

bym). С други думи,

(От дясната страна има безкрайна дизюнкция, което е вярно, ако поне един от нейните членове е истина.)

Имайте предвид, че в последните две точки стойността на променливата не играе роля в оценката. Това улеснява доказването (чрез индукция върху конструкцията на формулата) следното твърдение: ако две оценки 1 и 2 дават еднакви стойности на всички параметри на формулата ', тогава ['] (1) = = [ '] (2). С други думи, истинността на формулата се определя от стойностите на нейните параметри.

45. Направете това индуктивно разсъждение в детайли.

46. ​​Горните определения се отнасят за всеки

формула, включително странната формула y A (x). Какъв вид

има ли параметри? При какви стойности на параметрите е вярно? (Отговор: той има единичен параметър x и е еквивалентен на формулата A (x).)

47. В кой случай формулата x x A (x) ще бъде вярна? Същият въпрос за формулата x x A (x). (Отговор: първата от тези формули е еквивалентна на формулата x A (x), а втората | на формулата x A (x).)

Формула се нарича затворена, ако няма параметри. Затворените формули се наричат ​​още съждения. Както показахме, истинността на затворена формула се определя от избора на интерпретация (и не зависи от стойностите на променливите).

3.3. Изразими предикати

Нека някакъв подпис и неговата интерпретация да бъдат фиксирани с подкрепа М. Искаме да дефинираме концепцията

изразен (използвайки формулата на даден подпис в дадена интерпретация) k-ary предикат.

Нека да изберем k променливи x 1;::; x k. Помислете за произволна формула ', всички параметри на която се съдържат в списъка x 1;::; x k. Истинността на тази формула зависи само от стойностите на променливите x 1;::; x k. Това поражда картографирането M k → B = < И; Л >, това не е-

което е k-ary предикат на М. За този предикат се казва, че се изразява с формулата '. Всички предикати, които могат да бъдат получени по този начин, се наричат ​​изразими. (Ясно е, че конкретният избор на списъка с променливи няма значение.) Съответните подмножества на множеството M k (истинските домейни на изразими предикати) също се наричат ​​изразими.

48. Докажете, че пресичането, обединението и разликата на две изразими множества са изразими. Докажете, че проекцията на k-размерно изразимо множество по една от "координатните оси" е (k - 1) -измерно изразимо

Пример. Подписът съдържа символ на единична функция S и символ за равенство на предикат на две места (=). Нека разгледаме тълкуването на този подпис. Избираме естествената серия N.

Символът S ще означава функцията за добавяне на един (можете да мислите за S като съкращение за наследник | наследник). Знакът за равенство се тълкува като съвпадение на елементи.

Лесно е да се провери дали унарният предикат "да бъде нула" е изразим в това тълкуване, въпреки факта, че няма константа за нула в подписа. Всъщност тя се изразява с формулата

с един параметър x.

Още по-лесно е да изразите в този подпис предиката на две места „да бъде повече с 2“, докато дори не са необходими квантори: y = S (S (x)).

Езици от първи ред

Любопитно е, че дори в такава проста ситуация е възможно да се формулира смислен проблем: да се изрази предикатът y = x + N, където N | голям брой (да речем, милиард), използвайки значително по-кратка формула от y = S (S (:: (S (x)):)). Изненадващо, това е напълно възможно и съответната формула може добре да се побере на лист хартия.

49. Докажете, че предикатът y = x + N може да бъде изразен с формула на посочения подпис, чиято дължина е O (log N). (Съвет. Ако научихме как да изразяваме y = x + n, можем да изразим y = x + 2n, използвайки формулата

z ((z = x + n) (y = z + n))

(в която съответните формули се означават с z = x + n и y = z + n). Това само по себе си не прави нищо, тъй като дължината на формулата се е удвоила, но можете да използвате този трик:

z u v (((u = x v = z) (u = z v = y)) → (v = u + n)):

След това можете да използвате означението на числото N в двоичната бройна система.)

Може да се покаже, че в този подписващ квантор едва ли увеличава набора от изразими предикати: всеки изразен предикат ще бъде изразен с формула без квантор (вероятно много по-дълго), ако добавим константата 0 към подписа. в раздел 3.6. .

За да свикнете с изразимостта, разгледайте друг пример. Нека подписът съдържа предикат за равенство и троен предикат С. Помислете за интерпретация, при която опората е набор от точки на равнината, равенството се тълкува като съвпадение на точки, а C (x; y; z) означава, че точките x и y са на еднакво разстояние от точка z. Оказва се, че този предикат е достатъчен, за да изрази горе-долу всички традиционни понятия за елементарната геометрия.

Как, например, да запиша, че три различни точки A; В; C са колинеарни? Ето как: „не е-