|
DNF - dis'yunktiv normal shakl
|
| bet | 6/6 | | Sana | 30.11.2023 | | Hajmi | 30,39 Kb. | | #108899 |
Bog'liq Diskret tuzilmalar Аширматова Янгилиш, ТЗФКУ 1 (2)DNF - dis'yunktiv normal shakl
Elementar mantiqiy mahsulotlarning
mantiqiy yig'indisi. DNF haqiqat jadvalidan quyidagi algoritm yoki qoida
bo'yicha olinadi:
1) jadvalda chiqish funktsiyasi = 1 tanlangan o'zgaruvchilar qatorlari.
2) o'zgaruvchilarning har bir qatori uchun mantiqiy ko'paytma yoziladi; bu
erda = 0 o'zgaruvchilar inversiya bilan yoziladi.
3) hosil bo'lgan mahsulot mantiqiy ravishda umumlashtiriladi.
Fdnf = X 1 * X 2 * X 3
∨ X 1 x 2 X 3 ∨ X 1 X 2 x 3 ∨ X 1 X 2 X 3
Agar barcha o'zgaruvchilar bir xil daraja yoki tartibga ega bo'lsa, DNF
mukammal deb ataladi, ya'ni. har bir ish to'g'ridan-to'g'ri yoki teskari shaklda
barcha o'zgaruvchilarni o'z ichiga olishi kerak.
b)
CNF - kon'yunktiv normal shakl
Elementar mantiqiy summalarning
mantiqiy mahsulotidir.
CNF ni quyidagi algoritm yordamida haqiqat jadvalidan olish mumkin:
1) chiqish funktsiyasi = 0 bo'lgan o'zgaruvchilar to'plamini tanlang
2) har bir o'zgaruvchilar to'plami uchun elementar mantiqiy yig'indini
yozamiz va o'zgaruvchilar = 1 inversiya bilan yoziladi.
3) olingan summalar mantiqiy ravishda ko'paytiriladi.
Fscnf = (X 1 V X 2 V X 3)
∧ (X 1 V X 2 V X 3) ∧ (X 1 V X 2 V X 3) ∧ (X
1 V X 2 V X 3)
CNF mukammal deb ataladi
agar barcha o'zgaruvchilar bir xil darajaga
ega bo'lsa.
Algebraik shaklda siz mantiqiy eshiklar yordamida mantiqiy qurilma sxemasini
qurishingiz mumkin.
1-rasm - Mantiqiy qurilma diagrammasi
Barcha mantiqiy operatsiyalar aniqlangan
haqiqat jadvallari
qiymatlar. Haqiqat
jadvali operatsiya natijasini aniqlaydi
hammasi mumkin
x asl bayonotlarning
mantiqiy qiymatlari. Amaliyotlarni qo'llash natijasini aks ettiruvchi variantlar soni
mantiqiy ifodadagi gaplar soniga bog'liq bo'ladi. Agar mantiqiy ifodadagi
bayonotlar soni N bo'lsa, unda haqiqat jadvali 2 N qatorni o'z ichiga oladi, chunki
argumentlarning mumkin bo'lgan qiymatlarining 2 N xil kombinatsiyasi mavjud.
NO operatsiyasi - mantiqiy inkor (inversiya)
Mantiqiy operatsiya oddiy yoki murakkab mantiqiy ifoda bo'lishi mumkin bo'lgan
bitta argumentga QO'LLANILMAYDI. Operatsiyaning natijasi EMAS:
•
agar dastlabki ifoda rost bo'lsa, uni inkor qilish natijasi noto'g'ri bo'ladi;
•
agar asl ifoda noto'g'ri bo'lsa, uni inkor qilish natijasi to'g'ri bo'ladi.
Quyidagi konventsiyalar inkor operatsiyasi uchun QABUL QILMAYDI:
A emas, Ā, A emas, ¬A,!A
Rad etish operatsiyasining natijasi quyidagi haqiqat jadvali bilan aniqlanmaydi:
A
emas, balki A
0
1
1
0
Inkor amalining natijasi asl bayonot noto'g'ri bo'lganda to'g'ri bo'ladi va aksincha.
OR operatsiya - mantiqiy qo'shish (ajralish, birlashma)
Mantiqiy OR operatsiyasi oddiy yoki murakkab mantiqiy ifoda bo'lishi mumkin
bo'lgan ikkita bayonotni birlashtirish funktsiyasini bajaradi. Mantiqiy operatsiya
uchun manba bo'lgan bayonotlar argumentlar deb ataladi. OR operatsiyasining
natijasi, agar asl iboralardan kamida bittasi to'g'ri bo'lsa, to'g'ri bo'ladigan ifodadir.
Qo'llaniladigan belgilar: A yoki B, A V B, A yoki B, A || B.
OR operatsiyasining natijasi quyidagi haqiqat jadvali bilan aniqlanadi:
YOKI amalining natijasi A rost, yoki B rost, yoki A va B bir vaqtning o'zida to'g'ri,
A va B argumentlari noto'g'ri bo'lsa, noto'g'ri bo'ladi.
VA operatsiya - mantiqiy ko'paytirish (bo'g'in)
Mantiqiy AND operatsiyasi oddiy va murakkab mantiqiy ifoda bo'lishi mumkin
bo'lgan ikkita bayonotni (argumentlarni) kesish funktsiyasini bajaradi. AND
operatsiyasining natijasi ikkala asl ibora ham to'g'ri bo'lgan taqdirdagina to'g'ri
bo'ladigan ifodadir.
Qo'llaniladigan belgilar: A va B, A L B, A va B, A va B.
AND operatsiyasining natijasi quyidagi haqiqat jadvali bilan aniqlanadi:
A
B
A va B
0
0
0
0
1
0
1
0
0
1
1
1
AND operatsiyasining natijasi, agar A va B iboralar bir vaqtning o'zida to'g'ri
bo'lsa va boshqa barcha holatlarda noto'g'ri bo'lsa, rost bo'ladi.
"IF-THEN" operatsiyasi - mantiqiy keyingi (ta'sir)
Bu operatsiya ikkita oddiy mantiqiy ifodani bog'laydi, ulardan birinchisi shart,
ikkinchisi esa shu shartning natijasidir.
Amaliy belgilar:
agar A, keyin B; A B ni o'z ichiga oladi; agar A u holda B; A → B.
Haqiqat jadvali:
A
B
A → B
0
0
1
0
1
1
1
0
0
1
1
1
Quyidagi amalning natijasi (ma’nosi) faqat A asosi to‘g‘ri, B xulosasi (natija)
noto‘g‘ri bo‘lgandagina noto‘g‘ri bo‘ladi.
"A, agar va faqat B" operatsiyasi (ekvivalentlik, ekvivalentlik)
Amaliy belgi: A ↔ B, A ~ B.
Haqiqat jadvali:
A
B
A↔B
0
0
1
0
1
0
1
0
0
1
1
1
"Mod 2 qo'shish" operatsiyasi (XOR, eksklyuziv yoki qat'iy ajratish)
Amaliy belgi: A XOR B, A
⊕ B.
Haqiqat jadvali:
A
B
A
⊕B
0
0
0
0
1
1
1
0
1
1
1
0
Amaliyot ekvivalentligining natijasi faqat A va B bir vaqtning o'zida to'g'ri yoki
noto'g'ri bo'lsa, to'g'ri bo'ladi.
Mantiqiy ustuvorlik
•
Qavs ichidagi amallar
•
Inversiya
•
Bog'lovchi (&)
•
Disjunction (V), Exclusive OR (XOR), sum mod 2
•
Izoh (→)
•
Ekvivalentlik (↔)
Mukammal disjunktiv normal shakl
Formulaning mukammal dis'yunktiv normal shakli(SDNF) unga ekvivalent
formula bo'lib, u quyidagi xususiyatlarga ega elementar birikmalarning
diszyunksiyasidir:
1. Formulaning har bir mantiqiy atamasi F funktsiyasiga kiritilgan barcha
o'zgaruvchilarni o'z ichiga oladi (x 1, x 2, ... x n).
2. Formulaning barcha mantiqiy shartlari boshqacha.
3. Birorta ham mantiqiy atama o'zgaruvchini va uning inkorini o'z ichiga
olmaydi.
4. Formuladagi hech qanday mantiqiy atama bir xil o'zgaruvchini ikki marta o'z
ichiga olmaydi.
SDNF ni haqiqat jadvallari yordamida yoki ekvivalent transformatsiyalar
yordamida olish mumkin.
Har bir funktsiya uchun SDNF va SKNF o'zgartirishgacha noyob tarzda
aniqlanadi.
Mukammal kon'yunktiv normal shakl
Mukammal kon'yunktiv normal shakl formulasi (SKNF) xossalarini
qanoatlantiradigan elementar ayirmalarning birikmasi bo‘lgan unga ekvivalent
formuladir:
1. Barcha elementar bandlar F funktsiyasiga kiritilgan barcha o'zgaruvchilarni
o'z ichiga oladi (x 1, x 2, ... x n).
2. Barcha elementar disjunksiyalar har xil.
3. Har bir elementar dis'yunktsiya bir marta o'zgaruvchini o'z ichiga oladi.
4. Elementar dis'yunktsiyada o'zgaruvchi va uning inkori mavjud emas.
Foydalanilgan adabiyotlar
•
1. Toʼraev X. Matematik mantiq va diskret matematika. T.: “Oʼqituvchi”, 2003.
•
2. Sudoplatov S. V., Ovchinnikova Ye. V. Elementii diskretnoy matematiki – M.: «Infra-
M», 2002 g.
•
3. Аseev G.G., Аbramov O.M., Sitnikov D.E. Diskretnaya matematika. – Rostov – na-
Donu, «Feniks», 2003 g.
•
4. Kulabuxov S.Yu. Diskretnaya matematika – Taganrogskiy
radiotexnicheskiy
universitet
, Taganrog, 2001 g.
http://fayllar.org
|
| |
