Математическая логика и теория алгоритмов. Галуев Г.А. - 22 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

Составители: 

Рубрика: 

Математическая Логика и Теория Алгоритмов стр. 22 из 64
© 2003 Галуев Геннадий Анатольевич
Введение кванторов в формулу разбивает множество входящих в нее перемен-
ных на два подмножества: свободных
и связанных переменных. Определим эти поня-
тия.
Вхождение переменной X в данную формулу называется связанным, если X яв-
ляется переменной входящего в эту формулу квантора
x
∀
или
x
∃ или находится в
области действия входящего в формулу квантора; в противном случае вхождение пе-
ременной в формулу называется свободным.
Отметим, что одна и таже переменная может входить в формулу несколько раз
и в одном случае вхождение этой переменной может быть связанное а, в другом –
свободное.
Переменная называется свободной (связанной) если
в данной формуле суще-
ствуют только свободные (связанные) ее вхождения.
В рассмотренном выше примере (расстановка скобок в формуле) переменная X
имеет связанное вхождение, а переменная Y и связанное и свободное.
Понятие свободной и связанной переменных широко используется в математи-
ке. Выражение, содержащее свободную переменную, зависит от значения этой пере-
менной, а выражение, содержащее
связанную переменную, представляет результат
операции, примененной к области изменения этой переменной.
Например в выражении
∑
=
n
i
i
a
1
n – свободная переменная
i - связанная переменная
i
a - константа
Связанную переменную можно не меняя смысла и конечного результата заме-
нить на любую другую, имеющую ту же область изменения, например:
∑
=
n
j
j
a
1
.
Если в выражении подставить вместо свободной переменной какое-либо ее
конкретное значение из области ее изменения, то мы как правило получим осмыс-
ленный, конкретный результат, но эта же операция, примененная к связанной пере-
менной приводит к бессмыслице.
Например:
∑
=
4
1i
i
a
∑
=
n
i
a
1
4
Если одна и таже переменная входит в выражение и как свободная, и как свя-
занная, то представляемая этим выражением величина зависит только от значения
этой переменной в ее свободных вхождениях.
Приведенные результаты справедливы и для логических операций
xиx
∃
∀ , ко-
торые связывают соответствующие переменные (в данном случае переменную X).
Применение кванторов к формулам называется операцией квантификации или
навешивание кванторов. Нам потребуется далее операция подстановки.
Операция подстановки терма t вместо переменной X в формулу A состоит в од-
новременной замене каждого свободного вхождения X в A на вхождение t.
Если формула A зависит от X, то этот факт обычно
обозначается как A(x). Ре-
зультат подстановки t вместо X в A(x) записывается в виде A(t).
Операция подстановки, которая дает A(t) всегда должна производиться вместо
первоначальной переменной X в первоначальной формуле A(x).
Например: пусть A(x) есть
(
)
(
)
xcxSR ,, , тогда A(t) есть
()()
tctSR ,, ; а A(c)
есть
()()
cccSR ,, . Если подставить t не в первоначальную формулу A(x) а в A(c) вместо
C, то получим A(t) есть
()()
tttSR ,,
, что не совпадает с первоначальным A(t) есть
()()
tctSR ,, .

Страницы