Fan nomi: Diskret tuzilmalar Guruh: 912-21 Bajardi

Mulohazalar hisobi formulasi tushunchalari


1-teorema. Mulohazalar hisobidagi har bir isbotlanuvchi formula mulohazalar algebrasida aynan chin (tavtalogiya, umumqiymatli) formula bo’ladi.
Isboti. 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 qilingan formulalar ham aynan chin formulalar bo’ladi;
   

aynan chin formulalarga xulosa qoidasini qo’llash natijasida hosil

3. 
   qilingan formulalar ham aynan chin formulalar bo’ladi.
   

1. 
   Holning isboti. Mulohazalar hisobi aksiomalarining aynan chinligini
   

isbotlash uchun chinlik jadvalidan foydalanamiz:

1. 
   ifodasida bitta o’zgaruvchisi bor aksiomalar –
   

x	IV2	IV3
1	1	1
0	1	1

b) ifodasida ikkita o’zgaruvchisi bor aksiomalar –

X	y	I­1	I­I1	I­I2	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

d) ifodasida uchta o’zgaruvchisi bor aksiomalar –

X	y	z	I2	I­I3	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

1) hol isbot bo’ldi.

2. 
   holning isboti. Avval quyidagi lemmalarni kiritamiz.
   

1-lemma. A va B formulalarning ifodasiga kiruvchi hamma o’zgaruvchilar va bu o’zgaruvchilarning ixtiyoriy qiymatlar satri bo’lsin. Agar bo’ladi.
. 2-lemma. A – berilgan formula, x – o’zgaruvchi, B – mulohazalar hisobining istalgan formulasi bo’lsin. Agar A aynan chin formula bo’lsa, u holda formula ham aynan chin formula bo’ladi.
Bu lemmalar 2) holni isbot qiladi.

3. 
   hol uchun isboti quyidagi lemmaga tayanadi.
   

3-lemma. Agar C va formulalar aynan chin bo’lsa, u holda A ham aynan chin formula bo’ladi.
3-lemmaning isboti. lar C va A formulalar ifodasiga kiruvchi o’zgaruvchilar bo’lsin. A –aynan chin formula emas deb faraz qilamiz. U holda o’zgaruvchilarning shunday qiymatlar satr mavjud bo’ladiki, bo’ladi. Bu yerdan

ekanligi kelib chiqadi. Bu natija formulaning aynan chin ekanligiga ziddir. Bu qarama-qarshilik, A aynan chin formula ekanligini isbotlaydi. 3-lemma isbot bo’ldi.
2-teorema (keltirib chiqarish haqida). A–mulohazalar hisobining biror formulasi; formula ifodasiga kiruvchi o’zgaruvchilar va o’zgaruvchilarning ixtiyoriy qiymatlar satri bo’lsin. H orqali chekli formulalar majmuasini belgilaymiz. Agar

bo’lsa, u holda formulalar majmuasi uchun:

1. 
   bo’lgan holda
   
2. 
   bo’lgan holda bo’ladi.
   

3-teorema. Mulohazalar algebrasining har bir aynan chin formulasi mulohazalar hisobida isbotlanuvchi formula bo’ladi.
Formulalar majmuasidan formulani keltirib chiqarish qoidasi.


Ta’rif. 1) Har qanday Aformulalar majmuasi H dan keltirib
chiqariladigan formuladir.
2) Har qanday isbotlanuvchi formula H dan keltirib chiqariladi.
3) C va C B lar H formulalar majmuasidan keltirib chiqarilgan
formulalar bo’lsa, u holda B formula ham H dan keltirib chiqariladi.
Biror B formula H formulalar majmuasidan keltirib chiqariladigan bo’lsa, uni simvolik ravishda H|-B shaklda yozamiz.
Agar H bo’sh to’plam yoki elementlari faqat isbotlanuvchi formulalardan iborat bo’lsa, u vaqtda H dan keltirib chiqariladigan formulalar sinfi isbotlanuvchi formulalar sinfi bilan mos keladi. Agar formulalar majmuasi H ning hech bo’lmaganda bitta elementi isbotlanmaydigan formuladan iborat bo’lsa, u holda H dan keltirib chiqariladigan formulalar sinfi isbotlanuvchi formulalar sinfiga
nisbatan kengroq bo’ladi.


Keltirib chiqarish (isbotlash) tushunchasi

Ta’rif. Agar B1 ,B2 ,...,Bn chekli formulalar ketma-ketligining har qanday hadi quyidagi:

1)H formulalar majmuasining birorta formulasi;
2) isbotlanuvchi formula;
3) B1 ,B2 ,...,B2ketma-ketlikning istalgan ikkita oldinma-keyin keladigan elementlaridan xulosa qoidasiga asosan hosil qilinadi degan uch shartning birortasini qanoatlantirsa, u holda bu ketma-ketlik H chekli formulalar majmuasidan keltirib chiqarilgan deb aytiladi.
H {A,B} dan quyidagi formulalar chekli ketma-ketligi keltirilib chiqariladi:
A, B, (AA)((AB)(AAB)), B(AB),
A, B, AA, (AB)(AAB)), AB, AAB, A B.
Agar murakkab xulosa qoidasidan foydalansak, u vaqtda (isbot) keltirib chiqarish formulalari quyidagicha bo’ladi:
A, B, (AA)((AB)(AAB)),
B(AB), AA, AB, A B.
Formulani keltirib chiqarish va formulalar majmuasidan keltirib chiqarish ta’riflariga asosan keltirib chiqarishning quyidagi xossalari hosil bo’ladi:
-H formulalar majmuasidan keltirib chiqarilgan chekli ketma-ket-likning boshlang’ich qismi ham H dan keltirib chiqariladigan bo’ladi;
-agar H dan keltirib chiqarilgan ketma-ketlikning ikkita qo’shni hadlari (elementlari) orasiga H dan keltirib chiqarilgan qandaydir boshqa ketma-ketlik qo’yilsa, u vaqtda hosil etilgan yangi formula-lar ketma-ketligi ham H dan keltirib chiqarilishi mumkin.
-H formulalar majmuasidan keltirib chiqarilgan formulalar ketma-ketligining har qanday hadi H dan keltirib chiqariladigan formuladir.
-agar H W bo’lsa, u vaqtda H dan keltirib chiqarilgan har qanday formula W ning ham formulasi bo’ladi.
- B formula H dan keltirib chiqariladigan formula bo’lishi uchun H dan keltirib chiqarilgan ixtiyoriy formulalar ketma-ketligida bu formulaning mavjud bo’lishi yetarli va zarurdir.