Свойства булевой производной

При решении уравнений (1) и (2) широко используются свойства булевой производной:

1. – не зависит от .

2. Решение уравнения g(x) = 1 определяет набор , при котором становится существенной переменной.

3. Решение уравнения g(x) = 0 определяет набор , при котором не влияет на выходную функцию f(x).

4. Если , то всегда является существенной.

5. Если , то f не зависит от .

6.

7.

Свойства 6 и 7 следуют из симметричности формулы (3) относительно и f.

8.

Следствие: если f₁ не зависит от x_j , то

9.

Следствие: если f₁ не зависит от x_j , то

10.

Следствие: если f₁ не зависит от x_j, то

11.

где k – промежуточная точка схемы такая, что пути от j к выходу идут через k.

12. Булевы производные функций, реализуемых типовыми элементами:

a) Для f = x₁x₂…x_j…x_n и f =

b) Для f = и f =

c) Для f = x и f =

d) Для

, j = .

Пример 1:

Найти наборы для обнаружения неисправностей на входе a схемы рис. 20.

Рисунок 20 – Схема к примеру 1

Для определения тестового набора неисправности а 0 надо решить уравнение

(4)

Решаем, используя свойства булевой производной:

,

(свойство 11),

Или сразу (следствие свойства 8).

Или сразу (по выражению 12,b).

Следовательно,

(5)

Для уравнения (4) получаем

или

В обоих произведениях отсутствует по одной переменной, поэтому для каждого из них будет по два решения – по два набора.

Следовательно, наборы для обнаружения неисправности а 0 будут такими

Объединяя 1) и 2), получаем

Любой из этих наборов обнаруживает неисправность а 0.

Для неисправности а 1 надо решить уравнение

.

Производную мы уже знаем (5), она равна , поэтому получаем

.

Следовательно, имеем два решения

В обоих произведениях отсутствует по одной переменной, поэтому для каждого из них будет по два решения – по два набора.

Или

Объединяя, получаем

Любой из этих наборов обнаруживает неисправность а 1.

Пример 2:

Найти наборы для обнаружения неисправностей на входах и выходах сумматора (рис. 21).

Рисунок 21 – Схема к примеру 2

Сумматор выполняет функции

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

Находим

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

Для проверки надо подать , а для проверки надо подать .

Минимальными тестами здесь являются пары инверсных наборов

000 – 111, 001 – 110, 011 – 100, 101 – 010,

которые проверяют не только входы, но и выходы сумматора, так как на одном из наборов пары каждый выход равен 1, а на другом 0. Поэтому строить тест для проверки выхода p нет необходимости.

Замечание: Для контроля работоспособности сумматора получен тест минимально возможной длины (два набора). Тест такой же длины получается и для элементов ИСКЛЮЧАЮЩЕЕ ИЛИ и РАВЕНСТВО с нечетным числом входов.

Вопросы для самоконтроля

1. Что такое константная неисправность 0? 1?

2. Что такое существенная входная переменная и как она получается для типовых логических элементов?

3. Что такое «булева производная»?

4. Какое уравнение надо решить, чтобы сделать входную переменную x_j существенной?

5. Какие уравнения надо решить, чтобы определить входные наборы для обнаружения неисправностей 0 и 1 на входе x_j?

6. Какое уравнение надо решить, чтобы переменная x_j не влияла на выходную функцию?

7. При каком значении булевой производной переменная x_j всегда существенна? Приведите пример логического элемента, у которого все входы всегда существенны.

8. При каком значении булевой производной выходная функция не зависит от переменной x_j?

9. Какими свойствами обладает булева производная?

10. Приведите выражения булевой производной для типовых логических элементов.

Примеры преобразований логических функций