1-lektsiya. Qatnaslar. Binar qatnaslar
Aytımlar esabının’ qarama-qarsısızlıg’ı. Tolıqlıg’ı
Download 353.65 Kb. Pdf ko'rish
|
- Bu sahifa navigatsiya:
- Da’lillew
- 4- lektsiya. Predikatlar esabi. Toliqlig`i qarama-qarsiliqsizlig`i.
- Predikatlar esabı
- Predikatlar esabının’ qarama-qarsızlıg’ı h’a’m tolıqlıg’ı
- 6-lektsiya. Algoritim tu’sinigi ha`m onin` tiykarg`i qa`siyetleri. T
|
Aytımlar esabının’ qarama-qarsısızlıg’ı. Tolıqlıg’ı
Anıqlama:11.1 Aytımlar esabının’ aksiomalar sistemasında h’esh qanday ∝ formula o’zinin’ biykarlaması ∝ menen bir waqıtta da’liylenbese aytımlar esabının’ aksiomalar sisteması qarama-qarsılıqsız delinedi. Teorema:11.1 Eger Ξ A bolsa, onda # A boladı. Da’lillew : Aytımlar esabının’ tiykarg’ı da’lillewshi formulaları aksiomalar olardın’ birdeyligine ras ekenligi tikkeley ma’nisler tablitsasın du’ziw arqalı kiriw mu’mkin. Qalg’an da’lilewshi formulalar aksiomalardan S h’a’m MR qa’deleri arqalı alınadı. Al bul qa’deler boyınsha alıng’an formulalardan birdeyligine raslıg’ı 10-lektsiya na’tiyjelerinen kelip shıg’adı. Teorema:11.2 Aytımlar esabının’ aksiomalar sisteması qarama-qarsılıqsız.
:
Ξ
&
Ξ
Teorama 11.1 boyınsha ΞA h’a’m Ξ A. Bul mu’mkin emes,sebebi birdeyine ras formulanı biykarlaması birdeyine jalg’an formula boladı.(4- lektsiyanı qaran’) Anıqlama:11.2 Qa’legen birdeyine ras formula, aytımlar esabının’ aksiomalar sistemasıda da’liylenetug’ın bolsa, bunday aksiomalar sisteması ken’ ma’niste tolıq delinedi. Biz aytımlar esabının’ aksiomalar sisteması ken’ ma’niste tolıq ekenligin da’liylew ushın to’mendegi teoremalardan paydalanamız. Bul teoremalardın’ da’liyllewin (1) II bap §7den tabıwg’a boladı. Teorema:11.3 Ξ A ∨¬A. Teorema:11.4 Eger aytımlar esabının’ aksiomalar sisteması ken’ ma’niste tolıq ekenligi to’mendegi teoremalardan kelip shıg’adı. 18 Teorema:11.5 Eger ∝ birdeyine ras formula bolsa, ol aytımlar esabında da’liyleniwshi formula boladı. Da’liyllew: Ξ ∝ bolsa teorema 11.4 boyınsha A 1 ∨¬A
1 ,...,A
n ∨¬A
n ΞA boladı. Teorema 11.3 boyınsha Ξ A
1 ∨¬A
1 ,...,A
n ∨¬A
n . Bul eki formulag’a MR qa’desin qollansaq ΞA ekenligi kelip shıg’adı. Anıqlama:11.3 Aytımlar esabının’ formulaları ushın, olardın’ da’liyleniwshi ekenligin yamasa da’liyleniwshi emesligin anıqlawshı algoritm bar bolsa, da’liylew ma’selesi sheshiliwshi delinedi. Teorema:11.6 Aytımlar esabının’ formulaları ushın da’liylew ma’selesi sheshiliwshi boladı. Da’liyllew: Meyli ∝ aytımlar esabının’ qa’legen formulası bolsın. Aytımlar esabı tolıq bolıw ushın h’a’r qanday #A formulası ΞA bolıwı kerek. Solay etip ∝ formulası da’liylleniwshi yamasa da’liylenbewshi bolıwı ushın, ol birdeyine ras yamasa birdeyine ras emesligin ko’rsetiw jetkilikli. Bunı da’liyllew ushın ∝ nın’
ma’nisler tablitsasın du’ziw kerek. Bul eki algoritmde shekli qa’demnen keyin qoyılg’an sorawg’a juwap beredi. Shınıg’ıwlar. To’mendegi teoremalardı da’liylen’: 1) Ξ(Α→Β)→(¬Β→¬Α) 2) Ξ(Α→Β)→((Α→)→(Α→Β&) 3) ΞΑ∨¬Α
4) A,B ΞAWB
5) A,B ΞA∨B
6) A,B ΞA→B
7) A,B ΞA;B
8)A Ξ¬¬A.
9) Lektsiyadan basqa qanday aksiomalar sistemasın bilesiz ?
19
Tayanısh tu’sinikler: Aksiomalıq teorema tu’sinigi. Predikatlar esabının’ aksomaları,keltirip shıg’arıw qag’ıydaları. Da’liyleme h’a’m da’lillew. Matematikalıq teoriyanın’ qarama-qarsılıg’ı,tolıqlıg’ı tu’sinikleri.Bar bolıw h’aqqında teorema. Lindenbawn h’a’m Gedel teoremeları.
Biz bul lektsiyada jan’a aksiomalıq teorema bolg’an predikatlar esabın du’zemiz. Ol ushın aytımlar esabındag’ı sıyaqlı aksioma kelip shıg’ıw qa’delerin, da’lilleme tu’siniklerin anıqlaymız. Predikatlar esabının’ aksiomalar sxeması retinde to’mendegi formulalardı alamız. I. Aytımlar esabının’ barlıq aksiomalar yag’nıy (a),(v),(2a),(2v),(2c),(3a),(3v),(3c),(4a),(4v),(4c),(5a),(5v) II. (6a) ∀xR(x)→R(u)
(6v) R(u) →xR(x) Bul jerde R(x)-qa’legen o’zgeriwshi predikat, X,U ushın erikli o’zgeriwshi. Keltirip shıg’ıw qa’deleri to’mendegishe I. MR-qa’de Α,Α→Β/Β II.
S r -qa’de Α(r)/Α(Β) III.
S ∀∋ -qa’de Α(x)/Α(Β) (x-baylan) IV.
S x t -qa’de V.
∀-qa’de Β→Α(x)/Β→∀xΑ(x) VI.
-qa’de Α(x)→Β/xΑ(x)→ Β Anıqlama:15.1 1 0 Predikatlar esabının’ h’a’r bir aksioması kelip shıg’ıwshı formula boladı. 20 2 0 Aksiomalardag’ı kelip shıg’ıw qa’deni shekli ma’rte qolladıwdan alıng’an formula kelip shıg’ıwshı formula boladı. 3 0 Basqa kelip shıg’ıwshı formula joq. Anıqlama:15.2 Predikatlar esabındag’ı da’lilleme dep S 1 ,C
,. ..C n
formulanın’ to’mendegi sha’rtlerdi qanaatlandıratug’ın izbe-izligine aytıladı. I.C
8 ya aksioma 8=1,n II. C 8
(8=1,n) ya o’zinen aldın’g’ı formuladag’ı keltirip shıg’arıw qa’delerinin’ qoollana alamız. S 1
n izbe-izligi usı eki sha’rtti qanaatlandıratug’ın S n -formulasının’ da’liylemesi delinedi. n-sanı da’lillemenin’ uzınlıg’ı delinedi. Eger bul eki sha’rtke to’mendegi 3-sha’rtti qossaq gipotezalı da’lillewdin’ anın’laması kelip shıg’adı. 3. Ya,S
8 - Α 1 , .. .., Αn formulalardan’ birewine ten’. Da’lillewshi formulanı (gipotezadan) Α( Α) dep belgileymiz. Endi da’lillewshi formulalardın’ bazı bir mısalların keltiremiz. Teorema:15.1 ∀Α(x)∼ ∀xΑ(u) Da’lillew : ∀x r(x)→R(u)-(6a-aks) II. ∀x r(x)→ ∀uR(u) - ∀-qa’de III. ∀uR(u) →R(x)-S u x
∀- qa’de
IV.- ∀uR(u) →∀xR(x)- ∀-qa’de V. ∀xA(x) →∀uΑ(u)-S r -qa’de
VI. uΑ(u) →∀xΑ(x)-S r -qa’de
VII. ∀xΑ(x)∼ ∀uΑ(u)-(5.6) Teorema:15.3 ⊃xΑ(x)∼ ⊃u Da’lillewi oqıwshılarg’a qaldırıladı. To’mendegiler tuwındı keltirip shıg’arıw qa’deleri da’lillenedi. I. ⊂a(x)bolsa f∈∀Α(x) II. ∀xΑ(x)∈Α(t) 21 Sh. Α(t) ∈xΑ(x) IV.
,Α(x)⊂Β bolsa ,⊃xΑ(x)+Β boladı. Predikatlar esabının’ qarama-qarsızlıg’ı h’a’m tolıqlıg’ı
Teorema:16.1 Predikatlar esabı qarama-qarsılıqsız. Bul teoremanı da’lillew 11-lektsiyada keltirildi. Anıqlama:16.1 Predikatlar algebrasının’ h’a’r bir birdeyine ras farmulası da’lilleniwshiler bolsa,predikatlar esabı ken’ ma’niste tolıq delinedi. Anıqlama:16.2 Eger S ∈A h’a’m S∈Α bolg’an h’esh qanday Α tastıqlaw bolmasa S tastıqlawlar ko’ligi qarama-qarsılıqsız delinedi. 2. S-ko’pligine kiriwshi h’a’r bir tastıqlawlar ras bolatug’ın model bar bolsa S-ko’pligi orınlawshı ko’pligi delinedi. 3. Ha’r bir A-tastıqlaw ushın S ∈Α yamasa S∈Α bolsa,S-tolıq ko’plik delinedi. To’mendegi eki lemmanı da’liylew oqıwshılarg’a jeke jumıs sıpatında qaldıramız. Lemma:16.1 Eger S 0 ⊆S
⊆.. ..⊆S n ⊆.. Sha’rtli qanaatlandırıwshı h’a’r bir S 8 (8=0,1,2,.. ..) Tastıqlawlar ko’pligi qarama-qarsılıqsız bolsa,onda tastıqlawdın’ S= ∪S 8 ko’pligi qarama-qarsılıqsız boladı. Lemma:16.2 Tastıqlawdın’ S-ko’pligi qarama-qarsılıqsız bolıwı ushın onın’ h’a’r bir shekli u’les ko’pligi qarama-qarsılıqsız bolıwı za’ru’rli h’a’m jetkilikli. Teorema:16.2 (Lindenbaum) Eger S-tastıqlawdın’ qarama-qarsılıqsız ko’pligi bolsa,onda S-ti o’zishine alatug’ın tastıqlawlardın’ T-tolıq sisteması bar boladı. Da’lillew: T-ko’pligin to’mendegishe du’zemiz. S-tin’ tastıqlawların nomerattsiyalap shıg’amız Α 0 , Α 1 , .. .., Α n , usınday nomerattsiyanın’ biri bolsın. 22 Kerekli T-ko’pligi 2-lemmada keltirilgen ken’eyip barıwshı barıwshı izbe- izliktin’ birikpesi sıpatında du’zemiz. h’a’r bir S 8 -ko’pligi 8-qa’demde du’zilip , onın’ qarama-qarsılıg’ı induktsiya menen da’liylenedi.
S 0 = S-eger S∈Α 0 , yamasa S ∈Α 0
S ∪Αkeri jag’dayda Eger S 0 =S bolg’an teoremanın’ sha’rti boyınsha S 0 qaramaq
-qarsılıqsız. S 0 =S ∪Α bolsın sha’rt boynsha S∈⊂Α 0 h’a’m S ∈Α 0 , S 0 qarsılıqlı desek bazıbir Β formula ushın S,Α 0 ∈Β&Β boladı. Basqasha aytqanda S, Α∈Β&Β boladı. S ∈(Α→Β)→(Β→Α)- kontorpozittsiya S ∈(Α
0 →Β&Β)→((Β&Β)→Α 0 )
∈(Β&Β)→Α S,(
Β&Β)-Α 0
−(Β&Β)∼Β&Β S ∈Β∨Β S, Β∨Β+Α
0 qatnaslarınan ,Α∈∈Α/∈ qag’ida tiykarında S∈Α 0 kelip shıg’adı,bul jon’arıdag’ı sha’rtke qarsı. Demek, S 0 -qaldıqsız. Meyli endi S n ,n-
adımda du’zilgen ko’plik h’a’m qarsılıqsız bolsın. (n+1) qa’demde to’mendegi ko’plikti du’zemiz. S= S
eger S n ∈Α n+1 yamasa S n ∈Α
n+1
S ∪Α n+1
keri jag’dayda S n+1 qarsılıqsızlıg’ı S 0 -day da’liylenedi. Endi T= ∪S 8 dep alamız. 1 lemma boyınsha S-qaldıqsız. ∈T qa’legen ko’plik bolsa sonday n-nomeri tabılıp =Α
n boladı. S n -ko’pliginin’ du’zilisi boynsha. S n + Α n yamasa S n + Α S n <=bolg’anlıqtan T+Α yamasa T+Α. Demek T- ko’pligi tolıq . To’mendegi teorema h’a’m saldar Gedel teoremasın da’lillegende qollanıladı.
23 Teorema:16.3 Eger S-tastıqlawdın’ qarsılıqsız ko’pligi bolsa,onda S-tin’ qa’legen tastıqlawı ras bolatug’ın model bar boladı. Saldar: Eger predikatlar esabının’ Α-formulası orınlanatug’ın bolsa onda ol shekli yamasa sanaqlı ko’plikte h’a’m orınlanıwshı boladı. Teorema:16.4 (Gedel) Qa’legen Α-tastıqlawı predikatlı esabında da’lillewi ushın ol birdeyine ras bolıwı za’ru’rli h’a’m jetkilikli. Da’lillew: Za’ru’rligi 11-lektsiyadag’ıday da’lillenedi. jetkilikligi : Meyli Α birdeyine ras formula bolsın. Onda Α orınlanbaydı. Yag’nıy bazı bir Β- ko’pligi tabılıp Α∈Β&Β boladı. Kontirapozitsiya qa’desi boyınsha ( Β&Β)∈Α ∈(Β&Β) h’a’m ∈Α∼Α boyınsha ∈Α ekenligi kelip shıg’adı.
Sorawlar h’a’m shınıg’ıwlar. 1.Predikatlar esabında predikattın’ normal formulası qanday boladı ? 2.Da’lillen’ Eger Α⊂Βbolsa,Α∪∈Β 3.Tuwındı keltirip shıg’arıw qa’delerinin’ atların atan’ ? 4.Gedel teoremasının’ za’ru’rlik sha’rtin da’liylen’. 5.S-ko’pligi orınlawshı bolıwı ushın h’a’r bir shekli u’les ko’pligi orınlawshı bolıwı jetkiliklime ? 6.MRh’a’m S-qa’deleri boyınsha birdeyine ras framulalardan alıng’an formula birdeyine ras bolama ?
24
Tayanısh tu’sinikler: Gruppalar teoriyası, Bul algebrası. Kaltsolar teoreması . Formal arifmetika.
Ha’r qanday matematikalıq teoriya predikatlar esabına arnawlı aksiomalardı qosıw arqalı alınadı. A’meliy predikatlar esabı logikalıq akslanıwı menen birge ten’lik predikatının’ qa’siyetlerin belgileytug’ın to’mendegi akslamalardı o’z ishine aladı. .1. x=x .2.x=u→u=x 3.x=u&u=t→x=t 4.x 1
1 &.. ..&x m =u
→ [R(x
1 , .. ,x
m ) →R(u 1 , . . ..,u m )]
5. X 1 =u 1 &.. .&x m =u
→[[(x 1 , .. .. ,x m )=(u
1 , .. ..,u m) ]]
Bunda x,u,5 zatlıq o’zgeriwshiler, R-m-orınlı predikat s-m-orınlı terim. Endi matematikalıq teoremanın’ ayrım mısalların keltiremiz. 1.Gruppalar teoreması. Bul teoremanın’ signaturası <+,0>, arnawlı aksiomaları to’mendegeler (q)
∀x∀u∀z[x+0u+z]=(x+u)+z] (II)
∀x[x+0=0+x=x] (III)
∀x⊃u[x+u=u+x] Endi bul arnawlı aksiomalardag’ı to’mendegi aksiomanı qossaq abel gruppasındag’ı teoreması kelip shıg’adı. (IV)
∀x∀u[x+u=u+x] Signatura < ∪,∩,-0,1> bolsın. To’mendegi arnawlı aksiomalar sistemasına iye bolg’an matematikalıq teoriya Bul algebrası dep ataladı.(qa’legen x,u,z ler ushın)
25 1.x ∪(u∪z)=(x∪u)∪z 2.x
∩(u∩z)=(x∩u)∩z 3. x
∪u=u∪x 4. x
∩u=u∩x 5. x
∪x=x 6. x
∩x=x 7. x
∪(u∪z)=(x∪u)∩(x∪z) 8. x
∩(u∪z)=(x∩u)∪(x∩z) 9. x
∪(x∩u)=x 10. x
∪(x∩u)=x 11.x
∪u=x∩u 12.x
∩u=x∪u13.x∪0=x
14. x ∩0=0
15.x ∪1=1
16. x ∩1=1
17. 0 ≠1
18. x=x
19.x ∪x=1
20. x ∩x=0
3.Koltsolar teoreması: Birlik elementke iye komunikativ h’a’m assotsiativ koltsolar teoreması. <+, ⋅,0,1> signaturasında anıg’lanadı h’a’m to’mendegi arnawlı aksiomalarg’a tayaanadı. 1.0 ≠1 2. x+(u+z)=(x+u)+z 3. x+u=u+x 4. x+0=x 5. x(u+z)=xu+xz 6. ⊃∈(x+u=z) 7. x(uz)=(xu)z 8. xu=ux 9. x ⋅1=1 26 10. Xu=0 ⇒x=0 ∪u=0 Bug’an qosımsha II.orınlansa maydan boladı. II. x ≠0⇒⊃u(xu=1) Bug’an qosımsha 12. xarakteristikası n-ge ten’ maydan delinedi. ⊃n[x∈N&n⋅1=0 &∀ m (m
Bul jerde ulıwmalıq kvantır tu’sinigi qaldırılg’an. 4.Formal arifmetikanın’ signaturası <+, ⋅,s,0> min(2,2,1) s-keyin kemiw funktsiyası. Arnawlı aksiomaları to’mendegilerden turadı. 1. ∀x(s(x)≠0 2. ∀x∀u[s(x)=s(u) x=u 3. ∀x∀u[x=u, s(x)=s(u)] 4. ∀x(x+0=x) 5. ∀x∀u[x+s(u)=s(x)+u 6. ∀x(x⋅0=0) u. ∀x∀u[x⋅s(u)=x⋅u+x] 8. Α(0)&∀x[Α(x)Α(s))]Α(5)N’
Sorawlar h’a’m shınıg’ıwlar 1.Ta’rtiplengen ko’plik ushın arnawlı aksiomalardı jazın’. 2.Algebranın’ tuyıq maydanda anıqlawshı aksiomalardı jazın’. 3.Teoremalardı so’z benen ta’riplen’. A) s(x)+u=s(x+u) B) (x/z) &( U/z)→((x+u)/z). 27
Tayaanısh tu’sinikler: Algoritim. Algoritimli protsess.
Mısalları: Premetiv rekursiya, Superpozitsiya, Minimizatsiya operatorları, mısalları. Dara rekursiv funktsiya. Biz bir tu’rdegi,bir qıylı mazmung’a iye bolg’an ko’p mısallardı sheshiwde qollanatug’ın sxemanı algoritim dep tu’sinemiz. Mısalı sanlardın’ en’ u’lken ulıwma bo’liwshisin tabıw (Evklid algoritimi) Matritsalardı ko’beytiw, ten’lemeler sistemasın sheshiw (Gauss usılı) h’.t.b. Ma’selege algoritimlerdi qollang’anda to’mendegi 3 jag’day bolıwı mu’mkin. 1. Protsess h’esh toqtamaydı 2. Hesh qanday na’tiyje bermey toqtaydı. 3. Bazı bir qa’demnen keyin ma’selenin’ sheshimi tabıladı h’a’m protsess toqtaydı. Algoritimler teoriyasında to’mendegi funktsiyalar ko’p qollanıladı. S 1 (x)=x+1 O 1 (x)=0 J m n (x 1 , .. .,x n )=x
m (1<=m<=n) Bul funktsiyalar en’ a’piwayı funktsiyalar dep ataladı. ϕ n (x 1 , .. .,x n )= ϕ m ( ƒ 1 m (x 1 , .. ,x
n ) ,.. ., ƒ m
(x 1 , .. .,x n ) funktsiyası ϕ m , ƒ n 1 , .. . , ƒ m n funktsiyasınan superpozitsiya arqalı alıng’an delinedi. Egerde
ƒ n (x 1 , .. .. ,x n )=
m (t 1 , .. .,
t m ) bolsa bul funktsiyanı ϕ,ƒ 1
ƒ k
funktsiyasınan ornına qoyıw arqalı alıng’an dep ataymız. Bunda t
i = ƒ j (x j , . ..,x js ) ƒ n+1
(x q , .. .. ,x n ,u) funktsiyası ƒ n
1 , .. .. ,x n ) h’a’m 28 ϕ n+2 (x 1 , .. .. ,x n ,u,z) funktsiyalarınan prilitsiv rekursiya boyınsha alıng’an delinedi. Egerde ol to’mendegi prilitsiv Rekursiya sxeması arqalı beriletug’ın bolsa
ƒ n+1
(x 1 , .. .. ,x n ,0)=
ϕ n (x 1 , .. .,x n )
ƒ n+1
(x 1 , .. .. ,x n ,u+q)=
ϕ n+w
(x 1 , .. .,x n ,
ƒ n+1
(x 1 , .. .. ,x n ,u)
n=0 bolg’anda
ƒ(a)=a ƒ(u+1)=ϕ(u,ƒ(u) Bunda a-turaqlı bir orınlı ma’nisi a-g’a ten’ funktsiya ƒ n (x 1 , .. .. ,x n )
funktsiyasın ϕ n+1 (x 1 , .. .. ,x n ,u) funktsiyasınan minimizatsiya arqalı alıng’an dep aytamız h’a’m ƒ n (x 1 , .. .. ,x n )= µu[ϕ n+1 (x 1 , .. .,x n ,u)=0] dep belgileymiz egerde to’mendegi sha’rt orınlanatug’ın bolsa ƒ n (x 1 , .. .. ,x n ) anıqlang’an h’a’m u ten’ tek g’ana sonda ϕ n
1 , .. .,x n ), .. ., ϕ n (x 1 , .. .,x n ,u-1) ler anıqlang’an h’a’m nolge ten’ emes ,al ϕ n (x 1 , .. .,x n ,u)=0
Anıqlama:18.1 Eger ƒ n (x 1 , .. .. ,x n ) funktsiyası en’ a’piwayı funiktsiyalardan shekli sandag’ı superpozitsiya preliktiv rekursiyanı qollanıw arqalı alınatug’ın bolsa priliktiv rekursiya funktsiya delinedi. Anıqlama18.2 ƒ n (x 1 , .. .. ,x n ) funktsiyası en’ a’piwayı funktsiyalardan shekli sandag’ı superpazitsiya , priliktiv rekursiya h’a’m minimizatsiya operatorlardan qollanıw arg’alı alınatug’ın bolsa,dara rekursiv funktsiya delinedi.
Sorawlar h’a’m shınıg’ıwlar 1.En’ a’piwayı funktsiyalardan tek superpozitsiya arqalı qanday funktsiyalar alınadı
? 29 2.Funktsiyalardın’ prilitiv rekursiv ekenligin da’liylen’. A) ƒ(x)=n
B) ƒ(x)=x+n V) ƒ(x,u)=x+u G) π(x)
B) ƒ(x,u)=x/u eger x,u keselligi bo’linse Download 353.65 Kb. Do'stlaringiz bilan baham: 
|