Дискретная математика. Прокушев Л.А. - 25 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

23
Действительно, так как для простого импликанта то дизъюнкция всех
простых импликантов представляет эту функцию.
Тупиковой ДНФ функции f называется дизъюнкция простых импли-
кантов, из которых ни один простой импликант нельзя удалить так,
чтобы полученная ДНФ все еще представляла функцию f.
Булева функция f(x
1
, . . . , x
n
) может иметь несколько тупиковых ДНФ,
а среди них обязательно содержатся все ее минимальные ДНФ (их тоже
может быть несколько), т. е. такие ДНФ, которые содержат наименьшее
число букв по сравнению с остальными ДНФ этой функции. Получе-
ние МДНФ можно разбить на два этапа: 1) получение сокращенной
ДНФ; 2) получение тупиковых ДНФ и выбор из них МДНФ.
Получение сокращенной ДНФ основано на использовании соотноше-
ний (1–16), рассмотренных теорем и понятий, а также следующих пра-
вил эквивалентных преобразований и минимизации формул с целью их
упрощения.
1. Правило подстановки формулы вместо переменной. При подстанов-
ке формулы F вместо переменной х все вхождения переменной х в исход-
ное соотношение должны быть одновременно заменены формулой F.
Например, соотношение
1
FF
∨=
, полученное из закона “исклю-
ченного третьего” (
1
хх
∨=
), верно для любых F.
2. Правило замены подформул. В булевой алгебре равенство F
1
= F
2
означает, что формулы F
1
и F
2
эквивалентны, т.е. описывают одну и ту
же функцию f. Следовательно, если какая-либо формула F содержит
F
1
в качестве подформулы, то замена F
1
на F
2
не изменяет элемента
функции f, над которым производят операции в формуле F. Поэтому
формула F
‘
, полученная из F такой заменой, эквивалентна исходной
формуле F.
Пример. Возьмем соотношение правила де Моргана
12 1 2
хх х х=∨
и подставим вместо
1
х
формулу
13
хх
. Получим
132 13 2
ххх хх х=∨
, т. е.
две формулы, не эквивалентные исходным, но эквивалентные между
собой. Используя снова правило де Моргана и закон двойного отрица-
ния (
хх=
), можно получить цепочку преобразований формул, кото-
рые экви- валентны между собой:
132 13 2 1 3 2 1 2 3
хххххххххххх=∨=∨==∨∨
2. Правила упрощения формул:

Страницы