To‘liqlik haqida teorema

7-MAVZU

TO‘LIQLIK HAQIDA TEOREMA.

REJA:
1.Mulohazalar algebrasi va mulohazalar hisobi o‘rtasidagi munosabatlar.
2.Mulohazalar hisobidagi formulalar bilan mulohazalar algebrasidagi formulalar o‘rtasidagi munosabatlar.
3. Mulohazalar hisobining yechilish muammosi.
4. Mulohazalar hisobining zidsizlik muammosi.
5. Mulohazalar hisobining to‘liqlilik muammosi.
6. Mulohazalar hisobi aksiomalarining erkinlik muammosi.

Tayanch tushunchalar: mulohazalar hisobi formulasining qiymat, mulohazalar hisobidagi formulalar bilan mulohazalar algebrasidagi formulalar o‘rtasidagi munosabatlar, umumqiymatli formula, aynan chin formula, keltirib chiqarish haqidagi teorema. yechilish muammosi, zidsizlik muammosi, to‘liqlilik muammosi, erkinlik muammosi, aksiomatik nazariya, erkin aksioma, erkin aksiomalar sistemasi, tengkuchli formulalar.

Mulohazalar hisobi formulalarini xuddi mulohazalar algebrasi formulalari sifatida qarash mumkin. Buning uchun mulohazalar hisobi o‘zgaruvchilariga mulohazalar algebrasi o‘zgaruvchilari singari qaraymiz, ya’ni o‘zgaruvchilar chin yoki yolg‘on (1 yoki 0) qiymat oladi deb hisoblaymiz.

va  amallarni mulohazalar algebrasidagiday aniqlaymiz.
Mulohazalar hisobining har bir formulasi, o‘zgaruvchilar uning ifodasiga qanday kirishidan qat’iy nazar, 1 yoki 0 qiymat qabul qiladi. Uning qiymati mulohazalar algebrasidagi qoidalar bo‘yicha hisoblanadi.
Mulohazalar hisobi formulasining qiymati tushunchasini aniqlaylik.
-mulohazalar hisobi formulasi, lar esa formula ifodasiga kiruvchi o‘zgaruvchilar bo‘lsin. lar orqali mos ravishda o‘zgaruvchilarning qiymatlarini belgilaymiz, . vektor 2ⁿ ta qiymatlar satriga ega.
O‘zgaruvchilarning bitta qiymatlar satri uchun formulaning qiymati ni quyidagicha aniqlaymiz:
1. formulaning eng katta uzunlikdagi qismiy formulasi bo‘lganda, bo‘ladi.
2.Agar uzunlikdagi hamma qismiy formulalari aniqlangan bo‘lsa, u vaqtda , , , 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_iVA_j)=R₁.._n(A_i)VR₁.._n(A_j),
R₁.._n(A_iA_j)=R₁.._n(A_i)R₁.._n(A_j),
R₁.._n( )= .
Masalan, formula o‘zgaruvchilarning (0,1,1,0) qiymatlar satrida ₀₁₁₀ qiymatga ega.
Haqiqatan ham, bu formula quyidagi qismiy formulalarga ega:
- birinchi uzunlikdagi qismiy formulalar,
- ikkinchi uzunlikdagi qismiy formulalar,
- uchinchi uzunlikdagi qismiy formulalar,
- to‘rtinchi uzunlikdagi qismiy formula.
Bu yerdan ₀₁₁₀ , ₀₁₁₀ = ,
₀₁₁₀ , ₀₁₁₀ ,
₀₁₁₀ = _{0110 0110} ,
₀₁₁₀ = , ₀₁₁₀ ,
₀₁₁₀ =_{0110 0110} ,
₀₁₁₀ = ,
₀₁₁₀ =
= _{0110 0110}
ekanligini topamiz.
Endi mulohazalar hisobi bilan mulohazalar algebrasi o‘rtasidagi munosabatlarni aniqlovchi teoremalarga to‘xtalib o‘taylik.
1-teorema. Mulohazalar hisobidagi har bir isbotlanuvchi formula mulohazalar algebrasida aynan chin (tavtalogiya, umumqiymatli) formula bo‘ladi.
Isbot. Teoremani isbot qilish uchun quyidagi uchta holni ko‘rib chiqishga to‘g‘ri keladi:
1)Mulohazalar hisobidagi har bir aksioma mulohazalar algebrasidagi aynan chin formuladir.
2)Aynan chin formulalarga o‘rniga qo‘yish qoidasini qo‘llash natijasida hosil etilgan formulalar yana aynan chin formulalar bo‘ladi.
3)Aynan chin formulalarga xulosa qoidasini qo‘llash natijasida hosil etilgan formulalar yana aynan chin formulalar bo‘ladi.
1-holning isboti. Mulohazalar hisobi aksiomalarining aynan chinligini isbotlash uchun chinlik jadvalidan foydalanamiz.
a)Ifodasida bitta o‘zgaruvchisi bor aksiomalar:

	IV2	IV3
1	1	1
0	1	1

b)Ifodasida ikkita o‘zgaruvchisi bor aksiomalar:

		I1	II1	II2	III1	III2	IV1
1	1	1	1	1	1	1	1
1	0	1	1	1	1	1	1
0	1	1	1	1	1	1	1
0	0	1	1	1	1	1	1

v)Ifodasida uchta o‘zgaruvchisi bor aksiomalar:

			I2	II3	III3
1	1	1	1	1	1
1	1	0	1	1	1
1	0	1	1	1	1
1	0	0	1	1	1
0	1	1	1	1	1
0	1	0	1	1	1
0	0	1	1	1	1
0	0	0	1	1	1