O‘zbekiston respublikasi oliy va o’rta maxsus ta’limi vazirligi

Nazorat savollari.

1. 
   Shaxsiy kompyuter qanday tuzilishga ega?
   
2. 
   Ona platada nimalar joylashgan?
   
3. 
   Shaxsiy kompyuter tuzilishiga kim asos solgan?
   
4. 
   Fon - Neyman qanday prinsipni taklif qilgan?
   
5. 
   Shaxsiy kompyuter qanday mantiqiy tuzilishga ega?
   
6. 
   Axborotlarni fizik ifodalash deganda nimani tushunasiz?
   

21-mavzu: Bul funksiyalari, ularning berilish usullari. Bul funktsiyalari soni
Reja
1. Bul algebrasi haqida tushincha.
2. Sodda mulahazalar haqida tushincha.
3. Bul funktsiyalar soni.
Tayanch tushunchalar: Bul funktsiyasi, implikatsiya, Pers strelkasi. Sheffer shtrixi, argument, mulohaza, konyunktsiya, dizyunktsiya, ekvivalentlik, inkor.
1854 yilda ingliz matematigi Djorj Bul o‘zining «Fikrlash qonunlari» nomli kitobini chop etdi. U mantiqiy algebraning asosini tashkil etadi. Bul algebrasi avaliy jihatidan hech qanday ahamiyatga ega emas edi. Lekin XX asrda har xil turdagi electron sxemalarni yaratish va ularning ishlash jaroyonlariga qo’llanilishi topiladi. Shundan so’ng Bul algebrasi EHM ning rivojlanishida katta rol o‘ynaydi. EHM yaratish mumkinligining asosiy g‘oyasi bul algebrasiga asoslangan. Mantiqiy algebra apparatlari va qanunlari EHM ning turli qisimlarining proektlarini yaratishda qo’llanila boshladi. Ayniqsa xotira, protsessorlarini yaratishga asqatadi. Bu fikrni tushunish uchun matematik mantiqning asosiy sodda tushunchalarini eslaylik. Oddiy hodisalar yoki mantiqiy fikr elementlarini A,B,D. . . va mantiqiy fikrning rost yoki yolg‘onligini esa mos ravishda 1 va 0 bilan belgilash mumkin.
Bu esa o‘z navbatida ikkilik sanoq sistemasiga mos keladi. Agar bir hodisaning yuz berishi, ikkinchi hodisaga bog‘liq bo‘lmasa, bu hodisa sodda, aks holda murakkab deyiladi. Bul algebrasiga muvofiq, har qanday murakkab hodisa sodda hodisalarning mantiqiy funksiyasidan iborat.
Bul algebrasining asosiy tasdiqlaridan biri ixtiyoriy mantiqiy funksiyani mantiqiy amallar asosida chekli sondagi mantiqiy mulohazalar ko‘rinishida yozish mumkinligidadir. Bundan esa ixtiyoriy mantiqiy fikrni rost (1) va yolg‘onlarning (0) chekli sondagi kombinatsiyalari ko‘rinishida yozib olish mumkinligi kelib chiqadi. Bu esa, o‘z navbatida 1 (signal bor) va 0 (signal yo‘q) raqamlarining kombinatsiyalariga asoslangan va ixtiyoriy fikrni ifodalash imkoniga ega bo‘lgan maxsus elektron qurilmalar-EHM larni yaratish mumkinligi haqidagi fikrni yuzaga keltiradi.
Sodda mantiqiy mulohaza nima degani? Mulohaza deb, rost yoki yolg’onligi haqida gapirish mumkin bo’lgan har qanday darak gapga aytiladi. Quydagilar soda mulohazalardir. “uch soni birdan kattadir”, “5,8 butun son hisoblanadi”. Birinchi holda mulohaza rost, ikkincyi holda mulohaza soda. Mantiqiy algebra mulohazaning mohiyati bilan shug’illanmaydi, balki soda mulohazalarning oldindan berilgan qiymatlari asosida murrakkab mulohazalarning qiymatlarini hisoblash bilan shug’ullanadi.
f(x₁,x₂,…,x_n ) funktsiyaga Bul funktsiyasi deyiladi,bunda x₁,x₂,…,x_n argumentlar bog’liq emas o’zgaruvchilar, funktsiyaning o’zi o’zgaruvchilarga bog’liq va 0 yoki 1 qiymat qabul qiladi. Umuman n argumentli funktsiyalar {0,1}ⁿ →{0,1} akslantiradi. Bul fynktsiyalar soni n argumentga bog’liq bo’lib 2^(2^n) ga teng. Agar n=2 bo’lsa 16 ta turli xil Bul funktsiyasiga ega bo’lamiz.

x	y	f1	f2	f 3	f4	f5	f6	f7	f8	f9	f10	f11	f12	f13	f14	f15	f16
0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0	1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	0	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1

f₁(x,y)=0 - const;
f₂ (x,y)=x&y – kon’yunktsiya;
f₃ (x,y)= ┐(x→y) – implikatsiya inkori;
f₄ (x,y)=x - funktsiya birinchi argumentga teng;
f₅ (x,y)= ┐(y→x)- teskari implikatsiyaning inkori;
f₆ (x,y)=y – fynktsiya ikkinchi argumentga teng;
f₇ (x,y)=x + y – qa’tiy ajratilgan dizyunktsiya;
f₈ (x,y)=xvy – dizyunktsiya;
f₉ (x,y)=x↓y – pirs strelkasi(YoKI-EMASni beradi);
f₁₀ (x,y)=x≡y-ekvivalentlik;
f₁₁ (x,y)= ┐y – ikkinchi argument inkori;
f₁₂ (x,y)=y→x – teskari implikatsiya;
f₁₃ (x,y)= ┐x – birinchi argument inkori;
f₁₄ (x,y)=x→y – impkikatsiya;
f₁₅ (x,y)=x│y – Sheffer shtrixi;
f₁₆ (x,y)=1 – const. “rost”.
Sodda mulohazalar qanday amallar yordamida bog’lanadi. Biz odatdagi so’zimizda sod gaplarni “va”, “yoki”, “agar”, “y holda”, “emas”, “yo”,”yohud”, “agar… u holda”,”qochanki”,”faqat va faqat” bog’lovchilar bilan bog’laymiz. Misol “U bilim va ko’nikmaga ega”, “U seshanba yohud chorshanba kuni keladi”, “5 soni 6 soniga teng emas”, “Men o’yinga chiqaman faqat, qochanki darsni tayyorlauahimdan so’ng”. Matematik mantiq bunga o’xshash soda mulohazalardan murakkab mulohazalarning formal formasini qurub uning rost yoki yolg’onligini isbotlash bilan shug’ullanadi. Yuqoridagi tabiiy so’zlashuvdagi soda gaplarni bog’lovchilarning matematik mantiqning o’z belgilari bor jadvalga qarang.
Jadval 1.

Mantiqiy bog’lanish	Mantiqiy operatsiya nomi	Belgisi
emas	Inkor	՟ , ,
va	Konyunktsiya	˄, &
yoki	Dizyunktsiya	V, +
Yo, yoxud	Qa’tiy ajratilgan dizyunktsiya	+ , ∆
Agar…,u holda	Implikatsiya	→
Qachonki, faqat va faqat, u vaqtda	Ekvivalent	↔, ≡, ~

Jadvalda keltirilgan mantiqiy operatsiyalarning ta’riflarini keltirib o’tamiz.
Ta’rif 1. Konyunktsiya. Ikkita soda mulohazalardan har ikkisi rost bo’lganda rost, qolgan hollarda yolg’on bo’lgan murakkab mulohaza konyunktsiya deyiladi.
“A&B – A va B deb o’qiladi. Yuqoridagi “U bilim va ko’nikmaga ega” da A=”U bilimga ega”, B=”U ko’nikmaga ega. A&B=”U bilim va ko’nikmaga ega”. Misol. A&B=”6 soni 2 ga va 3 ga bo’linadi” bo’lsa, uning qiymati nimaga teng bo’ladi?
Ta’rif 2. Dizyunktsiya. Ikkita sodda mulohazalardan har ikkisi yolg’on bo’lganda yolg’on, qolgan hollarda rost bo’lgan murakkab mulohaza dizyunktsiya deyiladi. AvB – A yoki B deb o’qiladi. Misol “21>3 yoki 21=6” – AvB murakkab mulohazadan: A=”21>3” – rost, B=”21=6” – yolg’on sodda mulohazalarga ajratamiz. Savol ta’rifdan “AvB”=murakkab mulohazaning qiymati nimaga teng?
Ta’rif 3. Qa’tiy ajratilgan dizyunktsiya. Ikkita sodda mulohazadan birlari yolg’on, birlari rost bo’lgandagina rost, qolgan hollarda yolg’on murakkab mulohaza qa’tiy ajratilgan mulohaza deyiladi. Misol. A + B=”It uyni qo’riqlayapti yohud o’z uyida uhlayapti”. Bu misolda A=”It uyni qo’riqlayapti”, B=”It o’z uyida uhlayapti” sodda mulohazaga bo’linsa ta’rifga asjsan A=0, B=1 yoki A=1, B=0 bo’lganda
A + B=1 qolgan holda A + B=0 hisoblanadi. Savol. Agar murakkab mulohaza “yoki” bog’lovchisi bilan bog’lansa bu mulohza qanday dizyunktsiyami? Yoki qa’tiy ajratilgan dizyunktsiyami? Javob: Ta’rifga asosan bu narsa har ikkala sodda mulohaza rost bo’lganda mos kelmaydi, ya’ni misolda keltirilgan it uyda uxlab, uyni qo’riqlay olmaydi.
Ta’rif 4. Implikatsiya. Implikatsiya yordamida tuzilgan murakkab mulohaza faqat shart rost bo’lib, xulosa qismi yolgon bo’lganda yolg’on, qolgan hollarda rost bo’lgan murakkab mulog’aza implikatsiya deyiladi. Ta’rifdan agar A bo’lsa, uholda B bo’ladi. Yoki “A mulohazadan B mulohaza kelib chiqadi” deb o’qiladi. Misol. A→B=”2>3 bo’lsa, u holda ayiq uchadi.”, A→B=”Agar yomg’ir yog’sa, u holda tom ho’l” bu mulohazalar rost qiymat qabul qiladi.
Ta’rif 5. Ekvivalentlik. Ikkita sodda mulohazadan tuzilgan murakkab mulohaza rost bo’ladi, agarda har ikki sodda mulohaza yolg’on yoki rost bolsa, aks holda yolg’on qiymat qabul qiladi. Bunda A mulohazaning bajarilishi uchun B mulo-hazaning bajarilishi zarur va etarlidir.
Yuqorida qarab chiqilgan mantiqiy operatsiyalar binor(ikkilik) operatsiyalar deb yuritiladi. Undan tashqari unar(birlik) operatsiyalar ham keng qo’llaniladi. Masalan inkor operatsiyasi shulardan biri.
Ta’rif 6. Berilgan sodda mulohaza rost bo’lsa, inkori yolg’on, yoki sodda mulohaza yolg’on bo’lsa, inkori rost bo’ladi.
Misol. A=”Men uyda dars qildim”, ┐A=”Men uyda dars qilmadim. Lekin barcha sodda mulohazalarga doima inkorini topib bo’lmaydi. Misol. A=”Barcha 9-sinf o’quvchilari a’lochi emas”. Bunda A=0, lekin ┐A=”Barcha 9-sinf o’quvchilari a’lochi”, bunda ham ┐A=0 .
Yuqoridagi barcha mantiqiy operatsiyalarning rostlik jadvalini keltiramiz:

A	B	┐A	A&B	A v B	A + B	A → B	A ~ B
0	0	1	0	0	0	1	1
0	1	1	0	1	1	1	0
1	0	0	0	1	1	0	0
1	1	0	1	1	0	1	1

Qarab chiqilganidek mantiqiy algebrada mantiqiy operatsiyalar turi ko'pdir. Lekin ulardan uchtasi, konyunktsiya, dizyunktsiya va inkor asosiy e’tiborga ega. Shu uchalasi yordamida qolgan barcha mantiqiy operatsiyalarni ifodalab olish mumkin. Natijada sxemalarni yaratishda kamroq turli xil qurilmalardan foydalanishimizga imkon beradi. Quydagi teng kuchli aormulalarni keltirib o’tamiz.
1.kommutativlik xossasi: X&Y=Y&X; XVY=YVX
2.assotsiativlik xossasi: (X&Y)&Z=X&(Y&Z); (XVY)VZ=XV(YVZ)
3.yutishlik xossasi(0 va 1): XV0=X; X&1=X
4.distributivlik xossasi: X&(YVZ)=(X&Y)V(X&Z); XV(Y&Z)=(XVY)&(XVZ)
5.ziddiyatlik xossasi: X&┐X=0
6.uchinchini inkor qilish xossasi: XV┐X=1
7.idempotentlik xossasi: X&X=X; XVX=X
8.inkorning inkorlik xossasi: ┐┐X=X
9 de Morgan xossasi: ┐(X&Y)= ┐XV┐Y; ┐(XVY)= ┐X&┐Y
10 yutishlik xossasi: XV(X&Y)=X; X&(XVY)=X
11 X→Y=┐AVB, ┐(A→B)=A&┐B
12 A≡B=(A&B)V(┐A&┐B)=( ┐AVB)&(AV┐B)
13 AVA&B=A; 14) ┐A&(AVB)= ┐A&B 15) AV┐A&B=AVB
Bu teng kuchli formulalarning barchasini rostlik jadvali orqali isbotlash mumkin.