1_Algebra_logiki
.pdf
Двойственная функция
Принцип двойственности
Теорема
Пусть (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 |
|
|
|
|
||
= 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 |
|
|
|
|
||
= f(f1(x11; : : : ; x1p1 ); : : : ; fm(xm 1; : : : ; xm pm )) = 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 |
|
|
|
|
||
= f(f1(x11; : : : ; x1p1 ); : : : ; fm(xm 1; : : : ; xm pm ))
= f(f1(x11; : : : ; x1p1 ); : : : ; fm(xm 1; : : : ; xm pm )) = 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 )):
Доказательство
|
|
|
; : : : ; xn) |
|
|||||||||||
|
(x1; : : : ; xn) = (x1 |
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
= f(f1(x11; : : : ; x1p1 ); : : : ; fm(xm 1; : : : ; xm pm )) |
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
= f(f1(x11; : : : ; x1p1 ); : : : ; fm(xm 1; : : : ; xm pm )) |
|
|||||||||||||
|
= |
|
( |
|
1(x11; : : : ; x1p1 ); : : : ; |
|
|
m(xm 1; : : : ; xm pm )) |
|
||||||
|
f |
f |
f |
|
|||||||||||
|
|
f(~xn) = f(f1(~xp1 ); : : : ; fn(~xpn )) |
|
||||||||||||
|
|
f (~xn) = |
|
|
|
|
|
|
|
|
|||||
|
|
f |
(f1(~xp1 ); : : : ; fn(~xpn )) |
|
|||||||||||
Николаева Екатерина Александровна (ТГУ) |
|
|
|
Алгебра логики |
|
|
|
|
|
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 |
|
|
|
|||||||
Доказательство |
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
(x1; : : : ; xn) = (x1; : : : ; xn) |
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
||||||||
|
|
= f(f1(x11; : : : ; x1p1 ); : : : ; fm(xm 1; : : : ; xm pm )) |
||||||||||||||
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
= f(f1(x11; : : : ; x1p1 ); : : : ; fm(xm 1; : : : ; xm pm )) |
||||||||||||||
|
|
= |
|
( |
|
1(x11; : : : ; x1p1 ); : : : ; |
|
m(xm 1; : : : ; xm pm )) |
||||||||
|
|
f |
f |
f |
||||||||||||
|
|
= f (f (x11 |
; : : : ; x1p |
); : : : ; f |
(xm 1; : : : ; xm p |
m |
)) |
|||||||||
|
|
1 |
|
1 |
|
|
m |
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
Николаева Екатерина Александровна (ТГУ) |
|
|
|
Алгебра логики |
|
|
|
|
|
|
|
26 / 50 |
||||
Двойственная функция
Принцип двойственности
Теорема (принцип двойственности)
Если формула B = C[f1; : : : ; fl] реализует функцию f(x1; : : : ; xn),
òî |
формула |
B = C[f1 ; : : : ; fl ], т.е. формула, полученная из |
B |
заменой |
функций f1; : : : ; fl на двойственные им функции |
f1 ; : : : ; fl , реализует функцию f (x1; : : : ; xn).
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
27 / 50 |
Двойственная функция
Принцип двойственности
Теорема (принцип двойственности)
Если формула B = C[f1; : : : ; fl] реализует функцию f(x1; : : : ; xn),
òî |
формула |
B = C[f1 ; : : : ; fl ], т.е. формула, полученная из |
B |
заменой |
функций f1; : : : ; fl на двойственные им функции |
f1 ; : : : ; fl , реализует функцию f (x1; : : : ; xn).
Пары двойственных элементарных функций
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
27 / 50 |
Двойственная функция
Принцип двойственности
Теорема (принцип двойственности)
Если формула B = C[f1; : : : ; fl] реализует функцию f(x1; : : : ; xn),
òî |
формула |
B = C[f1 ; : : : ; fl ], т.е. формула, полученная из |
B |
заменой |
функций f1; : : : ; fl на двойственные им функции |
f1 ; : : : ; fl , реализует функцию f (x1; : : : ; xn).
Пары двойственных элементарных функций
01
|
|
x |
x |
|
|
|
|
x |
x |
|
|
|
|
x1 _ x2 |
x1 ^ x2 |
|
|
|
|
x1 x2 |
x1 x2 |
|
|
|
|
x1=x2 |
x1 # x2 |
|
|
Николаева Екатерина Александровна (ТГУ) |
|
Алгебра логики |
|
27 / 50 |
|
Двойственная функция
Принцип двойственности
Пример
Пример 1
f = xy _yz _ zx
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
28 / 50 |
Двойственная функция
Принцип двойственности
Пример
Пример 1
f = xy _yz _ zx = f_(f^(x; y); f^(y; z); f^(z; x))
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
28 / 50 |