Formulalar. Asosiy teng kuchli formulalar. Normal formalar. Mulohazalar hisobini qurish. Teng kuchli almashtirishlar. Normal formalar. Mulohazalar algebrasi

Normal formalar. Mukammal diz’yunktiv normal forma ( MDNF ), mukammal kon’yunktiv normal forma
( MKNF ).
Á₁, Á₂, . . . , Á_n ( n³ 1 ) mulohazalar algebrasining formulalari bo‘lsin, u holda (. . .( ( Á₁ Ù Á₂ ) Ù Á₃ ). . . Á_n ) –formula Á₁, Á₂ , . . . , Á_n – formulalarning kon’yunksiyasi deyiladi va ( Á₁ Ù . . . Ù Á_n ) orqali belgilanadi.
(. . .( ( Á₁ Ú Á₂ ) Ú Á₃ ) . . . Á_n ) – formula esa Á₁ , Á₂ , . . . , Á_n - formulalarning diz’yunksiyasi deyiladi va ( Á₁ Ú . . . Ú Á_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. X₁, X₂, X₃ – propozitsional o‘zgaruvchiberilgan bo‘lsin, u holda ( X₁ Ù X₂ ) Ú X₃ – DNF ga,
( X₁Ú X₂ ) Ù ( X₁Ú X₃ ) – KNF ga misol bo‘ladi.
I.7.4 - ta’rif. Á formula X₁, X₂ ,. . . ,X_n – 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. X₁, X₂ , X₃ –propozitsional o‘zgaruvchiberilgan bo‘lsin. U holda ù X₁ Ù X₂ – to‘g‘ri, X₁ Ù X₂ Ù X₃ Ù
Ù ù X₁ Ù ù X₂ - tûliq, X₁ Ù ù X₂ Ù X₃ – mukammal elementar kon’yunksiyalardir.
I.7.6 - ta’rif. Á - formula X₁, . . . ,X_n – 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. X₁ , X₂ , X₃ - propozitsional o‘zgaruvchiberilgan bo‘lsin. U holda X₁ Ú ù X₂ – tû\ri,

ù X₁ Ú X₂ Ú ù X₃ Ú ù X₁ – tûliq, X₁ Ú ù X₂ Ú X₃ – 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. X₁, X₂, X₃ – propozitsional o‘zgaruvchiberilgan bo‘lsin. U holda
( X₁ Ù ù X₂ Ù X₃ ) Ú ( X₁ Ù X₂ Ù ù X₃ ) Ú ( ù X₁ Ù X₂ Ù X₃ ) - MNDF ; ( X₁ Ú ù X₂ Ú X₃ ) Ù ( X₁ Ú X₂ Ú X₃ ) – 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. X₁ Ù ( X₂ Ú X₃ ) formulaning MDNF ini toping. Avval X₁ Ù ( X₂ Ú X₃ ) ning DNF ini topaylik. I.3.6 dagi 20 - tengkuchlilikka asosan :
X₁ Ù ( X₂ Ú X₃ ) º ( X₁ Ù X₂ ) Ú ( X₁ Ù X₃ ) .
X₁ Ù X₂ va X₁ Ù X₃ – larning MDNF larini I.3.6 da keltirilgan tengkuchliliklar yordamida topamiz.
X₁ Ù X₂ º X₁ Ù X₂ Ù 1 º X₁ Ù X₂ Ù ( X₃ Ú ù X₃ ) º
º ( X₁ Ù X₂ Ù X₃ ) Ú ( X₁ Ù X₂ Ù ù X₃ ) .
X₁ Ù X₃ º X₁ Ù 1 Ù X₃ º X₁ Ù ( X₂ Ú ù X₂ ) Ù X₃ º
º ( X₁ Ù X₂ Ù X₃ ) Ú ( X₁ Ù ù X₂ Ù X₃ ) . Bundan,
( X₁ Ù X₂ ) Ú ( X₁ Ù X₃ ) º ( X₁ Ù X₂ Ù X₃ ) Ú ( X₁ Ù
Ù X₂ Ùù X₃ ) Ú ( X₁ Ù X₂ Ù X₃ ) Ú ( X₁ Ù ù X₂ Ù X₃ ) º
( X₁ Ù X₂ Ù X₃ ) Ú ( X₁ Ù ù X₂ Ù X₃ ) Ú ( X₁ Ù X₂ Ù ù X₃ )-
MDNF. Demak, X₁ Ù ( X₂ Ú X₃ ) – formulaning MDNF i
( X₁ Ù X₂ Ù X₃ )Ú ( X₁ Ù ù X₂ Ù X₃ ) Ú ( X₁ Ù X₂ Ù ù X₃ ) – formuladan iborat ekan.