ВУЗ:
Составители:
авваавва →
′
→
все слова, кроме слов авва и а′в′в′а′, являются регулярными.
Теорема 1.1. Всякая формула системы П является формулой системы
N.
Доказательство. Очевидно, что теорема справедлива для аксиомы С,
так как она сопряжена с
С . Поскольку все формулы выводятся из аксиомы С,
достаточно показать, что свойство «быть формулой» системы N сохраняется
при применении подстановок системы П.
Предположим, что формула Х системы П является формулой в системе
N. Для того, чтобы Х имела следствие в системе П, необходимо, чтобы Х
могла быть представлена в виде
QPAX
i
=
. Тогда в соответствии со схемой
подстановок в системе П из Х непосредственно следует
QPBY
i
= . На основе
подстановок типа 1) системы N из Х может быть получено слово
PQA
i
′
,
которое является формулой в системе N, так как оно сопряжено с Х.
Применяя к
ii
QPA подходящую подстановку типа 3) системы N, мы можем
получить слово
i
BPQ
′′
, которое также является формулой в системе N. Слово
i
BPQ
′′
сопряжено со словом Y. Действительно, →
′′
→
′
′
′
→
′
′
PQBQBPBPQ
iii
QPBPBQ
ii
→
′
→ . Поэтому слово Y также является формулой системы N, что
доказывает теорему 1.1.
Теорема 1.2.. Всякая формула в системе N является регулярным
словом, сопряженным с некоторой формулой системы П.
Доказательство. Теорема справедлива для аксиомы
С , поскольку
является регулярным словом в силу способа построения слова, сопряженного
с аксиомой С. Поэтому достаточно доказать, что свойства регулярности и
сопряженности с некоторой формулой системы П сохраняются при
использовании системы N. Сохранение указанных свойств очевидно для
подстановок 1) и 2). Рассмотрим подстановки типа 3). Предположим, что
формула А
i
Р регулярна и сопряжена с некоторой формулой системы П. Из
регулярности А
i
Р следует, что она может быть записана в виде
21
PPА
i
′
, где Р
1
и Р
2
- некоторые слова в алфавите А. ***** сопряженное с А
i
Р слово в
Страницы
- « первая
- ‹ предыдущая
- …
- 17
- 18
- 19
- 20
- 21
- …
- следующая ›
- последняя »
