Model Checking with SAT and SMT

Sparen Sie mit 40% Rabatt auf 3 Monate Coursera Plus bei den Fähigkeiten, die Sie zum Strahlen bringen. Jetzt sparen

kurs ist nicht verfügbar in Deutsch (Deutschland)

Wir übersetzen es in weitere Sprachen.

Model Checking with SAT and SMT

Dozent: Hao Zheng

Bei enthalten

Mehr erfahren

3 Module

Verschaffen Sie sich einen Einblick in ein Thema und lernen Sie die Grundlagen.

Stufe Anfänger

Empfohlene Erfahrung

1 Woche zu vervollständigen

unter 10 Stunden pro Woche

Flexibler Zeitplan

In Ihrem eigenen Lerntempo lernen

3 Module

Verschaffen Sie sich einen Einblick in ein Thema und lernen Sie die Grundlagen.

Stufe Anfänger

Empfohlene Erfahrung

1 Woche zu vervollständigen

unter 10 Stunden pro Woche

Flexibler Zeitplan

In Ihrem eigenen Lerntempo lernen

Was Sie lernen werden

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

Kompetenzen, die Sie erwerben

Kategorie: Graph Theory

Wichtige Details

Zertifikat zur Vorlage

Zu Ihrem LinkedIn-Profil hinzufügen

Kürzlich aktualisiert!

November 2025

Bewertungen

10 Aufgaben

Unterrichtet in Englisch

Erfahren Sie, wie Mitarbeiter führender Unternehmen gefragte Kompetenzen erwerben.

Weitere Informationen zu Coursera für Unternehmen

Logos von Petrobras, TATA, Danone, Capgemini, P&G und L'Oreal

In diesem Kurs gibt es 3 Module

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://www.coursera.org/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.

Das ist alles enthalten

16 Videos3 Lektüren3 Aufgaben

16 VideosInsgesamt 125 Minuten

Introduction to Boolean Satisfiability Problem9 Minuten
Conjunctive Normal Form (CNF)7 Minuten
Basic Concepts of Resolution11 Minuten
Finding Satisfying Assignments11 Minuten
Introduction to the CDCL Algorithm10 Minuten
Overview of CDCL Algorithm8 Minuten
CDCL Illustration11 Minuten
Learned Clause Minimization7 Minuten
Fast Deduction - Introduction5 Minuten
Two Matched Literals6 Minuten
Computing UNSAT Cores: Part 16 Minuten
Computing UNSAT Cores: Part 2 6 Minuten
Enumerating Satisfying Assignments: Part 17 Minuten
Enumerating Satisfying Assignments: Part 24 Minuten
Enumerating Satisfying Assignments: Part 36 Minuten
Tseitin's Transformation13 Minuten

3 LektürenInsgesamt 21 Minuten

Course Updates and Accessibility Support1 Minute
Non-Credit Students: Welcome and Where to Find Help10 Minuten
Supplemental Reading10 Minuten

3 AufgabenInsgesamt 45 Minuten

Motivation of Verification15 Minuten
Formal Verification and Model Checking15 Minuten
SAT-based Problem Solving15 Minuten

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.

Das ist alles enthalten

12 Videos1 Lektüre3 Aufgaben

12 VideosInsgesamt 121 Minuten

Introduction to Bounded Model Checking11 Minuten
Basic BMC Workflow8 Minuten
Symbolic Representation of Transition Systems: Refreshment9 Minuten
Symbolic Encoding of BMC7 Minuten
Example of Symbolic BMC9 Minuten
Bounded LTL Semantics Without a Loop17 Minuten
Encoding of LTL on Bounded Path Without a Loop7 Minuten
Encoding of LTL on Bounded Path With a Loop14 Minuten
Completeness Thresholds9 Minuten
Inductive Invariants and K-Induction10 Minuten
Interpolation-Based Model Checking9 Minuten
Preimage Computation Using SAT Enumeration9 Minuten

1 LektüreInsgesamt 45 Minuten

Supplemental Reading45 Minuten

3 AufgabenInsgesamt 45 Minuten

Bounded Model Checking15 Minuten
LTL for Bounded Model Checking15 Minuten
Completeness for Bounded Model Checking15 Minuten

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.

Das ist alles enthalten

18 Videos1 Lektüre4 Aufgaben

18 VideosInsgesamt 118 Minuten

Introduction to SMT Solving4 Minuten
Approaches to SMT Solving8 Minuten
Generic Architecture of Lazy SMT Solving4 Minuten
Example of SMT Solving6 Minuten
Features of Lazy SMT Solving7 Minuten
Introduction to SMT Solver Z38 Minuten
An Example of Bounded Model Checking Using Z320 Minuten
Introduction to Integer Difference Logic8 Minuten
Example: Integer Difference Logic5 Minuten
Introduction to Linear Integer Arithmetic 8 Minuten
Example: Linear Integer Arithmetic 7 Minuten
Introduction to Equality and Uninterpreted Functions6 Minuten
EUF Theory Solving5 Minuten
Introduction to Theory of Arrays5 Minuten
Example: Introduction to Theory of Arrays2 Minuten
Introduction to Combining Theories6 Minuten
Applying Nelson-Oppen to Combined Theories4 Minuten
Practical Considerations and Optimizations6 Minuten

1 LektüreInsgesamt 10 Minuten

Supplemental Reading10 Minuten

4 AufgabenInsgesamt 60 Minuten

Satisfiability Modulo Theories15 Minuten
Linear Integer Arithmetic15 Minuten
Theory of Equality and Uninterpreted Functions15 Minuten
Combination of Theories15 Minuten

Dozent

Hao Zheng

University of Colorado Boulder

3 Kurse931 Lernende

von

University of Colorado Boulder

Mehr von Algorithms entdecken

Status: Kostenloser Testzeitraum
University of Colorado Boulder
Temporal Logic Model Checking
Kurs
Status: Kostenloser Testzeitraum
University of Colorado Boulder
Introduction to Modeling for Formal Verification
Kurs
28DIGITAL
Automated Reasoning: satisfiability
Kurs
Status: Kostenloser Testzeitraum
University of Colorado Boulder
Fundamentals of Model Checking
Spezialisierung

Warum entscheiden sich Menschen für Coursera für ihre Karriere?

Felipe M.

Lernender seit 2018

„Es ist eine großartige Erfahrung, in meinem eigenen Tempo zu lernen. Ich kann lernen, wenn ich Zeit und Nerven dazu habe.“

Jennifer J.

Lernender seit 2020

„Bei einem spannenden neuen Projekt konnte ich die neuen Kenntnisse und Kompetenzen aus den Kursen direkt bei der Arbeit anwenden.“

Larry W.

Lernender seit 2021

„Wenn mir Kurse zu Themen fehlen, die meine Universität nicht anbietet, ist Coursera mit die beste Alternative.“

Chaitanya A.

„Man lernt nicht nur, um bei der Arbeit besser zu werden. Es geht noch um viel mehr. Bei Coursera kann ich ohne Grenzen lernen.“

Häufig gestellte Fragen

To access the course materials, assignments and to earn a Certificate, you will need to purchase the Certificate experience when you enroll in a course. You can try a Free Trial instead, or apply for Financial Aid. The course may offer 'Full Course, No Certificate' instead. This option lets you see all course materials, submit required assessments, and get a final grade. This also means that you will not be able to purchase a Certificate experience.

When you purchase a Certificate you get access to all course materials, including graded assignments. Upon completing the course, your electronic Certificate will be added to your Accomplishments page - from there, you can print your Certificate or add it to your LinkedIn profile.

Yes. In select learning programs, you can apply for financial aid or a scholarship if you can’t afford the enrollment fee. If fin aid or scholarship is available for your learning program selection, you’ll find a link to apply on the description page.

Weitere Fragen

Besuchen Sie die das Hilfe-Center für Kursteilnehmer.

Finanzielle Unterstützung verfügbar,