Преименувания и замествания, дискретна математика
Ролята на свободните и обвързани променливи. Преименуване. Променлив сблъсък при преименуване. Съотношение на конгруентност (≈). Безплатна подмяна на дадения израз. Запазване на конгруентността по време на заместването. Свойството на чистота на променливите. Лема за чистотата на променливите.
Вече срещаме концепцията за обвързана променлива в хода на математическия анализ.Означението на граница, определен интеграл, дава примери за обвързването на променливи. От същия курс е известно, че свързаната променлива може да бъде променена, без да се променя значението на израза. Това общо правилно правило обаче може да доведе до неправилни резултати. Например, ако замените обвързаната променлива x с променливата y в израз, ще получите формула, която има съвсем различно значение. В този случай те казват, че по време на заместването е възникнал сблъсък на променливи. Извиква се едновременното заместване на всички появявания на променливата x в префикса на квантора * ∇x и в обхвата на този префикс с променлива y от същия вид преименуване. Променлив сблъсък при преименуване във формулата ∇xX - ситуацията, когато, когато променливата x е преименувана на променливата y в X или в една от нейните подформули, има променлива, която се превръща от свободна в свързана. Например във формулата ∀xp (x, y, z) променливите y и z са свободни. Но когато преименуваме x на y, получаваме ∀ y p (y, y, z), където само една променлива z остава свободна. Може да има и друга ситуация. Във формулата ∀ x p1 (x, (∀y p2 (x, y)), z) и двете появявания на променливата y са свързани. Променливата x влиза във формулата свързана (тъй като има квантор), но тази променлива вече влиза свободно в подформулата y p2 (x, y). Но преименуването на x на y превежда y в свързана променлива в тази подформула: ∀ y p1 (y, (∀y p2 (y, y)), z). В този случай също е възникнал променлив сблъсък. Можете да го сложите по различен начин. Ние наричаме променливата x във формулата Z безплатна променлива за променлива y, ако няма появявания на y в Z, които са свободни за Z или една от нейните подформули не попадат в обхвата на префиксите на квантора с променливата x Променливият сблъсък при преименуване е опит да се замени количествено измерима променлива x с y, докато x не е безплатна за y. Ще кажем, че две формули X и X ' конгруентна (са варианти един на друг, нотация X ≈ X '), ако единият е получен от другия с помощта на правилния, т.е. без променлива сблъсък, преименуване. Точно определение на тази концепция може да се даде чрез индукция върху конструкцията на формулата:
1) елементарна формула е конгруентна само на себе си;
2) ако Y ≈ Y 0, Z ≈ Z 0, тогава ¬Y ≈¬Y 0 и Y ∇ Z ≈ Y 0 ∇ Z 0, където ∇ е една от трите двуместни логически свързвания;
3) ако X = ∇xY, X0 = ∇y Z, тогава X ≈ X0, ако x и y са от един и същ вид, и за всяка променлива z от същия вид, която изобщо не се появява в Y или Z, имаме Y zx ≈ Zz y, където Wu v е резултат от замяна в W на всички свободни появявания на променливата v с променливата u.
Имайте предвид, че конгруентността е отношение на еквивалентност (симетрично, рефлексивно и преходно). По този начин множеството от всички формули е разделено на класове по двойки конгруентни формули. Въпреки че формално съвпадащите формули се различават, няма причина да се вземе предвид такава разлика. От математическа гледна точка преходът от понятието "формула" към по-общото понятие "клас на конгруентни формули".
Под заместването θ имаме предвид символична нотация на формата
