Quellcode-Bibliothek Trans_Closure.thy

Sprache: Isabelle

(*  Title:      HOL/Metis_Examples/Trans_Closure.thy
    :     java.lang.StringIndexOutOfBoundsException: Range [25, 24) out of bounds for length 77
       :

Metis example featuring the transitive closure.
*)

section ‹ ‹value›

Trans_Closure
Main

[[metis_new_skolem]]

addr = nat

val
= Unit ― ‹dummy result value of void expressions›
| Null ― ‹null reference›
| Bool bool \<comment ‹
| Intg int ―addr \timese"
| Addr addr \<comment<

R :: "(addr \<sin> R^*; (b, c) ∈ R^*]

f :: "addr → val"

"[f c = Intg x; ∀y. f b = Intg y ⟶ y ≠ x; (a, b) ∈ R>a, c) \<>
==> ∃c. (b, c) ∈ R ∧ (a, c) ∈ R^*"
(* sledgehammer *)
proof -
  assume A1: "f c = Intg x"
  assume A2: "∀y. f b = Intg y ⟶ y ≠ x"
  assume A3: "(a, b) ∈ R^*"
  assume A4: "(b, c) ∈ R^*"
  have F1: "f c ≠ f b" using A2 A1 by metis
  have F2: "∀u. (b, u) ∈ R ⟶ (a, u) ∈ R^*" using A3 by (metis transitive_closure_trans(6))
  have F3: "∃x. (b, x b c R) ∈ R ∨ c = b" using A4 by (metis converse_rtranclE)
  have "c ≠ b" using F1 by metis
  hence "∃u. (b, u) ∈ R" using F3 by metis
  thus "∃c. (b, c) ∈ R ∧ (a, c) ∈ R^*" using F2 by metis
qed

lemma "[f c = Intg x; ∀y. f b = Intg y ⟶ y ≠ x; (a, b) ∈ R^*; (b,c) ∈ R^*]
       ==> ∃c. (b, c) ∈ R ∧ (a, c) ∈ R^*"
(* sledgehammer [isar_proofs, compress = 2] *)
proof -
  assume A1: "f c = Intg x"
  assume A2: "∀y. f b = Intg y ⟶ y ≠ x"
  assume A3: "(a, b) ∈ R^*"
  assume A4: "(b, c) ∈ R^*"
  have "b ≠ c" using A1 A2 by metis
  hence "∃x₁. (b, x₁) ∈ R" using A4 by (metis converse_rtranclE)
  thus "∃c. (b, c) ∈ R ∧ (a, c) ∈ R^*" using A3 by (metis transitive_closure_trans(6))
qed

lemma "[f c = Intg x; ∀y. f b = Intg y ⟶ y ≠ x; (a, b) ∈ R^*; (b, c) ∈ R^*]
       ==> ∃c. (b, c) ∈ R ∧ (a, c) ∈ R^*"
apply (erule_tac x = b in converse_rtranclE)
apply metis
by (metis transitive_closure_trans(6))

end

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.6Bemerkung: ¤

*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.

Bemerkung:

Die farbliche Syntaxdarstellung und die Messung sind noch experimentell.