Diskretnaya_matematika_1_semestr

Классы т0, т1.

Т0 — класс функций, сохраняющих 0 ff(0,0,...,0,0)=0

ЄТ0	&,∪,⨁,0,x
∉T0	→,│,↓,1,¬x,≡

Число наборов определяющих значение функции из класса Т0 равно 2^n-1. Поэтому всего булевых ф-ций из класса Т0 от n-переменных=2^2^n-1

Докажем, что Т0 — замкнутый класс. Для этого достаточно показать, что элементарная суперпозиция функции, принадлежащей Т0, входит в класс Т0.

f0,f1,...fkT0

ФТ0?

Ф=(y1,...,yn)=f0(f1(x11,...,x1i),...,fk(xk1,...,xkik))

Ф(0,..,0)=f0(f1(0,0,…,0),…,fk(0,0,…,0))=f0(0,0,…,0)=0

Т1 — класс функций сохраняющий 1

ff(1,1,...,1,1)=1

ЄТ1	&,∪,1 ,→,x,≡
∉T1	↓,│,¬x,0,⨁

Число булевых функций 2^n-1. Аналогично смотреть Т0 по поводу всего остального