|
MAVZU. MDNSH (MUKAMMAL DIZYUNKTIV NORMAL SHAKL). MKNSh (MUKAMMAL KONYUNKTIV NORMAL SHAKL.
1 - teorema. Mulohazalar algebrasining ixtiyoriy Á formulasining MDNF ( MKNF ) i mavjud.
Isbot. teoremaga asosan Á - DNF. Isbotni formulaning rangi bo‘yicha matematik induksiya usuli bilan bajaramiz.
Á ning rangi 0 ga teng bo‘lsin. Aniqik uchun Á - X1 dan iborat bo‘lsin. U holda
X1 º X1 Ù 1 º X1 Ù ( X2 Ú ù X2 ) º ( X1 Ù X2 ) Ú ( X1 Ù ù X2 ) º
º ( X1 Ù X2 ) Ù 1 Ú ( X1 Ù ù X2 ) Ù 1 º (( X1Ù X2 ) Ù ( X3 Ú
Ú ù X3 )) Ú (( X1 Ù ù X2 ) Ù ( X3 Ú ù X3 )) º ( X1 Ù X2 Ù X3 ) Ú
Ú ( X1 Ù X2 Ù ù X3 ) Ú ( X1 Ù ù X2 Ù X3 ) Ú ( X1 Ùù X2 Ù
Ù ù X3 ) º . . . º ( X1 Ù X2 Ù . . . Ù Xn ) Ú . . . Ú
Ú ( X1 Ù ù X2 Ù . . . Ù ù Xn ) – MDNF.
Rangi n dan kichik barcha formulalar uchun teorema isbot qilingan deb faraz qilamiz va rangi n ga teng formula uchun teoremani isbot qilamiz. Á - rangi n ga teng formula bo‘lsin. U holda Á faqat Â Ú Ã ko‘rinishda bo‘lishi mumkin.
Ravshanki,  va à larning ranglari n dan kichik. Demak,  va à lar MDNF lardir. X Ú X º X teng kuchlilikka asosan Â Ú Ã formulada bir ùil mukammal elementar kon’yunksiyalardan bittadan qoldirsak, Â Ú Ã - MDNF bo‘lad
Á - formulaning MKNF i mavjudligi ikkilik qonundan kelib chiqad
Haqiqatdan ham, Á* formulaning MDNF i  - formula bo‘lsa, u holda Á º ( Á* )* º Â* - MKNF dir.
izoh. Agar mulohazalar algebrasining Á formulasini ikki qiymatli funksiya sifatida =arasak, u holda Á - formulaning MDNF ini ( MKNF ini) 5 dagi usuldan foydalanib topish mumkin.
misol. X1 Ù ( X2 Ú X3 ) formulaning MDNF ini toping. Avval X1 Ù ( X2 Ú X3 ) ning DNF ini topaylik. 3.6 dagi 20 - tengkuchlilikka asosan :
X1 Ù ( X2 Ú X3 ) º ( X1 Ù X2 ) Ú ( X1 Ù X3 ) .
X1 Ù X2 va X1 Ù X3 – larning MDNF larini 3.6 da keltirilgan tengkuchliliklar yordamida topamiz.
X1 Ù X2 º X1 Ù X2 Ù 1 º X1 Ù X2 Ù ( X3 Ú ù X3 ) º
º ( X1 Ù X2 Ù X3 ) Ú ( X1 Ù X2 Ù ù X3 ) .
X1 Ù X3 º X1 Ù 1 Ù X3 º X1 Ù ( X2 Ú ù X2 ) Ù X3 º
º ( X1 Ù X2 Ù X3 ) Ú ( X1 Ù ù X2 Ù X3 ) . Bundan,
( X1 Ù X2 ) Ú ( X1 Ù X3 ) º ( X1 Ù X2 Ù X3 ) Ú ( X1 Ù
Ù X2 Ùù X3 ) Ú ( X1 Ù X2 Ù X3 ) Ú ( X1 Ù ù X2 Ù X3 ) º
( X1 Ù X2 Ù X3 ) Ú ( X1 Ù ù X2 Ù X3 ) Ú ( X1 Ù X2 Ù ù X3 )-
MDNF. Demak, X1 Ù ( X2 Ú X3 ) – formulaning MDNF i
( X1 Ù X2 Ù X3 )Ú ( X1 Ù ù X2 Ù X3 ) Ú ( X1 Ù X2 Ù ù X3 ) – formuladan iborat ekan.
misol. X1 Ú ( ù X2 Ù X3 ) formulaning MKNF ini toping.
asosiy tengkuchliliklar yordamida teng kuchli almashtirishlar bajaramiz :
X1 Ú ( ù X2 Ù X3 ) º ( X1 Ú ù X2 ) Ù ( X1 Ú X3 ) . Bu erda
X1 Ú ù X2 º X1 Ú ù X2 Ú 0 º X1 Ú ù X2 Ú ( ù X3 Ù X3 ) º
º ( X1 Ú ù X2 Ú ù X3 ) Ù ( X1 Ú ù X2 Ú X3 ) va
X1 Ú X3 º X1 Ú 0 Ú X3 º X1 Ú ( X2 Ù ù X2 ) Ú X3 º
º ( X1 Ú X2 Ú X3 ) Ù ( X1 Ú ù X2 Ú X3 ) . U holda
X1 Ú ( ù X2 Ù X3 ) º ( X1Ú ù X2 Ú ù X3 ) Ù ( X1 Ú ù X2 Ú
Ú X3 ) Ù ( X1 Ú X2 Ú X3 ) – MKNF.
MAVZU. MULOHAZALAR ALGEBRASI TADBIQLAR MULOHAZALAR ALGEBRASINING ELEMENTAR MATEMATIKA VA FIZIKAGA TADBIQLAR
Hozirgi kunda xalq xo‘jaligining, inson faoliyatining har qanday soùasini EÙM siz tasavvur qilib bo‘lmayd Ilmiy – texnika revolyusiyasining yuz berishida matematik mantiqning katta ùissasi bor. XX asrning boshlaridan boshlab tez rivojlana boshlagan matematik mantiqdan yangi mustaqil soùalar ajralib chiqdi : avtomatlar nazariyasi, rele – kontakt va elektron sxemalar sintezi, algoritmlar nazariyasi shular jumlasidandir. Ûtgan asrning ûttizinchi yillariga kelib EÙM ning matematik ta’minoti ishlab chiqildi, qirqinchi yillarning borshlarida esa birinchi EHM lar ishga tushirild Avtomatik bosh=arish =urilmalari va elektron ùisoblash mashinalarida yuzlab va minglab rele– kontakt, elektron–lampa, yarimûtkazgich va magnit elementlarini ûz ichiga olgan rele–kontakt va elektron– lampa sxemalar uchrayd Bu sxemalar avtomatik boshqarish qurilmalari va EHM lari tarkibida benihoya katta tezlikda juda murakkab operatsiyalar bajarishda bevosita ishtirok etadi va avtomatlarning barcha ish faoliyatini boshqarib turad Rele–kontakt va elektron sxemalarni analiz va sintez qilishda mulohazalar algebrasi muùim ahamiyatga ega. Har qanday sxemaga mulohazalar algebrasining biror formulasini mos qo‘yish mumkin. Va aksincha mulohazalar algebrasining har bir formulasini rele – kontakt sxema
( RKS ) orqali ifoda qilish mumkin. RKS bilan mulohazalar algebrasining formulalari orasidagi bunday munosabat murakkab RKS larni mulohazalar algebrasining formulalari yordamida soddalashtirish imkoniyatini berad quyida RKS larini mulohazalar algebrasining formulalari yordamida ifodalash masalasini kûrib chiqamiz.
Kontaktni shartli ravishda
¸ ——•—— , —— —— , ——• •——
ko‘rinishda belgilaymiz. Kontakt yopiq (tok o‘tkazadigan) yoki ochiq (tok ûtkazmaydigan) holatda bo‘lishi mumkin. Kontaktning yopiq holatiga 1 ni , ochiq holatiga 0 ni mos qo‘yamiz.
Barcha kontaktlar orasida doimo tok o‘tkazadigan (doimo yopiq) hamda butunlay tok o‘tkazmaydigan (doimo ochiq) kontaktlar mavjuddir. Ularni ham mos ravishda 1 va 0 bilan belgilaymiz va hamda ——·—— , —— —— ko‘rinishda ifodalaymiz.
SHunday qilib, agar mulohazaning mazmunini e’tiborga olmasak, har bir mulohazaga ma’lum bir kontaktni mos qo‘yishimiz mumkin ekan. Biz o‘zgaruvchi kontaktlar bilan ish kûrganimiz uchun ularni X, U, Z, . . . harflar bilan belgilaymiz. U holda ikkita X va U mulohazalarning kon’yunksiyasiga kontaktlarni ketma – ket ulash natijasida hosil bo‘ladigan ——·X·——·U·—— sxemani, X va U muloqazalarning diz’yunksiyasiga kontaktlarni parallel ulash natijasida hosil bo‘ladigan quyidagi
———·X·———
●—— ———●
———·U·———
sxemani mos qo‘yamiz.
Ilgari isbot qilingan 6.3 teoremaga asosan mulohazalar algebrasining har qanday formulasini faqat ù , Ù , Ú amallar orqali ifodalash mumkin. Demak, mulohazalar algebrasining har bir formulasi RKS orqali ifoda qilinishi va aksincha, har qanday RKS ni mulohazalar algebrasining formulasi orqali ifodalash mumkin ekan.
1- misol . Mulohazalar algebrasining
( X Ù U ) Ú ù X - formulasiga quyidagi rele – kontakt sxemasi mos keladi :
———●X●——●U●——
●——— ———●
————●ù X ●————
2 - misol .
——●X●——— ——● U ●——
●——— ——— ———●
——●ù X●—— ——●ù U●——
sxemaga ( X Ú ù X ) Ù ( U Ú ù U ) formula mos kelad
3 - misol . Ovoz berish schetchig
Uch kishidan iborat komissiya biror bir masalani hal qilish uchun ovoz berayotgan bo‘lsin. Masalaning biror echimi uchun komissiya a’zolari oldilaridagi tugmachani bosadilar. Ikkita yo uchta tugmacha bosilsa, chiroq yonadi va shu echim qabul qilinad Aks holda chiroq yonmaydi va echim qabul qilinmayd
Ovoz berish schetchigining RKS sini tuzamiz. Bu sxema uch ûpgaruvchili bo‘lishi ravshan. Uch o‘zgaruvchili RKS mulohazalar algebrasining uch o‘zgaruvchili formulasi, bu formula esa ûz navbatida F ( X, U, Z) – funksiyadan iborat bo‘lib, uning qiymatquyidagi jadval orqali berilishi mumkin :
X
|
Y
|
Z
|
F
|
1
|
1
|
1
|
1
|
1
|
1
|
0
|
1
|
1
|
0
|
1
|
1
|
1
|
0
|
0
|
0
|
0
|
1
|
1
|
1
|
0
|
1
|
0
|
0
|
0
|
0
|
1
|
0
|
0
|
0
|
0
|
0
|
Bu funksiyani mulohazalar algebrasining MDNF i orqali ifoda qilaylik :
F ( X, U, Z ) º X Ù U Ù Z Ú X Ù ù Y Ù Z Ú ù X Ù Y Ù Z Ú X Ù
Ù Y Ù ù Z . Teng kuchli almashtirishlar yordamida bu formulani soddalashtiramiz :
F ( X , Y, Z ) º X Ù Y Ù Z Ú X Ù ù Y Ù Z Ú ù X Ù Y Ù Z Ú X Ù
Ù Y Ù ù Z º ( X Ù U Ù Z Ú X Ù ù Y Ù Z ) Ú ( X Ù Y Ù Z Ú ù X Ù
Ù Y Ù Z ) Ú ( X Ù Y Ù Z Ú X Ù Y Ù ù Z ) º (( X Ù Z ) Ù ( Y Ú
Ú ù Y )) Ú ( Y Ù Z Ù ( X Úù X )) Ú ( X Ù Y Ù ( Z Ú ù Z )) º
º X Ù Z Ú Y Ù Z Ú X Ù Y º ( Z Ù ( X Ú Y )) Ú X ÙY .
Hosil qilingan formula uchun RKS ni tuzamiz :
———● X●———
———●Z●—— ————
●——— ———● U●——— ————●
—————●X●—————●U●————
Do'stlaringiz bilan baham: | 
