Современные информационные технологии/1.Компьютерная инженерия

К.т.н. Ткаченко В.Г., аспирант Кокорев А.В.

                            Одесская национальная академия связи

Исследование монотонных булевых функций

 от четырех переменных

Рассмотрим некоторые понятия, связанные с методом классификации МБФ [1]  на типы [2]. Будем говорить, что две  МБФ от n переменных принадлежат одному типу, если соответствующие этим МБФ антицепи для любого i от 0 до n содержат одинаковое число наборов с i единицами. В этом случае для каждого i в минимальных дизъюнктивных формах [1] этих МБФ содержится одинаковое число конъюнкций, в которые входят i переменных. В [2] определен тип МБФ, как вектор Т = (a0, a1,…,ai,…,an) из n + 1-й компоненты, которые нумеруются слева направо от 0 до n, причем i-я компонента вектора ai равна числу входных наборов данной МБФ, содержащих по i  единиц. Число  n  называется рангом типа Т; число v ненулевых компонент – весом типа Т; номер i первой слева ненулевой компоненты – левой границей типа Т; номер j первой справа ненулевой компоненты – правой границей типа Т; сумма m всех компонент типа   Т – мощностью  типа  Т.  Тип Т называется максимальным, если при увеличении любой компоненты соответствующего ему вектора на 1, полученный вектор не соответствует никакому типу.

В нижеследующей таблице приведены все 168 МБФ ранга 4 в минимальной дизъюнктивной  форме. Здесь же приведены тип, левая граница i,  правая граница  j, вес v и мощность m каждой МБФ. Строки с МБФ максимального типа (29 строк) помечены знаком '+' в столбце тип МБФ. МБФ с номером 0, то есть  f0(4) это нулевая МБФ (равна 0 при всех значениях входных переменных), а f1(4) – единичная МБФ.

№

МБФ

Тип МБФ

Мин. дизъюнктивная  форма

i

j

v

m

0

(0,0,0,0,0)

0 конъюнкций

нет

нет

0

0

№

МБФ

Тип МБФ

Мин. дизъюнк-тивная  форма

i

j

v

m

1

(1,0,0,0,0)+

нет (един.МБФ)

0

0

1

1

2

(0,1,0,0,0)

x1

1

1

1

1

3

(0,1,0,0,0)

x2

1

1

1

1

4

(0,1,0,0,0)

x3

1

1

1

1

5

(0,1,0,0,0)

x4

1

1

1

1

6

(0,2,0,0,0)

x1x2

1

1

1

2

7

(0,2,0,0,0)

x1x3

1

1

1

2

8

(0,2,0,0,0)

x1x4

1

1

1

2

9

(0,2,0,0,0)

x2x3

1

1

1

2

10

(0,2,0,0,0)

x2x4

1

1

1

2

11

(0,2,0,0,0)

x3x4

1

1

1

2

12

(0,3,0,0,0)

x1x2x3

1

1

1

3

13

(0,3,0,0,0)

x1x2x4

1

1

1

3

14

(0,3,0,0,0) 

x1x3x4

1

1

1

3

15

(0,3,0,0,0)

x2x3x4

1

1

1

3

16

(0,4,0,0,0)+

x1x2x3x4

1

1

1

4

17

(0,0,1,0,0)

x1x2

2

2

1

1

18

(0,0,1,0,0)

x1x3

2

2

1

1

19

(0,0,1,0,0)

x1x4

2

2

1

1

20

(0,0,1,0,0)

x2x3

2

2

1

1

21

(0,0,1,0,0)

x2x4

2

2

1

1

22

(0,0,1,0,0)

x3x4

2

2

1

1

23

(0,0,2,0,0)

x1x2x1x3

2

2

1

2

24

(0,0,2,0,0)

x1x2x1x4

2

2

1

2

25

(0,0,2,0,0)

x1x2x2x3

2

2

1

2

26

(0,0,2,0,0)

x1x2x2x4

2

2

1

2

27

(0,0,2,0,0)

x1x2x3x4

2

2

1

2

28

(0,0,2,0,0)

x1x3x1x4

2

2

1

2

29

(0,0,2,0,0)

x1x3x2x3

2

2

1

2

30

(0,0,2,0,0)

x1x3x2x4

2

2

1

2

31

(0,0,2,0,0)

x1x3x3x4

2

2

1

2

32

(0,0,2,0,0)

x1x4x2x3

2

2

1

2

33

(0,0,2,0,0)

x1x4x2x4

2

2

1

2

34

(0,0,2,0,0)

x1x4x3x4

2

2

1

2

35

(0,0,2,0,0)

x2x3x2x4

2

2

1

2

36

(0,0,2,0,0)

x2x3x3x4

2

2

1

2

37

(0,0,2,0,0)

x2x4x3x4

2

2

1

2

38

(0,0,3,0,0)

x1x2x1x3x1x4

2

2

1

3

39

(0,0,3,0,0)

x1x2x1x3x2x3

2

2

1

3

40

(0,0,3,0,0)

x1x2x1x3x2x4

2

2

1

3

41

(0,0,3,0,0)

x1x2x1x3x3x4

2

2

1

3

№

МБФ

Тип МБФ

Мин. дизъюнк-тивная  форма

i

j

v

m

42

(0,0,3,0,0)

x1x2x1x4x2x3

2

2

1

3

43

(0,0,3,0,0)

x1x2x1x4x2x4

2

2

1

3

44

(0,0,3,0,0)

x1x2x1x4x3x4

2

2

1

3

45

(0,0,3,0,0)

x1x2x2x3x2x4

2

2

1

3

46

(0,0,3,0,0)

x1x2x2x3x3x4

2

2

1

3

47

(0,0,3,0,0)

x1x2x2x4x3x4

2

2

1

3

48

(0,0,3,0,0)

x1x3x1x4x2x3

2

2

1

3

49

(0,0,3,0,0)

x1x3x1x4x2x4

2

2

1

3

50

(0,0,3,0,0)

x1x3x1x4x3x4

2

2

1

3

51

(0,0,3,0,0)

x1x3x2x3x2x4

2

2

1

3

52

(0,0,3,0,0)

x1x3x2x3x3x4

2

2

1

3

53

(0,0,3,0,0)

x1x3x2x4x3x4

2

2

1

3

54

(0,0,3,0,0)

x1x4x2x3x2x4

2

2

1

3

55

(0,0,3,0,0)

x1x4x2x3x3x4

2

2

1

3

56

(0,0,3,0,0)

x1x4x2x4x3x4

2

2

1

3

57

(0,0,3,0,0)

x2x3x2x4x3x4

2

2

1

3

58

(0,0,4,0,0)

x1x2x1x3x1x4x2x3

2

2

1

4

59

(0,0,4,0,0)

x1x2x1x3x1x4x2x4

2

2

1

4

60

(0,0,4,0,0)

x1x2x1x3x1x4x3x4

2

2

1

4

61

(0,0,4,0,0)

x1x2x1x3x2x3x2x4

2

2

1

4

62

(0,0,4,0,0)

x1x2x1x3x2x3x3x4

2

2

1

4

63

(0,0,4,0,0)

x1x2x1x3x2x4x3x4

2

2

1

4

64

(0,0,4,0,0)

x1x2x1x4x2x3x2x4

2

2

1

4

65

(0,0,4,0,0)

x1x2x1x4x2x3x3x4

2

2

1

4

66

(0,0,4,0,0)

x1x2x1x4x2x4x3x4

2

2

1

4

67

(0,0,4,0,0)

x1x2x2x3x2x4x3x4

2

2

1

4

68

(0,0,4,0,0)

x1x3x1x4x2x3x2x4

2

2

1

4

69

(0,0,4,0,0)

x1x3x1x4x2x3x3x4

2

2

1

4

70

(0,0,4,0,0)

x1x3x1x4x2x4x3x4

2

2

1

4

71

(0,0,4,0,0)

x1x3x2x3x2x4x3x4

2

2

1

4

72

(0,0,4,0,0)

x1x4x2x3x2x4x3x4

2

2

1

4

73

(0,0,5,0,0)

x1x2x1x3x1x4x2x3x2x4

2

2

1

5

74

(0,0,5,0,0)

x1x2x1x3x1x4x2x3x3x4

2

2

1

5

75

(0,0,5,0,0)

x1x2x1x3x1x4x2x4x3x4

2

2

1

5

76

(0,0,5,0,0)

x1x2x1x3x2x3x2x4x3x4

2

2

1

5

77

(0,0,5,0,0)

x1x2x1x4x2x3x2x4x3x4

2

2

1

5

78

(0,0,5,0,0)

x1x3x1x4x2x3x2x4x3x4

2

2

1

5

79

(0,0,6,0,0)+

x1x2x1x3x1x4x2x3x2x4x3x4

2

2

1

6

80

(0,0,0,1,0)

x1x2x3

3

3

1

1

81

(0,0,0,1,0)

x1x2x4

3

3

1

1

82

(0,0,0,1,0)

x1x3x4

3

3

1

1

№

МБФ

Тип МБФ

Мин. дизъюнк-тивная  форма

i

j

v

m

83

(0,0,0,1,0)

x2x3x4

3

3

1

1

84

(0,0,0,2,0)

x1x2x3x1x2x4

3

3

1

2

85

(0,0,0,2,0)

x1x2x3x1x3x4

3

3

1

2

86

(0,0,0,2,0)

x1x2x3x2x3x4

3

3

1

2

87

(0,0,0,2,0)

x1x2x4 x1x3x4

3

3

1

2

88

(0,0,0,2,0)

x1x2x4 x2x3x4

3

3

1

2

89

(0,0,0,2,0)

x1x3x4x2x3x4

3

3

1

2

90

(0,0,0,3,0)

x1x2x3x1x2x4 x1x3x4

3

3

1

3

91

(0,0,0,3,0)

x1x2x3x1x2x4 x2x3x4

3

3

1

3

92

(0,0,0,3,0)

x1x2x3x1x3x4 x2x3x4

3

3

1

3

93

(0,0,0,3,0)

x1x2x4x1x3x4 x2x3x4

3

3

1

3

94

(0,0,0,4,0)+

x1x2x3x1x2x4 x1x3x4x2x3x4

3

3

1

4

95

(0,0,0,0,1)+

x1x2x3x4

4

4

1

1

96

(0,1,1,0,0)

x1x2x3

1

2

2

2

97

(0,1,1,0,0)

x1x2x4

1

2

2

2

98

(0,1,1,0,0)

x1x3x4

1

2

2

2

99

(0,1,1,0,0)

x2x1x3

1

2

2

2

100

(0,1,1,0,0)

x2x1x4

1

2

2

2

101

(0,1,1,0,0)

x2x3x4

1

2

2

2

102

(0,1,1,0,0)

x3x1x2

1

2

2

2

103

(0,1,1,0,0)

x3x1x4

1

2

2

2

104

(0,1,1,0,0)

x3x2x4

1

2

2

2

105

(0,1,1,0,0)

x4x1x2

1

2

2

2

106

(0,1,1,0,0)

x4x1x3

1

2

2

2

107

(0,1,1,0,0)

x4x2x3

1

2

2

2

108

(0,2,1,0,0)+

x1x2x3x4

1

2

2

3

109

(0,2,1,0,0)+

x1x3x2x4

1

2

2

3

110

(0,2,1,0,0)+

x1x4x2x3

1

2

2

3

111

(0,2,1,0,0)+

x2x3x1x4

1

2

2

3

112

(0,2,1,0,0)+

x2x4x1x3

1

2

2

3

113

(0,2,1,0,0)+

x3x4x1x2

1

2

2

3

114

(0,1,2,0,0)

x1x2x3x2x4

1

2

2

3

115

(0,1,2,0,0)

x1x2x3x3x4

1

2

2

3

116

(0,1,2,0,0)

x1x2x4x3x4

1

2

2

3

117

(0,1,2,0,0)

x2x1x3x1x4

1

2

2

3

118

(0,1,2,0,0)

x2x1x3x3x4

1

2

2

3

119

(0,1,2,0,0)

x2x1x4x3x4

1

2

2

3

120

(0,1,2,0,0)

x3x1x2x1x4

1

2

2

3

121

(0,1,2,0,0)

x3x1x2x2x4

1

2

2

3

122

(0,1,2,0,0)

x3x1x4x2x4

1

2

2

3

123

(0,1,2,0,0)

x4x1x2x1x3

1

2

2

3

№

МБФ

Тип МБФ

Мин. дизъюнк-тивная  форма

i

j

v

m

124

(0,1,2,0,0)

x4x1x2x2x3

1

2

2

3

125

(0,1,2,0,0)

x4x1x3x2x3

1

2

2

3

126

(0,1,3,0,0)+

x1x2x3x2x4x3x4

1

2

2

4

127

(0,1,3,0,0)+

x2x1x3x1x4x3x4

1

2

2

4

128

(0,1,3,0,0)+

x3x1x2x1x4x2x4

1

2

2

4

129

(0,1,3,0,0)+

x4x1x2x1x3x2x3

1

2

2

4

130

(0,0,1,1,0)

x1x2x1x3x4

2

3

2

2

131

(0,0,1,1,0)

x1x2x2x3x4

2

3

2

2

132

(0,0,1,1,0)

x1x3x1x2x4

2

3

2

2

133

(0,0,1,1,0)

x1x3x2x3x4

2

3

2

2

134

(0,0,1,1,0)

x1x4x1x2x3

2

3

2

2

135

(0,0,1,1,0)

x1x4x2x3x4

2

3

2

2

136

(0,0,1,1,0)

x2x3x1x2x4

2

3

2

2

137

(0,0,1,1,0)

x2x3x1x3x4

2

3

2

2

138

(0,0,1,1,0)

x2x4x1x2x3

2

3

2

2

139

(0,0,1,1,0)

x2x4x1x3x4

2

3

2

2

140

(0,0,1,1,0)

x3x4x1x2x3

2

3

2

2

141

(0,0,1,1,0)

x3x4x1x2x4

2

3

2

2

142

(0,0,2,1,0)

x1x2x1x3x2x3x4

2

3

2

3

143

(0,0,2,1,0)

x1x2x1x4x2x3x4

2

3

2

3

144

(0,0,2,1,0)

x1x2x2x3x1x3x4

2

3

2

3

145

(0,0,2,1,0)

x1x2x2x4x1x3x4

2

3

2

3

146

(0,0,2,1,0)

x1x3x1x4x2x3x4

2

3

2

3

147

(0,0,2,1,0)

x1x3x2x3x1x2x4

2

3

2

3

148

(0,0,2,1,0)

x1x3x3x4x1x2x4

2

3

2

3

149

(0,0,2,1,0)

x1x4x2x4x1x2x3

2

3

2

3

150

(0,0,2,1,0)

x1x4x3x4x1x2x3

2

3

2

3

151

(0,0,2,1,0)

x2x3x2x4x1x3x4

2

3

2

3

152

(0,0,2,1,0)

x2x3x3x4x1x2x4

2

3

2

3

153

(0,0,2,1,0)

x2x4x3x4x1x2x3

2

3

2

3

154

(0,0,3,1,0)+

x1x2x1x3x1x4 x2x3x4

2

3

2

4

155

(0,0,3,1,0)+

x1x2x2x3x2x4 x1x3x4

2

3

2

4

156

(0,0,3,1,0)+

x1x3x2x3x3x4 x1x2x4

2

3

2

4

157

(0,0,3,1,0)+

x1x4x2x4x3x4 x1x2x3

2

3

2

4

158

(0,0,1,2,0)+

x1x2x1x3x4x2x3x4

2

3

2

3

159

(0,0,1,2,0)+

x1x3x1x2x4x2x3x4

2

3

2

3

160

(0,0,1,2,0)+

x1x4x1x3x4x2x3x4

2

3

2

3

161

(0,0,1,2,0)+

x2x3x1x2x4x1x3x4

2

3

2

3

162

(0,0,1,2,0)+

x2x4x1x2x3x1x3x4

2

3

2

3

163

(0,0,1,2,0)+

x3x4x1x2x3x1x2x4

2

3

2

3

164

(0,1,0,1,0)+

x1x2x3x4

2

4

2

2

№

МБФ

Тип МБФ

Мин. дизъюнк-тивная  форма

i

j

v

m

165

(0,1,0,1,0)+

x2x1x3x4

2

4

2

2

166

(0,1,0,1,0)+

x3x1x2x4

2

4

2

2

167

(0,1,0,1,0)+

x4x1x2x3

2

4

2

2

 

Для типов и МБФ определены [2,5] матрицы распределения, в которых строка соответствует левой границе, а столбец  правой границе. Для максимальных типов и всех типов  это матрицы Mn и Rn , а для МБФ максимальных типов и всех МБФ ранга n это  матрицы распределения Gn и Fn ­. В [4] доказано рекуррентное выражение, позволяющее по матрице Mn-1 находить матрицу Mn , а в [5] доказано рекуррентное выражение, позволяющее по матрице Rn-1 находить матрицу Rn. Так M4 получается произведением 3 матриц:

         M4 = = .

Здесь операция '*' для произведения матриц в скобках обозначает, что к этому произведению нужно добавить строку из нулей снизу, столбец из нулей справа и на их пересечении поставить единицу. Матрица R4 получается произведением 3 матриц и добавлением к полученному произведению еще двух матриц:

R4 = +  +    +  = .

Здесь операция '+' для произведения матриц в скобках обозначает, что к этому произведению нужно добавить строку из нулей снизу, столбец из нулей справа. Для матриц Gn и Fn подобных формул пока не найдено, но из приведенной выше таблицы следует, что:

         G4 =   и  F4 = .

         Относительно операций дизъюнкции и конъюнкции все МБФ одного ранга образуют дистрибутивную решетку. На рис. 1 показана решетка всех МБФ ранга 4. Номера МБФ совпадают с номерами в приведенной выше таблице. Если отбросить МБФ  f0(4) и  f1(4), то решетка на рис. 1 является свободной дистрибутивной решеткой ранга 4.

В [7] на множестве МБФ любого ранга определены три унарные операции: двойственность, дизъюнктивное дополнение и конъюнктивное дополнение. Для получения дизъюнктивного дополнения (n) данной МБФ fi(n) нужно заменить в минимальной дизъюнктивной форме  каждую конъюнкцию из m переменных на конъюнкцию из всех n – m переменных, не входящих в первоначальную конъюнкцию. Для получения конъюнктивного дополнения (n) данной МБФ fi(n) нужно заменить в минимальной конъюнктивной форме  каждую дизъюнкцию из m переменных на дизъюнкцию из всех n – m переменных, не входящих в первоначальную дизъюнкцию. Для получения двойственной МБФ fi-1(n) от данной МБФ fi(n) нужно заменить в минимальной дизъюнктивной форме все операции конъюнкции на операции дизъюнкции и одновременно заменить все операции дизъюнкции операциями конъюнкции. При этом двойственная МБФ fi-1(n) получается в минимальной конъюнктивной форме. Для получения двойственной МБФ fi-1(n) в минимальной дизъюнктивной форме нужно в полученной минимальной конъюнктивной форме раскрыть скобки и привести подобные члены.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


Рисунок 1 – Решетка МБФ  4 ранга

 

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

На рис. 2 показано 3 блока МБФ ранга 4 мощности 2 ( a) блок 1), 3 ( b) блок 2) и 4         ( c) блок 3). Здесь операция двойственности изображается сплошной линией, операция дизъюнктивного дополнения штриховой линией и операция конъюнктивного дополнения штрихпунктирной линией.

 

 

 

 


Рисунок 2 ­–  Блоки МБФ ранга 4 мощности 2, 3 и 4 (блоки 1, 2 и 3)

                  Например, блок 1 состоит из МБФ  f27(4) = x1x2x3x4 и f68(4) = x1x3x1x4x2x3x2x4. Здесь  f68(4) = f27-1(4) и можно сказать, что этот блок порождается МБФ  f27(4). Блок 1 имеет еще 2 изоморфных блока, один из которых состоит из МБФ f30(4) = x1x3x2x4 и f65(4), а другой из МБФ f32(4) = x1x4x2x3 и f63(4). Все блоки, изоморфные блоку 1 (включая блок 1), порождаются МБФ  f27(4), f30(4) и f32(4). Эти блоки содержат 6 МБФ. Блок 2 состоит из МБФ f57(4), f38(4) и f164(4). Этот блок имеет еще 3  изоморфных блока, один из которых состоит из МБФ f50(4),  f45(4) и f165(4), другой из МБФ  f43(4),  f52(4) и f166(4), а третий из МБФ f39(4),  f56(4) и f167(4). Все блоки изоморфные блоку 2 порождаются МБФ f57(4) = x2x3x2x4x3x4,             f50(4) = x1x3x1x4x3x4,  f43(4) = x1x2x1x4x2x4 и f39(4) = x1x2x1x3x2x3. Эти блоки содержат 12 МБФ. Блок 3 состоит из МБФ f46(4), f44(4), f49(4) и f51(4). Этот блок имеет еще 2  изоморфных блока, один из которых состоит из МБФ f41(4),  f47(4), f54(4)  и f48(4), а другой из МБФ  f42(4),  f55(4),  f53(4) и  f40(4).  Все блоки изоморфные блоку 3 порождаются  МБФ     f46(4) = x1x2x2x3x3x4,  f41(4) = x1x2x1x3x3x4 и  f42(4) = x1x2x1x4x2x3. Эти блоки содержат 12 МБФ. Таким образом, имеется 3 + 4 + 3 = 10 блоков, изоморфных трем блокам на рис. 1. Эти блоки содержат 6 + 12 + 12 = 30 МБФ.

На рис. 3 показано 2 блока МБФ ранга 4 мощности 6 ( a) блок 4 и b) блок 5).

 

 

 

 

              Рисунок 3 ­–  Блоки МБФ ранга 4 мощности 6 (блоки 4 и 5)

Блок 4 не имеет изоморфных и состоит из МБФ  f79(4), f94(4), f16(4), f95(4), f0(4) и f1(4). Первые 4 МБФ и единичная МБФ f1(4) являются максимальными МБФ ранга 4 веса 1. МБФ f94(4) и нулевая МБФ f0(4) являются собственными дизъюнктивными дополнениями, а МБФ f79(4) и МБФ f1(4) являются собственными конъюнктивными дополнениями. Блок 5 состоит из МБФ f2(4) = x1, f83(4) = x2x3x4, f15(4) = x2x3x4, f90(4) = x1x2x3 x1x2x4 x1x3x4,               f126(4) = x1x2x3 x2x4 x3x4 и f154(4) = x1x2x1x3 x1x4 x2x3x4. МБФ f2(4) и f126(4) являются самодвойственными. Блок 5 имеет еще 3 изоморфных блока, один из которых состоит из МБФ f3(4),  f82(4), f14(4),  f91(4),  f127(4)  и f155(4), другой из МБФ  f4(4),  f81(4), f13(4),  f92(4), f128(4)   и f156(4), а третий из МБФ f5(4),  f80(4), f12(4),  f93(4), f129(4)     и f157(4). Все блоки, изоморфные блоку 5, порождаются МБФ f2(4) = x1, f3(4) = x2, f4(4) = x3 и f5(4) = x4. Всего имеется 5 блоков, изоморфных блокам на рис. 3. Эти блоки содержат 30 МБФ.

На рис. 4 показано 2 блока МБФ ранга 4 мощности 12 ( a) блок 6 и b) блок 7).

 

 

 

 

 

 

 

 


           Рисунок 4 ­–  Блоки МБФ ранга 4 мощности 12 (блоки 6 и 7)

Блоки 6 и 7 подобны, но неизоморфны. Блок 6 имеет еще 2 изоморфных блока. Все блоки изоморфные блоку 6, порождаются МБФ f17(4) = x1x2, f18(4) = x1x3 и f19(4) = x1x4. Эти блоки содержат 36 МБФ. Блок 7 имеет еще 5 изоморфных блоков. Все блоки изоморфные блоку 7, порождаются МБФ f23(4) = x1x2x1x3,         f24(4) = x1x2x1x4,    f25(4) = x1x2x2x3, f26(4) = x1x2x2x4, f28(4) = x1x3x1x4 и f29(4) = x1x3x2x3.  Эти блоки содержат 72 МБФ. Всего имеется 9 блоков, изоморфных блокам на рис. 3. Эти блоки содержат 108 МБФ.

Таким образом, все 168 МБФ ранга 4 образуют 24 блока. Среди этих блоков только 7 неизоморфных между собой и 6 не являются подобными друг другу. Мощность блока ранга 4 может быть одним из 5 чисел: 2, 3, 4, 6 и 12. Все МБФ любого блока могут быть получены из порождающей МБФ с помощью двух операций, например, дизъюнктивного дополнения и двойственности. Блоки, изоморфные некоторому блоку, можно получить подстановкой переменных в МБФ, входящих в этот блок. Операция подстановки переменных реализуется значительно проще, чем операция двойственности. Следовательно, для полного перебора МБФ заданного ранга методом построения блоков МБФ достаточно построить неизоморфные друг с другом блоки, а остальные получаются из них подстановкой переменных. Уже для ранга 4 вместо 24 блоков достаточно построить 7. С ростом ранга отношение всех блоков к неизоморфным увеличивается.

В заключение отметим следующее. Исследование МБФ ранга 4 позволило изучить свойства более 150 МБФ, которые можно использовать в различных цифровых схемах. Блоки МБФ имеют более простую структуру, чем решетка МБФ, поэтому метод построения блоков МБФ значительно сокращает полный перебор МБФ при синтезе цифровых схем.

 

Литература.

1.     Ткаченко В.Г. Отказы цифровых схем и представления монотонных булевых функций / В.Г. Ткаченко //Наукові праці ОНАЗ ім. О.С. Попова. – 2006. – № 2. – С. 45 – 69.

2.     Ткаченко В.Г. Классификация монотонных булевых функций при синтезе цифровых схем / В.Г. Ткаченко // Наукові праці ОНАЗ ім. О.С. Попова. – 2008. – № 1. – С. 35 – 43.

3.     Ткаченко В.Г. Перечисление типов монотонных булевых функций при синтезе цифровых схем / В.Г. Ткаченко // Наукові праці ОНАЗ ім. О.С. Попова. – 2008. – № 2. – С. 54 – 69.

4.     Ткаченко В.Г. Построение корректирующего кода для криптосистем на основе типов монотонных булевых функций  / В.Г. Ткаченко, О.В. Синявский // Наукові праці ОНАЗ ім. О.С. Попова. – 2010. – № 1. – С.  85 – 92.

5.     Ткаченко В.Г. Взаимосвязь между всеми типами и максимальными типами монотонных булевых функций/ В.Г. Ткаченко //Наукові праці ОНАЗ ім. О.С. Попова. – 2010. – № 2. – С. 60 – 69.

6.     Ткаченко В.Г. Метод построения блоков монотонных булевых функций/ В.Г. Ткаченко //Наукові праці ОНАЗ ім. О.С. Попова. – 2011. – № 1. – С.

7.     Иваницкий А.М. Взаимосвязь между матроидами и монотонными булевыми функциями электрических цепей/ А.М.Иваницкий, В.Г. Ткаченко //Наукові праці ОНАЗ ім. О.С. Попова. – 2009. – № 1. – С. 18 – 26.