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

UptoLike

ВУЗ: 

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

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

Рубрика: 

14
ù (x
1
x
2
) = ùx
1
Ú ùx
2
;
(2.5)
ù(x
1
Ú x
2
) = ùx
1
ùx
2
.
Покажем, как применить правило де Моргана для вывода формулы
СКНФ.
В табл. 2.4 имеется значение функции, инверсной к F, т. е. ùF. Эта
функция имеет только две единицы, поэтому СДНФ ее будет представ
лять собой две конъюнкции, каждая ранга три, объединенные знаком
дизъюнкции:
ùF = ùx
1
ùx
2
x
3
Ú x
1
ùx
2
ùx
3
. (2.6)
Проинвертируем левую и правую части выражения (2.6) и приме
ним к правой части правило де Моргана, тогда получим
F = (x
1
Ú x
2
Ú ùx
3
)(ùx
1
Ú x
2
Ú x
3
).
В результате получена формула СКНФ функции F.
2.5. Минимизация булевых функций
с помощью диаграмм Вейча (карт Карно)
Диаграммы Вейча являются той же таблицей истинности булевой
функции, только представленной в более компактной форме. Так, для
функции трех аргументов, которая задается на 8 наборах, таблица ис
тинности будет содержать 8 строк, а диаграмма Вейча – 8 клеток, при
чем каждая клетка в диаграмме Вейча соответствует некоторому набо
ру (строке) в таблице истинности.
111
1
Области в диаграмме Вейча обозначим следующим образом: подчер
кнутые столбцы или строки будут соответствовать истинному значе
нию аргумента, а не подчеркнутые – ложному. Тогда диаграмма Вейча
мажоритарной функции которой примет вид
111
1
X
2
X
1
X
3
X
2
X
1
X
3

Страницы