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

13-мавзу. Функциялар системасининг тўлиқлиги ва ёпиқлиги. (2-соат)
Режа:
1.Тенг кучли функция.
2.Монотон функция.
3. Функционал ёпиқ синф.
4.Пост теоремаси.
Маълумки, мантиқий амаллар мулоҳазалар алгебраси нуқтаи назаридан чинлик жадваллари билан тўлиқ характерланади. Агарда функциянинг жадвал шаклида берилишини эсга олсак, у вақтда мулоҳазалар алгебрасида ҳам функция тушунчаси мавжудлигини биламиз.
1-таъриф. Мулоҳазалар алгебрасининг аргументли функцияси деб, 0 ва 1 қиймат қабул қилувчи функцияга айтилади ва унинг аргументлари ҳам 0 ва 1 қиймат қабул қилади. Функция ўзининг чинлик жадвали билан берилади.

			...
0	0	0	...	0	0	f(0,0,...,0,0)
1	0	0	...	0	0	f(1,0,...,0,0)
...	...	...	...	...	...	...............
1	1	1	...	1	0	f(1,1,...,1,0)
1	1	1	...	1	0	f(1,1,...,1,1)

Бужадвалнингҳарбирсатридааввалўзгарувчиларнинг қийматларивашу қийматларсатрида функциянинг қийматиберилади. Олдингипараграфлардаисбот қилганэдикки, таўзгарувчиучун қийматларсатрларинингсони 2ⁿвафункцияларнингсони гатенгбўлади.

Мулоҳазалар алгебрасида асосий элементар функциялар қуйидагилардан иборат:



Агар f(0,0,.....,0)=0 бўлса, у ҳолда f(x₁,x₂,.....,x_n) функцияга 0 сақловчи функция деб айтилади. Агар бўлса, у вақтда функцияга 1 сақловчи функция деб айтамиз.
n аргументли 0 сақловчи функцияларнинг сони га ва 1 сақловчи функцияларнинг сони ҳам га тенг бўлади (исбот қилишни ўқувчига ҳавола этамиз).
Мулоҳазалар алгебрасидаги аргументли 0 сақловчи функциялар тўпламини ва 1 сақловчи функциялар тўпламини билан белгилаймиз.