Neuspokojivé jádro - Unsatisfiable core
v matematická logika, vzhledem k neuspokojivý Booleovský výrokový vzorec v konjunktivní normální forma, podmnožina vět, jejichž konjunkce je stále neuspokojivá, se nazývá neuspokojivé jádro původního vzorce.
Mnoho SAT řešitelé může produkovat a graf rozlišení což dokazuje neuspokojivost původního problému. To lze analyzovat a vytvořit menší neuspokojivé jádro.
Neuspokojivé jádro se nazývá a minimální nevyhovující jádro, je-li každá správná podmnožina (umožňující odebrání libovolné klauze nebo klauzulí) splněna. Takovým jádrem je tedy místní minimum, i když ne nutně globální. Existuje několik praktických metod výpočtu minimálních nevyhovujících jader.[1][2]
A minimální nevyhovující jádro obsahuje nejmenší počet původních klauzulí, které musí být stále neuspokojivé. Nejsou známy žádné praktické algoritmy pro výpočet minimálního jádra.[3] Všimněte si terminologie: vzhledem k tomu minimální nevyhovující jádro byl místní problém se snadným řešením, minimální nevyhovující jádro je globální problém bez známého snadného řešení.
Reference
Tento logika související článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to. |