Opløselighedslogik

Opløselighedslogik er et område inden for matematisk logik og teoretisk datalogi, der undersøger spørgsmålet, hvornår en given problemformulering eller en logisk sætning har en løsning eller et vidne inden for et bestemt formalisme. Begrebet fokuserer ikke blot på, om sætningen er sand, men på om der findes en konstruktiv løsning, en vidne eller en procedure, der udleder et svar inden for systemets regler.

Fagfeltet hører til krydsfeltet mellem bevisteori, modellering og beregningslogik. Det bruger forskellige logiksystemer som førsteordens logik, intuitionistisk logik og typer til at beskrive opløselighedsvilkår og at undersøge relationen mellem beslutsomhed (kan vi beslutte, at der findes en løsning?) og bevisbarhed (kan løsningen udledes i et bevis). Man undersøger også, hvordan opløselighed opfører sig under ændringer af rammerne, fx hvilke modeller er mulige, og hvilke vidner kan udtrækkes.

Metoder i opløselighedslogik omfatter analyse af beslutningsproblemer, konstruktion af algoritmer og studie af kompleksitet — hvilke logikker er besluttelige, og hvor effektivt kan en løsning udledes. Teorien undersøger også relationen mellem opløselighed og satisfiabilitet (eksistensen af en model) og hvordan disse egenskaber kan bruges i automatiske beviser og programudvikling.

Anvendelser findes inden for automatiseret bevisførelse, programsyntese, constraint solving og formel verifikation af systemer. Ved hjælp af opløselighedslogik kan man modellere og undersøge, hvornår et givent krav kan opfyldes, og hvordan man udleder konkrete løsninger eller vidner fra et system af regler.

Se også: satisfiability, decidability, konstruktiv logik, bevisTeori, modellering, constraint satisfaction problems.