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

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

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

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

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

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

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

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