Adj meg külön véve olyan tudományos feladatokat, aminek már ismered a megoldásait ! - vagyis együtt véve példákat . Ez a példád, ill. feladatod nem csak matematikai példa, ill. feladat lehet, de ha e példád, ill. feladatod nem formális, akkor a tény alapú megoldása legyen kattintásra elérhető online az interneten .
Előzetes megjegyzés: az alábbiak mind extenzionális halmazra vonatkoznak, tehát ha két elem "működése" azonos, akkor azonosak.
Valamint emlékeztetni szeretnék arra, hogy minden kombinátornak van fixpontja, és a fixpont eleme a kombinátor értékkészletének. Ha mondjuk a kombinátor értékkészlete a két logikai érték (t és f), akkor a fixpont is ezek egyike.
Ezek alapján azt mondanám, hogy nemcsak ilyen általános egyenlőségvizsgáló nincs, de semmilyen nemtriviális (nemüres, nemteli) részhalmaznak nincs karakterisztikus függvénye. (Illetve a függvényt reprezentáló kombinátora, tehát olyan kombinátor, ami a halmaz elemeihez t-t rendel, a nemelemeihez f-t.)
Indirekten tegyük fel, hogy k egy ilyen karakterisztikus függvény, m a kérdéses halmaz egy eleme (member), n pedig egy nemeleme (non-member).
Legyen k'x = kxnm = B(Vnm)kx
Ez a k' egy módosított karakterisztikus függvénye a halmaznak: az elemekhez n-et, a nemelemekhez m-et rendeli.
Most még kellene a k' fixpontja, ez a fixpont vagy n vagy m lehet.
Sajnos akár k'n=n -t, akár k'm=m -et teszük fel, ellentmondást kapunk, mivel a definíció szerint k'n=m és k'm=n kellene legyen.
Akkor most ott tartunk, hogy nincs olyan nem-konstans kombinátor, aminek az értékkészlete a logikai értékek halmaza.
PS: természetesen az alaphalmaz egy-egy részhalmazán vannak karakterisztikus függvények, például egy számról meg tudjuk mondani, hogy prím-e, egy bináris fáról meg tudjuk mondani, hogy kiegyensúlyozott-e.
Ilyen u elemet könnyen tudnánk mondani, ha lenne egy olyan e, ami bármely két elem extenzionális egyenlőségét el tudja dönteni, mégpedig úgy, hogy minden x,y párra: exy=t=K, ha x és y extenzionálisan egyenlő, és exy=f=KI, ha x és y extenzionálisan nem egyenlő.
Emlékeztetőül egy példa az extenzionálisan egyenlőre: SKS és SKK extenzionálisan egyenlők, ugyanis SKSx = Kx(Sx) = x, SKKx = Kx(Kx) = x
Szóval ha van ilyen e elem, akkor uabαβx lehetne (eax)αβ (vagy akár(eax)α((ebx)β<további_elágazás_vagy_hibajelzés>)).
Tegyük fel, hogy efy=y valamely y értékre (a szokott trükköt használva legyen y=θ(ef)) Ekkor y maga is a t és f valamelyike kell legyen, mégpedig ha y=t, akkor t=eft kellene teljesüljön, ha pedig y=f, akkor f=eff kellene igaz legyen. Sajnos mind a kettő ellentmondásra vezet, vagyis el kell engednünk azt a feltevést, hogy van ilyen e kombinátor.
PS: Most emlékezhetünk, hogy a logikai értékek tárgyalásánál volt ekvivalencia-kombinátor, pl: εxy=xy(ny)=Sxny=(CSn)xy, erre miért nem vonatkozik az előbbi ellentmondás?
Azért, mert ez csak logikai értékek (azaz t=K és f=KI) egyenlőségét jelzi logikai értékkel, egyéb bemenetekre bármi is lehet a kimenete, így a y=θ(εf)=εf(θ(εf))=εfy sem kell logikai érték legyen, sőt: a fentiek értelmében y nem is lehet logikai érték, mert az ellentmondásra vezetne.
Ez most kicsit paradox lesz, de azért vizsgáljuk meg ezeket az állításokat:
1. Ha ez az állítás igaz, akkor létezik a Mikulás. 2. Ha létezik a Mikulás, akkor ez az állítás igaz.
3. Ez a mondat ugyanannyira igaz, mint az, hogy létezik a Mikulás.
4. Ez a mondat hamis.
Ezekkel az a gond, hogy ha feltesszük, hogy van valamilyen igazságértékük, akkor vagy ellentmondást kapunk, vagy bebizonyítjuk a Mikulás létezését.
Az a kérdés, hogy lehet-e ezt a paradoxont logikai kombinátorokkal bemutatni.
Tegyük fel, hogy van egy φ függvény, ami minden kombinátorhoz egy logikai értéket rendel. Ez még önmagában nem vezet ellentmondáshoz, ezért vizsgáljunk meg három alesetet:
1. Tegyük fel, hogy létezik egy n kombinátor (negáló), amelyre φ(nx) = not(φ(nx)) Ekkor az lesz a gond, ha valamely y-ra y=ny, mert akkor φ(y) = φ(ny) = not(φ(y)). Ez az y nem más, mint a θn. (Ez összehasonlítható a fenti 4. állítással.)
2. Tegyük fel, hogy létezik egy e kombinátor (ekvivalencia), amelyre φ(exy) = φ(x)=φ(y). Ekkor bármely x-re bebizonyíthatjuk, hogy φ(x)=igaz, ha találunk egy y elemet, amelyre y=exy [ilyen az y=θ(ex)], mert akkor φ(y) = φ(exy) = (φ(x)=φ(y)), amiből pedig φ(x)=igaz következik. (Ez összehasonlítható a fenti harmadik állítással.)
3. Tegyük fel, hogy létezik egy p kombinátor (implikátor), amelyre φ(pxy) = not(φ(x)) or φ(y). Ekkor egy tetszőleges x-re legyen y=θ(Cpx), mert akkor y = Cpxy = pyx, amiből φ(y) = φ(pxy) = not(φ(y)) or φ(x), ami csak akkor teljesülhet, haφ(y)=φ(x)=igaz. (Ez összehasonlítható a fenti 1. állítással.)
4. A fenti 2. állítás nem vezet nyilvánvaló ellentmondáshoz, de a teljesség kedvéért annak is találjuk meg a megfelelőjét: y=θ(px), ekkor y = pxy, ami összehasonlítható a 'ha x igaz, akkor ez az állítás igaz'-zal.
Ha φ egy 'tulajdonság', vagyis egy számhoz logikai értéket rendel (ilyen például a Z (is-zero), vagy a π (is-prime)), akkor jó lenne ha lenne hozzá egy olyan logikai kombinátor, ami megmondja, hogy melyik a legkisebb nemnegatív egész szám, amelyre a tulajdonság igaz. (Ha φ semelyik számra nem teljesül, akkor a 'minimalizáló' kimenete bármi lehet, csak szám nem.)
Legyen az A segédfüggvény olyan, amelyre:
Aφn = (φn)n(Aφ(sn))
ez azt fejezi ki, hogy az n számtól kezdve melyik a minimális szám, amire teljesül a φ tulajdonság.
ekkor a μ minimalizátor legyen a CA0, ugyanis μφ = CA0φ = Aφ0 ami nem más, mint a minimális nemnegatív egész szám, amire teljesül a φ tulajdonság.
Kieg: a fenti A-ra példa:
A = θ(B(S(BSW))(C(BC(BB))s)), ekkor A = B(S(BSW))(C(BC(BB))s)A = S(BSW)(C(BC(BB))sA)φ Aφ = S(BSW)(C(BC(BB))sA)φ = BSWφ(C(BC(BB))sAφ) = S(Wφ)(B(Aφ)s) Aφn = S(Wφ)(B(Aφ)s)n = Wφn(B(Aφ)sn) = φnn(Aφ(sn))
Ugyebár egész számokat természetes számokból álló párokkal lehet reprezentálni, ehhez kellene nekünk három művelet, az egyik két számból párt képez, a másik kettő egy párból kiveszi az egyes elemeket. Próbáljuk meg így:
Vnm = az (n,m) párt reprezentálja ¹ = Tt a pár első elemét adja vissza: Tt(Vnm) = Vnmt = tnm = n ² = Tf a pár második elemét adja vissza: Tf(Vnm) = Vnmf = fnm = m
Ekkor ilyesmiket tudunk alkotni:
0 = 00 nulla Żx = =(¹x)(²x) nulla-vizsgálat Ṗx = >(¹x)(²x) pozitív Ńx = >(²x)(¹x) negatív Ṁx = V(²x)(¹x) ellentett x = V(s(¹x))(²x) következő (+1) ṕx = V(¹x)(s(²x)) előző (-1) ṗx = -(¹x)(²x) szám "pozitív értéke": min(x,0)
Bocsánat, kis változás: legyen most 's' a növelő (successor) és 'Z' az is-zero művelet, hogy ne ütközzünk az 'n' negáló logikai művelettel és a 'z' változószimbólummal.
Adott esetben akár nemnegatív egész számokat is ábrázolhatunk logikai kombinátorokkal (tudományos néven nevezve elemeinket):
0 = I (n+1) = Vfn
Ebből levezethető, hogy Tf(n+1) = (n+1)f = Vfnf = ffn = n Valamint Tt0 = 0t = t, Tt(Vfn) = Vfnt = tfn = f
Akkor a Vf-t elnevezhetjük növelőnek (jele legyen n), a Tf-t csökkentőnek (jele legyen p), a Tt-pedig if-zero-nak (jele legyen z).
Ezekből akár összeadást is levezethetnénk, ha meg tudnánk oldani A-ra az alábbit: Axy = zyx(A(nx)(py)) (vagyis ha y nulla, akkor az összeg x, egyébként rekurzívan x+1 és y-1 összege.
Ezt az A-t jelölhetné mondjuk a + jel, és máris felírhatnánk egy újabb megoldandó egyenletet: Axy = zy0(+(Ax(py))x) (vagyis ha y nulla, akkor a szorzat nulla, egyébként az x(y-1) szorzat és x összege)
Mivel a lejtőn nincs megállás, jönne a hatványozás (az előbbi egyenlet A megoldását * jelöli): Axy = zy1(*(Ax(py))x) (vagyis ha y nulla, akkor a hatvány egy, egyébként az x^(y-1) és x szorzata)
Talán nem lenne logikátlan, ha K-t elneveznénk igaznak (t=true), a KI-t meg hamisnak (f=false), és logikai műveleteket definiálnák, figyelembe vége az alábbi szabályt:
tab = a fab = b
Ennek alapján ilyesmiket találhatunk (nem, és, vagy, egyenlő, különbözik, következik).
n = Vf, nzw = Vftz = zft = not z a = Rf, azw = Rfzw = zwf = z and w o = Tt, ozw = Ttzw = ztw = z or w e = CSn, ezw = CSnzw = Sznw = zw(nw) = z equal w x = Ben, xzw = Benzw = e(nz)w = (not z) equal w = z xor w i = Rt, izw = Rtzw = zwt = z -> w
Még nem bizonyítottuk, hogy az S és K elemekből minden képlettel leírható elem felépíthető [képlet alatt a Hxyz=xyzy vagy Lxy=x(My) -szerű formulát értve], de van egy olyan elem, amiből meg S és K állítható elő, de ennek az elemnek nincs olyan képlete, amiben ne lenne literál.
Legyen Y olyan, hogy Yx=xSK (ilyen például az Y=VSK, mivel xSK=VSKx) Ekkor Y2=YY=YSK=SSKK=SK(KK) Y3=YY2=SK(KK)SK=KS(KKS)K=SK Y4=YY3=SKSK=KK(SK)=K Y5=YY4=KSK=S
És ha van S meg K, akkor I:=SKK ugyanis SKKx=Kx(Kx)=x M:=SII, ui SIIx=Ix(Ix)=xx W:=SS(KI), ui SS(KI)xy=Sx(KIx)y=SxIy=xyy B:=S(KS)K, ui S(KS)Kxyz=KSx(Kx)yz=S(Kx)yz=Kxz(yz)=x(yz) T:=S(K(SI))K, ui S(K(SI))Kxy=K(SI)x(Kx)y=SI(Kx)y=Iy(Kxy)=yx
és ebből R:=BBT, ui BBTxyz=B(Tx)yz=Tx(yz)=yzx C:=RRR, ui RRRxyz=RxRyz=Ryxz=xzy
Itt kimaradt annak a bizonyítása, hogy Tx≠Ky. Indirekten tegyük fel, hogy van olyan x és y, amire Tx=Ky, amiből TxI=KyI következik, átrendezve x=y. Innentől lásd a korábbi bizonyítást, hogy Tx≠Kx, tehát az indirekt feltevés hamis.
V5IKmtM = MIKmt= IIKmt = Kmt = m V5IKmtT = TIKmt= KImt = t
Valamint a (140)-hez egy változat: Megoldandó x,y-ra az x=axy, y=bxy egyenletrendszer. Oldjuk meg A-ra az Auvw=w(Auvu)(Auvv) egyenletet, és legyen x=Aaba és y=Aabb. Behelyettesítve: Aaba=a(Aaba)(Aabb), Aabb=b(Aaba)(Aabb)
Lehetséges-e olyan A elemet találni, amelyre AR=C és AC=R? Vagy általánosan ArcR=r és ArcC=c (adott r és c elemekhez). Vagy olyat, amire AtmT=t és AtmM=m?
Hát az univerzális megoldás egy olyan u elem lenne, melyre (uabαβ)a=α és (uabαβ)b=β. Első blikkre azt mondanám, hogy ez a halting problem-mel összehasonlítható feladata, vagyis kétlem, hogy létezne ilyen u elem.
A konkrét kérdésekre ad-hoc módszerekkel találhatunk megoldást, ehhez vezessük be a V6 elemet: V6abcdef = fabcde Ekkor V6IKIlmL = LIKIlm = I(KK)Ilm = KKIlm = Klm = l V6IKIlmM = MIKIlm = IIKIlm = KIlm = m
Másik példa: V6K(KI)(KI)rcR = RK(KI)(KI)rc = (KI)(KI)Krc = Krc = r V6K(KI)(KI)rcC = CK(KI)(KI)rc = K(KI)(KI)rc = KIrc = c
Tehát T és K injektívek, és invertálhatók is (pl. M(Kx)=x, TI(Tx)=x); még azt is tegyük hozzá, hogy értékkészletük különbözik (kivéve azt az elfajult esetet, ha az egész halmazban csak egy elem van).
Indirekt bizonyítás: Tf. Tx=Kx valamely x-re, ekkor Tx(KI)=Kx(KI) is igaz, vagyis KIx=x, tehát I=x.
Szóval TI=KI-nél tartunk, amiből következik, hogy TIK=KIK azaz KI=I. Erről a (90)-ben láttuk be, hogy nem igaz, tehát az indirekt feltevés hamis. Tehát Tx≠Kx
Hasonlóan kimutatható az is, hogy Tx≠K, Tx≠T, Kx≠K, Kx≠T.
Vannak szurjektív elemek is, ezt egy kis kerülővel mutatjuk ki, nevezetesen olyan elemeket keresünk, amelyek "egyetértőek".
Azt mondjuk, hogy fegyetértő, ha minden g-re létezik x, hogy fx=gx. (Mondjuk úgy, hogy f és gegyetért az x-en.)
Egyetértő például az M, ugyanis Mg=gg. Szintén egyetértő az I, ugyanis I(θy)=y(θy)
Továbbá, ha valamely l és r elemekre l(r(x))≡x (lásd az előbb említett inverz-elemeket), akkor l is egyetértő: tetszőleges g-re: l és g egyetért x=r(θ(Bgr)) elemen: l(x) = l(r(θ(Bgr))) = θ(Bgr) = Bgr(θ(Bgr)) = g(r(θ(Bgr))) = g(x)
És miért is szurjektívek az egyetértő elemek? Legyen e egy tetszőleges egyetértő elem (pl. I, M, TI, VII, VKK). Ekkor tetszőleges x-re legyen Kx = Kx, akkor létezik y, amelyre ey = Kxy Itt még azt vegyük észre, Kxy = Kxy = x, tehát ey = x, vagyis e minden x-et előállít, tehát szurjektív.
Inverz-elemekről még nem volt szó, pedig bizonyos elemeknek bizonyos mértékig van inverze.
Először gyorsan definiáljunk két további elemet:
Cxyz = xzy (ez nem új, csak ismétlés) Rxyz = yzx (ez sem új) Vxyz = zxy (ez az egyik új) Fxyz = zyx (ez a másik új)
Szóval az inverzek: B(TI)Kx = TI(Kx) = KxI = x B(TI)Tx = TI(Tx) = TxI = Ix = x B(VII)Rx = VII(Rx) = RxII = IIx = x B(VII)Fx = VII(Fx) = FxII = IIx = x B(VKK)Vx = VKK(Vx) = VxKK = KxK = x
Ebből azt vonhatjuk le, hogy a T, K, R, F és V műveletek injektívek, vagyis x≠y esetén Tx≠Ty (Kx≠Ky, stb). [Itt X művelet alatt az X-szel való balról szorzást értek.]
És ha egy olyat kellene megoldani, hogy x=ay, y=bx [a és b adott, keressük x-et és y-t]?
Első gondolat: x=ay=a(bx)=Babx, tehát x=θ(Bab), y=b(θ(Bab))
Második gondolat: találjunk A-t, hogy minden u,v-re: Auv=u(Avu), ekkor x=Aab, y=Aba megoldása az eredetinek.
(A gyakorlás kedvéért kiszámolhatjuk az A-t, de az igazi az lenne, ha lenne egy általános módszer az ilyen egyenletekhez, amit akár le is lehetne programozni.) Auv=u(Avu)=SI(Av)u=B(SI)Avu=C(B(SI)A)uv=BC(B(SI))Auv, tehát A=θ(BC(B(SI))) egy megoldás.
Vagy akár így: uax = x(aa) = T(aa)x = LTax, tehát u=LT, A=LT(LT) is megoldás.
További lehetőség, hogy veszünk egy θ tulajdonságú elemet (amilyen a BML vagy a SLL), és azt használjuk: Ax = xA = TAx, ehhez elég, ha A = TA, amit elérhetünk, ha A = θT
Vagy pl megoldandó: Ax = A = KAx, ehhez elég, ha A = KA, amit elérhetünk, ha A = θK
Mondjuk meg akarjuk oldani az Ax = xA egyenletet A-ra, vagyis keresünk egy olyan A-t, hogy minden x-re Ax = xA
Az első ötletünk az lehet, hogy keresünk egy olyan u-t, amire uax = x(aa) azonosan igaz lenne (tehát minden a-ra és x-re). Ez azért lenne jó, mert akkor speciálisan uux = x(uu) is teljesülne, tehát A=uu lenne egy megoldása az eredetinek.
Tehát uax = x(aa) = Lxa = CLax, tehát u=CL, A=uu=CL(CL) egy megoldás.
Persze még sok mást is lehetne, pl. T elem legyen olyan, hogy minden x,y-ra: Txy = yx; erre egy lehetőség a CI, ugyanis CIxy = Iyx = yx
Valamint S legyen olyan tulajdonságú, hogy Sxyz = xz(yz) Ekkor (SLL)x = Lx(Lx), tehát SLL is θ-tulajdonságú, vagyis találhatunk vele tetszőleges elemhez fixpontot.
Ez a S azért is jó, mert felhasználva őt és két korábbi elemet egyfajta szimmetriát láthatunk az alábbi esetekben: Babx = a(bx) Cabx = axb = (ax)b Sabx = ax(bx) = (ax)(bx)
