markov_teorija_algorifmov (522344), страница 15
Текст из файла (страница 15)
Значения этой операции мы зададим следующими определяющими равенствами: [Л" =Л, [Ре — Ц~Р (здесь — означает знак равенства по определению, а Р и $ — произвольное слово и произвольную букву алфавита А соответственно) 3 а м е ч а н и е.
Такого рода определения операций в математике называются рекурсивными. Первое из определяющих равенств позволяет найти обращение пустого слова. Второе <гл, и свмиотикл 10 однозначным образом сводит нахождение обращения непустого слова Р$ к нахождению обращения „предшествующего" ему слова Р, так что оба равенства в совокупности естественным образом дают нам способ, детерминированный процесс, позволяющий по любому слову Р в А получать такое слово [Р в А, что будут выполняться равенства [Л" -гЛ [~$~ ~ $[Р~ (здесь Р означает произвольное слово в А, а $ — произвольную букву этого алфавита).
Позже, когда мы в $ 26 познакомимся с понятием вербального алгорифма, мы поймем, что этот способ представляет собой некоторый вербальный алгорифм в алфавите А. Читатель, знакомый с рекурсивными функциями, увидит в нашем определении простой пример «вербальной» примитивной рекурсии. Определение, аналогичное только что приведенному, уже встречалось выше (см. 5 2.5).
В дальнейшем мы встретимся с другими рекурсивно определяемыми операциями. При этом всякий раз мы будем иметь в виду только что сделанное разьяснение. Имеют место следующие утверждения; 3.2.! . [$ Х $. 3.2.2. [Р<)" ~[д" [Р". 3.2.3. [[Р й. Р. Действительно, [В~ Х [Л$" Зг ~ [Л Х$Л хз. Тем самым 3.2.1 доказано. 3.2.2 мы докажем следующим образом: зафиксируем Р и правой индукцией по 9 покажем, что для любого <',< выполняется графическое равенство [РС7 ХЯ [Р . Действительно, оно выполняется при Я ХЛ; [РЛ" х [Р" хЛ[Р" Х [Л" [Р", «м! слова <п»одолжяние вм 7< Пусть теперь 9 — любое, и пусть выполняется указанное равенство. Тогда для любой буквы $ [РЯ" х $ [Ро" ~~Я" [Р" ~ И1" [Р" что и требовалось доказать. 3.2.3 мы также докажем, пользуясь методом правой индукции. В самом деле, при РХЛ равенство [[Р лР соблюдается: [[л"" ~ [л" ХЛ.
Пусть оно соблюдается при каком-либо Р. Тогда для любой буквы $ [[Р$""~[~ Р"" х [[Р"" [~" [3.2.2) ХРз [3,2.3, 3.2.!), что и требовалось доказать. Пусть теперь Р— какое-либо свойство слов, и пусть методом левой индукции мы доказали, что любое слово обладает этим свойством. Покажем, что зто утверждение может быть доказано методом правой индукции, примененным к некоторому другому свойству слов. В самом деле, рассмотрим свойство 6, определенное следующим образом: б (Р);Р ([Р-) Тогда, так как [[Р о Р, наличие Р у Р равносильно наличию << у [Р .
Кроме того, так как [Л л.Л, наличие Р у Л равносильно наличию б у Л. По предположению, мы доказали, что для любого слова Р имеет место импликация «если Р обладает свойством Р, то им обладает и всякое слово КР, где $ †как-нибудь буква». Следовательно, для любого Р имеет место импликация «если [Р обладает свойством Р, то им обладает и всякое слово $[Р , где 5 †как-нибудь буква (т.
е. всякое слово (Р$ )». « 17! СЛОВА 1ПРОДОЛ>КЕНИЕ $2) тз СЕМИОТИКА !Гл. и А тогда для любого Р верна импликацня «если Р обладает свойством б, то им обладает и всякое РК, где $ — какая-нибудь буква». Так как Л обладает свойством 6, то, пользуясь методом правой индукции, мы заключаем, что любое слово Р обла- дает свойством б, а значит, им обладает и слово [Р, что равносильно наличию у Р свойства Р, что и требовалось доказать. Таким образом, метод левой индукции сводится к методу правой индукции. 4. Непосредственно из определения графического равен- ства слов Ц 2.4] вытекает следующее предложение: 4.1.
Если РКХЯ>), то Р 2. Я и я Р Ч. Верно также и аналогичное предложение 4.2. Если $Р Х»!!",>, то РХ Я и 5 Аг«). Действительно, пусть КР о ТД. Тогда [$Р х[7ф . Но тогда [Р 5Х[1~ 7! [3.2.2, 3.2.1] и, значит, [Р ~Я и $Л.Т!. Но из [Р ХЯ следует, что [[Р м.[[Я и, значит, РХЯ [3.2.3], что и требовалось доказать. Таким образом, всякое непустое слово допускает единст- венное представление в виде РЦ и единственное представле- ние в виде ЕР. Букву $ в единственном представлении непус- того слова Я в виде РК мы будем называть последней буквой слова 9; букву $ в единственном представлении непустого слова Я в виде КР мы будем называть первой буквой слова Я.
4.3. Всякое непустое слово имеет единственную первую букву и единственную последнюю букву. 5. Высказывание РК м ЯК разрешимо [Я 11.7], Докажем материальную импликацию 5.1. Если РК лгЯК, то РХ«,>. Фиксируем слова Р и Я. О слове К условимся говорить, что оно сокращаемо справа, если верна материальная импли- кация (1) «если РК х 9К, то Рл.
Я», Покажем, что всякое слово сокращаемо справа. Слово Л обладает этим свойством (з 13.4.6, з 2.5). Дока- жем материальную импликацию (2) «еслн К сокращаемо справа, то и К$ сокращаемо справа». Действительно, предположим, что К сокращаемо справа, т. е, что верна материальная импликация (!). Имеем верную материальную нмпликацню (3) «если РКК я ЯКЗ, то РК Р ЯК» [4.1].
Поэтому верна материальная импликация «если РТЯ Р ЯК~, то РХ ф> [(3), (!), 3 13.4.2], означающая, что К$ сокращаемо. Тем самым мы доказали истинность материальной импликации (2). Применяя метод правой индукции, убеждаемся в истинности теоремы 5.1. Аналогично, верна материальная импликацня 5.2. Если Кря.К9, то Рл.Я. В самом деле, пусть КР Р КЦ. Тогда [КР Х[КЯ, т. с. [Р [К в [Я [К [3,2.2].
Но тогда [Р Р Я [5.1] и, зна- чит, [[Р м [[Я'-"-', т. е. Р л. Д [3.2.3], что и требовалось доказать. Теоремы 5,1 и 5.2 мы называем законами сокращения. 6. Следующие теоремы очевидны: 6.1. РЪД~~Л. 6.2. Если РЯЛ, то РК д Л и КР7'Л [6.1]. 6.3. Если РК д~>«, то Р Е.Л и К я.Л [6.2]. 7. Наконец, еще следует ввести несколько полезных для дальнейшего понятий, относящихся к алфавитам.
Прежде всего, мы условимся говорить, что алфавит Б является расширением алфавита А, если всякая буква А яв- ляется также и буквой Б. В этом случае мы иногда будем пользоваться записью А~Б. Введем, кроме того, разнвапь алфавитов А н Б, которую будем обозначать посредством (А' Б). Определение (А' Б) мы сформулируем индуктивно. Пусть А и Б — какие-либо алфавиты, а $ — буква, не являющаяся буквой алфавита А. Тогда положим (Л" Б) Л, [ (А',Б), если $ есть буква Б, (Аз" Б)— ( (А",Б) $, если я не есть буква Б. Нетрудно показать, что (А",Б) состоит нз тех и только тех букв, которые являются буквами А и не являются бук- вами Б. После этого можно ввести обьединение (А 0 Б) алфавитов А и Б, положив (АВ Б) — А(Б' А). Легко проверить, что (А () Б) состоит из тех н только тех букв, которые являются буквами хотя бы одного из алфавитов А и Б.
[гл. и семиотикА НЛЧЛЛЛ '44 КОНЦЫ СЛОВ : 1»1 75 Знаки ~, ', и (1 содержат в себе намек на имеющуюся теоретико-множественную аналогию. Однако понимать их мы должны, конечно, в соответствии с только что сформулированными определениями, без всякого апеллирования к теории множеств. $18 Начала и концы слов 1.
Мы говорим, что слово Р есть начало слова Я, если . существует слово Х такое, что Яя РХ; мы говорим, что слово Р есть конец слова Я, если существует слово Х такое, что Я тгХР. Имеем согласно этим определениям; 1.1. Двуместные предикаты «Р — начало Я» «Р — конец Я» полуразрешимы. Докажем усиленную импликацию 1.2. Если () — начало РК, то Π— начало Р или 1ея.рк. Ввиду 1.1 высказывание 1.2 можно действительно рассматривать как усиленную импликацию, т. е. как высказывание общности: «Прн ВСЯКОМ Х, ЕСЛИ Рсм.1ЕХ, та Я вЂ” НаЧаЛО Р ИЛИ (г.ко,», Для его доказательства достаточно уметь доказывать для любых слов Р, Я и К и любой буквы $ материальную импликацию (1) <если РКм. ЯР<, то 1г †нача Р или Я й.
РК» (4 14.1, 4 9.3]. Предположим, что (2) РК х Я17, Имеем Яд~А или Р м.Л Ц 11,7,2]. Если Д~.'Л, то имеются В и») такие, что (3) Д ХЯ»). Мы имеем тогда РЬ к Мц ((2), (3)] и потому Ря.ЯЯ [$17.4.1], Таким образом, в данном случае <г есть начало Р. Если же Я я.Л, то (г я.Р$.,((2)]. Таким образом, в обоих случаях имеет место дизъюнкция (4) «<г — начало Р или Я я Рк».
Мы доказали ее, предполагая верным равенство (2). Следовательно, имеет место материальная импликация (1) (9 13.6.2), что и требовалось доказать, 2. Истинность следующих утверждений легко усматривается: 2.!. Всякое слово есть начало и конец самого себя. 2.2. Пустое слово есть начало и конец всякого слова. 2.3. Пустое слово есть единственное начало (единственный конец) пустого слова 12,1, 2.2, 9 17.6.3!. 2.4. Всякое начало слова Р есть начало слова Р<г; всякий конец слова Р есть конец слова С7Р. Последнее следует нз сочетательного закона соединения слов. 2.5.
Слово () тогда и только тогда есть начало слова РЪ„ когда имеет место дизъюнкция 1(4) [1.2, 2.4, 2.1). В силу 2.5 при наличии списка всех начал слова Р мы, присоединяя к этому списку слово Рс, получаем список всех начал слова РЪ. Пользуясь этим и принимая во внимание, что список слов, единственным элементом которого является Л, есть список всех начал слона Л 12.3), убеждаемся в возможности построения списка начал любого слова, т.
е. в истинности утверждения 2.6. Для всякого слова может быть построен список всех его начал, Аналогично доказывается 2.7. Для всякого слова может быть составлен список всех его концов, В силу 2.6 имеем 2.8. Двуместный предикат «Р — начало 1;Ь разрешим. В самом деле, чтобы узнать, является ли слово Р началом слова 1е, достаточно, построив список всех начал слова 1е, сравнить Р с каждым элементом этого списка, выясняя совпадение слова Р с этим элементом. Аналогично утверждению 2.8 может быть доказано утверждение 2.9. Двуместный предикат «Р — конец 1;Ь разрешим. 77 СЛОВ НАЧАЛ 1гл. н «!8! 76 СЕМИОТИКА 3.
Теперь можно строить и доказывать материальные имплнкации, посылками которых являются высказывания видов: «Х — начало У», «Х — конец У» н конъюнкции высказываний этих видов. 3.1. Если Х вЂ” начало У, а У вЂ” начало 2, то Х вЂ” на- 2. 3.2. Если Х вЂ” конец У, а У вЂ” конец 2, то Х вЂ” конец Я. 3.3. Если Х вЂ” начало (конец) У, а У вЂ” начало (конец) Х, то Х~ У. Теоремы 3.1 и 3.2 доказываются на основе определения предикатов «Х вЂ” начало У» и «Х вЂ” конец У» с помощью сочетательного закона соединения слов.
Докажем первую из материальных импликаций 3.3 (ту, которая относится к началам). Предположим, что Х вЂ” начало У, а У вЂ” начало Х. Тогда осуществимы слова Р и Я такие, что (1) Ум. ХР и (2) Х м. УЯ. Имеем У х 1 аР [(1), (2)1* (4) Л хдР [(3), ~ 17.5.21, (5) д ~Л [(4), 4 17.6.31, Х м. 1 [(2), (5)1. Это равенство доказано в предположении, что Х вЂ” начало У, а У вЂ” начало Х.
Следовательно, имеет место материальная имплнкация «если Х вЂ” начало У, а У вЂ” начало Х, то Х Ае У». Аналогично доказывается вторая часть теоремы З.З (от- носящаяся к концам). Докажем теорему 3.4. Если Х и У вЂ” начала Я, то Х вЂ” начало У или У— начало Х.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
