Talim vazirligi buxoro davlat universiteti fizika-matematika fakulteti

Eslatma: Biz bu paragrafda A B formulani qisqacha AB ko`rinishida yozamiz.
Quyidagi belgilashni kiritamiz:

Aᵅ=

1-ta`rif. A<sub>1</sub> A<sub>2</sub> ... A<sub>n</sub> propozitsional o`zgaruvchilar

1va 0 lardan tuzilgan tanlanma bo`lsa, u holda A₁<sup>α₁</sup>,A₂<sup>α₂</sup>,…Aₙ<sup>αₙ</sup> formula elementar konyunksiya deyiladi (bunda propozitsional o‘zgaruvchilar takrorlangan bo‘lishi ham mumkin).
1-misol. A, A formulalar elementar konyunksiyalardir.
2-ta`rif. Elementar konyunksiyalarning har qanday dizyunksiyasi dizyunktiv normal forma (DNF) deyiladi.
2-misol. A A formula 6.1-misolda keltirilgan elementar konyunksiyalardan tuzilgan DNF dir.
3-ta`rif. Agar elementar konyunksiyasiga har bir propozitsional o‘zgaruvchi (inkor belgisi qatnashganini ham e‘tiborga olsak) bir martadan ortiq kirmagan bo‘lsa, bunday elementar konyunksiya to‘g‘ri elementar konyunksiya deyiladi.
3-misol. A , A₁ A₂A<sub>3 4</sub> formulalar to‘g‘ri elementar
konyunksiyalardir. 6.2-misolda keltirilgan formulaning dastlabki ikkita hadi to‘g‘ri elementar konyunksiyadir.
4-ta`rif. A₁ A₂ ... A_n propozitsional o‘zgaruvchilardan tuzilgan to‘g‘ri elementar konyunksiyadagi har bir propozitsional o‘zgaruvchi bu konyunksiyaga faqat bir marta
kirgan bo‘lsa, bunday elementar konyunksiyaga faqat bir marta kirgan bo‘lsa, bunday elementar konyunksiya A₁ A₂ ... A_n o‘zgaruvchilarga nisbatan to‘liq elementar konyunksiya deyiladi.
4-misol. Elementar konyunksiyalar A,B,C o‘zgaruvchilardan tuzilgan bo‘lsin. U holda ABC, formulalar to‘liq elementar konyunksiyalardir.
5-ta`rif. Tarkibida bir xil elementar konyunksiyalar bo‘lmagan hamda barcha elementar konyunksiyalar A₁ A₂ ... A_n o‘zgaruvchilarga nisbatan to‘g‘ri va to‘liq bo‘lgan DNF A₁ A₂ ... A_n o‘zgaruvchilarga nisbatan mukammal dizyunktiv normal forma (MDNF) deyiladi.

5-misol . ABCA formula A, B, C o`zgaruvchilarga nisbatan MDNF dir . DNF va MDNF larning ta`rifidan ko`rinadiki , bunday formulalar keltirilgan formulalardir.

1- teorema. Mulohazalar algebrasining AYo formula bo`lmagan ixtiyoriy U formulasi yagona MDNF ga teng kuchlidir.

Isbot. F(A₁ A₂ ... A_n ) mulohazalar algebrasining ixtiyoriy AYo formula bo‘lmagan formulasi bo‘lsin. Demak, F bajariluvchi formula bo‘lib, u propozitsional o‘zgaruvchilar qiymatlarining hech bo‘lmaganida bitta tanlanmaida 1 qiymat qabul qiladi. F formulani
rostga aylantiruvchi tanlanmalar to‘plami M_(p) bo‘lsin:

M_(p) = {(αˡ₁, α₂ˡ, …, αₙˡ) , (α₁², α₂²,…, αₙ²),…, (α₁ͬ, α₂ͬ, … , αₙͬ) },

Bunda 1ⁿ . Quyidagi DNF ni qaraylik :


G(A₁ A₂ ... A_n) ^α₁ˡ, A₂^α₂ˡ, …A_n^αₙˡ… A₁^α₁ͬ A₂^α₂ͬ …Aₙ^αₙͬ (2)

Mazkur DNF MDNF ekanligi ravshandir, chunki M_(p) ning elementlari har xil tanlanmalaridir. U( A₁ A₂ ... A_n)

ekanligini ko`rsatamiz (α₁ͬ, α₂ͬ, … , αₙͬ) bo`lsin. U holda F(α₁ͬ, α₂ͬ, … , αₙͬ)=1 bo`ladi. ( M<sub>(p)</sub> to`plamning tanlanishiga asosan ). G(A₁ A₂ ... A_n) formulaning (α₁ͬ, α₂ͬ, … , αₙͬ) tanlanmadagi qiymatini hisoblaylik.

(2) dagi MDNF tarkibida ^α₁ˡ, A₂^α₂ˡ, …A_n^αₙˡ to`liq elementar konyunksiya qatnashgan bo`lib, G(A₁ A₂ ... A_n) ning (α₁^s, α₂^s,…, αₙ^s)

tanlanmadagi G(α₁^s, α₂^s,…, αₙ^s) qiymatini hisoblashda (α₁^s) ^α₁ˢ, (α₂^s)^α₂ˢ,…,( αₙ^s)^αₙˢ had hosil qiladi . (1) ga asosan 1¹=1 hamda 0⁰=, chunki A¹=A , A⁰=

Demak, αˢ_i qanday bo`lishidan qat`iy nazar (α₁^s) ^α₁ˢ=1 (i=1,2,…,n) hamda (α₁^s) ^α₁ˢ, (α₂^s)^α₂ˢ,…,( αₙ^s)^αₙˢ =1 (1

A⋁1=1 ga asosan G(α₁^s, α₂^s,…, αₙ^s)=1bo`ladi.

Shunday qilib, M_(p) ga tegishli tanlanmalarda berilgan F formula ham, G formula ham 1 qiymat qabul qilar ekan.

β=(β₁, β₂, β_n) M_(p)
bo‘lgan ixtiyoriy tanlanma bo‘lsin. U holda bu tanlanma M_(p)
ga kiruvchi ixtiyoriy tanlanmadan hech bo‘lmaganda bitta
elementi bilan farq qiladi. ( bu tanlanmalar tartiblangan tanlanmalar ekanligini eslatib
o‘tamiz ) B ning β tanlanmadagi qiymatini hisoblashda hosil bo‘ladigan ifodada qatnashgan ixtiyoriy

(β₁) ^α₁ˢ, (β₂)^α₂ˢ,…,( βₙ)^αₙˢ (1
hadda hech bo‘lmaganda bitta i uchun β₁ dir. (1) ga asosan

1⁰= va 0¹= 0 bo‘lgani uchun (3) ifodaning qiymati 0 ga tengdir. Bundan G(β₁, β₂, β_n)=0

ekanligi kelib chiqadi . M_(p) bo`lgani uchun F(β₁, β₂, β_n)=0

demak M_(p) ga kirmagan tanlanmalarda F va G formulalar 0 qiymatga ega ekan . Shunday qilib , F=G ya`ni F formula (2) MDNF ga teng kuchli ekanligi kelib chiqadi . F formula yagona usulda MDNF ga yoyilishi ravshandir, chunki, G formula F formulaning
qiymatini 1 ga aylantiruvchi barcha tanlanmalar yordamida yagona usulda hosil qilinadi.