Kirish dissertatsiya mavzusining dolzarbligi va zarurati

Jegalkin ko‘phadini guruhlash uchun yordamchi jadval.

	x1	x2	x3	x4	x5
x1	0	0	1	1	0
x2	0	0	1	1	1
x3	1	1	1	1	1
x4	1	1	1	0	0
x5	1	1	1	0	0

Umumlashgan Jegalkin ko‘phadi
Jegalkin ko‘phadida berilgan bul funksiyaga inkor amalini kiritib elementar konyunksiyalar sonini kamaytirish mumkin lekin funksiyaning algebraik chiziqsizligi oshadi. (2.5) teng kuchlilik formulalar orqali inkor amalini bul funksiyasiga kiritish mumkin. Hosil bo‘lgan ko‘phadni shartli umumlashgan Jegalkin ko‘phadi deb nomlanadi.
(2.5)
Agar bizga (2.6) kabi tenglama berilsa uni 2.5-jadvaldagi kabi qismlarga ajratib yechish mumkin.
1-misol. Quyidagi bul tengmasini yeching.
(2.6)

2.5-jadval.

Umumlashgan Jegalkin ko‘phadini yechimlar jadval.

Yechimlar soni
8	4	1

Jami 13ta ildizi mavjud.
2-misol. Quyidagi bul tengmasini yeching.


2.6-jadval
Umumlashgan Jegalkin ko‘phadini yechimlar jadval.

Yechimlar soni
8	3

Jami 11ta ildizi mavjud.
Jegalkin ko‘phadi shaklida berilgan tenglamani guruhlashgan va umumlashgan Jegalkin ko‘phadi shakliga keltirib yechish samaraliroq ekanligini ko‘rish mumkin.

II bob bo‘yicha xulosa

Ushbu bobda bul funksiyalarni berilish usullari, to‘liqlik, yopiqlik, muxum yopiq sinflar va Post teoremasi keltirib o‘tildi. Shuningdek mantiqiy tenglamalar tizimini yechishning XL usuli haqida ma’lumotlar keltirilgan hamda Jegalkin ko‘phadidagi mantiqiy tenglamalarni soddalashtirish va soddalashgan mantiqiy funksiyani yechish usullari taklif qilingan. Jegalkin ko‘phadini yechishning SAT va XL usullar berilgan.

III BOB. MANTIQIY TENGLAMALAR TIZIMINI YECHISH DASTURIY TA’MINOTI VA AES ALGORITMINING MURAKKABLIGI TAHLILI

Ushbu bobda d.n.f. va Jegalkin ko‘phadidagi chiziqsiz mantiqiy tenglamalar tizimini yechish algoritmi va bu algoritm asosida bajarilgan dasturiy taminot haqida ma’lumot keltirib o‘tilgan. Shuningdek bobda AES algoritmini murakkabligini mantiqiy tenglamalar asosida tahlil qilingan.

3.1 Chiziqsiz DNSHdagi mantiqiy tenglamalar tizimini yechish dasturiy ta’minoti

D.n.sh. ifodasidagi bul tenglamalar tizimini yechishda ikki xil yondoshilgan. Birinchi berilgan funksiyalar asosida bul tenglamalar tizimi yechish. Ikkinchi usul d.n.sh. ifodasidagi tenglamalarga funksiyalarni oldin minimallashtirib so‘ng ularni yechish.
Minimallashtirish usullar masalan, Karta Karno usuli, Implikant test usuli, Implikant matritsasi usuli, Kvayn usuli va boshqalarni o‘z ichiga oladi. Karta Karno usuli 1952da Eduard V. Weich tomonidan ixtiro qilingan va 1953da Moris Karno tomonidan ishlab chiqilgan va raqamli elektron sxemalarni soddalashtirishga yordam berish uchun mo‘ljallangan[19,52]. Quyidagi blok sxema orqali bul funksiyalarni Karta-Karno, Kvayn usullari yordamida minimallashtirish mumkin.
Karta-Karno va Kvayn usuli yordamida minimallashtirish algoritmining murakkabligi nazariy tomondan baholash quyidagicha (3.1) aniqlandi.
(3.1)
Karta-Karno va Kvayn usuli yordamida minimallashtirish algoritmining murakkabligi polinomial ekanligini ko‘rish mumkin(3.1-rasm).
To‘liq tanlash usuli yordamida bul tenglamalar tizimini yechish algoritmida har bir operatsiyani bajarish uchun shartli vaqt talab etadi deb baholash mumkin. Bu yerda bajariladigan har bir amalga talab etiladigan vaqtlarning eng kattasi hisoblanadi va (3.2) tenglik bilan aniqlangan.
(3.2)
Minimallashtirilgandan so‘ng to‘liq tanlash usuli bilan chiziqsiz bul tenglamamiz yechiladi.