markov_teorija_algorifmov (522344), страница 17
Текст из файла (страница 17)
6. Рассмотрим теперь тот случай, когда наш алфавит со- стоит из буквы [. Слова в этом алфавите суть натуральные числа !в 1.1!. Будем говорить, что натуральное число М мажорируется натуральным числом й(, если М есть начало !ч'; будем гово- рить, что натуральное число М меныие натурального числа л(, если М есть собственное начало У. В дальнейшем запись М(У будет означать, что М мажорируется й(, а запись М(37 будет означать, что М меньше Л1. Следующие высказывания являются частными случаями высказываний предыдущих пунктов (буквы М, У, К, Е, О употребляются как натуральные переменные).
,гл и % свмиотикл 82 6.1. М(М. 6.2. Л(М. 6.3. Если М:Л, то М е.Л. 6.4. Если М=.,У, то М(УЬ») 6.6. М (У [ пюгда и только тогда, когда М(У или МХУ[. 6.6. Если М ' У, а У ( Ь, то М ( Ь, 6.7. Если М(У, а У(М, то М м.У, 6.8. М(У тогда и только тогда, когда М < У или МхУ. 6.9. М < У[ тогда и только тогда, когда М(У, 6.10. МУ(МЬ тогда и только тогда, когда У(Ь, 6.11. Если М < [, то Мм Л, 6,12.
Неверно, что М < М [4,17[. 6.13. Если У(М, лю неверно, что М < У [4,191. 6.!4. Если М < У, а У(Ь, то М < Ь [4.18), Следующие два высказывания касаются взаимной про- стоты слева натуральных чисел. 6.15. Если М )г.Л и У л Л, то М и У не являются взаимно простыми слева [5,4~, 6.16. Если М и У взаимно просты слева, то МхЛ или УяЛ. Очевидна лемма 6.17. Всякое начало натурального числа является натураль- ным числом, всякий конец натурального числа является нату- ральным ч»»слом.
Теперь легко доказывается 6.18. М(У или У«=М [5.6, 6Л7, 6,16[, Доказывается далее 6.19. М<У или У<М или МХУ [6.18, 6.8!. В дальнейшем мы будем также пользоваться тем фактом, что 6.20. М ='МУ !4.16!. 7. Мы будем иногда применять следующий метод индук- ции по началам слова. Чтобы доказать, что всякое начало слова Р удовлетворяет одноместному вербальному предикату Р, мы доказываем, что 1) Л удовлетворяет Р, 2) для всякого слова Х и всякой буквы 3 имеет место им- пликация ') Обрансаеи внимание читателя на то, что Л'Ь означает здесь соедине- ние слов У и /., т. е, по существу сумму иатуральяых чисел У и Ь. Относи. тельно умножения натуральных чисел си.
$ 20. НАЧАЛА И',КОНЦЫ СЛОВ 83 «если Х$ — начало Р и Х удовлетворяет Р, то Х$ удовлетворяет Г». Тогда всякое начало слова Р удовлетворяет Р. В самом деле, построим одноместным вербальный предикат 6 (1) «если Х вЂ” начало Р, то Х удовлетворяет Гм Л удовлетворяет 6, так как Л удовлетворяет Р. Пусть Х удовлетворяет 6, $ — буква. Пусть Х$ — начало Р. Тогда Х вЂ” начало Р [3.1[. Так как Х удовлетворяет 6, то Х удовлетворяет Р. А поэтому, согласно второму свойству предиката Р, слово Х$ удовлетворяет Р. К этому заключению мы пришли, предположив, что Х$ есть начало Р. Следовательно, имеет место импликация «если Х$ — начало Р, то Х$ удовлетворяет Г».
Она означает, что Х$ удовлетворяет 6. Мы пришли к этому заключению, предположив, что Х удовлетворяет 6. Следовательно, верна импликация «если Х удовлетворяет 6, то Хй удовлетворяет 6» [3 ! 3.6.2!. Здесь Х вЂ” любое слово в рассматриваемом алфавите, любая его буква. Применяя метод правой индукции по пост- роению слова, убеждаемся в том, что всякое слово (в рассмат- риваемом алфавите) удовлетворяет предикату 6. Но это и означает, что всякое начало слова Р удовлетворяет преди- кату Р [(1)[. В частном случае, когда рассматриваемый алфавит состоит из одной буквы [, метод индукции по началам слова перехо- дит в следующий метод ограниченной арифметической ин- дукции.
Чтобы доказать, что всякое натуральное число, мажори- руемое натуральным числом У, удовлетворяет одноместному арифметическому предикату Р, мы доказываем, что: 1) Л удовлетворяет Р, 2) для всякого натурального числа М имеет место импли- кация «если М[(У и М удовлетворяет Г, то М! удовлетворяет Рм Тогда всякое натуральное число, мажорируемое числом У, удовлетворяет предикату Р. [гл. и СЕМИОТИКА 84 8. Если слово Х является началом слова 2, то слово У такое, что Х)'~2, единственно Ц 17.5.2]. Это единственное слово мы будем называть концевым дополнением слова Х в слове 2 и обозначать (1) (Х -2). Согласно этому определению имеем: 8.1. Если Х вЂ” начало Я, то концевое дополнение Х в 2 есть конец 2.
8.2. Выражение (1) осмыслено тогда и только тогда, когда Х вЂ” начало 2. 8.3. (Х ХУ') 'и )'. 8.4. Если Х вЂ” начало 2, то (2) Х(Х-2) 3:2. Докажем 8.5. Если Хс — начало 2, то (3) (Х - г) х1(Х5-2). В самом деле, тогда Х вЂ” начало 2 [3.1], и мы имеем равенство (2) и аналогичное равенство (4) Х$(Х$ 2) ь 2. В силу равенств (2) и (4) имеет место равенство (3) [9 17.5,2] Легко доказываются следующие высказывания: 8.6.
(Л - 2) м.2. 8.7. (2 - 2) х Л. 8.8. Если Х вЂ” начало 2, то (Х-2) ) х(Х-2) ). 9. Если слово Х является концом слова Я, то слово 1' такое, что )'Хе 2, единственно [3 17.5.1]. Это единственное слово мы будем называть начальным дополнением слова Х в слове 2 и обозначать (5) (Х 3).
Имеем 9.1. Если Х вЂ” конец 2, то начальное дополнение Х в Я есть начало 2. 9,2. Выражение (5) осмыслено тогда и только тогда, когда Х вЂ кон 2. 9.3. (Х- УХ)ЗЕУ. 9.4. Если Х вЂ” конец У, то (Х-2) Ххг. 41В1 НАЧАЛА И КОНЦЫ СЛОВ 9.5. Если сХ вЂ” конец 2, то (Х 2)лс(Х$ '2)5. 9.6, (Л-г)Х2. 9.7. (2- 2)АУЛ. 9.8. Если Х вЂ” конец 2, то (Х - У'У) Х 'г' (Х - Я). 10. Для натуральных чисел мы введем операцию вычитания как частный случай образования концевого дополнения. Л именно, мы положим при М ( М (7ч' — М) == (М "- Ф). Имеем 10.1.
Если М( 57, то (У вЂ” М) есть натуральное число [8. 1]. 10.2. Выражение (й( — М) осмыслено тогда и только тогда, когда М ( М [8. 2]. !0.3. (МЛ( — М) х У [8,3], 10.4, Если Мг-й, пю М (й( — М) и' Ж [8.4]. 10,5. Если М)(У, то (У вЂ” М) м. ] (У вЂ” М ]) [8,5]. 10.6. (У вЂ” Л) '~ й) [8.6]. 10.7. (Л( — й)) л. Л [8.7]. 10.8. Если М(Ж, то (Л(Ь вЂ” М) лс (У вЂ” М) Е [8.8] 10.9. 5(]Х(Л [4 9.5(1)].
10.10. Если М(Ф, то М(М вЂ” М) а (М вЂ” М) М До к азат ель ство. На время этого доказательства будем говорить, что й( правильно, если для всякого М такого, что М ( Ж, имеет место равенство Требуется доказать, что всякое натуральное число правильно. Л правильно [6.3, 10.7]. Допустим, что )ч' правильно, н докажем правильность Л']. 86 СЕМИОТИКА !Тл. и Пусть М(й)). Тогда М(У или МмМ( [6.5].
Если М < й), то имеет место равенство (1), в силу которого имеем М(М( — М)~гМ(М М)] РО.8] х(ж — М) М! [(1)] х ())7 — м)! м ро.й] х (й)( м) м ро.б]. Таким образом, при М <М имеет место равенство м()у( — м) ~(л ( — м)м, Оно имеет место и при МхУ( Р0.7]. Следовательно, натуральное число У( правильно. Мы тем самым доказали (материальную) импликацию «если Ж правильно, то )т'1 правильно» [З 13.6.2].
Применяя теперь метод арифметической индукции, убеждаем- ся в истинности высказывания 10,10, Теперь докажем коммутативность сложения натураль- ных чисел. 16.11. МУйЛ7М. мии м (ми м) ро,з] х(МУ вЂ” М) М [6.20, 10,10] й й)м ро,з]. 11. Во многих случаях, особенно когда натуральные и рациональные числа будут выступать не в качестве основных объектов рассмотрения, а в качестве их числовых характе- ристик, мы будем пользоваться общепринятой арифметиче- ской символикой, употребляя знак «=» для обозначения ра- венства чисел, знаки «+» и « — » для обозначения операций сложения и вычитания и т.
п. В тех случаях, когда это не будет вызывать каких-либо коллизий, мы специальных ого- ворок делать не будем. 9 1й. Длина слова. Проекция слова на алфавит 1. Длина [Хв слова Х может быть индуктивно определена *) равенствами (1) [Лв — Л, (2) [Хфв = [Х']. Методом индукции доказываются высказывания *) См. »амечанне В $ 17.3.2 (с. 89 — 70). .
г ы) длииА словА, ПРОекция слОВА НА АЛФАВит 87 1.1. Длина всякого слова есть натуральное число. 1.2. [Х)»х[х 1 °, 1.з. [Х~т'х[х»р'[2' р.2]. 1.4. Если Х вЂ” начало У, то [Хг "[1'а Р.2]. 1.5. Если Х ф'Л, то [Ха ~ГЛ [(2)]. 1.6. [Ха»АЛ тогда и только тогда, когда Хм.л [(1), 1.5]. 1.7. Если Х вЂ” собственное нач ло У, то [Ха < Р'ь Р.2, 1.6, ~ 17.5.2].
2. Методом ограниченной арифметической индукции нетрудно доказать высказывание 2.1. Каковы бы ни были слово Х и натуральное число М, мажорируемое длиной слова Х, существует начало )' слова Х такое, что (1) р'»хм, Докажем также 2.2. Каковы бы ни были слово Х и натуральное число М, меньшее [Хл, существует собственное начало У' слова Х такое, что р'гхм.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
