Suchen Untersuchung
mit Columbo Integrität von
Datenbanken Interaktion und
Portierbarkeit Haftungshinweis

Bemerkung: zur Agenda Produktseite wechseln Projekt Beratung

Suchen Analytik Modellierung Sprachen Algebra Logik Hardware Denken Kreativität

Zusammenhänge Gesellschaft Wirtschaft Branche Firma


products/Sources/formale Sprachen/Isabelle/HOL/Data_Structures/ (Openclaw AI Version 22^©) Datei vom 16.11.2025 mit Größe 2 kB

Quellcode-Bibliothek Sorted_Less.thy Sprache: Isabelle

(* Author: Tobias Nipkow *)

section ‹›

theory Sorted_Less
imports Less_False
begin

hide_const sorted

text ‹Is a list sorted without duplicates, i.e., wrt ‹<\<>

sorted :: "'a::linorder list → bool" where
sorted ≡ sorted_wrt (<)"

sorted_wrt_Cons = sorted_wrt.simps(2)

‹The definition of const‹sorted_wrt› relates each element to all the elements after it.
causes a blowup of the formulas. Thus we simplify matters by only comparing adjacent elements.›

sorted_wrt.simps(2)[simp del]
sorted_wrt1[simp] sorted_wrt2[OF transp_on_less, simp]

sorted_cons: "sorted (x#xs) ==> sorted xs"
(simp add: sorted_wrt_Cons)

sorted_cons': "ASSUMPTION (sorted (x#xs)) ==> sorted xs"
(rule ASSUMPTION_D [THEN sorted_cons])

sorted_snoc: "sorted (xs @ [y]) ==> sorted xs"
(simp add: sorted_wrt_append)

sorted_snoc': "ASSUMPTION (sorted (xs @ [y])) ==> sorted xs"
(rule ASSUMPTION_D [THEN sorted_snoc])

sorted_mid_iff:
"sorted(xs @ y # ys) = (sorted(xs @ [y]) ∧ sorted(y # ys))"
(fastforce simp add: sorted_wrt_Cons sorted_wrt_append)

sorted_mid_iff2:
"sorted(x # xs @ y # ys) =
(sorted(x # xs) ∧ x < y ∧ sorted(xs @ [y]) ∧ sorted(y # ys))"
(fastforce simp add: sorted_wrt_Cons sorted_wrt_append)

sorted_mid_iff': "NO_MATCH [] ys ==>
sorted(xs @ y # ys) = (sorted(xs @ [y]) ∧ sorted(y # ys))"
(rule sorted_mid_iff)

sorted_lems = sorted_mid_iff' sorted_mid_iff2 sorted_cons' sorted_snoc'

‹Splay trees need two additional const‹sorted› lemmas:›

sorted_snoc_le:
"ASSUMPTION(sorted(xs @ [x])) ==> x ≤ y ==> sorted (xs @ [y])"
(auto simp add: sorted_wrt_append ASSUMPTION_def)

sorted_Cons_le:
"ASSUMPTION(sorted(x # xs)) ==> y ≤ x ==> sorted (y # xs)"
(auto simp add: sorted_wrt_Cons ASSUMPTION_def)

Messung V0.5 in Prozent

¤ Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.0.92Bemerkung: ¤

*Bot Zugriff

Wurzel

Suchen

PVS Prover

Isabelle Prover

NIST Cobol Testsuite

Cephes Mathematical Library

Vienna Development Method

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.