Yusupov Javohir Avazxon o’g’li ning «diskret tuzilmalar»

Predikatlar mantiqi formulasining t a ’ r i f i .
1. Har qanday o'zgaruvchi yoki o ‘zgannas mulohaza (elementar) formula bo ‘ladi.
2. Agar F ( ) n joyli o'zgaruvchi predikat yoki o'zgarmas nta predikat va x x, x 2,...,xn - predmet о 'zgaruvchilar yoki predmet konstantalar bo'lsa, и holda F(xt, x ,,...,x n) formula bo'ladi. Bunday formulani elementar formula deb ataymiz. Bu formulada predmet о ‘zgaruvchilar erkindir, ya ’ni kvantorlar bilan bog ‘langan emas.
3. Agar A va В shunday formulalarki, birorta predmet о ‘zgaruvchi birida erkin va ikkinchisida bog'langan o'zgaruvchi bo'lmasa, и holda A v В , А л В , A —> В ham formula bo ‘ladi. Bu formulalarda dastlabki formidalarda erkin b o ‘Igan о ‘zgaruvchilar erkin, bog'langan bo‘Igan о 'zgaruvchilar esa bog ‘langan о ‘zgaruvchilar^ bo ‘ladi.
4. Agar A_formula bo'lsa, и holda A ham formula bo'ladi. A formuladan A formulaga о ‘tishda о ‘zgaruvchilarning xarakteri о ‘zgarmaydi.
5. Agar A (x) formula bo'lsa va uning ifodasiga x predmet о ‘zgaruvchi erkin holda kirsa, и holda VxA(x) va 3xA(x) mulohazalar formula bo'ladi va x predmet o'zgaruvchi ularga bog'langan holda kiradi.
6. 1-5- bandlarda formulalar deb atalgan mulohazalardan farq qiluvchi har qanday mulohaza formula bo ‘Imaydi.
1-misol. Agar P(x) va Q(x,y) - bir joyli va ikki joyli predikatlar, q, r - o'zgaruvchi mulohazalar bo'lsa, u holda quyidagi mulohazalar formulalar bo'ladi:
q , P(x ), P(x) a Q(x° , y ), VxP(x) -> 3xQ(x, y ) , (Q (x,y )v q )^r.
\/xQ(x,y) —» P(x) mulohaza formula bo'la olmaydi, chunki predikatlar mantiqi formulasi ta’rifning 3- bandidagi shart buzilgan: x predmet o'zgaruvchi ^fxQ(x,y) formulaga bog'langan holda, P(x)ga esa erkin holda kirgan. ■ Predikatlar mantiqi formulasining ta’rifidan ko'rinib turibdiki, mulohazalar algebrasining har qanday formulasi predikatlar mantiqining ham formulasi bo'ladi.
2- misol. Quyidagi ifodalaming qaysilari predikatlar mantiqining formulasi bo'lishi va har bir formuladagi bog'langan va erkin o'zgaruvchilarni aniqlash talab etilgan bo'lsin:
1) 3x\/z(P{x,y) P(y,z))\
2) {p ^ > q ) / \ ( r v p ) -,
3) P(x) л \/x Q ( x );
4) V x(P(x) —» Q(x)) <-> (3xP(x) —> VxR(x, y ) ) ;
5) (P(x) <-> Q(x)) v 3 y ( \/y R ( y ) ) ;
6) 3xVz(P(x,y) -> P{y,z)) .
Predikatlar mantiqi formulasining ta’rifiga ko‘ra 1), 2), 4) va 6) ifodalar formulalardir.
3) va 5) ifodalar formula emas. Haqiqatdan ham, 3) ifodada л amali P(x) va \/xQ(x) formulalarga nisbatan qo'llanilgan bo‘lib, 'P(x) da x predmet o'zgaruvchi erkin va VxQ(x) da esa umumiylik kvantori bilan bog‘langan. Bu holat formula ta’rifining 3- bandiga ziddir. Shuning uchun 3) ifoda formula bo‘la olmaydi. 5) ifodada esa, 3у mavjudlik kvantori bilan Vy umumiylik kvantori orasida ziddiyat bor.
1) formulada у erkin, x va z o'zgaruvchilar esa bog'langan o'zgaruvchilardir. 2) formulada predmet o'zgaruvchilar yo‘q. 4) formulada x bog'langan o'zgaruvchi, у esa erkin o'zgaruvchidir.