Neinterpretovaná funkce - Uninterpreted function

v matematická logika, an neinterpretovaná funkce^[1] nebo symbol funkce^[2] je ten, který nemá jinou vlastnost než své jméno a n-ary formulář. K tvorbě se používají funkční symboly spolu s konstantami a proměnnými podmínky.

The teorie neinterpretovaných funkcí je také někdy nazýván volná teorie, protože je volně generován, a tedy a volný objekt, nebo prázdná teorie, přičemž teorie s prázdnou sadou věty (analogicky k počáteční algebra ). Teorie s neprázdnou množinou rovnic jsou známé jako rovnicové teorie. The uspokojivost problém bezplatných teorií řeší syntaktické sjednocení; Algoritmy pro druhé jsou používány tlumočníky pro různé počítačové jazyky, jako např Prolog. Syntaktické sjednocení se také používá v algoritmech pro problém uspokojivosti pro některé další rovníkové teorie, viz E-sjednocení a Zúžení.

Příklad

Příklad neinterpretovaných funkcí v SMT-LIB, vstupní standard pro Řešitelé SMT:

(declare-fun f (Int) Int) (assert (= (f 10) 1))

To je uspokojivé: F je neinterpretovaná funkce. Vše, o čem je známo F je jeho podpis, takže je možné, že f (10) = 1.

(declare-fun f (Int) Int) (assert (= (f 10) 1)) (assert (= (f 10) 42))

To je neuspokojivé: ačkoli F nemá žádnou interpretaci, je nemožné, že vrací různé hodnoty pro stejný vstup.

Diskuse

The rozhodovací problém zdarma teorie je obzvláště důležité, protože mnoho teorií může být redukováno na to.^{[Citace je zapotřebí ]}

Volné teorie lze vyřešit hledáním běžné podvýrazy tvořit shoda uzavření.^{[je zapotřebí objasnění ]} Řešitelé zahrnují teorie uspokojivosti modulo řešitelé.

Viz také

Poznámky

Reference

^ Bryant, Randal E .; Lahiri, Shuvendu K .; Seshia, Sanjit A. (2002). „Modelování a ověřování systémů pomocí logiky počítadla aritmetiky s lambda výrazy a neinterpretovanými funkcemi“ (PDF). Ověření pomocí počítače. Přednášky z informatiky. 2404. str. 78–92. doi:10.1007/3-540-45657-0_7. ISBN 978-3-540-43997-4.
^ Baader, Franz; Nipkow, Tobias (1999). Přepisování termínů a tak dále. Cambridge University Press. str. 34. ISBN 978-0-521-77920-3.

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

[1] Bryant, Randal E .; Lahiri, Shuvendu K .; Seshia, Sanjit A. (2002). „Modelování a ověřování systémů pomocí logiky počítadla aritmetiky s lambda výrazy a neinterpretovanými funkcemi“ (PDF). Ověření pomocí počítače. Přednášky z informatiky. 2404. str. 78–92. doi:10.1007/3-540-45657-0_7. ISBN 978-3-540-43997-4.

[2] Baader, Franz; Nipkow, Tobias (1999). Přepisování termínů a tak dále. Cambridge University Press. str. 34. ISBN 978-0-521-77920-3.

[1]

[2]