1_Algebra_logiki
.pdf
Двойственная функция
Двойственная функция
Двойственная функция
Функция f (x1; : : : ; xn) называется двойственной к функции f(x1; : : : ; xn), åñëè
f (x1; : : : ; xn) = f(x1; : : : ; xn).
|
x1 x2 x3 |
f(x1; x2; x3) |
|
|||||
|
0 |
0 |
0 |
|
1 |
|
|
|
|
0 |
0 |
1 |
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
1 |
0 |
|
1 |
|
|
|
|
0 |
1 |
1 |
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
0 |
0 |
|
0 |
|
|
|
|
1 |
0 |
1 |
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
0 |
|
1 |
|
|
|
|
1 |
1 |
1 |
|
1 |
|
|
|
|
|
|
||||||
Николаева Екатерина Александровна (ТГУ) |
|
Алгебра логики |
25 / 50 |
|||||
Двойственная функция
Двойственная функция
Двойственная функция
Функция f (x1; : : : ; xn) называется двойственной к функции f(x1; : : : ; xn), åñëè
f (x1; : : : ; xn) = f(x1; : : : ; xn).
|
x1 x2 x3 |
f(x1; x2; x3) |
|
|||||
|
0 |
0 |
0 |
|
1 |
|
|
|
|
0 |
0 |
1 |
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
1 |
0 |
|
1 |
|
|
|
|
0 |
1 |
1 |
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
0 |
0 |
|
0 |
|
|
|
|
1 |
0 |
1 |
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
0 |
|
1 |
|
|
|
|
1 |
1 |
1 |
|
1 |
|
|
|
|
|
|
||||||
Николаева Екатерина Александровна (ТГУ) |
|
Алгебра логики |
25 / 50 |
|||||
Двойственная функция
Двойственная функция
Двойственная функция
Функция f (x1; : : : ; xn) называется двойственной к функции f(x1; : : : ; xn), åñëè
f (x1; : : : ; xn) = f(x1; : : : ; xn).
|
x1 x2 x3 |
f(x1; x2; x3) |
|
|||||
|
0 |
0 |
0 |
|
1 |
|
|
|
|
0 |
0 |
1 |
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
1 |
0 |
|
1 |
|
|
|
|
0 |
1 |
1 |
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
0 |
0 |
|
0 |
|
|
|
|
1 |
0 |
1 |
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
0 |
|
1 |
|
|
|
|
1 |
1 |
1 |
|
1 |
|
|
|
|
|
|
||||||
Николаева Екатерина Александровна (ТГУ) |
|
Алгебра логики |
25 / 50 |
|||||
Двойственная функция
Двойственная функция
Двойственная функция
Функция f (x1; : : : ; xn) называется двойственной к функции f(x1; : : : ; xn), åñëè
f (x1; : : : ; xn) = f(x1; : : : ; xn).
|
x1 x2 x3 |
f(x1; x2; x3) |
|
f(x1; x2; x3) |
|
|
|||
|
0 |
0 |
0 |
1 |
|
1 |
|
|
|
|
0 |
0 |
1 |
0 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
1 |
0 |
1 |
|
0 |
|
|
|
|
0 |
1 |
1 |
0 |
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
0 |
0 |
0 |
|
0 |
|
|
|
|
1 |
0 |
1 |
0 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
0 |
1 |
|
0 |
|
|
|
|
1 |
1 |
1 |
1 |
|
1 |
|
|
|
|
|
|
|
|
|||||
Николаева Екатерина Александровна (ТГУ) |
|
Алгебра логики |
|
25 / 50 |
|||||
Двойственная функция
Двойственная функция
Двойственная функция |
|
|
|
|
|
|
||||||
Функция |
f (x1; : : : ; xn) называется двойственной |
к функции |
||||||||||
f(x1; : : : ; xn), åñëè |
|
|
|
|
|
|
||||||
|
|
|
|
|
f (x1; : : : ; xn) = f(x1; : : : ; xn). |
|
|
|||||
|
x1 x2 x3 |
|
f(x1; x2; x3) |
|
f(x1; x2; x3) f (x1; : : : ; xn) |
|||||||
|
|
|
||||||||||
|
0 |
0 |
0 |
|
1 |
|
1 |
|
|
0 |
|
|
|
0 |
0 |
1 |
|
0 |
|
1 |
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
1 |
0 |
|
1 |
|
0 |
|
|
1 |
|
|
|
0 |
1 |
1 |
|
0 |
|
0 |
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
0 |
0 |
|
0 |
|
0 |
|
|
1 |
|
|
|
1 |
0 |
1 |
|
0 |
|
1 |
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
1 |
0 |
|
1 |
|
0 |
|
|
1 |
|
|
|
1 |
1 |
1 |
|
1 |
|
1 |
|
|
0 |
|
|
|
|
|
|
|
|
|||||||
Николаева Екатерина Александровна (ТГУ) |
|
Алгебра логики |
|
|
25 / 50 |
|||||||
Двойственная функция
Принцип двойственности
(x1; : : : ; xn) = f(f1(x11; : : : ; x1p1 ); : : : ; fm(xm 1; : : : ; xm pm ))
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
26 / 50 |
Двойственная функция
Принцип двойственности
(x1; : : : ; xn) = f(f1(x11; : : : ; x1p1 ); : : : ; fm(xm 1; : : : ; xm pm ))
fx11; : : : ; x1p1 g fx1; : : : ; xng;
fxm 1; : : : ; xm pm g fx1; : : : ; xng:
fx11; : : : ; x1p1 g [ [ fxm 1; : : : ; xm pm g = fx1; : : : ; xng:
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
26 / 50 |
Двойственная функция
Принцип двойственности
(x1; : : : ; xn) = f(f1(x11; : : : ; x1p1 ); : : : ; fm(xm 1; : : : ; xm pm ))
fx11; : : : ; x1p1 g fx1; : : : ; xng;
fxm 1; : : : ; xm pm g fx1; : : : ; xng:
fx11; : : : ; x1p1 g [ [ fxm 1; : : : ; xm pm g = fx1; : : : ; xng:
Теорема
Пусть (x1; : : : ; xn) = f(f1(x11; : : : ; x1p1 ); : : : ; fm(xm 1; : : : ; xm pm )), xij 2 fx1; : : : ; xng для любых i; j. Тогда:
(x1; : : : ; xn) = f (f1 (x11; : : : ; x1p1 ); : : : ; fm(xm 1; : : : ; xm pm )):
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
26 / 50 |
Двойственная функция
Принцип двойственности
Теорема
Пусть (x1; : : : ; xn) = f(f1(x11; : : : ; x1p1 ); : : : ; fm(xm 1; : : : ; xm pm )), xij 2 fx1; : : : ; xng для любых i; j. Тогда:
(x1; : : : ; xn) = f (f1 (x11; : : : ; x1p1 ); : : : ; fm(xm 1; : : : ; xm pm )):
Доказательство
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
26 / 50 |
Двойственная функция
Принцип двойственности
Теорема
Пусть (x1; : : : ; xn) = f(f1(x11; : : : ; x1p1 ); : : : ; fm(xm 1; : : : ; xm pm )), xij 2 fx1; : : : ; xng для любых i; j. Тогда:
(x1; : : : ; xn) = f (f (x11 |
; : : : ; x1p |
); : : : ; f |
(xm 1; : : : ; xm p |
m |
)): |
||
|
1 |
|
1 |
m |
|
|
|
Доказательство |
|
|
|
|
|
|
|
|
|
; : : : ; xn) |
|
|
|
|
|
|
(x1; : : : ; xn) = (x1 |
|
|
|
|
||
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
26 / 50 |