1_Algebra_logiki
.pdf
Полиномы
Полином Жегалкина
Полином Жегалкина
L
Формула ai1;:::;im(xi1 : : : xim) называется полиномом
(i1;:::;im)
Жегалкина булевой функции, коэффициенты ai1;:::;im 2 f0; 1g определяют, какие конъюнкции входят в полином.
1 |
_ |
x |
2 |
= x |
1 |
|
2 |
1 |
2 |
x1 xn = |
(x1; |
n - нечетно. |
x |
|
|
|
x |
|
x x |
|
|
0; |
n - четно, |
||
x1(x2 x3) = x1x2 x1x3 |
|
|
|
|||||||||
x1 |
1 = x1 |
|
|
|
|
|
|
|
|
|||
Пример
f = x1x2 _ x1x3 _x2x3 = (x1x2 x1x3 x1x2x3) _x2x3 = (x1x2 x1x3 x1x2x3) x2x3 (x1x2 x1x3 x1x2x3)x2x3
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
21 / 50 |
Полиномы
Полином Жегалкина
Полином Жегалкина
L
Формула ai1;:::;im(xi1 : : : xim) называется полиномом
(i1;:::;im)
Жегалкина булевой функции, коэффициенты ai1;:::;im 2 f0; 1g определяют, какие конъюнкции входят в полином.
1 |
_ |
x |
2 |
= x |
1 |
|
2 |
1 |
2 |
x1 xn = |
(x1; |
n - нечетно. |
x |
|
|
|
x |
|
x x |
|
|
0; |
n - четно, |
||
x1(x2 x3) = x1x2 x1x3 |
|
|
|
|||||||||
x1 |
1 = x1 |
|
|
|
|
|
|
|
|
|||
Пример
f = x1x2 _ x1x3 _x2x3 = (x1x2 x1x3 x1x2x3) _x2x3 = (x1x2 x1x3 x1x2x3) x2x3 (x1x2 x1x3 x1x2x3)x2x3
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
21 / 50 |
Полиномы
Полином Жегалкина
Полином Жегалкина
L
Формула ai1;:::;im(xi1 : : : xim) называется полиномом
(i1;:::;im)
Жегалкина булевой функции, коэффициенты ai1;:::;im 2 f0; 1g определяют, какие конъюнкции входят в полином.
1 |
_ |
x |
2 |
1 |
2 |
1 |
2 |
x1 xn = |
(x1; |
n - нечетно. |
x |
|
|
= x |
x |
x x |
|
|
0; |
n - четно, |
|
x1(x2 x3) = x1x2 x1x3 |
|
|
|
|||||||
x1 |
1 = x1 |
|
|
|
|
|
|
|||
Пример |
|
|
|
|
|
|
|
|
||
f = x1x2 _ x1x3 _x2x3 = (x1x2 x1x3 x1x2x3) _x2x3 =
(x1x2 x1x3 x1x2x3) x2x3 (x1x2 x1x3 x1x2x3)x2x3 =x1x2 x1x3 x1x2x3 x2x3 x1x2x3 x1x2x3 x1x2x3
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
21 / 50 |
Полиномы
Полином Жегалкина
Полином Жегалкина
L
Формула ai1;:::;im(xi1 : : : xim) называется полиномом
(i1;:::;im)
Жегалкина булевой функции, коэффициенты ai1;:::;im 2 f0; 1g определяют, какие конъюнкции входят в полином.
1 |
_ |
x |
2 |
1 |
2 |
1 |
2 |
x1 xn = |
(x1; |
n - нечетно. |
x |
|
|
= x |
x |
x x |
|
|
0; |
n - четно, |
|
x1(x2 x3) = x1x2 x1x3 |
|
|
|
|||||||
x1 |
1 = x1 |
|
|
|
|
|
|
|||
Пример |
|
|
|
|
|
|
|
|
||
f = x1x2 _ x1x3 _x2x3 = (x1x2 x1x3 x1x2x3) _x2x3 =
(x1x2 x1x3 x1x2x3) x2x3 (x1x2 x1x3 x1x2x3)x2x3 =x1x2 x1x3 x1x2x3 x2x3 x1x2x3 x1x2x3 x1x2x3
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
21 / 50 |
Полиномы
Полином Жегалкина
Полином Жегалкина
L
Формула ai1;:::;im(xi1 : : : xim) называется полиномом
(i1;:::;im)
Жегалкина булевой функции, коэффициенты ai1;:::;im 2 f0; 1g определяют, какие конъюнкции входят в полином.
1 |
_ |
x |
2 |
1 |
2 |
1 |
2 |
x1 xn = |
(x1; |
n - нечетно. |
x |
|
|
= x |
x |
x x |
|
|
0; |
n - четно, |
|
x1(x2 x3) = x1x2 x1x3 |
|
|
|
|||||||
x1 |
1 = x1 |
|
|
|
|
|
|
|||
Пример |
|
|
|
|
|
|
|
|
||
f = x1x2 _ x1x3 _x2x3 = (x1x2 x1x3 x1x2x3) _x2x3 =
(x1x2 x1x3 x1x2x3) x2x3 (x1x2 x1x3 x1x2x3)x2x3
=x1x2 x1x3 x1x2x3 x2x3 x1x2x3 x1x2x3 x1x2x3 = x1x2 x1x3 x2x3
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
21 / 50 |
Полиномы
Полином Жегалкина
Полином Жегалкина
L
Формула ai1;:::;im(xi1 : : : xim) называется полиномом
(i1;:::;im)
Жегалкина булевой функции, коэффициенты ai1;:::;im 2 f0; 1g определяют, какие конъюнкции входят в полином.
1 |
_ |
x |
2 |
1 |
2 |
1 |
2 |
x1 xn = |
(x1; |
n - нечетно. |
x |
|
|
= x |
x |
x x |
|
|
0; |
n - четно, |
|
x1(x2 x3) = x1x2 x1x3 |
|
|
|
|||||||
x1 |
1 = x1 |
|
|
|
|
|
|
|||
Пример |
|
|
|
|
|
|
|
|
||
f = x1x2 _ x1x3 _x2x3 = (x1x2 x1x3 x1x2x3) _x2x3 =
(x1x2 x1x3 x1x2x3) x2x3 (x1x2 x1x3 x1x2x3)x2x3
=x1x2 x1x3 x1x2x3 x2x3 x1x2x3 x1x2x3 x1x2x3 = x1x2 x1x3 x2x3
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
21 / 50 |
Полиномы
Метод неопределенных коэффициентов
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
22 / 50 |
Полиномы
Метод неопределенных коэффициентов
P (~xn) = |
ai1;:::;im (xi1 : : : xim ) |
(i1 Lm |
) |
;:::;i |
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
22 / 50 |
Полиномы
Метод неопределенных коэффициентов
P (~xn) = |
ai1;:::;im (xi1 : : : xim ) |
(i1 Lm |
) |
;:::;i |
|
P (~xn) = a0 1 a1x1 a2x2 |
a1;2x1x2 a1;:::;nx1 : : : xn |
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
22 / 50 |
Полиномы
Метод неопределенных коэффициентов
P (~xn) = |
|
ai1;:::;im (xi1 : : : xim ) |
(i1 Lm |
) |
|
;:::;i |
|
|
P (~xn) = a0 1 a1x1 a2x2 |
a1;2x1x2 a1;:::;nx1 : : : xn |
|
P (0; : : : ; 0; 0; 0) = a0 0 = a0 |
|
|
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
22 / 50 |