Билет №12

1. Свойства элементарных функций алгебры логики.

1. Система контроля работы цифрового автомата.

1) Свойства элементарных функций алгебры логики.

Функция штрих Шеффера { / }.

Свойства функции штрих Шеффера х₁ / х₂ = = ₁ + ₂

• х / х = ( т.к. х / х = = )

• х / 1 =

• х / 0 = 1

• / 1 = х

• / 0 = 1

• х / = 1

• Коммутативность для двух переменных, т.е. х₁ / х₂ = х₂ / х₁

Очередность операций для функции штрих Шеффера с n переменными устанавливается с помощью скобок.

Свойства ассоциативности и дистрибутивности для функции штрих Шеффера не справедливы.

Функция стрелка Пирса = ₁ + ₂ = х₁ ↓ х₂

• х ↓ х = (т.к. х ↓ х = = )

• х ↓ 0 =

• х ↓ 1 = 0

• х ↓ = 0

• ↓ 1 = 0

• ↓ 0 = х

• х₁ ↓ х₂ = х₂ ↓ х₁ свойство коммутативности выполняется только для двух переменных.

Для установления приоритетов выполнения операции стрелка Пирса, обязательно должны использоваться скобки.

Для функции стрелка Пирса свойства ассоциативности и дистрибутивности несправедливы.

Функция сложение по модулю 2 (х₁ х₂).

х1	х2	х1 ⊕ х2	СДНФ
0	0	0
0	1	1	1 х2
1	0	1	х1 2
1	1	0

Через отрицание, конъюнкцию и дизъюнкцию функция сложения по модулю 2 выражается следующим образом:

х₁ ⊕ х₂ = х_{1 2} + ₁ х₂;

Функция сложения по модулю 2 обладает следующими свойствами:

• коммутативности х₁ ⊕ х₂ = х₂ ⊕ х₁

• ассоциативности х₁ ⊕ (х₂ ⊕ х₁) = (х₁ ⊕ х₂) ⊕ х₃

• дистрибутивности х₁ (х₂ ⊕ х₃) = х₁ х₂ ⊕ х₁ х₃

Для этой функции справедливы аксиомы

• х ⊕ х = 0

• х ⊕ 1 =

• х ⊕ = 1

• х ⊕ 0 = х

• х₁ ⊕ х₂ = ₁ ⊕ ₂

• х₁ ⊕ ₂ = х₁~ х₂

• ₁ ⊕ х₂ = х₁ ~ х₂

• = х₁ ~ х₂

На основании аксиом и свойств можно вывести правила перевода функций отрицание, конъюнкция, дизъюнкция через функцию сложения по модулю 2 и наоборот.

• ₁ = х₁ ⊕ 1;

• х₁ + х₂ = х₁ ⊕ х₂ ⊕ х₁ х₂

• х₁ х₂ = (х₁ ⊕ х₂) ⊕ (х₁ + х₂)

Функция равнозначности (х₁ ~ х₂) выражается через отрицание, конъюнкцию и дизъюнкцию следующим образом:

х1	х2	х1 ~ х2	СДНФ
0	0	1	1 2
0	1	0
1	0	0
1	1	1	х1 х2

х₁ ~ х₂ = х₁ х₂ + _{1 2}

Свойства функции равнозначности:

• х ~ х = 1

• х ~ 0 =

• х ~ 1 = х

• х ~ = 0

• х₁ ~ х₂ = ₁ ~ ₂

• х₁ ~ ₂ = х₁ ⊕ х₂

• ₁ ~ х₂ = х₁ х₂

• = х₁ ⊕ х₂

• Для двух переменных выполняется свойство коммутативности х₁ ~ х₂ = х₂ ~ х₁

Свойства ассоциативности и дистрибутивности для этой функции не выполняются.

Функция импликация (х₁ → х₂) выражается через отрицание и дизъюнкцию следующим образом:

х1	х2	х1 → х2	СКНФ
0	0	1
0	1	1
1	0	0	1 + х2
1	1	1

х₁ → х₂ = ₁ + х₂

Для функции импликации справедливы аксиомы:

• х → х = 1

• х → =

• х → 1 = 1

• 0 → х = 1

• х → 0 =

• 1 → =

• х₁ → х₂ = ₂ → ₁

• х₁ ∙ х₂ = ₂

• х₁ + х₂ = ₁ → х₂ = ₂ → х₁

Свойства коммутативности, ассоциативности и дистрибутивности для этой функции не справедливы.

Функция коимпликация ( ) выражается через отрицание и конъюнкцию следующим образом:

= х_{1 2}

Для функции коимпликации справедливы аксиомы:

• = 0

• = х

• = 0

• =

• = х

• = 0

• х₁ + х₂ =

• х₁ х₂ =

2) Система контроля работы цифрового автомата

Алгоритмы выполнения арифметических операций обеспечат правильный результат только в случае, если машина работает без нарушений. При возникновении какого-либо нарушения нормального функционирования результат будет неверным, однако пользователь об этом не узнает, если не будут предусмотрены меты для создания системы обнаружения возможной ошибки, а с другой стороны, должны быть проработаны меры, позволяющие исправить ошибки. Эти функции следует возложить на систему контроля работы цифрового автомата. Система контроля - совокупность методов и средств, обеспечивающих определение правильности работы автомата в целом или его отдельных узлов, а также автоматическое исправление ошибки. Ошибки в работе цифрового автомата могут быть вызваны либо выходом из строя какой-то детали, либо отклонением от нормы параметров (например, изменение напряжения питания) или воздействием внешних помех. Вызванные этими нарушениями ошибки могут принять постоянный или случайный характер. Постоянные ошибки легче обнаружить и выявить. Случайные ошибки, обусловленные кратковременными изменениями параметров, наиболее опасны и их труднее обнаружить.

Поэтому система контроля должна строится с таким расчетом, чтобы она позволяла обнаружить и по возможности исправить любые нарушения. При этом надо различать следующие виды ошибок результата:

• возникающие из-за погрешностей в исходных данных;

• обусловленные методическими погрешностями;

• появляющиеся из-за возникновения неисправностей в работе машины.

Первые два вида ошибок не являются объектом для работы системы контроля. Конечно, погрешности перевода или представления числовой информации в разрядной сетки автомата приведут к возникновению погрешности в результате решения задачи. Эту погрешность можно заранее рассчитать и, зная её максимальную величину, правильно выбрать длину разрядной сетки машины. Методические погрешности также учитываются предварительно.

Проверка правильности функционирования отдельных устройств машины и выявление неисправностей может осуществляться по двум направлениям:

• профилактический контроль, задача которого - предупреждение появления ошибок в работе;

• оперативный контроль, задача которого - проверка правильности выполнения машиной всех операций.

Решение всех задач контроля становится возможным только при наличии определенной избыточности. Избыточность может быть либо аппаратными (схемными) средствами, либо логическими или информационными средствами. К методам логического контроля можно отнести следующие приемы. В ЭВМ первого и второго поколений отсутствие системы оперативного контроля приводило к необходимости осуществления "двойного счета", когда каждая задача решалась дважды, и в случае совпадения ответов принималось решение о правильности функционирования ЭВМ.

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

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

Все рассмотренные примеры свидетельствуют о том, что такие методы контроля позволяют лишь зафиксировать факт появления ошибки, но не определяют место, где произошла эта ошибка. Для оперативного контроля ра-боты ЭВМ определение места, где произошла ошибка, т.е. решение задачи поиска неисправности, является весьма существенным вопросом.

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

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