13-мавзу. Функциялар системасининг тўлиқлиги ва ёпиқлиги. (2-соат) Режа: Тенг кучли функция

14-таъриф. билан (n аргументли мантиқ алгебрасининг ҳамма функцияларини ўз ичига олган) тўпламнинг бирор қисм тўпламини белгилаймиз. тўплам функцияларнинг суперпозициясидан ҳосил этилган ҳамма буль функциялари тўплами ( тўплам функциялари орқали ифодаланган ҳамма буль функциялари тўплам)га тўпламнинг ёпиғи деб айтилади ва [ ] каби белгиланади.
Мисол. 1. = бўлсин, у ҳолда [ ]= .
2. ={ } бўлсин, у вақтда тўпламнинг ёпиғи ҳамма - чизиқли функциялар тўпламидан иборат бўлади.
Тўплам ёпиғи қуйидаги хоссаларга эга:
1. [ ]  ;
2. [[ ]] = [ ];
3. агар ₁ ₂ бўлса, у ҳолда [ ₁]  [ ₂] бўлади;
4. [ _{1 2}]  [ ₁] [ ₂].
15-таъриф. Агар [ ]= бўлса, у ҳолда тўплам (синф)га функционал ёпиқ синф деб айтилади.
Мисол. 1. = синфи ёпиқ синф бўлади.
2. ={ } cинфи ёпиқ синф бўлмайди.
3. - синфи ёпиқ синф бўлади.
Осонгина кўриш мумкинки, ҳар қандай [ ] синф ёпиқ синф бўлади. Бу ҳол кўпгина функционал ёпиқ синфларни топишга ёрдам беради.
Тўплам ёпиғи ва ёпиқ синф тилида функциялар системасининг тўлиқлиги ҳақидаги таъриф (аввалги таърифга эквивалент бўлган таъриф) ни бериш мумкин.
16-таъриф. Агар [ ]= бўлса, у ҳолда функция-лар системаси тўлиқ деб айтилади.
Мисол. Қуйидаги функциялар системаларининг тўлиқ эмаслигини Пост жадвали орқали исбот қилайлик:
а) ; б) ;
в) ; г) ;
_д)

а)		+	-	-	+	+
		+	+	-	-	+
		+	+	+	+	-
б)		-	+	-	+	+
		+	+	-	-	+
		+	+	+	+	-
в)		-	-	+	-	-
г)		+	-	-	+	+
		-	+	-	+	+
		+	-	-	+	-
д)		+	-	-	+	+
		-	+	-	+	+
		+	+	-	-	+

Жадвалдан кўриниб турибдики, юқорида келтирилган ҳамма функциялар системаси тўлиқ эмас, чунки ҳар бир система учун жадвалда битта устун фақатгина “+” ишораларидан иборат. Шуни таъкидлашимиз керакки, ҳар бир система учун бу устунлар ҳар хил. Демак, Пост теоремаси шартидан , , , , максимал функционал ёпиқ синфларнинг бирортасини ҳам олиб ташлаш мумкин эмас. Бу хулосадан ўз навбатида , , , , максимал функционал ёпиқ синфларнинг бирортаси иккинчисининг қисм тўплами бўла олмаслиги келиб чиқади.
Асосий дарслик ва қўлланмалар.
1. E.Mendelson Introduction to mathematical logic, fifthe edition, by Taylor &Francis Group, LLC, 2010
2. Kenneth H. Rosen, Discrete mathematics and its applications, 7- edition, The McGraw-Hill Companies, 2012
3. Ершов Ю. Л., Палютин Е. А. Математическая логика. М.: Наука, 1987.
4. Kasimov N.Kh., Dadajonov R.N., Ibragimov F.N. Diskret matematika va matematik mantiq asoslari (o’quv qullanma), Тoshkent, 2016.
5. Yunusov A.S. Matematik mantiq va algoritmlar nazariyasi elementlari, T., 2008.
6. Lavrov I. A., Maksimova L. L. Zadachi po teorii mnojestv, matematicheskoy logike i teorii algoritmov. M.: Fiz.-mat. literatura, 1995
Мустақилишлашучунсаволлар:
1. Функциялартенгкучлилиги. Функциялар суперпозицияси.
2. Функционал ёпиқ синфлар ва хусусий функционал ёпиқ синфлар.
3. Максимал функционал ёпиқ синф ва Пост теоремаси.
4. Тўплам ёпиғи ва Пост жадвали.