Прилагане на субституция към литерал и към дизюнкт

ПРИЛАГАНЕ НА СУБСТИТУЦИЯ КЪМ ЛИТЕРАЛ И КЪМ ДИЗЮНКТ

За всяка субституция σ и всеки отрицателен литерал λ по следния начин дефинираме резултат λσ от прилагането на σ към λ: ако λ = not(φ), то полагаме λσ = not(φσ) (очевидно този резултат е дефиниран еднозначно и е пак отрицателен литерал).

Нека под стойност λ^S,v на един отрицателен литерал λ в дадена конфигурация (S,v) разбираме числото 1 − φ^S,v, където φ е атомарната формула с отрицание λ (тази дефиниция осигурява, че произволен литерал е верен в дадена конфигурация точно тогава, когато стойността му в тази конфигурация е 1).

Теорема за стойността на резултата от прилагане на субституция към литерал. Нека са дадени един литерал λ, една субституция σ, една структура S и една оценка v в S. Нека σ^S(v) = v′. Тогава е в сила равенството (λσ)^S,v = λ^S,v′.

Доказателство. Когато литералът λ е положителен, верността на твърдението е известна от въпроса „Оператори за присвояване, съответни на субституция“. Затова да разгледаме случая, когато този литерал е отрицателен, т.е. λ = not(φ) за някоя атомарна формула φ. Тогава

(λσ)^S,v = not(φσ)^S,v = 1−(φσ)^S,v = 1−φ^S,v′ = λ^S,v′. _□

Забележка. Под стойност λ^S на един затворен отрицателен литерал λ в дадена структура S разбираме числото 1 − φ^S, където φ е затворената атомарна формула с отрицание λ (тази дефиниция осигурява, че произволен затворен литерал е верен в дадена структура точно тогава, когато стойността му в тази структура е 1).

Нека δ е един дизюнкт, а σ е някоя субституция. Резултат от прилагането на σ към δ ще наричаме множеството от литералите, получени чрез прилагане на σ поотделно към всеки литерал от δ. Това множество е крайно (броят на елементите му не надминава броя на елементите на δ) и значи е пак един дизюнкт; ще го означаваме със δσ. Частни случаи на даден дизюнкт ще наричаме резултатите от прилагането на субституции към него.

Пример 1. Нека p е двуместен предикатен символ. Тогава дизюнктът {p(X,X)} е частен случай на дизюнкта {p(X,Y), p(Y,X)} , защото е резултат от прилагане към него на субституцията [Y/X] .

Твърдение за запазване на валидността на дизюнкт при преминаване към частен случай. Ако един дизюнкт е валиден в дадена структура, то всички негови частни случаи също са валидни в нея.

Доказателство. Нека даден дизюнкт δ е валиден в дадена структура S. Да разгледаме произволен негов частен случай. Той има вида δσ, където σ е някоя субституция. Нека v е произволна оценка в S и нека v′ е оценката σ^S(v). Благодарение на валидността на δ в S някой литерал λ от δ е верен в S при оценката v′. Като вземем пред вид равенството (λσ)^S,v = λ^S,v′, виждаме, че принадлежащият на δσ литерал λσ е верен в S при оценката v. С това показахме, че при всеки избор на оценка в S някой литерал от δσ е верен в S при тази оценка, т.е. дизюнктът δσ е валиден в S. _□

Пример 2. Нека Δ е множеството от дизюнктите {p(X,Y), p(Y,X)} и {¬p(X,Y), ¬p(Y,X)}. Ще покажем, че Δ не притежава модел. За целта да допуснем, че някоя структура S е модел за Δ, т.е. в нея е валиден всеки от двата дизюнкта, принадлежащи на Δ. Тогава обаче в S ще бъдат валидни и техните частни случаи {p(X,X)} и {¬p(X,X)}, а това не е възможно.

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