Question

Эквивалентность логических схем(конспект)

Answer 1

Проблемы эквивалентности и распознавания принадлежности к некоторому классу алгоритмов в своей полной подстановке являются алгоритмически неразрешимыми проблемами. До сих пор их решали только для некоторых видов алгоритмических систем при довольно узком определении эквивалентности.Основные результаты относятся к операторным схемам.В качестве характерных черт операторных схем можно выделить следующие черты:-совокупность операторов, образующих схему алгоритма, изображается явно;-для каждого оператора явно указываются его приемники и предшественники по выполнению, а также его аргументы и результаты;-при построении реализации приемник оператора обычно выбирается без учета истории движения к этому оператору;-если в рассмотрение вовлекается некоторая величина, «вырабатывается» некоторым оператором, то она трактуется как независимая переменная, то есть считается, что после выполнения данного оператора она может принимать любое значение независимо от предыдущей истории;-если аргументом или результатом оператора оказывается компонента массива, указанная индексом, то значение индекса обычно игнорируется и считается, что аргументом и результатом оператора является весь массив.Первой работой, посвященной общей теории преобразования алгоритмов, явилась работа Ю.И. Янова «О логических схемах алгоритмов». В ней были сформулированы основные компоненты теории преобразования алгоритмов, а именно:-формализация понятия схемы алгоритма;-задание отношения эквивалентности;-определение алгоритма, распознающего эквивалентность схем;-построение системы преобразований, полной в том смысле, что любую пару эквивалентных алгоритмов можно трансформировать один в другой последовательным применением этих преобразований, сохраняющих эквивалентность.Всякий алгоритм при переработке конкретного объекта предписывает однозначно определенную последовательность элементарных действий. Такая последовательность, вообще говоря, различна для различных объектов, к которым данный алгоритм может быть применен. Однако всегда найдется конечное множество предикатов, характеризующих некоторые свойства перерабатываемых объектов, такое, что для данного алгоритма зависимость порядка выполнения элементарных действий от перерабатываемых объектов будет однозначной функцией этих предикатов.Такая функция может быть записана при помощи конечной строки, составленной из символов элементарных действий А1,A2,…,An( называемых операторами), предикатов и некоторых вспомогательных символов: [i ; i] (i=1.2….), называемых соответственно левой и правой полускобками.Строка А1А2А3…Аs означает, что последовательно должны быть выполнены операторы А1 ,А2, А3, …,Аs.Строка А1 р[iA2…i]A3 ,где р - некоторый предикат, означает, что после выполнения оператора А1 в случае р=1 должен быть выполнен оператор А2 ,стоящий непосредственно правее р[i, а если р=0, то оператор А3, стоящий справа от полускобки i].Строки такого вида называются схемными записями алгоритмов. Один и тот же алгоритм при фиксированном множестве элементарных операций и предикатов может иметь различные логические схемы.

Answer 2

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

Вот некоторые ключевые понятия и методы, связанные с определением эквивалентности логических схем:

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

2. Методы алгебры логики: Существуют различные методы алгебры логики, такие как алгебра Буля и метод Карно, которые позволяют упростить и анализировать логические выражения. Используя эти методы, можно преобразовать логические схемы в эквивалентные формы и сравнить их.

3. Доказательство эквивалентности: Для доказательства эквивалентности двух логических схем можно использовать различные методы. Например, можно применить метод прямого доказательства, показав, что выходные значения для каждой комбинации входных сигналов одной схемы совпадают с выходными значениями другой схемы. Также можно использовать метод доказательства от противного, предполагая, что схемы не эквивалентны, и доказывая противоречие.

4. Упрощение логических выражений: При сравнении логических схем можно применять методы упрощения логических выражений, чтобы сделать их более компактными и легкими для анализа. Например, можно использовать законы алгебры логики, такие как закон дистрибутивности или закон двойного отрицания, чтобы упростить выражения и сравнить их.

Определение эквивалентности логических схем является важным шагом в анализе и проектировании цифровых систем. При сравнении схем можно