1_Algebra_logiki
.pdf
Полнота и замкнутость |
Замкнутые классы |
Класс монотонных функций
Отношение предшествования
Рассмотрим два набора значений переменных x1; : : : ; xn, = ( 1; : : : ; n) è
= ( 1; : : : ; n), предшествует ( 4 ), если i 6 i, i = (1; n).
Пара наборов ( ; ) сравнимы, если один из них предшествует другому. Иначе несравнимы.
Пример
= (0; 1; 0; 1; 0; 0)
== (> = > =
= (0; 1; 1; 1; 1; 0)
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
37 / 50 |
Полнота и замкнутость |
Замкнутые классы |
Класс монотонных функций
Отношение предшествования
Рассмотрим два набора значений переменных x1; : : : ; xn, = ( 1; : : : ; n) è
= ( 1; : : : ; n), предшествует ( 4 ), если i 6 i, i = (1; n).
Пара наборов ( ; ) сравнимы, если один из них предшествует другому. Иначе несравнимы.
Пример
= (0; 1; 0; 1; 0; 0)
== ( = > = ) 4
>
= (0; 1; 1; 1; 1; 0)
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
37 / 50 |
Полнота и замкнутость |
Замкнутые классы |
Класс монотонных функций
Отношение предшествования
Рассмотрим два набора значений переменных x1; : : : ; xn, = ( 1; : : : ; n) è= ( 1; : : : ; n), предшествует ( 4 ), если i 6 i, i = (1; n).
Пара наборов ( ; ) сравнимы, если один из них предшествует другому. Иначе несравнимы.
Пример |
|
= (0; 1; 0; 1; 0; 0) |
= (1; 0; 0; 0; 1; 0) |
= = > ( = > = |
) 4 |
= (0; 1; 1; 1; 1; 0) |
= (1; 1; 0; 1; 0; 0) |
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
37 / 50 |
Полнота и замкнутость |
Замкнутые классы |
Класс монотонных функций
Отношение предшествования
Рассмотрим два набора значений переменных 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) |
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
37 / 50 |
Полнота и замкнутость |
Замкнутые классы |
Класс монотонных функций
Отношение предшествования
Рассмотрим два набора значений переменных 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) |
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
37 / 50 |
Полнота и замкнутость |
Замкнутые классы |
Класс монотонных функций
Отношение предшествования
Рассмотрим два набора значений переменных 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) |
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
37 / 50 |
Полнота и замкнутость |
Замкнутые классы |
Класс монотонных функций
Отношение предшествования
Рассмотрим два набора значений переменных 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) |
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
37 / 50 |
Полнота и замкнутость |
Замкнутые классы |
Класс монотонных функций
Отношение предшествования
Рассмотрим два набора значений переменных 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) |
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
37 / 50 |
Полнота и замкнутость |
Замкнутые классы |
Класс монотонных функций
Отношение предшествования
Рассмотрим два набора значений переменных 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) |
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
37 / 50 |
Полнота и замкнутость |
Замкнутые классы |
Класс монотонных функций
Отношение предшествования
Рассмотрим два набора значений переменных 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) |
несравнимы |
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
37 / 50 |