Минимизация нормальных форм всюду определённых булевых функций
Решение задачЭлементарная конъюнкция Е называется импликантой булевой функции f, если Е → f ≡ 1.
Импликанта Е называется простой, если при удалении любой буквы из неё она перестаёт быть импликантой булевой функции f.
Сокращённой ДНФ называется ДНФ, состоящая из всех простых импликант данной булевой функции.
Ядровая импликанта — импликанта, удаление которой из ДНФ некоторой булевой функции f приводит к ДНФ, не равносильной f.
Минимальная ДНФ данной функции f — ДНФ, имеющая наименьшее число символов переменных из всех ДНФ, задающих функцию f.
Тупиковой ДНФ функции f называется такая её ДНФ, состоящая из простых импликант, что удаление из неё любой конъюнкции нарушает равносильность ДНФ данной функции.
Сложностью ДНФ (КНФ) называется количество символов переменных, использованных в записи формулы.
Сокращённая ДНФ может быть получена из СДНФ последовательным применением, пока это возможно, формулы неполного склеивания Кu ∨ Кu = Ku ∨ Кu ∨ К, а затем — формулы поглощения Ku ∨ К = К.
Задание 2.5.1
Для данной функции f(x,y,z,w), заданной векторно, проделать следующее:
- Записать её СДНФ и СКНФ.
- Методом Квайна найти сокращённую ДНФ.
- Для сокращённой ДНФ построить матрицу Квайна, указать ядровые импликанты.
- С помощью матрицы Квайна найти минимальную ДНФ, указать её сложность.
- Найти минимальную ДНФ данной функции с помощью карт Карнау, сравнить полученный результат с ДНФ, найденной в п. 4.
Таблица 2.5.1
| № | f | № | f | № | f |
| 1 | 1111 0101 0011 1101 | 11 | 0100 1110 1101 1111 | 21 | 1011 1111 0001 1111 |
| 2 | 1101 1110 1010 1110 | 12 | 1111 1110 0111 1100 | 22 | 1110 1100 1111 1001 |
| 3 | 0111 0001 1111 1101 | 13 | 1000 1011 1111 1111 | 23 | 1001 1011 1111 1010 |
| 4 | 1011 1111 1111 1000 | 14 | 1111 1101 1110 0001 | 24 | 1111 1110 0111 0011 |
| 5 | 1101 0101 1101 1111 | 15 | 1101 0111 1100 1110 | 25 | 1010 1111 0111 0011 |
| 6 | 1111 1110 1010 0011 | 16 | 1011 1111 1010 1101 | 26 | 1110 0110 1111 1100 |
| 7 | 1111 0010 0111 1110 | 17 | 1001 1101 1010 1111 | 27 | 0111 0111 0101 1011 |
| 8 | 1100 1110 1111 1011 | 18 | 1110 0110 1111 1100 | 28 | 1101 1111 1110 1010 |
| 9 | 1100 0110 1111 0111 | 19 | 0011 1011 1010 1111 | 29 | 1111 0011 0111 0111 |
| 10 | 1011 1111 1110 0010 | 20 | 1111 0110 1110 1110 | 30 | 1110 1110 1010 1101 |
Пример решения задания 2.5.1 Решим задание 2.5.1 для функции f(x;y,z,w) = (1101 1010 1101 1100). 1. Изобразим таблицу функции f в виде двумерной таблицы — карты Карнау (табл. 2.5.1а). |
 |
Найдём СДНФ данной функции:
f(x,y,z,w) = 
xa ⋅ yb ⋅ zc ⋅ wd =
x0 y0 z0 w0 ∨ x0 y0 z0 w1 ∨ x0 y0 z1 w1 ∨ x0 y1 z0 w0 ∨ x0 y1 z1 w0 ∨ x1 y0 z0 w0 ∨ x1 y0 z0 w1 ∨ x1 y0 z1 w1 ∨ x1 y1 z0 w0 ∨ x1 y1 z0 w1 ∨ =
= xyzw ∨ xyzw ∨ xyzw ∨ xyzw ∨ xyzw ∨ xyzw ∨ xyzw ∨ xyzw ∨ xyzw ∨ xyzw.
Найдём СКНФ данной функции:
f(x,y,z,w) = 
(xa ∨ yb ∨ zc ∨ wd) =
(x1 ∨ y1 ∨ z0 ∨ w1) ∧
(x1 ∨ y0 ∨ z1 ∨ w0) ∧
(x1 ∨ y0 ∨ z0 ∨ w0) ∧
(x0 ∨ y1 ∨ z0 ∨ w1) ∧
(x0 ∨ y0 ∨ z0 ∨ w1) ∧
(x0 ∨ y0 ∨ z0 ∨ w0) =
(x ∨ y ∨ z ∨ w) ∨ (x ∨ y ∨ z ∨ w) ∨ (x ∨ y ∨ z ∨ w) ∨ (x ∨ y ∨ z ∨ w) ∨ = (x ∨ y ∨ z ∨ w) ∨ (x ∨ y ∨ z ∨ w)
2. Построим сокращённую ДНФ из СДНФ, используя формулы неполного склеивания и поглощения. Для удобства, вместо символов переменных будем работать только с показателями степеней переменных.
Например, вместо xz будем употреблять набор 0 - 1 - . Тогда СДНФ функции будет соответствовать множество всех её единичных наборов. Выпишем единичные наборы данной булевой функции в таблицу, разбив их на группы в соответствии с количеством единичных компонент в наборах.
Тогда для применения формулы неполного склеивания доста точно просмотреть всевозможные пары наборов, входящих в соседние группы. Результаты склеивания наборов из I полосы поместим во II полосе, а наборы, участвующие в склеиваниях, пометим крестиком. Во второй полосе снова применяем, насколько возможно, операцию склеивания, записывая результаты в III полосу и т. д. После завершения процедуры склеивания все простые импликанты попадут в таблицу и не будут помечены крестиком. Помеченные же конъюнкции поглотятся на этапе применения формулы поглощения.
Сокращённая ДНФ данной булевой функции имеет вид: xyw ∨ yz ∨ zw ∨ yw ∨ xz .
3. Для получения из сокращённой ДНФ минимальной ДНФ изобразим следующую таблицу — матрицу Квайна (табл. 2.5.1с).
Ядровыми импликантами будут 1, 4 и 5, так как для каждой из них найдётся единичный набор, на котором она одна принимает значение 1.
4. Выбираем наименьшее число столбцов таких, чтобы для каждой строки из данной таблицы и хотя бы одной единицы в этой строке нашёлся бы по крайней мере один столбец из множества выбранных столбцов, который содержит эту единицу. Тогда дизъюнкция членов, сопоставленных всем выбранным столбцам, является минимальной ДНФ.
Tабл. 2.5.1с.
| № простой импликанты | 1 | 2 | 3 | 4 | 5 |
| единичные наборы\простые импликанты | xyw | yz | zw | yw | xz |
| 0000 | 1 | 1 | |||
| 0001 | 1 | 1 | |||
| 0011 | 1 | ||||
| 0100 | 1 | 1 | |||
| 0110 | 1 | ||||
| 1000 | 1 | 1 | 1 | ||
| 1001 | 1 | 1 | 1 | ||
| 1011 | 1 | ||||
| 1100 | 1 | 1 | |||
| 1101 | 1 |
Для выбора наименьшего числа столбцов, удовлетворяющих перечисленным выше требованиям, составляем символическое выражение (2 ∨3)·(2 ∨4)·4·(1 ∨3)·1·(2 ∨3 ∨5)·(2 ∨4 ∨5)·4·(5 ∨3)·5.
Приведём это символическое выражение к ДНФ, используя дистрибутивный закон и формулу поглощения (A ∨ В) · А = А.
Получим: (2 ∨3)·4·1·5 = 2·4·1·5 ∨3·4·1·5, Сопоставим каждой символической конъюнкции тупиковую ДНФ и выберем из них кратчайшую.
 |
В нашем примере символической конъюнкции 2·4·1·5 соответствует ДНФ xyw∨ yz ∨ yw ∨ xz , а симво лической конъюнкции 3·4·1·5 — xyw ∨zw ∨ yw ∨ xz . Каждая из полученных ДНФ является минимальной для данной булевой функции и имеет сложность, равную количеству символов переменных в формуле, т. е. сложность 9. 5. Найдём минимальную ДНФ с помощью карты Карнау (табл. 2.5.ld). |
Задача нахождения минимальной ДНФ с помощью карты Карнау сводится к задаче покрытия всех единиц карты Карнау прямоугольниками возможно больших размеров, причём разрешается использовать только прямоугольники, площади которых являются натуральными степенями двойки.
При построении покрытия не забываем, что карта Карнау как бы наклеена на поверхность тора, т. е. её левая и правая, а также верхняя и нижняя границы отождествляются.
В нашем примере все единицы покрываются четырьмя прямоугольниками: прямоугольник 1x2, соответствующий конъюнкции xyw, прямоугольник 1x4, соответствующий конъюнкции zw, и два квадрата, соответствующих импликантам xz и yw. Значит, минимальная ДНФ, соответствующая этому покрытию, равна xyw ∨ zw ∨ yw ∨ xz.
Задание 2.5.2
Для функций f(x,y,z), g(x,y,z,w), h(x,y,z,w,t) найти мини- мальные ДНФ и минимальные КНФ с помощью карт Карнау, указать сложности минимальных ДНФ.
Таблица 2.5.2
| № | f | g | h |
| 1 | 1011 1100 |
1110 1110 1111 0001 |
1011 1110 1100 1111 1111 0001 0101 1100 |
| 2 | 0111 1010 |
1111 0010 1111 0111 |
1100 1011 1011 1110 1110 1011 0111 1111 |
| 3 | 1001 1001 |
1101 1001 1111 0011 |
1011 1111 0011 0001 0110 1101 1011 1110 |
| 4 | 1110 1110 |
1011 1010 1111 1110 |
1100 1100 1110 1111 1000 1111 1011 1111 |
| 5 | 1010 1111 |
1101 1100 1111 1101 |
1101 0011 1111 1101 1110 1101 0111 1100 |
| 6 | 0110 1111 |
1111 1011 0011 1101 |
1011 1100 1111 1000 0111 1011 1110 0101 |
| 7 | 1000 1101 |
1010 1111 1011 1110 |
1100 1110 0111 1111 0001 1111 1011 0111 |
| 8 | 0111 0110 |
1100 1110 1100 1111 |
1010 1110 1111 1101 0111 1001 1110 0000 |
| 9 | 1110 0011 |
1101 1011 1111 1101 |
1001 1100 1101 1111 1101 1111 0001 1011 |
| 10 | 0111 0101 |
1010 1110 1110 1111 |
1010 1110 0111 1110 0011 1110 0110 0101 |
| 11 | 1000 1111 |
1001 0001 1110 1110 |
0101 1110 1110 0111 0111 1110 1101 0110 |
| 12 | 1011 0111 |
1101 1011 1110 1110 |
1010 0111 1101 1111 1000 1111 1110 1001 |
| 13 | 0011 1101 | 0111 1011 0011 1110 |
1001 1100 1110 1111 1100 1111 1010 0000 |
| 14 | 1011 0111 |
1000 0110 1111 1110 |
0110 1101 1111 1101 1111 1011 0111 1110 |
| 15 | 0111 0101 |
1011 1101 0011 0111 |
1010 1111 1011 1101 0111 1110 1101 1110 |
| 16 | 1000 1110 |
1100 1100 0111 1100 |
1101 0111 1101 1011 0111 1110 1111 0000 |
| 17 | 1111 0110 |
0011 0111 111 1011 |
0101 1000 1111 1100 1000 1110 1110 0111 |
| 18 | 0111 1001 |
1100 1100 1110 0011 |
0111 1111 1101 0111 1111 0101 1110 1101 |
| 19 | 1000 1110 |
0111 1110 0011 1110 |
0001 1111 1011 1101 0010 1111 1000 1000 |
| 20 | 0111 1001 |
1010 1110 1111 1101 |
1011 0001 1111 1100 0111 1001 1110 1110 |
| 21 | 0101 1100 |
1111 0011 1011 1111 |
1001 1011 1100 1110 0001 0111 1011 1000 |
| 22 | 0111 0101 |
1100 0000 1110 1101 |
1011 1111 1101 0111 1110 1110 0111 0001 |
| 23 | 1001 0110 |
1101 1110 1101 1111 |
0111 1110 1110 0011 1111 0011 1001 1111 |
| 24 | 0001 1100 |
1100 1110 0111 1111 |
1010 1111 1101 1100 1111 1010 1101 0110 |
| 25 | 1000 1110 |
1010 0111 1110 1100 |
0111 0111 1010 0011 1111 0010 1010 1111 |
| 26 | 1110 0101 |
1101 1001 1111 0111 |
0110 1111 1110 1010 0110 0110 1101 0010 |
| 27 | 1101 1100 |
0011 0011 1011 1111 |
1001 1110 1001 1111 0010 1001 1111 0011 |
| 28 | 1110 0110 |
1010 0101 1111 1011 |
0111 1011 1011 1111 1111 1011 0010 1111 |
| 29 | 0001 1111 |
1101 0111 1110 0110 |
1101 0100 1111 0111 1110 0110 1111 1000 |
| 30 | 1100 0011 |
0110 1101 1111 1000 |
0111 1010 1110 0111 1110 0111 1110 0110 |
Пример решения задания 2.5.2
Решим задание 2.5.2 для функций f(x, у, z) = (0111 0011), g(x,y,z,w) = (1111 1101 1010 0000), h(x,y,z,w,t) = (1111 0111 1010 0110 1111 0111 1010 1010).
 |
Карта Карнау для функции f(x,y,z) от трёх переменных имеет такой вид (табл. 2.5.2а). Мы считаем её как бы наклеенной на поверхность цилиндра, т. е. отождествляем верхнюю часть карты Карнау с нижней. При отыскании минимальной ДНФ единицы карты Карнау покрываем прямоугольниками вида 2x2 и 1x2, отвечающим импликантам у и xz соответственно, получаем минимальную ДНФ у ∨ xz . Её сложность равна 3. |
Для нахождения минимальной КНФ покрываем нули карты Карнау двумя прямоугольниками размера- ми 1x2, которые соответствуют элементарным дизъюнкциям y ∨ ∨ и у ∨ z . В результате получаем минимальную КНФ (у ∨ x) ⋅ (у ∨ z).
 |
При нахождении минимальной ДНФ функции g(x,y,z,w) заполняем карту Карнау и покрываем единицы карты прямоугольниками возможно больших размеров (табл. 2.5.2b). Получим минимальную ДНФ: уw ∨ xz ∨ xw. Сложность минимальной ДНФ равна 6. |
 |
Отыщем минимальную КНФ функции g(x,y,z,w). Для этого произведём покрытие нулей карты Карнау (табл. 2.5.2с). |
Минимальная КНФ будет иметь вид:
(x ∨ y)⋅(x ∨ w)⋅(y ∨ z ∨ w).
Рассмотрим функцию h(x,y,z,w,t) = (1111 0111 1010 1111 0111 1010 1010).
Карту Карнау для пяти переменных можно воспринимать, как "двухслойную" карту Карнау для функции от 4 переменных, где верхний слой соответствует значениям х = 0, а нижний - х = 1, причём клетки, образующие "двухслойный" прямоугольник, соответствуют импликантам, в которых переменная х отсутствует. Двухслойные прямоугольники будем изображать жирными линиями, а однослойные — тонкими (табл. 2.5.2d).
Все единицы карты Карнау могут быть покрыты тремя двухслойными прямоугольниками и двумя однослойными. Минимальная ДНФ будет иметь вид: zt v yt v xzwt v xyt.
Её сложность равна 13.
Для отыскания минимальной КНФ покроем прямоугольниками нули карты Карнау (табл. 2.5.2е).
Все нули карты Карнау могут быть покрыты тремя двухслойными прямоугольниками и двумя однослойными.
Минимальная КНФ будет иметь вид:
(y ∨ w ∨ t)-(y ∨ z ∨ t)⋅(y ∨ z ∨ w ∨ t)⋅(x ∨ y ∨ t)⋅(x ∨ z ∨ w ∨ t).