Umumiy doc

Bul funksiyalari va ularning kononik shakllari.Bul funksiyasiga ta’rif 
beramiz. 20. o‘zgaruvchilarning bul funksiyasi
n
x
x
x
...,
,
2
1
argumentlarning chekli 
qiymati bilan aniqlanib, bunda argumentlar qiymatlarini chekli V to‘plamdan qabul 
qiladi. Bu argumentlar o‘zaro va ma’lum qiymatdagi bul amallari bilan bog‘langan 
bo‘lib, funksiyaning o‘zi (argumentlar kabi) V = {0, 1} to‘plamdan qiymatlar qabul 
qiladi. 20. o‘zgaruvchilarning bul funksiyasini 
(
)
n
x
x
x
x
f
,...,
,
,
3
2
1
ko‘rinishda yozamiz. 
Birlashtirish, ko‘paytirish va inkor qilish amallarining ma’nosini ochamiz. 
Buning uchun bitta va ikkita argument uchun mumkin bo‘lgan funksiyalarni aniqlash 
lozim. Ikkili bul funksiyasining umumiy sonini aniqlash ifodasi argumentlarning 
soniga borliq holda quyidagi ko‘rinishda bo‘ladi: 
N = 2
2n, 

(19.11) 
bu erda, N — bul funksiyalari soni, n — argumentlar soni. 
Bu ifodadan bitta argument uchun 4 ta bul funksiyasi mavjudligi kelib chiqadi
(19.1-jadval). 
19.1-jadval. 
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.