Лаборатория2

8-таъриф. Агар [ ]= бœлса, у ќолда функциялар системаси тœлиš деб айтилади.
Мисол. Куйидаги функциялар системаларининг тœлиš эмаслигини Пост жадвали орšали исбот šилайлик:
а) ; б) ;
в) ; г) ;
д)

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

Жадвалдан кœриниб турибдики, юšорида келтирилган ќамма функциялар системаси тœлиš эмас, чунки ќар бир система учун жадвалда битта устун фаšатгина “+” ишораларидан иборат. Шуни таъкидлашимиз керакки, ќар бир система учун бу устунлар ќар хил. Демак, Пост теоремаси шартидан , , , , максимал функционал ёпиš синфларнинг бирортасини хам олиб ташлаш мумкин эмас. Бу хулосадан œз навбатида , , , , максимал функционал ёпиš синфларнинг бирортаси иккинчисининг šисм тœплами бœла олмаслиги келиб чиšади.
1.3 Берилган мисол ёрдамида амалий кўрсатмалар.
Ф={ } функциялар синфининг тўлиšлигини Пост жадвали ёрдамида текширинг.
1-šадам. Пост жадвали орšали берилган функциялар синфини тўлиšлигини текшириш учун, системадаги барча функцияларнинг чинлик жадвалини тузамиз

					1
0	0	0	1	1	1
0	1	1	1	1	1
1	0	1	0	0	1
1	1	1	1	0	1

2- šадам. Берилган функцияларнинг P₀ , P₁, L, S, M функционал ёпиš синфларга тегишлилигини юšоридаги чинлик жадвалидан аниšлаймиз. Функциямиз P₀ –ноль саšловчи функциялар синфига кириши учун аргументларнинг барчаси бир ваšтда ёлђон šиймат šабул šилганда функция ќам ёлђон šиймат šабул šилиши керак. Чинлик жадвалидан кўриниб турибдики фаšат функция ноль саšловчи, šолган функцияларимиз ноль саšловчи эмас. Пост жадвалида мос устунни тўлдирамиз.

	P0	P1	L	S	М
	+
	-
	-
1	-

3- šадам. Функция P₁ –бир саšловчи функциялар синфига кириши учун аргументларнинг барчаси бир ваšтда чин šиймат šабул šилганда функция ќам чин šиймат šабул šилиши керак. Чинлик жадвалидан кўриниб турибдики фаšат функция бир саšловчи эмас, šолган функцияларнинг барчаси бир саšловчи. Пост жадвалида мос устунни тўлдирамиз.

	P0	P1	L	S	М
	+	+
	-	+
	-	-
1	-	+

4- šадам Энди системадаги функцияларни L- чизиšли функциялар синфига тегишли ёки тегишли эмаслигини текширамиз. Бунинг учун функцияларнинг Жегалкин кўпќади кўринишини ќосил šиламиз. Кўпќадда кўпайтириш амали иштирок этмаса, бундай функция чизиšли бўлади

Кўриниб турибдики ва функциялар чизиšли эмас, ва 1 чизиšли. Пост жадвалида мос устунни тўлдирамиз

	P0	P1	L	S	М
	+	+	-
	-	+	-
	-	-	+
1	-	+	+

5- šадам. Чинлик жадвали ёрдамида функцияларнинг S-ўз –ўзига šўшма функциялар синфига киришини текширамиз. Буни 3 хил усулда амалга ошириш мумкин
1-усул. Чинлик жадвалида функцияларни šийматлари сатрини чизиš билан ўртасидан ажратиб, шу чизиššа нисбатан šийматларнинг симметриклигини текширамиз

					1
0	0	0	1	1	1
0	1	1	1	1	1
1	0	1	0	0	1
1	1	1	1	0	1

2- усул. Чинлик жадвалида функция šийматлирини тескари œгириб, (кœшмалик принципига кœра) инкорларини олганда функциянинг чинлик šиймати билан мос тушса, бу функция œз-œзига šœшма бœлади
3-усул. функцияга šœшма функцияни топиш учун функциянинг барча œзгарувчиларини ва функцияни инкорини топиш керак. Агар = бœлса, функция œз-œзига иккитарафлама ёки œз-œзига šœшма функция дейилади
, демак бу функция œз-œзига šœшма эмас.
, демак бу функция œз-œзига šœшма эмас.
бу холда, бу функция œз-œзига šœшма функция бœлади. 1 га šœшма функция 0 бœлади

	P0	P1	L	S	М
	+	+	-	-
	-	+	-	-
	-	-	+	+
1	-	+	+	-

6-šадам. Функциялар системасидаги функцияларни монотонлигини текширамиз. Функция монотон бœлиши учун барча ларда шарт бажарилиши керак. Чинлик жадвалидан кœриниб турибдики монотон, номонотон, номонотон, 1 монотон бœлади.

	P0	P1	L	S	М
	+	+	-	-	+
	-	+	-	-	-
	-	-	+	+	-
1	-	+	+	-	+

Пост жадвалнинг барча устунларида камида биттадан «-» ишора šатнашган, яъни максимал функционол синфларга кирмайдиган камида биттадан функция мавжуд. Демак кœрилган функциялар системаси тœлиš.