Aborot texnologiyalari va kommunikatsiyalarini rivojlantirish vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti

х_i*х = 0 bo‘lgani uchun bunday amal funksiyaning qiymatiga ta’sir qilmaydi. х_i*х ifodani qandaydir Y hadiga qo‘shish natijasida quyidagi ko‘rinishga keltiruvchi Yх_i *х

ifoda hosil qilinadi
Bu tenglikning to‘q‘riligi taqsimlash qonunidan kelib chiqadi, buni ifodaning o‘ng tomonidagi qavslarni ochish orqali ko‘rsatish mumkin. Quyidagi funksiya misolida

KNSH dan MKNSHga o‘tishni ko‘rib chiqamiz:

Quyidagi ifodaning biror hadining ustida almashtirish bajarib taqsimot qonunini qo‘llashni ko‘rsatamiz:

Belgilaymiz

Zarur belgilashlarni kiritgandan so‘ng, taqsimot qonuni asosida quyidagiga ega bo‘lamiz

Quydagicha belgilab taqsimot qonunini qo‘llaymiz.

Z₁ va Z₂ ning qiymatlarini, o‘rniga qo‘iyb KNSH dan MKNSHga o‘tishda keltirilgan ifodaning mos hadlarini hosil qilamiz.
MKNSH funksiyalar rostlik jadvali bo‘yicha oson quriladi. Misol sifatida 3.1 jadvalda keltirilgan funkiyani ko‘rib chiqamiz.
(2.3)
Ifoda f(x₁, x₂, x₃) funksiyasi rostlik jadvalida qiymatlari orasida nechta nol bo‘lsa, shuncha konyunksiya amali bilan bog‘langan hadlarga ega. Shunday qilib, funksiya nolga teng bo‘ladigan argumentlar qiymati toplamiga shu to‘plamda nol qiymatga ega bo‘luvchi MKNSHning aniq bir hadi mos keladi. MKNSH hadlari kon’yunksiya amali bilan bog‘langanligi uchun, hadlaridan birortasi nolga teng bo‘lsa funksiya ham nolga teng bo‘ladi.
Shunday qilib, rostlik jadvali orqali berilgan MKNSH funksiyani yozish qoydasini keltiramiz. Argumentlar qiymatlarining qancha to‘plamlarida funksiya nolga teng bo‘lsa, barcha argumentlar diz’yunksiyasini tashkil qiluvchi, shuncha kon’yunktiv hadlarni yozish kerak va agar to‘plamda argumentning qiymati 1 ga teng bo‘lsa,u holda diz’yunksiyaga shu argumentning inversiyasi kiradi.
Ihtiyoriy funksiya yagona MNKSH ga ega.
Mantiqiy qurilmaning tuzilmali sxemasi bevosita amalga oshirilayotgan funksiyaning kanonik shakliga (MDNSH yoki MKNSH) asosan quriladi. (3.2 ) va (3.3) funksiyalar uchun hosil qilingan sxemasi 3.9a va 3.9b rasmda keltirilgan

16-rasm

17-rasm

Qurilmaning, umuman olganda, to‘g‘ri ishlashini ta’minlovchi bu usulning kamchiligi ham yo‘q emas. Hosil qilingan sxemalar juda murakkab, katta sondagi mantiqiy elementlardan foydalanishni talab qiladi, unumliligi va ishonchliligi juda quyi. Ko‘p hollarda funksiyalarni o‘zgartirmasdan mantiqiy ifodalarni shunday soddalashtirish mumkinki, bunda mos keluvchi tuzilmali sxema soddaroq bo‘lib qoladi. Funksiyani bunday soddalashtirish funksiyalarni minimallashtirish deyiladi

Ta'rif. Agar formula ma'lum miqdordagi o'zgaruvchilarning dis'yunksiyasi yoki ularning inkori natijasida hosil bo'lsa, elementar dis'yunksiya deyiladi.
Misollar: ¬ x 3, x 1 ∨ x 2, x 1 ∨ x 2 ∨ ¬ x 3
Ta'rif. Formula, agar u takrorlanmaydigan elementar disjunksiyalarning birikmasi bo'lsa, kon'yunktiv normal shakl (CNF) deb ataladi.
CNF quyidagi ko'rinishda yoziladi: F 1 ∧ F 2 ∧ ... ∧ F n, bu erda F i elementar dis'yunksiya.
Misollar: (x 1 ∨ ¬ x 2) ∧ x 3, (x 1 ∨ x 2) ∧ (¬ x 1 ∨ x 2 ∨ x 3) ∧ (x 1 ∨ ¬ x 2 ∨ ¬ x 3)
Ta'rif. K o'zgaruvchidagi mantiqiy formula mukammal kon'yunktiv normal shakl (KDNF) deb ataladi, agar:
1) formula CNF bo'lib, unda har bir elementar dis'yunksiya k o'zgaruvchilari x 1 , x 2 , …, x k ning dis'yunksiyasidir va bu dis'yunktsiyaning i-o'rni yo o'zgaruvchisi x i yoki uning inkori;
2) bunday CNFdagi barcha elementar disjunksiyalar juft-juft farqlanadi.
Misol: (x 1 ∨ x 2 ∨ x 3) ∧ (¬ x 1 ∨ ¬ x 2 ∨ x 3)
e'tibor bering, bu 0 yoki 1 ga teng bo'lmagan har qanday mantiqiy funktsiya SDNF yoki SKNF sifatida ifodalanishi mumkin.
Algoritmlar tahlili shuni ko'rsatadiki, agar funksiyaning qiymati haqiqat jadvalining ko'p satrlarida 0 ga teng bo'lsa, uning mantiqiy formulasini olish uchun SDNF, aks holda SKNF qurish yaxshidir.
Misol: uchta o'zgaruvchining mantiqiy funktsiyasining haqiqat jadvali berilgan. Ushbu funktsiyani amalga oshiradigan mantiqiy formulani tuzing.