markov_teorija_algorifmov (522344), страница 21
Текст из файла (страница 21)
Имеем, как легко видеть, 8.5. Х(Я, Л, Т) ХВТ. $24. Системы слов 1, В этом параграфе мы будем имегь дело с алфавитом А и двумя различными буквами ««и у, не входящими в А. Под «словами» будем понимать слова в алфавите А, если не оговорено иное; под «вхождениями» вЂ” ««-вхождения в алфавите А. Слова в алфавите Ау, начинающиеся буквой у и оканчивающиеся этой буквой, мы будем называть у-системами в алфавите А или, короче,— системами. Буквы Р, Я, Р, В будут применяться как вербальные переменные в алфавите А; буквы Х, )', 2 — как вербальные переменные в алфавите Ау.
Следующие высказывания очевидны: 1.1. Если Х вЂ” система, то ХРу и уРХ суть систел«ы. 1.2. Если Х вЂ” система, то всякий конец Х, начинающийся буквой у, есть система и всякое начало Х, оканчивающееся буквой у, есть система. 1.3. Вербальный предикат в алфавите Ау «Х — система» разрешим. Легко доказывается высказывание 1.4. Одноместный вербальный предикат в алфавите Ау со свободной переменнои 1' «существуют система Х и слово Р в алфавите А такие, что 1' ь Хрр разрешим, Докажем высказывание 1.5.
Всякая система, отличная от у, представима как уРХ, где Р— слово в алфавите А, Х вЂ” система. Пусть У' — система и )' ау. Покажем, что У можно представить в виде уРХ. По определению у есть начало системы )', и потому 1 ь у (у., )') [к 18 8 4] где (У 1') 1гЛ, так как )'~Су [(1)], Поэтому (у )') имеет последнюю букву [2 17.4.3]. Ввиду (1) она является также последней буквой системы У, т. е. буквой у. Таким образом, у входит в (у — у'), и потому существует первое вхождение $»«1 СИСТЕМЫ СЛОВ 107 буквы у в слово (у У) [8 23.6.3].
Это вхождение имеет вид (2) Р««уж (»', где Р и 1« — слова в алфавите Ау. Ввиду того, что вхож- дение (2) является первым вхождением у в (у )л), у не входит в Р [4 23.7,10]. Таким образом, Р есть слово в ал- фавите А, Ввиду того, что (2) есть вхождение в (у -)'), имеем (3) (у 1') х РуУ7, и потому 1 д у у(Р [(1), (3)] ХТРХ, где Х т(ч". Будучи концом системы )', начинающимся буквой у [(3)], Х есть система [1.2], что и оставалось доказать. Докажем следующую теорему: 1.8. Пусть Р— одноместный вербальный предикат в алфавите Ау.
Пусть у удовлетворяет Р, и пусть соблюдается следующее условие: «каковы бы ни были система Х и слово Р в алфавите А, имеет место импликация если Х удовлетворяет Р, то уРХ удовлетворяет Р». Тогда всякая система удовлетворяет Р. Пусть 6 означает следующий одноместный арифметический предикат со свободной натуральной переменной 51: «всякая система, длина которой не превышает У, удовлетворяет Р». Число Л удовлетворяет 6, так как не существует систем длины, ие превышающей Л 11.51.
Пусть натуральное число Ж удовлетворяет 6. Покажем, что Ж[ тоже удовлетворяет 6. Пусть Х вЂ” система и [Хг(Ж[, Покажем, что Х удовлетворяет Р. Если Х ь у, то Х удовлетворяет Р по условию теоремы. Пусть Хд':у. Тогда существуют слово Р в алфавите А и система )л такие, что (4) Х ь уРУ [1.5]. Ввиду (4) [1 г < [Хг Ц 19.1.2], и потому [у'г(У. Так как Ф удовлетворяет предикату 6„ 1' удовлетворяет Р. Поэтому .
по условию теоремы и ввиду (4) Х также удовлетворяет Р. Это мы доказали для всякой системы Х, длина которой не превышает Ф[. Следовательно, А1[ удовлетворяет предикату 6. Итак, каково бы ни было натуральное число й(, имеет место импликация «если А' удовлетворяет 6, то Ж( удовлетворяет 6». Таким образом, всякое натуральное число удовлет- !ов СЕМИОТИКА сгл.
и воряет 6. Отсюда легко следует, что всякая система удовлетворяет предикату Р, что и требовалось доказать. С помощью теоремы 1.6 легко доказывается высказывание 1.7. Всякая система, отличная от у, представляется ввиде Хру, где Х вЂ” система, а Р— слово в алфавите А. После этого аналогично 1.6 может быть доказана теорема 1.8. Пусть Р— одноместный вербальный предикат в алфавите Ау.
Пусть у удовлетворяет Р, и пусть соблюдается следующее условие: «каковы бы ни были система Х и слово Р в алфавите А, имеет место импликация если Х удовлетворяет Р, то Хру удовлетворяет Рм Тогда всякая система удовлетворяет Р. 2. Будем называть атомами слова вида уру, где Р— слово в алфавите А. Будем называть элементами вхождения атомов в системы.
Будем называть элементами системы Х вхождения атомов в систему Х. Верно высказывание 2.1. Всякий элемент являетсявхождением однозначно определенного атома в однозначно определенную систему (з 23.5.! 1. Докажем следующую теорему: 2.2. Всякий элемент системы уРХ, где Р— словов алфавите А, а Х вЂ” система, имеет один из видов: а) журуев(у Х); б) ур йг, где У' — эле,чент системы Х. Пусть 1' — элемент системы уРХ, т. е.
вхождение в уРХ некоторого атома у«1у, где Я вЂ” слово в алфавите А. Обозначая крылья этого вхождения буквами У и Я, имеем (') У к1 жуЯуж2 (2) Уу дуг Х урх. Так как у — начало системы Х, имеем (3) Х~у(у-х). Рассмотрим два возможных случая: случай 1), когда УмЛ, и случай 2), когда У 1~Л. В случае 1) имеем (4) ЯуЯХРу(у — Х) [(2), ~ 17.5.2, (3)], где Р и Я вЂ” слова в алфавите А, не содержащем буквы у. Поэтому (5) (е льр системы слов Поэтому (16) (р (у У)) уд угу Х [(8), (й), 2 17.5.2].
Полагая (11) йу=(р-(у-У)) КТЯу*2, мы видим, что яу есть вхождение атома уеду в систему Х [(10), (11)] и, следовательно, элемент системы Х. Вместе с тем 1 ~ у (у - У) ж уду*2 [(1) (7И хур(р-(у- У))жудужл [(й)] '«уРУР [(11)]. Таким образом, в случае 2) У имеет вид б) и доказатель- ство теоремы 2.2 завершено. Аналогично имеем 2.3. Всякий элемент системы Хру, где Х вЂ” система, а Р— слово в алфавите А, имеет один из видов: а) (у Х)шуруя«, б) УРРу, где Я7 — элемент системы Х. Докажем теорему 2.4. Всякая система, отличная от у, начинается атомом. 4У .'; Фэ«! 109 г.'- ;«! и (6) Ях(у-Х) [(4), 4 22,1.1] и, следовательно, У вЂ”,муру к(у Х) [(1), (5), (6)]- Таким образом, в случае 1) У имеет вид а).
Рассмотрим теперь случай 2). В этом случае 1' имеет началом букву у, ввиду чего (7) ! ~у(у.- !'). Имеем (8) (у У)Яу2мРХ [(2), (7), 2 !7.5,2]. ( -У)у не есть начало слова Р в алфавите А. Так как (у -1')у и Р суть начала одного и того же слова [г( )], у у г8] Р есть начало слова (у -У) Ц 18,4,6], и мы имеем (й) Р(р (у-!'))~(у !') [5 18.8.4] !1О СЕМИОТИКА Егл.
и Пусть Х вЂ” система и Х~еу. Тогда могут быть указаны слово Р в алфавите А и система 2 такие, что Х м уР7, [1. 5]. Система 2 имеет началом букву у, и потому гну(у-2) [4 !8.8.4]. Следовательно, Х Х тру (у-2), причем уРу есть атом. Теорема тем самым доказана. Аналогично доказывается высказывание 2.5, Всякая система, отличная от у, оканчивается атомом [1.7). 3. Будем называть членами системы Х слова Р (в алфавите А) такие, что атом уРу входит в Х. Будем говорить, что Р— первый член системы Х, если уРу есть начало Х; будем говорить, что Р— последний член системы Х, если тру — конец Х. Будем говорить, что система Х соединяет слово Р со словом ег, если Р— первый член Х, а Я вЂ” последний член Х.
Имеем следующие верные высказывания: 3.1. Всякая система, отличная от у, имеет единственный первый член и единственный последний член [2.4, 2.5, 4 24.1.1, $ 17.5.1, 3 17.5.2). 3.2. Первый и последний члены системы, отличной от у, суть ее члены. З.З. Если Х вЂ” система, то Р есть первый член системы уРХ и последний член системы ХРу. 3.4. Если Х вЂ” система, то всякий ее член есть член как системы уРХ, так и системы ХРу. 3.5. Если Х вЂ” система, то всякий член системы уРХ либо совпадает с Р, либо есть член системы Х [2.2, 3 23.3.2, 3 23.7.1, 3 17.5.1, $ 17.5.21. 3.6. Если Х вЂ” сисп1ема, то всякий член системы Хру либо совпадает с Р, либо есть член системы Х [2.3, 3 23.3.2, 3 23.7.1, 4 1 7.5.1, 3 1 7.5.2). Систему у естественно называть пустой: никакое слово не является ее членом.
Разумеется, следует отличать пустую систему от пустого слова. 4, Какова бы ни была система Х, имеет место неравенство [[Хтд) [*), и потому осмысленно выражение ([[Хтд — [). Число, являющееся его значением, мы будем называть объ- *) [Хт злесь означает проекцию слова Х на однобуквенныа алфавнт у. $241 СИСТЕМЫ СЛОВ 111 елзом снс1пелеы Х. Объем системы Х мы будем обозначать символом откуда (3) [[22 [[< [[Хтд Следовательно, (4) [[7тд [ ( [Хо т, е. имеем (1) [(4) (2)] докажем следующую [~ 19.4.1, ~ 19,4,3].
[(3), 4 (!), ~ !7.5,11 что и требовалось доказать теорему: [Хо Согласно определению имеем (1) .[х'х ([[х ' — [) н, следовательно, [Хо [ т [[Хтд [(1)], Здесь Х вЂ” любая система. 4.1. Если система Х отлична от у, то Л([Х' [2,4, $ 19.4.1, ~ 19.4,3]. 4.2. [у !. 5. Каждому элементу 1' припишем в качестве его номера натуральное число [[Етд[, где 2 †лев крыло 1'.
Номер элемента 1' будем обозначать символом [)'А 5.1. Нол1ер всякого элемента Х есть положительное на1ну- ральное число. Это непосредственно следует из определения номера эле- мента. 5.2. Нол1ер всякого элемента системы Х мажорируется объе- мом сисгпемы Х. Пусть У вЂ” элемент системы Х. Докажем, что (1) [у'А ~- [Хо 1' есть вхождение в Х однозначно определенного атома у у Ру, где Р— слово в алфавите А [2.!]. Обозначим буквой Я левое крыло Г.
Имеем по определению номера элемента (2) [КА о [[2тд!. Слово 2у Ру является началом системы Х Ц 23.3.8]. Поэтому [[Яу Рута([[Хтд [4 !9.4.2], 1!2 СЕМИОТИКА ~гл. и 5.3. Какоеы бы ни были система Х и натуральное число А! такое, что (5) [( ф < '[Хо может быть указан элемент У системы Х такой, что (6) [1'" л. й!. Доказательство проведем методом ограниченной арифметической индукции. Фиксируем систему Х н рассмотрим следующий одноместный арифметический предикат Р со свободной переменной М: (7) «может быть указан элемент 1' системы Х такой, что [УАХМ~». Если Хму, то ЦХтэ о! и [Х'мЛ [4(1)].
Тогда не существует натуральных чисел А1, удовлетворяющих условию (5), и тривиально верно, что для всякого такого й! может быть указан элемент У системы Х, удовлетворяющий условию (6) [2 9.3]. В дальнейшем мы будем считать, что Х ф 7. Тогда Х начинается атомом [2.4], т. е. имеется слово Р в алфавите А такое, что атом уР7 есть начало Х. Имеется слово 2 в алфавите Ау такое, что (8) Х Хуруг. Положим (9) У окуРуоиь.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
