Tovább a tartalomhoz
Tudástár

Átfogó kérdőív-ellenőrzés

Ez az oldal azt mutatja be, hogyan viszonyul egy teljes kérdőív globális kielégíthetőségi vizsgálata az Askalot által futtatott elemenkénti vizsgálatokhoz, valamint a holtkódot felderítő útvonalalapú vizsgálathoz. Kimondja, mely következtetések mely vizsgálatokból adódnak, és mindegyiket példával szemlélteti. A definíciók, tételek és bizonyításaik az ICAI 2026 konferencián (13th International Conference on Applied Informatics) bemutatott, lektorált tanulmányban találhatók, a konferenciakötet 227–243. oldalán, doi:10.17048/icai.2026.227; a teljes hivatkozás a Hivatkozás részben olvasható.

Ahogyan a Kérdőívelemzés oldal kifejti, minden válasznak van értékkészlete, és az értékkészletek együtt adják az alapmegszorítást. Minden elemnek van előfeltétele, amely eldönti, hogy megjelenik-e, és utófeltétele, amelyet az érvényes válasznak teljesítenie kell. Mindkettő a válaszokra vonatkozó feltétel.

A globális kielégíthetőségi formula

Szekció neve “A globális kielégíthetőségi formula”

A globális vizsgálat egyetlen kérdést tesz fel a teljes kérdőívről: van-e legalább egy olyan válaszegyüttes, amely

  1. minden elem értékkészletén belül marad, és
  2. minden elemet vagy kihagy (az előfeltétele nem teljesül), vagy teljesíti az utófeltételét?

Ha létezik ilyen válaszegyüttes, a kérdőív átmegy a globális vizsgálaton.

Egyetlen elemre a tanúkérdés így szól: van-e olyan válaszegyüttes, amely az értékkészleteken belül marad, eléri az elemet (az előfeltétele teljesül), és megsérti az utófeltételét? Az ilyen válasz tanúja annak, hogy az elem megbukhat az ellenőrzésen.

  • Ha nincs tanú, az elem lokálisan érvényes: valahányszor a kitöltés eléri, az utófeltétele teljesül.
  • Ha van tanú, az elem megsérthető, és a tanút a rendszer diagnosztikai üzenetként jelzi.

Az alábbi összefüggések pontosan megmondják, mit árulnak el az elemenkénti vizsgálatok a globális vizsgálatról, és mit nem.

Tétel: az elemenkénti érvényesség helyessége

Szekció neve “Tétel: az elemenkénti érvényesség helyessége”

Ha az értékkészletek egyáltalán kielégíthetők, és egyetlen elemnek sincs tanúja, a kérdőív átmegy a globális vizsgálaton.

Más szóval: ha minden elem lokálisan érvényes, akkor bármely, az értékkészleteken belül maradó válaszegyüttes eleve teljesít minden rá vonatkozó utófeltételt, így létezik érvényes kitöltés.

Gyakorlati következmény: az elemenkénti ellenőrzés a globális ellentmondásmentesség elégséges feltétele. Ha minden elem átmegy a saját vizsgálatán, nincs szükség a költségesebb globális vizsgálatra. A bizonyítást a tanulmány tartalmazza.

Tétel: a lokális érvénytelenségből nem következik globális kielégíthetetlenség

Szekció neve “Tétel: a lokális érvénytelenségből nem következik globális kielégíthetetlenség”

Ha egy elemnek van tanúja, az nem jelenti azt, hogy a kérdőív megbukik a globális vizsgálaton. A tanú azt mutatja, hogy valamely válaszegyüttes megsérti az adott elemet; a globális vizsgálat azt kérdezi, hogy valamely más válaszegyüttes egyszerre kielégít-e mindent.

Tétel: a felhalmozódó megszorítások globális kielégíthetetlenséget okozhatnak

Szekció neve “Tétel: a felhalmozódó megszorítások globális kielégíthetetlenséget okozhatnak”

Vannak olyan kérdőívek, amelyekben önmagában egyetlen elem sem INFEASIBLE, a globális vizsgálat mégis megbukik.

Az elemenkénti vizsgálatok minden utófeltételt külön-külön, az értékkészletekhez viszonyítva néznek. A kitöltés során azonban a válaszadó függőségi sorrendben válaszol az elemekre, és a korábbi elemek utófeltételeinek már teljesülniük kell, amikor a kitöltés egy későbbi elemhez ér. Ezeket a felhalmozódó megszorításokat az elemenkénti vizsgálatok nem látják.

A globális vizsgálat minden elemet rendben lévőnek tekint, amelynek nem teljesül az előfeltétele, így nem tudja megkülönböztetni a jogosan kihagyott elemet attól, amely sosem érhető el. Ezt a hiányt pótolja az útvonalalapú ellenőrzés.

A függőségi gráfra és a belőle Kahn algoritmusával kiszámított kiértékelési sorrendre épül.

A végrehajtási út elemek olyan sorozata, amelynek sorrendjét a függőségi gráf topologikus rendezése megengedi, és amelyben minden elem előfeltétele teljesül az előtte álló elemekből felhalmozódott megszorítások mellett.

Egy út megvalósítható, ha létezik olyan válaszegyüttes, amely az értékkészleteken belül marad, és az út minden elemére teljesíti az előfeltételt és az utófeltételt is.

A globális vizsgálattól az a különbség, hogy az úton lévő elemet ténylegesen el kell érni: az előfeltételének ténylegesen teljesülnie kell, míg a globális vizsgálat a nem teljesülését is elfogadja.

Tétel: a globális érvényesség az útérvényesség szükséges feltétele

Szekció neve “Tétel: a globális érvényesség az útérvényesség szükséges feltétele”

Ha a globális vizsgálat megbukik, egyetlen végrehajtási út sem megvalósítható. Az a válaszegyüttes, amely egy utat megvalósíthatóvá tenne, a globális vizsgálatot is kielégítené, hiszen az úton lévő elemeket a kitöltés eléri, és a válaszuk érvényes, az úton kívüliek pedig kimaradnak. A sikertelen globális vizsgálat tehát azt jelenti, hogy a kérdőíven nincs érvényes út.

Tétel: a globális érvényesség nem garantálja, hogy minden elem elérhető

Szekció neve “Tétel: a globális érvényesség nem garantálja, hogy minden elem elérhető”

Egy kérdőív átmehet a globális vizsgálaton úgy is, hogy egy elem, amelynek előfeltétele önmagában nem lehetetlen, minden megvalósítható úton elérhetetlen marad.

A gyakorlatban az utakat nem soroljuk fel egyenként. Az elemzés a Kahn algoritmusával kiszámított topologikus sorrendben halad végig az elemeken (lásd: Függőségelemzés), és minden elemet az összes előtte álló elemből felhalmozódott megszorításokhoz viszonyítva ellenőriz.

Egy elem felhalmozottan elérhető, ha létezik olyan válaszegyüttes, amely az értékkészleteken belül marad, minden korábbi elem utófeltételét teljesíti, amelyet a kitöltés elér, és igazzá teszi a vizsgált elem előfeltételét. A korábbi elemek itt a topologikus sorrendben előtte álló összes elemet jelentik, nem csak azokat, amelyektől közvetlenül függ.

Az a CONDITIONAL elem, amely nem érhető el felhalmozottan, holtkód: az előfeltétele az előtte álló elemek által támasztott megszorítások mellett sosem teljesülhet.

A kérdőív-ellenőrzés három, egyre alaposabb és egyre nagyobb számítási költségű szinten végezhető:

Minden elemre, egymástól függetlenül:

  • Elérhetőség: az előfeltétel besorolása ALWAYS, NEVER vagy CONDITIONAL osztályba
  • Érvényesség: az utófeltétel besorolása TAUTOLOGICAL, CONSTRAINING vagy INFEASIBLE osztályba, a tanúkérdés segítségével

Ez a leggyorsabb szint: minden elem önállóan és párhuzamosan ellenőrizhető.

Mindkét vizsgálat számol azokkal a válaszokkal, amelyeket a válaszadó üresen hagyhat. Az ilyen választ olvasó előfeltétel üres válasz esetén eldöntetlen, ami elrejti az elemet, így az elem CONDITIONAL, nem ALWAYS. Az az utófeltétel, amely alól azért van felmentés, mert az általa olvasott válasz üres, nem számít teljesültnek, így nem kap TAUTOLOGICAL besorolást. Üres válasz csak ott jön számításba, ahol a kérdés saját utófeltétele elfogadja; a q.outcome is not None utófeltétel kötelezővé teszi a választ.

A részleteket az Elő- és utófeltételek oldal tartalmazza.

Futtassa a globális vizsgálatot: van-e legalább egy olyan válaszegyüttes, amely minden elemet kihagy vagy érvényesen megválaszol?

Ez igazolja, hogy legalább egy érvényes kitöltés létezik, de minden kihagyott elemet rendben lévőnek tekint.

Minden feltételes elemre ellenőrizze a felhalmozott elérhetőséget: kielégíthető-e még az előfeltétele, miután a topologikus sorrendben előtte álló összes elem utófeltétele érvényesül? Ahelyett, hogy egyenként felsorolná a végrehajtási utakat, az elemzés topologikus sorrendben halad végig az elemeken, és minden feltételes elemet az elődeiből felhalmozódott megszorításokhoz viszonyítva vizsgál (lásd fent: Felhalmozott elérhetőség).

Ez a legalaposabb szint: felismeri azokat az elemeket, amelyek a felhalmozódó utófeltételek miatt elérhetetlenné válnak (holtkód).

A három szint a következőképpen függ össze:

  • Ha az elemenkénti ellenőrzés sikeres, a globális is az. A helyességi eredmény szerint, ha egyetlen elemnek sincs tanúja (minden utófeltétel TAUTOLOGICAL), a globális vizsgálat garantáltan sikeres. További vizsgálatra nincs szükség.
  • Ha a globális ellenőrzés megbukik, az útvonalalapú is. Ha a globális vizsgálat megbukik, egyetlen végrehajtási út sem lehet érvényes. A globális vizsgálat a kérdőív érvényességének szükséges feltétele.
  • A sikeres globális ellenőrzés nem jelenti, hogy minden út érvényes. A globális vizsgálat akkor is sikeres lehet, ha egyes elemek elérhetetlenek, mert a kihagyott elemet rendben lévőnek tekinti.
  • Az elemenkénti ellenőrzés elegendő, ha minden utófeltétel TAUTOLOGICAL. A kérdőívben nincs megszorító logika, így bármely válaszkombináció érvényes.
  • A globális ellenőrzés elegendő, ha csak azt kell igazolni, hogy létezik valamilyen érvényes kitöltés, és a holtkód (elérhetetlen elemek) elfogadható.
  • Útvonalalapú ellenőrzésre van szükség, ha megköveteli, hogy minden feltételes elem ténylegesen elérhető legyen legalább egy érvényes úton. Ez felismeri azokat a tervezési hibákat, amelyeknél a felhalmozódó utófeltételek elérhetetlenné teszik az elemeket.

Az ellenőrzési eredmények összefoglalása

Szekció neve “Az ellenőrzési eredmények összefoglalása”
  • Egyetlen elemnek sincs tanúja: minden utófeltétel TAUTOLOGICAL. A helyességi eredmény szerint a globális és az útvonalalapú érvényesség garantált; további vizsgálatra nincs szükség.
  • Valamely elemnek van tanúja, és a globális vizsgálat megbukik: a felhalmozódó CONSTRAINING utófeltételek ütköznek, és egyetlen végrehajtási út sem érvényes. Ez tervezési hiba.
  • Valamely elemnek van tanúja, a globális vizsgálat sikeres, és minden elem felhalmozottan elérhető: a kérdőív teljes mértékben érvényes, kitölthető, holtkód nélkül.
  • Valamely elemnek van tanúja, a globális vizsgálat sikeres, és valamely elem nem érhető el felhalmozottan: a kérdőív kitölthető, de holtkódot (elérhetetlen elemeket) tartalmaz, amelyet a rendszer figyelmeztetésként jelez.
  • Valamely elem INFEASIBLE: az utófeltétel nem teljesíthető, amikor a kitöltés eléri az elemet; kijavítandó tervezési hiba.
  • Valamely elem NEVER besorolású (elemenként): az előfeltétel felhalmozódó megszorítások nélkül is kielégíthetetlen; tervezési hiba.
B alapmegszorításokSAT?Minden W_i UNSATF UNSATHibás alaprendszerMinden W_i UNSAT?F SATA kérdőív ellentmondásmentesAz elemenkénti vizsgálat elegendőValamely W_i SATF SAT voltának vizsgálataMinden elemfelhalmozottan elérhető?F UNSATNincs érvényes kitöltési útTeljesen érvényesNincs holtkódKitölthető, deholtkódot tartalmaz UNSATSATIgenNemSATUNSATIgenNem

Az ábrán B az alapmegszorítás, W_i az i-edik elem tanúkérdése, F pedig a globális vizsgálat.

Ezen összefüggések alapján egy megbízható ellenőrzési stratégia rétegenként halad:

1. réteg: az alapmegszorítás vizsgálata

Szekció neve “1. réteg: az alapmegszorítás vizsgálata”
  1. Ellenőrizze, hogy az értékkészletek egyáltalán kielégíthetők-e
    • Ha nem: jelezzen alapvető tervezési hibát az értékkészlet-megszorításokban
    • Ha igen: folytassa az elemenkénti elemzéssel
  1. Minden elemre:
    • Vizsgálja az előfeltétel elérhetőségét: ALWAYS, NEVER vagy CONDITIONAL
    • Vizsgálja az utófeltétel állapotát: VACUOUS, TAUTOLOGICAL, CONSTRAINING vagy INFEASIBLE
    • Jelezze diagnosztikai üzenetként a feltételt megsértő konkrét hozzárendeléseket
    • Jelölje tervezési hibaként a NEVER besorolású elemeket és az INFEASIBLE utófeltételeket

3. réteg: globális ellentmondásmentesség (opcionális)

Szekció neve “3. réteg: globális ellentmondásmentesség (opcionális)”
  1. Ha nagy bizonyosságra van szükség, végezze el a globális vizsgálatot:
    • Erősítse meg, hogy létezik legalább egy érvényes kitöltési út
    • Ha az elemenkénti érvényesség ellenére megbukik, vizsgálja meg az elemek közötti ütközéseket
    • Ha sikeres, a kielégítő válaszokat érvényes kitöltési út példájaként is megjelenítheti

4. réteg: útvonalalapú elemzés (opcionális)

Szekció neve “4. réteg: útvonalalapú elemzés (opcionális)”
  1. Átfogó ellenőrzéshez:
    • Vizsgálja minden CONDITIONAL elem felhalmozott elérhetőségét
    • Jelezze holtkód-figyelmeztetésként az elérhetetlenné váló elemeket
    • Győződjön meg róla, hogy minden szándékolt kitöltési út ténylegesen megvalósítható

Az askalot_qml 1.14.0-s verziójától a MatrixQuestion elemek mátrix-utófeltételei ugyanabban az elemenkénti, globális és útvonalalapú ellenőrzési hierarchiában vesznek részt, mint a skalár elemek. A három kanonikus mintát – szimmetria, rögzített összegű elosztás, valamint rangsorolás / különbözőség – a rendszer statikusan ellenőrzi, ha kanonikus formájukban vannak megírva:

  • Szimmetria: all([m.outcome[j][k] == m.outcome[k][j] for j in range(N) for k in range(N) if k > j])
  • Rögzített összeg: all([sum([m.outcome[j][k] for k in range(N)]) == T for j in range(M)])
  • Rangsorolás / különbözőség: all([len(set([m.outcome[j][k] for k in range(N)])) == N for j in range(M)])

Minden MatrixQuestion cellánként egy Z3 Int változót foglal le, (row, col) indexeléssel. A literális range(N) (vagy range(len(m.rows)) / range(len(m.columns))) feletti listaértelmezéseket a rendszer a build során statikusan cellánkénti klózokra bontja ki, így a validátor még a kérdőív kiadása előtt felismeri az INFEASIBLE utófeltételeket (pl. egy olyan rögzített összegű célt, amely a cellák értékkészletének korlátai között nem érhető el). Az m.rows, az m.columns és a QuestionGroup qg.questions értéke az elem deklarált listái, amelyek futás közben is olvashatók, így a range(len(m.rows)) ugyanazt a korlátot adja, amellyel a validátor a kibontást végezte.

A validátor a mátrixot celláról cellára ellenőrzi. Az a feltétel, amely a teljes választ (m.outcome == 1, if m.outcome:) vagy egy teljes sort (m.outcome[0] == [1, 2]) olvas, nincs cellája, amelyről következtetni lehetne; a kitöltéskor fut le, és a validátor a mátrixot megnevező kihagyott feltételként jelzi. Ugyanígy nem ellenőrzi a validátor a kihagyható Question elemek feletti len(set([...])) == N feltételt: a kihagyott Question üres válaszként számít a halmazban, ezért a különbözőségi bizonyítás nem állna meg.

Futásidejű érvényesítésre visszaeső változatok. Néhány megadási formát a futtatókörnyezet (FlowProcessor + PythonRunner) elfogad, a statikus validátor azonban elutasít: a BinOp tartománykezdeteket (range(j+1, N)), a zip / enumerate használatát, a részleges különbözőségi formákat (len(set(...)) == K, ahol K < N), valamint a min / max összesítéseket. Ezek az utófeltételek a válaszadó beküldésekor továbbra is lefutnak, de a statikus validate_qml_file kimenete elemenként coverage_gaps formában jelzi őket, így a szerző pontosan látja, mely megszorítások estek vissza futásidejű érvényesítésre ahelyett, hogy csendben elvesznének.