Algorithmic structural completeness and a retrieval system for proving theorems in algorithmic Biela

WUŚ 2000, str. 122, stan bdb-
Język angielski



Algorytmiczna strukturalna zupełność i system wyszukiwania dowodów twierdzeń w teoriach algorytmicznych

Dowody poprawności oprogramowania są jedynym sposobem zapewnienia użytkownika (inwestora), że można z niego korzystać bez ryzyka. W pracy rozważa się zatem klasę reguł algorytmicznie strukturalnie zupełnych, pozwalających na poprawne wnioskowanie.
Duże znaczenie w automatycznym dowodzeniu twierdzeń ma właściwy dobór reguł, dlatego badania rozpoczęto od próby uzasadnienia wyprowadzalności reguł dopuszczalnych w logice algorytmicznej.
W publikacji zawarto wyniki badań dotyczące algorytmicznej strukturalnej zupełności logiki algorytmicznej oraz omówiono system automatycznego dowodzenia twierdzeń, w którym pewne relacje czy funkcje mogą być reprezentowane za pomocą programów. Badania przedstawiono w języku umożliwiającym wyrażenie własności programów (rozdz. 2).
Pierwsza część pracy dotyczy:
1) wprowadzenia reguły podstawiania do logiki algorytmicznej i do logiki z niedetermini-stycznymi programami oraz udowodnienia zasadniczych własności podstawiania (rozdz. 3),
2) uzasadnienia algorytmicznej strukturalnej zupełności logiki algorytmicznej z dołączoną regułą podstawiania (rozdz. 4).
Zdefiniowano zbiór podstawień taki, że wprowadzona za jego pomocą reguła podstawiania okazała się, mówiąc intuicyjnie, na tyle „silna dedukcyjnie", iż pozwoliła na uzyskanie algorytmicznej strukturalnej zupełności logiki algorytmicznej. Na podstawie tej własności stwierdza się, że w konsekwencji logiki algorytmicznej każda reguła strukturalna, finitarna i dopuszczalna jest w niej wyprowadzalna. Można zatem swobodnie stosować reguły z tej klasy. Ponadto dla niezupełnego systemu logiki algorytmicznej otrzymano pewien rodzaj ijuasi-zupełności, którym jest algorytmiczna strukturalna zupełność.
Dalszą część pracy (rozdz. 5) poświęcono omówieniu systemu dowodzącego, który umożliwia dowodzenie twierdzeń metodą Gentzena, sformułowanych w języku różnych teorii, a także dowodzenie twierdzeń o programach. Ponadto możliwe są dowody wyrażeń nie będących twierdzeniami, polegające na znalezieniu i dołączeniu dodatkowych aksjomatów umożliwiających dowód. System ten pozwala również na dowodzenie poprawności programów, rozwiązywanie równań funkcyjnych, których funkcje są zdefiniowane za pomocą programów, a także badanie relacji zdefiniowanych za pomocą procedur oraz badanie niezależności aksjomatów.