Сборник задач по дискретной математике. Учебное пособие. Москва: Наука

1- teorema. Elementar mulohazalarning tavtologiyadan farqli ixtiyoriy formulasini MKNShga keltirish mumkin.
Teoremaning quyidagi konstruktiv isboti tavtologiyadan farqli ixtiyoriy mantiqiy formulani MKNShga keltirish algoritmi sifatida ishlatilishi mumkin.
1. Berilgan formulani KNShga keltiramiz.
Buning uchun formulani faqat kon’yunksiya, diz’yunksiya va inkor mantiqiy amallari orqali ifodalaymiz (bunda inkor amali faqatgina o‘zgaruvchilarga nisbatan qo‘llanilgan bo‘lishi kerak). Formulani KNShga keltirish jarayonida, vaziyatga qarab, zarur qoida va qonunlardan foydalangan holda mumkin bo‘lgan soddalashtirishlarni bajaramiz.
2. Agar KNSh ifodasida bittadan ko‘p bir xil elementar diz’yunksiyalar topilsa, u holda teng kuchlilikdan foydalanib, ulardan faqat bittasini berilgan formulaning ifodasida qoldiramiz.
3. Agar KNSh ifodasidagi barcha elementar diz’yunksiyalar to‘g‘ri elementar diz’yunksiyalar bo‘lsa, u holda algoritmning 4- bandiga o‘tamiz, aks holda barcha elementar diz’yunksiyalarni to‘g‘ri elementar diz’yunksiyalarga aylantiramiz.
Buning uchun, vaziyatga qarab, quyidagi ikki jarayon qo‘llanilishi mumkin:
a) agar biror elementar diz’yunksiya ifodasida birorta o‘zgaruvchi o‘zining inkori bilan birgalikda qatnashgan bo‘lsa, u holda , va teng kuchliliklarga asosan bu elementar kon’yunksiyani KNSh ifodasidan olib tashlaymiz;
b) agar qandaydir elementar diz’yunksiya ifodasida biror o‘zgaruvchi bir
necha marta qatnashgan (barcha hollarda yo inkor ishorasi ostida yoki barcha hollarda inkor ishorasi ostida emas) bo‘lsa, u holda teng kuchlilikka asosan ulardan faqatgina bittasini elementar diz’yunksiya ifodasida qoldiramiz.
Natijada, barcha elementar diz’yunksiyalar to‘g‘ri elementar diz’yunksiyalarga aylanadi.
4. Agar KNSh ifodasidagi barcha elementar diz’yunksiyalar to‘liq elementar diz’yunksiyalar bo‘lsa, u holda algoritmning 6- bandiga o‘tamiz, aks holda barcha elementar diz’yunksiyalarni to‘liq elementar diz’yunksiyalarga aylantiramiz. Agar KNShdagi biror elementar diz’yunksiya to‘liq elementar diz’yunksiya bo‘lmasa, ya’ni biror diz’yunktiv had ifodasidagi elementar mulohazalardan ba’zilari (yoki ularning inkorlari) topilmasa, u holda bunday elementar diz’yunksiyani quyidagi usul yordamida to‘liq elementar diz’yunksiya holiga keltiramiz.
Masalan, tarkibida elementar mulohazalalar ishtirok etgan, tavtologiyadan farqli, elementar diz’yunksiya ifodasida faqat o‘zgaruvchi yoki uning inkori yo‘q deb faraz qilaylik. U holda va teng kuchliliklardan foydalanib elementar diz’yunksiyani ikkita to‘liq elementar diz’yunksiyalar kon’yunksiyasiga keltiramiz:

.
Agar biror elementar diz’yunksiya ifodasida ta o‘zgaruvchilar qatnashmayotgan bo‘lsa, u holda bu jarayonni har bir o‘zgaruvchi uchun (ya’ni, marta) yoki ta o‘zgaruvchilar uchun birdaniga qo‘llash natijasida bitta to‘liq bo‘lmagan elementar diz’yunksiya o‘rnida unga teng kuchli ta to‘liq elementar diz’yunksiyalar kon’yunksiyalariga ega bo‘lamiz.
5. Agar 4- band bajarilishi natijasida KNSh ifodasida bir xil elementar diz’yunksiyalar paydo bo‘lsa, u holda algoritmning 2- bandiga o‘tamiz.
6. Algoritm tugadi.
Demak, formulani MKNShga keltirish algoritmini qo‘llash natijasida berilgan KNSh ifodasida bir xil elementar diz’yunksiyalar qatnashmaydi va barcha elementar diz’yunksiyalar to‘g‘ri va to‘liq bo‘ladi. 1- ta’rifga asosan bunday KNSh
MKNShdir. ■