Kirish dissertatsiya mavzusining dolzarbligi va zarurati

Chinlik jadvaliga misol

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

jadval yordamida aniqlangan funksiyani kabi aniqlash mumkin.
Barcha Bul funksiyalar to’plamini orqali belgilaymiz.
2.1- teorema. n ta o’zgaruvchili barcha Bul funksiyalari soni ga teng.
Endi, elementar funksiyalar deb ataluvchi funksiyalarni keltiramiz.
1⁰. Ushbu

0	0
1	0

jadval bilan aniqlangan funksiya nol funksiya deyiladi va u 0 kabi belgilanadi:
2⁰. Ushbu

0	1
1	1

jadval bilan aniqlanadigan funksiya birlik funksiya deyiladi va u 1 kabi belgilanadi:
3⁰. Ushbu

0	1
1	0

jadval bilan aniqlanadigan funksiya inkor funksiya deyiladi va u kabi belgilanadi:
4⁰. Ushbu

0	0
1	1

jadval bilan aniqlanadigan funksiya ayniy funksiya deyiladi va u kabi belgilanadi:
5⁰. Ushbu

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

jadval bilan aniqlanadigan funksiya kon’yunksiya deyiladi va u yoki kabi belgilanadi:
6⁰. Ushbu

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

jadval bilan aniqlanadigan funksiya diz’yunksiya deyiladi va u kabi belgilanadi:
7⁰. Ushbu

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

jadval bilan aniqlanadigan funksiya implikatsiya deyiladi va u kabi belgilanadi:
8⁰. Ushbu

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

jadval bilan aniqlanadigan funksiya ekvivalensiya deyiladi va u kabi belgilanadi:
9⁰. Ushbu

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

jadval bilan aniqlanadigan funksiya ikki modul bo’yicha olingan yig’indi funksiya deyiladi va u kabi belgilanadi:
10⁰. Ushbu

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

jadval bilan aniqlanadigan funksiya Sheffer (strixi) funksiyasi deyiladi va u kabi belgilanadi: .
11⁰. Ushbu

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

jadval bilan aniqlanadigan funksiya Pirs (strelkasi) funksiyasi deyiladi va u kabi belgilanadi:
Elementar funksiyalar yordamida formulalar qurish mumkin. Aytaylik, - qandaydir Bul funksiyalar to’plami bo’lsin. ustidagi formulaga quyidagicha ta’rif beramiz.
2.2-ta’rif. a) barcha o’zgaruvchilarni ustidagi formula deb ataymiz;
b) va ifodalar ustidgia formulalar bo’lsa, ifodani ustida formula deb ataymiz.
Masalan, - elementar funksiyalar to’plami bo’lsin. Quyidagi ifodalar ustidagi formula bo’ladi.

1. 
   
   
2. 
   
   
3. 
   .
   

ustidagi har bir formula biror bir Bul funksiyasini aniqlaydi. Ushbu aniqlangan funksiyaga dan olingan funksiyalarning superpozitsiyasi deyiladi. dan funksiyani hosil qilish jarayonini superpozitsiya amali deyiladi. Yana funksiyani ustidagi formula ko’rinishida ifodalash mumkin deyiladi. formulaga funksiya mos qo’yilgan deymiz. Bir funksiya bir necha formulaga mos qo’yilishi mumkin.


Formulalar ekvivalentligi.
Yuqorida aytilganidek, turli formulalarga bitta Bul funksiyasi mos qo’yilishi mumkin. Masalan, va formulalarga bitta funksiya mos qo’yiladi.
2.3-ta’rif. Mos qo’yilgan funksiyalari teng bo’lgan formulalarga ekvivalent formulalar deyiladi va kabi belgilanadi.
Boshqacha aytganda formulalar bir xil rostlik jadvaliga ega bo’lsa, ular ekvivalent formulalar deyiladi.
Misollar.

1. 
   
   
2. 
   
   
3. 
   
   

Quyidagi ekvivalent formulalar elementar funksiyalarning xossalarini ko’rsatadi.

2.4-ta’rif. Ushbu tenglik yordamida aniqlangan

funksiya funksiyaga dual funksiya deyiladi.
Dual funksiyaning jadvali funksiyaning jadvalidan 0 ni 1 ga va 1 ni 0 ga o’zgartirib, yuqoridan pastga aylantirib hosil qilinadi. Quyidagi jadvalga qarang.

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

Misol. Quyidagi funksiyalarga dual funksiyani toping:

1. 
   
   
2. 
   
   

Yechish: 1) ta’rifga ko’ra
17-ekvivalentlik formulasiga ko’ra .
2) Bu misolni yechish uchun dual funksiyaning qiymatlar jadvali to’g’risida aytilgan mulohazalardan foydalanamiz, ya’ni 0 ni 1 ga va1 ni 0 ga o’zgartirib, teskari aylantirib dual funksiyani hosil qilamiz: .
2.2-teorema. Agar
bo’lsa,
u holda

_{Isbot.
Teorema isbotlandi.}
Teoremadan quyidagi duallik printsipi kelib chiqadi.
Duallik prinsipi. Agar formula funksiyani aniqlasa, u holda formuladagi funksiyalarni funksiyalarga mos ravishda almashtirib hosil qilingan formula funksiyani aniqlaydi. formulani formulaga dual formula deb ataymiz.
Elementar funksiyalarga dual funksiyalarni ko’rsatamiz
2.3-jadval
O‘z-o‘ziga Dual funksiyalarga misollar

0	1
1	0

Misol. Duallik prinsipidan foydalanib, berilgan funksiyaga dual funksiyani toping. 1)
2)
Yechish: 1) Yuqoridagi jadvaldan foydalanib, berilgan funksiyada qatnashgan barcha funksiyalarni dualiga almashtiramiz
2) .
2.5-ta’rif. Quyidagi tenglik

o’rinli bo’lsa, funksiya o’z-o’ziga dual funksiya deyiladi.
NORMAL FORMALAR
Biz yuqorida mantiq algebrasining formulalarini o’rganish va undan tegishli mantiqiy xulosalar chiqarishda muhim bo’lgan “formulalarning ekvivalentligi” tushunchasini bayon etgan edik.
Ma’lumki, har bir formulani unga ekvivalent bo’lgan, ayni paytda, soddaroq tuzilgan formulaga keltirish muhim.
Mantiq algebrasining har qanday formulasini { } mantiqiy amallar yordamida tuzilgan maxsus formulaga (odatda bunday formulalar diz’yunktiv normal forma, kon’yunktiv normal forma deyiladi) keltiramiz.
Propozitsional o’zgaruvchi uchun ushbu

belgilashni kiritamiz.
2.3-teorema. (Funksiyani o’zgaruvchilar bo’yicha yoyish haqida). Fikrlar algebrasining har qanday funksiyasini ixtiyoriy m uchun ushbu ko’rinishda ifodalash mumkin:
(*)
bu yerda diz’yunksiya o’zgaruvchilarning barcha qabul qilishi mumkin qiymatlar bo’yicha olinadi.
Isbot. Ixtiyoriy uchun (*) tenglikni chap va ong tomoni bir xil qiymat qabul qilishini ko’rsatamiz. Chap tomoni ga teng. O’ng tomoni esa, .