Дискретная математика. Ерош И.Л - 20 стр.

UptoLike

ВУЗ: 

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

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

Рубрика: 

20
Для упрощения произвольных булевых выражений можно постро
ить диаграмму Вейча этого выражения и выписать из полученной ди
аграммы аналитическое выражений в дизъюнктивной нормальной фор
ме. Алгоритм упрощения можно представить следующим образом.
1. Подсчитать число аргументов, которые входят в выражение.
2. Для любого фрагмента упрощаемого выражения строить диаг
рамму Вейча на полное число аргументов.
3. Применять встречающиеся функции к диаграммам, которые со
ответствуют фрагментам.
4. Из результирующей диаграммы выписать минимальное выраже
ние в дизъюнктивной нормальной форме.
Пусть, например, требуется упростить булево выражение: ù(ABC ®
AD) Å (BC / ACD). Число разных аргументов в этом выражении равно
4. Следовательно, все диаграммы будут строиться на 4 аргумента. По
строим две диаграммы для конъюнкций ABC и AD.
1
1
11
11
Из таблицы истинности двух аргументов (табл. 2.2) найдем табли
цу функции «импликация». Построим диаграмму Вейча для резуль
тата: ABC ® AD и проинвертируем результат.
1111
1111
1011
1111
1
ABC ® AD ù(ABC ® AD)
Построим диаграммы Вейча для следующих конъюнкций: BC и
ACD.
11
11
11
A
B
D
C
A
B
D
C
A
B
D
C
A
B
D
C
A
B
D
C
A
B
D
C

Страницы