Tayanch iboralar

Mavzu: Mulohazalar algebrasi va m ulohazalar hisobi orasidagi

Munosabatlar

Reja:

1. 
   M ulohazalar hisobi formulasining qiymati tushunchasi.
   
2. 
   Mulohazalar hisobi bilan mulohazalar algebrasi orasidagi
   

munosabatlarni aniqlovchi tasdiqlar.

Tayanch iboralar: Mulohazalar hisobi formulasining qiymati. Mulohazalar hisobi formulalar bilan mulohazalar algebrasi formulalari orasidagi munosabatlar. Umumqiymatli formula, Aynan chin formula. Keltirib chiqarish haqidagi teorema.

Mulohazalar hisobi formulalarini xuddi mulohazalar algebrasi formulalari

sifatida qarash mumkin. Вuning uchun mulohazalar hisobi o‘zgaruvchilariga mulohazalar algebrasi o‘zgaruvchilari singari qaraymiz, ya’ni o‘zgamvchilar chin yoki yolg‘on (1 yoki 0) qiymat qabul qiladi deb hisoblaymiz.

˄ , ˅ , → va ⸣ amallarini mulohazalar algebrasidagidek aniqlaymiz.

Mulohazalar hisobining har bir formulasi, o‘zgaruvchilar uning ifodasiga qanday kirishidan qat’i nazar, 1 yoki 0 qiymat qabul qiladi. Uning qiymati mulohazalar algebrasidagi qoidalar bo‘yicha hisoblanadi.

Mulohazalar hisobi formulasining qiymati tushunchasini aniqlaylik.

A - mulohazalar hisobi formulasi, x₁, x₂,…, x_n lar esa A formula ifodasiga kiruvchi o‘zgaruvchilar (x_i≠x_j,) bo‘lsin. α₁, α₂,…, α_n larorqali mos ravishda x₁, x₂,…, x_n o‘zgaruvchilarning qiymatlarini belgilay-

miz, α_j €E2 = {0,1}. α₁, α₂,…, α_n) vektor 2ⁿ ta qiymatlar satriga ega.

0 ‘zgaruvchilaming bitta qiymatlar satri uchun A formulaning qiymati

R α₁ α₂… α_n (A) ni quyidagicha aniqlaymiz:

1. A formulaning eng katta uzunlikdagi qismiy formulasi x_i

Bo’lganda, R α₁ α₂… α_n (x_i) = α_i , bo'ladi.

2. Agar к +1 uzunlikdagi hamma qismiy formulalar aniqlangan

bo‘lsa, u holda A _i ˄ A _j, A _i ˅ A _j A _i → A _j,- amallarning bajarilishi

natijasida olingan к uzunlikdagi qismiy formulalar quyidagi qiymatlarga

ega bo‘ladi:

R α₁ α₂… α_n (A _i ˄ A _j) = R α₁ α₂… α_n (A _i ) ˄ R α₁ α₂… α_n (A _j)

R α₁ α₂… α_n (A _i ˅ A _j) = R α₁ α₂… α_n (A _i ) ˅ R α₁ α₂… α_n (A _j)

R α₁ α₂… α_n (A _i → A _j) = R α₁ α₂… α_n (A _i ) → R α₁ α₂… α_n (A _j)

R α₁ α₂… α_n (⸣A _i)= ⸣R α₁ α₂… α_n (A _i)

Masalan, x ₁ ˅ ⸣x ₄ →⸣(x ₂ ˄⸣ x ₃), formula x ₁, x ₂ ,x ₃ ,x ₄ o‘zgamvchilarning

(0, 1, 1, 0) qiymatlar satrida R ₀₁₁₀(x ₁ ˅ ⸣x ₄ →⸣(x ₂ ˄⸣ x ₃)) = 1 qiymatga ega.

Haqiqatan ham, bu formula quyidagi qismiy formulalarga ega:

x ₁ ˅ ⸣x ₄ ,⸣(x ₂ ˄⸣ x ₃)- birinchi uzunlikdagi qismiy formulalar,

x ₁ , ⸣x ₄ ,x ₂ ˄⸣ x ₃- ikkinchi uzunlikdagi qismiy formulalar,

x ₄ ,x ₂ ,⸣ x ₃- uchinchi uzunlikdagi qismiy formulalar,

x ₃ - to‘rtinchi uzunlikdagi qismiy formula.

Mulohazalar hisobi bilan mulohazalar algebrasi orasidagi

munosabatlarni aniqlovchi tasdiqlar. Endi mulohazalar hisobi bilan

mulohazalar algebrasi orasidagi munosabatlarni aniqlovchi teoremalarga

va lemmalarga to'xtalib o‘tamiz.

1- t e o r e m a . Mulohazalar hisobidagi har bir isbotlanuvchi for­

mula mulohazalar algebrasida aynan chin (tavtalogiya, umumqiymatli)

formula bo ‘ladi.

1- l e m m a . A va В formulalarning ifodasiga kiruvchi hamma

о ‘zgaruvchilar x₁, x₂,…, x_n,x va bu о ‘zgaruvchilarning ixtiyoriy qiy-

matlar satri α₁ α₂… α_n , α bo'lsin. Agar R α₁ α₂… α_n , α (B ) = β bo'lsa, u holda

R α₁ α₂… α_n , α bo ‘ladi.

2 - l e m m a . A - berilgan formula, x - о 'zgaruvchi, В - mulohazalar hisobining istalgan formulasi bo'lsin. Agar A aynan chin formula bo ‘Isa, и holda formula ham aynan chin formula bo ‘ladi.

3 - l e m m a . Agar С va С —>A formulalar aynan chin bo ‘Isa, u holda A ham aynan chin formula bo ‘ladi.

2 - t e o r e m a {keltirib chiqarish haqida). A –mulohazalar hisobining birorformulasi; x₁, x₂,…, x_n — A formula ifodasiga kiruvchi о ‘zgaruvchilar va α₁ α₂… α_n o'zgaruvchilarning ixtiyoriy qiymatlar

satri bo ‘Isin. H orqali chekli formulalar majmuasini belgilaymiz. Agar

bo ‘Isa, u holda H = {} formulalar majmuasi uchun:

1) R α₁ α₂… α_n (A ) = 1 bo ‘Igan holda H \—A ;

2) R α₁ α₂… α_n (A ) = 0 bo ‘Igan holda H \—⸣A bo ‘ladi.

3 - t e o r e m a . Mulohazalar algebrasining har bir aynan chin

formulasi mulohazalar hisobida isbotlanuvchi formula bo ‘ladi.