Частичные функции и схемы

Частичной функцией называется функция, определённая не на всех наборах своих переменных.

Простой импликантой частичной функции f называется элементарная конъюнкция К, для которой выполняются условия:

1) ∃_αК(α) = 1, f(а) = 1;

2) ∀_β f(B) = 0 → K(B) = 0;

3) если из импликанты К удалить любую букву, получится формула К' такая, что ∃_γК'(γ) = 1, f(γ) = 0.

Доопределением частичной функции f будем называть всюду определённую функцию g, значения которой совпадают со зна чениями функции f на тех наборах, на которых функция f определена.

Критерий существования декомпозиции заданного вида:

Частичная функция f представляется в виде f(u,v,w) = g(u,w,h(u,v)) тогда и только тогда для каждого фиксированного набора а значений переменных из множества и таблица функции f_α(v,w) допускает доопределение до таблицы, со держащей столбцы не более двух различных типов.

Контактной схемой называется неориентированный граф, каждому ребру (контакту) которого приписан символ перемен- ной в некоторой степени и выделены две вершины, которые на- зываются полюсами.

Частная производная булевой функции f(x₁ , x₂ ,..., x_n) по пременной X_i определяется так:

fx_i = f(x₁, ...,x_i-1, 0, x_i+1, ..., x_n) + f(x₁, ...,x_i-1, 1, x_i+1, ..., x_n).

Тестом относительно множества G = {g_i} попарно различных булевых функций называется множество наборов значений переменных Т такое, что ∀_i∀_k≠i∃_i∈T(g_i(e) ≠ g_k(e)).

 

Задание 2.6.1

1. Реализовать частичную функцию f(x,y,z,w) формулами над базисом конъюнкция, дизъюнкция, отрицание четырьмя спо- собами:

а) методом Квайна;

б) исходя из минимальной ДНФ, найден- ной с помощью карт Карнау;

в) исходя из минимальной КНФ, найденной с помощью карт Карнау;

г) методом последовательно- го разложения по переменным xyzw.

2. Для простейшего представления построить схему из функ- циональных элементов типа конъюнкция, дизъюнкция, отри- цание.

3. Реализовать простейшее представление контактной схемой.

4. Проверить возможность разделительной декомпозиции функции f(x,y,z,w) в виде g(u,v,h(p,t)), где u,v,p,t —некоторая перестановка переменных xyzw. Если декомпозиция указанного вида возможна, реализовать её схемой с ветвлениями из функциональных элементов типа конъ- юнкция, дизъюнкция, отрицание. Указать сложность построен- ной схемы.

Таблица 2.6.1

№	f(x,y,z,w)		№	f(x,y,z,w)
1	--011-11-0--011-		11	-1-0-0111--1-011
2	1--10-0-010--01-		12	11--01-0-01-011-
3	-0-1-001--1110-1		13	1--101-1--1000-1
4	11--0-11-1-1-100		14	-010-1-001-1-1-0
5	--100-11--01-101		15	0-0-11-1-1101--1
6	1--101---100-110		16	1--01-11-0-0110-
7	0-110-1010--1-1-		17	0--01-1-11101-11
8	10-1-10010--10--		18	11---0-1-0100-10
9	-10-101--1-011-0		19	0-111--10-1-00-1
10	1--0-110-1-011-0		20	1-10---011-0011-
21	01-1-10-011--01-		26	-0-0-1111-0-00-1
22	--1-01-000-1111-		27	11-00-10--0-00-1
23	0-1--1-00-11-001		28	--011-11-0-0-001
24	-10--0111-10--01		29	10---0111--011-1
25	1--01-1--1010-10		30	-1-10-110-1-101-

Пример решения задания 2.6.1 Решим задание 2.6.1 для функции f(x,y,z,w) = (-10101---- 0-11-0). Запишем таблицу функции f в виде карты Карнау (табл. 2.6.1а). Для отыскания сокращённой ДНФ выпишем в список М0 все нулевые наборы функции, а в М1 — единичные наборы (табл. 2.6.1b). Будем перебирать все единичные наборы из списка М1 который запишем в виде первого столбца. Для каждого из единичных наборов будем заменять последовательно его символы на неопределённый символ "-" и смотреть, не будет ли совпадать с точностью до неопределённого символа полученная комбинация с каким-либо набором, вошедшим в список М0. Если совпадение есть, переходим к следующему символу, а если нет — помечаем набор "крестиком", выписываем результат замены во второй столбец и переходим к следующему символу или к следующему набору.

Затем совершаем аналогичную процедуру над наборами из второго столбца и так далее. В результате наборы, не помеченные крестиком, будут соответствовать простым импликантам, из которых состоит сокращенная ДНФ (табл. 2.6.1с). Итак, простые импликанты нашей функции таковы: xyw, yz, xw , zw , yw, xz. а) Изобразим матрицу Квайна (табл. 2.6.Id), в которой строки соответствуют единичным наборам функции, а столбцы простым импликантам.

Как видим, ядровых импликант нет. Для нахождения минимальной ДНФ составим символическую КНФ, каждая элемен- тарная дизъюнкция которой соответствует единичному набору нашей функции, которую преобразуем затем в ДНФ. Получим:

(2∨3∨4∨5)-(3∨5)-(3∨4)-(1∨6)-(4∨6) = (3∨5⋅4)>(6∨1⋅4) = = 3⋅6∨5⋅4⋅6∨3⋅1⋅4∨5⋅1⋅4.

Видим, что наименьшую длину имеет символическая конъюнкция 3⋅6, которая соответствует минимальной ДНФ xw ∨ xz.

Сложность найденной минимальной ДНФ равна 4.

б) При нахождении минимальной ДНФ с помощью карты Карнау (табл. 2.6.1е), мы доопределяем функцию f так, чтобы покрытие имело более простой вид.

Тогда все единицы покроются двумя квадратами 2x2 xw и xz, соответствующая минимальная ДНФ совпадает с ДНФ, найденной в п. а).

в) Для отыскания минимальной КНФ покрываем нули карты Карнау (табл. 2.6.1f) двумя квадратами 2x2: x ∨ w и x ∨ z .

Соответствующая минимальная КНФ такова: (х ∨ w) ⋅ (x ∨ z).

Сложность её равна 4.

г) Проведём разложение по набору переменных xyzw. На первом этапе, раскладывая по переменной х, имеем:

f(x, у, z, w) = x ⋅ f(0, у, z,w) ∨ x ⋅ f(1, у, z, w).

Изобразим таблицы функций f(0,y,z,w) и f(1,y,z,w) (табл. 2.6. 1g).

Каждая из функций f(0,y,z,w) и f(1,y,z,w) не доопределима до константы, но f(1,y,z,w) доопределима до z. Изобразим таблицы (табл. 2.6.1h) функций f(0,0,z,w) и f(0,1,z,w).

Видим, что f(0,0,z,w) и f(0,1,z,w) доопределимы до w и 1 соответственно. Получаем разложение исходной функции: f(x, у, z, w) = x⋅ (y ⋅ w v у ⋅ 1) v х⋅ z = x ⋅ (w v у) v х⋅ z . Во время упрощений мы применяли тождества с константами и правило вычёркивания. Сложность полученной формулы оказалась равной 5. 2) В качестве простейшего представления возьмём минимальную ДНФ xw v xz и реализуем её схемой из функциональных элементов (рис. 2.6.1, а). Реализуем ту же минимальную ДНФ контактной схемой (рис. 2.6.1, b). 3) Реализуем ту же минимальную ДНФ контактной схемой (рис. 2.61, b). 4) Запишем двумерную таблицу функции f (табл. 2.6.1i). Видим, что таблица допускает доопределение до строк только двух типов (табл. 2.6.1 j).

Значит, f(x,y,z,w) допускает разделительную декомпозицию вида f(x,y,z,w) = g(z,w,h(x,y)).

Найдём вид функций g и h.

т.е. h(x,y) = (1110), h(x,y) = x   y.

Строкам I типа соответствует функция φ(z, w) = (0101) = w.

Строкам II типа соответствует функция Ψ(z, w) = (1101) = z.

Тогда функция f выражается через h, φ, Ψ так:

f(x, y, z, w) = h(x, у) ⋅ φ(z, w) v h(x, y) ⋅ Ψ(z, w) = = (x v y) ⋅ w v (x v y) ⋅ z.

Соответствующая схема из функциональных элементов с ветвлениями будет иметь вид (рис. 2.6.1, с).

Сложность схемы равна количеству функциональных элементов, её образующих, т. е. 8.

 

Задание 2.6.2

1. Представить функцию f(x₁,x₂,x₃,x₄,x₅) декомпозицией вида g(x_i,x_k,x_p,h(x_i,x_m,x_n)), где x_ix_kx_px_ix_mx_n —некоторая перестановка переменных x₁,x₂,x₃,x₄,x₅.

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

3. Построить минимальную ДНФ с помощью карт Карнау, указать сложность найденной формулы.

Таблица 2.6.2

№	i	f(x1,x2,x3,x4,x5)
1	1	1-01	1101	10--	1-0-	1-1-	111-	000-	-011
2	2	1-1-	00-0	-001	-001	--0-	11-0	01-1	0-01
3	3	110-	01-0	1-11	0-00	1-11	011-	111-	011-
4	4	-011	-000	-111	-000	1-10	100-	11-0	-001
5	5	0-10	-000	10-0	01-1	0010	-11-	--11	-11-
6	1	-001	--01	1-01	-101	--11	1--1	00-0	001-
7	2	-11-	0-00	0--1	-00-	00-0	-10-	-101	-10-
8	3	-1-0	010-	11--	01-0	11--	0110	--11	0110
9	4	0-1-	00--	01-1	0-00	10--	10-1	1-1-	100-
10	5	-010	-00-	-1--	0101	-01-	0-11	-1-1	1--1
11	1	10--	11-1	-001	1-01	-1-1	11-1	0-0-	0-11
12	2	--11	00-0	-001	0001	--00	1-00	010-	-101
13	3	1-00	-100	1-11	01-0	1-1-	011-	1--1	0-10
14	4	--11	00-0	011-	-00-	1010	-001	-110	-0-1
15	5	00-0	00-0	1010	0-01	0-10	-111	1-11	--1-
16	1	-00-	1-01	-0-1	110-	111-	11-1	000-	0--1
17	2	111-	00-0	0-0-	000-	000-	1-00	-101	0-0-
18	3	-10-	01-0	1-11	0-00	1-11	--10	111-	0110
19	4	001-	-000	-111	00-0	101-	1001	1-1-	1001
20	5	0-1-	000-	101-	01-1	00-0	01-1	11-1	111-
21	1	10-1	110-	1-01	-101	-111	-11-	0-00	0011
22	2	-1-1	0-0-	-0--	0001	-0-0	1100	-1-1	0101
23	3	1100	-10-	-111	010-	-1-1	0-10	1-11	-1-0
24	4	0-11	-000	0-11	0-00	1-10	10-1	111-	10-1
25	5	-01-	0-00	-0-0	0-01	-01-	0--1	1-11	1-11
26	1	1001	11-1	1-01	--0-	1-11	1-1-	0-00	0-1-
27	2	111-	0-00	0-01	0-01	00--	110-	0101	01-1
28	3	-100	01--	1111	010-	1-1-	01-0	1111	0-10
29	4	001-	0000	01-1	00-0	10-1	1001	--1-	10-1
30	5	0-10	00--	101-	01-1	001-	0111	-1-1	111-

 

Пример решения задания 2.6.2

Решим задание 2.6.2 для i = 5 и функции

f(x₁,x₂,x₃,x₄,x₅) = (10-10--0 --01 -1-- 0-10 010- 1--0 --1-).

Выпишем значения функции f в виде таблицы (табл. 2.6.2а):

Выясним, возможна ли декомпозиция вида

f = g(x₅,x₁,x₂,h(x₅,x₃,x₄))     (*)

или

f = g(x₅,x₃,x₄,h(x₅,x₁,x₂)).     (**)

Для этого выпишем двумерные таблицы функции f для х₅ = 0 и x₅ = 1 так, чтобы в заголовках строк и столбцов были написаны наборы х₁х₂ и х₃х₄ соответственно. Получим (табл. 2.6.2b).

Как видим, таблица функции f, соответствующая х₅ = 0, не доопределима так, чтобы использовались столбцы только двух типов, и не доопределима до вида, в котором используются строки только двух типов. Значит, декомпозиция вида (*) или (**) невозможна.

Проверим, допустима ли декомпозиция вида

f = g(x₅,x₂,x₃,h(x₅,x₁,x₄)) или f = g(x₅,x₁,x₄,h(x₅,x₂,x₃)).

Для этого выпишем двумерные таблицы функции f для х₅ = 0 и х₅ = 1 так, чтобы в заголовках строк и столбцов были написаны наборы х₂х₃ и х₁х₄ соответственно. Получим (табл. 2.6.2с).

Видим, что в этом случае обе таблицы допускают доопределение до столбцов двух типов.

Для х₅ = 0 столбцам I типа соответствует функция

φ⁽⁰⁾(x₂,x₃) = (1001) = x₂, x₃ ∨ x₂,x₃, а столбцу II типа — функция Ψ⁽⁰⁾(x₂,x₃) = (0101) = x₂.

Введём функцию

Вектор значений h⁽⁰⁾(x₁,x₄) равен (1101), значит.

h⁽⁰⁾(x₁,x₄) = x₁,x₄

f(x₁,x₂,x₃,x₄,0) = h⁽⁰⁾(x₁,x₄) ⋅ φ⁽⁰⁾(x₂,x₃) ∨ h⁽⁰⁾(x₁,x₄) ⋅ Ψ⁽⁰⁾(x₂,x₃) =

= (x₁,x₄)(x₂,x₃ ∨ x₁ ∨ x₄⋅ x₂

Рассмотрим таблицу, соответствующую х₅ = 1.

Столбцам I типа соответствует функция

φ⁽¹⁾(x₂,x₃) = (0101) = хx₃, столбцам II типа — функция

Ψ⁽¹⁾(x₂,x₃) = (1110) = x₂ ∨ x₃.

Введём функцию

Вектор значений h⁽¹⁾(x₁,x₄) равен (1001), значит,

h⁽¹⁾(x₁,x₄) = x₁,x₄ ∨ x₁,x₄.

f(x₁,x₂,x₃,x₄,1) = h⁽¹⁾(x₁,x₄) ⋅ φ⁽¹⁾(x₂,x₃) ∨ h⁽¹⁾(x₁,x₄) ⋅ Ψ⁽¹⁾(x₂,x₃) =

=(x₁,x₄ ∨ x₁,x₄)x₃ ∨ x₁,x₄ ∨ x₁,x₄ ⋅ x₂ ∨ x₃.

Получаем искомое представление для f:

f(x₁,x₂,x₃,x₄,x₅) =x₅ ⋅ f(x₁,x₂,x₃,x₄,0) ∨ x₅ ⋅ f(x₁,x₂,x₃,x₄,1)

= x₅((x₁ ∨ x₄)(x₂x₃ ∨ x₂,x₃) ∨ x₁ ∨ x₄ ⋅ x₂) ∨ x₅((x₁x₄ ∨ x₁x₄)x₃ ∨ x₁,x₄ ∨ x₁,x₄ ⋅(x₂ ∨ x₃)).

2. Реализуем это представление схемой с ветвлениями.

Ввиду громоздкости полученного выражения реализуем схемами S₀ (рис. 2.6.2, а) и S₁ (рис. 2.6.2, b) соответственно f(x₁,x₂,x₃,x₄,0) иf(x₁,x₂,x₃,x₄,1), а саму функцию реализуем блок-схемой S (рис. 2.6.2, с).

Сложность построенной схемы равна 24.

3. Найдём минимальную ДНф с помощью карты Карнау (табл. 2.6.2d). Все единицы карты Карнау могут быть покрыты двумя двухслойными прямоугольниками и тремя однослойными. Минимальная ДНФ будет иметь вид: x3 ⋅ x5 ∨ x2 ⋅ x3 ⋅ x4 ⋅ x5 ∨ x1 ⋅ x2 ⋅ x3 ⋅ x5 ∨ x1 ⋅ x4 ⋅ x5 ∨ x1 ⋅ x2 ⋅ x5 Её сложность равна 16.

 

Задание 2.6.3

1. С помощью частных производных найти оптимальный для метода каскадов порядок дизъюнктивного разложения функции f(x,y,z,w) по её переменным на первых двух этапах.

2. Используя результаты п. 1, построить контактную схему методом каскадов, указать сложность построенной контактной схемы.

Таблица 2.6.3

№	f(x,y,z,w)		№	f(x,y,z,w)
1	1110 0110 1010 1101		16	0111 0101 1101 1111
2	0011 1100 1101 0111		17	0010 1011 1101 1110
3	0110 1101 1100 1111		18	0011 1110 1101 0000
4	1110 0111 1100 0111		19	0101 1010 1111 1101
5	0010 1110 1111 0011		20	0101 1101 1110 0011
6	1110 1101 0010 1111		21	0010 1101 1001 0110
7	1110 1010 0010 0110		22	1110 1101 0101 1010
8	1110 1000 1111 0110		23	0010 1010 1110 1111
9	1101 0110 1110 0001		24	0110 1001 1100 1101
10	1011 0111 1010 0110		25	0010 0000 1000 1110
11	1101 0001 0010 1111		26	0010 1010 0001 1111
12	1110 0100 1110 1001		27	0101 1101 0000 1011
13	0001 1000 1100 0110		28	1101 1000 0110 1110
14	1101 1111 0010 1101		29	1000 0110 0101 1001
15	1001 1101 0011 1000		30	1101 0111 1101 0011

Пример решения задания 2.6.3 Решим задание 2.6.3 для функции f(x, у, z, w) = = (1010 0100 0100 1010). Запишем таблицу функции f(x,y,z,w) в виде карты Карнау (табл. 2.6.3а).

Найдём полином Жегалкина:

Определим оптимальный для метода каскадов порядок разложения. По определению, fx(x,y,z,w) = f(0,y,z,w) + f(1,y,z,w). Таблица для fx имеет вид (табл. 2.6.3b). Видим, что | fx |= 6. Аналогично, fy(x,y,z,w) = f(x,0,z,w) + f(x,1,z,w). Таблица для fy имеет вид (табл. 2.6.3с). Видно, что | fy |= 6. Продолжаем отыскание частных производных. fy (x,y,z,w) = f(x, у,0, w) + f(x,y,1, w). Таблица для fz, имеет вид (Табл. 2.6.3d). Заметим, что | fz |= 2. И далее, fw(x,y,z,w) = f(x, у, z,0) + f(x, у, z,1). Таблица для fw имеет вид (табл. 2.6.3е).

Как видно, | f_w |= 6.

Так как набольшее число единиц в таблице имеют f_x, f_y и f_w, то на 1 и 2 этапах метода каскадов разложение ведём по любой из переменных x,y,w. Выберем, например, в качестве первой переменной, по которой будем проводить разложение, х, а второй — w.

Получим: f(x,y,z,w) = x ⋅ f(0,y,z,w) ∨ х ⋅ f(1,y,z,w).

Выпишем таблицы функций f(0,y,z,w) и f(1,y,z,w) (табл. 2.6.3f).

3. Строим контактную схему методом каскадов (рис. 2.6.3, а). На втором этапе разложение ведём по переменной w.

f₀(y,z,w) = w ⋅ f₀(y,z,0) ∨ w ⋅ f₀(y,z,1) =

= w ⋅ (1 + y + 0 +0) ∨ w ⋅ (1 + y + 1 +yz) =

= w ⋅ (1 + y) ∨ w ⋅ (y + yz) = w ⋅ y ∨ w ⋅ y ⋅ (1 + z) = w ⋅ y ∨ w ⋅ y ⋅ z.

f₁(y,z,w) = w ⋅ f₁(y,z,0) ∨ w ⋅ f₁(y,z,1) =

= w ⋅ (y + 0) ∨ w ⋅ (y+1+z+yz) = w ⋅ y ∨ w ⋅ f₁₁(y,z).

Осталось разложить функцию f₁₁(y,z)

f₁₁(y,z) = z ⋅ f₁₁(y,0) ∨ z ⋅ f₁₁(y,1) = z ⋅ (y+1) ∨ z ⋅ (y+1+1+y) =

z ⋅ y ∨ z ⋅ 0 = z ⋅ y.

Изобразим полученную контактную схему (рис. 2.6.3, b).

Сложность построенной схемы равна количеству контактов в ней, т. е. 8.

 

Задание 2.6.4

Для функции f(x,y,z,t), заданной своей ДНФ:

1. Построить таблицу данной булевой функции.
2. Найти минимальную ДНФ. Исходя из минимальной ДНФ, построить контактную схему.
3. Построить контактную схему методом каскадов, отыскав оптимальный порядок разложения переменных с помощью частных производных.
4. Исходя из простейшей контактной схемы, построить минимальный тест для нахождения неисправности:
   а) для вариантов с чётными номерами — типа замыкания ровно одного контакта
   б) для вариантов с нечётными номерами —типа размыкания ровно одного контакта.

Таблица 2.6.4

№	f(x,y,z,t)		№	f(x,y,z,t)
1	xyz ∨ xyz ∨ xyzt ∨ yzt		4	xyzt ∨ xzt ∨ xyzt
2	xyzt ∨ xzt ∨ xyzt ∨ xzt ∨ yz		5	xyzt ∨ xyzt ∨ xzt
3	xyzt ∨ xyzt ∨ xyzt ∨ xzt		6	xzt ∨ xyzt ∨ yzt
7	xyzt ∨ xyt ∨ xyzt ∨ xyt zt		19	xyz ∨ yzt ∨ xyzt
8	xyz ∨ xyt ∨ xyzt		20	xyzt ∨ xyzt ∨ xyzt ∨ yzt
9	xyzt ∨ xyzt ∨ xyt		21	xyt ∨ xyt ∨ xyzt yzt
10	xyzt ∨ xyzt ∨ xyzt ∨ xyt		22	xyzt ∨ xzt ∨ xyzt yzt
11	xzt ∨ xyt ∨ xzt ∨ xyzt		23	xyzt ∨ xyz ∨ xyzt
12	xyzt ∨ xyz ∨ xyzt ∨ xyz ∨ xt		24	xyzt ∨ xyzt ∨ yzt
13	xyzt ∨ xyz ∨ xyzt		25	xyzt ∨ xyzt ∨ xyzt ∨ yzt
14	xyzt ∨ xyzt ∨ xyz		26	xzt ∨ xzt ∨ xyzt ∨ yzt
15	xyzt ∨ xyzt ∨ xyz ∨ xyzt		27	xyzt ∨ xyt ∨ xyzt ∨ xyt ∨ yz
16	xyt ∨ xyz ∨ xyzt xyt		28	xyzt ∨ yzt ∨ xyzt
17	xyzt ∨ yzt ∨ xyzt ∨ xyz ∨ xy		29	xyzt ∨ xyzt ∨ xzt
18	xyzt ∨ yzt ∨ xyzt		30	xyzt ∨ xyzt ∨ xyzt ∨ xyz

Пример решения задания 2.6.4 Решим задание 2.6.4 для f(x,y,z,t) = x yzt ∨ xy ∨ xyt ∨ xzt, выбрав в п. 4 неисправность типа размыкания ровно одного кон- такта. 1. Построим таблицу функции f{x,y,z,t) в виде карты Карнау (табл. 2.6.4а). 2. Все единицы карты Карнау покрываем тремя прямоугольниками. Соответствующая минимальная ДНФ будет иметь вид yzt v xtv xz. Упростим формулу: yzt ∨ xt ∨ xz = yzt ∨ x(t ∨ z). Реализуем это представление контактной схемой (рис. 2.6.4, а). 3. При отыскании оптимального порядка разложения по методу каскадов заметим, что | fx | = 6,| fy | = 2, | fz | = 2, | ft | = 2.

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

Получаем:

f(x, у, z, t) = x ⋅ f(0, у, z, t) ∨ x ⋅ f(1, у, z,t) =

= x ⋅ (yzt) ∨ х ⋅ (y ∨ ytv zt) =

= хyzt ∨ х ⋅ (у ∨ t ∨ zt) = xyzt ∨ x ⋅ (y ∨ t ∨ z).

Разложение по у нет необходимости делать.

Строим контактную схему (рис. 2.6.4, b).

4. Так как контактная схема, полученная в п. 2, имеет более простой вид, будем работать с ней.

Занумеруем все контакты схемы (рис. 2.6.4, с).

Неисправность типа размыкания контакта означает, что при любых значениях аргументов соответствующий контакт разомкнут, т. е. реализует функцию 0. Разомкнутый контакт будем изображать пунктирной линией, а. замкнутый — сплошной. Для каждого из единичных наборов функции на соответствующем изображении контактной схемы полюсы соединены цепью контактов из сплошных линий. На каждом же из нулевых наборов функции такой цепи не найдётся.

Пусть f₀(x,y,z,t) = f(x,y,z,t), а при неисправности i-го контакта схема реализует функцию f_i(x, у, z,t).

Если исправно работающая контактная схема на некотором наборе аргументов принимает значение 0, значит, на её изображении между полюсами нет цепи из сплошных линий. Ясно, что при наличии неисправности типа размыкания контакта на том же наборе аргументов полюсы контактной схемы тем более не соединены цепью из сплошных линий. Значит, на всех нулевых наборах функции f(x,y,z,t) все функции f_i(x,y,z,t), i = 1,2,...,6 также принимают значение, равное 0.

При построении теста нас не интересуют наборы аргументов, на которых значения всех функций совпадают, поэтому напишем таблицу всех функций fi(x,y,z,t), i = 1,2,...,6, вписывая в неё только те наборы аргументов, на которых исходная функция равна 1. При заполнении таблицы для каждого набора аргументов изобразим схему. Например, для набора (0,0,1,0) схема примет вид (рис. 2.6.4, d).

Видим, что цепь из сплошных линий, соединяющая полюсы схемы, разрывается, если разомкнут 4, 5 или 6 контакт, т. е. на наборе (0,0,1,0) значение 0 принимают функции f₄, f₅ и f₆. Изобразим вид контактной схемы на всех единичных наборах функции f(x,y,z,t) (рис. 2.6.4, е).

Заполняем "таблицу неисправностей", вписывая для каждого набора аргументов нули в столбцы, соответствующие функциям с номерами, записанными в кружочках. Получим следующую таблицу (табл. 2.6.4b).

Таблица 2.6.4b

xyzt	f0	f1	f2	f3	f4	f5	f6
0100	1	1	1	1	0	0	0
1000	1	0	0	1	1	1	1
1001	1	0	1	1	1	1	1
1010	1	1	1	1	0	0	0
1011	1	0	1	0	1	1	1
1100	1	0	0	1	1	1	1
1101	1	0	1	1	1	1	1
1111	1	0	1	0	1	1	1

Видим, что некоторые столбцы таблицы совпадают. Это означает, что неисправности типа размыкания одного контакта неотличимы в случае разомкнутости 4, 5 или 6 контактов.

Объединяем неотличимые неисправности в классы неисправностей.

Получим 5 классов:

g₀ = {f₀}, g₁ = {f₁}, g₂ = {f₂}, g₃ = {f₃}, g₄ = {f₄, f₅, f₆}.

Строим таблицу классов неисправностей, таблицу, не содержащую одинаковых столбцов.

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

Получим (табл. 2.6.4с):

Выясним, какие из наборов 1-5 войдут в минимальный тест. Для этого выпишем все сочетания индексов {i,k} и для каждого сочетания укажем номера наборов, на которых отличаются функции gi и gk.

Упростим полученное выражение, применяя формулу поглощения.

Получим: К_T = 2⋅5⋅(1∨4).

С помощью дистрибутивного закона преобразуем это выражение в ДНФ, тогда каждой символической конъюнкции будет соответствовать минимальный тест. Имеем:

К_T = 2⋅5⋅(1∨4) = 2⋅5⋅1∨2⋅5⋅4

В качестве минимального теста можно взять, например, совокупность 1, 2 и 5 наборов, т. е. найден минимальный тест

T_min = { (0,1,0,0), (1,0,0,0), (1,1,1,1)}.

 

Задание 2.6.5

1. Построить таблицу значений функции, реализуемой данной контактной схемой.

2. Найти минимальную ДНФ с помощью карты Карнау, построить на её основе контактную схему, равносильную исходной.

Таблица 2.6.5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

Пример решения задания 2.6.5

Решим задание 2.6.5 для контактной схемы. Рассмотрим вид контактной схемы на всех 8 наборах переменных x,y,z, изображая разомкнутые контакты пунктирной линией, а замкнутые — сплошной. Рассмотрим набор (0,0,0). Видим, что в данном случае между полюсами нет маршрута, составленного из сплошных линий, значит, на этом наборе функция, реализованная данной схемой, равна нулю, f(0,0,0) = 0.

Рассмотрим изображение схемы на остальных наборах:

f(0,0,1) = 0
f(0,1,0) = 1
f(0,1,1) = 1
f(1,0,0) = 1
f(1,0,1) = 1
f(1,1,0) = 1
f(1,1,1) = 0
Запишем найденные значения функции f(x,y,z) в карту Карнау (табл. 2.6.5а). Минимальная ДНФ: ху ∨ xz ∨ ху. Преобразуем формулу: ху ∨ xz ∨ ху = = ху ∨ x(z ∨ y). Соответствующая контактная схема имеет вид: Задание выполнено.