9.2.1. Способы представления выводов

Естественная форма представления выводов  их запись в виде последовательностей входящих в них слов. При этом для каждого слова последовательности указывается, из каких слов и с помощью какой продукции выводится такое слово.

Пример. Рассмотрим систему Поста, продукции которой содержат знания для вывода (построения) путей между вершинами графов.

Задание конкретного графа выполняется с помощью продукций-аксиом, задающих его ребра, и имеющих вид: (a, b), где a  начало ребра, а b  его конец.

Например, рассмотрим граф G, приведенный на рис. 9.1:

a₂

a₁ a₃

G

a₄ a₅

a₆ a₇

Рис. 9.1

Ребра приведенного графа задаются следующими продукциями:

₁  ₈:

(a₁, a₂), (a₂, a₃), (a₁, a₄), (a₃, a₄),

(a₄, a₅), (a₄, a₆), (a₃, a₇), (a₆, a₇).

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

₉: .

Наконец, правила определения пути, соединяющего произвольные две вершины графа, можно выполнять с помощью следующих двух продукций:

₁₀: ;

₁₁: .

Здесь слово way(x, y, z) означает, что z  это путь из x в y.

Продукция ₁₀ представляет простейшее правило существования пути, записываемого как xy, между вершинами x и y, связанными между собой отдельными ребрами.

В продукции ₁₁ представлено свойство транзитивности путей в графе, которое состоит в том, что если из вершины x в вершину y ведёт путь uy, а из вершины y в вершину z ведет путь yw, то x и z соединяет путь uw.

Данная система Поста состоит из:

1) основного алфавита A ={(, ), “,”, way, a₁, . . . , a₇};

2) алфавита переменных V ={x, y, z, u, w};

3) множества продукций P = {₁, ... , ₁₁}.

(Отметим, что символ запятой является элементом множества A.)

Рассмотрим вывод слова, содержащего путь между вершинами a ₁ и a ₇ в графе G.

1. (a₁, a₄)  применение аксиомы ₃;

2. way(a₁, a₄, a₁a₄)  получается применением продукции ₁₀ к уже выведенному слову (a₁, a₄);

3. (a₃, a₄)  применение аксиомы ₄;

4. (a₄, a₃)  получается применением продукции ₉ к слову (a₃, a₄);

5. way(a₄, a₃, a₄a₃)  применением продукции ₁₀ к слову (a₄, a₃);

6. way(a₁, a₃, a₁a₄a₃)  получается с помощью ₁₁, применённой к словам:

way(a₁, a₄, a₁a₄) и way(a₄, a₃, a₄a₃);

7. (a₃, a₇)  аксиома ₇;

8. way(a₃, a₇, a₃a₇)  выводится из слова (a₃, a₇) применением продукции ₁₀;

9. way(a₁, a₇, a₁a₄a₃a₇)  выводится с помощью продукции ₁₁ из слов

way(a₁, a₃, a₁a₄a₃) и way(a₃, a₇, a₃a₇).

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

При этом, если вывод в некоторой системе Поста является бесконечным, то для его представления могут потребоваться специальные соглашения, например при обосновании включения слов в вывод возможно появление последовательностей вида:

₁, ₂, ... , _i, ... "и так далее".

Возможно также использование записи вывода без объяснений, если в них нет необходимости.

При этом приведенный вывод перепишется как:

1) (a₁, a₄);

2) way(a₁, a₄, a₁a₄);

3) (a₃, a₄);

4) (a₄, a₃);

5) way(a₄, a₃, a₄a₃);

6) way(a₁, a₃, a₁a₄a₃);

7) (a₃, a₇);

8) way(a₃, a₇, a₃a₇);

9) way(a₁, a₇, a₁a₄a₃a₇).

Другим удобным и применяемым способом представления выводов в произвольных системах Поста являются деревья вывода.

Корню такого дерева приписывается последнее выводимое слово. Остальные вершины дерева помечены словами, входящими в вывод слова, приписанного корню, и продукциями, используемыми в этом выводе.

Всякая вершина дерева соединена с другими вершинами дерева с помощью ориентированных ребер по следующему правилу.

1. Если является применением некоторой аксиомы , то дерево вывода этого слова имеет вид ( рис. 9.2):



Рис. 9.2.

2. Если D₁, . . . , D_k  это деревья вывода слов ₁, . . . , _k и применение продукции  к этим словам позволяет вывести слово _k+1, то дерево вывода такого слова имеет вид (рис. 9.3):

D₁ D₂ D_k

_{1 2} . . . _k



_k+1

Рис. 9.3

Из определения дерева вывода следует, что если одно и то же слово применяется в выводе для получения нескольких разных слов, то дерево вывода содержит столько вершин, помеченных этим словом, сколько раз оно используется в выводе.

Кроме того, всякая вершина дерева, помеченная словом в основном алфавите, является корнем поддерева, являющегося деревом вывода этого слова.

Для приведенного выше примера вывода слова, представляющего путь из вершины a₁ в вершину a₇, соответствующее дерево вывода имеет вид, приведенный на рис.9.4:

₃ ₄

(a₁, a₄) (a₃, a₄)

₁₀ ₉

way(a₁, a₄, a₁a₄) (a₄, a₃)

₁₀

₁₁ way(a₄, a₃, a₄a₃) ₇

way(a₁, a₃, a₁a₄a₃) (a₃, a₇)

₁₀

₁₁ way(a₃, a₇, a₃a₇)

way(a₁, a₇, a₁a₄a₃a₇)

Рис.9.4

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

Приводимые далее продукции реализуют определение отношения "больше" на множестве неотрицательных целых чисел.

1. Если длины записей сравниваемых чисел  разные, то запись большей длины представляет большее число.

2. Если длины записей сравниваемых чисел равны, то большим является такое число, в котором раньше встречается разряд, по значению больший соответствующего разряда другого слова при поразрядном сравнении слов слеванаправо.

АКСИОМЫ: ₁: 0 < 1, ₂: 1 < 10, ₃: 1 < 11.

Остальные продукции, разбитые на четыре группы:

1) ₄: , ₅: ,

2) ₆: , ₇: , ₈: ,

₉: ,

3) ₁₀: , ₁₁: ,

4) ₁₂: , ₁₃: .

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

Покажем, что с помощью приведенных продукций выводится множество слов, представляющих в точности все правильные неравенства “меньше“ между целыми неотрицательными числами.

1. Непосредственно проверяется, что заключение всякой из продукций ₁  ₁₃ представляет верное неравенство “меньше” для пары чисел, если посылка такой продукции представляет собой верное неравенство.

Следовательно, множество слов, выводимых в приведенной системе, представляет часть отношения “<“ между целыми неотрицательными числами.

2. Пусть ₁ ... _m и ₁ ... _n  двоичные записи натуральных чисел, между которыми выполнено отношение “<“.

2.1. Если m < n, то вывод слова ₁ . . . _m < ₁ . . . _n начинается либо со слова ₁ < ₁ ₂, если ₁ = 1, являющегося применением одной из продукций ₂, ₃ , либо со слова ₁ < ₁, если ₁ = 0, являющегося применением продукции ₁.

После этого с помощью продукций ₄  ₉ можно достроить начальное слово до слова ₁ … _m < ₁ ... _{m+ 1}.

Затем с помощью продукций ₁₀  ₁₁ полученное слово можно достроить в слово ₁ ... _m < ₁ . . . _n.

2.2. Если m = n, то найдем такое наименьшее i, что _i < _i.

Начнем вывод слова ₁ ... _n < ₁ . . . _n со слова _i < _i, являющегося применением продукции ₁.

Затем с помощью продукций ₁₂ и ₁₃ можно вывести слово ₁ . . . _i < ₁ . . . _i, для которого j = 1,...,i-1(_j = _j). Процесс вывода этого слова начинается с применения продукции ₁₃, которая добавляет первые слева от _i и _i единицы. Затем с помощью необходимого числа повторных применений продукции ₁₂ можно разместить в обоих числах все нули между _i и _i и первыми единицами слева. Затем выполняется вставка в ₁ . . . _m и ₁ . . . _n следующих единиц левее _i и _i с последующим размещением нулей и т.д. пока не будут построено слово ₁ ...  _i < ₁ . . .  _i

Из полученного слова с помощью продукций ₆  ₉, позволяющих добавлять в них справа по одну символу можно вывести окончательное слово ₁ ... _n < ₁ . . . _n.

Следовательно, множество слов, выводимых в приведенной системе продукций ₁  ₁₃, совпадает с множеством слов, которые представляют отношение“<“ между целыми неотрицательными числами.

Упражнение. 1.Добавить к продукциям ₁  ₁₃ такие новые продукции, которые позволяют дополнительно выводить все слова вида x<>y, где x и y  неравные числа представленные в двоичной системе счисления. 2. Определить систему Поста, в которой выводятся слова вида x = y, где x и y записи неотрицательных целых чисел в двоичной системе.