Составители:
Рубрика:
14
Раздел 6. Булевы (переключательные) функции
Понятие о булевых функциях (БФ); булевы операции и булева алгеб-
ра; способы задания БФ; представление БФ дизъюнктивными и конъ-
юнктивными нормальными формами; эквивалентные преобразования
формул; минимизация БФ; получение простых импликантов; теорема о
функциональной полноте.
Булевыми (переключательными) функциями f(x
1
, x
2
, …, x
n
) называ-
ют такие функции, у которых все аргументы, как и сами функции, мо-
гут принимать лишь два значения. Эти значения, называемые булевы-
ми, представляют двумя системами обозначений: {ложь, истина}, {0,
1}. Последнюю систему удобно использовать при разработке дискрет-
ных элементов преобразователей информации с двумя устойчивыми
состояниями, например “высокое или низкое напряжение”. Булеву фун-
кцию f(x
1
, x
2
, …, x
n
) называют n-местной с областью значений из мно-
жества {0, 1} и со значениями аргументов из этого же множества. Об-
ласть определения n-местной булевой функции может состоять макси-
мум из 2
n
различных наборов значений n ее аргументов (кортежи (пос-
ледовательности) из 0 и 1).
Конечность области определения и области значения булевой функ-
ции позволяет задавать функцию с помощью таблиц. Так как число
наборов аргументов равно 2
n
, а на каждом наборе функция может при-
нимать значения 0 или 1, то существует точно 2
2n
различных булевых
функций от n переменных. Число булевых функций от n переменных
растет очень быстро: при n = 1 число функций равно 4; при n = 2 число
функций равно 16; при n = 3 число функций равно 256 и т. д. Поэтому
представляют таблицы одно- и двухместных булевых функций (табл. 1
и 2), а на основе этих элементарных функций с помощью формул созда-
ют булевы функции любой сложности. Множество булевых функций от
n переменных обозначим P
n
.
Булева функция f ∈ P
n
существенно зависит от переменной x
i
, если
существует такой набор значений x
1
, …, x
i-1
, x
i
, x
i+1
, …, x
n
, что f (x
1
, …,
x
i-1
, 0, x
i+1
, …, x
n
) ≠ f (x
1
, …, x
i-1
, 1, x
i+1
, …, x
n
). В этом случае x
i
называ-
ют существенной переменной, или фиктивной (несущественной) пере-
менной, т. е. изменение значения фиктивной переменной не меняет зна-
чения функции. Например, f(x
1
, x
2
, x
3
) = g(x
1
, x
2
) означает, что при лю-
бых значениях x
1
, x
2
f = g независимо от значения x
3
. Фиктивные пере-
менные можно удалять из функции. Однако бывает полезно вводить их,
чтобы обеспечить полный набор переменных.
Страницы
- « первая
- ‹ предыдущая
- …
- 14
- 15
- 16
- 17
- 18
- …
- следующая ›
- последняя »
