8. Операции кубического исчисления пересечение, объединение и дополнение

Операции кубического исчисления определяют преобразования над выражениями в кубической (векторной форме) в алфавите {0, 1, X}. Основными теоретико-множественными операциями кубического исчисления являются пересечение, объединение и дополнение. Существует еще ряд специальных теоретико-множественных кубических операций, используемых в кубических методах минимизации булевых функций, для моделирования и построения тестов при описании примитивных элементов схем в кубическом виде, но они используются достаточно редко и не рассматриваются в данном курсе.

Операция пересечения () двух n-мерных векторов (кубов) А = (а₁,а₂, ... а_n) и B = (b₁,b₂, ... b_n), где n - количество разрядов вектора (координат куба), обозначается C = A  B, где C = (c₁,c₂, ... c_n), и определяется следующим образом:

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

Таблица 2.1 - Кубическая операция пересечения

Частным случаем операции пересечения является операция поглощения (). Часто в литературе эту операцию называют операцией принадлежности по аналогии с соответствующей теоретико-множественной операцией. Куб А поглощается кубом В (А принадлежит В) (А  В), если А Ç В = А. Если в поглощении участвуют одинаковые кубы, то результатом будет один из этих кубов.

Ниже приведены примеры выполнения операции пересечения C = A Ç B для различных операндов.

0X0X Ç X10X = 010X;

0X0X Ç 110X = Æ;

0X00 Ç 0X0X = 0X00 (поглощение, A Î B);

0X01 Ç 0X01 = 0X01 (A = B).

Операция объединения () двух n-мерных кубов А = (а₁,а₂, ... а_n) и B = (b₁,b₂, ... b_n), где n - количество координат куба, обозначается C = A  B, где C = (c₁,c₂, ... c_n), и определяется как C = ((a₁b₁), (a₂₂), ... (a_nb_n)). Кубическая операция объединения является покоординатной и правила ее выполнения в каждом разряде указаны в таблице в таблице 2.2. Ранг результата объединения С всегда больше или равен рангу большего из кубов, участвующих в объединении. Отметим, что для кубов с кодовым расстояним d больше или равным 2, результаты объединения могут быть противоречивыми.

Таблица 2.2 - Кубическая операция объединения

Частным случаем операции объединения является операция склеивания. Кубы одного ранга А и В склеиваются, если они различаются только в одном разряде i, причем a_i и b_i не равны X. Отметим, что именно операция склеивания никогда не дает противооречивых результатов.

Ниже приведены примеры выполнения операции объединения C = A È B для различных операндов.

0X0X È 0XX0 = 0XXX (d=2, результат противоречив, т.к. 0X11 A,B , но 0X11 Î0XXX);

0X0X È 0X01 = 0X0X (поглощение, B ÎA);

0X01 È 0X00 = 0X0X (d=1, склеивание);

0101 È 0110 = 01XX (d=2, результат противоречив).

Операция дополнения для одного n-мерного куба А = (а₁,а₂, ... а_n), где n - количество координат куба, обозначается C = Ā, где C = (c₁,c₂, ... c_n). По аналогии с аналитическим описанием логических функций операцию дополнения часто называют логической инверсией и правила ее выполнения в каждом разряде указаны в табл. 2.3. Отметим, что ранг дополнения С по отношению к исходному кубу А всегда остается неизменным.

Таблица 2.3 - Кубическая операция дополнения

Примеры выполнения

A = 0X0X, C = 1X1X;

A = 0110, C = 1001.