1_Algebra_logiki
.pdf
Полнота и замкнутость |
Замкнутые классы |
|
Классы T0 è T1 |
|
|
Класс T0 |
|
Класс T1 |
Åñëè f(0; : : : ; 0) = 0, òî f |
2 T0 |
Åñëè f(1; : : : ; 1) = 1, òî f 2 T1 |
Число функций от |
n переменных в классах T0; T1, |
|
равняется 22n 1 |
|
|
T0 замкнутый класс
(x1; : : : ; xn) = f(f1(x11; : : : ; x1p1 ); : : : ; fm(xm 1; : : : ; xm pm )), ãäå f; f1; : : : ; fm 2 T0.
Тогда |
(0; : : : ; 0) |
= |
f(f1(0; : : : ; 0); : : : ; fm(0; : : : ; 0)) |
= f(0; : : : ; 0) = 0 |
|
|
|
) (x1; : : : ; xn) 2 T0.
) любая формула, являющаяся суперпозицией функций из T0, представляет функцию из T0
) класс T0 замкнут.
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
33 / 50 |
Полнота и замкнутость |
Замкнутые классы |
Класс самодвойственных функций
Класс S класс самодвойственных функций Åñëè f(x1; : : : ; xn) = f (x1; : : : ; xn) òî f 2 S
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
34 / 50 |
Полнота и замкнутость |
Замкнутые классы |
Класс самодвойственных функций
Класс S класс самодвойственных функций Åñëè f(x1; : : : ; xn) = f (x1; : : : ; xn) òî f 2 S
Определение
Наборы ( 1; : : : ; n) è ( 1; : : : ; n)
называются противоположными.
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
34 / 50 |
Полнота и замкнутость |
Замкнутые классы |
Класс самодвойственных функций
Класс S класс самодвойственных функций Åñëè f(x1; : : : ; xn) = f (x1; : : : ; xn) òî f 2 S
Определение
Наборы ( 1; : : : ; n) è ( 1; : : : ; n)
называются противоположными.
Свойства самодвойственной функции
Самодвойственная |
функция |
на противоположных |
наборах |
принимает противоположные значения.
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
34 / 50 |
Полнота и замкнутость |
Замкнутые классы |
Класс самодвойственных функций
Класс S класс самодвойственных функций Åñëè f(x1; : : : ; xn) = f (x1; : : : ; xn) òî f 2 S
Определение
Наборы ( 1; : : : ; n) è ( 1; : : : ; n)
называются противоположными.
Свойства самодвойственной функции
Самодвойственная функция на противоположных наборах принимает противоположные значения.
Число самодвойственных функций от n переменных равно 22n 1 .
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
34 / 50 |
Полнота и замкнутость |
Замкнутые классы |
Класс самодвойственных функций
Класс S класс самодвойственных функций Åñëè f(x1; : : : ; xn) = f (x1; : : : ; xn) òî f 2 S
Определение
Наборы ( 1; : : : ; n) è ( 1; : : : ; n)
называются противоположными.
Свойства самодвойственной функции
Самодвойственная функция на противоположных наборах принимает противоположные значения.
Число самодвойственных функций от n переменных равно 22n 1 .
Пример
x1 x2 |
x1x2 _ x1x3 _ x2x3 |
f |
0 0 0 |
0 |
0 |
0 0 1 |
0 |
0 |
|
|
|
0 1 0 |
0 |
0 |
0 1 1 |
1 |
1 |
|
|
|
1 0 0 |
0 |
0 |
1 0 1 |
1 |
1 |
|
|
|
1 1 0 |
1 |
1 |
1 1 1 |
1 |
1 |
|
|
|
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
34 / 50 |
Полнота и замкнутость |
Замкнутые классы |
Класс самодвойственных функций
S замкнутый класс
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
35 / 50 |
Полнота и замкнутость |
Замкнутые классы |
Класс самодвойственных функций
S замкнутый класс
(x1; : : : ; xn) = f(f1(x11; : : : ; x1p1 ); : : : ; fm(xm 1; : : : ; xm pm )), ãäå f; f1; : : : ; fm 2 S.
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
35 / 50 |
Полнота и замкнутость |
Замкнутые классы |
Класс самодвойственных функций
S замкнутый класс
(x1; : : : ; xn) = f(f1(x11; : : : ; x1p1 ); : : : ; fm(xm 1; : : : ; xm pm )), ãäå f; f1; : : : ; fm 2 S.
Тогда:
(x1; : : : ; xn)
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
35 / 50 |
Полнота и замкнутость |
Замкнутые классы |
Класс самодвойственных функций
S замкнутый класс
(x1; : : : ; xn) = f(f1(x11; : : : ; x1p1 ); : : : ; fm(xm 1; : : : ; xm pm )), ãäå f; f1; : : : ; fm 2 S.
Тогда:
(x1; : : : ; xn) =f (f1 (x11; : : : ; x1p1 ); : : : ; fm(xm 1; : : : ; xm pm ))
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
35 / 50 |