14-Mavzu Bul funksiyalar. Ahamiyati va ahamiyatsiz o’zgaruvchilar. Bul funksiyalarining formulalar orqali amalga oshirilishi. Teng kuchli formulalar. Reja

14-Mavzu

Bul funksiyalar. Ahamiyati va ahamiyatsiz o’zgaruvchilar. Bul funksiyalarining formulalar orqali amalga oshirilishi. Teng kuchli formulalar.

Reja:

1. 
   Bul funksiyalar, ularning usullari. Bul funksiyalari soni. Bul algebrasi.
   
2. 
   Ahamiyatli va ahamiyatsiz o’zgaruvchilar
   
3. 
   Bul funksiyalarning formulalar orqali amalga oshirilishi
   
4. 
   Ikkilamchi funksiyalar. Ikkilamchi prinsipi
   

Kalit so’zlar: Bul funksiyalar, Bul algebrasi, ahamiyatli va ahamiyatsiz o’zgaruvchilar, formula, ikkilamchi funksiya, ikkilamchi prinsipi.

Ma’lumki, mantiqiy amallar mulohazalar algebrasi nuqtai nazardan chinlik jadvallari bilan to’liq xarakterlanadi. Agarda funskiyaning jadval shaklda berilishini esga olsak, u vaqtda mulohazalar algebrasida ham funksiya tushunchasini aniqlashimiz mumkin.

Ta’rif. x₁, x₂, … ,x_n mulohazalar algerbasining x₁, x₂, … ,x_nargumentli f(x₁, x₂, … ,x_n) funksiyasi deb nol va bir qiymat qabul funksiyaga aytiladi va uning x₁, x₂, … ,x_nargumentlari ham nol va bir qiymatlar qabul qilinadi.

Ta’rif. F:{0,1}ⁿ -> {0,1} funksiya mantiqiy algebraning funksiyasi yoki Bul funksiyasi deyiladi. N-o’zgaruvchili Bul funksiyalar to’plamini P_n orqali belgilaymiz, ya’ni

Bir o’zgaruvchili funksiyalar 4 ta bo’lib, ular quyidagilar

1. 
   f₀(x)=0 – aynan nolga teng funksiya yoki aynan yolg’on funksiya
   
2. 
   f₁(x)=x – aynan funksiya
   
3. 
   - inkor funksiya
   
4. 
   f₃(x)=1 – aynan birga teng funksiya yoki aynan chin funksiya
   

Argument	Bul funksiyalar
x	0	x		1
1	0	1	0	1
0	0	0	1	1

Barcha ikki o’zgaruvchili funksiyalarni sanab o’tamiz.

x	Y		0					x							1			1
1	1		0	1	0	0	0	1	0	0	1	1	0	1	0	1	1	1
1	0		0	0	1	0	0	1	1	0	0	0	1	1	1	0	1	1
0	1		0	0	0	1	0	0	1	1	0	1	0	1	1	1	0	1
0	0		0	0	0	0	1	0	0	1	1	0	1	0	1	1	1	1

Hammasi bo’lib 16 ta har xil iki o’zgaruvchili funksiyalar mavjud. Ularning ko’pchiligi maxsus nomlanadi:

– konyunksiya

- Pirs strelkasi

- 2 modul bo’yicha qo’shish yoki Jegalkin yig’indisi

Bul funksiyalarining qiymatlar jadvaliga chinlik jadvali deyiladi. Har qanday n o’lchovli f(x₁, x₂, … ,x_n) Bul funksiyani chinlik jadvali orqali berish mumkin:

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

– ekvivalentlik

– dizyunksiya

- Sheffer shtrixi

– implikatsiya

Bul funksiyalarining qiymatlar jadvaliga chinlik jadvali deyiladi. Har qanday n o’lchovli f(x₁,x₂,...,x_n) Bul funksiyani chinlik jadvali orqali berish mumkin:

x1	x2	...........	xn	f(x1,x2,...,xn)
0	0	...........	0	λ1
1	0	...........	0	λ2
0	1	...........	0	λ3
...........	...........	...........	...........	...........
1	1	...........	1	λ2n

bu yerda λ_iϵ{0,1},i=1,2,...,2ⁿ. Bu jadval 2ⁿ ta satr bo’lib, ularga ta har xil ustunlar mos qo’yish mumkin. Lekin bunday har bir ustun biror n o’zgaruvchili Bul funksiyaga mos keladi. Shunday qilib, quyidagi teorema isbotlandi:

Teorema. N o’zgaruvchili har xil Bul funksiyalarining soni ga teng, ya’ni |P_n|=

Bul algebrasi

Teorema. Konyunksiya , dizyunksiya , inkor amallari va 0,1ϵM elementlari uchun quyidagi amallar:

bajarilsa, bunday M to’plamga Bul algebrasi deyiladi.

Mulohazalar to’plami uchun konyunksiya , dizyunksiya , inkor amallari va {0,1} elementlari aniqlangani uchun, bu to’plam Bul algebrasi bo’ladi.

Ta’rif. Agar o’zgaruvchining shunday a₁, a­₂,...,a_i-1,a_i,...,a_n qiymatlar majmuasi mavjud bo’lib, f(a₁, a­₂,...,a_i-1,1,a_i,...,a_n)=f(a₁, a­₂,...,a_i-1,0,a_i,...,a_n) munosabat bajarilsa, u vaqtda x_i o’zgaruvchiga f(x₁,x₂,...,x_n) funksiyaning ahamiyatsiz (sohta) o’zgaruvchisi, agar f(a₁, a­₂,...,a_i-1,1,a_i,...,a_n)≠f(a₁, a­₂,...,a_i-1,0,a_i,...,a_n) munosabat bajarilsa, u vaqtda x_i o’zgaruvchiga f(x₁,x₂,...,x_n) funksiyaning ahamiyatli (sohta emas) o’zgaruvchisi deb ataladi.

Misol. funksiyada o’zgaruvchi sohta bo’ladi.

Haqiqatdan,

Misol. f₁,f₂ va f₃ funksiyalar quyidagi chinlik jadvali orqali berilgan bo’lsin:

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

Ko’rinib turibdiki, f₁ funksiya uchun x o’zgaruvchi ahamiyatli o’zgaruvchi, u esa ahamiyatsiz, f₂ uchun ikkala o’zgaruvchi ham ahamiyatsiz, f₃ uchun ikkala o’zgaruvchi ham ahamiyatli.

Ф={f₁,f₂,...,f_n} Bul funksiyalar to’plami berilgan bo’lsin.

Ta’rifФ to’plam ustida aniqlangan formula deb, F(Ф)=f(t₁,t₂,...,t_n) ifodaga aytiladi, bu yerda fϵФ va t_iФ ustidagi yoki o’zgaruvchi, yoki formula.

Ф to’plam bazis, f tashqi funksiya, t_i lar esa qism formulalar deyiladi. Har qanday F formulaga bir qiymatli biror f Bul funksiyasi mos keladi. Bu holda F formula f funksiyani ifodalaydi deyiladi va f=funcF ko’rinishida belgilanadi.

Bazis funksiyalarini chinlik jadvalini bilgan holda, bu formula ifodalaydigan funksiyaning chinlik jadvalini hisoblashimiz mumkin.

Misol.

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

F formulaga mos keluvchi f funksiyani Ф dan olingan funksiyalarning superpozitsiyasi, f funksiyani Ф dan hosil qilinish jarayonini superpozitsiya amali deb ataymiz.

formula berilgan bo’lsin. formula uchta qadamda ko’riladi. Haqiqatdan, biz quyidagi uchta qism formulalarga ega bo’lamiz:

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

Biz yuqorida ko’rdikki, Ф to’plamdan hosil qilingan har bir formulaga mantiq algebrasining formulasi mos keladi, biroq har xil formulalarga teng funksiyalar mos kelishi mumkin.

Ta’rif Bitta Bul funksiyasini ifodalovchi formulalar ekvivalent deyiladi, ya’ni


Teorema. Ixtiyoriy f,g,h Bul funksiyalar uchun quyidagi ekvivalentliklar o’rinli:

1. 
   
   
2. 
   Konyunksiya, dizyunksiya va ikki modul bo’yicha qo’shishning idempotentligi:
   

3. 
   Konyunksiya, dizyunksiyava ikki modul bo’yicha qo’shishning kommunikativligi:
   

4. 
   Konyunksiya, dizyunksiya va ikki modul bo’yicha qo’shishning assotsiativligi:
   

Distributivlik qonunlari:

5. 
   Yutish qonuni:
   

6. 
   De Morgan qonuni:
   
7. 
   
   
8. 
   
   
9. 
   
   
10. 
    Implikatsiyani yo’qotish qonuni:
    

11. 
    Ekvivalentlikni yo’qotish qoidasi:
    

12. 
    
    
13. 
    
    
14. 
    
    
15. 
    
    

Ta’rif. f(x₁,x₂,...,x_n)ϵP_n bul funksiya bo’lsin, unda

funksiya, f bul funksiyaga ikkilamchi bo’lgan funksiya deyiladi.

Bu ta’rifdan bevosita, ixtiyoriy f bul funksiyasi uchun f**=f ekanligi kelib chiqadi. Haqiqatdan,

.

Misol. a)

Yechish.







Ta’rif. Agar f*=f bo’lsa, f funksiya o’z-o’ziga ikkilamchi deyiladi.

Yuqoridagi misoldan ko’rinadiki, inkor va aynan funksiya o’z-o’ziga ikkilamchi, dizyunksiya funksiya o’z-o’ziga ikkilamchi emas.

Teorema. Agar φ(x₁,x₂,...,x_n) bul funksiya f(f₁(x₁,x₂,...,x_n),f₂(x₁,x₂,...,x_n),...,f_n(x₁,x₂,...,x_n)) formula ko’rinishida ifodalangan bo’lsa, bu yerda f₁,f₂,...,f_n lar bul funksiyalar, unda f*(f*₁(x₁,x₂,...,x_n),f*₂(x₁,x₂,...,x_n),...,f*_n(x₁,x₂,...,x_n)) formula φ*(x₁,x₂,...,x_n) funksiyani ifodalaydi.

Isbot. .

Teorema isbotlandi.

Keyingi teorema “ikkilamchi prinsipli” deb nomlanadi va matematik induksiya usuli bilan isbotlanadi. Bunda induksiya o’tishlar yuqoridagi isbotlangan teorema asosida amalga oshiriladi.

Teorema. (Ikkilamchi prinsipli)

Ф={f₁,f₂,…,f_n­} va - bazislar bo’lsin. U holda, agar F formula Ф bazisda f funksiyani ifodalasa, unda F formuladan f_i ni uni ikkilamchi funksiyaga almashtirish natijasida hosil qilingan F* formula Ф bazisda f* funksiyani ifodalaydi, ya’ni


Nazoat savollar:

1. 
   Mulohazalar algebrasining funksiyasi ta’rifini ayting.
   
2. 
   Bir o’zgaruvchi funksiyalar keltiring.
   
3. 
   N o’zgaruvchilar soni nimaga teng?
   
4. 
   Bul algebrasi deb nimaga aytiladi?
   
5. 
   Ahamiyatli o’zgaruvchi deb nimaga aytiladi?
   
6. 
   Ahamiyatsiz o’zgaruvchi deb nimaga aytiladi?
   
7. 
   Formula ta’rifini keltiring.
   
8. 
   Qanday formulalar ekvivalent deyiladi?
   
9. 
   Qanday ekvivalentliklarni bilasiz?
   
10. 
    Ikkilamchi funksiya ta’rifini ayting.
    
11. 
    Ikkilamchi prinsipini keltiring.
    

ASOSIY ADABIYOTLAR

1. 
   Тураев Х. Математик мантиқ ва дискрет математика. Т.: “Ўқитувчи”, 2003.
   
2. 
   Судоплатов С. В., Овчинникова Е. В. Элементы дискретной математики – М.: «Инфра-М», 2002 г.
   
3. 
   Асеев Г.Г., Абрамов О.М., Ситников Д.Э. Дискретная математика. – Ростов – на-Дону, «Феникс», 2003 г.
   
4. 
   Кулабухов С.Ю. Дискретная математика – Таганрогский радиотехнический университет, Таганрог, 2001 г.
   
5. 
   Гаврилов Г.П. , Сапожченко А.А. Задачи и упражнения по дискретной математики.М.:Наука.2005.
   
6. 
   Еруссалимский Я.М. Дискретная математика теория , задачи , приложения.- М. «Вузовская книга» , 2002 г.
   
7. 
   Шапорев С.Д. Дискретная математика. Курс лекций и пратических занятий. Санкт-Петербург «БХВ- Петербург» 2009 г.
   
8. 
   Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Теория графов. М.: «Наука» 1991.
   

ҚЎШИМЧА АДАБИЁТЛАР

1. 
   Яблонский С.В. Введение в дискретную математику. М.: “Наука”, 1979.
   
2. 
   Куратовский К. Мостовский А. Теория множеств. М.: “Мир”, 1970.
   
3. 
   Игошин В.И. Задачник-практикум по математической логике. М.
   

Просвешение.1986.

4. 
   Зыков А.А. Основы теории графов.-М., «Наука» 1987 г.
   
5. 
   Ершов Ю.Л. и др. Математическая логика. .-М., «Наука» 1987 г.
   

INTERNET SAHIFALARI

1. 
   www.intuit.ru/department/ds/discrmath/
   
2. 
   http://www.uni-dubna.ru/~mazny/kurses/odm/lekcii/
   
3. 
   http://www.lvf2004.com/dop_t2r1part2.html
   
4. 
   http://www.mielt.ru/dir/cat14/subj266/file292.html
   
5. 
   http://window.edu.ru/window/catalog?p_rid=28455
   
6. 
   http://lib.rus.ec/b/259478
   
7. 
   www.doc.ic.ac.uk/~iccp/papers/discrete94.pdf
   

8. http://calvino.polito.it/~tilli/matdiscreta/Discrete%20Mathematics.html