2.4. Сокращенные и тупиковые нормальные формы.
Задача нахождения сокращенных и тупиковых нормальных форм БФ возникает при решении задачи минимизации, как ее частный случай: представить БФ в нормальной форме с использованием наименьшего возможного букв и функций.
Эта задача минимизации, называемая канонической, является основной при синтезе комбинационных схем.
В общем случае под минимизацией БФ понимают нахождение этой функции в виде суперпозиции функций, составляющих какой-либо базис или систему БФ.
Сокращенные формы (ДСНФ и КСНФ) получают из совершенных (СДНФ, СКДФ) путем склеивания элементарных конъюнкций (дизъюнкций) одного ранга по принципу ”каждая с каждой”.
Например, , представленную таблицей истинности табл. 1, необходимо привести к форме КСНФ. Поместим в первый столбец все ее конституенты «0» (табл. 2) и склеим все возможные варианты по принципу «каждая с каждой» одновременно помечая « » участвующих в склейке и записывая результаты во второй столбец.
Затем повторим эту операцию с элементарными дизъюнкциями второго столбца, получая третий и т.д., до тех пор, пока в текущем столбце будут встречаться склеиваемые дизъюнкции.
Заметим, что в скобках приведены номера дизъюнкций предыдущего столбца, участвующие в получении данной дизъюнкции.
Табл. 1 Табл. 2
|
|
|
|
| Конституенты "0" | Эл. дизъюнкц. ранга 2 | Эл. дизъюнкц. ранга 1 | ||
0 | 0 | 0 | 0 |
| 1) 2) 3) 4) 5) | 1) (1,2)* 2) (2,3)* 3) (2,4)* 4) (3,5)* 5) (4,5)* | (2,5) (3,4) | ||
0 | 0 | 1 | 1 | ||||||
0 | 1 | 0 | 0 | ||||||
0 | 1 | 1 | 0 | ||||||
1 | 0 | 0 | 1 | ||||||
1 | 0 | 1 | 1 | ||||||
1 | 1 | 0 | 0 | ||||||
1 | 1 | 1 | 0 |
В функцию в форме КСНФ попадут все непомеченные дизъюнкции всех столбцов табл. 2
.
Покажем получение ДСНФ на примере функции , заданной в табл. 3. состоит из 8 конституент. "1", по которым и произведем склеивание, аналогично предыдущему примеру для КСНФ. В табл. 4 показано склеивание конституент «1» и элементарных конъюнкций функции записанных в виде комбинаций 1 и 0.
Табл. 3 Табл. 4
x1 x2 x3 x4 | f2 |
| Конституенты 1 | Конъюнкции ранга 3 | Конъюнкции ранга 2 |
0 0 0 0 | 1 |
| 1) 0 0 0 0 * | 0 0 0 _ (1, 2) * | 0 _ 0 _ (1, 4) |
0 0 0 1 | 1 |
| 2) 0 0 0 1 * | 0 _ 0 0 (1, 3) * | 0 _ 0 _ (2, 3) |
0 0 1 0 | 0 |
| 3) 0 1 0 0 * | 0 _ 0 1 (2, 4) * |
|
0 0 1 1 | 0 |
| 4) 0 1 0 1 * | 0 1 0 _ (3, 4) * |
|
0 1 0 0 | 1 |
| 5) 0 1 1 1 * | 0 1 _ 1 (4, 5) * |
|
0 1 0 1 | 1 |
| 6) 1 0 1 0 * | _ 1 1 1 (5, 8) * |
|
0 1 1 0 | 0 |
| 7) 1 1 1 0 * | 1 _ 1 0 (6, 7) * |
|
0 1 1 1 | 1 |
| 8) 1 1 1 1 * | 1 1 1 _ (7, 8) * |
|
1 0 0 0 | 0 |
|
|
|
|
1 0 0 1 | 0 |
|
|
|
|
1 0 1 0 | 1 |
|
|
|
|
1 0 1 1 | 0 |
|
|
|
|
1 1 0 0 | 0 |
|
|
|
|
1 1 0 1 | 0 |
|
|
|
|
1 1 1 0 | 1 |
|
|
|
|
1 1 1 1 | 1 |
|
|
|
|
Форма ДСНФ для функции f2 является избыточной, однако сократить ее по основным законам булевой алгебры не представляется возможным. Определим, какие конъюнкции в форме ДСНФ можно исключить без изменения таблицы истинности функции.
Итак, все конституенты «1» функции являются обязательными. Конъюнкции более низкого ранга получены из конституент «1» путем склеивания и значит, содержат в себе значения исходных конституент.
Определение минимального количества дизъюнкций с пониженным рангом, содержащих в себе все конституенты единицы, производится с помощью импликантной таблицы (табл. 5).
Табл. 5
Иден-тиф. строки | Конституенты Простые единицы Импликанты |
0000 |
0001 |
0100 |
0101 |
0111 |
1010 |
1110 |
1111 |
a |
| X | X | X | X |
|
|
|
|
b |
|
|
|
| X | X |
|
|
|
c |
|
|
|
|
| X |
|
| X |
d |
|
|
|
|
|
| X | X |
|
e |
|
|
|
|
|
|
| X | X |
|
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
Нам необходимо определить по ней варианты покрытий всех столбцов (конституент "1") строками (простыми импликантами).
Итак, в покрытие П должны входить все конституенты единицы функции:
При этом каждая из конституент может быть представлена в покрытии одной или несколькими простыми импликантами, например,
То есть,
Функция , таким образом имеет 2 тупиковые формы:
Тупиковой формой функции называют такую систему простых импликант, соответствующих , при удалении из которой хотя бы одной импликанты система перестает соответствовать .
Среди тупиковых форм различают минимальные и кратчайшие.
Минимальная форма ДНФ или КНФ – это такая тупиковая ДНФ или КНФ, которая содержит минимальное количество переменных.
Кратчайшая ДНФ или КНФ – это тупиковая форма, содержащие минимальное количество элементарных конъюнкций или дизъюнкций.
В рассмотренном случае является одновременно МДНФ и КДНФ.
Для функций от небольшого количества переменных (до 5) кратчайшая и минимальная формы совпадают. Вероятность несовпадения увеличивается с ростом числа переменных функции.
- Часть I
- 1. Математическая логика
- 1.1.Булева алгебра
- 1.5. Системы и базисы булевых функций
- 2. Нормальные формы бф.
- 2.2 Совершенные нормальные формы.
- 2.3. Приведение к совершенным формам днф и кнф.
- 2.4. Сокращенные и тупиковые нормальные формы.
- 3. Методы минимизации булевых функций.
- 3.1. Метод Квайна – Мак-Класки
- 3.2. Минимизация по картам Карно-Вейча
- 3.3. Понятие интервала функции.
- 3.4. Слабоопределенные бф.
- Этапы минимизации бф. Табл. 6
- Контрольные вопросы и задания