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) ).

    В следващите задачи нека ϕ и ψ са съответно формулите
            ∃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. Покажете, че никоя от формулите ϕ и ψ не е тъждествено вярна.

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

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

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

    Решение на задача 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. Това, че формулата ϕ не е тъждествено вярна, се вижда например от факта, че тя не е вярна в структурите с носител от един елемент. И наистина, в такава структура има само една оценка на променливите и поставянето на квантори не влияе върху стойността на формулите при тази оценка. Значи ако S е структура с едноелементен носител, то стойността на ϕ в S съвпада със стойността, която има в S при единствената оценка на променливите следната формула (получена от ϕ чрез пропускане на кванторите):

¬ p(y,x) & ( p(x,z) & p(y,z) ) .
Очевидно е обаче, че въпросната стойност е винаги 0. Твърдението, отнасящо се за формулата ψ, ще докажем, като покажем с помощта на изучени общи методи, че формулата ¬ψ е изпълнима (начинът, по който постъпихме в случая на ϕ, сега не би ни помогнал – вижда се, че ψ е вярна в структурите с едноелементен носител). Първо привеждаме ¬ψ в пренексен вид и виждаме, че е еквивалентна на формулата
∃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. Въпросът дали от ϕ следва ψ има същия отговор както въпроса дали е неизпълнимо множеството {ϕ,¬ψ}. Като представим елементите на това множество в пренексен вид, виждаме, че изпълнимостта на множеството е равносилна с изпълнимост на множеството

{ ∃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)) ) ,  ∀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 е затворен терм. Изпълнимостта на последното множество е ясна от следствието от основната лема за озъществимост. С това е показано, че от формулата ϕ не следва формулата ψ. Отговорът на другия въпрос – дали от ψ следва ϕ – също е отрицателен. Това се вижда много по-лесно, а именно достатъчно е да забележим, че в структурите с едноелементен носител формулата ψ е вярна, а формулата ϕ не е вярна (вж. решението на задача 2).

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

{ ∃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 чрез никакъв брой прилагания на резолюция и следователно множеството {ϕ ,ψ} е изпълнимо. По подобен начин бихме могли да покажем, че и множеството {¬ϕ,¬ψ} е изпълнимо. Може обаче да се спести повечето от нужния за това труд, като се използва по подходящ начин вече установената изпълнимост на множесtвото {ϕ ,ψ}. А именно достатъчно е да забележим, че отрицанието на формулата ϕ е еквивалентно на формулата, получаваща се от ψ чрез поставяне на отрицание навсякъде пред предикатния символ p, а пък отрицанието на ψ е еквивалентно на формулата, получаваща се по аналогичен начин от ϕ. Благодарение на това можем да получим структура, която е модел за множеството {¬ϕ,¬ψ}, по следния начин: вземаме кой да е модел за множеството {ϕ,ψ} и в този модел променяме интерпретацията на предикатния символ p така, че стойността на новия предикат да бъде 1 точно в онези точки от дефиниционната му област, в които стойността на стария е 0.

Последно изменение на съдържанието: 29.07.2002 г. На 23.04.2020 г. елиминирано използването на шрифт Symbol, а препратките в текста към HTML файлове заменени с препратки към PDF файлове.