Previous  Next  Contents
 

 

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

    Нека е дадена една произволна структура S. За всяка логическа формула F и всяка оценка v в S на променливите ще дефинираме стойност на F в S при оценката v, която стойност ще бъде някое от числата 0 и 1 и ще бъде означавана с FS,v. Дефиницията ще бъде индуктивна, като за атомарни формули ще използваме вече дадената дефиниция за стойност. С оглед на точката, в която ще се дефинира стойността на формула с функтор for_all или for_some, ще въведем предварително едно означение за определен вид модификации на оценки в S на променливите. Нека носителят на S е дадено множество D. Тогава за коя да е оценка v в S на променливите, коя да е променлива X и кой да е елемент x на D ние ще означаваме с v[X:x] онази оценка в S на променливите, която съпоставя на X елемента x и за всички други променливи съвпада с v; оценката v[X:x] ще наричаме модификация на v върху X чрез x. Сега вече сме готови да дефинираме какво ще разбираме под FS,v за произволна неатомарна формула F и произволна оценка v в S на променливите. Това ще направим чрез следните уславяния:
    1. Полагаме  trueS,v=1,  falseS,v=0.
    2. При всеки избор на положително число n, по-голямо от 1, и на формули F1, F2, ..., Fn полагаме

(F1,F2...,Fn)S,v = min{F1S,v, F2S,v, ..., FnS,v},
   (F1;F2...;Fn)S,v = max{F1S,v, F2S,v, ..., FnS,v}.
    3. За всяка формула F полагаме  not(F)S,v = 1 - FS,v.
    4. За всяка променлива X и всяка формула F полагаме
   for_all(X:F)S,v = min{FS, v[X:x] | xОD},
for_some(X:F)S,v = max{FS,v[X:x] | xОD}.

    Както при атомарните формули, уславяме се да казваме, че дадена форнула е вярна в S при дадена оценка в S на променливите, ако стойността на формулата в S при тази оценка е 1. Отново ще използваме знаците  ъ=  и  ъ№  за символичното записване съответно на наличие или на отсъствие на горното положение на нещата, т.е. записите  S,v ъ= F  и  S,v ъ№ F  ще означават съответно, че формулата F е вярна и че е невярна в S при оценката v. Без затруднение се проверява, че са в сила следните четири твърдения:
    I. Празната конюнкция е вярна в S при всяка оценка на променливите, а празната дизюнкция не е вярна в S при никоя оценка на променливите.
    II. Конюнкцията на ненулев краен брой формули е вярна в S при дадена оценка на променливите точно тогава, когато всяка от тези формули е вярна в S при дадената оценка, а дизюнкцията на същите формули е вярна в S при дадената оценка точно тогава, когато някоя от формулите е вярна в S при тази оценка.
    III. Отрицанието на една формула е вярно в S при дадена оценка на променливите точно тогава, когато самата формула не е вярна в S при същата оценка.
    IV. Генерализацията на една формула по дадена променлива X е вярна в S при дадена оценка на променливите точно тогава, когато самата формула е вярна в S при всяка модификация на дадената оценка върху X чрез елемент на D, а екзистенциализацията на същата формула по X е вярна в S при дадената оценка точно тогава, когато формулата е вярна в S при някоя модификация на дадената оценка върху X чрез елемент на D.

    Забележка. Ако в твърдението II пропуснем думата "ненулев", можем да считаме, че полученото твърдение включва в себе си и твърдението I.

    Когато се занимавахме със семантиката на атомарните формули, доказахме едно твърдение, което нарекохме лема за базисна роля на променливите на една атомарна формула. То се обобщава за произволни формули по следния естествен начин:

    Лема за базисна роля на променливите на една формула. За произволна формула F имаме, че ако две оценки v и vў на променливите в структурата S съвпадат върху множеството FVAR(F), то е в сила равенството FS,v=FS,vў.

    Доказателство. Ще използваме индукция, съобразена с дефиницията на понятието формула. Знаем, че твърдението е вярно, когато F е атомарна формула. То очевидно е вярно и в случая, когато F е празната конюнкция или празната дизюнкция, защото тогава стойността на F изобщо не зависи от избора на оценката. Да предположим сега, че свойството, за което става дума в това твърдение, е налице за всяка една от дадени формули F1, F2, ..., Fn, където n е цяло число, по-голямо от 1. Ще покажем, че въпросното свойство е налице също за тяхната конюнкция и за тяхната дизюнкция. За конюнкцията разсъжденията изглеждат така: ако две оценки v и vў в S на променливите съвпадат върху FVAR((F1,F2...,Fn)), тези оценки ще съвпадат и върху всяко от множествата FVAR(Fi), i=1,2,...,n, следователно ще имаме равенствата FiS,v=FiS,vў, i=1,2,...,n, откъдето виждаме, че

min{F1S,v, F2S,v, ..., FnS,v} = min{F1S,vў, F2S,vў, ..., FnS,vў},
т.е.  (F1,F2...,Fn)S,v = (F1,F2...,Fn)S,vў. Разсъжденията за дизюнкцията на F1, F2, ..., Fn са аналогични. Още по-лесно се показва, че винаги, когато твърдението е вярно за една формула, то е вярно и за нейното отрицание. Остава да покажем, че свойството от това твърдение се запазва при генерализация и при екзистенциализация. Нека F е формула, притежаваща това свойство. Ще покажем, че при всеки избор на променлива X то е налице и за формулите for_all(X:F) и for_some(X:F). Ще извършим разсъжденията за първата от тях, а за втората те са аналогични. И така, да предположим. че две оценки v и vў в S на променливите съвпадат върху множеството FVAR(for_all(X:F)). Това означава, че те съвпадат за всички променливи, които принадлежат на множеството FVAR(F) и са различни от X. Оттук следва, че при всеки избор на елемент x на D оценките v[X:x] и vў[X:x] съвпадат навсякъде в множеството FVAR(F) и значи имаме равенството FS,v[X:x] = FS,vў[X:x]. Следователно
min{FS,v[X:x] | xОD} = min{FS,vў[X:x] | xОD},
т.е.  for_all(X:F)S,v = for_all(X:F)S,vў. ї
    Следствие. Ако F е затворена формула, то FS,v=FS,vў за всеки две оценки v и vў в S на променливите.

    Току-що полученото следствие показва, че когато F е затворена формула, стойността FS,v не зависи от избора на оценката v. Тази независеща от v стойност ще наричаме стойност на F в S и ще я означаваме с FS (ясно е, че тя е някое от числата 0 и 1). За една затворена формула F ще казваме, че е вярна в S, и ще пишем  S ъ= F,  когато FS=1 (разбира се, записът  S ъ№ F  ще означава, че F не е вярна в S, т.е. че имаме равенството FS=0). Казано малко по-интуитивно, затворените формули изразяват твърдения, които могат да бъдат верни или неверни в зависимост само от разглежданата структура, докато верността на формулите, които имат свободни променливи, в общия случай зависи не само от избора на структурата, но и от стойностите на променливите.
 

Последно изменение: 13.02.2003 г.
 
 Previous  Next  Contents