12-mavzu mukammal diz’yunktiv va kon’yunktiv normal shakllar

12-mavzu mukammal diz’yunktiv va kon’yunktiv normal shakllar

12-MAVZU

Mukammal diz’yunktiv va kon’yunktiv normal shakllar.
Normal shakllar.
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. A₁, A₂, …, A_n fikr o‘zgaruvchilarining kon’yunktiv bir hadi deb, ushbu o‘zgaruvchilar yoki ularning teskarilarining kon’yunksiyasiga aytiladi.
Masalan: ⌐A₁&A₂&A₃, ⌐A₁&A₂&A₃&⌐A₄


Ta’rif 2. A₁, A₂, …, A_n fikr o‘zgaruvchilarining diz’yunktiv bir hadi deb, ushbu o‘zgaruvchilarning yoki ularning teskarilarining diz’yunksiyasiga aytiladi.
Masalan: ⌐A₁\/A₂\/A₃


Ta’rif 3. Diz’yunktiv normal shakl (DNSh)deb, kon’yunktiv bir hadlar diz’yunksiyaga aytiladi, ya’ni a_i , i=1, 2, …, k kon’yunktiv bir hadlar bo‘lsa a₁\/a₂\/…\/a_n - ifodaga Diz’yunktiv normal shakl deyiladi.

Ta’rif 4. Kon’yunktiv normal shakl (KNSh) deb, dizyunktiv bir hadlar kon’yunksiyasiga ayiladi, ya’ni b_i , i=1, 2, …,l kon’yunktiv bir hadlar bo‘lsa, b₁&b₂&…&b_n – ifoda KNSh deyiladi.
Har bir formula uchun cheksiz ko‘p KNSh, DNSh lari mavjud.


Mukammal normal shakllar

Ta’rif 5. Agar bir hadga A_i yoki ⌐A_i formulalar juftligidan faqat bittasi kirgan bo‘lsa, A₁, A₂, …, A_n fikr o‘zgaruvchilarining kon’yunktiv yoki diz’yunktiv bir hadlari mukammal deyiladi.
Ta‘rif 6. Agar KNSh yoki DNSh larda A₁, A₂, …, A_n o‘zgaruvchilarning takrorlanmaydigan mukammal bir hadlari kirgan bo‘lsa, A₁, A₂, …, A_n 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.

http://fayllar.org