СПОСОБЫ ПРЕДСТАВЛЕНИЯ ВЫВОДОВ

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

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

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

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

a₂

a₁a₃

a₄a₅

a₆ a₇

Рис. 9.1

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

p₁ - p₈:

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

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

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

p₉: .

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

p₁₀: ;

p₁₁: .

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

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

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

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

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

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

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

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

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

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

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

3) (a₃, a₄) - применение аксиомы p₄;

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

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

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

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

7) (a₃, a₇) - аксиома p₇;

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

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

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. Если является применением некоторой аксиомы p, то дерево вывода этого слова имеет вид ( рис. 9.2):

p

Рис. 9.2.

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

D₁ D₂ D_k

₁₂. . . _k

p

_k+₁

Рис. 9.3

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

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

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

p₃p₄

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

p₁₀p₉

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

p₁₀

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

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

p₁₀

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

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

Рис.9.4

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

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

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

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

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

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

1) p₄: , p₅: ,

2) p₆: , p₇: , p₈: ,

p₉: ,

3) p₁₀: , p₁₁: ,

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

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

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

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

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

2. Пусть s₁... s_m и d₁ ... d_n - двоичные записи натуральных чисел, между которыми выполнено отношение “<“.

2.1. Если m < n, то вывод слова s₁ . . . s_m < d₁ . . . d_n начинается либо со слова s₁ < d₁ d₂, если s₁ = 1, являющегося применением одной из продукций p₂, p₃ , либо со слова s₁ < d₁, если s₁ = 0, являющегося применением продукции p₁.

После этого с помощью продукций p₄- p₉ можно достроить начальное слово до слова s₁… s_m < d₁ ... d_m+₁.

Затем с помощью продукций p₁₀ - p₁₁ полученное слово можно достроить в слово s₁... s_m< d₁ . . . d_n.

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

Начнем вывод слова s₁ ... s_n< d₁ . . . d_n со слова s_i< d_i, являющегося применением продукции p₁.

Затем с помощью продукций p₁₂ и p₁₃ можно вывести слово s₁. . . s_i< d₁ . . . d_i, для которого "j = 1,...,i-1(s_j = d_j). Процесс вывода этого слова начинается с применения продукции p₁₃, которая добавляет первые слева от s_i и d_iединицы. Затем с помощью необходимого числа повторных применений продукции p₁₂ можно разместить в обоих числах все нули между s_i и d_i и первыми единицами слева. Затем выполняется вставка в s₁. . . s_mи d₁ . . . d_n следующих единиц левее s_i и d_i с последующим размещением нулей и т.д. пока не будут построено слово s₁ ... s_i< d₁ . . . d_i

Из полученного слова с помощью продукций p₆ - p₉, позволяющих добавлять в них справа по одну символу можно вывести окончательное слово s₁ ... s_n < d₁ . . . d_n.

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

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

<5 6 789 10 11 >

Дата добавления: 2015-09-18; просмотров: 600;