lec07 производная булевой функции
.pdf
Кафедра Прикладной математики Института информационных технологий РТУ МИРЭА
Дисциплина
«Математическая логика и теория алгоритмов»
2022-2023 уч.г.
Часть 4.
Дифференциал булевой функции. Разложение Шеннона.
Дифференциалом (производной) первого порядка ∂f /∂xi – от БФ f по переменной xi называется логическое выражение:
∂f /∂xi = f (x1,x2,...,xi-1,1,xi+1,...,xn) f (x1,x2,...,xi-1,0,xi+1,...,xn),
где f (x1,x2,...,xi-1,1,xi+1,...,xn) – единичная остаточная функция; f (x1,x2,...,xi-1,0,xi+1,...,xn) – нулевая остаточная функция.
Единичная остаточная функция получается в результате приравнивания переменной xi к единице,
нулевая – приравнивания xi к нулю.
!!! Производная ∂f /∂xi определяет условия, при которых БФ f изменяет значение при инвертировании переменной xi
3
Пример 7.6. |
|
|
|
Найдем производную ∂f /∂x1 |
БФ (x1,x2,x3) = 2 3 x1 x2 x3. |
||
1 |
? |
|
( 2 3) = ? |
∂f /∂x |
= ( 2 |
3 x2 x3) |
|
= ( 2 3 x2 x3 2 3 x2 x3 ) ( 2 3) = x2 x3
(x1,x2,x3) изменяет свое значение при x2=x3=1, ( (x1,1,1)=1).
4
Конституента единицы – это такая БФ, которая принимает значение единицы только для одной комбинации значений переменных, а для остальных комбинаций значений переменных она равна нулю.
Конституента нуля – это такая БФ, которая принимает значение нуля только для одной комбинации значений переменных, а для остальных комбинаций значений переменных она равна единице.
!!! для БФ (x) имеются две конституенты единицы: |
? |
Каждая конституента единицы равна единице лишь на одном, вполне определенном наборе значений переменных. Для каждого набора имеется своя конституента, принимающая значение “1” на этом наборе и значение “0” на всех остальных наборах.
Проверим это на ТИ для (x1,x2)
5
Булева функция двух переменных. Таблица истинности элементарных функций.
x1 |
x2 |
x1 & x2 |
x1 x2 |
x1 x2 |
x1 x2 |
x1 x2 |
x1 x2 |
x1 x2 |
|
|
|
|
|
|
|
|
|
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
|
|
|
|
|
|
|
|
|
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
|
|
|
|
|
|
|
|
|
1 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
|
|
|
|
|
|
|
|
|
6
Булева функция двух переменных. Таблица истинности элементарных функций
x |
x |
≡0 |
x · |
x |
·x |
2 |
x |
|
1 |
x2 x1 ≡1 |
||
1 |
2 |
|
1 |
2 |
1 |
1 |
2 |
2 |
|
|
|
|
0 |
0 |
0 |
0 |
|
0 |
0 |
|
0 |
1 |
1 |
1 |
1 |
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
1 |
0 |
0 |
|
0 |
1 |
|
1 |
0 |
1 |
0 |
1 |
|
|
|
|
|||||||||
1 |
0 |
0 |
1 |
|
1 |
0 |
|
0 |
1 |
0 |
1 |
1 |
|
|
|
|
|||||||||
1 |
1 |
0 |
0 |
|
1 |
0 |
|
1 |
0 |
0 |
1 |
1 |
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
7
Пусть задана булева функция от n переменных (x1,x2,…xn)
Элементарная полная конъюнкция называется
конституентой единицы.
Элементарная полная дизъюнкция называется
конституентой нуля.
Для (x1,x2,…xn) общее число всех конституент единицы |
2n |
также как и общее число всех конституент нуля равно – |
? |
8
Пример 7.7.
БФ (x1,x2,x3). Выпишем все конституенты единицы и все конституенты нуля.
Конституенты единицы:
x1 x2 x3, x1 x2 x3, x1 x2 x3 , x1 x2 x3,
x1 x2 x3, x1 x2 x3, x1 x2 x3, x1 x2 x3
Конституенты нуля:
x1 x2 x3, x1 x2 x3, x1 x2 x3 , x1 x2 x3,
x1 x2 x3, x1 x2 x3, x1 x2 x3, x1 x2 x3
9
Весом производной P(∂ f /∂xi) от булевой функции f называется число конституент «1» этой производной.
!!! Чем больше вес производной, тем больше функция f (x1,…,xn) зависит от переменной xi.
Смешанной производной k-го порядка от БФ f (x1,…,xn) называется выражение вида:
|
|
|
|
|
|
|
|
|
|
|
−1 |
|
|
|||||
|
|
|
|
|
= |
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
… |
|
|
|
|
|
|
|
… |
|
|||
|
1 |
|
2 |
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
1 |
|
|
2 |
|
|
−1 |
||||
При этом порядок фиксированной переменной не имеет значения. Производная k-го порядка определяет условия, при которых эта функция изменяет свое значение при одновременном изменении значений 1, …,
10