Математика \ Дискретная математика

Минимизация системы булевых функций. Синтез ПЛМ с заданной выходной матрицей, страница 3

К =	а	б	в	г	д	е	ж	з	И	к	л	м	н	о	п	р	с	т
	1	1	0	0	0	0	0	0	0	1	0	1	0	1	1	0	0	0	1
	0	0	1	0	1	1	0	0	0	0	0	0	0	0	0	0	0	0	2
	0	0	1	0	0	1	0	0	0	0	0	0	0	1	0	1	0	0	3
	0	0	0	1	1	1	0	0	0	0	0	0	0	0	0	0	0	0	4
	0	0	0	1	1	0	1	1	0	0	0	0	0	0	0	0	0	0	5
	0	0	0	0	0	0	1	0	1	0	1	0	1	0	0	0	1	1	6
	0	0	0	0	0	0	0	1	1	0	0	0	0	0	0	0	0	0	7
	0	0	0	0	0	0	0	0	0	1	1	1	0	0	0	0	0	0	8
	0	0	0	0	0	0	0	0	0	1	0	1	1	0	0	0	0	0	9
	1	0	1	0	0	0	0	0	0	1	0	0	0	1	0	0	0	0	10
	0	0	0	1	0	0	1	0	0	0	1	0	0	0	0	0	1	0	11

Кратчайшее строчное покрытие этой матрицы находится простым редуцированием: сначала в решение включаются строки 1, 3 и 6, для каждой из которых в матрице находится столбец, где только эта строка содержит значение 1,затем выбирается строка 5, покрывающая оставшиеся непокрытыми столбцы.

Отберем далее из существенных множеств Q_t те, которые соответствуют вошедшим в кратчайшее покрытие строкам матрицы К:

1	2	3	4	5	6
1	0	0	1	0	0	1
1	0	0	0	1	0	3
0	1	1	0	0	0	5
0	1	0	0	0	1	6

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

1 2 3 4 5 6 7 8 9 10 11

Скачать файл