Индуктивное доказательство по длине последовательности вывода. | MetodPro.ru

Реклама на сайте

Индуктивное доказательство по длине последовательности вывода.


26. Индуктивное доказательство по длине последовательности вывода
Оно часто используется для СОС.
Метод:
1) Доказывается, что свойство выполнимо для всех последовательностей вывода, длиной 0.
2) Доказывается, что свойство выполнимо для всех остальных последовательностей вывода, при этом считается доказанным это свойство для всех последовательностей, длина которых не превышает k (это индуктивная гипотеза), и показываем истинность этого свойства последовательностей длины k+1.
Индуктивный шаг при этом включает в себя рассмотрение вариантов, отражающих
a) структуру синтаксических элементов
b) возможные переходы в соответствии с деревом вывода.





Методические пособия

  • Системы автоматизированного проектирования
  • Социология молодёжи
  • Общая социология
  • Криптография
  • Проектирование трансляторов
  • Компьютерная графика
  • Моделирование систем
  • Информационная безопасность
  • Теория вычислительных процессов
  • Логические основы искусственного интелекта
  • Проектирование распределённых информационных систем