Автор работы: Пользователь скрыл имя, 05 Апреля 2012 в 22:12, лекция
Элементарные конъюнкции(дизъюнкции) называются конституентами единицы(нуля), если он содержат все переменные функции.
В геометрическом смысле каждому набору переменных соответствует вершина n- мерного куба с координатами(например х1х2 х3). Элемент х1х2 х3 принято называть 0- кубом. Множество 0- кубов, на которых функция принимает единичные значения, называется кубическим комплексом К0 .
Объединение по столбцам z=
Объединение по строкам y xy =y
Получим КНФ f=y (так как рассматривался прямоугольник).
Для минимизации булевых функций используется еще один метод- метод Квайна.
Для этого необходимо
1. получить сокращенную ДНФ(простые импликанты) путем преобразований или с помощью кубов;
2. составить матрицу Квайна.
Для получения МДНФ из сокращенной строят следующую матрицу Квайна:
1. в заголовки столбцов матрицы записываются конституенты единицы СДНФ;
2. в заголовки строк простые импликанты сокращенной ДНФ.
В матрице ставят отличительный символ по строке, где элементарная конъюнкция (импликанта)входит в конституенту. МДНФ получается из минимального количества вхождений.
Пример №1. Формула А= xy xz xz.
Сокращенная ДНФ
А≡ хz.
Простые импликанты | Конституенты единицы СДНФ | |||
xy | xz
| x | z | |
x
|
| * | * |
|
х | * |
| * |
|
z |
| * |
| * |
МДНФ А= хz