19.Орындалатын формулалардың қасиеттері

а)Әрқашан ақиқат формулалардың мысалдары

в)Орындалатын және әрқашан жалған формулалар мен олардың қасиеттері. Мысалдар.

Салдар 5.4 φ сейлемі берілсін. Онда φ сейлемі ϻалгебралық жуйесінде ақиқат (орындалатын) болуы үшін бұл формуланың ɱ жиынынан алынган кандай да бip (кез келген десек те болады) элементтер тізбегінде орындалуы кажетті және жеткілікті

Дәлелдеуі. Сейлемде бос айнымалы болмайды.

Аныктама. 1. σ сигнатурасының φ(х) формуласы берілсін. Осы сигнатураның ϻ = (М, σ) алгебралық жуйесінен алынған кез келген m=(m_1, ..., m_s) тізбегі үшін ϻ|=φ[т] болса, онда φ(х) формуласын ϻ алгебралық жуйесінде ақиқат формула деп аталады (Белгіленуі ϻ\= φ).

σ сигнатурасының φ(х) формулаеы берілсін. Осы сигнатураның кандай да бip ϻ<М,σ> алгебралық жуйесінен алынган m=(m_1, ..., m_s) тізбегі үшін ϻ|= φ[m] болса, онда φ(x) формуласын ϻ алгебральs0 жуйесінде орындалатын формула деп атаймыз.

Берілген сигнатураныц ешбір структурасына орындалмайтын формуланы әрқашан жалған(кайшылық) деп атайды

Егер σ сигнатурасының кез келген ɱ алгебралық жуйесінде φ формуласы акикат болса, онда φ формуласын әрқашан ақиқат (жалпымәнді) формула деп айтамыз. Белгіленуі: |= φ.

Бірнеше мысал келтірейік.

1 мысал. [Р(х) ^¬Р(у)] формулаcы кандай формула (орындалатын, әркашан акикат немесе әркашан жалган) болады?

Шешуі .

Р(х)-:”x- жуп сан” предикаты болсын. Онда берілген формула N = <N, Р> моделінде акикат болады. Ал егер натурал сандар жиынының орнына Е - жуп сандар жиынын алып М= <Е,Р> моделін карастырсак, жогарыдагы сейлем бул моделде орындалмайды. Демек жогарыдагы формула әркашан акикат емес, бірақ орындалатын формула.

2 мысал. (х,х_,у) формуласы акикат болатындай форму­ланың сигнатурасына сәйкес моделді таңдап алыныз.

шешуі.

N = <N, P> моделінде P предикаты P(x,y,z)=ax*y=z катынасына интерпретациялансын, Онда (х,х_,у) формуласы кез келген санның квадраты болатыны туралы айтады. Демек, берілген формула тандалган моделде акикат формула болады.

3 мысал. хР(x, у, z) формуласы акикат болатындай формула­ның сигнатурасына сәйкес моделді таңцдап алыңыз.

Шешуі.

Тагы да N = <N, Р> моделш карастырайық. Егер Р предикаты P(x,y,z)=ax*y=z катынасы аркьлы интерпретацияланса,онда берілген формуланы бірлік элемент қанағаттандырады.

Ал Р предикатының интерпретациясы P(x,y,z)=ax+y=z шартымен аныкталса, онда бұл формуланын шешімі нелдік элемент болады. Демек бұл формула орындалатын фомула, бірақ әркашан акикат формула емес.

4 мысал. (х,_,у) →хР(x, у, z) формуласы әркашан акикат формула бола ма? Kepi жагдайда ол акикат болмайтын моделді кұру керек.

Шешуі.

Формулага сэйкес сигнатураның ең болмаганда үш элементі бар қандай да бip ϻ структурасын карастырайық. Бул стуктурада Р(х, у) предикаты симметриялы графтың х жне у тобелері кыр аркылы жалгасканын білдірсін. М= {а, b,c} ең болмағанда үш элементтен турады. Егер a төбесі b төбесімен инцидентті, ал с тебесімен инцидентті емес болса, онда У айнымалысының орнына а элементін койсак, ϻ моделінде (х,_,у ) формуласы акикат, ал хР(x, у, z) формуласы жалган болады. Яғни ϻ моделінде (х,_,у) →хР(x, у, z )формуласы да жалган болады. Демек бұл формула әркашан акикат формула бола алмайды.

5 мысал. ¬A(y)^ A(z) формуласының әркашан жалган болатынын негізгі анықтамага сүйеніп дәлелде.

Шешуі.

Осы формуланың сигнатурасының кандай да 6ip ϻ структурасында берілген формула акикат болады деп есептейік. Онда кайшылықты негізгі анықтама бойынша аламыз.ϻ|=¬A(y)^A(z) болса, онда негізгі анықтама бойынша ϻ|=¬A(y) және ϻ|=A(z). Тағы да

негізгі аныктама бойынша b M элементі үщін ϻ|=¬A(b) . Ал ϻ|=A(z) катынасына негізгі аныктаманы колдансак, кез келген a M үшін ϻ|=A(a). Егер a M элементі кез келген болгандыктан, алдыңғы катынаста a=b алуға болады, онда ϻ|=A(b) .Тағы да негізгі аныктама бойынша ϻ|=¬A(b)^A(b)катынасын аламыз. Кайшы­лык. Осы кайшылык берілген формуланың өз сигнатурасының ешбір модеінде орындалмайтынын керсетеді. Яғни ол әркашан жалган формула.

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

. Шешуі.

(x, у, z), (х, у, z) предикаттары (x, у, z) = ax+y=z және (х, у, z) = ax*y=z шарттарымен анықалсын. Элементтердің алдын-ала белгілі касиеттеріне сәйкес формулалар жазып, олардыц ϻ = (N, S³, Р³) структурасында кай кезде акикат болатынын тексерейік.

х жай сан болганда ғана ϻ структурасында акикат болатын 6ip бос айнымалы формула жазайык.

х - жай сан . Алдымен осы формулада кездесететін y=x және у = 1 тендіктерін берілген сигнатураның формулаларын жазуымыз керек.

у = 1  и (у* и = и)  P³(y, и, и)

v = 0  k (k+v=k)  S³(k, v, k).

Сонғы формуланы φ₀(v) аркылы белгілесек, онда у = x  v(v=0^(y+v=x))v φ₀(v)^(_,у,z х_,)

Демек x санының жай сан болу касиетін берілген сигнатурада (_,у, z, х_,))→ v φ₀(v)^(_,у,v х_,))˅иP³(y, и, и) формулаcы

аркылы сипаттай аламыз. Бул касиетті 6ip айнымалылы формулаcы аркылы белгілейміз.

мысал.

формуласы әркашан акикат сейлем болады.

Шешуі

Егер σ=(Q²) 6ip гана бинарлык Q² предикаттык символдан туратын сигнатура болса, онда формуласы акикат формула немесе ойы символды турде келесі белгілеу |= аркылы жазады.

мысал.

формуласы әркашан акикат формула бола ма?

Шешуі

Heriзгі жиын ретінде бутін сандар жиынын Z-тi алайык. интерпретациясын кабылдасак, жогарыдагы тужырымгатepiс жауап беру үшін z = x + 1 алсак жеткілікті.

Тужырым 5.5 Егер t терімі x айнымалысы ушін бос болып, ф(t) формуласы ф(х) формуласынан x айнымалысының бос кездесулерін t термімен ауыстыру аркылы алынса,

xφ(x)→φ(t)

φ(t)→xφ(x)

формулалары әркашан акикат формулалар болады.

9 мысал. Енді жогарыдагы тужырымның шарттары орыналмаса, жогарыдагы eкi формула акикат болмайтындай φ(х) формуласы мен t терміне мысалдар келпрейк.

1)σ = <=, +, е> сигнатурасыныц N- натурал сандар жиынындагы интерпретациясы бойынша + - натурал сандарды косу, = - тендік катынасы, е – бәрлік элементі білдірсе,

ϻ= < N, =, +, е>алгебралык жуйесінде φ(х):=(x=е) формуласы мен t(x,y):=х + у термі үшін xφ(x)→φ(t(x,x)) формуласы жалган болады.

2) σ=<=,Р,+> сигнатурасы берілсін. Мұндағы Р предикаттык символы 6ip орынды. Осы сигнатураның алгебралык жуйесін аныктайық. N - натурал сандар жиыны, + амалы мен = катынасы кәдімгі магыналарында аныкталган. Ал Р(п)=a жұп сан шартымен анықталса, t термі косу амалын білдірген жагдайда, P(t) →xP(x) формуласы ϻ= <N, σ> алгебралык жуйесінде жалган болады.

20) Предикаттар логикасының заңдары.

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

в) 1-ші және 11-ші заңдар.

Орындалатын формулалар және олардың қасиеттері.

Анықтама. Г берілген сигнатурадағы формулалар жиыны жэне осы сигнатураның белгілі6ip формуласы болсын. Егер Г жиынының кез келген формуласы орындалатын осы сигнатураның әp6ip структурасының кез келген тізбегінде формуласы да орындалса (қысқашаМ, Мⁿ, Г,М| = [] =>М| = []), ондаформуласы Гжиынының семантикалық салдары деп аталады.

Белгілуі Г |=.

Егер жәнеформулалары үщін|=( Оқылуы:формуласыформуласының салдары) және|=(формуласыформуласының салдары) болған жағдайдажәнеформулаларынлогикалық эквивалентті(Белгілеуі ~) формулалар деп атайды.

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

Енді пікірлер логикасынан бiзгe белгілі логикалық заңдарымен 6ipгe предикаттар логикасында кеңінен қолданылатын, логикалық өрнектерді турлендіруге арналған негізгі логикалық эквиваленттіліктердің(логика зацдарының) тізімін келтірейік. Осы тізімдегі кейбір маңызды эквивалеттіліктердің дәлелдеулерін негізгі аньқтамаға сүйеніп береміз.

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

1°. ()~ (),

2°. ()~ (),

3°. ( () ) ~ ()),

4°. ( ()) ~ ()),

5°. (()) ~( ()),

6°. (()) ~( ()),

7°. ( ()) ~ (()),

8°. ( ()) ~ (()),

9°. (()) ~(()),

10°. (()) ~(()),

11°. ( ()) ~ ( ()),

12°. ( ()) ~ ( ()),

13°. (()) ~ ( ()),

Жоғарыдағы эквиваленттіліктердің көршілігі өзінің алдындағы эквиваленттілікке қосалкы эквиваленттілік болатынын байқауга болады.

Осыны ескеріп, тізімдегі эквиваленттіліктердің дәлелдеулерінің ішінен аздаған қиындық туғызатын l°-шi, 6°-шы жэне 13°-шi эквиваленттіліктердің ғана дәлелдеулерін береміз. Ол үшін негізгі анықтаманы еске ұстасақ жeткiлiктi.

1°. ()~ ()

|= жағдайын немесе ()| = () болатынын көрсетейік. Қандай да6ip М структурасында берілген Мⁿ тізбегі үшін М| = () [] болсын, онда М| () [], яғни М|=[а,] қатынасы кез келген а Мүшін орындала бермейді, демек ең болмағанда 6ip b М элемен табылып М|[b,] немесе М|= [b,] болады. Онда негізгі анықтама бойынша М |= () []. Яғни ()| = ().Тура осылай жолмен()|= () болаты­нын көрсетуге болады. Демек ()~ (). Бірінші қасиет осымен дәлелденді.