Model Checking with SAT and SMT

Model Checking with SAT and SMT

位教师：Hao Zheng

访问权限由 Coursera Learning Team 提供

3个模块

深入了解一个主题并学习基础知识。

初级等级

推荐体验

1 周完成

在 10 小时一周

灵活的计划

自行安排学习进度

3个模块

深入了解一个主题并学习基础知识。

初级等级

推荐体验

1 周完成

在 10 小时一周

灵活的计划

自行安排学习进度

您将学到什么

Describe the core principles of Propositional Satisfiability and Satisfiability Modulo Theories, including key techniques used for efficient solving
Explain an encoding method to translate Boolean circuits into Conjunctive Normal Form (CNF)
Describe bounded model checking of transition systems using SAT or SMT
Describe techniques to complement SAT-based bound model checking to make it complete

您将获得的技能

要了解的详细信息

可分享的证书

添加到您的领英档案

作业

10 项作业

授课语言：英语（English）

了解顶级公司的员工如何掌握热门技能

了解关于 Coursera for Business 的更多信息

Petrobras, TATA, Danone, Capgemini, P&G 和 L'Oreal 的徽标

该课程共有3个模块

This course introduces the fundamentals of model checking techniques based on using SAT (Propositional Satisfiability) solving and SMT (Satisfiability Modulo Theories) solving. You will learn basic concepts of propositional SAT solving, including conflict-driven clause learning (CDCL), proof methods, and theory-specific solvers, and concepts of encoding a model checking problem as a SAT solving problem. Topics include introduction to modern propositional SAT solving techniques, encoding Boolean circuits to Conjunctive Normal Form (CNF), bounded and unbounded model checking, and basic introduction to SMT solving. This course is Ideal for those seeking to understand SAT-based model checking and apply it in practical scenarios.

This course can be taken for academic credit as part of CU Boulder’s Master of Science in Electrical and Computer Engineering (MS-ECE) degree offered on the Coursera platform. The degree offers targeted courses, short 8-week sessions, and pay-as-you-go tuition. Admission is based on performance in three preliminary courses, not academic history. CU degrees on Coursera are ideal for recent graduates or working professionals. Learn more: MS in Electrical and Computer Engineering: https://hua.dididi.sbs/degrees/msee-boulder

This module introduces basic concepts and core techniques and procedures within modern propositional satisfiability solving, including resolution, Conflict-Driven Clause Learning (CDCL), Fast Deduction, and some features of SAT useful for problem solving. By examining these strategies, students will gain a foundational understanding of how modern SAT solvers analyze, deduce, and verify propositional formulae. Each lesson builds on practical examples to demonstrate how these methods contribute to modern SAT solver efficiency, reliability, and scalability.

涵盖的内容

16个视频3篇阅读材料3个作业

16个视频总计125分钟

Introduction to Boolean Satisfiability Problem 9分钟
Conjunctive Normal Form (CNF) 7分钟
Basic Concepts of Resolution 11分钟
Finding Satisfying Assignments 11分钟
Introduction to the CDCL Algorithm 10分钟
Overview of CDCL Algorithm 8分钟
CDCL Illustration 11分钟
Learned Clause Minimization 7分钟
Fast Deduction - Introduction 5分钟
Two Matched Literals 6分钟
Computing UNSAT Cores: Part 1 6分钟
Computing UNSAT Cores: Part 2 6分钟
Enumerating Satisfying Assignments: Part 1 7分钟
Enumerating Satisfying Assignments: Part 2 4分钟
Enumerating Satisfying Assignments: Part 3 6分钟
Tseitin's Transformation 13分钟

3篇阅读材料总计21分钟

Course Updates and Accessibility Support 1分钟
Non-Credit Students: Welcome and Where to Find Help 10分钟
Supplemental Reading 10分钟

3个作业总计45分钟

Motivation of Verification 15分钟
Formal Verification and Model Checking 15分钟
SAT-based Problem Solving 15分钟

This module dives into SAT-based model checking techniques. Lessons cover basic concepts of bounded model checking including bounded encodings of models and LTL formulas, and methods to complement BMC to make it complete.

涵盖的内容

12个视频1篇阅读材料3个作业

12个视频总计121分钟

Introduction to Bounded Model Checking 11分钟
Basic BMC Workflow 8分钟
Symbolic Representation of Transition Systems: Refreshment 9分钟
Symbolic Encoding of BMC 7分钟
Example of Symbolic BMC 9分钟
Bounded LTL Semantics Without a Loop 17分钟
Encoding of LTL on Bounded Path Without a Loop 7分钟
Encoding of LTL on Bounded Path With a Loop 14分钟
Completeness Thresholds 9分钟
Inductive Invariants and K-Induction 10分钟
Interpolation-Based Model Checking 9分钟
Preimage Computation Using SAT Enumeration 9分钟

1篇阅读材料总计45分钟

Supplemental Reading 45分钟

3个作业总计45分钟

Bounded Model Checking 15分钟
LTL for Bounded Model Checking 15分钟
Completeness for Bounded Model Checking 15分钟

This module introduces the fundamental concepts and techniques of Satisfiability Modulo Theories (SMT), an extension of satisfiability solving to more expressive logical domains such as Integer Difference Logic (IDL) and Equality with Uninterpreted Functions (EUF). It also covers methods for combining different theories, including the Nelson-Oppen procedure used in SMT solving. The lessons emphasize how SMT solvers handle diverse theories to efficiently solve complex logical and mathematical problems.