[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

# Re: [tlaplus] Proving partial correctness of the SetGCD algorithm in the hyperbook

 Hard to tell without being able to replay the proof. (If you send me your TLA module by private email I can have a look.)Note that ax2 is subsumed by ax1 since it asserts that some particular singleton set is finite.Regards,StephanOn 24 Jun 2016, at 20:30, Jens Weber wrote:Thanks Stephan.Yes, I also thought that I needed some axioms regarding removing and adding elements to finite sets. I didn't know about the FiniteSetsTheorem module though. I tried to define my own. Below is my current theorem. I'll look into the standard module now (but would still be interested in understanding why my axioms don't work.)THEOREM ax1 == ASSUME NEW x \in Int PROVE IsFiniteSet({x})THEOREM ax2 == ASSUME NEW x \in Int, NEW y \in Int PROVE IsFiniteSet({y-x})THEOREM ax3 == ASSUME NEW S1, NEW S2,                      /\ IsFiniteSet(S1)                      /\ IsFiniteSet(S2)               PROVE /\ IsFiniteSet(S1 \ S2)                     /\ IsFiniteSet(S1 \cup S2)THEOREM Spec => []PartialCorrectness<1>1. Init => SInv    BY InputOK DEF Init, SInv, TypeOK, PartialCorrectness<1>2. SInv /\ [Next]_vars => SInv'  <2> SUFFICES ASSUME SInv /\ [Next]_vars               PROVE  SInv'    OBVIOUS  <2>1. TypeOK'    <3>1. CASE Lbl_1      <4>1. (S \subseteq Nat \{0})'        BY <3>1 DEF SInv, TypeOK, Next, vars, Lbl_1      <4>2. (S # {})'        BY <3>1 DEF SetGCD, SInv, TypeOK, Next, vars, Lbl_1, SetMax, Divides      <4>3. IsFiniteSet(S)'        BY <3>1, ax1, ax2, ax3 DEF SInv, TypeOK, Next, vars, Lbl_1      <4>4. QED        BY <4>1, <4>2, <4>3 DEF TypeOK          <3>2. CASE pc = "Done" /\ UNCHANGED vars      BY <3>2 DEF PartialCorrectness, SInv, TypeOK, vars    <3>3. CASE UNCHANGED vars      BY <3>3 DEF Init, SetGCD, PartialCorrectness, SInv, TypeOK, Next, vars    <3>4. QED      BY <3>1, <3>2, <3>3 DEF Next      <2>2. (SetGCD(S) = SetGCD(T))'    BY InputOK DEF Init, SInv, TypeOK, Next, vars  <2>3. PartialCorrectness'    BY InputOK DEF Init, SInv, TypeOK, Next, vars  <2>4. QED    BY <2>1, <2>2, <2>3 DEF SInv    <1>3. SInv => PartialCorrectness    BY DEF SInv, PartialCorrectness<1>4. QED    BY <1>1, <1>2, <1>3, PTL DEF Spec    On Friday, June 24, 2016 at 11:15:34 AM UTC-7, Stephan Merz wrote:I haven't tried writing a formal proof of that algorithm, and it is not entirely clear to me where you are stuck.The (type) invariant contains the conjunct  IsFiniteSet(S)and you need to prove that this predicate is preserved by action Lbl_1. You'll need to use the standard module FiniteSetTheorems contained in the TLAPS distribution. (If you haven't done so yet, you should add the corresponding directory to the Toolbox search path.) In particular, the lemmas FS_AddElement and FS_RemoveElement will be useful.Hope this helps,StephanOn 24 Jun 2016, at 02:55, Jens Weber wrote:Hello TLA community,I am trying to prove partial correctness of the SetGCD algorithm in the hyperbook - but I am not successful. Does anybody have a solution here? I am currently stuck on showing that S' is a finite set. ThanksJens -- You received this message because you are subscribed to the Google Groups "tlaplus" group. To unsubscribe from this group and stop receiving emails from it, send an email to tlaplus+u...@googlegroups.com. To post to this group, send email to tla...@xxxxxxxxxxxxxxxx. Visit this group at https://groups.google.com/group/tlaplus. For more options, visit https://groups.google.com/d/optout. -- You received this message because you are subscribed to the Google Groups "tlaplus" group. To unsubscribe from this group and stop receiving emails from it, send an email to tlaplus+u...@xxxxxxxxxxxxxxxx. To post to this group, send email to tla...@xxxxxxxxxxxxxxxx. Visit this group at https://groups.google.com/group/tlaplus. For more options, visit https://groups.google.com/d/optout.

• Follow-Ups:
• References: