Navoiy davlat pedagogika instituti fizika matematika fakulteti

MAVZU. PREDIKATLAR ALGEBRASINING AYNAN CHIN VA AYNAN YOLG’ON FORMULALAR

PAning tengkuchliliklarnormal forma va yechilish muammos

Predikatlar algebrasining formulalar

Predikatlar uchun quyida kiritiladigan barcha tushunchalar ihtiyoriy ℳ to`plam bilan bog‘liqBu to`plamni predmetlar to`plami deb ataymiz. Lotin alifbosining oxirrog‘idagi x, u, z, u, v, x<sub>1</sub>, x<sub>2</sub> , . . . - lar o‘zgaruvchi predmetlarni, boshidagi harflar a, b, c, a<sub>1</sub>, a<sub>2</sub> , . . . - lar ℳ to`plamning ani= elementlarini bildirad Lotin alifbosining bosh harflari A , V , S , . . . - orqali o‘zgaruvchi yoki o‘zgarmas mulohazalar belgilanad

F ( x ), G ( x, y ), P ( x₁, x₂, . . . , x_n ), . . . – ifodalar orqali predikatlarni belgilaymiz.

Agar a, b – doimiy predmetlar, G – ikki o‘zgaruvchili predikat bo‘lsa, G ( a, b ) mulohaza bo‘lishi ravshan.

A , V , S , . . . va F ( a ), G ( a, b ), . . . ko‘rinishdagi mulohazalar elementar mulohazalar deyilad

Endi predikatlar algebrasining formulasi tushunchasini kiritamiz.

Predikatlar algebrasida quyidagi simvollar ishlatiladi:

1. 
   x₀, x₁, . . . , x_n – predmet o‘zgaruvchilar.
   
2. 
   , , . . . , , . . . – predikatlar ( - n – o‘rinli predikat).
   
3. 
   ù , Ù , Ú , Þ , Û - mantiq amallar
   
4. 
   " , $ - kvantorlar.
   
5. 
   ( , ) - qavslar.
   

2.1 - ta’rif. 1. Har qanday elementar mulohaza – formuladir.

2. Agar - n_i – o‘rinli predikat, , . . . , - o‘zgaruvchi predmetlar yoki doimiy predmetlar bo‘lsin. U holda - formuladir.

YUQoridagi 1,2 – punktlarda aniqangan formulalar elementar formulalar deyilad

3. Predikatlar algebrasining birida bog‘liq bo‘lgan predmet o‘zgaruvchi ikkinchisida erkin bo‘lmaydigan Á va  formulalar berilgan bo‘lsin. U holda Á Ù Â, Á Ú Â, Á Þ Â,

Á Û Â ,ù Á ifodalar ham predikatlar algebrasining formulalaridir.

4. Predikatlar algebrasining x erkin o‘zgaruvchi qatnashgan A ( x ) formulasi berilgan bo‘lsin, u holda

"x A ( x ), $ x A ( x ) ifodalar ham predikatlar algebrasining formulasidir.

5. 
   Predikatlar algebrasining 1 – 4 punktlarda sanab chiqilgan formulalardan boshqa formulalari yo‘q.
   

2.2 - misol. , " x

$ x , " x - ifodalar predikatlar algebrasining formulalaridir.

Predikat simvolidagi indekslarni kerak bo‘lmagan hollarda tashlab yozishni kelishib olamiz. Masalan, o`rniga R ( x, y, z ) yozish mumkin.

2.3 - misol . " x Q ( x, u ) Ú R ( x ) ifoda formula bo‘lmaydi, chunki, 2.1 - ta’rifdagi 3 - punkt shartlari bajarilmagan.

2.4 - misol . N₀ = { 0, 1, 2, . . . } to`plam va N₀´N₀ da aniqangan P( x, y ) ⇌ “ x < y ” , Q( x, y ) ⇌ “ x² + y² = 5 “ predikatlar berilgan bo‘lsin. $x ( R( x, u ) Ù Q( x, u )) – predikatning qiymatlarini topaylik. Bu formula bir o‘zgaruvchili predikat bo‘lib, uning qiymatfaqat u ga bog‘liqMasalan, agar

u = 0 bo‘lsa, $x ((« x < u ») Ù (« x² + 0² = 5 »)) = 0 ;

u = 1 bo‘lsa, $x ((« x < 1 ») Ù (« x² + 1² = 5 »)) = 0;

u = 2 bo‘lsa, $x ((« x < 2 ») Ù (« x² + 2² = 5 »)) = 1 va h.k[D2].

( bu erda * «⇋» belgi « aynan shu » ma’nosini bildiradi ).