2004-09-20 után

A logika általános tárgyalásmódja (unified logic)

A 0-adrendű (Boole) kiértékelés és az 1-rendű kiértékelés kapcsolatáról.

A 0-adrendű logika ABC-jében szereplő szimbólumok:
 a logikai összekötőjelek (, , , )
az ítéletváltozók megszámlálható halmaza (p, q, …)
(más elnevezés szerint logikai változók, állításváltozók vagy prímformulák) .

0-adrendű formulák:		a formula jelölésére A, X..-t (nagybetűket) használunk.
1. p ítéletváltozó jól formált formula (prímformula) 
2. Ha X,Y formulák akkor X, (X), (X)b(Y) jff., ahol b az (, , ) bármelyike. A zárójel elhagyható, ha b hatásköre a teljes kifejezés.
Megjegyzés: A prímformulákból kiindulva logikai összekötőjelek ismert módon való felhasználásával kapott formulákat kapjuk.
Részformula, egy logikai művelet bal- és jobboldali közvetlen részformulái XbY
1.	Itéletváltozónak nincs közvetlen részformulája.
2.	X közvetlen részformulája az X.
3.	XbY alakú formulák közvetlen részformulái X és Y.

Formula bonylultsága: d(F) lényegében a logikai összekötőjelek száma F-ben.
1.	d(p)=0
2.	d(X)= d(X)+1
3.	d(XbY)= d(X)+d(Y)+1

A 0-adrendű (Boole) kiértékelés -igazságértékelés az ítéletkalkulus szemantikája, megadja egy formula közvetlen részformuláira azokat a feltételeket, amelyek biztosítják a formula igaz (vagy hamis) értékét. Végül ez rekurzíve odavezet, hogy egy n-változós formulában szereplő ítéletváltozókra (amelyek egymástól függetlenül veszik fel értéküket) megkapjuk az összes olyan i,h értékekből álló n-eseket, amelyekre a formula helyettesítési értéke igaz (vagy hamis) a kiindulásnak megfelelően. Más szóval a formula igazságtáblájának igaz (vagy hamis) sorait kapjuk meg.
0-adrendű igaz halmaz  Legyen  egy Boole értékelés és legyen S az összes olyan formulák halmaza, amelyek igazak -re. Azonnal látható, a Boole értékelés definíciójából, hogy az S halmaz rendelkezik a következő tulajdonságokkal (minden S,Y-ra nézve).
A1 : Az (X, X) párból pontosan az egyik tartozik S-hez. Más szóval XS akor és csak akkor ha XS.
A2 : (XY) eleme S-nek akor és csak akkor X is és Y is eleme S-nek.
A3 : (XY) eleme S-nek akor és csak akkor X eleme S-nek vagy Y eleme S-nek.
A4 : (XY) eleme S-nek akor és csak akkor X nem eleme S-nek vagy Y eleme S-nek.
Konzisztenciafogalom 1. S konzisztens, ha minden véges részhalmaza kielégíthető. S inkonzisztens, ha van véges kielégíthetetlen részhalmaza. Konzisztens formulahalmaz bármely részhalmaza is konzisztens. Inkonzisztens formulahalmaz bármely kiterjesztése is inkonzisztens. A konzisztencia teljesíti az alábbi feltételeket.
C0 komplemens párt tartalmazó formulahalmaz nem konzisztens.
C1 Ha {S,} konzisztens, akkor {S, 1, 2} konzisztens.
C2 Ha {S,} konzisztens, akkor {S, 1} és {S, 2} legalább egyike konzisztens.
Illetve
I0 Inkonzisztens minden formulahalmaz amely tartalmaz komplemens párt.
I1 Ha {S, 1, 2} inkonzisztens, akkor {S,} is az.
I2 Ha {S, 1} és {S, 2} mindkettő inkonzisztens, akkor {S,} is az.

Az 1-rendű logika ABC-jében szereplő szimbólumok a megszokott módtól eltérően megszámlálhatóan végtelen indivíduumváltozó, indivíduum paraméter, predikátumszimbólum (minden n argumentumszámra), logikai összekötőjelek és kvantorok. 

1-rendű formulák:
1. Atomi formulák: P(c1,c2,...,cn) , ahol c1,c2,...,cn indivíduum szimbólumok (változók vagy paraméterek)
2. Formulák: Az atomi formulákból kiindulva logikai összekötőjelek ismert módon való felhasználásával kapott formulák. Valamint a kvantált formulák xA , xA.
Tiszta formulák: Paramétermentes formulák.
Formula bonylultsága: d(F) - (a formulában szereplő logikai összekötőjelek és kvantorok száma.)
1. Az atomi formula bonyolultsága 0. 
2. d(A)=d(A)+1
 d(AB)=d(AB)=d(AB)=d(A)+d(B)+1
3. d(xA)=d(xA)=d(A)+1

Az 1-rendű értékelés, -L értékelés a predikátumkalkulus szemantikája, megadja egy formula közvetlen részformuláira azokat a feltételeket, amelyek biztosítják a formula igaz (vagy hamis) értékét egy adott interpretáló struktúrában. Végül ez rekurzíve odavezet, hogy egy n-változós formulában szereplő szabad indivíduumváltozókra (amelyek egymástól függetlenül veszik fel értéküket) megkapjuk az összes olyan az univerzum elemekből álló n-eseket, amelyekre a formula helyettesítési értéke igaz (vagy hamis) a kiindulásnak megfelelően. Más szóval a formula értéktáblájának igaz (vagy hamis) sorait kapjuk meg és mivel a táblázatban szerepelnek a formula prímkomponensei (logikai összekötőjelekkel összekapcsolt felbonthatatlan részformulái) ezekben a sorokban megjelennek a formula alapatomjaihoz és kvantált formuláihoz (lényegében az 1. rendű prímkomponensekhez) tartozó igazságértékek.

1-rendű értékelések és modellek
Legyen U egy nem üres halmaz, univerzum,indivíduumhalmaz, értelmezési tartomány értelemben.
U formulák FU olyan elsőrendű formula, amelyben a paraméterek helyett már U-beli elemek állnak. A tiszta formulák is U-formulák. 
Jelölje EU az összes zárt U-formulák halmazát. Az EU 1-rendű v értékelésén igazságérték hozzárendelését értjük az EU minden eleméhez úgy hogy minden AEU ra és minden x változóra a következő teljesül.
F1. v az EU -nak Boole értékelése (csak a logikai összekötőjelekre vonatkozó értékelést kellett alkalmazni)
F2. (a) xA igaz v -re, ha minden kU-ra A(x/k) igaz v-re. (b) xA igaz v -re, ha legalább egy kU-ra A(x/k) igaz v-re.
1-rendű igaz halmaz  U-ra nézve az SEU amelyre fennállnak a 0-rendben elmondottak és még az, hogy (a)  xAU akkor és csak akkor ha minden kU-ra A(x/k)S.
(b) xAU akkor és csak akkor ha van olyan kU, hogy A(x/k)S.

Atomi értékelés. Az EU atomi értékelésén az EU -beli összes atomi elem alapelőfordulásaihoz igazságértékekek hozzárendelését értjük.
Interpretáció. E-nek egy I interpretációja egy U univerzumon egy f függvényt jelent, amely minden n argumentumos predikátumhoz hozzárendel egy az U-n értelmezett n argumentumos relációt. 
Másik megfogalmazásban : Az alapatomokhoz  az f értéket rendel. Alapatomok kiértékelése.

Mivel lényegében nincs különbség a két nézőpont között, mindig azt a meghatározást használjuk, amelyik megfelelőbb.
Eddig az E -vel a predkátumlogika összes predikátumaiból felépíthető formulák halmazát jelöltük. Reálisan E inkább a predikátumok egy véges részhalmazából felépíthető összes formulák halmazát jelenti. Ennek megfelelően csak a formulákban előforduló predikátumszimbólumokat tekintjük EU atomi értékelésénél és 1-rendű értékelésénél valamint E -nek U feletti interpretációjánál.
Az S modellje az olyan interpretáció, amelyben S minden eleme igaz.
Érvényesség és kilégíthetetlenség. Egy A tiszta formula érvényes (logikailag igaz), ha igaz minden interpretációban (minden univerzumon). Vagy ami ugyanaz, hogy  igaz  EU minden elsőrendű értékelésén 
Az A formula (elsőrendben) kielégíthető, ha igaz legalább egy interpretációban, legalább egy univerzumon vagy ami ugyanaz ha igaz legalább egy U univerzumon, van legalább egy 1-rendű értékelés amelyre A igaz.
Lehet szó egy bizonyos számosságú U univerzumon értelmezett érvényességről és kielégíthetőségről. Mint ismeretes a Löwenheim Skolem tétel a megszámlálható univerzumon való kielégíthetőségről szól.
Paraméteres mondatok.  Legyen A(a1,a2,...,an) egy az (a1,a2,...,an) paramétereket tartalmazó mondat. Az A(k1,k2,...,kn) egy olyan EU -beli mondat, ahol a paramétereket U-beli elemekkel helyettesítettük. A kielégíthetőség, érvényesség definíciója ismert és ez a következőkön alapul. A(a1,a2,...,an) kielégíthető egy I interpretációban, ha van legalább egy < k1,k2,...,kn > n-es az U elemeiből, hogy A(k1,k2,...,kn) igaz az I-ben. A(a1,a2,...,an) érvényes egy I interpretációban, ha minden  < k1,k2,...,kn > n-esre az U elemeiből, A(k1,k2,...,kn) igaz az I-ben. Legyen S egy paraméteres mondathalmaz és  az S paramétereinek az U elemeihez való hozzárendelése. A a behelyettesítés eredménye, ahol ai helyébe (ai) kerül. S kielégíthető, ha van az S paramétereire olyan   hozzárendelő leképezés U-ba, hogy minden AS-re A igaz I-ben.

Boole értékelések és 1-rendű értékelések
 Az állítást leíró legegyszerűbb formula a  0-adrendű logikában az ítéletváltozó, az 1-rendű logikában az atomi formulák alappédányai P(a1,a2,...,an) és a zárt kvantált formulák (xA, xA) ezeket Boole atomnak is nevezik. Legyen az univerzum a paraméterek halmaza V. Az EV mondathalmaz Boole kiértékelése azt jelenti, hogy az EV mondathalmaz Boole atomjaihoz egymástól függetlenül rendelünk igazságértékeket. Az EV mondathalmaz 1-rendű kiértékelése az atomi formulákhoz az interpretáló struktúrabeli reláció megfelelőjüket rendeli, amelytől azután függ a kvantált formulák értéke. Ennek megfelelően egy 1-rendű kiértékelés egyben 0-adrendű (Boole) kiértékelés de fordítva nem. Ez azt jelenti, hogy az ítéletkalkulusbeli Boole értékelés átvihető a predikátumkalkulusra mivel a Boole atomok egy igazságértékelése az EV egy meghatározott Boole értékelése.
Például a 0-adrendben bebizonyított kompaktsági tétel ugyanúgy bizonyítható 1.  rendben is. Tehát, ha S egy végtelen részhalmaza EV-nek és S minden véges részhalmaza  0-adrendben kielégíthető, akkor S is az. A bizonyításban ítéletváltozó helyett Boole atomot használunk. A kompaktsági tétel elsőrendben is bebizonyítható, vagyis ha S egy végtelen részhalmaza EV-nek és S minden véges részhalmaza  1-rendben kielégíthető, akkor S is az.
Ugyanígy meg kell különböztetni az érvényes (logikailag igaz) mondatot a tautológiától. Érvényes egy mondat, ha igaz minden 1-rendű kiértékelésre és tautológia egy mondat, ha igaz minden  0-adrendű (Boole) kiértékelésre (még akkor is, ha az nem elsőrendű értékelés).
xP(x)xQ(x)xP(x) logikailag igaz és tautológia is pqp
x(P(x)Q(x))xP(x) logikailag igaz de nem tautológia rp

Az egységes elv
A szisztematikus tabló módszerrel és az erre épülő Hintikka lemmával a Löwenheim Skolem tételt sikerült elemi úton igazolni. Három tétel fontos lesz a következőkben.
5.Tétel: Bármely S-nek van teljes tablója.
Lemma. Ha S tiszta formulahalmaznak van zárt tablója, akkor S-nek van olyan véges részhalmaza, amely kielégíthetetlen. Vagy ami ugyanaz, ha az S minden részhalmaza kielégíthető (elsőrendben), akkor S-nek a tablója nem lehet zárt.
6. Tétel (kompaktság): Ha egy S tiszta formulahalmaz bármely véges részhalma kialégíthető, akkor S kielégíthető megszámlálható univerzumon.
7. Tétel: Ha S-nek nincs zárt tablója, akkor S kielégíthető megszámlálható univerzumon.

A1. Analitikus konzisztencia
Kialakítunk egy véges jellegű analitikus konzisztencia fogalmat, amely keretet ad a különböző kalkulusok konzisztencia fogalmainak és ezen keresztül biztosítjuk, hogy az elért eredmények általános érvényűek legyenek. Legyen  véges jellegű tulajdonság. Azt mondjuk, hogy az S formulahalmaz -konzisztens, ha S rendelkezik a  tulajdonsággal és  -inkonzisztens, ha nem rendelkezik a  tulajdonsággal.
Az analitikus konzisztencia definíciója: minden -konzisztens S formulahalmaz rendelkezik a következő tulajdonságokkal.
A0 : S nem tartalmaz komplemens párt (atom és negáltja)
A1 : Ha S, akkor {S,1} és {S,2} (következésképp {S,1,2} is) -konzisztens.
A2 : Ha S, akkor vagy {S,1} -konzisztens vagy{S,2} -konzisztens.
A3 : Ha S, akkor {S,(a)} is -konzisztens.
A4 : Ha S, akkor {S,(a)} is -konzisztens, feltéve, hogy az a paraméter nem fordul elő S.ben.
Sokszor hasznos az A0-A4 -el ekvivalens feltételek használata a -inkonzisztenciára vonatkozóan:
'A0 : Bármely S formulahalmaz amely tartalmaz komplemens párt (atom és negáltja) -inkonzisztens
'A1 : Ha {S,,1} -inkonzisztens vagy {S,,2} -inkonzisztens, akkor {S,} is -inkonzisztens.
'A2 : Ha {S,1} és {S,2} -inkonzisztens, akkor {S,} is -inkonzisztens.
'A3 : Ha {S,,(a)} -inkonzisztens, akkor {S,} is -inkonzisztens.
'A4 : Ha {S,(a)} -inkonzisztens, és, ha az a paraméter nem fordul elő {S,}-ban, akkor {S,} is -inkonzisztens.
Példák analitikus -konzisztenciára.
- A kielégíthetőség.
- Az S formulahalmaznak nem létezik zárt analitikus tablója.
Jelöljön  bármilyen analitikus konzisztencia tulajdonaságot. Tegyük fel, hogy S -konzisztens és hogy S egy véges T tablójának van egy olyan  ága, hogy az S{ formulái} -konzisztens ( az S-el együtt  konzisztens). Ha ezt az ágat kiterjesztjük az A,C,D szabályok alkalmazásával egy ' ággá, akkor ez az S-el együtt -konzisztens lesz az A1, A3, A4 feltételek miatt. Ha a B szabályt alkalmazzuk, akkor a kapott két ág 1,2 közül legalább az egyik az S-el együtt -konzisztens. Ebből következik, hogy a ha S -konzisztens, akkor a tablóépítés bármely stádiumában kell hogy legyen legalább egy  ág, amely az S-el együtt -konzisztens. Ezekből következik az
1. Lemma. Bármely -konzisztens S tiszta formulahalmaznak nincs lezárható tablója.
Megjegyzés. A 6. tétel előtti lemma az 1. lemma speciális esete, ahol a  -konzisztencia megfelelője az a tulajdonság, hogy minden véges részhalmaz kielégíthető. Ez a lemma és a 7. tétel bizonyítja az I. tételt
I tétel. (Egységes elv - egyik). Bármely tiszta S formulahalmazra, ha S -konzisztens, akkor S kielégíthető megszámlálható univerzumon. 
Definíció. Egy X mondatot -bizonyíthatónak nevezünk, ha {X} -inkonzisztens.
Következmény. Ha X érvényes, akkor X -bizonyítható.

A2. További eredmények az analitikus konzisztenciával kapcsolatban
Az I tétel bizonyításánál felhasználtuk az analitikus tablót, pedig az I tétel nem hivatkozik a tablóra. De az is igaz, hogy a 6. és a 7. tétel speciális esete az I tételnek, ha -konzisztenciaként a minden véges részhalmaza kielégíthető tulajdonságot tekintjük. Ekkor az elsőrendű logika kompaktsági tétele, a Löwenheim Skolem tétel és a tabló teljességi tétel és még több alapvető eredmény speciális esete az egységes elvnek.
Más úton bizonyítjuk be az I. tételt. Beágyazzuk a -konzisztens S formulahalmazt egy  Hintikka halmazba. Mint látni fogjuk ez a  halmaz az S szisztematikus tablójának a legbaloldalibb végtelen ága. A konstrukció ismert. S elemeit az X1,X2,...,Xn... sorozatba rendezzük. X1 a  első eleme, ez a konstrukció első állapota. Tegyük fel, hogy az n-edik állapottal kész vagyunk, ez egy véges n sorzat. Tekintsük a sorozat n-edik elemét Y-t. Ha ez egy , , ,  típusú formula, akkor a n sorzat végére írjuk rendre az Y direkt tablója szerinti formulát vagy formulákat és Xn+1.-et.   Tehát n+1= n, 1, 2 ,Xn+1 vagy .n+1=n, 1 ,Xn+1 vagy  n+1=n, 2, Xn+1 vagy n+1=n, (a), Xn+1 vagy n+1=n, (a), Xn+1. n+1-nek legalább n+1 eleme van és a -konzisztencia megfelelő feltétele miatt -konzisztens az S-el. Mivel minden n -konzisztens az S-el n nem tartalmazhat komplemens párt. Ezért és azért, mert a Hintikka lemma miatt  megszámlálhatóan kielégíthető és az S minden eleme megjelenik legalább egy helyen -ban. Ez bizonyítja az I. tételt. 
Léteznek más módszerek is az I. tétel bizonyítására, ahol elkerülhetjük a Hintikka halmaz konstrukcióját.

A3. Analitikus konzisztencia tulajdonság véges halmazokra
Ugyanúgy az A0 - A4  tulajdonságoknak kell teljesülni az S összes részhalmazaira, de -nak nem kell véges jelegűnek lennie.
Diszjunktív érvényesség. S diszjunktíve érvényes, ha minden I interpretációban S-nek legalább egy eleme igaz. S diszjunktíve érvényes, akkor és csak akkor ha S (az S elemei negáltjának a halmaza) kielégíthetetlen.

Az elsőrendű logika alaptétele
Ez a tétel azt mondja ki, hogy minden érvényes formulához hozzárendelhető egy elsőrendű formula, amely tautológia. E tétel szépsége, hogy a logika semmilyen különleges formális rendszerére nincs szükség a belátásához.Elegendő kizárólag az elsőrendű kielégíthetőség és a Boole kielégíthetőség alapvető kapcsolatát felhasználni. Ezért nevezik ezt a tételt az elsőrendű logika alaptételének.
R1. Reguláris halmazok.
Reguláris formulák a (a) és a (a) formulák. A (a)-t C típusú és a (a)-t D típusú reguláris formulának nevezzük.
1. Lemma. Legyen S egy kielégíthető mondathalmaz. Ekkor
(a) Bármely paraméterre az {S, (a)} kielégíthető.
(b) Bármely olyan a paraméterre, amely nem fordul elő sem S-ben, sem -ban az {S, (a)} kielégíthető.
Bizonyítás. Mivel  (a) érvényes formula ezért (a) bizonyítása kész.
Tegyük fel, hogy {S, (a)} kielégíthetetlen. Ekkor kielégíthetetlen az {S, } és az {S, (a)} formulahalmaz is. mivel az a paraméter nem fordul elő {S, }-ban, ezért {S, (a)} csak ugy lehet kielégíthetetlen, ha {S, } is kielégíthetetlen. Viszont az {S, } és az {S, } csak úgy lehet kielégíthetetlen, ha az S kielégíthetetlen a feltétellel ellentétben.
Megjegyzés. Egy másik bizonyítást is adunk az 1. Lemma (b) részére. Tegyük fel, hogy S kielégíthető. Legyen I egy olyan interpretáció az S paramétereire és predikátumszimbólumaira, amely kielégíti S-et. Terjesszük ki I-t az {S,} bármely I* interpretációjára (a  azon paramétereire és predikátumszimbólumaira, amelyek a S.ben nem fordulnak elő). I*-ban a -nak van valamilyen igazságértéke, de (a)-nak nincs, mivel az a paraméter nem szerepelt korábban. Legyen  hamis az I*-ban, akkor az a paraméter bármely értéket felvehet ahhoz, hogy (a) igaz legyen. Legyen  igaz az I*-ban, akkor bizonyos kU -kra (a) igaz. Helyettesítsünk egy ilyen k értéket az a helyébe és így (a) igaz lesz. Ezzel lényegében kiterjesztjük az I*-ot I**-ggá, amelyben {S, (a)} igaz. Ez viszont azt jelenti, hogy {S, (a)} kielégíthető.
Jelölje Q a , vagy a  valamelyikét és Q(a) a (a), vagy a (a) valamelyikét.
Reguláris sorozatnak nevezünk egy véges (esetleg üres), < Q1 Q1(a), Q2 Q2(a),..., Qn Qn(a)> sorozatot, ahol minden elem reguláris és minden i<n-re, ha Qi+1 -formula az ai+1 paraméter nem fordul elő a < Q1 Q1(a), Q2 Q2(a),..., Qi Qi(a)>   sorozatban.
Reguláris halmaznak nevezünk reguláris formulák egy olyan véges halmazát, amelyet reguláris sorozatba lehet rendezni. Reguláris halmaz tehát egy a következő szabályok szerint előálló véges halmaz.
R0: Az üres halmaz reguláris.
R1: Ha R reguláris, akkor az {R,(a)} is reguláris.
R2: Ha R reguláris, akkor az {R,(a)} is reguláris, amennyiben az a nem fordul elő sem R-ben sem -ban (az a kritikus paraméter).
A fenti szabályok miatt R kielégíthető. Az 1. lemma biztosítja, hogy ha S egy kielégíthető, tiszta mondathalmaz, akkor SR is kielégíthető. 
1. Tétel. Ha S kielégíthető és ha S-ben nem fordul elő R-nek egyetlen kritikus paramétere sem, akkor kielégíthető SR is.
Jelölje R^ az R elemeinek konjunkcióját.
Következmény. Ha R^X érvényes és ha X-ben nem fordul elő R-nek egyetlen kritikus paramétere sem, akkor X érvényes. Speciálisan, ha X tiszta mondat, akkor ha R^X érvényes akkor X is érvényes.
Bizonyítás. Mivel R^X érvényes ezért {R,X} kielégíthetetlen. Mivel R kritikus paraméterei nem szerepelnek X-ben a X a kielégíthetetlen (az 1. tétel miatt), vagyis X érvényes.
Nevezzük az S formulahalmazt helyes/jó/ép-nek, ha az S összes predikátumának, egy adott U univerzum feletti bármely interpretációja esetén van az S paramétereinek olyan kiértékelése, hogy az S igaz. A formulahalmaz helyessége a kielégíthetőség és az érvényesség között helyezkedik el. Az 1 tétel következménye, hogy minden R reguláris halmaz kielégíthető. Azonban egy reguláris halmaz nemcsak kielégíthető, hanem helyes is. Ugyanis Az R összes predikátumának és nem kritikus paramétereinek összes interpretációjához létezik a kritikus paraméterek olyan kiértékelése, hogy R minden eleme igaz.
Kvázi reguláris sorozatnak nevezünk egy véges  < Q1 Q1(a), Q2 Q2(a),..., Qn Qn(a)> sorozatot, ahol minden elem reguláris és minden i<n-re, ha Qi+1 -formula az ai+1 paraméter vagy nem fordul elő a < Q1 Q1(a), Q2 Q2(a),..., Qi Qi(a)>   sorozatban vagy nem kritikus paraméterként fordul elő a megelőzőkben, de nincs olyan kritikus paraméter a megelőző termekben amelyek a Qi+1-ben előfordulnának.
2. Lemma. Tegyük fel, hogy R reguláris és hogy a nem fordul elő -ban és nem fordul elő kritikusan R-ben (de nem kritikusan előfordulhat) és R-nek egyetlen kritikus paramétere sem szerepel -ban. Ekkor  az {R,(a)} reguláris.
Bizonyítás. Azt kell belátni, hogy a fenti feltételek teljesülése esetén hozzá lehet venni (a)-t az R-hez. Legyen R1 az R D típusú elemeinek halmaza reguláris sorozatba rendezve 11(a1), 22(a2),..., nn(an) és legyen R2 az R C típusú elemeinek halmaza. A feltevés szerint az a1, ..., an közül egyik sem szerepel -ban és nem egyeznek meg az a-val sem ezért nemfordulnak elő a (a)-ban sem. Ezért a <(a), 11(a1), 22(a2),..., nn(an)> sorozat reguláris. Vagyis R1(a) reguláris halmaz. De akkor  R2R1(a) is reguláris halmaz. Ami azt jelenti, hogy {R,(a)} reguláris halmaz.
3. Lemma. Bármely kvázi reguláris sorozat átrendezhető reguláris sorozattá. Más szóval bármely kvázi reguláris sorozat elemei reguláris halmazt alkotnak.

2. Az alaptétel
Az alaptétel egy gyenge formája:
2. Tétel. Minden X érvényes tiszta  mondatot Boole értelemben (0-adrendben) implikál valamely R reguláris halmaz. Más szóval bármely X érvényes tiszta  mondathoz létezik olyan R reguláris halmaz, hogy R^X tautológia.
Az 1. és a 2. tételek azt fejezik ki, hogy egy X tiszta mondat érvényes akkor és  csak akkor ha őt Boole értelemben implikálja valamely reguláris halmaz. Ez ekvivalens azzal, hogy S véges tiszta mondathalmaz kielégíthetetlen, akkor és csak akkor ha létezik olyan R reguláris halmaz, hogy RS 0-adrendben kielégíthetetlen.
A 2. tétel elegendő a predikátumkalkulus teljességének bizonyítására a szokásos axiomatizálási esetben. De vannak olyan teljességi problémák, amelyekhez ennél erősebb tétel kell.

Def. Az X formula gyenge részformulája az X formula egy részformulája vagy annak negáltja.
2*.Tétel. (Az alaptétel) Minden X érvényes tiszta  mondatot Boole értelemben (0-adrendben) implikál valamely R reguláris halmaz, ahol még az is érvényes, hogy az R-beli Q Q(a) formulákra Q gyenge részformulája az X-nek. 
Egy a 2* tételnek megfelelő R halmazt a X formulához asszociáltnak nevezünk. Általánosabban szólva egy S véges mondathalmazhoz asszociáltnak nevezzük R-et, ha teljesülnek a következők:
(1) R reguláris
(2) Az R minden egyes Q Q(a) formulájára Q gyenge részformulája S valamely elemének.
(3) S-ben nem fordul elő R-beli kritikus paraméter
(4) SR 0-adrendben kielégíthetetlen.
Az alaptételnek sok bizonyítása lehetséges. Most mint az egységes elv következményét tekintjük. Ehhez a következő ekvivalens formába fogalmazzuk meg a tételt: Minden kielégíthetetlen S tiszta formulahalmaznak van assszociáltja.(A megfordítást az 1 tétel biztosítja)
Jelentse (S) azt, hogy S-nek nincs asszociáltja, más szóval, hogy S-nek van asszociáltja az azt jelent, hogy S -inkonzisztens. Csak azt kell belátni, hogy  analitikus konzisztencia tulajdonság. Ezt az 'A0 - 'A4 feltételeken nézzük végig, vagyis hogy S-nek ***van asszociáltja hogy belássuk S  inkonzisztens.
(0) Ha S tartalmaz komplemens atompárt, akkor S 0-adrendben kielégíthetetlen és az üres halmaz az asszociáltja.
(1) Ha {S,1,2}-nek van egy R asszociáltja, akkor az R  aszociáltja az {S,}-nak is.
(2) Tegyük fel, hogy R1 asszociáltja {S,1}-nek és R2 asszociáltja {S,2}-nek. Ha R1 egyetlen kritikus paramétere sem fordul elõ R2-ben, akkor R1R2 reguláris és asszociáltja {S,}-nak. Ha R1 bizonyos kritikus paraméterei elõfordulnak R2-ben, akkor átnevezéssel ez megváltoztatható és R*1 R2 már asszociáltja {S,}-nak.
(3) Ha R asszociáltja {S,,(a)}-nak, akkor {R, (a)} asszociáltja {S,}-nak.
Ennek belátásához megállapítjuk, hogy {R, (a)} reguláris, ami nyilvánvaló. A  részformulája {S,}-nak és minden R-beli QQ(b)-ra mivel Q gyenge részformulája a  {S,, (a)} halmaz valamelyik elemének, így ha (a) gyenge részformulája lenne akkor a -nak is gyenge részformulája lenne.
Mint tudjuk {R,S,,(a)} 0-adendben kielégíthetetlen, be kell látni, hogy { R, (a),S, } 0-adendben kielégíthetetlen. Ez abból következik, hogyha kielégíthetõ lenne, akkor {R,S,,(a)}-nek is kielégíthetõnek kellene lenni.
(4) Ha R asszociáltja {S,(a)}-nak és az a nem fordul elõ sem S-ben sem -ban, akkor {R,(a)} asszociáltja  {S,}-nak.
Itt csak azt kell igazolni, hogy {R,(a)} reguláris, ami a feltételekbõl jön. A többi lépés hasonló a (3) pontbeliekhez.
R3. Analitikus tablók és reguláris halmazok.
Tegyük fel, hogy eg S tiszta formulahalmaznak van zárt T tablója. Az alaptétel miatt S-nek van R asszociáltja. Vajon egy adott tabló esetén hogyan lehet magtalálni egy ilyen R-et. Ez az R azokból a 
QQ(a) formulákból áll, ahol Q(a) le lett vezetve Q-ból a C vagy a D szabállyal.
Az R reguláris a D szabály megszorítása miatt. Q biztosan gyenge részformulája S-nek, mivel megjelent a tablóban. S-ben nincs paraméter igy R-beli kritikus paraméter nem lehet S-ben. Könnyű megmutatni, hogy R az S-nek egy asszociáltja (mégpedig az alaptétel felhasználása nélkül - vagyis csak a tabló teljességének kihasználásával).
Ezek után azt kell megmutatni, hogy SR tautológikusan kielégíthetetlen. Ezt úgy mutatjuk meg, hogy megkonstruáljuk az SR olyan lezárt T0 tablóját, amelyben csak 0-drendű szabályokat használtunk.
Mielõtt ezt megtennénk vizsgáljuk meg a modus ponens szerepét a tablóban. A modus ponens a legtöbb logikai rendszerben meglévõ szabály azaz X és XY-ból levezetjük Y-t. Tegyük fel, hogy ezt hozzávesszük a tabló szabályaihoz, vagyis a tablónk minden olyan ágához, amely tartalmazza X-et  és XY-t hozzávesszük Y-t. Ezzel nem növeltük a bizonyítható formulák körét, mivel az X és XY-t tartalmazó ág X-el vagy Y-al folytatható, amelyekbõl a X-el való folytatás zárt ág. 
Térjünk vissza annak megmutatásához, hogy SR tautológikusan kielégíthetetlen, azaz hogy csak az A és B szabályok segítségével érjük el az SR  lezárt T0 tablóját Tegyük fel, hogy az S T tablóját úgy változtassuk meg, hogy valahányszor egy ágon elõfordul egy Q, Q(a) levezetés valamelyik kvantorszabály alapján beszúrjuk e két formula közé a QQ(a) formulát. Ezzel bevezettük a tablóba az R elemeit, nem használtuk csak az A és B szabályokat, a tábló zárt, így SR tautológikusan kielégíthetetlen. Vagyis, ha X egy érvényes tiszta mondat, akkor X -nek van egy R asszociáltja. Ez azt is jelenti, hogy R^X tautológia.
Példa R konstrukciójára:
Az érvényes formula: x(P(x)Q(x))[xP(x) xQ(x)]
A tabló:
(1) 	[x(P(x)Q(x))[xP(x) xQ(x)]]
(2) 	x(P(x)Q(x)		(1)
(3) 	[xP(x) xQ(x)]	(1)
(4)	xP(x)		(3)
(5)	xQ(x)		(3)
(6)	P(a)Q(a)		(2)  *  kvantorszabállyal
(7)	P(a)			(4)  *	“
(8)	Q(a)			(5)  *	“
(9)	P(a)  (6)    Q(a)  (6)
A három kvantorszabály miatt be lehet írni a (2)(6),(4)(7),(5)(8) reguláris formulákat, amelyek egyben az R-et adják. Vagyis 
R={x(P(x)Q(x)( P(a)Q(a)), xP(x) P(a), xQ(x) Q(a)} 0-adrendben kell hogy implikálja  x(P(x)Q(x))[xP(x) xQ(x)]-t.
Vezessük be a következõ jelöléseket a Boole atomokra.
p1=x(P(x)Q(x)
p2= P(a)
p3= Q(a)
p4=xP(x)
p5=xQ(x)
Ekkor		R={p1(p2p3), p4p2, p5p3}
A formula	A=p1(p4p5) egyszerű kiszámolni, hogy R^A tautológia.

M1. Mágikus halmazok.
Definíciók:
Paraméteres vagy nem paraméteres mondatok M halmazát mágikus halmaznak nevezzük, ha :
 M1: Minden az M-et kielégítõ Boole értékelés elsõrendű értékelés is.
 M2: Tiszta mondatok valamely véges S0 és az M bármely véges M0 részhalmazára, ha S0 kielégíthetõ elsõrendben, akkor S0M0 is az.
Egy X formula nulladrendben levezethetõ egy S halmazból, ha van az S-nek olyan véges S0 részhalmaza amely nulladrendben implikálja X-et, vagis S0^X tautológia.
Egy B halmaz az elsõrendű logikának nulladrendű bázisa, ha minden X tiszta mondatra X érvényes akkor és csak akkor, ha X nulladrendben levezethetõ B-bõl.
Mielõtt megmutatnánk a mágikus halmaz létét bebizonyítunk egy tételt.
1 M. Tétel. Minden M mágikus halmaz nulladrendű bázisa az elsõrendű logikának.
Bizonyítás. Legyen M mágikus halmaz
(a) Tegyük fel, hogy X érvényes. Azt állítjuk, hogy X igaz az M-et kielégítõ minden Boole értékelésre. Legyen  az M-et kielégítõ Boole értékelés. Az M1 miatt  egyben elsõrendű értékelés is. Mivel X érvényes, ezért -re igaznak kell lennie.
Igy X igaz minden az M-et kielégítõ Boole értékelésre. Emiatt  és az ítéletkalkulus kompaktsági tétele miatt X nulladrendben levezethetõ M-bõl.
(b) A másik irányhoz tegyük fel, hogy X nulladrendben levezethetõ M-bõl és hogy X-ben nincsen paraméter. Ekkor X-et nulladrendben implikálja az M valamely véges M0 részhalmaza, ezért az M0{X} nulladrendben nem kielégíthetõ. Következésképen elsõrendben sem kielégíthetõ (miért). A{X} sem lehet elsõrendben kielégíthetõ, mert ha az lenne akkor M2 miatt M0{X} is az lenne, amirõl tudjuk, hogy nem az. Ezzel a bizonyítás kész.
Megjegyzés. Az (a)-ban nem használtuk ki azt, hogy X tiszta lenne és valójában ez az oka, hogy bármely érvényes mondat - akkor is ha tartalmaz paramétert - nulladrendben levezethetõ M-bõl.
Mielõtt  mágikus halmaz létezését biztosító tételt kimondanánk nézzük a következõ lemma variációkat.
1 M Lemma. Legyen  (a  és  típusú formulákra nézve) a következõ két tulajdonsággal rendelkezõ Boole értékelés. Ebben az esetben   elsõrendű értékelés.
(1) Ha  igaz -re, akkor minden a paraméterre (a) igaz -re.
(2) Ha  igaz -re, akkor legalább egy a paraméterre (a) igaz -re.
Bizonyítás.  ...
1’ M Lemma. Legyen S egy Boole értelemben igaz halmaz (a  és  típusú formulákra nézve) a következõ két tulajdonsággal:
(1) Ha  S, akkor minden a paraméterre (a) S.
(2) Ha S, akkor legalább egy a paraméterre (a) S
Tehát S egy elsõrendű igaz halmaz.

A mágikus halmaz létezését biztosítja a következõ tétel.
2 M. Tétel. Létezik M reguláris mágikus halmaz.
Bizonyítás. Az elõhelyettesített paraméterek módszerét használjuk. Az összes  mondatokat felsoroljuk egy megszámlálható sorozatba 1, 2,..., n, .... Ezután a paraméterek egy rögzített b1, b2, ..., bn, ... sorozatát tekintjük. Az a1 az elsõ olyan eleme a {bi} sorozatnak, amely nem fordul elõ 1-ben, a2 a következõ olyan, amelyik nem fordul elõ sem 1-ben sem 2-ben. Az an+1 az an kiválasztása után következõ olyan eleme a {bi} sorozatnak, amely nem fordul elõ 1-ben,..., n-ben, n+1-ben. Legyen R1 a 11(a), 22(a), ..., nn(a), ...halmaz, R2 az öszes (a) mondatok halmaza, minden a-ra. Az R1R2 reguláris halmaz és egyben egy M mágikus halmaz.
Lássuk be az M1 tulajdonságot (minden az M-et kielégítõ Boole értékelés egyben elsõrendű értékelés).