1. Predikatlar hisobida yechilish muammosi. Yechilish muammosi

6- 

m i s o l .

 

))

(

)

(

(

))

(

)

(

(

y

B

x

А

x

y

y

B

x

А

y

x















 

teng 

kuchlilik 

o‘rinli 

ekanligini ko‘rsatamiz. 

)

(

)

(

))

(

)

(

(

))

(

)

(

(

y

yB

x

xА

y

yB

x

А

x

y

B

x

А

y

x























, 

)

(

)

(

))

(

)

(

(

))

(

)

(

(

y

yB

x

xА

y

B

x

xА

y

y

B

x

А

x

y























. 

Demak, keltirilgan teng kuchlilik o‘rinlidir.

 

14.

 

Bajaruvchi va umumqiymatli formulalar, ularning xossalari. 

2- t a ’ r i f .

 

Agar 

A

 formula ifodasiga kiruvchi va 

M

 sohaga oid o‘zgaruvchilarning shunday 

qiymatlari  mavjud  bo‘lib,  bu  qiymatlarda 

A

  formula  chin  qiymat  qabul  qilsa,  u  holda  predikatlar 

mantiqining 

A

 formulasi 

M

 sohada

 

bajariluvchi formula

 deb ataladi. 

3- t a ’ r i f .

 

Agar shunday soha mavjud bo‘lib, unda 

A

 formula bajariladigan bo‘lsa, u holda 

A

 

bajariluvchi formula

 deb ataladi. 

Demak,  agar  biror  formula  bajariluvchi  bo‘lsa,  bu  hali  uning  istalgan  sohada 

bajariluvchanligini bildirmaydi. 

4-  t a ’ r i f .

 

Agar 

A

ning  ifodasiga  kiruvchi  va 

M

  sohaga  oid  hamma  o‘zgaruvchilarning 

qiymatlarida 

A

 formula chin qiymat qabul qilsa, u holda 

A

 formula 

M

 sohada 

aynan chin formula

 

deb ataladi. 

5- t a ’ r i f .

 

Agar 

A

 formula har qanday sohada aynan chin bo‘lsa, u holda 

A

 

umumqiymatli

 

formula

 deb ataladi.

 

6- t a ’ r i f .

 

Agar 

A

 formula ifodasiga kiruvchi va 

M

 sohaga oid hamma o‘zgaruvchilarning 

qiymatlarida 

A

  formula  yolg‘on  qiymat  qabul  qilsa,  u  holda 

A

  formula 

M

  sohada 

aynan  yolg‘on 

formula 

deb ataladi. 

Keltirilgan ta’riflardan ushbu tasdiqlar kelib chiqadi. 

---

1.  Agar 

A

  umumqiymatli  formula  bo‘lsa,  u  holda  u  har  qanday  sohada  ham  bajariluvchi 

formula bo‘ladi. 

2.  Agar 

A

  formula 

M

  sohada  aynan  chin  formula  bo‘lsa,  u  holda  u  shu  sohada  bajariluvchi 

formula bo‘ladi. 

3.  Agar 

M

  sohada 

A

 

aynan  yolg‘on  formula  bo‘lsa,  u  holda  u  bu  sohada  bajarilmaydigan 

formula bo‘ladi. 

4.  Agar 

A

  bajarilmaydigan  formula  bo‘lsa,  u  holda  u  har  qanday  sohada  ham  aynan  yolg‘on 

formula bo‘ladi. 

Demak, predikatlar mantiqi formulalarini ikki sinfga ajratish mumkin: 

bajariluvchi

 sinflar va 

bajarilmas

 (bajarilmaydigan) sinflar formulalari. 

7- t a ’ r i f .

 

Umumqiymatli formula 

mantiq qonuni

 deb ataladi. 

3-  m i s o l .

 

)

,

(

y

x

yP

x





  formula  bajariluvchidir.  Haqiqatan  ham,  agar 

)

,

(

y

x

P

:  «

y

x



» 

predikat 

E

E

M





  sohada  aniqlangan  (bu  yerda 

,...}

...,

,

2

,

1

,

0

{

n

E



)  bo‘lsa,  u  holda 

)

,

(

y

x

yP

x





 

formula 

M

 sohada aynan chin formula bo‘ladi, demak, bu sohada u bajariluvchi formuladir. Ammo, 

agar 

}

...,

,

2

,

1

,

0

{

1

k

E



 uchun «

y

x



» predikat chekli 

1

1

1

E

E

M





 sohada aniqlangan bo‘lsa, u holda 

)

,

(

y

x

yP

x





 formula 

1

M

 sohada aynan yolg‘on formula bo‘ladi va, demak, 

1

M

 sohada 

)

,

(

y

x

yP

x





 

formula bajariluvchi emas. Ravshanki, 

)

,

(

y

x

yP

x





 umumqiymatli formula bo‘lmaydi. ■ 

4-  m i s o l .

 

]

)

(

)

(

[

y

P

x

P

y

x







 formula bajariluvchidir. Haqiqatan ham, agar 

)

(

x

P

: «

x

 – juft 

son» predikat 

,...}

...,

,

2

,

1

,

0

{

n

E



 uchun 

E

E

M





 sohada aniqlangan bo‘lsa, u holda bu formula 

M

 

sohada aynan chin bo‘ladi, demak, u 

M

 sohada bajariluvchi formuladir. Ammo, agar 

)

(

x

P

: «

x

 – juft 

son»  predikat 

...}

,

8

,

6

,

4

,

2

{

1



E

  uchun 

1

1

1

E

E

M





  sohada  aniqlangan  bo‘lsa,  u  holda 

]

)

(

)

(

[

y

P

x

P

y

x







 formula 

1

M

 sohada aynan yolg‘on formula bo‘ladi, demak, bu sohada u bajarilmas 

formuladir. ■ 

5-  m i s o l . 

]

)

(

)

(

[

x

P

x

P

x





  formula  ixtiyoriy 

M

  sohada  aynan  chin  bo‘ladi.  Demak,  u 

umumqiymatli formula, ya’ni bu formula mantiqiy qonundir. ■ 

6- m i s o l . 

]

)

(

)

(

[

x

P

x

P

x





 formula ixtiyoriy 

M

 sohada aynan yolg‘on va shuning uchun ham 

u bajarilmas formuladir.

 

15.

 

Umumqiymatli va bajaruvchi formulalar haqida teoremalar. 

T e o r e m a   1 .

 

A

 umumqiymatli formula bo‘lishi uchun uning inkori  A  bajariluvchi formula 

bo‘lmasligi zarur va yetarlidir.

 

I s b o t i .

  Z a r u r l i g i .  

A

 

umumqiymatli  formula  bo‘lsin.  U  holda,  ravshanki, 

A

  istalgan 

sohada aynan yolg‘on formula bo‘ladi va shuning uchun ham u bajarilmas formuladir. 

Y e t a r l i l i g i .  

A

  istalgan  sohada  bajariluvchi  formula  bo‘lmasin.  U  holda  bajarilmas 

formulaning ta’rifiga asosan 

A

 istalgan sohada aynan yolg‘on formuladir. Demak, 

A

 istalgan sohada 

aynan chin formula bo‘ladi va u umumqiymatlidir. ■ 

Te o r e m a   2 .

 

A

  bajariluvchi  formula  bo‘lishi  uchun  A ning  umumqiymatli  formula 

bo‘lmasligi zarur va yetarlidir. 

I s b o t i .

  Z a r u r l i g i .  

A

  bajariluvchi  formula  bo‘lsin.  U  holda  shunday 

M

  soha  va 

A

 

formula tarkibiga kiruvchi o‘zgaruvchilarning shunday qiymatlar majmui (satri) mavjudki, 

A

 formula 

bu qiymatlar satrida chin qiymat qabul qiladi.  Ravshanki, o‘zgaruvchilarning bu qiymatlar satrida 

A

 

formula yolg‘on qiymat qabul qiladi va, demak, 

A

 umumqiymatli formula bo‘la olmaydi. 

Y e t a r l i l i g i .  

A

 umumqiymatli formula bo‘lmasin. U holda shunday 

M

 soha va 

A

 formula 

tarkibiga  kiruvchi  o‘zgaruvchilarning  shunday  qiymatlar  satri  mavjudki, 

A  

formula  bu  qiymatlar 

satrida  yolg‘on  qiymat  qabul  qiladi.  Bu  qiymatlar  satrida 

A

  formula  chin  qiymat  qabul  qilganligi 

uchun u bajariluvchi formula bo‘ladi. ■ 

---