- •1. Элементы булевой алгебры
- •2. Разнообразие булевых функций
- •3. Нормальные формы булевых функций
- •4. Числовая и символическая формы представления булевых функций
- •5. Преобразование произвольной аналитической формы булевой функции в нормальную
- •6. Приведение произвольных нормальных форм булевой функции к каноническим
- •7. Разнообразие двоичных алгебр
- •8. Задача минимизации булевых функций
- •9. Кубическое представление булевых функций
- •10. Геометрическая интерпретация кубов малой размерности. Графическое представление булевых функций
- •11. Покрытия булевых функций
- •12. Минимизация булевых функций на картах Карно
- •13. Импликанты булевой функции. Системы импликант
- •14. Метод Квайна - Мак - Класки
- •14.1. Нахождение множества максимальных кубов (простых импликант) булевой функци
- •14.2. Определение ядра покрыти
- •14.3. Определение множества минимальных покрытий
- •15. Функциональная полнота системы булевых функций
- •15.1. Теорема о функциональной полноте (теорема Поста)
- •15.2. Другая формулировка теоремы Поста
- •15.3. Замечательные классы булевых функций
- •15.4. Конструктивный подход к доказательству функциональной
14.2. Определение ядра покрыти
Для выполнения этого этапа первоначально строится таблица покрытий, строки которой соответствуют максимальным кубам покрытия, а столбцы – существенным вершинам булевой функции. Безразличные наборы аргументов при минимизации неполностью определенной булевой функции в таблице покрытий не участвуют. Тем самым для этого этапа производится доопределение неполностью определенной булевой функции значениями нуля на безразличных наборах аргументов.
Таблица покрытий отображает отношение покрытия между существенными вершинами булевой функции и максимальными кубами. Для этого на пересечении i - ой строки и j - го столбца таблицы делается соответствующая отметка в том случае, если максимальный куб из i - ой строки покрывает существенную вершину из j - го столбца.
Таблица покрытий с соответствующими отметками приведена в виде табл. 5.
Замечания.
Таблицу покрытий называют также импликантной таблицей в связи с тем, что максимальные кубы соответствуют простым (первичным) импликантам булевой функции, а существенные вершины - конституентам единицы булевой функции.
Для полностью определенных булевых функций количество меток в строке таблицы покрытий, соответствующей максимальному кубу размерности r, равно 2r. Для не полностью определенных функций количество меток может быть меньше 2r в том случае, если в образовании r-куба участвуют кроме существенных вершин и безразличные наборы.
Для выделения ядра покрытия в таблице покрытий ищутся столбцы, в которых содержится единственная метка. Это означает, что существенная вершина, соответствующая такому столбцу, покрывается только одним из максимальных кубов. В соответствии с этим максимальный куб, который один и только один покрывает некоторую существенную вершину булевой функции, включается в обязательную часть покрытия, называемую ядром.
В табл. 5 выделены метки, являющиеся единственными в своих столбцах
Таблица покрытий
Таблица 5
-
Максимальные кубы
Существенные вершины
0000
0001
0101
0111
1 000
1 010
1 110
1110
1111
1 XX0
000X
X000
0X01
01X1
X111
111X
Как видно из табл. 5 в нашем примере кубом ядра, будет являться куб: T(f)={1ХХ0}.