Съдържание 
 

ПРОМЕНЛИВИ НА ФОРМУЛА

      За всяка формула φ ще дефинираме две множества от променливи  –  множество на свободните променливи на φ и множество на свързаните променливи на φ. Тези две множества ще означаваме съответно с FVAR(φ) и BVAR(φ), а елементите им разбира се ще наричаме съответно свободни променливи на φ (free variables of φ на английски) и свързани променливи на φ (bound variables of φ на английски). Дефиницията на тези две множества е индуктивна и нейната коректност се основава на еднозначния прочит на формулите. За всяка атомарна формула φ дефинираме въпросните множества, като следва: ако  φ = π(τ1,…,τm),  където m е положително цяло число, π e m-местен предикатен символ и τ1, …, τm са термове, то под FVAR(φ) разбираме обединението на множествата на променливите на термовете τ1, …, τm, а ако φ е нулместен предикатен символ, то приемаме, че FVAR(φ) е празното множество; и в двата случая приемаме, че BVAR(φ) е празното множество. След това разпространяваме така дадената дефиниция за произволни формули с помощта на равенствата
FVAR(¬φ) = FVAR(φ),  BVAR(¬φ) = BVAR(φ),
FVAR(φ&ψ) = FVAR(φ∨ψ) = FVAR(φ) ∪ FVAR(ψ),  BVAR(φ&ψ) = BVAR(φ∨ψ) = BVAR(φ) ∪ BVAR(ψ),
FVAR(∀ξφ) = FVAR(∃ξφ) = FVAR(φ) \ {ξ},  BVAR(∀ξφ) = BVAR(∃ξφ) = BVAR(φ) ∪ {ξ}.
Под множество на променливите на една формула ще разбираме обединението на множеството на нейните свободни променливи и множеството на нейните свързани променливи. Множеството на променливите на формулата φ ще означаваме с VAR(φ).

      Пример 1. Ще намерим кои са така дефинираните множества за всяка от формулите (1 – 11) в пример 2 от текста „Формули на предикатното смятане“. Всяка от формулите (1 – 5) и формулата (10) е с множество на свободните променливи {x}. Всяка от формулите (6), (7) и (9) е с празно множество на свободните променливи, а формулите (8) и (11) имат множество на свободните променливи {x,y}. Множеството на свързаните променливи е празно при всяка от първите пет формули, при всяка от двете формули (6) и (7) то е {x}, а при формулите (8), (9), (10) и (11)  –  съответно {z}, {x,y,z}, {y} и {x,y}. За всяка от тези формули с изключение на последните четири множеството на променливите е едноелементното множество с единствен елемент x. Множеството на променливите на всяка от формулите (8) и (9) е триелементното множество {x,y,z}, а множеството на променливите на всяка от формулите (10) и (11)  –  двуелементното множество {x,y}. Забелязваме, че x е и свободна, и свързана променлива на формулата (11), но за всяка от останалите десет формули множеството на свободните променливи и множеството на свързаните са без общи елементи.

      Забележка. От дефиницията е ясно, че ако една променлива ξ е свободна променлива на дадена формула φ, то множеството на свободните променливи на всяка от формулите ∀ξφ и ∃ξφ е същинско подмножество на множеството на свободните променливи на φ, а ако променливата ξ не е свободна променлива на φ, то споменатите три множества съвпадат (например формулата (8), за която стана дума по-горе, има същото множество {x} на свободните променливи както формулата, на която тя е генерализация относно y).

      Чрез индукция, съобразена с дефиницията на понятието формула, лесно се показва, че за всяка формула φ множествата FVAR(φ) и BVAR(φ) са крайни. За дадена формула казваме, че е затворена, когато множеството на нейните свободни променливи е празно, и че е отворена, когато множеството на свързаните й променливи е празно.

      Пример 2. Измежду единадесетте формули, за които стана дума в пример 1, затворени са формулите (6), (7) и (9), а отворени  –  формулите (1), (2), (3), (4) и (5).

      От дадените дефиниции следва, че отрицанието на една формула е затворено точно тогава, когато самата формула е затворена, и че формула, която е конюнкция или дизюнкция на две формули, е затворена точно тогава, когато тези две формули са затворени. Следват и аналогични твърдения, отнасящи се за отвореност на формули, както и твърдението, че всяка атомарна формула е отворена. Разбира се формула, която е получена по последната точка от дефиницията на понятието формула, не може да бъде отворена, но би могла да бъде или да не бъде затворена.

      Понятието отворена формула е еквивалентно на понятието безкванторна формула, дефинирано посредством следната индуктивна дефиниция:
        1. Всяка атомарна формула е безкванторна формула.
        2. Отрицанието на всяка безкванторна формула е пак безкванторна формула.
        3. Конюнкцията и дизюнкцията на две безкванторни формули са също безкванторни формули.

      И наистина, индукция, съобразена с горната дефиниция, веднага показва, че всяка безкванторна формула е отворена. Обратното пък може да се установи, като чрез индукция, съобразена с дефиницията на понятието формула, се докаже, че всяка формула има поне една свързана променлива или е безкванторна (следователно формулите, които нямат свързани променливи, непременно са безкванторни).

      Ако φ е формула, чиито свободни променливи са дадени n различни променливи ξ1, …, ξn, то затворените формули  ∀ξ1…∀ξnφ  и  ∃ξ1…∃ξnφ  се наричат съответно универсално затваряне на φ и екзистенциално затваряне на φ  (при n>1 те не са еднозначно определени, понеже съществуват  n!  различни възможности за подреждане на ξ1, …, ξn).

      Лемата за базисна роля на променливите на един терм има следния аналог за формули.

      Лема за базисна роля на свободните променливи на една формула. Ако две оценки в дадена структура S съвпадат върху множеството на свободните променливи на дадена формула φ, то стойностите на φ в S при тези две оценки са равни. В частност, ако φ е затворена, то стойността на φ в S при всяка оценка в S е една и съща.

      Доказателство. Разбира се достатъчно е да се докаже първото от горните две твърдения. Доказателството му се извършва чрез индукция, съобразена с дефиницията на понятието формула. За атомарни формули верността на това твърдение вече е установена, защото за тях множеството на свободните променливи съвпада с множеството на променливите. Индуктивните стъпки за случаите на отрицание, конюнкция и дизюнкция са прости. Например, ако една формула θ е конюнкция на две други, за които твърдението на лемата е в сила, а дадени оценки v и w в S съвпадат върху множеството FVAR(θ), те ще съвпадат и върху множеството на свободните променливи на всяка от въпросните други две формули (понеже то се съдържа във FVAR(θ)), следователно всяка от тях ще има в S равни стойности при оценките v и w, а оттук се вижда, че и формулата θ ще има равни стойности в S при оценките v и w. Малко повече труд изискват случаите на генерализация и на екзистенциализация. Нека например θ е формулата ∀ξφ за някоя променлива ξ и за някоя формула φ, за която твърдението на теоремата е в сила. Да предположим, че дадени оценки v и w в S съвпадат върху множеството на свободните променливи на θ. Тогава, означавайки с D носителя на структурата S, можем да твърдим, че при всеки избор на елемент d на D оценките v[ξ→d] и w[ξ→d] ще съвпадат върху множеството на свободните променливи на φ (за произволна измежду тези променливи разглеждаме поотделно случая, когато тя е различна от ξ, и случая, когато тя е ξ). Оттук получаваме, че

θS,v = min{φS,v[ξ→d] | d∈D} = min{φS,w[ξ→d] | d∈D} = θS,w.
Съвсем аналогично се разглежда и случаят на екзистенциализация.  □

      Ако φ е произволна затворена формула, то независещото от избора на оценката v в S число φS,v ще наричаме стойност на φ в S и ще го означаваме с φS. В случай, че φ е затворена формула и имаме равенството φS = 1, казваме, че φ е вярна в S.

      Пример 3. Нека структурата S е както в пример 3 от текста „Сигнатури и структури“. Затворените формули (6) и (9) от пример 2 в текста „Формули на предикатното смятане“ са верни в S, а затворената формула (7) от същия пример не е вярна в S.

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