Z Wikipedii

Automatyczne dowodzenie twierdzeń (ang. automated theorem proving) to proces, w którym komputer rozstrzyga czy dane twierdzenie jest dowodliwe w jakiejś teorii, często przy okazji generując jego dowód. Twierdzenia te należą zwykle do rachunku zdań lub rachunku predykatów pierwszego rzędu.

Dla komputera wygodniejsze jest zwykle wnioskowanie w tył, choć czasem stosuje się też wnioskowanie w przód.

[edytuj] Automatyczne dowodzenie twierdzeń rachunku zdań

Chodzi o stwierdzenie czy dane twierdzenie jest tautologią, lub czy jest spełnialne. Oba przypadki są wzajemnie połączone: zaprzeczenie twierdzenia jest spełnialne wtedy i tylko wtedy, gdy twierdzenie to nie jest tautologią.

Twierdzenia rachunku zdań zawsze są rozstrzygalne - choćby metodą brute force, która polega na sprawdzeniu 2ⁿ kombinacji wartości prawda-fałsz dla n zmiennych zdaniowych występujących w twierdzeniu.

Istnieje wiele innych metod, które mają większą wydajność i generują bardziej czytelne dowody. Do najprostszych z nich należą sekwenty Gentzena, systemy Hilberta oraz dedukcja naturalna. W praktyce używa się zwykle metod bazowanych na procedurze Davisa-Putnama. Można też używać uproszczonych wersji metod dla rachunku predykatów pierwszego rzędu.

Problem spełnialności jest jednak w każdym systemie NP zupełny, zaś problem tautologii - CoNP zupełny.

[edytuj] Automatyczne dowodzenie twierdzeń rachunku predykatów

Dominujące metody to tableau, a przede wszystkim różne wersje rezolucji. W systemach z równością używa się też paramodulacji. Warto zaznaczyć, że "ogólny" język I rzędu jest nierozstrzygalny. W szczególności nie istnieje algorytm, który dla ogólnego języka I rzędu może określić, czy dane zdanie jest w nim prawdziwe, czy nie. Istnieją jednak "szczególne" języki I rzędu, które są rozstrzygalne. Przykładem rozstrzygalnego języka I rzędu może być arytmetyka liczb rzeczywistych, co udowodnił Alfred Tarski. Do weryfikacji zdań o liczbach rzeczywistych służy metoda eliminacji kwantyfikatorów.

[edytuj] Zobacz też

• przegląd zagadnień z zakresu matematyki
• rachunek lambda
• CADE
• CASC
• subsumpcja
• unifikacja
• term
• indeksowanie termów
• system wspomagający dowodzenie twierdzeń
• system Mizar

jestesmysuper PODCAST MUSIC na naszej stronie

Nowość na naszej stronie. Od dziś bedziemy promować nowych artystów udostępniając ich utwory wystarczy subskrybować nasz kanał RSS by móc pobierać najnowsze kawałki. W dniu dzisiejszym kawałki twórcy muzyki Trance AmbahJak AmbahJaK - Dazchust AmbahJaK - Treetashki AmbahJaK - Float My Boolean

jestesmysuper najnowsze wieści z prac nad stroną

Zajmujemy bardzo dobre pozycje we wszystkich wyszukiwarkach ... Najnowsze informacje o pozycji strony jestesmysuper grupy Jungle is Massive. Kolejne naruszenia regulaminu konkursu.

jestesmysuper kolejna wiadomosc w naszym kanale

kanał RSS jest rozwijany dodajemy kolejną wiadomośc w naszym kanale

Jestesmysuper - Jungle is Massive RSS Start kanału

jestesmysuper RSS to najnowszy kanał RSS grupy Jungle is Massive. Serdecznie zapraszamy do dodawania naszego kanału. Najnowsze informacje i newsy z naszej strony www w twojej przeglšdarce lub readerze kanałów RSS.