Származtathatók

Származtathatók a matematikai logika és formális nyelvek közösségében olyan állításokra utaló kifejezés, amelyek egy adott axiomsoron vagy elveken alapuló formális rendszerben levezethetők vagy bizonyíthatók. A szó a magyar származtatás (deriváció) igéből származik, és azt a tulajdonságot fejezi ki, hogy egy formula igazolható a megadott szabályrendszer segítségével.

Formálisan egy Γ halmaz legyen a kiinduló axiómák vagy sémahalmaz, és legyen R a levezetési szabályok halmaza. Egy φ formulát akkor és csak akkor tekintünk származtathatónak Γ-ból, ha létezik egy véges derivációs sorozat, amelynek minden eleme vagy egy axióma, vagy eleme Γ-nek, vagy a korábbi elemek felhasználásával R szabályai révén származik, és a sorozat végén φ áll. A származtatható φ-k sorozát a Γ tételsorozatának nevezik.

A származtathatók fogalma megkülönbözteti a szintaktikai bizonyíthatóságot a szemantikailag igaz professziótól. A formális bizonyítás a szabályokkal végrehajtott szekvencia, míg a szemantika a modellekben adott igazságértékek alapján értelmezi a mondatokat. Gyakran a Γ-tételsorozat fogalmát használják a teóriák összegzésére: a Γ tételeinek halmaza összefoglalja az összegyűjtött bizonyított állításokat.

Különböző logikákban alkalmazható a koncepció, például proposicionális, elsőrendű vagy módosított logikákban. A származtathatók fogalmát központi szerep tölti be automatizált bizonyításban és formális ellenőrzésben, ahol a programok derivációkat keresnek és ellenőriznek. Kapcsolódó fogalmak a bizonyítási rendszerek, a derivációk, a dedukciós tétel és a teljesesség.