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

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

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

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

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

a ₂

a ₁ a ₃

G

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+ 1}, то дерево вывода такого слова имеет вид (рис. 9.3):

D ₁ D ₂ D _k

_{1 2}... _k

p

_{k+ 1}

Рис. 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+ 1}.

Затем с помощью продукций 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 записи неотрицательных целых чисел в двоичной системе.

Дата добавления: 2015-03-31