Применение методов дискретной математики в экономике (стр. 2 из 6)

V (2)

Любая булева функция, тождественно не равная единице представима и притом единственным образом в виде КНФ.

L (3).

Любая булева функция представима формулой, в которую входит только конъюнкция, дизъюнкция и отрицание /2/.

Искомая ДНФ для функции (1) имеет вид:

Искомая КНФ для функции (1) будет иметь следующий вид:

В расчетах ДНФ и КНФ использована методика /2/.

Построение полинома Жегалкина.

Представление булевой функции над базисом {0,1,v,Å} называется полиномом Жегалкина.

Таким образом, всякая булева функция представима в виде:

где ∑ - сложение по модулю два, знак · обозначает конъюнкцию/7/.

Для функции f(x,y,z)(1) полином Жегалкина имеет вид:

P(x, y, z)=b₀×1Åb₁×xÅb₂×yÅb₃×zÅb₄×x×yÅb₅×x×zÅb₆y×zÅb₇x×y×z

Метод неопределенных коэффициентов заключается в том, что путем последовательной подстановки переменных x, y, z и соответственно значений функции при этих переменных, из таблицы 1 в данный полином (4), строится система уравнений:

0=b₀×1Åb₁×0Åb₂×0Åb₃×0Åb₄×0×0Åb₅×0×0Åb₆0×0Åb₇0×0×0

0=b₀×1Åb₁×0Åb₂×0Åb₃×1Åb₄×0×0Åb₅×0×1Åb₆0×1Åb₇0×0×1

1=b₀×1Åb₁×0Åb₂×1Åb₃×0Åb₄×0×1Åb₅×0×0Åb₆1×0Åb₇0×1×0

0=b₀×1Åb₁×0Åb₂×1Åb₃×1Åb₄×0×1Åb₅×0×1Åb₆1×1Åb₇0×1×1

0=b₀×1Åb₁×1Åb₂×0Åb₃×0Åb₄×1×0Åb₅×1×0Åb₆0×0Åb₇1×0×0

0=b₀×1Åb₁×1Åb₂×0Åb₃×1Åb₄×1×0Åb₅×1×1Åb₆0×1Åb₇1×0×1

0=b₀×1Åb₁×1Åb₂×1Åb₃×0Åb₄×1×1Åb₅×1×0Åb₆1×0Åb₇1×1×0

0=b₀×1Åb₁×1Åb₂×1Åb₃×1Åb₄×1×1Åb₅×1×1Åb₆1×1Åb₇1×1×1

По свойству суммы по модулю два находится b:

b₀=0, b₁=0, b₂=1, b₃=0, b₄=1, b₅=0, b₆=1, b₇=1

Полином Жегалкина будет иметь вид:

¦(x, y, z) = y Å x×y Å y×z Å x×y×z

Правильность построения полинома проверяется таблицей истинности:

Таблица 4 - Таблица истинности для полинома Жегалкина

1	2	3	4	5	6	7	8	9
x	y	z	x&y	Å	y&z	Å	x&y&z	Å
0	0	0	0	0	0	0	0	0
0	0	1	0	0	0	0	0	0
0	1	0	0	1	0	1	0	1
0	1	1	0	1	1	0	0	0
1	0	0	0	0	0	0	0	0
1	0	1	0	0	0	0	0	0
1	1	0	1	0	0	0	0	0
1	1	1	1	0	1	1	1	0

Дифференцирование функции нескольких переменных.

Производной булевой функции ¦(xⁿ) по совокупности

переменных называется функция:

На основе данной формулы (5) находится производная по одной переменной x

Для данной функции (1) производная по формуле (6) принимает вид:

Таблица 5 - Производная ∂¦⁄∂xдля формулы(7)

1	2	3	4	5	6	7	8	9	10	11	12	13
x	y	z		&
0	0	0	1	0	1	1	1	0	1	0	0	0
0	0	1	1	1	1	1	1	0	1	0	0	0
0	1	0	1	0	1	0	1	0	1	1	1	0
0	1	1	1	1	1	0	0	1	1	1	0	1
1	0	0	0	0	1	1	1	0	0	1	0	1
1	0	1	0	0	1	1	1	0	0	1	0	1
1	1	0	0	0	1	0	1	0	0	0	0	0
1	1	1	0	0	1	0	0	1	1	1	0	1

Вектор значений функции (7) имеет вид:

Производная по двум переменным находится также по формуле (5):

Для данной функции (1) производная принимает вид:

Таблица 6 - Производная ∂²¦⁄∂(x;y) для формулы(9)

1	2	3	4	5	6	7	8	9	10	11	12
x			&
0	1	1	0	1	1	1	0	1	0	0	0
0	1	0	0	1	1	1	0	1	0	0	0
0	0	1	0	1	0	1	0	1	1	1	0
0	0	0	0	1	0	0	1	1	1	0	1
1	1	1	1	1	1	1	0	0	1	0	1
1	1	0	0	1	1	1	0	0	1	0	1
1	0	1	1	1	0	1	0	0	0	0	0
1	0	0	0	1	0	0	1	1	1	0	1

Вектор значений функции (6) имеет вид: