Индуктивная спецификация: сверху вниз против снизу вверх по правилам вывода?

Question

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

Согласно тексту парадигм языка программирования:

Индуктивная спецификация - это мощный метод задания набора значений.Чтобы проиллюстрировать этот метод, мы используем его для описания некоторого подмножества S натуральных чисел N = {0, 1, 2,.,.} .

Определение сверху вниз:

Натуральное число n в S, если итолько если

1. n = 0 или
2. n −3 ∈ S.

Мы знаем, что 0 ∈ S. Следовательно, 3 ∈S, так как (3 - 3) = 0 и 0 ∈ S. Аналогично 6 ∈ S, так как (6−3) = 3 и 3 ∈ S. Продолжая таким образом, мы можем заключить, что все кратные 3 находятся в S.

А как насчет других натуральных чисел?Является ли 1 ∈ S?Мы знаем, что 1! = 0, поэтому первое условие не выполняется.Кроме того, (1−3) = −2, которое не является натуральным числом и, следовательно, не является членом S. Поэтому второе условие не выполняется.

Определение снизу вверх:

Определите набор S как наименьший набор, содержащийся в N и удовлетворяющий следующим двум свойствам:

1. 0 ∈ Sи
2. если n ∈ S, то n +3 ∈ S.

«Наименьшее множество» - это то, которое удовлетворяет свойствам 1 и 2 и является подмножеством любогодругой набор, удовлетворяющий свойствам 1 и 2. Легко видеть, что может быть только один такой набор: если S1 и S2 оба удовлетворяют свойствам 1 и 2 и оба наименьшие, то S1 ⊆ S2 (поскольку S1 наименьший), иS2 ⊆ S1 (поскольку S2 наименьшее), следовательно, S1 = S2.Нам нужно это дополнительное условие, потому что в противном случае существует множество наборов, которые удовлетворяют оставшимся двум условиям

Правила вывода:

_____
0 ∈ S

n ∈ S
---------
(n+3) ∈ S

Этоэто просто сокращенная запись предыдущей версии определения.Каждая запись называется правилом вывода или просто правилом;горизонтальная линия читается как «если-тогда». Часть над линией называется гипотеза или антецедент ;часть под линией называется вывод или последующий .Когда есть две или более гипотезы в списке, они связаны неявным «и»

---

Теперь возникают вопросы.

• Вероятно, самый важный вопрос - почемуМне нужно знать эти индуктивные определения и как они полезны в реальном случае?
• Почему Google почти не дает результатов по индуктивному определению?
• Если сверху вниз, снизуи правила вывода по существу показывают одно и то же. Зачем нам нужно 3 способа написания одного и того же?
• Почему мне так трудно найти индуктивные определения проблем, немного более сложные, чем в книгеНапример, например:

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

1. {2n+3m +1 | n,m ∈ N}
2. {(n, 2n+1) | n ∈ N}

Answer 1

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

Ваш первый вопрос - зачем нам нужны индуктивные определения? - проще всего ответить. В информатике огромное количество структур определяются индуктивно. Например, ваш простой связанный список имеет индуктивное определение

• Пустой список является связанным списком.
• Один узел, за которым следует связанный список, является связанным списком

Или двоичное дерево:

• Пустое дерево - это двоичное дерево.
• Узел с двумя дочерними элементами, которые являются двоичными деревьями, является двоичным деревом.

Или регулярные выражения:

• & пустой; является регулярным выражением.
• a является регулярным выражением для каждого символа a
• Если R1 и R2 - регулярные выражения, R1 | R2 - регулярное выражение.
• Если R1 и R2 - регулярные выражения, то R1 R2 - регулярное выражение.
• Если R - регулярное выражение, R * - регулярное выражение.
• Если R - регулярное выражение, (R) - регулярное выражение.

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

• Чтобы посетить пустое дерево, ничего не делать.
• Чтобы посетить дерево, состоящее из узла и двух поддеревьев:
  • Посетить узел
  • Посетите левое поддерево
  • Посетите нужное поддерево

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

Индуктивные определения также могут быть использованы для формального доказательства свойств структур. Например, вот формальное определение дерева AVL:

• Один узел - это дерево AVL порядка 0
• Узел с одним или двумя дочерними элементами, которые являются деревьями AVL порядка 0, является деревом AVL порядка 1.
• Узел с двумя дочерними элементами, которые являются деревьями AVL порядка n - 1, или с одним дочерним элементом, который является деревом AVL порядка n - 1, а другой - это дерево AVL порядка n - 3, является деревом AVL порядка n.

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

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

Ваш второй вопрос - почему Google не приводит никаких примеров для индуктивного определения? - Я думаю, это потому, что он интерпретирует это как «определение индукции», а не как сам термин. Если вы посмотрите рекурсивное определение , то вы найдете множество примеров индуктивных определений, поскольку индуктивные определения и рекурсивные определения очень похожи друг на друга.

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

Ваш четвертый вопрос - почему вы не можете найти примеры?- можно легко исправить, потратив минуту, чтобы взглянуть на классические структуры данных и алгоритмы, о которых вы знаете.Сколько структур данных вы можете определить индуктивно?Попробуйте взглянуть на связанные списки, двоичные деревья, красно-черные деревья, деревья AVL и т. Д. Для вдохновения.Как бы вы определили график?DAG?Точно так же попробуйте взглянуть на синтаксические структуры.Например, как бы вы индуктивно определили строки сбалансированных скобок?Как насчет прототипов функций в C?

Ваш последний вопрос - существует ли систематический способ решения этих проблем?- имеет отрицательный ответ.Вы можете определить повторения, которые эквивалентны имитации произвольных машин Тьюринга на входах, и, поскольку проблема остановки неразрешима, нет общей процедуры для решения подобных проблем.Однако существует множество подходов.Попробуйте взглянуть на «Конкретную математику» Грэма, Кнута и Паташника, чтобы узнать, как работать через рецидивы.

Надеюсь, это поможет!

Answer 2

Нет системного подхода, кроме как "использовать свой мозг". Но вам повезло, потому что эти два примера действительно очень близки к исходному примеру:

1. Натуральное число k находится в S, если а) k = 1 или b) k-2 ∈ S или с) k-3 ∈ S

1. а) 0 ∈ S б) If n ∈ S, then n+2 ∈ S в) If n ∈ S, then n+3 ∈ S

2. Пара натуральных чисел (k, l) находится в S, если а) k=0 and l=1 или b) (k-1, l-2) ∈ S

2. а) (0,0) ∈ S б) If (k,l) ∈ S, then (k+1, l+2) ∈ S