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

UptoLike

ВУЗ: 

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

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

Рубрика: 

Математическая Логика и Теория Алгоритмов стр. 47 из 64
© 2003 Галуев Геннадий Анатольевич
все слова, кроме слов abba и a'b'b'a', являются регулярными.
Т
Т
е
е
о
о
р
р
е
е
м
м
а
а
.
. Всякая формула системы П является формулой из системы N.
Доказательство.
Очевидно, что теорема справедлива для аксиомы С , так как она спряжена с
C .
Поскольку все формулы выводятся из аксиомы С, достаточно показать, что свойство
''быть формулой системы N'' сохраняется при применении подстановок системы П.
Предположим, что формула X системы П является формулой в системе N. Для
того, чтобы формула Х имела следствие в системе П, необходимо, чтобы Х могла быть
представлена в виде
QPAX
i
=
. Тогда в соответствии со схемой подстановок в системе
П из Х непосредственно следует
QPBY
i
= . На основе подстановок типа 1) системы N
из Х может быть получено слово
PQA
i
′
, которое является формулой в системе N, так
как оно сопряженное с Х.
Применяя к
ii
QPA подходящую подстановку типа 3), системы N, мы можем по-
лучить слово
i
QPB , которое также является формулой в системе N. Слово ''
i
BQP со-
пряжено со словом Y . Действительно,
QPBPBQPQBQBPBpQ
iiiii
⎯→⎯
′
⎯→⎯
′′
⎯→⎯
′′′
⎯→⎯
′
2221
.
Поэтому слово Y, также является формулой системы N, что доказывает теорему.
Т
Т
е
е
о
о
р
р
е
е
м
м
а
а
.
. Всякая формула в системе N является регулярным словом, со-
пряженным с некоторой формулой системы П.
Доказательство.
Теорема справедлива для аксиомы
C
, поскольку она является регулярным
словом в силу способа построения слова, сопряженного с аксиомой С. поэтому доста-
точно доказать, что свойства регулярности и сопряженности с некоторой формулой
системы П сохраняются при использовании системы N. Сохранение указанных
свойств очевидно для подстановок 1) и 2). Рассмотрим подстановки типа 3). Предпо-
ложим, что формула
PA
i
регулярна и сопряжена с некоторой формулой системы П.
Из регулярности
PA
i
следует, что она может быть записана в виде
'
21
PPA
i
, где
1
P и
2
P
-некоторые слова в алфавите А. Единственное спряженное с
PA
i
слово в системе П
это слово
12
PAP
i
. Из сделанного предположения следует, что слово
12
PAP
i
является
формулой в системе П. Однако слово
12
PAP
i
сопряжено со словом ''
21 i
BPP , которое мо-
жет быть получено с помощью подстановки 3)(
'
ii
PBPA → ) из слова
'
21
PPA
i
. Очевидно,
что слово
''
21 i
BPP является регулярным. Следовательно, теорема доказана.
Таким образом, сформулированные теоремы показывают, что для любой полу-
туэвской системы можно построить нормальную систему, в классах эквивалентности
которых содержатся все формулы исходной полутуэвской системы. Легко показать,
что можно установить соответствия между полутуэвской и туэвской, нормальной и по-
стовской, а следовательно между туэвской и постовской
системами.
Отсюда видно, что множество всех выводимых слов А* в некоторой комбинаторной
системе(туэвской, постовской и т. д.) порождает ассоциативное исчисление в алфави-
те А, а ее подстановки задают так называемый алфавитный оператор ϕ, отображаю-
щий слова из А* в слова из А*. Этот алфавитный оператор еще не является алгорит
-
мом так как в ассоциативном исчислении не определен порядок применения подста-
новок: нормальные алгоритмы Маркова, вычислимые функции машины Тьюринга, то
есть способы, дающие уточненное (а не интуитивное ) понятие алгоритма. Рассмот-
рим их более подробно.
Нормальные алгоритмы Маркова.
Пусть задана полутуэвская система с алфавитом А={a,b,c} и системой подста-
новок вида: сb→a; ab→b; cba→cca; cca→baa; baa→cba. Порядок их применения сле-

Страницы