O’zbekiston Respublikasi Axborot Texnologiyalari va kommunikatsiyalarini qo’llab quvvatlash vazirligi Muhammad Al-Xorazmiy nomidagi Toshkent Axborot Texnologiyalari Universiteti KIF fakulteti 219-21 guruhi talabasi Rahimov UDiskret tuzilmalar fanidan tayyorlagan
MUSTAQIL ISH
Mavzu: MUKAMMAL KON’YUKTIV NORMAL SHAKL (MKNSH),UNI TUZISH USULLARI.
Bajardi: Rahimov U. Tekshirdi: Qo’ldoshev H. Toshkent 2022.
Har bir fikr algebrasi formulasi uchun unga teng kuchli bo‘lgan va faqatgina inkor ⌐, kon’yunksiya &, diz’yunksiya \/ amallarini o‘z ichiga olgan formulani keltirish mumkin. Buning uchun implikasiya va ekvivalensiyadan qutulish qoidalaridan foydalanish kifoya.
Ta’rif 1. A1, A2, …, An fikr o‘zgaruvchilarining kon’yunktiv bir hadi deb, ushbu o‘zgaruvchilar yoki ularning teskarilarining kon’yunksiyasiga aytiladi.
Masalan: ⌐A1&A2&A3 , ⌐A1&A2&A3&⌐A4
Ta’rif 2. A1, A2, …, An fikr o‘zgaruvchilarining diz’yunktiv bir hadi deb, ushbu o‘zgaruvchilarning yoki ularning teskarilarining diz’yunksiyasiga aytiladi.
Masalan: ⌐A1\/A2\/A3 https://hozir.org/mavzu--mantiqiy-elementlar-va-sxemalar-v3.html?page=10
Ta’rif 5. Agar bir hadga Ai yoki ⌐Ai formulalar juftligidan faqat bittasi kirgan bo‘lsa, A1, A2, …, An fikr o‘zgaruvchilarining kon’yunktiv yoki diz’yunktiv bir hadlari mukammal deyiladi.
Ta‘rif 6. Agar KNSh yoki DNSh larda A1, A2, …, An o‘zgaruvchilarning takrorlanmaydigan mukammal bir hadlari kirgan bo‘lsa, A1, A2, …, An fikr o‘zgaruvchilarining KNSh yoki DNSh lari mukammal deyiladi.
Masalan: A&B\/⌐A&B\/A&⌐B – A va B fikr o‘zgaruvchilarining Mukammal diz’yunktiv normal shakli (MDNSh) bo‘ladi. A\/B – esa MKNSh bo‘ladi.
Teorema 1. Har bir ayniy yolg‘on bo‘lmagan formula yagona MDNF ega bo‘ladi.
Teorema 2. Har bir tavtologiya bo‘lmagan fikrlar algebrasi formulasi, yagona MKNSh ga ega bo‘ladi.
