Funcție neinterpretată - Uninterpreted function
În logica matematică , o funcție neinterpretată sau un simbol funcțional este una care nu are altă proprietate decât numele și forma sa n-ari . Simbolurile funcționale sunt utilizate, împreună cu constante și variabile, pentru a forma termeni .
Teoria funcțiilor uninterpreted este , de asemenea , numit uneori teoria liberă , deoarece este generat în mod liber, și , astfel , un obiect liber , sau teoria goală , fiind teoria care are un set gol de propoziții (în analogie cu o algebră inițială ). Teoriile cu un set de ecuații care nu sunt goale sunt cunoscute sub numele de teorii ecuaționale . Problema satisfacției pentru teoriile libere este rezolvată prin unificarea sintactică ; algoritmii pentru aceștia din urmă sunt folosiți de interpreți pentru diverse limbaje de calculator, cum ar fi Prolog . Unificarea sintactică este, de asemenea, utilizată în algoritmi pentru problema satisfacției pentru alte teorii ecuaționale, a se vedea E-Unificare și îngustare .
Exemplu
Ca exemplu de funcții neinterpretate pentru SMT-LIB, dacă această intrare este dată unui rezolvator SMT :
(declare-fun f (Int) Int)
(assert (= (f 10) 1))
rezolvatorul SMT va returna „Această intrare este satisfăcătoare” Acest lucru se întâmplă pentru că f este o funcție uninterpreted (adică, tot ce se stie despre f este de semnătură ), deci este posibil ca f(10) = 1 . Dar aplicând datele de mai jos:
(declare-fun f (Int) Int)
(assert (= (f 10) 1))
(assert (= (f 10) 42))
rezolvatorul SMT ar returna „Această intrare este nesatisfăcătoare”. Acest lucru se întâmplă pentru că, deși f nu are interpretare, dar este imposibil să returneze valori diferite pentru aceeași intrare.
Discuţie
Problema deciziei pentru teoriile gratuite este deosebit de importantă, deoarece multe teorii pot fi reduse de aceasta.
Teoriile libere pot fi rezolvate căutând subexpresii comune pentru a forma închiderea congruenței . Solvenții includ rezolvatori de teorii modulo de satisfacție .
Vezi si
Note
Referințe
 |
Acest articol legat de metodele formale este un butuc . Puteți ajuta Wikipedia extinzându-l . |
