1_Algebra_logiki

Полнота и замкнутость

Замкнутые классы

Класс самодвойственных функций

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 )) = f (f1 (x11; : : : ; x1p1 ); : : : ; fm(xm 1; : : : ; xm pm ))

Николаева Екатерина Александровна (ТГУ)

Алгебра логики

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 )) = f (f1 (x11; : : : ; x1p1 ); : : : ; fm(xm 1; : : : ; xm pm )) =

f (f1 (x11; : : : ; x1p1 ); : : : ; fm(xm 1; : : : ; xm pm ))

Николаева Екатерина Александровна (ТГУ)

Алгебра логики

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 )) = f (f1 (x11; : : : ; x1p1 ); : : : ; fm(xm 1; : : : ; xm pm )) =

f (f1 (x11; : : : ; x1p1 ); : : : ; fm(xm 1; : : : ; xm pm )) =(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 )) = f (f1 (x11; : : : ; x1p1 ); : : : ; fm(xm 1; : : : ; xm pm )) =

f (f1 (x11; : : : ; x1p1 ); : : : ; fm(xm 1; : : : ; xm pm )) =(x1; : : : ; xn)

) (x1; : : : ; xn) 2 S.

Николаева Екатерина Александровна (ТГУ)

Алгебра логики

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 )) = f (f1 (x11; : : : ; x1p1 ); : : : ; fm(xm 1; : : : ; xm pm )) =

f (f1 (x11; : : : ; x1p1 ); : : : ; fm(xm 1; : : : ; xm pm )) =(x1; : : : ; xn)

) (x1; : : : ; xn) 2 S.

) класс S замкнут.

Николаева Екатерина Александровна (ТГУ)

Алгебра логики

35 / 50

Полнота и замкнутость

Замкнутые классы

Класс самодвойственных функций

Николаева Екатерина Александровна (ТГУ)

Алгебра логики

36 / 50

Полнота и замкнутость

Замкнутые классы

Класс самодвойственных функций

Лемма о несамодвойственной функции

Если функция f(x1; : : : ; xn) 2= S, то из нее путем замены переменных на x или x можно получить несамодвойственную функцию одной переменной, то есть константу.

Николаева Екатерина Александровна (ТГУ)

Алгебра логики

36 / 50

Полнота и замкнутость

Замкнутые классы

Класс самодвойственных функций

Лемма о несамодвойственной функции

Если функция f(x1; : : : ; xn) 2= S, то из нее путем замены переменных на x или x можно получить несамодвойственную функцию одной переменной, то есть константу.

Доказательство

f 2= S ) существует такой набор значений переменных

( 1; : : : ; n), ÷òî f( 1; : : : ; n) = f( 1; : : : ; n)

Николаева Екатерина Александровна (ТГУ)

Алгебра логики

36 / 50

Полнота и замкнутость

Замкнутые классы

Класс самодвойственных функций

Лемма о несамодвойственной функции

Если функция f(x1; : : : ; xn) 2= S, то из нее путем замены переменных на x или x можно получить несамодвойственную функцию одной переменной, то есть константу.

Доказательство

f 2= S ) существует такой набор значений переменных

( 1; : : : ; n), ÷òî f( 1; : : : ; n) = f( 1; : : : ; n)

Самодвойственная функция на противоположных наборах принимает противоположные значения

Николаева Екатерина Александровна (ТГУ)

Алгебра логики

36 / 50

Полнота и замкнутость

Замкнутые классы

Класс самодвойственных функций

Лемма о несамодвойственной функции

Если функция f(x1; : : : ; xn) 2= S, то из нее путем замены переменных на x или x можно получить несамодвойственную функцию одной переменной, то есть константу.

Доказательство

f 2= S ) существует такой набор значений переменных

( 1; : : : ; n), ÷òî f( 1; : : : ; n) = f( 1; : : : ; n) '(x) = f(x 1 ; : : : ; x i; : : : ; x n)

Николаева Екатерина Александровна (ТГУ)

Алгебра логики

36 / 50