Свободные и связанные вхождения переменных в формулу. Область действия кванторов. Замкнутые формулы

Определение. Вхождения переменных в атомарную формулу называются свободными. Свободные вхождения переменных в формулы А и В остаются свободными в формулах .

Определение. Вхождение переменной х в формулы и называется связанным. Вхождение других переменных (отличных от х), которые были свободны в формуле А остаются свободными в формулах и . Одна и та же переменная может иметь в одной и той же формуле как свободные, так и связанные вхождения.

Определение. Формула, не содержащая свободных вхождений переменных, называется замкнутой формулой.

Пример 1. Рассмотрим формулу

В этой формуле переменные x и z имеют как связанные, так и свободные вхождения. Переменная y в этой формуле связана.

Сейчас мы посмотрим на некоторую формулу просто как на последовательность символов, составленную по определенным правилам, и запишем , где - символы, составляющие формулу . Назовем число длиной формулы . Начальным отрезком формулы длины назовем последовательность символов . Начальный отрезок не обязан быть формулой. Конечным отрезком формулы длины назовем последовательность символов . Конечный отрезок не обязан быть формулой. Наконец, подформулой формулы назовем всякую правильную формулу, которая получается из формулы удалением ее некоторого начального и некоторого конечного отрезков.

Пример 2. Пусть .

Тогда ,

- это подформулы формулы .

Определение. В формулах и подформула А называется областью действия квантора по переменной х.

Определение. Областью действия квантора, входящего в некоторую формулу, называется та подформула, к которой он относится. Возможные двусмысленности устраняются введением скобок.

Пример 3. Рассмотрим формулу

.

Область действия квантора - подформула Р (х,у). Область действия квантора - подформула . Область действия квантора - подформула .

Дата добавления: 2014-01-07