Asystent sprawdzający to aplikacja, która pomaga ludziom tworzyć dowody sprawdzane maszynowo.
Podczas kodowania logiki w asystencie dowodu, takim jak Coq lub Isabelle, należy dokonać wyboru między użyciem płytkiego a głębokiego osadzenia. W płytkim osadzaniu formuły logiczne są zapisywane bezpośrednio w logice twierdzenia twierdzącego, podczas gdy w głębokim osadzaniu formuły logiczne są...
Pytanie: Jak działają „taktyki” w asystentach dowodowych? Wydają się być sposobami na określenie, jak przepisać termin na równoważny (dla pewnej definicji „równoważnego”). Przypuszczalnie istnieją formalne zasady dotyczące tego, w jaki sposób mogę dowiedzieć się, czym one są i jak działają? Czy...
Przeglądam notatki z kursu na CIS 500: podstawy oprogramowania i ćwiczenia są świetną zabawą. Jestem dopiero na trzecim zestawie ćwiczeń, ale chciałbym dowiedzieć się więcej o tym, co się dzieje, gdy używam taktyki do udowodnienia, żeforall (n m : nat), n + n = m + m -> n =...
Większość (wszystkich?) Dowódców ma czasami naprawione błędy związane z dźwiękiem. Jednak z tych, które widziałem, błędy te zwykle trudno jest przypadkowo natknąć się, a wyniki udowodnione przed naprawieniem błędu zwykle są wstrzymywane po naprawie. Trzy pytania, w kolejności według siły: Czy...
Załóżmy, że chciałem sformalizować dowód Turinga dotyczący problemu zatrzymania, aby maszyna mogła to sprawdzić. Niektóre ze znanych automatycznych systemów dowodzenia twierdzeń obejmują Mizar, Coq i HOL4. Pobrałem i eksperymentowałem z Coq, ale nie ma biblioteki dla maszyn Turinga. Sam pomyślałem...
Wygląda na to, że George Gonthier i jego współpracownicy zakończyli formalizację Twierdzenia o nieparzystym porządku . We wcześniejszej pracy nad twierdzeniem o czterech kolorach Gonthier wynalazł szereg nowych algorytmów (głównie wariantów BDD i algorytmów grafowych), które były szczególnie...
W artykule „KOMPLEKSOWOŚĆ PROBLEMÓW Z ZADOWOLENIEM” Tomasza J. Schaefera autor wspomniał, że This raises the intriguing possibility of computer-assisted NP-completeness proofs. Once the researcher has established the basic framework for simulating conjunctions of clauses, the relational complexity...
Czy istnieje sposób na udowodnienie następującego twierdzenia w Coq? Theorem bool_pirrel : forall (b : bool) (p1 p2 : b = true), p1 = p2. EDYCJA : Próba krótkiego wyjaśnienia „czym jest nieistotność dowodu” (popraw mnie, jeśli się mylę lub nieścisłość) Podstawowym założeniem jest to, że w...
Czy jest jakiś realizowany projekt formalnej weryfikacji twierdzeń i dowodów teorii złożoności przy użyciu asystenta dowodu, takiego jak Coq? Czy są jakieś
Często chcemy zdefiniować obiekt zgodnie z pewnymi regułami wnioskowania. Zasady te oznaczają funkcję generowania F , która gdy jest monotonna, daje się przynajmniej stały punkt | j F . Bierzemy A : = μ F być „definicja indukcyjna” od A . Co więcej, monotoniczność F pozwala nam rozumować za pomocą...
Patrząc na blog dotyczący teorii homotopii, łatwo można znaleźć wiele bibliotek formalizujących większość teorii typów homotopii w Agdzie i Coq. Czy ktoś wie, czy istnieje podobna próba sformalizowania HoTT w Idris
Próbując udowodnić pewne podstawowe właściwości przy użyciu typów koindukcyjnych w Coq, ciągle napotykam na następujący problem i nie mogę go obejść. Wydzieliłem problem na prosty skrypt Coq w następujący sposób. Rodzaj Drzewo definiuje ewentualnie nieskończone drzew z gałęziami oznaczonych...
Jak przekonać Coq, że podana poniżej funkcja rekurencyjna kończy się? Funkcja przyjmuje dwa argumenty indukcyjne. Intuicyjnie rekursja kończy się, ponieważ którykolwiek argument jest rozkładany. W szczególności funkcja przyjmuje dwa drzewa jako dane wejściowe. Inductive Tree := | Tip: Tree | Bin:...
Biorąc pod uwagę tematy poruszane na konferencji, takie jak STOC, czy naukowcy zajmujący się algorytmem lub złożonością aktywnie korzystają z COQ lub Isabelle? Jeśli tak, to jak wykorzystują go w swoich badaniach? Zakładam, że większość ludzi nie użyłaby takich narzędzi, ponieważ dowody byłyby zbyt...
Chciałbym pisać matematyczne dowody przy pomocy asystenta dowodu. Wszystko zostanie napisane przy użyciu logiki pierwszego rzędu (z równością) i naturalnej dedukcji. Tłem jest teoria mnogości (ZF). Na przykład, jak mogę napisać następujący dowód? Aksjomat:∀ x ∀ y( x = y↔ ∀ z( z∈ x ↔ z. Y)...
Programuję od kilku lat, ale nie znam teoretycznej CS. Niedawno próbowałem uczyć się języków programowania, a w ramach tego sprawdzania i wnioskowania. Moje pytanie brzmi: jeśli spróbuję napisać program wnioskowania i sprawdzania języka programowania i chcę udowodnić, że mój program do sprawdzania...