ПРЕНЕКСНИ ФОРМУЛИ
За една формула казваме, че е пренексна (или че има пренексен вид), ако тя може да се получи от някоя безкванторна формула чрез някакъв (евентуално нулев) брой прилагания на действието поставяне на квантор пред дадена формула по свободна променлива на формулата. Това описание може да се оформи като индуктивна дефиниция със следните две точки:
1. Всяка безкванторна формула е пренексна.
2. Всеки път, когато φ е пренексна формула, а η е нейна свободна променлива, формулите ∀η φ и ∃η φ също са пренексни.
Ясно е, че за да бъде една формула пренексна, необходимо и достатъчно е тя да има вида
Κ1…Κnθ ,
където θ е безкванторна формула, n е неотрицателно цяло число и Κ1, …, Κn са квантори по различни помежду си променливи на θ. При това, когато една формула φ е пренексна, нейното представяне в споменатия вид е единствено. Безкванторната формула θ се нарича безкванторна част (или матрица) на формулата φ, а променливите, по които са кванторите Κ1, …, Κn – свързани променливи на φ. Очевидно свободни променливи на формулата φ са точно онези измежду променливите на θ, които не са свързани променливи на φ (следователно φ е затворена точно тогава, когато всички променливи на θ са свързани променливи на φ). Ясно е също, че една пренексна формула не притежава свързани променливи точно тогава, когато е безкванторна. Ако всичките Κ1, …, Κn са квантори за общност, формулата φ се нарича универсална, а ако всички те са квантори за съществуване, φ се нарича екзистенциална.
Пример. Нека ξ и η са две различни променливи и нека θ е безкванторна формула с множество на променливите {ξ,η}. Тогава пренексните формули с безкванторна част
θ са точно следните тринадесет:
θ ,
∀ξ θ ,
∀η θ ,
∃ξ θ ,
∃η θ ,
∀ξ ∀η θ ,
∀ξ ∃η θ ,
∀η ∀ξ θ ,
∀η ∃ξ θ ,
∃ξ ∀η θ ,
∃ξ ∃η θ ,
∃η ∀ξ θ ,
∃η ∃ξ θ .
Забележка 1. Две различни пренексни формули с една и съща безкванторна част могат да се окажат еквивалентни. Например ∀ξ ∀η θ
≡ ∀η ∀ξ θ и ∃ξ
∃η θ
≡
∃η ∃ξ θ в условията на горния пример.
Забележка 2. Понятието пренексна формула често се дефинира без да се поставя изискването да се поставят квантори само по свободни променливи (тогава разбира се всяка безкванторна формула ще бъде безкванторна част на безбройно много различни пренексни формули). При дефиницията, която възприехме тук и която съдържа това изискване, ако поставим пред една формула φ квантор по някоя променлива, която не е свободна променлива на φ, то получената формула не ще бъде пренексна. Например в условията на горния пример формулата ∀ξ ∃ξ θ няма да бъде пренексна. Тя обаче ще бъде еквивалентна на пренексната формула ∃ξ θ и като нея ще бъде с единствена свободна променлива η.
Последно изменение: 7.09.2008 г.