ВАРИАНТИ НА БЕЗКВАНТОРНА ФОРМУЛА
Нека F е безкванторна формула. Вариант на F ще наричаме такъв частен случай
Fў
на F, че и F да бъде частен случай на Fў.
Пример. Нека p е двуместен предикатен
символ. Тогава атомарната формула p(V,W) е вариант
на атомарната формула p(U,V), а атомарната формула
p(U,U) не е вариант на p(U,V).
Очевидно всяка безкванторна формула е вариант на себе си, а една затворена безкванторна формула представлява свой единствен вариант.
Лесно се съобразява, че всеки вариант на една безкванторна формула има същите частни случаи като нея.
Следното твърдение дава един лесен начин за строене на варианти на незатворени безкванторни формули.
Твърдение 1. Нека F е безкванторна формула и нека VAR(F)={X1,X2,...,Xn}, където n е положително цяло число и променливите X1, X2, ..., Xn са две по две различни помежду си. Да положим s=[X1/Y1, X2/Y2,...,Xn/Yn], където Y1, Y2, ..., Yn са някои две по две различни помежду си n променливи. Тогава формулата Fs е вариант на F.
Доказателство. Формулата Fs е частен случай на F. За да покажем, че и F е частен случай на Fs, полагаме sў=[Y1/X1, Y2/X2,...,Yn/Xn] и виждаме, че субституцията ssў съвпада
с тъждествената субституция за всички променливи на F. Това позволява да твърдим, че
(Fs)sў=F(ssў)=Fi=F. ї
Следствие. Нека F е безкванторна
формула и нека е дадено някое крайно множество от променливи. Тогава F притежава вариант, на който никоя от променливите не принадлежи на въпросното множество.
Доказателство. Ако формулата F е затворена, твърдението е тривиално, а в противен случай използваме обстоятелството, че при предположенията и означенията на твърдение 1 е в сила равенството VAR(Fs)={Y1,Y2,...,Yn} (използваме още и това, че множеството X на всички променливи е безкрайно). ї
Ще докажем, че всеки вариант на една незатворена безкванторна формула може да бъде построен по начина, посочен в твърдение 1.
Твърдение 2. Нека F е безкванторна формула и нека VAR(F)={X1,X2,...,Xn}, където n е положително цяло число и променливите X1, X2, ..., Xn са две по две различни помежду си. Тогава всеки вариант на F може да се представи във вида F[X1/Y1, X2/Y2,...,Xn/Yn], където Y1, Y2, ..., Yn са някои две по две различни помежду си n променливи.
Доказателство. Нека Fў е произволен вариант на F. Тогава имаме равенствата Fў=Fs и F=Fўsў за някои две субституции s и sў. От тези равенства получаваме, че
Fi=F=(Fs)sў=F(ssў)
и следователно субституциите i и ssў съвпадат върху множеството на променливите на F. Значи за всяка променлива X на F имаме равенството X=(Xs)sў. Оттук е ясно, че за всяка такава променлива X термът Xs също е променлива (в противен случай не би било възможно субституцията sў да го преобразува в променлива). Да положим Yi=Xis при i=1,2,...,n. Тогава ще имаме равенствата Xi=Yisў, i=1,2,...,n, и от тях е ясно, че променливите Y1, Y2, ..., Yn са две по две различни помежду си. Тъй като субституцията [X1/Y1, X2/Y2,...,Xn/Yn] съвпада със s върху множеството VAR(F), ще имаме още, че
F[X1/Y1, X2/Y2,...,Xn/Yn]=Fs=Fў. ї
Последно изменение: 24.06.2002 г.