|
Zbekiston respublikasi raqamli texnologiyalar vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalar universiteti
|
| bet | 1/2 | | Sana | 14.05.2024 | | Hajmi | 204,25 Kb. | | #230512 |
Bog'liq azamatdiskretmi18v
O’ZBEKISTON RESPUBLIKASI RAQAMLI TEXNOLOGIYALAR VAZIRLIGI MUHAMMAD
AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALAR UNIVERSITETI
Diskret tuzilmalar fanidan
Mustaqil ish
Guruhi: 0178-23 SKXo‘
Bajardi : Maxammatov Azamat
Toshkent – 2024
Mavzu : Fikriy funksiyalar qiymatlar jadvalini tuzish. Bunda variantlar soni cheklanganligi.
Reja
1. Mantiqiy funksiyalar
2. Mantiqiy funksiyalar uchun qiymatlar jadvali
3. Mantiqiy masalalarni yechish usullari.
4. Foydanilgan adabiyotlar
Mantiqiy funktsiya o'zgaruvchilar faqat ikkita qiymatni qabul qiladigan funktsiya: mantiqiy bitta yoki mantiqiy nol. Murakkab hukmlarning haqiqat yoki noto'g'riligi oddiylarning haqiqat yoki noto'g'riligiga bog'liq. Bu funktsiya mantiqiy hukm funktsiyasi f (a, b) deb ataladi. Har qanday mantiqiy funktsiyani haqiqat jadvali yordamida aniqlash mumkin, uning chap tomonida argumentlar to'plami, o'ng tomonida esa mantiqiy funktsiyaning tegishli qiymatlari yoziladi. Haqiqat jadvalini tuzishda mantiqiy amallarni bajarish tartibini hisobga olish kerak. Mantiqiy ifodadagi amallar chapdan o'ngga, qavslar ostida quyidagi tartibda amalga oshiriladi:
• 1. inversiya;
• 2. konyuksiya;
• 3. dizyunksiya;
• 4. implikatsiya va ekvivalentlik.
Qavslar mantiqiy amallarni bajarish tartibini o'zgartirish uchun ishlatiladi. Quyidagilar taklif etiladi Haqiqat jadvalini tuzish algoritmi.
• 1. Aniqlash kirish o'zgaruvchilari to'plamlari soni- formula bo'yicha ifodalarga kiritilgan o'zgaruvchilar qiymatlarining barcha mumkin bo'lgan kombinatsiyalari: Q = 2 n, bu erda n - kiritilgan o'zgaruvchilar soni. U jadvaldagi qatorlar sonini aniqlaydi. • 2. Jadvalga kiritilgan o'zgaruvchilarning barcha to'plamlarini kiriting. • 3. Mantiqiy amallar sonini va ularni bajarish ketma-ketligini aniqlang. • 4. Ko'rsatilgan ketma-ketlikda mantiqiy amallarni bajarish natijalari bilan ustunlarni to'ldiring. Kiritilgan o'zgaruvchilar qiymatlarining har qanday kombinatsiyasini takrorlamaslik yoki o'tkazib yubormaslik uchun jadvalni to'ldirish uchun quyidagi usullardan birini qo'llashingiz kerak. 1-usul. Boshlang'ich o'zgaruvchilarning har bir qiymatlari to'plami ikkilik sanoq tizimidagi raqamning kodi bo'lib, raqamning raqamlari soni kiritilgan o'zgaruvchilar soniga teng. Birinchi to'plam 0 raqamidir. Joriy raqamga har safar 1 qo'shilsa, biz keyingi to'plamni olamiz. Oxirgi to'plam berilgan kod uzunligi uchun
maksimal ikkilik qiymatdir. Masalan, uchta o'zgaruvchidan iborat funktsiya uchun to'plamlar ketma-ketligi raqamlardan iborat: 2-usul. Uch o'zgaruvchidan iborat funktsiya uchun ma'lumotlar ketma-ketligini quyidagi tarzda olish mumkin: • a) birinchi o'zgaruvchining qiymatlari ustunini yarmiga bo'ling va yuqori yarmini nol bilan, pastki yarmini birlar bilan to'ldiring; • b) ikkinchi o'zgaruvchining keyingi ustunida yarmini yana yarmiga bo'ling va nol va birlik guruhlarini to'ldiring; ikkinchi yarmini xuddi shu tarzda to'ldiring; • c) buni nol va birliklar guruhlari bitta belgidan iborat bo'lguncha bajaring. 3-usul. Ikki argument uchun ma'lum bo'lgan haqiqat jadvalidan foydalaning. Uchinchi argumentni qo'shib, birinchi navbatda jadvalning birinchi 4 qatorini yozing, ularni uchinchi argumentning qiymati 0 ga teng bo'ladi va keyin yana bir xil 4 qatorni yozing, lekin endi uchinchi argumentning qiymati 1 ga teng. Natijada, uchta argument uchun jadval 8 qatordan iborat bo'ladi: Masalan, mantiqiy funksiya uchun haqiqat jadvalini tuzamiz: Berilgan ifodadagi kiritilgan o'zgaruvchilar soni uchta (A, B, C)... Shunday qilib, kirish to'plamlari soni Q = 2 3 =8 . Haqiqat jadvali ustunlari asl iboralarning qiymatlariga mos keladi A, B, C, oraliq natijalar va ( B V C), shuningdek, murakkab arifmetik ifodaning istalgan yakuniy qiymati: • 0 0 0 1 0 0 • 0 0 1 1 1 1 • 0 1 0 1 1 1 • 0 1 1 1 1 1 • 1 0 0 0 0 0 • 1 0 1 0 1 0 • 1 1 0 0 1 0 • 1 1 1 0 1 0 • 7.4. Mantiqiy funksiyalar va ularning transformatsiyasi. Mantiq qonunlari Konyunksiya, dis'yunksiya va inversiya operatsiyalari uchun mantiqiy algebra qonunlari aniqlangan bo'lib, ular hosil qilish imkonini beradi. mantiqiy ifodalarning bir xil (ekvivalent) transformatsiyalari. Mantiq qonunlari •
1. ¬¬ A • 2. A&B • 3. AVB • 4. A va (B&C) • 5. AV (BVC) • 6.A va (BVC) • 7. AV (B&C) • 8. A&A • 9. AVA • 10. AV¬A • 11.A & ¬A • 12. A&I • 13. AVI • 14.A&L • 15. AVL • 16. ¬ (A&B) • 17. ¬ (AVB) • 18.A => B Qonunlar asosida siz murakkab mantiqiy ifodalarni soddalashtirishingiz mumkin. Murakkab mantiqiy funktsiyani oddiyroq, lekin unga ekvivalenti bilan almashtirish jarayoni funksiyani minimallashtirish deb ataladi. 1-misol. Olingan formulalarda murakkab ifodalarning inkori bo'lmasligi uchun ifodalarni soddalashtiring. Yechim 2-misol. Funktsiyani minimallashtirish Ifodani soddalashtirish uchun yutilish va yopishish formulalaridan foydalanilgan. 3-misol. Quyidagi gapning inkorini toping: "Agar dars qiziqarli bo'lsa, unda o'quvchilarning hech biri (Misha, Vika, Sveta) derazadan tashqariga qaramaydi".
Yechim Keling, bayonotlarni belgilaymiz: Y- "Dars qiziqarli"; M- "Misha derazadan tashqariga qaraydi"; B- "Vika derazadan tashqariga qaraydi"; C- "Sveta derazadan tashqariga qaraydi." Ifodani soddalashtirishda amallarni almashtirish formulasi va de Morgan qonunidan foydalanilgan. 4-misol. Jinoyat ishtirokchisini ikkita asosga asoslanib aniqlang: mantiqiy kompyuter jadvali • 1) "Agar Ivanov qatnashmagan yoki Petrov qatnashgan bo'lsa, unda Sidorov qatnashgan"; • 2) "Agar Ivanov qatnashmagan bo'lsa, Sidorov qatnashmagan". Yechim Keling, iboralarni tuzamiz: I- "Ivanov jinoyatda ishtirok etgan"; P- "Petrov jinoyatda ishtirok etgan"; S- "Sidorov jinoyatda ishtirok etgan". Keling, posilkalarni formulalar shaklida yozamiz: Natijani haqiqat jadvali yordamida tekshiramiz: Javob: Jinoyatda Ivanov ishtirok etgan. Uning haqiqat jadvalidan mantiqiy funktsiyani qurish Mantiqiy funksiya uchun haqiqat jadvalini tuzishni o'rgandik. Keling, teskari masalani hal qilishga harakat qilaylik. Z funksiyaning haqiqat qiymati rost (Z = 1) bo'lgan qatorlarni ko'rib chiqaylik. Bu haqiqat jadvali uchun funksiyani quyidagicha tuzish mumkin: Z (X, Y) = (¬ X & ¬Y) V (X & ¬Y). Funktsiya rost (1 ga teng) bo'lgan har bir satr argumentlar birikmasi bo'lgan qavsga mos keladi va agar argumentning qiymati O bo'lsa, biz uni inkor bilan qabul qilamiz. Barcha qavslar ajratish operatsiyasi bilan bog'langan. Olingan formulani mantiq qonunlarini qo'llash orqali soddalashtirish mumkin: Z (X, Y)<=>((¬X & ¬Y) VX) & ((¬X & Y) V ¬Y)<=>(XV (¬X & ¬Y)) & (¬YV (¬X & ¬Y))<=>((XV¬X) & (XV ¬Y)) & ((Y¬V ¬X) & (¬YV ¬Y))<=>(1 & (XV ¬Y)) & (¬YV ¬X) & ¬Y)<=>(XV ¬Y) & (¬YV ¬X) & ¬Y). Olingan formulani tekshiring: Z (X, Y) funksiyasi uchun haqiqat jadvalini tuzing. Mantiqiy funktsiyani haqiqat jadvaliga ko'ra qurish qoidalarini yozing: • 1. Haqiqat jadvalida funksiya qiymati 1 ga teng bo'lgan qatorlarni tanlang. • 2. Kerakli formulani bir nechta mantiqiy elementlarning diszyunksiyasi shaklida yozing. Ushbu elementlarning soni tanlangan chiziqlar soniga teng.
• 3. Bu diszyunksiyadagi har bir mantiqiy element funksiya argumentlarining birikmasi sifatida yoziladi. • 4. Agar jadvalning mos qatoridagi har qanday funktsiya argumentining qiymati 0 ga teng bo'lsa, u holda bu argumentni inkor bilan qabul qilamiz. 1. Harakatlar tartibini aniqlang. 2. Haqiqat jadvalining o'lchamini aniqlang. Ustunlar soni mantiqiy o'zgaruvchilar soni (ikkita A, B mavjud) va harakatlar soni (ulardan ikkitasi ham bor) bilan belgilanadi. 4. Javobni shakllantirish. Oxirgi ustunda bitta "0" A ga "1" ga, B esa "0" ga teng. Ma'lum bo'lishicha, bu funksiya A mantiqiy o'zgaruvchisi rost, B mantiqiy o'zgaruvchisi esa noto'g'ri bo'lgan taqdirdagina noto'g'ri bo'ladi, bu esa NATIJA mantiqiy funksiyasiga mos keladi. Demak, bu funktsiya A va B o'zgaruvchilarning mantiqiy natijasiga teng: Agar A bo'lsa, B bo'lsa. Mantiqiy funktsiya uchun haqiqat jadvalini yarating: 1. Harakatlar tartibini aniqlang. 2. Haqiqat jadvalining o'lchamini aniqlang. Jadvalning "sarlavhasi" ikkita qatorni o'z ichiga oladi - harakatlar raqamlari va harakatlarning mantiqiy operatsiyalari. Ustunlar soni mantiqiy o'zgaruvchilar soni (ikkita A, B mavjud) va harakatlar soni (ulardan beshtasi bor) bilan belgilanadi. Jadvaldagi qatorlar soni mantiqiy o'zgaruvchilar soniga teng bo'lgan quvvatga ikkitaga teng - ikkita o'zgaruvchi bo'lsa, 4 qator olinadi. 3. Jadval ustunlarini shu ustunning mantiqiy vazifasiga muvofiq birin-ketin to'ldiring. 4. Javobni shakllantirish. Oxirgi ustunda "1" A ga teng B ga, "0" esa - A ga teng bo'lmagan B ga to'g'ri keladi. Ma'lum bo'lishicha, bu funktsiya A ga B ga teng bo'lganda to'g'ri va A ga mos bo'lmagan B ga teng bo'lmaganda noto'g'ri bo'ladi. IDENTITY mantiqiy funksiyasiga. Demak, bu funktsiya A va B o'zgaruvchilarning mantiqiy IDENTITY ga teng: A B bilan bir xil. Kompyuter fanlari: shaxsiy kompyuter texnikasi Yashin Vladimir Nikolaevich 4.3. Mantiqiy funksiyalar va haqiqat jadvallari Mantiq algebrasida mantiqiy o'zgaruvchilar va mantiqiy funksiyalar o'rtasidagi bog'lanishlar haqiqat jadvallari deb ataladigan mos jadvallar yordamida ham
ko'rsatilishi mumkin. Haqiqat jadvallari keng qo'llaniladi, chunki ular mantiqiy funktsiyaning mantiqiy o'zgaruvchilari qiymatlarining barcha kombinatsiyalari uchun qanday qiymatlarni olishini aniq ko'rsatadi. Haqiqat jadvali ikki qismdan iborat. Birinchi (chap) qism mantiqiy o'zgaruvchilarga tegishli bo'lib, mantiqiy o'zgaruvchilarning mumkin bo'lgan kombinatsiyalarining to'liq ro'yxatini o'z ichiga oladi. A, B, C ... va hokazo. Ushbu jadvalning ikkinchi (o'ng) qismida chiqish holatlari kirish miqdorlari birikmalarining mantiqiy funktsiyasi sifatida belgilanadi. Masalan, mantiqiy funktsiya uchun F = A v B v C uchta mantiqiy o'zgaruvchining (dizyunksiyasi). A, B, va BILAN Haqiqat jadvali rasmda ko'rsatilgan shaklga ega bo'ladi. 4.1. Mantiqiy o'zgaruvchilar va mantiqiy funktsiyaning qiymatlarini yozish uchun ushbu haqiqat jadvali 8 qator va 4 ustunni o'z ichiga oladi, ya'ni har qanday haqiqat jadvalining argumentlari va funktsiyalari qiymatlarini yozish uchun qatorlar soni teng bo'ladi. 2 n, qayerda P - mantiqiy funktsiyaga argumentlar soni va ustunlar soni n + 1. Guruch. 4.1. Mantiqiy funktsiya uchun haqiqat jadvali F = A v V v C Haqiqat jadvali har qanday mantiqiy funktsiya uchun tuzilishi mumkin, masalan, rasmda. 4.2 - mantiqiy funktsiyaning haqiqati jadvali F = A? B? C(ekvivalentlar). Mantiqiy funksiyalar mos ravishda nomlanadi. Ikki ikkilik oʻzgaruvchilar uchun oʻn oltita mantiqiy funksiya mavjud boʻlib, ularning nomlari quyida keltirilgan. Shaklda. 4.3 - mantiqiy funktsiyalarni ko'rsatadigan jadval F 1, F 2, F 3, ... , F 16 ikkita mantiqiy o'zgaruvchi A va V. Funktsiya F 1 = 0 va doimiy nol funksiyasi yoki nol generatori deb ataladi. Yuqorida sanab o'tilgan o'zgaruvchilarning mantiqiy funktsiyalari orasida boshqa mantiqiy funktsiyalarni ifodalash uchun ishlatilishi mumkin bo'lgan bir nechta mantiqiy funktsiyalar mavjud. Mantiq algebrasida bir mantiqiy funktsiyani boshqasiga almashtirish operatsiyasi superpozitsiya operatsiyasi yoki superpozitsiya usuli deyiladi. Masalan, Sheffer funktsiyasini de Morgan qonuni yordamida mantiqiy dis'yunktsiya va inkor funktsiyalari yordamida ifodalash mumkin: Superpozitsiya usuli yordamida boshqa mantiqiy funktsiyalarni ifodalash uchun ishlatilishi mumkin bo'lgan mantiqiy funktsiyalar asosiy mantiqiy funktsiyalar deb ataladi. Bunday asosiy mantiqiy funktsiyalar to'plami mantiqiy funktsiyalarning funktsional to'liq to'plami deb ataladi. Amalda bunday to'plam sifatida uchta mantiqiy funktsiya eng ko'p qo'llaniladi: konyunksiya, dis'yunktsiya va inkor. Agar mantiqiy funktsiya asosiy funktsiyalar yordamida ifodalansa, u holda taqdimotning bu shakli normal deyiladi. Oldingi misolda asosiy funksiyalar bilan ifodalangan Sheffer mantiqiy funksiyasi normal shaklda ifodalangan. Ushbu mantiqiy funktsiyalarni amalga oshiradigan asosiy funktsiyalar to'plami va ularga mos keladigan texnik qurilmalardan foydalanib, siz har qanday mantiqiy qurilma yoki tizimni loyihalashingiz va yaratishingiz mumkin. Ta'rifi: Bog'lovchi chaqirdi boshlang'ich agar unga kiritilgan barcha o'zgaruvchilar boshqacha bo'lsa. Elementar birikma yoki elementar ayirma tarkibiga kiruvchi harflar soni deyiladi daraja.
1-raqam 0-darajali elementar birikma hisoblanadi. Oʻzgaruvchi elementar bogʻlanish yoki 1-darajali elementar dis'yunksiya hisoblanadi. elementar shaklga keltiriladi va harflarning bir xil to'g'ri bo'lmagan har qanday diszyunksiyasi elementar shaklga ham keltirilishi mumkin. Buning uchun konyunksiya va diszyunksiyaning kommutativlik, idempotentlik va assotsiativlik xossalarini qo`llash zarur. Mantiqiy algebraning istalgan formulasini , &, amallari yordamida ifodalash mumkinligi qat'iy isbotlangan. Intuitiv ravishda, bu haqiqat aniq, keling, haqiqat jadvaliga ko'ra formulani tuzish algoritmini eslaylik. Biroq, biz faqat ushbu operatsiyalardan foydalanamiz. Belgilanishning bu shakli deyiladi disjunktiv normal shakl (DNF). Bu mantiqiy algebra formulalarini normallashtirish mexanizmining bir turi. Ta'rifi: DNF Har xil elementar qo'shma gaplarning diszyunksiyasi (ya'ni, har bir qo'shma gap elementar gaplardan yoki ularning inkorlaridan iborat). CNF xuddi shunday aniqlanadi - kon'yunktiv normal shakl. Ta'rifi: Agar DNFda barcha elementar birikmalar DNF bog'liq bo'lgan o'zgaruvchilar soniga teng bir xil darajaga ega bo'lsa, u deyiladi. mukammal (SDNF). Teorema. Xuddi shunday noto'g'ri bo'lmagan har qanday funktsiya uchun noyob SDNF ham mavjud. Natija ... Xuddi shunday noto'g'ri bo'lmagan har qanday mantiqiy funktsiya superpozitsiya sifatida taqdim etilishi mumkin &, , va inkor faqat o'zgaruvchilarga tegishli. Ta'rifi: Mantiqiy amallar tizimi, agar ushbu amallar va ushbu tizimning konstantalaridan foydalanib, mantiqiy algebraning istalgan funksiyasini ifodalash mumkin bo'lsa, funktsional tugallangan deb ataladi. Tizimlar (&, , ); (, ); (&, ), (/) - funksional jihatdan tugallangan (&, ) - funktsional jihatdan to'liq emas. Biz bu faktlarni isbotsiz qabul qilamiz va masalalarni yechishda istalgan formulani (&, , ) yordamida ifodalashga harakat qilamiz. Keyinchalik operatsiyalar tizimining funktsional to'liqligi va to'liq emasligi masalasini batafsilroq ko'rib chiqamiz. 1.7-mavzu. Mantiqiy ifodalarni soddalashtirish usullari. Mantiqiy masalalarni yechish usullari. Keling, mantiqiy masalani yechish misolini ko'rib chiqaylik. Misol : Ekspeditsiya ishtirokchilari tarkibini muhokama qilib, ikkita shart bajarilishi kerak degan qarorga keldi. Agar Arbuzov ketsa, Bryukvin yoki Vishnevskiy ketishi kerak
Agar Arbuzov va Vishnevskiy ketsa, Bryukvin ketadi Ramziy shaklda qaror qabul qilishning mantiqiy formulasini tuzing, natijada olingan formulani soddalashtiring va undan foydalangan holda ekspeditsiyani shakllantirishning yangi shartini tuzing. Keling, o'zgaruvchilar va ularga mos keladigan elementar bayonotlarni kiritamiz. - Arbuzov ketadi Mantiqiy algebra qonunlari va o'ziga xosliklaridan foydalanib, siz mantiqiy ifodalarni soddalashtirishingiz mumkin. Xizmat maqsadi... Onlayn kalkulyator uchun mo'ljallangan mantiqiy ifoda uchun haqiqat jadvalini tuzish . Haqiqat jadvali - kiritilgan o'zgaruvchilarning barcha mumkin bo'lgan kombinatsiyalarini va ularning tegishli chiqish qiymatlarini o'z ichiga olgan jadval. Haqiqat jadvali 2 n qatorni o'z ichiga oladi, bu erda n - kirish o'zgaruvchilar soni va n + m - ustunlar, bu erda m - chiqish o'zgaruvchilari. Ko'rsatma. Klaviaturadan kiritishda quyidagi belgidan foydalaning: Masalan, abc + ab ~ c + a ~ bc mantiqiy ifodani quyidagicha kiritish kerak: a * b * c + a * b = c + a = b * c Mantiqiy diagramma shaklida ma'lumotlarni kiritish uchun ushbu xizmatdan foydalaning. Mantiqiy funktsiyani kiritish qoidalari 1. v o'rniga + dan foydalaning (dizyunksiya, OR). 2. Mantiqiy funktsiyadan oldin funktsiya belgilovchisi kerak emas. Misol uchun, F (x, y) = (x | y) = (x ^ y) o'rniga, siz shunchaki (x | y) = (x ^ y) ni kiritishingiz kerak. 3. O'zgaruvchilarning maksimal soni - 10 ta. Kompyuterning mantiqiy sxemalarini loyihalash va tahlil qilish matematikaning maxsus bo'limi - mantiq algebrasi yordamida amalga oshiriladi. Mantiq algebrasida uchta asosiy mantiqiy funktsiyani ajratib ko'rsatish mumkin: "EMAS" (inkor), "VA" (konjunksiya), "OR" (dizyunksiya). Har qanday mantiqiy qurilmani yaratish uchun chiqish o'zgaruvchilarning har birining operatsion kirish o'zgaruvchilarga bog'liqligini aniqlash kerak, bunday bog'liqlik kommutatsiya funktsiyasi yoki mantiq algebrasining funktsiyasi deb ataladi. Mantiqiy algebra funktsiyasi, agar uning barcha 2 n qiymatlari berilgan bo'lsa, to'liq aniqlangan deb ataladi, bu erda n - chiqish o'zgaruvchilari soni. Agar barcha qiymatlar aniqlanmagan bo'lsa, funktsiya qisman aniqlangan deb aytiladi. Qurilmaning holati mantiqiy algebra funktsiyasi yordamida tasvirlangan bo'lsa, u mantiqiy deb ataladi. Mantiq algebrasining funksiyasini ifodalash uchun quyidagi usullardan foydalaniladi: • og'zaki tavsif - dastlabki loyihalash bosqichida qo'llaniladigan va shartli tasvirga ega bo'lgan shakl. • mantiq algebrasining funksiyasini haqiqat jadvali shaklida tasvirlash.
• mantiq algebrasi funktsiyasini algebraik ifoda ko'rinishida tavsiflash: FAL ning ikkita algebraik shakllari qo'llaniladi: a) 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
|
|
Bosh sahifa
Aloqalar
Bosh sahifa
Zbekiston respublikasi raqamli texnologiyalar vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalar universiteti
|
