Formalizing Pick's Theorem in Isabelle/HOL

被引:0
|
作者
Binder, Sage [1 ]
Kosaian, Katherine [2 ]
机构
[1] Univ Iowa, Iowa City, IA 52242 USA
[2] Iowa State Univ, Ames, IA 50011 USA
来源
INTELLIGENT COMPUTER MATHEMATICS, CICM 2024 | 2024年 / 14690卷
基金
美国国家科学基金会;
关键词
Pick's theorem; Isabelle/HOL; formalization; geometry;
D O I
10.1007/978-3-031-66997-2_7
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We formalize Pick's theorem for finding the area of a simple polygon whose vertices are integral lattice points. We are inspired by John Harrison's formalization of Pick's theorem in HOL Light, but tailor our proof approach to avoid a primary challenge point in his formalization, which is proving that any polygon with more than three vertices can be split (in its interior) by a line between some two vertices. We detail the approach we use to avoid this step and reflect on the pros and cons of our eventual formalization strategy. We use the theorem prover Isabelle/HOL, and our formalization involves augmenting the existing geometry libraries in various foundational ways (e.g., by adding the definition of a polygon and formalizing some key properties thereof).
引用
收藏
页码:109 / 126
页数:18
相关论文
共 50 条
  • [41] Random testing in Isabelle/HOL
    Berghofer, S
    Nipkow, T
    PROCEEDINGS OF THE SECOND INTERNATIONAL CONFERENCE ON SOFTWARE ENGINEERING AND FORMAL METHODS, 2004, : 230 - 239
  • [42] Nominal techniques in Isabelle/HOL
    Urban, Christian
    JOURNAL OF AUTOMATED REASONING, 2008, 40 (04) : 327 - 356
  • [43] A comparison of PVS and Isabelle/HOL
    Griffioen, D
    Huisman, M
    THEOREM PROVING IN HIGHER ORDER LOGICS, 1998, 1479 : 123 - 142
  • [44] Data Refinement in Isabelle/HOL
    Haftmann, Florian
    Krauss, Alexander
    Kuncar, Ondrej
    Nipkow, Tobias
    INTERACTIVE THEOREM PROVING, ITP 2013, 2013, 7998 : 100 - 115
  • [45] From LCF to Isabelle/HOL
    Paulson, Lawrence C.
    Nipkow, Tobias
    Wenzel, Makarius
    FORMAL ASPECTS OF COMPUTING, 2019, 31 (06) : 675 - 698
  • [46] Linear Resources in Isabelle/HOL
    Smola, Filip
    Fleuriot, Jacques D.
    JOURNAL OF AUTOMATED REASONING, 2024, 68 (02)
  • [47] Nominal techniques in Isabelle/HOL
    Urban, C
    Tasson, C
    AUTOMATED DEDUCTION - CADE-20, PROCEEDINGS, 2005, 3632 : 38 - 53
  • [48] Markov Processes in Isabelle/HOL
    Hoelz, Johannes
    PROCEEDINGS OF THE 6TH ACM SIGPLAN CONFERENCE ON CERTIFIED PROGRAMS AND PROOFS, CPP'17, 2017, : 100 - 111
  • [49] A Consistent Foundation for Isabelle/HOL
    Kuncar, Ondrej
    Popescu, Andrei
    INTERACTIVE THEOREM PROVING, 2015, 9236 : 234 - 252
  • [50] A Consistent Foundation for Isabelle/HOL
    Ondřej Kunčar
    Andrei Popescu
    Journal of Automated Reasoning, 2019, 62 : 531 - 555