Bernays – Schönfinkel třída - Bernays–Schönfinkel class

The Bernays – Schönfinkel třída (také známý jako Třída Bernays – Schönfinkel – Ramsey) vzorců, pojmenovaných po Paul Bernays, Mojžíš Schönfinkel a Frank P. Ramsey, je fragment z logika prvního řádu vzorce kde uspokojivost je rozhodnutelné.

Je to sada vět, do kterých se zapisují normální forma prenex, mít ${displaystyle existuje ^ {*} pro všechny ^ {*}}$ předponu kvantifikátoru a neobsahují žádnou funkční symboly.

Tato třída logických vzorců se také někdy označuje jako efektivně výrokové (EPR) protože jej lze efektivně přeložit do výroková logika vzorce procesem uzemnění nebo vytvoření instance.

Problém uspokojivosti pro tuto třídu je NEXPTIME -kompletní.^[1]

Viz také

• Prenex normální forma

Poznámky

Reference

• Ramsey, F. (1930), „O problému formální logiky“, Proc. London Math. Soc., 30: 264–286, doi:10.1112 / plms / s2-30.1.264
• Piskac, R .; de Moura, L .; Bjorner, N. (prosinec 2008), „Efektivní rozhodování o výrokové logice s rovností“ (PDF), Technická zpráva Microsoft Research (2008–181)

Tento matematická logika související článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to.