Семантика на формулите

СЕМАНТИКА НА ФОРМУЛИТЕ

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

Предполагайки, че е дадена една структура S=(Σ,D,I), за всяка формула φ ще дефинираме нейна стойност φ^S,v в произволна конфигурация (S,v), като тази стойност ще бъде винаги някое от числата 0 и 1 (интуитивно те ще играят ролите на „лъжа“ и „истина“). Дефиницията е чрез уславянето, че при всеки избор на формули φ и ψ, на променлива ξ и на оценка v в S имаме равенствата

(¬φ)^S,v = 1 − φ^S,v,
(φ & ψ)^S,v = min{φ^S,v,ψ^S,v},
(φ ∨ ψ)^S,v = max{φ^S,v,ψ^S,v},
(∀ξφ)^S,v = min{φ^S,v[ξ→d] | d∈D},
(∃ξφ)^S,v = max{φ^S,v[ξ→d] | d∈D}.
Тази дефиниция е коректна, защото всяко непразно подмножество на множеството {0,1} има най-малък и най-голям елемент и е налице еднозначен прочит на формулите. Отбелязваме още, че за стойността на отрицателен литерал тя дава същото, което приехме във въпроса „Прилагане на субституция към литерал и към дизюнкт“.

Забележка. Макар горната дефиниция еднозначно да определя стойността на всяка формула в дадена структура при дадена оценка на променливите, фактическото намиране на тази стойност в някои случаи се оказва много трудно. Главната причина за това е в обстоятелството, че понякога за да пресметнем дясната страна на някое от последните две равенства от дефиницията, може да е нужно да търсим стойността на формулата φ в безбройно много различни конфигурации.

За една формула φ ще казваме, че е вярна в дадена конфигурация (S,v), ако е в сила равенството φ^S,v = 1. Дефинициите, които дадохме, осигуряват, че отрицанието на една формула е вярно в дадена конфигурация точно тогава, когато самата формула не е вярна в тази конфигурация, и че конюнкцията на две формули е вярна в дадена конфигурация точно тогава, когато в нея са верни тези две формули, а дизюнкцията им е вярна в дадена конфигурация точно тогава, когато в нея е вярна някоя от тях. Дефинициите осигуряват още следното: генерализацията на една формула по една променлива ξ е вярна в дадена конфигурация (S,v) точно тогава, когато самата формула е вярна във всяка от конфигурациите (S,v[ξ→d]), където d принадлежи на носителя на S, а екзистенциализацията на формулата е вярна в конфигурацията (S,v) точно тогава, когато формулата е вярна в поне една от споменатите други конфигурации.

Пример. В пример 3 от въпроса „Формули на предикатното смятане“ разглеждахме формулата

¬ m(X,X,X) & ∀Y ∀Z( ¬ m(Y,Z,X) ∨ (m(Y,Y,Y) ∨ m(Z,Z,Z))) , където m е триместен предикатен символ. Отбелязахме, че ако S е структура с носител множеството на естествените числа, за която множеството на истинност на предиката m^S се състои от тройките (i,j,k) от естествени числа с k = ij, то при интуитивно описаната семантика на формулите тази формула е вярна в S точно тогава, когато стойността на X е просто число. Строгата версия на това твърдение е, че ако S е структура от споменатия вид, то въпросната формула е вярна в S точно при онези оценки, които съпоставят на променливата X просто число. За да проверим, че така изказаната версия на твърдението е в сила, да предположим, че S е структура от споменатия вид, а v е произволна оценка на променливите в S. За да бъде вярна разглежданата формула в S при оценката v, необходимо и достатъчно е в S при оценката v да бъде вярна всяка от двете формули ¬ m(X,X,X) ,
∀Y ∀Z( ¬ m(Y,Z,X) ∨ (m(Y,Y,Y) ∨ m(Z,Z,Z))) . Първата от тях е вярна в S при оценката v точно тогава, когато числото v(X) е различно от 0 и от 1. Втората пък е вярна в S при оценката v точно тогава, когато при всеки избор на естествено число l формулата ∀Z( ¬ m(Y,Z,X) ∨ (m(Y,Y,Y) ∨ m(Z,Z,Z))) е вярна в S при оценката v[Y→l]. Това обаче е равносилно с изискването при всеки избор на естествени числа l и m формулата ¬ m(Y,Z,X) ∨ (m(Y,Y,Y) ∨ m(Z,Z,Z)) да бъде вярна в S при оценката v[Y→l][Z→m], т.е. числото v(X) да е различно от произведението на числата l и m или пък някое от тези две числа да не надминава 1. В крайна сметка получихме условието, числото v(X) да е по-голямо от 1 и да не може да се представи като произведение на две числа, по-големи от 1.

Дотук се занимавахме със стойности на формули в една фиксирана структура. Да предположим сега, че са дадени структура S със сигнатура Σ и нейно обогатяване S′, което е със сигнатура Σ′. Тогава формулите при сигнатура Σ същевременно са формули и при сигнатура Σ′, а всяка оценка на променливите в S е тяхна оценка в S′ и обратно. С индукция се доказва, че за всеки формула φ при сигнатура Σ и всяка оценка v на променливите в S имаме равенството φ^S,v = φ^S′,v.

Последно изменение: 1.08.2008 г.

(¬φ)^S,v	=	1 − φ^S,v,
(φ & ψ)^S,v	=	min{φ^S,v,ψ^S,v},
(φ ∨ ψ)^S,v	=	max{φ^S,v,ψ^S,v},
(∀ξφ)^S,v	=	min{φ^S,v[ξ→d] \| d∈D},
(∃ξφ)^S,v	=	max{φ^S,v[ξ→d] \| d∈D}.