To’liq sistemalar. Bul funksiyasini Jekalkinko’pxadiga yoyish

6-misol. - funksiyalar sistemasi to‘liqdir. Quyidagi ayniyatlarning o‘rinli ekanlini ko‘rsatish qiyin emas.

Demak 3-misoldagi sistemaning barcha funksiyalari bu sistema ustida formula ko‘rinishida ifodalanadi.

Ixtiyoriy Bul funksiyasini funksiyalari yordamida formula ko‘rinishida ifodalagandan keyin, qavslarni ochib chiqib, algebraik almashtirishlar bajarib mod 2 bo‘yicha ko‘phad (Jegalkin ko‘phadi) ko‘rinishida ifodalanadi. Quyidagi teorema o‘rinli.

2-teorema.(Jegalkin). (32-bet)Ixtiyoriy Bul funrsiyasi Jegalkin ko‘phadi yordamida ifodalanishi mumkin, ya’ni uchun

, bu yerda .

Ushbu ko‘phadda

ko‘rinishidagi hadlar soni 1 dan n gacha bo‘lgan natural sonlar to‘plamining qism to‘plamlari soniga, ya’ni ga teng. Ularning koeffitsiyentlari faqat 0 yoki 1 qiymat qabul qilgani uchun barcha n o‘zgaruvchili Jegalkin ko‘phadlarining soni ga, ya’ni barcha n o‘zgaruvchili Bul funksiyalarining soniga teng. Bu esa Bul funksiyasini Jegalkin ko‘phadi yordamida yagona ravishda ifodalanishini bildiradi.

Misol. Ushbi funksiyani Jegalkin ko‘phadi ko‘rinishida ifodalang:



Yechish: Berilgan funksiya uchun noma’lum koeffisientli ko‘phad ko‘rinishidagi ifodasini izlaymiz:



_{Funksiyaning qiymatlar jadvalida noma’lum koeffisientlarni aniqlaymiz:}

0	0	0	1	h	h=1
0	0	1	1	g+h	g=0
0	1	0	1	f+h	f=0
0	1	1	1	d+f+g+h	d=0
1	0	0	1	e+h	e=0
1	0	1	0	c+e+g+h	c=1
1	1	0	0	b+e+f+h	b=1
1	1	1	1	a+b+c+d+e+f+g+h	a=0

_{Jadvalning 4 va 5- ustunlarini tenglashtirishdan hosil bo‘lgan tenglamalar (noma’lum koeffisientlarga nisbatan) sistemasini yechib, 6- ustunni hosil qilamiz. Demak}

To‘liqlik tushunchasi bilan yopilma va yopiq sinf tushunchalari bevosita bog‘liq hisoblanadi. (33-bet)

2-ta’rif. Aytaylik bo‘lsin. to‘plamning funksiyalari yordamida formula ko‘rinishida ifodalash mumkin bo‘lgan barcha funksiyalar to‘plamiga to‘plamning yopilmasi deyiladi. M to‘plamning yopilmasi [M] kabi belgilanadi.

Misol:1) M=P₂ bo‘lsa, ko‘rinib turibdiki [M]=P₂ bo‘ladi.

2) bo‘lsa, bu to‘plamning yopilmasi barcha chiziqli funksiyalar sinfi L, yani ko‘rinishidagi funksiyalar sinfi bo‘ladi.

3- ta’rif. Agarda M to‘plamning yopilmasi o‘ziga teng, yani [M]=M bo‘lsa, M yopiq to‘plam deyiladi.

Misol:1) M=P₂ sinf yopiq sinf bo‘ladi.

2) sinf yopiq emas.

3) L sinf yopiq.

Muhim yopiq sinflar.

Ushbu mavzuda biz ba’zi muhim yopiq sinflarni o‘rganamiz. (34-bet)

1. 
   Nolni saqlovchi barcha Bul funksiyalari sinfini orqali belgilaymiz, yani .
   

Masalan, funksiyalar T₀ sinfga tegishli bo‘ladi.

1-Jumla. T₀ – yopiq sinfdir.

Isbot. Biz ixtiyoriy funksiyalar uchun funksiyani T₀ sinfga tegishli ekanigini ko‘rsatsak yetarli. Haqiqatan

2. 
   Birni saqlovchi barcha Bul funksiyalari sinfini orqali btlgilaymiz, yani .
   

Masalan, funksiyalar T₁sinfga tegishli bo‘ladi.

2-Jumla. T₁ – yopiq sinfdir.

Isbot. Biz ixtiyoriy funksiyalar uchun funksiyani T₁ sinfga tegishli ekanigini ko‘rsatsak yetarli. Haqiqatan

3. 
   O‘z-o‘ziga dual barcha Bul funksiyalar sinfini orqali btlgilaymiz, yani .
   

Masalan, funksiyalar S sinfiga tegishli bo‘ladi.

3-Jumla. S – yopiq sinfdir.

Isbot. Biz ixtiyoriy funksiyalar uchun funksiyani S sinfga tegishli ekanigini ko‘rsatsak yetarli. Haqiqatan

Quyidagi lemma o‘z-o‘ziga dual bo‘lmagan funksiya haqidagi lemma deb yuriniladi.

1-lemma. Agar bo‘lsa, u holda ushbu funksiyadan funksiyalarni o‘rniga qo‘yish yo‘li bilan bir o‘zgaruvchili o‘z-o‘ziga dual bo‘lmagan funksiyani, yani konstantani, hosil qilish mumkin. (35-bet)

Isbot. Ayraylik bo‘lsin. U holda shunday borki tenglik o‘rinli. Quyidagi funksiyalarni qaraymiz va ular yordamida funksiyani aniqlaymiz:

Bu funksiya funksiyadan funksiyalarni o‘zgaruvchilar o‘rniga qo‘yish bilan hosil qilindi va konstantaga teng. Haqiqatan,

Lemma isbotlandi.