Diskret tuzilmalar
Normal formalar. Mukammal diz’yunktiv normal forma ( MDNF ), mukammal kon’yunktiv normal forma
Download 224.93 Kb.
|
3-mustaqil ish
|
Normal formalar. Mukammal diz’yunktiv normal forma ( MDNF ), mukammal kon’yunktiv normal forma
( MKNF ). Á1, Á2, . . . , Án ( n³ 1 ) mulohazalar algebrasining formulalari bo‘lsin, u holda (. . .( ( Á1 Ù Á2 ) Ù Á3 ). . . Án ) –formula Á1, Á2 , . . . , Án – formulalarning kon’yunksiyasi deyiladi va ( Á1 Ù . . . Ù Án ) orqali belgilanadi. (. . .( ( Á1 Ú Á2 ) Ú Á3 ) . . . Án ) – formula esa Á1 , Á2 , . . . , Án - formulalarning diz’yunksiyasi deyiladi va ( Á1 Ú . . . Ú Án) orqali belgilanadi. I.7.1 - ta’rif. Propozitsional o‘zgaruvchiyoki ularning inkorlaridan tuzilgan iùtiyoriy kon’yunksiya (diz’yunksiya) elementar kon’yunksiya (diz’yunksiya) deyiladi. I.7.2 - ta’rif. Elementar kon’yunksiyalarning ixtiyoriy diz’yunksiyasi - diz’yunktiv normal forma (DNF), elementar diz’yunksiyalarning ixtiyoriy kon’yunksiyasi - kon’yunktiv normal forma (KNF) deyiladi. I.7.3 - misol. X1, X2, X3 – propozitsional o‘zgaruvchiberilgan bo‘lsin, u holda ( X1 Ù X2 ) Ú X3 – DNF ga, ( X1Ú X2 ) Ù ( X1Ú X3 ) – KNF ga misol bo‘ladi. I.7.4 - ta’rif. Á formula X1, X2 ,. . . ,Xn – propozitsional o‘zgaruvchilardan tuzilgan elementar kon’yunksiya bo‘lsin. Agar har bir propozitsional o‘zgaruvchi, inkori ham ùisoblanganda, Á da bir martadan ortiqqatnashmasa Á - tû\ri, kamida bir marta qatnashsa , Á - to‘liq, faqat bir marta qatnashsa, Á - mukammal elementar kon’yunksiya deyiladi. To‘g‘ri va to‘liq elementar kon’yunksiya mukammal elementar kon’yunksiya bo‘lishi ravshan. I.7.5 - misol. X1, X2 , X3 –propozitsional o‘zgaruvchiberilgan bo‘lsin. U holda ù X1 Ù X2 – to‘g‘ri, X1 Ù X2 Ù X3 Ù Ù ù X1 Ù ù X2 - tûliq, X1 Ù ù X2 Ù X3 – mukammal elementar kon’yunksiyalardir. I.7.6 - ta’rif. Á - formula X1, . . . ,Xn – o‘zgaruvchilardan tuzilgan elementar diz’yunksiya bo‘lsin. Agar har bir propozitsional o‘zgaruvchi, inkori ham ùisoblanganda, Á - formulada bir martadan ortiq qatnashmasa, tzg‘ri, kamida bir marta qatnashsa, to‘liq, faqat bir marta qatnashsa, mukammal elementar diz’yunksiya deyiladi. I.7.7 - misol. X1 , X2 , X3 - propozitsional o‘zgaruvchiberilgan bo‘lsin. U holda X1 Ú ù X2 – tû\ri, ù X1 Ú X2 Ú ù X3 Ú ù X1 – tûliq, X1 Ú ù X2 Ú X3 – mukammal elementar diz’yunksiyalardir. I.7.8 - ta’rif. Turli mukammal elementar kon’yunksiya ( diz’yunksiya ) lardan tuzilgan diz’yunksiya ( kon’yunksiya ) mukammal diz’yunktiv ( kon’yunktiv ) normal forma MDNF ( MKNF ) deyiladi. I.7.9 - misol. X1, X2, X3 – propozitsional o‘zgaruvchiberilgan bo‘lsin. U holda ( X1 Ù ù X2 Ù X3 ) Ú ( X1 Ù X2 Ù ù X3 ) Ú ( ù X1 Ù X2 Ù X3 ) - MNDF ; ( X1 Ú ù X2 Ú X3 ) Ù ( X1 Ú X2 Ú X3 ) – MKNF bo‘ladi. I.7.10 -ta’rif. Mulohazalar algebrasining Á formulasiga teng kuchli DNF ( KNF, MDNF, MKNF ) Á - formulaning DNF ( KNF, MDNF, MKNF ) si deyiladi. I.7.11 - teorema. Mulohazalar algebrasining ixtiyoriy formasining DNF ( KNF ) si mavjud. I.7.12 - teorema. Mulohazalar algebrasining ixtiyoriy Á formulasining MDNF ( MKNF ) i mavjud. I.7.14 - misol. X1 Ù ( X2 Ú X3 ) formulaning MDNF ini toping. Avval X1 Ù ( X2 Ú X3 ) ning DNF ini topaylik. I.3.6 dagi 20 - tengkuchlilikka asosan : X1 Ù ( X2 Ú X3 ) º ( X1 Ù X2 ) Ú ( X1 Ù X3 ) . X1 Ù X2 va X1 Ù X3 – larning MDNF larini I.3.6 da keltirilgan tengkuchliliklar yordamida topamiz. X1 Ù X2 º X1 Ù X2 Ù 1 º X1 Ù X2 Ù ( X3 Ú ù X3 ) º º ( X1 Ù X2 Ù X3 ) Ú ( X1 Ù X2 Ù ù X3 ) . X1 Ù X3 º X1 Ù 1 Ù X3 º X1 Ù ( X2 Ú ù X2 ) Ù X3 º º ( X1 Ù X2 Ù X3 ) Ú ( X1 Ù ù X2 Ù X3 ) . Bundan, ( X1 Ù X2 ) Ú ( X1 Ù X3 ) º ( X1 Ù X2 Ù X3 ) Ú ( X1 Ù Ù X2 Ùù X3 ) Ú ( X1 Ù X2 Ù X3 ) Ú ( X1 Ù ù X2 Ù X3 ) º ( X1 Ù X2 Ù X3 ) Ú ( X1 Ù ù X2 Ù X3 ) Ú ( X1 Ù X2 Ù ù X3 )- MDNF. Demak, X1 Ù ( X2 Ú X3 ) – formulaning MDNF i ( X1 Ù X2 Ù X3 )Ú ( X1 Ù ù X2 Ù X3 ) Ú ( X1 Ù X2 Ù ù X3 ) – formuladan iborat ekan. Download 224.93 Kb. Do'stlaringiz bilan baham: 
|