1_Algebra_logiki

	Полнота и замкнутость		Замкнутые классы
Замкнутые классы
Замыкание			Cвойства замыкания:
Замыканием	íàä	системой		[M]	= [M].
	ff1; : : : ; fr; : : : g ([M])		1	[P2]	2
M =			2	= P .
называется множество всех булевых
функций, представимых		формулами	3	Åñëè M N, òî [M] [N].
íàä M.
[M] обязательно содержит M.			4	[M] [ [N] [M [ N].

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

Класс M называется замкнутым если [M] = M.

Функционально полная система булевых функций

Система M полна, если ее замыкание совпадает с множеством всех булевых функций, [M] = P2.

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

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

32 / 50

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

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

Классы T0 è T1

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

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

33 / 50

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

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

Классы T0 è T1

Класс T0

Åñëè f(0; : : : ; 0) = 0, òî f 2 T0

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

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

33 / 50

Полнота и замкнутость	Замкнутые классы
Классы T0 è T1
Класс T0	Класс T1
Åñëè f(0; : : : ; 0) = 0, òî f 2 T0	Åñëè f(1; : : : ; 1) = 1, òî f 2 T1

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

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

33 / 50

Полнота и замкнутость		Замкнутые классы
Классы T0 è T1
Класс T0		Класс T1
Åñëè f(0; : : : ; 0) = 0, òî f	2 T0	Åñëè f(1; : : : ; 1) = 1, òî f 2 T1
Число функций от	n переменных в классах T0; T1,
равняется 22n 1

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

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

33 / 50

Полнота и замкнутость		Замкнутые классы
Классы T0 è T1
Класс T0		Класс T1
Åñëè f(0; : : : ; 0) = 0, òî f	2 T0	Åñëè f(1; : : : ; 1) = 1, òî f 2 T1
Число функций от	n переменных в классах T0; T1,
равняется 22n 1

T0 замкнутый класс

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

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

33 / 50

Полнота и замкнутость		Замкнутые классы
Классы 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.

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

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

33 / 50

Полнота и замкнутость		Замкнутые классы
Классы 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

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

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

33 / 50

Полнота и замкнутость		Замкнутые классы
Классы 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.

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

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

33 / 50

Полнота и замкнутость		Замкнутые классы
Классы 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

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

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

33 / 50