Explore

Automated Reasoning: satisfiability

Approx. 25 hours to complete

Save Course

Go to Course

Course Summary

This course teaches the foundations of automated reasoning, with a focus on the Boolean Satisfiability (SAT) problem. Students will learn how to solve problems using SAT solvers and how to encode problems as Boolean formulas. The course also covers applications of automated reasoning in various fields.

Key Learning Points

Learn the fundamental concepts and techniques of automated reasoning
Understand how to encode problems as Boolean formulas
Develop problem-solving skills using SAT solvers

Learning Outcomes

Ability to solve problems using SAT solvers
Understanding of problem encoding as Boolean formulas
Developed problem-solving skills using automated reasoning

Prerequisites or good to have knowledge before taking this course

Basic knowledge of propositional logic
Familiarity with programming concepts

Course Difficulty Level

Intermediate

Course Format

Online
Self-paced

Similar Courses

Logic and Proofs
Discrete Optimization

Notable People in This Field

Georg Gottlob
Moshe Vardi

Related Books

Description

In this course you will learn how to apply satisfiability (SAT/SMT) tools to solve a wide range of problems.

Several basic examples are given to get the flavor of the applications: fitting rectangles to be applied for printing posters, scheduling problems, solving puzzles, and program correctness. Also underlying theory is presented: resolution as a basic approach for propositional satisfiability, the CDCL framework to scale up for big formulas, and the simplex method to deal with linear inequallities. The light weight approach to following this course is just watching the lectures and do the corresponding quizzes. To get a flavor of the topic this may work out fine. However, the much more interesting approach is to use this as a basis to apply SAT/SMT yourself on several problems, for instance on the problems presented in the honor's assignment.

Outline

SAT/SMT basics, SAT examples
General introduction, and an application to poster printing
Introduction to SAT
SMT syntax and tools
Eight queens problem
Binary Arithmetic: addition
Binary Arithmetic: multiplication
Examples from the lecture
Eight queens formula in SMT syntax
Truth table
Carries in binary addition
Binary multiplication

SMT applications
Rectangle fitting
Solving Sudoku
Scheduling
Bounded model checking
Sudoku formula in SMT 2 format
Introduction
Rectangle fitting
Scheduling
Bounded Model Checking
Filling trucks for a magic factory
A sudoku variant
Job scheduling
Program correctness

Theory and algorithms for CNF-based SAT
Resolution
Example of resolution
DPLL
Transforming DPLL to resolution
CDCL basics
CDCL optimizations
Resolution
apply resolution
DPLL
DPLL to resolution

Theory and algorithms for SAT/SMT
Transforming a propositional formula to CNF
The Tseitin transfomation
Introduction to the Simplex method
Optimizing by the Simplex method
Checking feasibility by the Simplex method
The Simplex method and SMT

Summary of User Reviews

Discover the power of Automated Reasoning SAT with this online course from Coursera. Students rave about the engaging lectures, practical exercises, and useful resources that help them understand the subject better. One key aspect that many users appreciated is the clear explanations of complex concepts.