ВУЗ:
Составители:
20
2.3. Преобразование булевых выражений
Рассмотренные законы и правила используются для тождественных преобразо-
ваний булевых выражений, описывающих логические функции. Булевое выражение
представляет собой формулу, состоящую из логических констант и логических пере-
менных, соединенных знаками логических операций. Как и в обычной алгебре для за-
дания порядка выполнения логических выражений используются скобки. Примером
булевого выражения для трех переменных служит формула
f(x
1
, x
2
, x
3
) = )хх)(ххххх(
3121321
. (2.1)
Обычно считают, что операция логического умножения всегда предшествует
операции логического сложения.
Преобразуем выражение (2.1), применив законы и правила алгебры логики.
).хх(ххххх
хх)хх(ххххххххххххх
ххххххххххх)хх)(ххххх(
1322132
21113232121321321
121332113213121321
Полученное в результате тождественных преобразований выражение (2.2) зна-
чительно проще выражения (2.1). Процесс упрощения логического выражения, осно-
ванный на тождественных преобразованиях, называется минимизацией булевых вы-
ражений.
2.4. Дизъюнктивные нормальные формы
Для записи одной и той же функции алгебры логики можно использовать раз-
личные формы. Формы, которые представляют суммы элементарных произведений,
называют дизъюнктивными нормальными формами (ДНФ).
Под элементарным понимается такое произведение, в котором сомножителями
являются только отдельные переменные или их отрицания. Например, формула f(x
1
,
x
2
, x
3
) =
2132
хххх содержит два элементарных произведения, каждое из кото-
рых состоит из двух сомножителей. Очевидно, одна и та же функция может быть
представлена множеством различных ДНФ. Однако существуют такие виды ДНФ,
(2.2)
Страницы
- « первая
- ‹ предыдущая
- …
- 18
- 19
- 20
- 21
- 22
- …
- следующая ›
- последняя »
