Contents

Примерни задачи за държавен изпит и техни решения

    Задача 1. Да се изследва дали от формулите
            $x "y ( p(x,y) Ъ p(y,x) ),   $x "y ( Ш p(x,y) Ъ Ш p(y,x) )
следва формулата
            $x $y ( p(x,y) & Ш p(y,x) ).

    В следващите задачи нека j и y са съответно формулите
            $x ( Ш $y p(y,x) & "y $z ( p(x,z) & p(y,z) ) ) ,
            "x ( Ш "y p(y,x) Ъ $y "z ( p(x,z) Ъ p(y,z) ) ) .

    Задача 2. Покажете, че никоя от формулите j и y не е тъждествено вярна.

    Задача 3. Изследвайте дали някоя от формулите j и y следва от другата.

    Задача 4. За всяко от множествата {j,y} и {Шj,Шy} изследвайте дали е изпълнимо.

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

    Решение на задача 1. Въпросът, поставен в задачата, има същия отговор както въпроса дали е неизпълнимо множеството от формули

{ $x "y ( p(x,y) Ъ p(y,x) ),  $x "y ( Ш p(x,y) Ъ Ш p(y,x) ),  Ш $x $y ( p(x,y) & Ш p(y,x) ) }.
Като преработим третата от горните формули с помощта на някои от еквивалентностите, отнасящи се до отрицание (вж. края на въпроса "Следване на една формула от друга. Еквивалентни формули"), и се избавим от кванторите за съществуване в първите две формули с помощта на скулемови константи a и b (вж. въпроса "Скулемова нормална форма"), виждаме, че изпълнимостта на горното множество е равносилна с изпълнимостта на следното множество от универсални формули:
{ "y ( p(a,y) Ъ p(y,a) ),  "y ( Ш p(b,y) Ъ Ш p(y,b) ),  "x "y ( Ш p(x,y) Ъ p(y,x) ) }.
Ще изследваме дали това множество е изпълнимо, като приемем, че Ербрановият универсум е двуелементното множество {a,b}, и си послужим с метода на Ербран. Работейки по този начин, свеждаме разглеждания въпрос за изпълнимост към въпроса за изпълнимостта на множеството от следните осем затворени безкванторни формули:
p(a,a) Ъ p(a,a),  p(a,b) Ъ p(b,a),  Ш p(b,a) Ъ Ш p(a,b),  Ш p(b,b) Ъ Ш p(b,b), 
Ш p(a,a) Ъ p(a,a),  Ш p(a,b) Ъ p(b,a),  Ш p(b,a) Ъ p(a,b),  Ш p(b,b) Ъ p(b,b).
Последния въпрос ще решим с помощта на метода на резолюцията (разбира се няма пречки въпросът да бъде решен и непосредствено). А именно, за да бъде горното множество изпълнимо, необходимо и достатъчно е чрез никакъв брой прилагания на резолюция празният дизюнкт да не може да се получи от дизюнктите, съответни на формулите от множеството, т.е. от дизюнктите
{ p(a,a) },  { p(a,b),  p(b,a) },  { Ш p(b,a),  Ш p(a,b) },  { Ш p(b,b) }, 
{ Ш p(a,a) },  { Ш p(a,b),  p(b,a) },  { Ш p(b,a),  p(a,b) },  { Ш p(b,b) }.
Очевидно от двата измежду тях, които имат елемент p(a,b), можем чрез резолюция да получим дизюнкта { p(a,b) }, а пък от двата, които имат елемент Ш p(a,b) - дизюнкта { Ш p(a,b) }. От така получените два дизюнкта обаче чрез резолюция се получава празният дизюнкт. Значи множеството от разглежданите осем безкванторни формули е неизпълнимо. Тогава ще бъдат неизпълними и преди това разгледаните други две множества от формули, а това показва, че третата от споменатите в задачата формули следва от другите две.

    Решение на задача 2. Това, че формулата j не е тъждествено вярна, се вижда например от факта, че тя не е вярна в структурите с носител от един елемент. И наистина, в такава структура има само една оценка на променливите и поставянето на квантори не влияе върху стойността на формулите при тази оценка. Значи ако S е структура с едноелементен носител, то стойността на j в S съвпада със стойността, която има в S при единствената оценка на променливите следната формула (получена от j чрез пропускане на кванторите):

Ш p(y,x) & ( p(x,z) & p(y,z) ) .
Очевидно е обаче, че въпросната стойност е винаги 0. Твърдението, отнасящо се за формулата y, ще докажем, като покажем с помощта на изучени общи методи, че формулата Шy е изпълнима (начинът, по който постъпихме в случая на j, сега не би ни помогнал - вижда се, че y е вярна в структурите с едноелементен носител). Първо привеждаме Шy в пренексен вид и виждаме, че е еквивалентна на формулата
$x "y $z ( p(y,x) & Ш p(x,z) & Ш p(y,z) ) .
Като се избавим от двата квантора за съществуване в горната формула с помощта на скулемова константа a и скулемов едноместен функционален символ f, стигаме до заключението, че е достатъчно да установим изпълнимостта на формулата
"y ( p(y,a) & Ш p(a,f(y)) & Ш p(y,f(y)) ) .
Работейки по метода на Ербран, виждаме, че нейната изпълнимост е равносилна с изпълнимост на множеството на всички формули от вида
p(Y,a) & Ш p(a,f(Y)) & Ш p(Y,f(Y)),
където Y е затворен терм, или, все едно, на множеството на всички формули от видовете  p(Y,a),  Ш p(a,f(Y))  и  Ш p(Y,f(Y)),  където Y е затворен терм. Въпроса за изпълнимостта на последното множество ще решим с помощта на следствието от основната лема за осъществимост (вж. края на въпроса "Атомарни формули"). А именно, нека T е множеството на всички формули от вида p(Y,a), където Y е затворен терм, а F пък е множеството, състоящо се от всички формули от видовете p(a,f(Y)) и p(Y,f(Y)), където Y пак е затворен терм. Според споменатото следствие интересуващата ни изпълнимост е равносилна с условието множествата T и F да нямат общи елементи. Очевидно в случая това условие е изпълнено. С това изпълнимостта на формулата Шy е доказана.

    Решение на задача 3. Въпросът дали от j следва y има същия отговор както въпроса дали е неизпълнимо множеството {j,Шy}. Като представим елементите на това множество в пренексен вид, виждаме, че изпълнимостта на множеството е равносилна с изпълнимост на множеството

{ $x "y $z ( Ш p(y,x) & p(x,z) & p(y,z) ) ,  $x "y $z ( p(y,x) & Ш p(x,z) & Ш p(y,z) ) } .
Като отстраним кванторите за съществуване чрез скулемизация, получаваме, че отговорът на въпроса дали от j следва y съвпада с отговора на въпроса дали е неизпълнимо множеството
{ "y ( Ш p(y,a) & p(a,f(y)) & p(y,f(y)) ) ,  "y ( p(y,b) & Ш p(b,g(y)) & Ш p(y,g(y)) ) } ,
където a и b са константи, а f и g са едноместни функционални символи. Прилагайки метода на Ербран, виждаме, че изпълнимостта на това множество е равносилна с изпълнимост на множеството, състоящо се от всички формули от видовете Ш p(Y,a) & p(a,f(Y)) & p(Y,f(Y))  и  p(Y,b) & Ш p(b,g(Y)) & Ш p(Y,g(Y)),  където Y е затворен терм, или, все едно, с изпълнимост на множеството, състоящо се от всички формули от видовете
Ш p(Y,a),  p(a,f(Y)),  p(Y,f(Y)),  p(Y,b),  Ш p(b,g(Y)),  Ш p(Y,g(Y)),
където Y е затворен терм. Изпълнимостта на последното множество е ясна от следствието от основната лема за озъществимост. С това е показано, че от формулата j не следва формулата y. Отговорът на другия въпрос - дали от y следва j - също е отрицателен. Това се вижда много по-лесно, а именно достатъчно е да забележим, че в структурите с едноелементен носител формулата y е вярна, а формулата j не е вярна (вж. решението на задача 2).

    Решение на задача 4. Като представим елементите на множеството {j ,y} в пренексен вид, виждаме, че изпълнимостта на това множество е равносилна с изпълнимост на множеството

{ $x "y $z ( Ш p(y,x) & p(x,z) & p(y,z) ) ,  "x $y "z ( Ш p(y,x) Ъ p(x,z) Ъ p(y,z) ) } .
Тя от своя страна е равносилна с изпълнимост на множеството
{ "y ( Ш p(y,a) & p(a,f(y)) & p(y,f(y)) ) ,  "x "z ( Ш p(g(x),x) Ъ p(x,z) Ъ p(g(x),z) ) } ,
където a е константа, а f и g са едноместни функционални символи. Чрез метода на Ербран заключаваме, че въпросната изпълнимост е равносилна с изпълнимост на множеството на всички формули от видовете  Ш p(Y,a) & p(a,f(Y)) & p(Y,f(Y))  и  Ш p(g(X),X) Ъ p(X,Z) Ъ p(g(X),Z),  където X, Y и Z са затворени термове, или, все едно, на множеството на всички формули от видовете  Ш p(Y,a),  p(a,f(Y)),  p(Y,f(Y))  и  Ш p(g(X),X) Ъ p(X,Z) Ъ p(g(X),Z),  където X, Y и Z са затворени термове. Въпроса за изпълнимостта на последното множество ще решим с помощта на метода на резолюцията. А именно, за да бъде то изпълнимо, необходимо и достатъчно е чрез никакъв брой прилагания на резолюция празният дизюнкт да не може да се получи от дизюнкти от видовете  { Ш p(Y,a) },  { p(a,f(Y)) },  { p(Y,f(Y)) }  и  { Ш p(g(X),X),  p(X,Z),  p(g(X),Z), }  където X, Y и Z са затворени термове. Нека M е множеството на всички дизюнкти от изброените четири вида. Очевидно за всеки два затворени терма Y и Yў имаме неравенствата  p(a,f(Y)) № p(Yў,a)  и  p(Y,f(Y)) № p(Yў,a). Също така за всеки два затворени терма X и Y имаме неравенствата p(a,f(Y)) № p(g(X),X)  и  p(Y,f(Y)) № p(g(X),X)  - първото от тях е очевидно, а второто е ясно от това, че в лявата му страна първият аргумент има по-малка дължина от втория, докато в дясната положението е обратното. Като се използват тези неравенства, може да се покаже, че всеки дизюнкт, получен от дизюнкти от M чрез някакъв брой прилагания на резолюция, има някой от първите три вида или притежава елемент от вида  Ш p(g(X),X),  където X е затворен терм. Действително, нека два дизюнкта имат резолвента D и всеки от тях има току-що формулираното свойство. Тогава поради първите две от неравенствата поне един от тях ще трябва да притежава елемент от вида  Ш p(g(X),X),  където X е затворен терм. Ако всеки от двата притежава такъв елемент, поне един от техните елементи от споменатия вид ще принадлежи и на D. Ако пък само единият от двата дизюнкта притежава елемент от въпросния вид, този елемент ще принадлежи на D поради другите две неравенства. Значи при всяко положение резолвентата D притежава елемент от вида  Ш p(g(X),X),  където X е затворен терм. От доказаното е ясно, че празният дизюнкт не може да бъде получен от дизюнкти от M чрез никакъв брой прилагания на резолюция и следователно множеството {j ,y} е изпълнимо. По подобен начин бихме могли да покажем, че и множеството {Шj,Шy} е изпълнимо. Може обаче да се спести повечето от нужния за това труд, като се използва по подходящ начин вече установената изпълнимост на множесtвото {j ,y}. А именно достатъчно е да забележим, че отрицанието на формулата j е еквивалентно на формулата, получаваща се от y чрез поставяне на отрицание навсякъде пред предикатния символ p, а пък отрицанието на y е еквивалентно на формулата, получаваща се по аналогичен начин от j. Благодарение на това можем да получим структура, която е модел за множеството {Шj,Шy}, по следния начин: вземаме кой да е модел за множеството {j,y} и в този модел променяме интерпретацията на предикатния символ p така, че стойността на новия предикат да бъде 1 точно в онези точки от дефиниционната му област, в които стойността на стария е 0.

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