Toshkent axborot texnologiyalari universiteti 2020/2021o’quv yili sirtqi ta’lim yo`nalishi talabalari uchun mustaqil ishlar

“Algoritmlash va matematik modellashtirish” kafedrasi

13.01.2015 y. Bayonnoma № 16

Variant 28.	TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI 2020/2021o’quv yili sirtqi ta’lim yo`nalishi talabalari uchun mustaqil ishlar	___________
1.	Takrorlanadigan guruhlashlar (formulasini keltirib chiqaring).
2.	Matematik mantiq nazariyasi tarixi.
3.	soddalashtiring.
4.	(1+4t- 2t^2)^8 yoyilmasida t^9 oldidagi koeffitsiyent nimaga teng?
5.	F(0,0,0)=F(0,0,1)=F(0,1,0)=F(0,1,1)= F(1,1,0)=1 yechimlar daraxtini tuzing va soddalashtiring. Qism dasturini yozing.

1.	Takrorlanadigan guruhlashlar (formulasini keltirib chiqaring).

Ta`rif. Agar tanlangan qism to`plamda elementlar tartibi ahamiyatsiz bo`lsa, u holda tanlanmalarga (n,k) guruhlash deyiladi va k Сn ko`rinishida belgilanadi. C – inglizcha “combination”, ya`ni “guruhlash” so`zining bosh harfidan olingan. Tanlanmalarda elementlar takrorlanishi va takrorlanmasligi mumkin.

Ta’rif. n ta elementli to‘plamning barcha tartiblanmagan takrorlanuvchi

11. 
    ta elementli qism to‘plamlarini ajratish takrorlanuvchi guruhlash deyiladi.
    

19. 
    to`plamning elementlari 1;2;…; n sonlari bilan raqamlangan bo`lsin. S
    

to`plam chekli yoki sanoqli bo`lgani uchun, har doim S to`plam elementlari va N natural sonlar to`plami elementlari o`rtasida bir qiymatli moslik o`rnatish mumkin.

U holda

S

to`plam o`rniga o’zaro bir qiymatli moslik kuchiga asosan, unga

ekvivalent bo`lgan

S ^/ {1;2;...; n} to`plamning Сn^k

guruhlashlarini topish mumkin.

S ^/

to`plamning har qanday tanlanmasini

{n1; n2 ;...; nk }

ko`rinishda yozish

mumkin,

bunda

n1  n2  ...  nk

ketma-ketlik

o’rinli

bo’lib,

“tenglik” amali

tanlanma takrorlanuvchi

bo`lishi mumkinligini bildiradi.

k

ta

elementli

tanlanma

{n1; n2 ;...; nk }

ga

k

ta

elementli to`plam

{n1;n2 1;...; nk  k 1} ni mos qo`yamiz, bunda elementlar turlicha

bo`ladi.

{n1; n2 ;...; nk }

va

{n1;n2 1;...; nk  k 1}

to`plamlar orasidagi moslik yana

o`zaro bir

qiymatli bo`lib,{n1;n2 1;...; nk

 k 1}

to`plam

S ^/ {1;2;...; k 1}

to`plamdan

n  k 1 tadan takrorlanmaydigan k elementli guruhlash bo`ladi.

Сn^kk 1

~

U holda

takrorlanmaydigan

guruhlashlar soni Cn^k takrorlanuvchi

guruhlash soniga teng bo’ladi, ya`ni

~

(n  k 1)!

n (n 1) ...(n  k 1)

Cn^k  Сn^kk 1 



k!(n 1)!

k!

Teorema.

n

ta elementdan

k

ta elementli takrorlanuvchi guruhlashlar soni

~

Cn^k  Сn^kk 1

ga teng.

Misol. 4 ta o’yin kubigini tashlab, nechta turlicha variant hosil qilish mumkin? Yechilishi: Har bir o’yin kubigida 1 dan 6 gacha raqamlardan bittasi
tushishi mumkin, ya’ni har bir kubikda 6 ta variant bo’lishi mumkin. Agar 4 ta o’yin kubigi tashlansa, har bir variantni 4 ta ob’yektning tartiblanmagan takrorlanuvchi ketma-ketligi deyish mumkin, ularning har biri uchun esa 6 ta imkoniyat bor:

~	(n  k 1)!			(6  4 1)!			9!		6789
C ^k 										126.
n	k!(n 1)!			4!5!			4!5! 1234

2.	Matematik mantiq nazariyasi tarixi.

Matematik mantiq diskret matemetikaning asosiy bo`limi bo`lib, bu bo`lim mulohazalar algebrasi bilan boshlanadi. Matematik mantiq hamda to`plamlar nazariyasi birgalikda hozirgi zamonaviy matematikaning fundamenti hisoblanadi. Amaliy nuqtai nazardan qaraydigan bo`lsak, matematik mantiq ma`lumotlar bazasini qurishda, elektrotexnika, informatika va hisoblash texnikasi va umuman barcha raqamli qurilmalarda dasturlash tili uchun asos bo`lib hizmat qiladi. Shuning uchun ham tahliliy mulohaza yuritishga qiziquvchi har bir kishi matematik mantiq bo`limini o`rganishi kerak bo’ladi. Insoniyat tomonidan to’plangan matematik bilimlarni jamlashda greklarning hissasi nihoyatda salmoqli bo`lgan, shuningdek, ular mantiq, ya`ni to`g`ri mulohaza yuritish san`ati bilan ham shug’ullanishgan. Er. av. 389 yilda Platon (er.av. 427-347 yy) asos solgan falsafiy maktabda matematikaning ilk nazariy asoslari qurildi. Platon mantiqiy teoremalarni isbotlashning quyidagi 3 ta metodini ishlab chiqdi: 1) analitik metod; 2) sintetik metod; 3) apagogik metod. Analitik metod – har biri o’zidan oldingisining bevosita natijasi bo’lgan gaplar zanjirini hosil qilishdan iborat. Bu zanjirning birinchi elementini isbotlash kerak bo’lgan mulohaza, oxirgi elementini esa isbotlangan haqiqat tashkil qiladi. Sintetik metod – analitik metodning aksibo’lib, unda birinchi element isbotlangan haqiqat va har bitta mulohaza o’zidan keyingisining natijasi bo’ladi. Apagogik metod – teskarisini faraz qilish yo’li bilan isbotlash metodi bo’lib, unda zanjirning birinchi elementi isbotlash kerak bo’lgan mulohazani inkor qilish bo’ladi, oxirida esa ziddiyatga olib kelinadi. Platonning shogirdlaridan Aristotel Stagirit (er.av. 384 -322 yy) alohida ajralib turadi. Aristotelni mantiq ilmining asoschisi desak, yanglishmaymiz, chunki u o’zigacha bo’lgan barcha mantiqiy bilimlarni jamladi va mantiqiy qonuniyatlar sistemasini yaratdi. Bu qonunlardan tabiatni tadqiq qilishda mulohazalar quroli sifatida foydalandi. Aristotelning olamni o’rganishdagi bilimlari yagona bo’lib, naturfalsafa deb nom olgan. Qadimgi greklar matematikani ikkiga ajratib o’rganishgan: 1) mantiqni hisoblash san`ati deb, 2) arifmetikani sonlar nazariyasi deb nomlashgan. Ushbu bobda mulohazalar va ular ustida amallar, mantiqiy bog‘liqliklar, Bul (mantiqiy) formulalari, mantiq qonunlari, mantiq funksiyalari, mantiq funksiyalari uchun rostlik jadvalini tuzish va aksincha, rostlik jadvali berilgan bo’lsa, mantiq funksiyasi ko‘rinishini tiklash, mukammal diz’yunktiv va kon’yunktiv normal shakllar, rele - kontakt sxemalari, rele - kontakt sxemalarida analiz, sintez, minimallashtirish masalalari, Karno kartalari, Veych diagrammalari, yechimlar daraxti haqida so’z yuritiladi. Shuningdek, elementlari 0 va 1 dan tashkil topgan to`plamlar ustida ish ko`riladi. Bu elementlar son sifatida emas, balki mantiqiy “ha”, “yo`q” ma`nolarida ishlatiladi.

3.	soddalashtiring.

5.	F(0,0,0)=F(0,0,1)=F(0,1,0)=F(0,1,1)= F(1,1,0)=1 yechimlar daraxtini tuzing va soddalashtiring. Qism dasturini yozing.

Karno kartasi bo‘yicha formulaning soddalashgan ko‘rinishi quyidagicha bo‘ladi:

F(A,B,C)= BD.

Rostlik jadvali quyidagicha bo`lgan formula uchun minimizatsiyalash masalasini qaraymiz:

A	B	C	D	a ( A, B, C , D)
0	0	0	0	0
0	0	0	1	0
0	0	1	0	0
0	0	1	1	0
0	1	0	0	0
0	1	0	1	0
0	1	1	0	0
0	1	1	1	1
1	0	0	0	0
1	0	0	1	0
1	0	1	0	0
1	0	1	1	1
1	1	0	0	0
1	1	0	1	1
1	1	1	0	1
1	1	1	1	1

Bu jadvalga mos funksiya uchun mukammal diz’yunktiv normal shaklni quyidagicha tuzamiz:

a ( A, B, C , D ) = ^Ø AÙ B Ù C Ù D Ú A Ù ^Ø B Ù C Ù D Ú A Ù B Ù ^ØC Ù DÚ
ÚAÙBÙCÙ ^ØDÚ AÙBÙCÙD.

Bu formulani Karno kartasidan foydalanib soddalashtiramiz:

^ØCÙ^ØD ^ØCÙD CÙD CÙ^ØD

^ØAÙ ^ØB

• 
  ^ØA Ù B
  

^ØA Ù B

^ØAÙ ^ØB

0	0	0	0
0	0	1	0
0	1	1	1
0	0	1	0

Karno kartasidan ko`rinib turibdiki, funksiyaning ko`rinishi
a ( A, B, C , D) = A Ù B Ù C Ú A Ù B Ù D Ú B Ù C Ù D Ú A Ù C Ù D
shaklda bo`ladi