- •Часть I
- •1. Математическая логика
- •1.1.Булева алгебра
- •1.5. Системы и базисы булевых функций
- •2. Нормальные формы бф.
- •2.2 Совершенные нормальные формы.
- •2.3. Приведение к совершенным формам днф и кнф.
- •2.4. Сокращенные и тупиковые нормальные формы.
- •3. Методы минимизации булевых функций.
- •3.1. Метод Квайна – Мак-Класки
- •3.2. Минимизация по картам Карно-Вейча
- •3.3. Понятие интервала функции.
- •3.4. Слабоопределенные бф.
- •Этапы минимизации бф. Табл. 6
- •Контрольные вопросы и задания
2.3. Приведение к совершенным формам днф и кнф.
Для приведения любых видов ДНФ и КНФ к совершенным формам используется закон склеивания в обратном порядке:
для преобразования ДНФ в СДНФ
для преобразования КНФ в СКНФ
Примеры:
а).
б).
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) кратчайшая и минимальная формы совпадают. Вероятность несовпадения увеличивается с ростом числа переменных функции.