Interactive Theorem Proving in Software Verification
Created byJonas M
17 views0 downloads

Interactive Theorem Proving in Software Verification

College/UniversityMathComputer Science5 days
This project-based learning experience for college students explores the integration of propositional and predicate logic, automata, and formal languages in software verification using formal methods and theorem proving. Students engage in interactive activities, such as a design sprint and logic foundations refresher, to deepen their understanding of these principles and their applications. They will build finite automaton models, analyze software verification processes, and reflect on their learning experiences, with assessments focusing on applying and innovating using these concepts.
Theorem ProvingSoftware VerificationFormal MethodsAutomataPredicate LogicCollege-LevelFormal Modeling
Want to create your own PBL Recipe?Use our AI-powered tools to design engaging project-based learning experiences for your students.
📝

Inquiry Framework

Question Framework

Driving Question

The overarching question that guides the entire project.How can the principles of propositional and predicate logic, along with automata and formal languages, be integrated to employ formal methods and theorem proving in enhancing software verification processes?

Essential Questions

Supporting questions that break down major concepts.
  • What are the main principles and concepts of propositional and predicate logic that are essential for understanding theorem provers?
  • How do automata and formal languages contribute to the field of software verification and theorem proving?
  • In what ways do formal methods improve the software development lifecycle?
  • How can the concepts learned in formal modelling and specification be applied to real-world software verification problems?
  • What role does decidability play in the context of formal methods and theorem proving?

Standards & Learning Goals

Learning Goals

By the end of this project, students will be able to:
  • Students will be able to apply principles of propositional and predicate logic in the process of software verification using theorem proving.
  • Students will learn to integrate knowledge of automata and formal languages into the development and verification of software solutions.
  • Individuals will explore the improvement of software development processes via the application of formal methods.
  • Learners will identify and solve real-world software verification problems by applying formal modeling and specification techniques.
  • Students will analyze the role of decidability in the context of theorem proving and formal methods.

Common Core Standards

CCSS.MATH.CONTENT.HSN-Q.A.1
Supporting
Use units as a way to understand problems and to guide the solution of multi-step problems; choose and interpret units consistently in formulas; choose and interpret the scale and the origin in graphs and data displays.Reason: Understanding and application of units and mathematical structures are crucial for reasoning about automata, formal languages, and their role in software verification.
CCSS.MATH.CONTENT.HSA-REI.C.5
Primary
Prove theorems involving algebraic equations.Reason: Proving theorems is directly related to the use of theorem provers in software verification. Establishing logical consistency and correctness is key in this context.
CCSS.MATH.CONTENT.HSA-REI.C.10
Supporting
Understand that the graph of an equation in two variables is the set of all its solutions plotted in the coordinate plane, often forming a curve (which could be a line).Reason: Graphing and understanding representations are important for visualizing concepts related to logical structures and automata.

Computer Science Guidelines

COMP.SCI.1.1
Primary
Understanding of basic algorithms and their application in software design.Reason: Application of algorithms, particularly those derived from formal methods, is a core part of enhancing software verification processes.

Next Generation Science Standards

NGSS.PS4-5
Secondary
Understand that waves have energy that can be transferred and interact with matter, fostering the broader understanding of interactions in systematic structures.Reason: While this concept is more peripheral, understanding interactions within systems is marginally supportive when considering complex system interactions in formal methods.

Entry Events

Events that will be used to introduce the project to students

Theorem Proving Design Sprint

Coordinate a design sprint where students collaborate to develop a software application from scratch, implementing theorem proving at each stage of development to ensure correctness and interoperability. This entry event is a direct application of formal methods from their courses.
📚

Portfolio Activities

Portfolio Activities

These activities progressively build towards your learning goals, with each submission contributing to the student's final portfolio.
Activity 1

Logic Foundations Refresher

In this activity, students review and consolidate their understanding of propositional and predicate logic, essential for theorem proving.

Steps

Here is some basic scaffolding to help students complete the activity.
1. Review course materials related to propositional and predicate logic.
2. Engage in problem-solving exercises to reinforce logic concepts.
3. Participate in group discussions to clarify understanding and misconceptions.

Final Product

What students will submit as the final product of the activityA set of solved logic problems and a summary report on key logic concepts.

Alignment

How this activity aligns with the learning objectives & standardsSupports CCSS.MATH.CONTENT.HSA-REI.C.5 by reinforcing the understanding necessary to prove theorems.
Activity 2

Automata and Formal Language Exploration

Students will explore the role of automata and formal languages in software verification through practical exercises.

Steps

Here is some basic scaffolding to help students complete the activity.
1. Study examples of automata and their applications in computing.
2. Create a finite automaton model using a software tool.
3. Analyze how formal languages are used in the software verification process.

Final Product

What students will submit as the final product of the activityA digital model of a finite automaton and an analysis report outlining their application in software.

Alignment

How this activity aligns with the learning objectives & standardsSupports CCSS.MATH.CONTENT.HSN-Q.A.1 by using mathematical structures to guide solutions.
🏆

Rubric & Reflection

Portfolio Rubric

Grading criteria for assessing the overall project portfolio

Interactive Theorem Proving and Software Verification Rubric

Category 1

Conceptual Understanding

Evaluation of student's ability to understand and apply core concepts of propositional and predicate logic, automata, and formal languages effectively.
Criterion 1

Propositional and Predicate Logic Mastery

Measures the depth of understanding and application of logic in theorem proving.

Exemplary
4 Points

Demonstrates sophisticated understanding of propositional and predicate logic, applying these concepts innovatively in solving complex problems.

Proficient
3 Points

Shows thorough understanding of propositional and predicate logic, applying them appropriately to solve problems.

Developing
2 Points

Shows emerging understanding of propositional and predicate logic with inconsistent application in problem-solving.

Beginning
1 Points

Shows initial understanding of logic principles with minimal or incorrect application.

Criterion 2

Automata and Formal Language Integration

Assesses how well students integrate knowledge of automata and formal languages within software verification.

Exemplary
4 Points

Integrates automata and formal languages seamlessly in innovative software verification solutions.

Proficient
3 Points

Effectively integrates automata and formal languages into software verification with clear application.

Developing
2 Points

Integrates automata and formal languages with partial success in software verification.

Beginning
1 Points

Struggles to integrate automata and formal languages within software verification processes.

Category 2

Application and Innovation

Assessment of student ability to apply learned concepts to real-world scenarios and innovate within the software development process.
Criterion 1

Real-world Application and Problem Solving

Evaluates the ability to apply formal methods, modelling, and specifications to solve real-world software verification problems.

Exemplary
4 Points

Applies formal methods with innovation and effectiveness, solving complex real-world problems exemplary.

Proficient
3 Points

Applies formal methods with effective problem-solving typical of encountered verification issues.

Developing
2 Points

Attempts to apply formal methods with emerging competency, resulting in varied problem-solving effectiveness.

Beginning
1 Points

Shows initial attempts to apply formal methods with limited success in addressing verification problems.

Criterion 2

Innovative Use of Theorem Proving

Examines the innovative use of theorem proving in developing software solutions.

Exemplary
4 Points

Employs theorem proving with exceptional creativity and depth, enhancing software solutions.

Proficient
3 Points

Uses theorem proving effectively in creating robust software solutions.

Developing
2 Points

Incorporates theorem proving with basic innovation but needs further development.

Beginning
1 Points

Barely implements theorem proving in software solutions, requiring foundational enhancement.

Category 3

Collaboration and Communication

Evaluates student interaction, communication, and teamwork in collaborative software development settings.
Criterion 1

Team Collaboration

Measures effectiveness of collaboration in group activities such as design sprints.

Exemplary
4 Points

Exhibits leadership and fosters a highly collaborative and productive team environment.

Proficient
3 Points

Works effectively within a team, contributing valuable input and support.

Developing
2 Points

Participates in team activities with occasional contributions, requiring prompting.

Beginning
1 Points

Reluctantly participates in team settings, requiring significant support and encouragement.

Reflection Prompts

End-of-project reflection questions to get students to think about their learning
Question 1

How has your understanding of propositional and predicate logic evolved through this course, particularly in the context of theorem proving?

Text
Required
Question 2

Rate your confidence in applying formal methods to solve real-world software verification problems.

Scale
Required
Question 3

Which entry events or activities did you find most beneficial for understanding the integration of theorem proving in software verification? Why?

Text
Required
Question 4

Consider the role decidability played in your learning. How well do you understand this concept in relation to formal methods and theorem proving?

Scale
Optional
Question 5

What challenges did you encounter when working with formal modeling and specification techniques? How did you overcome them?

Text
Required