Cтраница 4
Пусть плоские изображения А и В заданы своими кодами ( Мд, ТА) и ( Мв, TB) - Тривиальный способ проверки их на эквивалентность состоял бы в том, чтобы всеми возможными вариантами однозначно сопоставлять элементы множеств МА и MB и проверять при этом, как это следует из определения эквивалентности, равенство соответствующих элементов из множеств ТА и TQ. [46]
Определение эквивалентности, согласующейся с внутренним законом композиции, дано в задаче 1.11.) Закон композиции в группе G будет записываться аддитивно. [47]
Свойство 3 не требует доказательства. Из определения эквивалентности расширения следует, что оптимальное решение исходной задачи является одним из оптимальных решений эквивалентной расширенной задачи, а следовательно, удовлетворяет необходимым условиям ее оптимальности. Это свойство позволяет выразить необходимые условия оптимальности исходной задачи через необходимые условия оптимальности расширенной задачи, доказав предварительно эквивалентность расширения. [48]
По определению эквивалентности сущестствует биекция /: N - А. [49]
Липтон, Снайдер и Зальстейн сравнили основные модели параллельных вычислений, проделав работу, подобную выполненной в [5] и [240], но их результаты существенно отличны. Отличия проистекают из определения эквивалентности и включения. Это исследование более формально и более трудно для его развития, чем [5] или [240], но одинаково справедливо и интересно. [50]
Однако прежде чем ввести понятие об эквивалентности двух множеств векторов, мы в § 2 введем в рассмотрение две векторные характеристики - главный вектор и главный момент системы, - которые имеют смысл для любого множества векторов. Далее в § 3 дается определение эквивалентности систем векторов, и тем самым выделяется интересующий нас класс таких множеств. Наконец, в § 4 устанавливаются основные свойства множеств векторов выделенного класса. [51]
Однако в этом случае труднее обстоит дело с определением соответствующей эквивалентности. Действительно, требуется уточнить понятие состояния и останется еще трудность, связанная с необходимостью предвидеть все возможные состояния. В математической логике имеется еще один - синтаксический - подход к определению той же эквивалентности формул, не требующий обращения к состояниям. Он основан на подходящем логическом исчислении. В каждом таком исчислении имеется понятие формулы, некоторые формулы объявляются аксиомами исчисления, и указываются правила вывода. Тогда две формулы и ж v объявляются эквивалентными, если формула ( и-у) Д f ( v - - u) выводима из аксиом. Доказывается, что и и v тогда и только тогда эквивалентны в указанном сейчас синтаксическом смысле, когда они семантически эквивалентны. Доказательство этой теоремы основано на серьезной теории ( см. § 2 гл. [52]
Очевидно, чем слабее отношение эквивалентности, тем шире классу алгоритмов, эквивалентных согласно этому отношению. Естественным является стремление расширить классы эквивалентных алгоритмов, вводя более слабое определение эквивалентности. Однако при слишком слабом определении эквивалентности массовые проблемы, возникающие в теории алгоритмов, и среди них основная проблема распознавания эквивалентности алгоритмов, могут оказаться - неразрешимыми. С другой стороны, слишком сильное определение эквивалентности чрезмерно сужает классы эквивалентных алгоритмов. Правильный выбор понятия эквивалентности играет большую роль как с точки зрения возможности получения содержательных теорем, так и с точки зрения их практической применимости. [53]