СЕМАНТИКА НА ТЕРМОВЕТЕ И ФОРМУЛИТЕ
Ако D е някое множество, ще наричаме оценка на променливите в D всяко изображение на множеството Ξ на променливите в множеството D. Казано интуитивно, с избора на такова изображение ние избираме кои обекти от D да бъдат означени с отделните променливи в даден конкретен случай (за да избегнем някои усложнения в теоретичните разглеждания, приели сме да правим това за всичките безбройно много променливи от Ξ, въпреки че обикновено на практика във всеки конкретен случай се използват само краен брой променливи).
Когато е дадена една структура S=(Σ,D,I), оценките на променливите в D ще наричаме още техни оценки в S. Ще наричаме конфигурация всяка наредена двойка (S,v), където S е структура, а v е оценка на променливите в S. Под сигнатура на една конфигурация ще разбираме сигнатурата на нейния пръв член.
Нека Σ е една сигнатура. Ще разглеждаме термове и формули при сигнатура Σ, а също и конфигурации със сигнатура Σ, като за краткост ще ги наричаме просто термове, формули и конфигурации. Ще дефинираме какво ще разбираме под стойност на даден терм и на дадена формула в дадена конфигурация.
Да предположим, че е дадена една конфигурация (S,v), където S=(Σ,D,I). Стойността на произволен терм T в тази конфигурация ще бъде подходящо определен елемент на множеството D, който ще означаваме с TS,v. Дефиницията на този елемент е индуктивна и има следния вид, като коректността й се обосновава с еднозначния прочит на термовете: ако термът T е константа на Σ, полагаме TS,v = TS (т.е. TS,v = I(T) ), ако T е променлива, полагаме TS,v = v(T), а ако
T = φ(T1,…,Тn), където n е положително цяло число, φ е n-местен функционален символ на Σ и T1, …, Тn са термове, приемаме, че
TS,v = φS(T1S,v,…,ТnS,v) (т.е. че TS,v = I(φ)(T1S,v,…,ТnS,v) ).
Предполагайки, че е дадена една структура S=(Σ,D,I), ние за всяка формула F ще дефинираме нейна стойност FS,v в произволна конфигурация (S,v), като тази стойност ще бъде винаги някое от числата 0 и 1 (интуитивно те ще играят ролите на "лъжа" и "истина"). Ако можехме да се ограничим само с безкванторни формули, дефиницията би била в същия дух както дефиницията за стойност на терм, но при разглеждането на произволни формули нещата са по-сложни и е подходящо да въведем първо едно спомагателно понятие. А именно, за произволна оценка v на променливите в множеството D, произволна променлива ξ и произволен елемент d на D ние ще въведем наименование и означение за онази оценка на променливите в D, която съпоставя на променливата ξ елемента d, а за всички други променливи съвпада с v. Ще наричаме така описаната оценка модификация на v върху ξ чрез d и ще я означаваме с v[ξ→d]. Eто как изглежда дефиницията за стойност на формула при използване на въведеното спомагателно понятие там, където е подходящо (коректността на дефиницията се обосновава с еднозначния прочит на формулите):
а) ако F = π(T1,…,Тn), където n е положително цяло число, π е n-местен предикатен символ на Σ и T1, …, Тn са термове, полагаме
FS,v = πS(T1S,v,…,ТnS,v) (т.е. FS,v = I(π)(T1S,v,…,ТnS,v) ), a ako F е нулместен предикатен символ на Σ, полагаме FS,v = FS (т.е. FS,v = I(F) );
б) ако F = true, то FS,v = 1, а ако F = fail, то FS,v = 0;
в) ако F = not(F0) за дадена формула F0, то FS,v = 1 − F0S,v;
г) ако F = (F1,…,Fn), където n е цяло число, по-голямо от 1, а F1, …, Fn са формули, то FS,v = min { F1S,v, …, FnS,v };
д) ако F = (F1;…;Fn), където n е цяло число, по-голямо от 1, а F1, …, Fn са формули, то FS,v = max { F1S,v, …, FnS,v };
е) ако F = (ξ,F0) за дадена променлива ξ и дадена формула F0, то FS,v = min { F0S,v[ξ→d] | d∈D };
ж) ако F = (ξ;F0) за дадена променлива ξ и дадена формула F0, то FS,v = max { F0S,v[ξ→d] | d∈D }.
За една формула F ще казваме, че е вярна (или изпълнена) в дадена конфигурация (S,v), ако е в сила равенството FS,v = 1. За да изразим, че F е вярна в конфигурацията (S,v), ще си служим и с означението S,v ⊨ F. Чрез означението S,v ⊭ F ще изразяваме пък това, че F не е вярна в конфигурацията (S,v), т.е. че имаме равенството FS,v = 0.
Дадените по-горе дефиниции осигуряват, че отрицанието на една формула е вярно в дадена конфигурация точно тогава, когато самата формула не е вярна в тази конфигурация, че конюнкцията на какъв да е даден краен брой формули е вярна в дадена конфигурация точно тогава, когато в нея са верни всичките тези формули, а дизюнкцията на въпросните формули е вярна в дадена конфигурация точно тогава, когато в нея е вярна някоя от тези формули. Дефинициите осигуряват още следното: генерализацията на една формула по една променлива ξ е вярна в дадена конфигурация (S,v) точно тогава, когато самата формула е вярна във всяка от конфигурациите (S,v[ξ→d]), където d принадлежи на носителя на S, а екзистенциализацията на формулата е вярна в конфигурацията (S,v) точно тогава, когато формулата е вярна в поне една от споменатите други конфигурации.
Дотук се занимавахме със стойности на термове и формули при една фиксирана сигнатура. Да предположим сега, че са дадени структура S със сигнатура Σ и нейно обогатяване S′, което е със сигнатура Σ′. Понеже Σ′ съдържа Σ, термовете и формулите при сигнатура Σ същевременно са съответно термове и формули при сигнатура Σ′. Освен това, тъй като S и S′ имат един и същ носител, всяка оценка на променливите в S е тяхна оценка в S′ и обратно. С индукция се доказва, че за всеки терм T в сигнатура Σ и всяка оценка v на променливите в S имаме равенството TS,v = TS′,v, а след това с още една индукция се установява, че FS,v = FS′,v за всяка формула F в сигнатура Σ и всяка оценка v на променливите в S.
Последно изменение: 12.08.2004 г.