Теорема за компактност за затворени дизюнкти. Ако всяко крайно подмножество на едно множество от затворени дизюнкти е изпълнимо, то и цялото множество е изпълнимо.

      Доказателство. Нека Δ е множество от затворени дизюнкти, всяко крайно подмножество на което е изпълнимо. Дизюнктите от Δ могат да бъдат подредени в редица  -  крайна или безкрайна. Случаят, когато тази редица е крайна, е ясен, затова да предположим, че тя е безкрайна. Нека нейните членове са D₁,  D₂, D₃, …  Една крайна редица от затворени литерали (L₁,…,L_n) ще наричаме допустима, ако L_i принадлежи на D_i при i=1,…,n и никой член на тази редица не е отрицание на друг неин член. Ясно е, че всяка редица, която е начало на допустима крайна редица от литерали, също е допустима, и че всяка n-членна допустима редица от литерали има най-много краен брой n+1-членни допустими продължения. Освен това поради изпълнимостта на всяко крайно подмножество на Δ съществуват допустими редици с произволно голям брой членове. Тези свойства на множеството на допустимите редици позволяват да приложим едно твърдение (вж. накрая), известно като лема на Кьониг, и да заключим, че съществува безкрайна редица от затворени литерали, на която всяка крайна начална част е допустима. Понеже никой член на тази безкрайна редица не е отрицание на друг, съществува структура, в която всички членове на редицата са верни. В такава структура ще бъдат верни и всички дизюнкти, принадлежащи на Δ.  _□

      Следствие Всяко неизпълнимо множество от затворени дизюнкти има неизпълнимо крайно подмножество.

      Когато е дадена такава безкрайна редица (D₁,D₂,D₃,…) от затворени дизюнкти, че да разполагаме с алгоритъм за намиране на последователните нейни членове, може да се посочи алгоритъм, който в случай, че множеството на членовете й е неизпълнимо, дава нейна крайна начална част с неизпълнимо множество на членовете. Един такъв алгоритъм може да бъде описан по следния начин: последователно изброяваме всичките едночленни, всичките двучленни, всичките тричленни и т.н. допустими редици от литерали и действаме по този начин, докато евентуално намерим естествено число n, за което няма нито една n-членна допустима редица. Намерим ли такова n, можем да сме сигурни, че множеството {D₁,…,D_n} не е изпълнимо. В случай, че безкрайното множество {D₁,D₂,D₃,…} е неизпълнимо, съществуването на такова n е гарантирано от изказаното преди малко следствие.

      Лемата на Кьониг най-често се формулира в терминологията на теорията на графите, но може да се изкаже и като следното твърдение, непосредствено приложимо в ситуацията от горното доказателство: ако L е някакво множество, а A е такова множество от крайни редици от елементи на L, че а) всяка редица, която е начало на редица от A, също принадлежи на A, б) всяка n-членна редица от A има най-много краен брой n+1-членни продължения, принадлежащи на A, и в) в множеството A има редици с произволно голям брой членове, то съществува безкрайна редица от елементи на L, на която всяка крайна начална част принадлежи на множеството A. Така изказаното твърдение може да се докаже по следния начин. Нека са дадени множества L и A, удовлетворяващи предположенията на твърдението. Да се условим да наричаме обещаваща такава редица от A, която има в A продължения с произволно голям брой членове. От направените предположения е ясно, че празната редица е обещаваща, а лесно се съобразява още, че всяка n-членна обещаваща редица има поне едно n+1-членно обещаващо продължение (можем да се убедим в това чрез допускане на противното). От тези две свойства следва, че можем да изберем елемент L₁ на L, за който редицата с единствен член L₁ е обещаваща, след това да изберем елемент L₂ на L, за който двучленната редица (L₁,L₂) е обещаваща, после да изберем елемент L₃, за който тричленната редица (L₁,L₂,L₃) е обещаваща, и така нататък до безкрайност. Получаващата се по този начин безкрайна редица (L₁,L₂,L₃,…) от елементи на L има желаното свойство.
 

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

Previous  Next  Contents