Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 53
Текст из файла (страница 53)
Аксиомы, а также посылки и следствия продукций — это слова в алфавите А()Х; иначе говоря, они содержат, кроме собственных букв системы, еще и переменные. В дальнейшем слова в алфавите А()Х будем называть термами, а слова в А— просто словами. Перемеш1ые капопическои системы аналогичны мстапеременным в логических исчислениях; аксиомы канонической системы — это по существу схемы аксиом логических исчислений.
Говоря о подстановке в термы слов вместо переменных, мы всегда будем иметь в виду, что сохраняется обычное ограничение: вместо всех вхождений одной и той же переменной подставляется одно и то же слово (быть может, пустое). Слово а называется применением аксиомы и, если и получается подстановкой в ы слов вместо переменных. Сло. во а непосредственно выводимо из слов аи ..., а„применением продукции Р с и посылками, если найдется такая подстановка слов вместо переменных Р, которая посылки Р превратит в слова аи ...,а„, а заключение Р— в слово а.
Например, слово ЬЬ непосредственно выводимо из слов асаЬ, саЬЬ применением продукции ах,Ь, х,Ьх, Ьхз при подстановке х, =са, хз=Ь. Последовательность слов называется доказательством в канонической системе, если каждое слово этой последовательности — либо применение аксиомы, либо непосредственно выводимо из предыдущих слов последовательности применением некоторой продукции системы. Слово называется доказуемым (или теоремой), если оно является последним словом некоторого доказательства.
Пример 6.7.а. Множество всех нечетных чисел в уиарном представлении — это множество всех теорем канонической системы с алфавитами ((), (х), аксиомой) и продукцией х-+хз. Если эту продукцию заменить продукцией х- хх, то получим каноническую систему, порождающую степени двойки (в унарном представлении): ~, ~1, ~~1~, ... б. Множество всех формул исчисления высказываний порождается канонической системой с алфавитами (аи ...
..., а„~/,й, 1, —, (,)), (хь хе), аксиомами аи ..., а„и про- (8.18) дукциями х„х,=»(х, '/ х,); Х1 Хэ» (Х1 й Х2) х, х =«(х -эх,); Х,=» ) Хь Отметим, что здесь алфавит пропозициональных букв конечен. Для построения исчисления с бесконечным множеством пропозициональных букв сначала нужно построить формальную систему, порождающую это множество пз конечного алфавита символов. Именно с этой целью в языках программирования вводится индуктивное определение идентификатора; оно представляет собой формальную си.
стему, порождающую бесконечное множество'переменных языка из конечного алфавита букв и цифр. При построении машин Тьюринга часто оказывалось удобным (а иногда необходимым) вводить вспомогательные символы, которые участвуют в процессе вычисления, но не присутствуют ни в исходных данных, ни в результате. Аналогичные средства вводятся и в формальных системах. Пусть дана каноническая система 5 с собственным алфавитом А', в котором выделен подалфавит А. Если иас интересуют только те теоремы 5, которые являются словами в А, то будем говорить, что система 5 является канонической системой над А, А назовем основным алфавитом, А' — расширением А, а символы из А",А — вспомогательными. Пример 6.8.а. Последовательность чисел О, 1, 1, 2, 3, 5, 8...,в которой каждый член, начиная с третьего, равен сумме двух предыдущих, называется последовательностью Фибоначчи, а ее элементы — числами Фибона ши.
Числа Фибоначчи в унарном представлении порождаются канонической системой над (1) со вспомогательным символом *, аксиомой ° 1 и двумя продукциями: Х1 ° Хэ» Х1 Х1 Хз' К1 Х1 ~> Х1. В этой системе символ ° служит маркером, разделя1ощим два числа, аксиома задает первые два числа последовательности (О изображен пустым словом слева от маркера), первая продукция из п-го и (и+1)-го члена получает (и+1)-й и. (и+2)-й члены последовательности, вторая продукция из пары чисел выделяет первое; только применение второй продукции дает слона в алфавите (1), 2зз б.
Реализуем изложенный в примере 6.7, б план построения формул исчисления высказываний с бесконечным множеством пропознциональных букв. Зти «буквы» будут обозначаться символом а с числовым индексом, т. е, будут представлять собой слона вида а, а01, а523 и т.
д,, играющие роль идентификаторов (имен переменных). Система содержит основной алфавит А=(а, О, 1, 2, ..., 9, ~/, й, ), —, (,)), вспомогательные символы (1, 1), аксиому а1 и 16 продукций: х,1=~х, 01; х, 1 =р х, 11; х, 1 =р х, 91; х,(=,'>х,7; х,~, х,7'=,">(х, ~/ х,)); х,7', х,7=Р(х,йхз) 7"; х, ~, х,7'~ (х,- х,) 7'; х(~ ) х~; х1~ =рх1 Первые десять продукций порождают идентификаторы; следующие пять продукций формализуют индуктивное определение формулы (из этих пяти четыре последние отличаются от продукций (6.15) только символом 1), последняя продукция служит для удаления символа 1.
Вспомогательные символы играют здесь несколько непривычную роль — они по существу являются признаками (или метками) определенного класса слов: 1 — метка класса идентификаторов, 1 — метка класса формул. Благодаря этому формальный вид продукции очень близок к тексту соответствующей части индуктивного определения: 11-я продукция означает «всякнй идентификатор естьформула», а 12-я: «если х~ и хз — формулы, то (х,~/х~) — формула». Прием использования в формальных системах специальных символов как признаков классов широко используется в формальных системах Смальяна, которые за недостатком мес та в данной книге не рассматриваются.
Более подробно об использовании формальных систем такого рода для опи. сания алгоритмических языков говорится в (34], о системах Смальяна — в [46~. Связь канонических систем с системами подстановок довольно ясна, по крайней мере в одну сторону; очевидно, что всякой подстановке аг-~6; соответствует продукция х~а~х~=ьхь 6;х„ поэтому для всякой системы подстановок легко построить эквивалентную ей каноническую систему.
Соответствие в обратную сторону менее очевидно; однако о том, что оно существует, можно заключить, сопоставив теорему 6.14 (из которой следует, что множество теорем канонической системы перечислимо) с теоремой 6.15 (любое перечислимое множество можно представить как множество заключительных слов в некоторой системе подстаиовок).
Правда, понятие заключительного слова может показаться несколько искусственным и слишком уж приближающим формальные системы к машинам Тьюринга; если рассматривать формальную систему как генератор элементов перечислимого множества, более естественным было бы описание перечислимого множества как множества теорем некоторой формальной системы.
Это нетрудно сделать, используя введенное ранее понятие канонической системы с расширенным алфавитом. Теорема 6Л8. Для любого перечислимого множества М слов в алфавите А существует каноническая система иад А, множество теорем которой совпадает с М. Пусть М перечисляется машиной Тьюринга Т с алфавитом ленты Ат=(аь ..., а„), первые пг букв которого образуют алфавит исходных данных (т(п), множеством состояний я=(дь ..., д,) и системой команд ут.
Определим каноническую систему 5 над А следующим образом: А = Ах, А'=Ат()Ят, 'аксиома системы °; командам машины Т поставим в соответствие продукции аналогично тому, как это делалось при доказательстве теорем 6.15 и 6.16: например, команде д,а~- д~аЯ соответствует продукция х,су;а;хз=ь-х,а,дахр [ср. (6.13)). Кроме того, введем следующие гп+2 продукции: х, ° -рх, а, °; х, . =рх,а х,. ~д,х,; д,х,~х,. Первые т продукций порождают из аксиомы все множество слов в алфавите исходных данных с маркером в конце: (и+1)-я продукция (стартовая) порождает из лю- бого исходного слова начальную конфигурацию; после этого работают продукции, соответствующие командам машииы Т; наконец, в заключительных конфигурациях (и только в иих!) символ состояния выбрасывается и получаются искомые теоремы в алфавите А. П Итак, в терминах канонических систем можно описать любые перечислимые множества.
Правда, используемое определеиие канонической системы (в частности, вид ее продукций) является слишком общим; применение продукции трудно назвать элементарным шагом (хотя свойство применимости продукции, как нетрудно видеть, разрешимо). Поэтому возникает задача нормализации канонических систем, т.е. придание им более простого, «иормальиого» вида.
Каноническая система называется нормальной, если оиа имеет одну аксиому, а все ее продукции имеют вид ах-+-х]). Применение такой продукции к слову (если оио возможно) просто и стандартно: у слова вычеркивается начальный отрезок а и к копну приписывается ]). Теорема 6.19 (теорема Поста о норм алькой форме). Для любой канонической системы С5 с алфавитом А существует нормальная каиоиическая система Л5 иад А, эквивалеитвая С5 (т.е, множество теорем У5 пад А и множество теорем С5 совпадают). Прямое доказательство этой теоремы, содержащее метод построе.
ния й)5 по С5, довольно слогкно. Его можно найти, например, в ]44], где оно занимает целую главу. Ограаичимся косвенным доказательством существования )У5, а имеиао: пока>кем, что для любой системы подстановок 5 в алфавите А существует нормальная каноническая система )У5 пад А, эквивалентная 5. Пусть А=(аь,,.,а„) и 5 содержит й подстаповок а;-ьйь Определим й!5 как систему с расширенным алфавитом Л'=(аь...,а„, а,,...,а„) и й+2л продукциями: а,. х =-> яр, (1 — — 1, ..., л); (6.16) о, (~) ю ж,! (6.17) а,, (х) ~ ха., (6.! 8) где Р,.
здесь и в дальнейшем обозначает слово Рь в котором все буквы из А заменены соответствующими буквами со штрихом. Пусть к слову у в 5 применима подстановка аг-ьрж у=у~аьуз и в 5 у,матэ!-у1])гув но тогда в й!5 уфмфг1-о~угу,1-уэу!6,1-тгр ь-у,Раут. Тзк как любой вывод у,'6 в 5 есть цепочка подстановок, то по выводу у 1- Ь в 5 можно построить вывод у ь б в й!5. 268 Пусть теперь в Л!Я имеется вывод у, б, где у, б — слова в А. Разобьем этот вывод на отрезки 71-е! ь-е! ь-...г-б, такие, что е . и е! з О (для всех !) — слова в А, а все слова между ними содержат вспомогательные буквы, и рассмотрим для определенности первый из них ть-ег Если у — слово в А, то продукциями (6.17), (6.18) из него можно получить лишь слова вида угу1, ттуь у', где слова ть у, таковы, что тгуз=у.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
