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

UptoLike

ВУЗ: 

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

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

Рубрика: 

Математическая Логика и Теория Алгоритмов стр. 21 из 64
© 2003 Галуев Геннадий Анатольевич
(индивидные) переменные X
1
,...,X
n
,..., предметные (индивидные) константы а
1
,…,а
n
,…,
функциональные буквы
k
n
1
1
f,...,f , а также указанные выше кванторы ∀ и ∃.
Предикатные
k
n
1
1
A,...,A и функциональные
k
n
1
1
f,...,f буквы могут иметь аргументы,
которые в этом случае указываются справа от них в скобках (
)X(A ,)X(f
1
1
2
2
). Аргумен-
ты отделяются друг от друга запятой (
)Y,X(A
2
1
). Количество аргументов определяет
верхний индекс
)X,X,X,X(A ,)Z,Y,X(f
4321
4
2
3
1
, а нижний индекс используется для инди-
видуализации предикатных и функциональных букв.
Из функциональных букв (
k
n
f ), предметных переменных (X
1
,...,X
n
) и констант
(а
1
,…,а
n
) могут быть построены термы. Дадим индуктивное определение терма.
a) Всякая предметная переменная (X
i
) или константа (а
i
) есть терм.
b) Если
k
n
f функциональная буква и t
1
,...,t
k
– термы, то )t,...,t(f
k1
k
n
тоже есть
терм.
c) Выражение является термом тогда и только тогда, когда это следует из a) и
b).
Из предикатных букв и термов можно получать элементарные формулы. Так если
k
n
A предикатная буква, t
1
,...,t
k
термы, то )t,...,t(A
k1
k
n
- элементарная формула.
Формулы исчисления предикатов определяются так:
a) Всякая элементарная формула есть формула.
b) Если А и В формулы и y – предметная переменная, то каждое из выраже-
ний (⎤А), (А→В), (∀yA), (∃yB) – есть формулы.
c) Выражение является формулой лишь тогда, когда оно получено в соответ-
ствии с a) и b).
В выражениях
(∀yA) и (∃yА) формула А называется областью действия соответст-
венно кванторов ∀y и ∃y.
Будем придерживаться введённого в исчислении высказываний соглашения о
более экономном употреблении скобок. Будем считать, что кванторы ∀y и ∃y распола-
гаются между связками
∨
¬
,&,
и связками
↔
→,
(т.е.
↔
∃
→
¬
∀ ,&
и т.д.)
Вместо выражения
(
)
(
)
(
)
(
)
21
2
21
1
11
, xxAxAx →∀ можно использовать запись
() ( )
21
2
21
1
11
, xxAxAx →∀ , т.е. можно убрать внешние скобки. При восстановлении скобок
связки анализируются последовательно в порядке
↔
→
∃
∀
∨
¬
,,,,,&, , и область дейст-
вия из этих операторов вместе с ним заключается в скобки. Для операторов
∃
∀
¬
,,
область действия располагается справа от оператора и либо выделяется скобками,
либо нет, если это наименьшая формула с учетом уже расставленных скобок. Для
операторов
,,,&, ↔→∨ области действия располагаются с обеих сторон от каждого из
них и заключается в скобки аналогичным образом.
Рассмотрим на примере процесс восстановления скобок для правильного чтения
и анализа формул.
Пусть задано выражение:
x∀ y⎤∀ z∀
()
(
)
(
)
(
)()
yDyxyBxyxCyxBzyxA
↔
∃
→∨ ,,&,,,
Восстановим скобки:
1.
()
()
()
(
)
(
)
(
)
yDyxByxyxCyxBzyxAzyx ↔∃∀→∨∀⎤∀∀ ,,&,,,
2.
()
()
()
(
)()
(
)
(
)
yDyxByxyxCyxBzyxAzyx ↔∃∀→∨∀⎤∀∀ ,,&,,,
3.
()
()
()
(
)()
()
(
)
(
)
yDyxByxyxCyxBzyxAzyx ↔∃∀→∨∀⎤∀∀ ,,&,,,
4.
()()()
()()
()
(
)()
()
(
)
(
)()
yDyxByxyxCyxBzyxAzyx ↔∃∀→∨∀∀⎤∀ ,,&,,,
5.
()()()
()()
()
(
)()
()
(
)
(
)
(
)()
yDyxByxyxCyxBzyxAzyx ↔∃∀→∨∀∀⎤∀ ,,&,,,
6.
()()()
()()
()
(
)()
()
(
)
(
)
(
)
()
()
yDyxByxyxCyxBzyxAzyx ↔∃∀→∨∀∀⎤∀ ,,&,,,
7.
(
)()()
()()
(
)
(
)
(
)
()
()
(
)
(
)
()
(
)
()
yDyxByxyxCyxBzyxAzyx ↔∃∀→∨∀∀⎤∀ ,,&,,,

Страницы