1_Algebra_logiki
.pdf
Полнота и замкнутость |
Замкнутые классы |
Класс монотонных функций
Отношение предшествования
Рассмотрим два набора значений переменных x1; : : : ; xn, = ( 1; : : : ; n) è
= ( 1; : : : ; n), предшествует ( 4 ), если i 6 i, i = (1; n).
Пара наборов ( ; ) сравнимы, если один из них предшествует другому. Иначе несравнимы.
Пример |
|
|
= (0; 1; 0; 1; 0; 0) |
) 4 |
= (1; 0; 0; 0; 1; 0) |
= = > ( = > = |
= > = > < |
|
= (0; 1; 1; 1; 1; 0) |
|
= (1; 1; 0; 1; 0; 0) |
Класс M класс монотонных функций
Функция f(x1; : : : ; xn) называется монотонной ( f 2 M), если для любых двух наборов и таких, что 4 , выполняется условие f( ) 6 f( ).
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
37 / 50 |
Полнота и замкнутость |
Замкнутые классы |
Класс монотонных функций
M замкнутый класс
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
38 / 50 |
Полнота и замкнутость |
Замкнутые классы |
Класс монотонных функций
M замкнутый класс
Рассмотрим (x1; : : : ; xn) = f(f1(x11; : : : ; x1p1 ); : : : ; fm(xm 1; : : : ; xm pm )), ãäå f; f1; : : : ; fm 2 M.
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
38 / 50 |
Полнота и замкнутость |
Замкнутые классы |
Класс монотонных функций
M замкнутый класс
Рассмотрим (x1; : : : ; xn) = f(f1(x11; : : : ; x1p1 ); : : : ; fm(xm 1; : : : ; xm pm )), ãäå f; f1; : : : ; fm 2 M.
= ( 1; : : : ; n), = ( 1; : : : ; n) è 4
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
38 / 50 |
Полнота и замкнутость |
Замкнутые классы |
Класс монотонных функций
M замкнутый класс
Рассмотрим (x1; : : : ; xn) = f(f1(x11; : : : ; x1p1 ); : : : ; fm(xm 1; : : : ; xm pm )), ãäå f; f1; : : : ; fm 2 M.
= ( 1; : : : ; n), = ( 1; : : : ; n) è 4
4 ) äëÿ 8 ij ij 6 ij
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
38 / 50 |
Полнота и замкнутость Замкнутые классы
Класс монотонных функций
M замкнутый класс
Рассмотрим (x1; : : : ; xn) = f(f1(x11; : : : ; x1p1 ); : : : ; fm(xm 1; : : : ; xm pm )), ãäå f; f1; : : : ; fm 2 M.
= ( 1; : : : ; n), = ( 1; : : : ; n) è 4
4 ) äëÿ 8 ij ij 6 ij
| |
|
{z |
|
} |
|
+ |
|
|
|
( 11; :::; 1p1 ) 4 |
( 11; : : : ; 1p1 ) |
|||
|
: : : |
|
|
|
( m 1; :::; m pm ) 4 |
( m 1; : : : ; m pm ) |
|||
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
38 / 50 |
Полнота и замкнутость Замкнутые классы
Класс монотонных функций
M замкнутый класс
Рассмотрим (x1; : : : ; xn) = f(f1(x11; : : : ; x1p1 ); : : : ; fm(xm 1; : : : ; xm pm )),
ãäå f; f1 |
; : : : ; fm 2 |
M. |
|
|||
= ( 1; : : : ; n), = ( 1; : : : ; n) è 4 |
f1; : : : ; fm 2 M |
|||||
4 ) äëÿ 8 ij ij 6 ij |
||||||
| |
|
|
{z |
|
} |
|
|
|
+ |
|
|
|
|
( 11 |
; :::; 1p1 ) 4 |
( 11; : : : ; 1p1 ) |
|
|||
|
|
: : : |
|
|
||
( m 1; :::; m pm ) 4 |
( m 1; : : : ; m pm ) |
|
||||
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
38 / 50 |
Полнота и замкнутость Замкнутые классы
Класс монотонных функций
M замкнутый класс
Рассмотрим (x1; : : : ; xn) = f(f1(x11; : : : ; x1p1 ); : : : ; fm(xm 1; : : : ; xm pm )),
ãäå f; f1 |
; : : : ; fm 2 |
M. |
|
|
|
|
|
|||
= ( 1; : : : ; n), = ( 1; : : : ; n) è 4 |
|
|
|
|
||||||
4 ) äëÿ 8 ij ij 6 ij |
f1; :::; fm 2 M |
|||||||||
| |
|
|
{z |
|
} |
| |
|
{z |
|
} |
|
|
+ |
|
|
|
+ |
|
|
||
( 11 |
; :::; 1p1 ) 4 |
( 11; : : : ; 1p1 ) |
f1( 11; :::; 1p1 ) 6 f1( 11; : : : ; 1p1 ) |
|||||||
|
|
: : : |
|
|
: : : |
|
|
|||
( m 1; :::; m pm ) 4 |
( m 1; : : : ; m pm ) |
fm( m 1; :::; m pm ) 6 fm( m 1; : : : m pm ) |
||||||||
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
38 / 50 |
Полнота и замкнутость Замкнутые классы
Класс монотонных функций
M замкнутый класс
Рассмотрим (x1; : : : ; xn) = f(f1(x11; : : : ; x1p1 ); : : : ; fm(xm 1; : : : ; xm pm )), ãäå f; f1; : : : ; fm 2 M.
= ( 1; : : : ; n), = ( 1; : : : ; n) è 4 |
f1; :::; fm 2 M |
||||||||
4 ) äëÿ 8 ij ij 6 ij |
|||||||||
| |
|
{z |
|
} |
| |
|
{z |
|
} |
|
+ |
|
|
+ |
|
|
|||
( 11; :::; 1p1 ) 4 ( 11; : : : ; 1p1 )
: : :
( m 1; :::; m pm ) 4 ( m 1; : : : ; m pm )
f1( 11; :::; 1p1 ) 6 f1( 11; : : : ; 1p1 )
: : :
fm( m 1; :::; m pm ) 6 fm( m 1; : : : m pm )
f(f1( 11; : : : ; 1p1 ); : : : ; fm( m 1; : : : ; m pm )) 6
f(f1( 11; : : : ; 1p1 ); : : : ; fm( m 1; : : : ; m pm )) ò.ê. f 2 M
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
38 / 50 |
Полнота и замкнутость Замкнутые классы
Класс монотонных функций
M замкнутый класс
Рассмотрим (x1; : : : ; xn) = f(f1(x11; : : : ; x1p1 ); : : : ; fm(xm 1; : : : ; xm pm )),
ãäå f; f1 |
; : : : ; fm 2 |
M. |
|
|
|
|
|
|||
= ( 1; : : : ; n), = ( 1; : : : ; n) è 4 |
|
|
|
|
||||||
4 ) äëÿ 8 ij ij 6 ij |
f1; :::; fm 2 M |
|||||||||
| |
|
|
{z |
|
} |
| |
|
{z |
|
} |
|
|
+ |
|
|
|
+ |
|
|
||
( 11 |
; :::; 1p1 ) 4 |
( 11; : : : ; 1p1 ) |
f1( 11; :::; 1p1 ) 6 f1( 11; : : : ; 1p1 ) |
|||||||
|
|
: : : |
|
|
: : : |
|
|
|||
( m 1; :::; m pm ) 4 |
( m 1; : : : ; m pm ) |
fm( m 1; :::; m pm ) 6 fm( m 1; : : : m pm ) |
||||||||
f(f1( 11; : : : ; 1p1 ); : : : ; fm( m 1; : : : ; m pm )) 6
f(f1( 11; : : : ; 1p1 ); : : : ; fm( m 1; : : : ; m pm )) ò.ê. f 2 M
) (x1; : : : ; xn) 2 M.
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
38 / 50 |