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

а)Предикаттар логикасындағы терм ұғымы

в) Предикаттар логикасындағы формула ұғымы.

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

Осы максатта, X = VUCUPrUFnULogUQuUD алфавитін қарас- тырайық.

Мұндағы

V = {х, у, z, v, и,...} - айнымалылар символдары жиыны;

С = {с₀, c_v...} - тұрақтылар жиыны;

Рг ={P_iⁿⁱ|n_iϵN}- предикаттық символдар жиыны; жоғарғы индекс

предикаттық символдың неше орындық екендігін көрсетеді.

Fn ={f_j^mj|m_jϵN}- функционалдық символдар жиыны; жоғарғы

индекс функционалдық символдың неше орынды екендігін керсетеді.

Log = {˄немесе & (конъюнкция), ˅(дизъюнкция), → (импликация), ⌐(терістеу),↔( эквиваленттік)} – логикалық амалдар жиыны;

Qu = {(жалпылау),ⱻ(табылу)} - кванторлар жиыны;

D = {сол жақша, оң жақша, үтip} - қосымша символдар жиыны;

алфавитінің символдарының кез келген шектелген тіз6eгi предикаттар логикасының cөзі деп аталады. Ішкі сөз ұғымын, символды немесе сөзді сезбен ауыстыру уғымдарын біз анықтағанбыз.

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

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

Анықтама.

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

Егер t₁,.. ,t_m - терм,f^m - т орынды функционалдық символ болса, онда f^m(t₁ ,...,t_m) сөзі терм болады.

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

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

υ,f¹(υ), f¹ (f¹(υ)),…, f¹ (…(f¹(υ)…),…

Ал g² - eкi орынды, f¹- 6ip орынды функционалдық символдар үшін, g² (f¹(х,у)) және f¹(g²(υ)) сөздері термдер болмайды. Өйткені бұл екі сөздегі функционалдық символдардың орын сандары бұзылып тұр.

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

а)Предикаттар логикасындағы терм ұғымы

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

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

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

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

Алдыңғы тексерістен оң нәтиже берсін. Онда егер f^m - кез келген т орынды функционалдық символ, ал t_1,..._,t_m — P қасиеті орындала­тынын термдер болса, онда f^m(t_1,..._,t_m) термі үшін Р касиетінің орындалатынын тексереміз.

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

Анықтама.

Егер t₁,t₂ термдер болса, онда t₁= t₂ cөзi атомдық формула болады.

Егер t_1,... ,t_n-термдер, Р^п-п орынды предикаттық символ болса, онда Pⁿ(t₁, ... ,t_n) cөзi атомдық формула болады.

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

Мысалы, егер Р² eкi орынды предикаттық символ, ал f¹ 6ip орынды функционалдық символ болса, онда

P²(v,v), P²( v, f¹ (v)) ,P²(f¹(v), f¹(f¹(v))), v = v, f¹(v)=v сөздерінің

әрқайсысы атомдық формуланың мысалдары болады.

Аныктама. Берілген σ сигнатурасының формуласы келесі тәртіппен анықталады.

Әp6ip атомдық формула формула болады.

Егер φ және ψ формулалар болса, онда (¬φ), (φ˄ψ), (φ˅ψ) және (φ→ψ)сөздері формула болады.

Егер φ - формула, ал v - айнымалы символы болса, онда Ʉυφ және ⱻυφ сөздері формула болады. Мұндағы φ формуласы сәйкес Ʉv жэне ⱻυ кванторларының әсер аймағы деп аталады.

Кез келген σ сигнатурасының формуласы жоғарыдағы ережелерді ақырлы рет қолдану арқылы құрылады.

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

yⱻxP²(v, x) және ⱻv(yx(P²(υ,f¹(y))→¬Р²(υ, x))˄¬P²(v,y)) формулалары сөйлем мысалдары болады.

Мысалдар.

Р²(υ,υ), ¬P²(f¹(υ), υ), υ ¬Р²(υ,υ),

xⱻz((P²(f¹(x),z))˄ⱻυQ² (υ, z))→ⱻyQ²(x_,y)

ⱻxɄy Р²(x, f¹(у))→¬P²(v, x)

сөздері формулалар болады. Ал ¬P²(f¹(υ),υ)→ⱻQ²(x_,y) және υ f¹(P²(υ,υ)) сездері формула болмайды, өйткені 6ipiнші сөздегі квантор қайсы айнымалыға қолданылып тұрғаны көрсетілмеген, ал eкiншi сездегі функционалдық символ предикатқа қолданылып тұр.

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

Формулаларды дұрыс оқи білгеннің маңызы зор. Мысалы, жоғарыдағы xⱻz(P²(f¹(x)_,z)˄ⱻυQ²(v_,z))→ⱻy Q²(x,y) формуласының оқылуын келтірейік: "Кез келген х ушін z табылып, егер P²(f¹{x)_yz) және Q²(v_,z) болатындай υ табылса, онда Q²(х,у) болатындай у табылады".

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

Мысалдар.

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

ⱻvy(P²(v,f¹(y))→¬P²(υ,х))˄¬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 қатынасын білдіреді. Осы мысалдан кез келген формула тек онда кездесетін бос айнымалылардың арасындағы байланыстарды ғана 6ілдipemiнін байқауға болады. Мысалы ⱻ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 қатынасын білдіреді. Оның vzқатынасынан мағынасы өзгеше болатыны түсінікті. Демек айнымалыны терммен келтірілген жолмен ауыстыруға болмайды. Осындай жағдайларды болдырмау yшін төмендегідей ұғым енгізейік.

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

в) Предикаттар логикасындағы формула ұғымы.

Бірінші ретті тілді интерпретациялау.

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

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

Мысалдар.

Р²(υ,у)→¬ⱻуР²(у,у) формуласындағы v айнымалысы ушін t =f¹(x) термі бос.

¬P²(f¹(x),y)→ⱻyP²(x,y) формуласындағы х айнымалысы yшін t=у термі бос болмайды.

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

Мысал.

¬ Р ²(f¹(х),у)→¬υP²(x,(y))=φ формуласының iшкі формулалары мыналар:

P²(f¹(x),y), P ²(х, f¹(у)), vP²(x,f¹(y)), ¬P²(f¹(x),y), ¬υP²(x,f¹(y)), φ.

М жиыны берілсін. Егер σ сигнатурасының әp6ip п орынды предикаттьқ символына М жиынының п орынды катынасы, әp6ip т орынды функционалдық символына М жиынындағы т орынды алгебралық амал, әp6ip тұрақты символына М жиынының белгілі 6ip элементі сәйкес қойылса, онда М жиынында σ сигнатурасының алгебралық жүйесінің (структурасыныц) құрылымы анықталды деп айтамыз жэне оны =<М,σ> арқылы белгілейміз. Жоғарыдағы сәйкестік σ сигнатурасының М жиынындағыинтерпретациясы деп аталады. Сонымен алгебралық жүйенің табиғаты сигнатурамен, берілген жиынмен және интерпретациямен толық анықталады. = <М,σ> алгебралық жуйесіндегі М жиыны негізгі жиын (универсум) деп аталады.

Ескерту: Біз сигнатураны алгебралық жүйесі және сигнатураның структурасы атауларын 6ip бірінің орнына еркін қолдана береміз.

4.Бірінші ретті тілді интерпретациялау.

а) Берілген тілдің структурасы.

в) Берілген тілдің структурасының мысалдары.

а) Бос емес А₁...,А_п жиындары берілсін . Жиында анықталған катынас уғымын еске түсірейік. А₁*.. .*А_п={(а₁.. ,а_п)|а₁€A₁,.. .,a_n€A_n }- реттелген n-діктер (эндіктер) жиынын А₁,...₉А_п жиындарының декарттық көбейтіндісі деп айтқанбыз. Егер A ₁ =... =А_п=А болса, онда А₁*.. .*А_п жиынын А жиынының n-ші pemmi (энші pemmi) дәрежесі деп айтады. Белгілеуі : А^п

Аныктама. А^п жиынының кез келген iшкі жиыны А жиынында анықталған п орынды қатынас деп аталады.

Аныктама. Кез келген α: А^m —>А бейнелеуін А жиынында анықталған m орынды алгебралық амал деп айтамыз.

Төмендегі кестеде белілі арифметикалық амалдардың нeriзгi сандық жиындарда алгебралық амал болу болмауы туралы мәліметтер келтірілген.

Амалдар	Сәйкес жиында алгебралық бола ма? N, Z, Q, Q\{0}, R, С
косу көбейту алу Kepi элемент табу	иә, иә, иә, иә, иә, иә иә,иә,иә,иә, иә, иә ЖОК, Иә, Иә, ЖОК, иә, иэ жок, ЖОК, ЖОК, Иә, ЖОК, ЖОК

Жаттығу. Жогарыдагы кестені түсіндіріңіз.

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

Аныктама. R^п аркылы М жиынында анықталған n орынды катынасты белгілейік.

Егер Pⁿ: Мⁿ—>{а,ж} бейнелеуі берілген а ₁,...,а_n€М элементтері ушін Р^п(а₁...,а_п)=а <=> (a₁...,a_n)€RⁿcM шартымен анықталса, Р^п бейнелеуін Rⁿ қатынысына сәйкес М жиынындағы п орынды предикат деп айтамыз.

Біз предикаттық , функционалдық және константалық символдардан тұратын кандай да 6ip жиынды сигнатура деп айтқанбыз. Сигнатураны әдетте σ немесе ^ әріптерімен ( қосындының белгісі) мен белгілейміз.

М≠Ø жиыны берілсін . Егер σ сигнатурасының әp6ip п орынды предикаттық символына М жиынының п орынды катынасы, әp6ip т орынды функционалдық символына М жиынындағы т орынды алгебралық амал, әp6ip турақты символына М жиынының белгілі 6ip элементі сәйкес койылса, онда М жиынында σ сигнатурасының алгебралық жуйесінің (структурасының) курылымы анықталды деп айтамыз және оны M=<М, σ> аркылы белгілейміз. Жоғарыдағы сәйкестік σ сигнатурасының М жиынындагы интерпретациясы деп аталады. Сонымен алгебралық жуйенің табиғаты сигнатурамен, берілген жиынмен және интерпретациямен толық анықталады. M=<М, σ> алгебралық жуйесіндегі М жиыны негізгі жиын (универсум ) деп аталады.

Ескерту: Біз сигнатураны алгебралық жуйесі және сигнатураның структурасы атауларын 6ip бірінің орнына еркін колдана береміз.

в) Мысал. σ = <R²,f², с> сигнатурасы жэне Z = {0, ±1, ±2,...} бүтін сандар жиыны берілсін. Екі турлі интерпретация аркылы Z₁ = <Z, σ >, Z₂= <Z, σ > алгебралык жуйелерін аныктайық.

R² предикаттык символына сәйкес Z жиынында аныкталган eкi орынды Р₁ катынасын

Р₁{m,n) = а<=> m<n

шартымен ал f² функционалдык символына сәйкес алгебралық амалды

g₁(x,y) = Z <=>x+y=z

шартымен, турақты символы с—> 0 арқылы анықталған интерпре­тация бойынша

Z1= <Z, <, +, 0> алгебралық жуйесі анықталса, жогарыдагы тәртіпке ұксас, келесі

Р₂(m,n) = а <=> m < n, g₂(x,y) = z <=> х*у = z, с—>1

шарттары нeгiзiндeгi интерпретация аркылы Z₂= <Z, <, *, 1> алгебралық жуйесін анықтауға болады.

Бул мысалдан берілген сигнатураның алгебралық жуйелері өте көп және әp6ip интерпретацияға сәйкес жаңа алгебралық жүйе алуға болатынын көpeмiз.

5. Структурадағы формуланың орындалуы туралы негізгі анықтама.

а) Берілген тізбектегі термнің мәні.

в) Берілген тізбектегі формуланың орындалуы. Мысалдар.

Бос емес жиындары берілсін. Жиында анықталған қатынас ұғымын еске тусирейік. реттелген n-діктер жиынынжиындарының декарттық көбейтіндісі деп айтқанбыз. Егерболса, ондажиынын А жиынының n-ші ретті дәрежесі деп атайды. Белгілеуі

Анықтама. жиынының кез келген ішкі жиынын А жиынында анықталған n орынды қатынас деп атайды.

Анықтама. Кез келген бейнелеуін А жиынында анықталған m орынды алгебралық амал деп атаймыз.

Анықтама. арқылы М жиынында анықталған n орынды қатынасты белгілейік.

Егер бейнелеуі берілгенэлементтері үшіншартымен анықталса,қатынасына сәйкес М жиынындағы n орынды предикат дейміз.

М≠ жиыны берілсін. Егер сигнатурасының әрбір n орынды предикаттық символына М жиынының n орынды қатынасы, әрбір m орынды орынды функционалдық символына М жиынындағы m орынды алгебралық амал, әрбір тұрақты символына М жиының белгілі бір элементі сәйкес койылса, онда М жиынындасигнатурасыныңалгебралық жүйесінің (структурасының) құрылымы деп атаймыз және оны арқылы белгілейміз.

Термнің мәні.

Енді алгебралық жүйеде берілген тізбектегі термнәі мәні және формуланың орындалу ұғымын анықтайық.

арқылы барлық айнымалылары (бос және байланған) тізбегінен табылатын сәйкес терм мен формуланы белгілейік.

алгеьралық жүйеде тізбегіндегітермнің мәнін анықтайық. Берілген тізбегіндегі терм мәнінм(t)[]немесе м(t)[] арқылы белгілейміз.

Анықтама.

Егер t = (1≤ i ≤ s) айнымалы термі болса, онда м(t)[]=

Егер t =константалық терм болса, онда м(t)[]=

Егер t = функционалдық терм болса, онда м(t)[]=[м(t)[ деп аламыз.

Берілген тізбектегі формуланың орындалуы. Мысалдар.

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

Белгілеуі: М |=

Ол үшін алдымен формуланың алгебралық жүйеде орындалу ұғымын атомдық формулалар үшін анықтап, формулалардың күрделілігі бойынша индукцияны пайдаланып бұл ұғымды барлық формулалар жиынына ұлғайтамыз.

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

Мысалы, терміннемесе кез келген {арқылы жиыны үшінтүріндегі терм деп есептеуімізге блады. Бірақ, бұл бос айнымалыларғана. Алформуласынтүріндегі формула десек болады. Бұл формуладағы бос айнымалы тек z болатыны түсінікті.

Негізгі анықтама.

Анықтамада қысқалық үшін белгілеуін қолданамыз.

алгебралық жүйесіндегі тізбегіндегіформуланың орындалуы.

Егер формуласы)= түріндегі атомдық формула болса, онда ,

Егер формуласы Р(),…,түріндегі атомдық формула болса, ондаалгебралық жүйесінде) қатынасы орындалады.

Егер формуласы болса, онда ,

Егер болса, онда ,

Егер формуласытүрінде болса, онда М |= φ[m ̅]⇔М |= ψ[] немесе

М |=θ[

6. Егер болса, онда немесе М |=θ[

7. Егер болса, ондакез келгенэлементі үшін

М |= ψ[]

8. Егер болса, онда қандай да бір элементі табылып М |= ψ[] орындалады.

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

Анықтама .Г берилген сигнатурадағы формулалар жиыны,φ осы сигнатуранын белгили бир формуласы болсын.Егер Г жиынынын кез келген формуласы орындалатын осы сигнауранын арбир сигнатурасынын кез келген тизбегинде φ формуласы да орындалса, онда φ формуласы Г жиынынын семантикалык салдары деп аталады.

Белгилеуи :Г|= φ

Егер φ, ψ формулалары ушин φ |= ψ && ψ |= φ болган жагдайда ψ , φ формулаларын логикалык эквивалентти формулалар дейди

а) Негізгі эквиваленттіліктер.

Енди пикирлер логикасынан бизге белгили логикалык зандарымен бирге предикаттар логикасында кенинен колданылатын логикалык орнектерди турлендируге арналган негизги логгикалык эквиваленттиктердин далелдеулерин негизги аныктамага суйенип беремиз

Егер ψ формуласында айнымалысы бос болып кездеспесе онда томендеги эквиваленттиктер орындалады

1 .⌐ ∀φ(υ) ~Ǝ υ ⌐ φ(υ),

2⌐Ǝυφ(υ)~ ∀υ⌐φ(υ)

3(∀υφ(υ)˄ψ)~ ∀υ(φ(υ)˄ψ)

4(ψ˄∀υφ(υ))~ ∀υ(ψ˄φ(υ)

5((ψ˄Ǝυφ(υ))~Ǝυ(ψ˄φ(υ))

6(Ǝυφ(υ)˄ψ)~Ǝυ(φ(υ)˄ψ)

7(ψ˅∀υφ(υ)~ ∀υ(ψ˅φ(υ))

8(∀υφ(υ)˅ψ)~ ∀υ(φ(υ)˅ψ)

9(Ǝυφ(υ)˅ψ)~Ǝυ(φ(υ)˅ψ)

10(ψ˅Ǝυψ(υ))~Ǝυ(ψ˅φ(υ))

11(∀υφ(υ)→ψ)~Ǝυ(φ(υ)→ψ)

12(ψ→∀υφ(υ))~ ∀υ(ψ→φ(υ))

13(Ǝυφ(υ)→ψ)~ ∀υ(φ(υ)→ψ)

14(ψ→Ǝυφ(υ))~Ǝυ(ψ→φ(υ))

15(∀υφ(υ)˄ ∀υθ(υ))~ ∀υ(φ(υ)˄θ(υ))

16(Ǝυφ(υ)˅Ǝυθ(υ))~Ǝυ(φ(υ)˅θ(υ))

17Егер у айнымалысы φ(υ) формуласында кездеспесе ,онда

∀υφ(υ)~ ∀уφ(у),Ǝυφ(υ)~Ǝуφ(у)

18 ∀υψ~ψ

19Ǝυψ~ψ

Жогарыдагы эквиваленттиктердин копшилиги озинин алдындагы эквиваленттикке косалкы эквиваленттилик болатынын байкауга болады.

Осыны ескерип тизимдеги эквиваленттиктердин далелдеулеринин ишинен аздаган киындык тугызатын 1ши эквиваленттикти далелдеймиз.

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

a) Пренексті нормаланған форма. Анықтама және мысал.

в) Ауыстыру туралы лемма(дәлелдеусіз). Теорема.

а)

Анықтама. Егер кванторсыз формула болса, онда (i = 1, т) кванторлары үшін = түріндегі формуланы npeнeкcmi нормаланган форма (ПНФ) деп атаймыз. Егер ПНФ- дағы кванторлардың барлығы болып келсе, ондай формуланы -формула (-формула) немесеуниверсалды (экзистенсиалды) формула деп атаймыз.

Мысалы, (Q²(x,y)P¹(x)) формулаcы пренекстi норма­ланган формада тұр, ал пренексті нормаланган формада тұрған(P¹(x)Q²(x,y)P¹(z)) формуласы универсалды формула да, (Q²(x,y)(P¹(v)P¹(x)) формуласы экзистенциалды формула болады.

в)

Лемма(Ауыстыру туралы).А₁А₂,...,А_т- формуласынд кездесетін әріптердің тізімі болсын. Егер кез келгенi—1,т жэне v ақиқаттық функциясы(ақиқаттық мәндердің орналасуы) үшін

шарттарымен А'₁ ,А'₂ , ..., А’_m ,’формулалары анықталса, онда А'₁ ,А'₂ , ..., А’_m |- қорытуы орындалады.

Теорема 5.6 (ауыстыру туралы). Егер формулаcыформула­сыныңішкі формуласы, ал ₁ формуласы формуласынан фор­муласын оған логикалық эквивалентті₁ формуласымен (~₁) ауыстыру арқылы алынса~₁болады.

Дәлелдеуі.Теореманы формулада кездесетін барльқ логикалық амалдар мен кванторлар саны бойынша индукцияны қолданып дәлелдейміз. п=п() саны формуласында кездесетін барлык логикалық амалдар мен кванторлар саны болсын. Индукциянып бойынша жүргізейік.

1) п =0 болсын. Онда – P^m (t₁ ,…, t_m ) немесе t₁ = t₂ түріндегі атомдық формула болады. Яғни оның 6ip ғана ішкі формуласы (осы формуланың өзі) бар. Демек =. Егер~₁ болса, онда ₁ формуласының аныктамасы бойынша, =болгандыктан,₁ =₁~=

немесе~₁. Индукцияның базисі осымен дәлелденді.

2) Кез келген к<п =n() үшін логикалык амалдар мен квантор­ларының саны к санына тең формулалар теореманың тұжырымын қанағаттандырады деп есептейік те, теореманы п үшін дәлелдейік. Негізгі эквиваленттіліктерден формуласы темендегі үш жағдайдың бірінде кездеседі деп алуымызга болады.

1. формуласы түріндегі формула. Онда п () =п() - 1 = = п - 1 < п. Сондықтан индукция жоруы бойынша формуласы теореманың тұжырымын қанағаттандырады. Егер формуласы формуласының ішкі формуласы болса, онда формуласыформуласының да ішкі формуласы болады. Егер ₁ формуласы формуласынан формуласын₁ формуласымен ауыстыру арқылы алынса, онда қандай да бip ₁ формуласы үшін ₁ = ₁ жэне ₁ формуласы индукцияның жоруы бойынша ~₁ болғанда формуласына эквиваленті, яғни ~ ₁ => ~₁ .Теорема бұл жағдай үшін дәлелденді.

2. :=. Ондажәнеформулаларындағы барльқ логикалық амалдар мен кванторлар санып санынан кіші болады. Ендеше бұл формулалар үшін индукция жоруы орындалады. Егер формуласыформуласыныңішкі формуласы болса, онда формуласынемесеформуласының біріншіішкі формуласы болады. формуласыформуласыныцішкі формуласы болсын деп есептейік. Оны ~₁ болатындай ₁ формуласымен ауыстырсақ, онда ~ ₁ болатындай ₁ формуласын аламыз. Онда ₁ = ₁ жэне ~ ₁~_{1 .}

3. = v(v).

Егер формуласыформуласыныңішкі формуласы болса, онда ол формуласыныңөзі немесе (v) формуласының ішкі формуласы болады. Алғащқы жағдай үшін бәрі анық. Екінші формуласы(v) формуласының ішкі формуласы болған жағдайда, (v) формуласы үшін индукция жоруы орындалады, өйткені п ((v))= п-1. Егер формуласын онымен логикалық эквивалентті₁ формуласымен ауыстьрсақ, индукция жоруы бойынша (v) ~ ₁(v), яғни ₁~v₁ (v) ~ v(v) ~ .Kepi жағдай да осы жолмен дәлелденеді.