Определения, операции, свойства

Исчисление — определённый набор операций над совокупностью математически однородных объектов и правила преобразования этих объектов с использованием данных операций. Примером исчисления, которое широко используется в процессе синтеза логических схем, являются преобразования алгебры логики. Набор правил (аксиом, законов, тождеств) говорит лишь о том, как можно преобразовать исходное булево выражение, но ничего не говорит о том, как надо его преобразовывать (в какой последовательности и что делать на каждом шаге), чтобы, например, на заданном логическом базисе получить минимальную задержку схемы. Таким образом, исчисление, в отличие от алгоритма, не содержит указаний, куда нужно идти, чтобы получить результат, а содержит только список допустимых преобразований.

Расширение понятия алгоритма за счёт введения в рассмотрение объектов нечисловой природы связано с ассоциативным исчислением. Ассоциативное исчисление строится на множестве всех слов в данном алфавите с помощью определённой совокупности операций.

Алфавит — любая конечная совокупность различных символов, называемых буквами. Любая конечная совокупность n букв некоторого алфавита является словом длины n в этом алфавите.

Если, слово L является частью слова М, то говорят, что слово L входит в слово М. Например, в слове abcbcbad имеются два варианта вхождения слова bcb и одно вхождение слова bа.

В качестве операций ассоциативного исчисления определяется система допустимых подстановок, спомощью которых одни слова преобразуются в другие. Подстановка вида L — М, где L и М — слова в том же алфавите, означает: слово L заменяется на М и наоборот.

Например, пусть имеется алфавит А = { а, b, с }. Рассмотрим слово abcbcbab; к этому слову можно применить подстановку ab - bcb четырьмя способами. Заменяя вхождение ab дважды, получим: bcbcbcbbcb. В то же время к слову bacb эта подстановка не применима.

Рассмотрим особую подстановку B. Она означает, что из преобразуемого слова удаляется вхождение слова Р (оно заменяется пустым символом), а также, что между двумя какими-либо буквами преобразуемого слова, впереди него либо за ним, вставляется слово Р. Например, заданы слово dbcd и подстановка abc - #. В результате подстановки получаем: dabcbcd

Итак, ассоциативное исчисление (АИ) — это множество всех слов в некотором алфавите вместе с конечной системой допустимых подстановок.

Эквивалентность слов. Два слова называют эквивалентными, если, одно из них можно получить из другого последовательным применением допустимых подстановок.

Последовательность слов R1, R2, R3,..., Rn, когда каждое слово является результатом однократного применения допустимой подстановки к предыдущему слову, образует дедуктивную цепочку, причём соседние слова в этой цепочке называются смежными. Очевидно, что любые два слова в дедуктивной цепочке являются эквивалентными.

Эквивалентность слов (обозначается L ~ M)обладает всеми свойствами отношения эквивалентности — рефлексивностью, симметричностью и транзитивностью.

Если L ~ М, то при наличии в каком-либо слове R вхождения L в результате подстановки L - М получается слово R', эквивалентное R.

Например, используя эквивалентность acd ~ cad, из слова R = b acd c получаем эквивалентное ему слово R' = b cad c.

В каждом АИ возникает своя специфическая проблема слов, которая заключается в следующем: для любых двух слов в данном исчислении требуется узнать, эквивалентны они или нет. Решение этой проблемы аналогично поиску пути в лабиринте, площадки которого соответствуют смежным словам.

Очевидно, эквивалентность двух слов означает, что соответствующие им площадки связаны некоторым путём, который представляет собой дедуктивную цепочку от одного слова к другому. Проблема слов является далеко идущим обобщением задачи поиска пути в конечном лабиринте. Так как в любом АИ содержится бесконечное множество различных слов, то соответствующий лабиринт имеет бесконечное число площадок, и, следовательно, решение вопроса об эквивалентности слов сводится к поиску пути в бесконечном лабиринте.

С помощью алгоритма перебора решается ограниченная проблема слов; требуется установить, можно ли одно из заданных слов преобразовать в другое применением допустимых подстановок не более чем К раз, где К — произвольное, но фиксированное целое число. Такое ограничение в случае лабиринта означает, что расстояние между рассматриваемыми площадками не превышает К коридоров.

Однако перебор не подходит для неограниченной проблемы слов. Поэтому для получения желаемых результатов необходимо применять другие идеи, основанные на анализе самого механизма преобразования посредством допустимых подстановок.

В некоторых случаях могут быть обнаружены и использованы свойства, остающиеся неизменными для всех слов дедуктивной цепочки (дедуктивные инварианты). На основе дедуктивного инварианта можно установить, какие слова не могут быть эквивалентными.

Проблема слов в АИ имеет большое значение в связи с тем, что к ней сводятся многие геометрические, алгебраические и логические задачи. Так, любую формулу логики высказываний и предикатов можно трактовать как слово в некотором алфавите, содержащем логические символы, высказывания, предикаты и некоторые переменные.