Umumiy doc

 
Bitta argumentning bul funksiyalari 
x 
f
1 
f
2 
f
3 
f
4 
0 
0 
0 
1 
1 
1 
0 
1 
0 
1 
f
1 
– funksiya – nol konstanta deyiladi, 
f
4 
– birlik konstanta, 
f
2
– takrorlash, 
f
3
– 
inkor qilish yoki inversiya deyiladi. 
Bul funksiyalar soni (19.11) ifoda bo‘yicha ikki argument uchun 16 ga teng. 
Bu funksiyalarning hammasini jadval ko‘rinishida ifodalaymiz, uning chap qismida 
argument qiymatlarini tanlashning imkoni bo‘lgan hamma to‘plamlari ko‘rsatilgan, 
o‘ng tomonida esa argumentlarning mazkur to‘plamlariga mos keluvchi bul 
funksiyalari qiymatlari ko‘rsatilgan:
1
X
2
X
1
f
2
f
3
f
4
f
5
f
6
f
7
f
8
f
9
f
10
f
11
f
12
f
13
f
14
f
15
f
16
f
PDF created with pdfFactory Pro trial version 
www.pdffactory.com

---

514 
0 
0 
0 
0 
1 
1 
1 
0 
1 
1 
0 
0 
0 
1 
0 
1 
1 
0 
1 
0 
0 
1 
0 
1 
0 
1 
1 
0 
1 
0 
1 
0 
1 
1 
1 
0 
1 
1 
1 
1 
1 
1 
1 
0 
0 
0 
0 
0 
1 
0 
1 
0 
1 
0 
Bu funksiyalarning belgilanishi va nomlarini quyidagicha izohlash mumkin: 
Funksiyaning belgilanishi 
Funksiyaning nomi 
2
1
1
x
x
f
⋅
=
2
1
2
vx
x
f
=
2
1
3
x
x
f
→
=
2
1
4
x
x
f
←
=
2
1
5
~
x
x
f
=
2
1
6
x
x
f
=
2
1
7
/
x
x
f
=
2
1
8
/
x
x
f
=
2
1
9
x
x
f
−
−
−
→
=
2
1
10
x
x
f
−
−
−
→
=
1
11
x
f
=
1
12
x
f
=
2
13
x
f
=
2
14
x
f
=
1
15
=
f
0
16
=
f
Ko‘paytirish, konyunksiya, VA funksiyasi
∑
Qo‘shish, diz’yunksiy, YOKI funksiyasi, 
∑
1
Х
ning 
2
Х
ga implikasiyasi 
2
Х
ning
1
Х
ga implikasiyasi 
Ekvivalentlik, mos kelish 
Teng qiymatli emaslik, 2 modul bo‘yicha 
qo‘shish, mod 2 
SHeffer funksiyaci, SHeffer shtrixi, YO‘Q- VA 
funksillari. 
Vebb funksiyasi. Pirs strelkasi, YO‘Q-
YOKIfunksiyalari 
1
Х
ni man qilish funksiyasi 
2
Х
ni ma’n qilish funksiyasi 
1
Х
ning takrorlanishi 
1
Х
ning inversiyasi 
2
Х
ning takrorlanishi
2
Х
ning inversiyasi 
Birlik konstanta 
Nol konstanta 
n
= 3 uchun bul funksiyalari soni 256 ga teng bo‘lishi ravshan. 
Ikki argument uchun olingan funksiyalarni tahlil qilish shuni ko‘rsatadiki, ba’zi 
funksiyalar boshqalari orqali aniqlanishi mumkin ekan. Masalan, Vebb funksiyasi 
PDF created with pdfFactory Pro trial version 
www.pdffactory.com

---

515 
2
8
x
f
=
1
2
1
2
,
:
x
x
x
x
=
ning 
2
x
ga implikasiyasi 
2
1
2
1
3
Vx
x
x
x
f
=
→
=
ko‘rinishda yozilishi 
mumkin. Demak, Bul funksiyalarining bitta yoki ikkita argumentdan iborat minimal 
to‘plami mavjud bo‘lib, uning yordamida istalgan (ammo chekli) sondagi
argumentlarning hamma ixtiyoriy bul funksiyalarini ifodalash mumkin. 
Funksiyalarning bunga o‘xshash to‘plami 
funksional to‘liq
funksiyalar deyiladi.
To‘plamning funksional to‘liqligi bul funksiyalarining maxsus xossalarini o‘rganish 
yo‘li bilan aniqlanadi. Funksional to‘liq to‘plamlar qatoriga quyidagilar kiradi: 1)
kon’yunksiya, diz’yunksiya, inkor qilish; 2) SHeffer funksiyasi 3) Vebb 
funksiyasi; 4) 
x
, ma’n qilish funksiyasi, birlik konstanta, implikasiya va hokazo. 
Funksional to‘liq to‘plamlar bazis (asos) deb ham ataladi. Amalda quyidagilar eng 
ko‘p tarqalgan:
VA
— 
YOKI
— 
YO‘Q
bazisi; SHeffer funksiyasi; Vebb funksiyasi. 
Nazariy tadqiqotlarning eng katta soni 
VA
— 
YOKI
—
YO‘Q 
bazisida (asosida)
bajarilgan. SHuning uchun, biz bundan keyin bul funksiyalarini shu asosda qarab 
chiqamiz. 
Bul funksiyalarining kanonik shakllarini aniqlaymiz. Buning uchun SHennon 
yoyilmasi tenglamasini isbotsiz keltiramiz. 
Teorema.
Istagan 
)
,...
,
,
(
3
2
1
n
x
x
x
x
f
bul funksiyasi quyidagi ko‘rinishda 
ifodalanishi mumkin:
1
3
2
1
3
2
2
1
)
...,
,
,
0
(
)
,....,
,
,
1
(
)
,...,
,
(
x
x
x
x
f
v
x
x
x
x
f
x
x
x
n
n
n
⋅
⋅
=
(19.12) 
Agar SHennon teoremasi diz’yunksiya bilan ajratilgan chap va o‘ng qismlar 
uchun alohida 
2
x
o‘zgaruvchi uchun, keyin esa 
3
x
uchun va shunday davom etib 
n
x
gacha qo‘llanilsa, u holda quyidagi ifodani hosil qilamiz: 
)
...,
(
)
0
,..,
0
,
0
,
0
(
...
)
...,
(
)
1
,...,
1
,
1
,
0
(
)
...,
(
)
1
,...,
1
,
1
,
1
(
)
...,
,
,
(
3
2
1
3
2
1
3
2
1
3
2
1
n
n
n
n
x
x
x
x
vf
v
x
x
x
x
vf
x
x
x
x
f
x
x
x
x
f
⋅
⋅
⋅
⋅
⋅
⋅
⋅
⋅
⋅
⋅
⋅
⋅
⋅
⋅
⋅
⋅
⋅
⋅
=
(19.13) 
Bul funksiyasining bunday ifodalanishi diz’yunktiv, normal shakli (DMNSH) 
deyiladi. (19.13) ifodani tahlil qilish istagan bul funksiyasi DMNSH kanonik 
ko‘rinishiga yoyilishi mumkinligini ko‘rsatadi. U ma’lum nuqtadagi funksiya 
qiymatining hamma argumentlar kon’yuksiyasiga yoki ularning inkorlariga 
ko‘paytmasidan iborat hadlar birlashmasi (diz’yunksiyasi) bo‘lib, shu bilan birga 
PDF created with pdfFactory Pro trial version 
www.pdffactory.com

---

516 
nuqta koordinatalari bilan argumentlar kon’yuksiyasi o‘rtasida qat’iy bir qiymatli 
moslik mavjud bo‘ladi. Masalan, 4 argumentli bul funksiyasi uchun (0, 0, 1, 1) 
koordinataga 
)
,
,
,
(
4
3
2
1
x
x
x
x
kon’yunkasiya mos keladi, (1, 0, 1, 0) koordinataga esa 
)
,
,
,
(
4
3
2
1
x
x
x
x
kon’yunkasiya mos keladi va hokazo. Hamma argumentlar yoki ular 
inkorlarining kon’nyuksiyalari 
elementar kon’yunkasiyalar
deyiladi. 
(20.13) ifodadan berilgan funksiya nolga aylanadigan argumentlar to‘plamiga 
(koordinatalarga) DMNSH ning nol tashkil etuvchilari mos kelishi kelib chiqadi. 
Bundan DMNSHning muhim xossasi kelib chiqadi, u quyidagidan iborat: bul 
funksiyasining DMNSH ga yoyilishi elementar kon’yunksiyalar birlashmasi bo‘lib, 
ularning mos koordinatalarida mazkur funksiya birga teng. 
DMNSH ning boshqa zarur xossasi hamma elementar kon’yunkasiyalarda 
hamma argumentlarning mavjudligidir. Masalan, uchta o‘zgaruvchili funksiya uchun 
3
2
1
3
2
1
3
2
1
)
,
,
(
x
x
x
V
x
x
x
x
x
x
f
⋅
⋅
⋅
⋅
=
ifoda DMNSH bo‘ladi, 
3
2
1
2
1
3
2
1
)
,
,
(
x
x
x
V
x
x
x
x
x
f
⋅
⋅
⋅
=
yoyilma DMNSH bo‘lmaydi. Agar funksiya konyukasiyalar diz’yunkasiyasi 
ko‘rinishida ifodalansa (ular har bir argumentni o‘z ichiga albatta olmagan bo‘lsa), u 
holda bunday ifoda 
diz’yunktiv normal shakl
(DNSH) deb ataladi. 
YUqorida bul algebrasi uchun yoki yoqlamalik aksiomasi to‘g‘ri ekani 
ta’kidlangan edi. Uning qo‘llanilishi kon’yunkativ mukammal normal shakl 
(KMNSH)ni hosil qilishga imkon beradi. Oraliq shakl almashtirishlarni tashlab ketib, 
quyidagi ifodani hosil qilamiz: 
)]
...,
(
)
1
,..,
1
,
1
,
1
(
...
)]
...,
(
)
0
,...,
0
,
0
,
1
(
[
)]
...,
(
)
0
,...,
0
,
0
,
0
(
[
)
...,
,
,
(
3
2
1
3
2
1
3
2
1
3
2
1
n
n
n
n
x
v
v
x
v
x
v
x
v
f
x
v
v
x
v
x
v
x
v
f
vx
v
x
v
x
v
x
f
x
x
x
x
f
⋅
⋅
⋅
⋅
=
(19.14) 
Agar nol va birlik elementlar haqidagi (5, 9, 5, 10) aksiomalar hisobga olinsa, u 
holda KMNSH ning quyidagi xossasini aniqlash mumkin. Oldindan nuqta 
koordinatalari va hamma argumentlar diz’yunksiyalari hamda ularning inkorlari 
PDF created with pdfFactory Pro trial version 
www.pdffactory.com

---

517 
o‘rtasida moslik o‘rnatamiz, uni KMNSH bilan analogiya bo‘yicha elementar deb 
ataymiz. Bu moslik oddiygina o‘rnatiladi, bu misoldan ko‘rinib turibdi. Uchta 
argument (0, 1, 0) funksiya koordinatasiga 
)
,
,
(
3
2
1
x
x
x
elementar diz’yunksiya mos 
keladi, (1,0, 1) koordinataga 
)
,
,
(
3
2
1
x
x
x
elementar diz’yunksiya mos keladi va hokazo. 
Keyin nol element haqidagi (19.9) aksiomaga muvofiq l v d ifodadan (bu erda, d-
elementar dizyunksiya) dastlabki bul funksiyasi 1 ga teng bo‘lgan koordinatalarga 
moc keluvchi (19. 14) tenglamaning kvadrat qavs ichidagi hadlari ham birga teng.
SHu bilan bir vaqtda birlik element haqidagi (19.10) aksiomaga ko‘ra 
0
0
1
i
i
f
f
=
⋅
ifodada (bunda, 
0
i
f
– kvadrat ildizlar ichidagi hadlar) bul funksiyasi 0 ga teng.
Binobarin (19.14) tenglamaning o‘ng tomonida shunday elementar diz’yunksiyalar
borki, ularning tegishli koordinatalarida dastlabki funksiyasi 0 ga teng.