16. Предикаттар логикасының тілі.

а) Предикаттар логикасының термдері мен формулалары.

в) Ішкі формула.

а) Предикаттар логикасының термдері мен формулалары

Предикаттар логикасының тілі математикалық теорияларда кездесетін өрнектердің мәндерін табу мен сөйлемдердің ақиқаттығын зерттеу құралы болғандықтан, оның алфавитінде осы ұғымдарды жеткізуге арналған символдар жеткілікті болу керек. Атап айтқанда, предикаттар логикасын тілі- тұрақтылар мен айнымалыларды, функциялар мен предикаттар символдарын, кванторларды,логикалық амалдарды және қажетті қосымша символдар – тыныс белгілірін қамтуға тиіс. Предикаттар логикасы осы алфавит негізінде математикалық өрнектер мәнін анықтауға және пәннің әртүрлі нысандары арасындағы байланыстардың орындалу жағдайларын зерттеуге қажетті құралдарға толығымен ие.

Предикаттық, функционалдық және тұрақтылар символдарының қандай да бір жиыны берілсе, оны сигнатура деп атап, σ арқылы белгілейміз.

Енді қандайда бір σ сигнатурасын, осы сигнатураның термі , атомдық формуласы және формуласы ұғымдарын анықтайық.

Анықтама.

Кез – келген тұрақтылар мен айнымалылар символдары терм болады.

Егер ,…., - терм, - m орынды функционалдық символ болса, онда ,сөзі терм болады.

Әрбір терм жоғарыдағы ережелерді ақырлы рет қолдану арқылы құрылады.

Мысалы , v айнымалы символы мен - 1 орынды фуекционалдық символынан ғана тұратын барлық термдер тізімі мынандай:

V,, (),…..,(…),…

Ал - екі орынды,- бір орынды функционалдық символдар үшін ,

()және ()сөздері

терм болмайды, өйткені бұл екі сөздегі функционалдық символдардың орын сандары бұзылып тұр.

Ескерту. Анықтама бойыншатермдер құрйға предикат символдары қолданылмайды. Демек предикат символы қатысқан ешбір сөз терм болмайды.

Термдердің қасиеттерін термнің күрделілігі бойынша индукцияны пайдаланып дәлелдеу.

Жоғарыдағы анықтама термдердің күрделілігі бойынша индукцияға құралған. Сондықтан, термдердің кандай да бір Р қасиетін индукция арқылы дәлелдеу келесі тәртіппен жүреді.

Тұрақтылар үшін Р қасиетінің орындалуын тексереміз

Айнымалылар үшін Р қасиетінің орындалатынын тексереміз

Алдыңғы тексерістер оң нәтиже берсін. Онда егер - кез келген m орынды функционалдық символ, ал,…., Р қасиеті орындалатын термдер болса, онда термі үшінР ұасиетінің орындалатынын тексереміз.

Егер Р қасиеті осы үш шарттың барлығын қанағаттандырса, онда Р қасиеті берілген тілдің барлық термдері үшін орындалады.

Анықтама.

Егер термдер болса, онда сөзі атомдық формула болады.

Егер - термдер болса ,- n орынды прeдикаттық символ болса, ондасөзі атомдық формула болады.

Басқа атомдық формула жоқ .

Мысалы , егер екі орынды предикаттық символ , албір орынды функционалдық символ болса, онда

,,,(), v=v ,=v сөздерінің әрқайсысы атомдық формуланың мысалдары болады.

в) Ішкі формула.

Анықтама. Өзі де формула болатын ішкі сөзді ішкі формула деп атайды .

Мысал. формуласының ішкі формулалары мыналар:

,,,,

17. Бос және байланған айнымалылар.

а) Айнымалыны терммен ауыстыру ережесі.

в) Айнымалыны терммен ауыстыру

Аныктама. Бос айнымалысыз формула сөйлем деп аталады.

ⱯyƎxP²(v,x) және Ǝv(ⱯyⱯx(P²(v,f¹(y)) —>˥Р²(v,x)) Ʌ˥P²(v,v)) формулалары сөйлем мысалдары болады.

Мысалдар.

Р²(v,v), ˥P²(f¹(v),v), Ɐv ˥Р²(v,v),

ⱯxƎz((P²(f¹(x),z)) ɅƎvQ²(v,z))-> ƎyQ²(x,y)

ƎxⱯy Р²(x,f¹(y)) –>P²˥ (v,x)

сөздері формулалар болады. Ал ˥P²(f¹(v),v)-> ƎQ²(x,y) және Ɐvf¹/(P²(v,v)) ссөздері формула болмайды, өйткені бірінші сөздегі квантор кайсы айнымалыға қолданылып тұрғаны көрсетілмеген, ал екінші сөздегі функционалдык символ предикатка колданылып тұр.

Ескерту. Предикаттар логикасының формудасында кездесетін жақшаларды орналастыру тәртібі пікірлер логикасындағы келсімімізге сай келеді.

Формулаларды дұрыс оқи білгенінің маңызы зор. Мысалы, жоғарыдағы ⱯxƎz(P²(f¹(x)_,z) ɅƎvQ²(v_,z))—> ƎvQ²(x,y) формуласының оқылуын келтірейік: "Кез келген х үшін z табылып, егер P²(f¹(x)_yz) және Q²(v,z) болатындай v табылса, онда Q²(x,у) болатындай y табылады".

Егер v айнымалысы φ формуласының ішінде Ǝv немесе Ɐv кванторларының әсер аймағында кездессе, онда v айнымалысын φ формуласында сәйкес Ǝv немесе Ɐv кванторымен байланган айны­малы деп айтамыз, кері жағдайда v айнымалысы бос айнымалы деп аталады. Осы анықтамадан кандай да 6ip формулада айналымның 6ip мезгілде әрi бос, әpi байланған болып кездесуі мүмкін екенін көреміз.

Мысалдар.

ƎvP²(v,v)—»ⱯyP²(v,v) формуласында v айнымалысы әpi байланған, әpi бос айнымалы болып кездесіп тұр.

ƎvⱯy(P²(v,f¹(y)) →˥P²(v,v)) Ʌ˥P²(v,v) формуласында х - бос айнымалы, ал у - байланған айнымалы, ал v айнымалысы әpi бос, әpi байланған күйінде кездеседі.

Бос және байланған айнымалылар формулаларда әртүрлі қызмет аткарады. Мысалы, натурал сандар жиынында анықталған үш орынды S(x,y,z) қатынасы S(x,y,z) = а <=> х+у = z шартымен анықталсын. Онда, S(3,5,3) = ж, S(3,2,5,) = а, S(2,1,0) = ж. Егер осы өрнектерге у айнымалысын енгізіп, ол өрнектердегі у айнымалысын ƎyS(x,y,z) жолымен байласак, ƎyS(3,y,3) = а, ƎyS(3,y,5) = а, ƎyS(2,y,0) = ж болатынын кереміз. Бұл мысалдан колданылған квантор атомдьқ формуланьң акикаттық мәндеріне тікелей әсер ететінін көреміз. Шындығында да, келтірілген ƎyS(x,y,z) формуласы х < z катынасын білдіреді. Осы мысалдан кез келген формула тек онда кездесетін бос айнымалылардың арасындагы байланыстарды ғана білдіретінін байкауға болады. Мысалы ƎyS(v,y,z) формуласының орнына ƎxS(v,x,z) формуласын алсак, онда бұл формулалар 6ip мағынаны білдіреді.

Түйіндеп айтсак, байланған айнымалының формуладағы барлық кездесулерін байлаушы квантордың әсер аймағында берілген формулада кездеспейтін кез келген баска айнымалыга 6ip мезгілде ауыстырсак, формуланьң мағынасы езгермейді. Мысалы, ƎyS(v,y_yz), ƎuS(v,u,z), Ǝ tS(v,t,z) формулалары 6ip ғана v <z катынасын білдіреді.

Ескерту. Байланған айнымалыны ауыстырғанда берілген формуланың кез келген ішкі формуласындағы eш6ip бос айнымалы ауыстырудан кейін квантор аркылы байланбауға тиіс.

Мысалы, v<z катынасын білдіретін ƎyS(v,y,z) формуласын карастырайық. Осы формуладағы у айнымалысын v айнымалысымен ауыстырсак, ƎvS(v,v,z) формуласын аламыз. Ал бұл формула z саны­ның жұп болатындығын білдіреді. Сондыктан, жоғарыдағы ескерту байланған айнымалылардың атын өзгерту кезінде мұқияттылыкты сактау туралы айтады.

Мысал.

Екі орынды f функционалдык символы үшін f(х,у) термі натурал сандарды кебейтуді білдірсін. Яғни f(x_, y) = z <=> х-у = z.

Егер жоғарыда келтірілген ƎyS(v,y,z) формуласындагы v айнымалысын t=ху термімен ауыстырсак, ƎyS(t,y^z) формуласын аламыз. Бұл формула ху + у = z қатынасын білдіреді. Оның v<z қатынасынан мағынасы өзгеше болатыны түсінікті. Демек айнымалыны терммен келтірген жолмен ауыстыруға болмайды. Осындай жағдайларды болдырмау үшін төмендегідей ұғым енгізейік.

Аныктама. Егер v айнымалысының φ формуласындағы еш6ip кездесуі, t термінің кез келген у айнымалысы үшін Ǝy немесе Ɐy кванторларының әсер аймағында болмаса, онда t mepмi φ формуласындағы v айнымалысы ушін бос деп аталады.

Корыта айтсак, формуладағы v айнымалысын кандай да 6ip t термімен ауыстыру үшін t термі φ формуласында v айнымалысы үшін бос болуы керек.

Әдетте жоғарыдағыы ескертуді айналып өту мумкін болмаса, алдымен формуладағы байланған айнымалының атын өзгертіп алып, аталған айнымалыны терммен ауыстырамыз. Мысалы t=xy термін v айнымалысының орнына кою үшін ƎyS(v,_,y,z) формуласында у айнымалысының атын и айнымалысымен ауыстырсак, бастапкы формулаға парапар ƎuS{v_,u,z) формуласын аламыз. Ал бул формулада t термі v айнымалысы үшін бос болады. Яғни, ƎuS{t_,u,z) формулаеы бастапкы ƎuS(v,u,z) формуласынан заңды ауыстыру аркылы алынған болып шығады.

Мысалдар.

Р²(v,у)→ ˥ƎуР²(у_, у) формуласындагы v айнымалысы үшін t =f¹(x) термі бос.

˥P²(f¹(x)_, y)→ ƎyP²(x_, y) формуласындагы х айнымалысы үшін t=у термі бос болмайды.