Составители:
Пусть функция f представлена СДНФ. Переход к сокращенной форме
основан на последовательном применении двух операций: операции
склеивания и операции поглощения.
Для выполнения операции склеивания в выражении функции
выявляются пары членов вида
x
w
⋅
и
x
w
⋅
, различающихся лишь тем, что
один из аргументов в одном из членов представлен без инверсии, а в другом –
с инверсией. Затем производится склеивание таких пар
w
x
x
w
x
w
x
w =∨⋅=⋅∨⋅ )( , и результаты склеивания вводятся в выражение
функции в качестве дополнительных членов.
Далее производится операция поглощения. Она основана на равенстве:
(член w поглощает член
w · z). При проведении этой
операции из логического выражения вычеркиваются все члены, поглощаемые
членами, которые введены в результате операции склеивания.
wzwzww =∨⋅=⋅∨ )1(
Операции склеивания и поглощения выполняются последовательно до
тех пор, пока это возможно.
Члены сокращенной формы называются простыми импликантами
функции.
Второй этап (получение минимальной формы).
Сокращенная форма
может содержать лишние члены, исключение которых из выражения не
повлияет на значение функции.
Упрощение логического выражения достигается исключением из
выражения лишних членов. Для этого используется импликантная матрица. В
столбцы импликантной матрицы вписываются члены СДНФ заданной
функции, а в строки – простые импликанты функции. Отмечаются столбцы
членов СДНФ, поглощаемых отдельными простыми импликантами.
Импликанты, которые не могут быть лишними и, следовательно, не могут
быть исключены из сокращенной формы, составляют ядро. Входящие в ядро
импликанты легко определяются по импликантной матрице. Для каждой из
них имеется хотя бы один столбец, перекрываемый только данной
импликантой.
Для получения минимальной формы достаточно выбрать из импликант,
не входящих в ядро, такое минимальное их число с минимальным количеством
букв в каждой из этих импликант, которое обеспечит перекрытие всех
столбцов, не перекрытых членами ядра.
При использовании метода Квайна для получения минимальной
конъюнктивной нормальной формы (МКНФ) логической функции имеются
следующие особенности:
исходной для минимизации формой логического выражения заданной
функции является СКНФ;
пары склеиваемых членов имеют вид:
x
w ∨ и
x
w ∨ ;
операция поглощения проводится в соответствии с выражением
zyzyzzyzz
=
∨⋅=⋅∨=∨⋅ )1()(.
15
Пусть функция f представлена СДНФ. Переход к сокращенной форме
основан на последовательном применении двух операций: операции
склеивания и операции поглощения.
Для выполнения операции склеивания в выражении функции
выявляются пары членов вида w ⋅ x и w ⋅ x , различающихся лишь тем, что
один из аргументов в одном из членов представлен без инверсии, а в другом –
с инверсией. Затем производится склеивание таких пар
w ⋅ x ∨ w ⋅ x = w ⋅ ( x ∨ x ) = w , и результаты склеивания вводятся в выражение
функции в качестве дополнительных членов.
Далее производится операция поглощения. Она основана на равенстве:
w ∨ w ⋅ z = w ⋅ (1 ∨ z ) = w (член w поглощает член w · z). При проведении этой
операции из логического выражения вычеркиваются все члены, поглощаемые
членами, которые введены в результате операции склеивания.
Операции склеивания и поглощения выполняются последовательно до
тех пор, пока это возможно.
Члены сокращенной формы называются простыми импликантами
функции.
Второй этап (получение минимальной формы). Сокращенная форма
может содержать лишние члены, исключение которых из выражения не
повлияет на значение функции.
Упрощение логического выражения достигается исключением из
выражения лишних членов. Для этого используется импликантная матрица. В
столбцы импликантной матрицы вписываются члены СДНФ заданной
функции, а в строки – простые импликанты функции. Отмечаются столбцы
членов СДНФ, поглощаемых отдельными простыми импликантами.
Импликанты, которые не могут быть лишними и, следовательно, не могут
быть исключены из сокращенной формы, составляют ядро. Входящие в ядро
импликанты легко определяются по импликантной матрице. Для каждой из
них имеется хотя бы один столбец, перекрываемый только данной
импликантой.
Для получения минимальной формы достаточно выбрать из импликант,
не входящих в ядро, такое минимальное их число с минимальным количеством
букв в каждой из этих импликант, которое обеспечит перекрытие всех
столбцов, не перекрытых членами ядра.
При использовании метода Квайна для получения минимальной
конъюнктивной нормальной формы (МКНФ) логической функции имеются
следующие особенности:
исходной для минимизации формой логического выражения заданной
функции является СКНФ;
пары склеиваемых членов имеют вид: w ∨ x и w ∨ x ;
операция поглощения проводится в соответствии с выражением
z ⋅ ( z ∨ y ) = z ∨ z ⋅ y = z ⋅ (1 ∨ y ) = z .
15
