Составители:
1.
СДНФ функции представляют наборами значений аргументов, на
которых функция равна лог.1.
Десятичный эквивалент
набора аргументов
0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
x
1
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
x
2
0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
x
3
0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
x
4
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
f(x
1
, x
2
, x
3
, x
4
) 0 1000100011 1 0 1 0 0
Пусть функция задана таблицей истинности. СДНФ функции
записываем в виде совокупности наборов (представленных их десятичными
эквивалентами), на которых функция принимает значение лог.1.
f(x
1
, x
2
, x
3
, x
4
) = ∨ (1, 5, 9, 10, 11, 13).
Эта запись читается так: "функция f принимает значение лог.1 на
наборах, соответствующих десятичным эквивалентам или 1, или 5, или 9, или
10, или 11, или 13". Функцию можно записать и через наборы,
представленные в двоичной форме: f = 0001V0101V1001V1010V1011V1101.
2. Все члены в этой форме СДНФ
разбивают на группы по числу единиц,
содержащихся в наборах
(представленных в двоичной форме). Эта
разбивка наборов на группы для
рассматриваемой функции представлена
в графе 1 этапа табл. 1.17.
Номер
группы
Наборы
I этап II этап III этап
0 -- -- --
1 0001
3. Производят склеивание наборов.
Склеиваться могут только наборы
соседних групп, различающиеся лишь в
одном разряде. Результат склеивания пары наборов содержит на месте разряда
с различающимися значениями в наборах символ * и заносится в графу
следующего этапа, а пара склеивающихся наборов вычеркивается (при этом
вычеркнутые наборы должны использоваться в последующих поисках
склеивающихся пар наборов). Так, склеивание пары наборов 0001 и 0101
графы 1 этапа приводит к набору 0*01, записываемому в графе II этапа.
Результаты склеивания наборов II этапа заносятся в графу III этапа.
Сюда перенесены и невычеркнутые наборы из графы II этапа. Дальнейшее
склеивание оказывается невозможным.
Наборы графы последнего этапа изображают простые импликанты
функции, т.е. члены сокращенной ДНФ. В рассматриваемом примере
сокращенная ДНФ функции f(x
1
, x
2
, x
3
, x
4
)=**01 v 10*1 v 101 *.
Эта запись соответствует логическому выражению, получаемому по
правилу:
1.
каждый набор соответствует отдельной импликанте;
2.
каждому символу в наборе соответствует переменная функции с
индексом, совпадающим с номером позиции символа в наборе;
0*01 **01
*001
2 0101 *101 10*1
1001 10*1 101*
1010 1*01
101*
3 1011 -- --
1101
17
1. СДНФ функции представляют наборами значений аргументов, на
которых функция равна лог.1.
Десятичный эквивалент 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
набора аргументов
x1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
x2 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
x3 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
x4 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
f(x1, x2, x3, x4) 0 1 0 0 0 1 0 0 0 1 1 1 0 1 0 0
Пусть функция задана таблицей истинности. СДНФ функции
записываем в виде совокупности наборов (представленных их десятичными
эквивалентами), на которых функция принимает значение лог.1.
f(x1, x2, x3, x4) = ∨ (1, 5, 9, 10, 11, 13).
Эта запись читается так: "функция f принимает значение лог.1 на
наборах, соответствующих десятичным эквивалентам или 1, или 5, или 9, или
10, или 11, или 13". Функцию можно записать и через наборы,
представленные в двоичной форме: f = 0001V0101V1001V1010V1011V1101.
Номер Наборы 2. Все члены в этой форме СДНФ
группы I этап II этап III этап разбивают на группы по числу единиц,
0 -- -- --
1 0001 0*01 **01
содержащихся в наборах
*001 (представленных в двоичной форме). Эта
2 0101 *101 10*1 разбивка наборов на группы для
1001 10*1 101* рассматриваемой функции представлена
1010 1*01 в графе 1 этапа табл. 1.17.
101*
3 1011 -- -- 3. Производят склеивание наборов.
1101 Склеиваться могут только наборы
соседних групп, различающиеся лишь в
одном разряде. Результат склеивания пары наборов содержит на месте разряда
с различающимися значениями в наборах символ * и заносится в графу
следующего этапа, а пара склеивающихся наборов вычеркивается (при этом
вычеркнутые наборы должны использоваться в последующих поисках
склеивающихся пар наборов). Так, склеивание пары наборов 0001 и 0101
графы 1 этапа приводит к набору 0*01, записываемому в графе II этапа.
Результаты склеивания наборов II этапа заносятся в графу III этапа.
Сюда перенесены и невычеркнутые наборы из графы II этапа. Дальнейшее
склеивание оказывается невозможным.
Наборы графы последнего этапа изображают простые импликанты
функции, т.е. члены сокращенной ДНФ. В рассматриваемом примере
сокращенная ДНФ функции f(x1, x2, x3, x4)=**01 v 10*1 v 101 *.
Эта запись соответствует логическому выражению, получаемому по
правилу:
1. каждый набор соответствует отдельной импликанте;
2. каждому символу в наборе соответствует переменная функции с
индексом, совпадающим с номером позиции символа в наборе;
17
