Cтраница 2
Отметим попутно, что было бы ошибкой пытаться представить возмущение как действие внешней среды на изучаемую систему, получая таким образом равновероятность собственных состояний полной энергии системы. I: задача доказательства / / - теоремы, составляющая одну из наиболее важных частей теории, может быть поставлена лишь по отношению к изолированной системе. [16]
Правильность программы определяется как соответствие между программой и ее заданной функцией. Для сведения задачи доказательства правильности определенной составной программы к задаче доказательства правильности определенных элементарных составляющих программ привлекают алгебраические понятия. Верификация правильности программ без циклов осуществляется с помощью анализа соответствующих Е - схем. Лемма о переходе от итеративных программ к рекурсивным позволяет свести задачу верификации циклических программ к задаче верификации эквивалентных программ без циклов. В теореме правильности обобщены требования к верификации, соответствующие ациклическим и циклическим элементарным программам. Для доказательства правильности программ используются трассировочные таблицы и разделяющиеся условные правила. Теоретико-функциональный подход к верификации иллюстрируется несколькими примерами. Еще один способ доказательства правильности циклических программ основан на использовании инвариантов цикла. Инварианты применяются также в качестве вспомогательного средства документирования программ. Для определения инвариантов дана общая процедура, основанная на теореме об инварианте. Наконец, с целью углубления в процесс проектирования программ приводится метод вывода правильных программ, использующий функциональные уравнения элементарных программ, для которых существуют формальные решения. [17]
Системы автоматического программирования решают задачи подготовки программ для ЭВМ. Эти задачи тесно связаны с задачей доказательства теорем. Поиск доказательства ( или опровержения) некоторой математической теоремы рассматривается как пример интеллектуальной задачи. Не только потому, что для этого требуется способность произвести дедукцию исходя из гипотез, но и потому, что необходимы интуитивные навыки, такие, как построение догадки о том, какие промежуточные леммы следует доказать, чтобы способствовать доказательству основной теоремы. [18]
Правильность программы определяется как соответствие между программой и ее заданной функцией. Для сведения задачи доказательства правильности определенной составной программы к задаче доказательства правильности определенных элементарных составляющих программ привлекают алгебраические понятия. Верификация правильности программ без циклов осуществляется с помощью анализа соответствующих Е - схем. Лемма о переходе от итеративных программ к рекурсивным позволяет свести задачу верификации циклических программ к задаче верификации эквивалентных программ без циклов. В теореме правильности обобщены требования к верификации, соответствующие ациклическим и циклическим элементарным программам. Для доказательства правильности программ используются трассировочные таблицы и разделяющиеся условные правила. Теоретико-функциональный подход к верификации иллюстрируется несколькими примерами. Еще один способ доказательства правильности циклических программ основан на использовании инвариантов цикла. Инварианты применяются также в качестве вспомогательного средства документирования программ. Для определения инвариантов дана общая процедура, основанная на теореме об инварианте. Наконец, с целью углубления в процесс проектирования программ приводится метод вывода правильных программ, использующий функциональные уравнения элементарных программ, для которых существуют формальные решения. [19]
Для этого мы должны были бы показать, что если формула 2 истинна, а из по нашим правилам выводима формула §, то §; тоже истинна. Если в качестве 2 взять какую-нибудь истинную формулу, например 0 0, то дело сведется к тому, чтобы показать, что каждая выводимая по нашим правилам формула является истинной. Но в этом как раз и заключается наша задача доказательства непротиворечивости. [20]
Программа, записанная на любом из языков программирования, называется исходным модулем или исходной программой. Программы в объектном коде не являются еще машинными программами. Они не предназначаются для непосредственного выполнения, так как кроме текста программы содержат дополнительную информацию, позволяющую организовывать связи между отдельными частями программы. То, что здесь подразумевается под автоматическим программированием, можно описать как суперкомпилятор, или программу, способную воспринимать описание на понятном нам языке того, что требуется от искомой программы. Задача автоматического написания программы для достижения заданного результата тесно связана с задачей доказательства того, что программа достигает этого результата. Последняя задача называется задачей верификации программы. [21]
В проблеме изоморфизма графов мы хотим знать, изоморфен ли граф подграфу другого графа. Эта проблема не только представляет математический интерес, эта проблема практическая. Например, структура органического соединения может быть описана графом. Следовательно, проверка того, является ли подструктура структуры некоторого органического соединения структурой другого органического соединения, есть проблема изомор физма. Таким образом, задача может быть сформулирована как задача доказательства того, что формула, представляющая граф, следует из формулы, представляющей другой граф. [22]