1_Algebra_logiki
.pdf
Полнота и замкнутость |
Замкнутые классы |
Класс линейных функций
Линейный полином Жегалкина
Линейный полином
Полином Жегалкина, в котором все конъюнкции имеют ранг не более единицы (т.е. полином первой степени), называется линейным.
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
41 / 50 |
Полнота и замкнутость |
Замкнутые классы |
Класс линейных функций
Линейный полином Жегалкина
Линейный полином
Полином Жегалкина, в котором все конъюнкции имеют ранг не более единицы (т.е. полином первой степени), называется линейным.
Линейный полином
Линейным полиномом называется формула:
c0 c1x1 cnxn, ãäå ci 2 f0; 1g.
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
41 / 50 |
Полнота и замкнутость |
Замкнутые классы |
Класс линейных функций
Линейный полином Жегалкина
Линейный полином
Полином Жегалкина, в котором все конъюнкции имеют ранг не более единицы (т.е. полином первой степени), называется линейным.
Класс L класс линейных функций
Линейный полином
Линейным полиномом называется формула:
c0 c1x1 cnxn, ãäå ci 2 f0; 1g.
Функция f(x1; : : : ; xn) называется линейной ( f 2 L), если она представляется линейным полиномом Жегалкина.
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
41 / 50 |
Полнота и замкнутость |
Замкнутые классы |
Класс линейных функций
Линейный полином Жегалкина
Линейный полином
Полином Жегалкина, в котором все конъюнкции имеют ранг не более единицы (т.е. полином первой степени), называется линейным.
Класс L класс линейных функций
Линейный полином
Линейным полиномом называется формула:
c0 c1x1 cnxn, ãäå ci 2 f0; 1g.
Функция f(x1; : : : ; xn) называется |
линейной ( f 2 L), если она |
представляется линейным полиномом Жегалкина. |
|
Пример |
|
Линейные полиномы: |
Нелинейные полиномы: |
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
41 / 50 |
Полнота и замкнутость |
Замкнутые классы |
Класс линейных функций
Линейный полином Жегалкина
Линейный полином
Полином Жегалкина, в котором все конъюнкции имеют ранг не более единицы (т.е. полином первой степени), называется линейным.
Класс L класс линейных функций
Линейный полином
Линейным полиномом называется формула:
c0 c1x1 cnxn, ãäå ci 2 f0; 1g.
Функция f(x1; : : : ; xn) называется |
линейной ( f 2 L), если она |
представляется линейным полиномом Жегалкина. |
|
Пример |
|
Линейные полиномы: |
Нелинейные полиномы: |
1 x2 x5 x6 |
1 x2 x4 x5 x6 |
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
41 / 50 |
Полнота и замкнутость |
Замкнутые классы |
Класс линейных функций
Линейный полином Жегалкина
Линейный полином
Полином Жегалкина, в котором все конъюнкции имеют ранг не более единицы (т.е. полином первой степени), называется линейным.
Класс L класс линейных функций
Линейный полином
Линейным полиномом называется формула:
c0 c1x1 cnxn, ãäå ci 2 f0; 1g.
Функция f(x1; : : : ; xn) называется |
линейной ( f 2 L), если она |
||
представляется линейным полиномом Жегалкина. |
|||
Пример |
|
|
|
Линейные полиномы: |
Нелинейные полиномы: |
||
1 x2 x5 x6 |
1 x2 x4 x5 x6 |
||
x y = |
x y |
= x y 1 |
x _ y = x y x y |
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
41 / 50 |
Полнота и замкнутость |
Замкнутые классы |
Класс линейных функций
L замкнутый класс
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
42 / 50 |
Полнота и замкнутость |
Замкнутые классы |
Класс линейных функций
L замкнутый класс
Рассмотрим (x1; : : : ; xn) = f(f1(x11; : : : ; x1p1 ); : : : ; fm(xm 1; : : : ; xm pm )) ãäå f; f1; : : : ; fm 2 L.
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
42 / 50 |
Полнота и замкнутость |
Замкнутые классы |
Класс линейных функций
L замкнутый класс
Рассмотрим (x1; : : : ; xn) = f(f1(x11; : : : ; x1p1 ); : : : ; fm(xm 1; : : : ; xm pm )) ãäå f; f1; : : : ; fm 2 L.
(x1; : : : ; xn) =c0 c1f1 : : : cmfm =
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
42 / 50 |
Полнота и замкнутость |
Замкнутые классы |
Класс линейных функций
L замкнутый класс
Рассмотрим (x1; : : : ; xn) = f(f1(x11; : : : ; x1p1 ); : : : ; fm(xm 1; : : : ; xm pm )) ãäå f; f1; : : : ; fm 2 L.
(x1; : : : ; xn) =c0 c1f1 : : : cmfm =
=c0 c1 (c01 c11x11 cp11xp11) cm(: : : ):
| {z }
= f(x11; : : : ; x1p1 )
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
42 / 50 |