markov_teorija_algorifmov (522344), страница 14
Текст из файла (страница 14)
В каждом отдельном случае, однако, читатель, если он того пожелает, извлечет из доказательства интересующие его детали. Иногда читатель, вероятно, захочет остановиться на соображениях „здравого смысла". Мы не будем мешать ему в этом, так как в конце концов семантика должна уточнять здравый смысл, но не отменять его, а те места, где здравый смысл может подвести, мы более или менее полно „оградили" соответствующими разъяснениями. 3 А. А. Марнов, Н. М. Нагорный а 771 СЛОВА (ПРОДОЛЖЕНИЕ $27 67 ГЛАВА 11 СЕМИОТИКА ЛИНЕЙНО РАСПОЛОЖЕННЫХ КОНСТРУКТИВНЫХ ОБЪЕКТОВ В 17. Слова (продолжение В 2) 1. На протяжении Я!7- -2! мы будем считать фиксиро- ванным некоторый алфавит А «). Слова в нем мы будем назы- вать просто словами, а его буквы — просто буквами.
Слова мы будем обозначать вербальными переменными Р, О, 1г, 8, буквы — литеральными переменными $, т), й. 2. В 5 2.5 мы ввели операцию соединения слов. Результат применения этой операции к словам Р и Я мы условились обозначать посредством (Р, Я). Естественно ожидать, что введенная операция подчиняется сочетательиому закону, т... что для любых слов Р, !7 и )с выполняется графическое 7 венство (1) [Р, [О, 7(]]~[[Р, ф, 77], Покажем, что это действительно так. С этой целью зафиксируем слова Р и !',7, рассмотрим свой- ство слов»с «удовлетворять графическому равенству (1)» и правой индукцией по 1« 5 9А! установим, что этим свойством обладает любое слово )с.
Действительно, пустое слово А им обладает, так как [Р, [О, А]]~[Р, (7] Х[[Р, <~, А]. Пусть теперь 77 — произвольное слово, удовлетворяющее ра- венству (1), и пусть $ -- произвольная буква. Тогда [Р М 77Ч]~[Р [О 7(]И вЂ” [Р [О )7]]~ ~ПР, й, Ч~ [(1)] т [[Р, О], А7Ц, т.
е. (2) [Р, Я , !се]] л"ь[[Р, О], )се]. ") В качестве переменных для обозначения алфавитов мы будем подь- зоваться прямыми прописными буквамн русского алфавита А, Б, В и т. п.. прибегая, когда ато будет удобно, к индексам. Таким образом, пустое слово обладает указанным свойством, и если им обладает какое-либо слово»с, то, какова бы ни была буква 6, им обладает и слово 1«6. Значит, указанным свойством обладает любое слово 1«, и потому при любых Р, 9 и гс имеет место равенство (1), что и требовалось доказать.
Заметим, что предикат графического равенства разрешим [3 11.7), и поэтому импликация «если (!), то (2)> при любых Р, Я, 1« и В может пониматься как материальная. Принимая во внимание установленный сочетательный закон, мы теперь — как обычно — будем писать РС7 вместо (Р, Щ, РЩ вместо !Р, (О, )с)! и т. д. Очевидно, что РЩ есть слово, получаемое написанием подряд слова, (графически) равного Р, слова, равного О, и слова, равного 1«. Слово РЩ мы будем называть соединением слов Р, с) и 1«, слово РОРΠ— соединением Р, Я, Р и 5 и т. д. Мы видим, таким образом, что сочетательный закон сложения натуральных чисел является частным случаем общего сочетательного закона соединения слов.
3. Формулируя наше определение слов в данном алфавите (э 2,2), мы существенным образом пользовались наличием в нашем распоряжении некоторой исходной элементарной операции — операции «правого присоединения» букв этого алфавита к словам. Ее наличие давало нам возможность развертывать конструктивные процессы построения слов в направлении «слева направо». Метод правой индукции обосновывался нами со ссылкой на такой именно способ порождения. Естественно спросить: что будет, если операцию правого присоединения заменить аналогичной операцией «левого присоединения» или пользоваться обеими этими операциями совместно, чередуя их применение произвольным образом? Что будет, если метод правой индукции дополнить (или заменить) аналогичным ему «методом левой индукции»7 3.!.
Чтобы ответить на первый из поставленных вопросов, мы рассмотрим одно связанное с алфавитом А исчисление ЯА, Объекты, выводимые в этом исчислении, мы будем называть лп-словами в алфавите А. В качестве единственной аксиомы ЗА мы возьмем „пустое" лп-слово, которое тоже будем обозначать Л. Правил вывода у нас будет два: П) от лп-слова (7 разрешается перейти к лп-слову (7$; Л) от лп-слова (7 разрешается перейти к лп-слову $(7 (здесь $ — произвольная буква алфавита А, а 0$ и $(7 означают ссютветственно результаты приписывания к лп-слову 0 буквы $ справа и слева).
3 ° зв семиотикз 1гл. и СЛОВА (ПРОДОЛЖЕНИЕ 1 2) Вывод с анализом в 5д мы будем называть нормальным, если аксиома встречается в нем только однажды (на первом месте) и если всякое являющееся его членом лп-слово выводится из непосредственно предшествующего. Вывод с анализом в 5л мы будем называть правосторонним, если в его анализе нет ссылок на правило Л). Индукцией подлине вывода легко показать, что члены любого правостороннего нормального вывода в 5„являются словами в А. Пусть $ — произвольная буква. Рассмотрим операцию ~рь над правосторонними нормальными выводами, определенную следующим образом. Взяв произвольный вывод (г' указанного типа, мы к каждому его члену слева припишем букву е и над полученным таким образом списком слов напишем пустое слово Л. Обозначим полученный список через В". Индукцией по его длине легко показать, что он является выводом в 5л и что переход от любого его члена к непосредственно следующему может быть осуществлен по правилу П).
Кроме того, аксиома встречается в Ф" только один раз. Следовательно, придав )Г соответствующий анализ, мы можем превратить его в правосторонний нормальный вывод. Этот вывод мы и возьмем в качестве срь(Ф'). Легко видеть, что если заключительный член 1Р' есть Р, то заключительным членом срь()Р) будет КР. Имеет место следующее утверждение: 3.1.1.
Для всякого вывода в 5л может быть построен некоторый правосторонний нормальный вывод в 5л с тем же самым заключительным членом. Действительно, взяв произвольный вывод йг в 5л, устроив какой-либо его анализ и двигаясь в соответствии с этим анализом от заключительного члена вывода вспять, мы получим некоторый нормальный вывод М7, с тем же самым заключительным членом.
Если при этом окажется, что в анализе вывода 13", отсутствуют ссылки на правило Л), то этот вывод и будет искомым. Если же такие ссылки будут иметься, то мы возьмем начальный отрезок вывода Ф', до первой из них (включительно). Этот отрезок будет иметь вид Ф', ~Р (по правилу Л) из предыдущей формулы), где Ф, — правосторонний нормальный вывод, а $ — буква, присоединяемая по правилу Л) к заключительному члену вывода )3'„который, таким образом, есть Р. Применим к В', операцию я~1. Согласно сделанному выше замечанию заклю- читальным членом правостороннего нормального вывода ~рь(13',) будет ЕР, и, заменив рассматриваемый начальный отрезок вывода )Р', выводом <рь()Р',), мы уменьшим число ссылок на правило Л) в выводе (Р', на единицу. Повторяя указанную процедуру нужное число раз, мы придем к правостороннему нормальному выводу Р7, в 5л с заключительным членом, совпадающим с заключительным членом вывода И'О а тем самым — и Ю, что и требовалось доказать.
Принимая во внимание, что объекты, выводимые право- сторонними нормальными выводами, суть слова, мы можем утверждать, что 3.1.2. Всякое лп-слово является словом. 3.2. Как уже отмечалось, наряду с методом правой индукции может быть сформулирован аналогичный ему метод левой индукции по построению слов, состоящий в следующем. Пусть мы хотим доказать, что всякое слово в алфавите А удовлетворяет некоторому предикату Р. Для этого мы доказываем, что: 1) Л удовлетворяет Р и 2) каково бы ни было слово Р, если Р удовлетворяет Р, то и всякое слово ~Р, где е — какая-нибудь буква, удовлетворяет Р. В ряде случаев бывает удобно пользоваться именно этим методом левой индукции. Представляет известный интерес вопрос о взаимоотношении методов правой и левой индукции.
Можно ли, например, всякое доказательства, проведенное с использованием метода левой индукции, заменить соответствующим доказательством, использующим одну только правую индукцию? Ответ на этот вопрос оказывается утвердительным. Однако для получения его нам предварительно требуется рассмотреть одну операцию над словами — операцию их обращения. Результат применения этой операции к слову Р мы будем обозначать посредством(Р .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
