We may earn an affiliate commission when you visit our partners.
Course image
Hans Zantema

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

Read more

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 flavour of the applications: fitting rectangles to be applied for printing posters, scheduling problems, solving puzzles, and program correctness. Also, the 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 inequalities.

The lightweight approach to following the Automated Reasoning: satisfiability course is just watching the lectures and doing 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.

Enroll now

What's inside

Syllabus

SAT/SMT basics, SAT examples
This module introduces SAT (satisfiability) and SMT (SAT modulo theories) from scratch, and gives a number of examples of how to apply SAT.
Read more
SMT applications
This module shows a number of applications of satisfiability modulo the theory of linear inequalities (SMT)
Theory and algorithms for CNF-based SAT
This module describes how a rule called Resolution serves to determine whether a propositional formula in conjunctive normal form (CNF) is unsatisfiable. It is shown how an approach called DPLL does the same job, and how it is related to resolution. Finally, it is shown how current SAT solvers essentially implement and optimize DPLL.
Theory and algorithms for SAT/SMT
This module consists of two parts. The first part is about transforming arbitrary propositional formulas to CNF, leading to the Tseitin transformation doing this job such that the size of the transformed formula is linear in the size of the original formula. The second part is about extending SAT to SMT, in particular to dealing with linear inequalities. It is shown how the Simplex method for linear optimization serves for this job; the Simplex method itself is explained in detail.

Good to know

Know what's good
, what to watch for
, and possible dealbreakers
Focuses on using SAT tools to solve various problems, which is highly applicable in industry and research
Taught by Hans Zantema, who is recognized for their work in automated reasoning
Provides a theoretical foundation for SAT and SMT, which is valuable for understanding the principles behind these tools
Requires students to apply SAT/SMT to real-world problems, which promotes practical skills
Assumes prior knowledge of propositional logic, which may be a barrier for some students

Save this course

Save Automated Reasoning: satisfiability to your list so you can find it easily later:
Save

Reviews summary

Satisfiability concepts applied

Learners say this introductory course covers satisfiability well and is suitable for those coming into the topic with no background knowledge. Important concepts like the Z3 theorem prover and honorary assignments are emphasized. While some assignments were felt to be unclear, the majority of students said the practical applications and examples led to a strong understanding.
Features helpful Z3 theorem prover.
"The highlight of the course (and my main takeaway) is the theorem prover z3 from Microsoft."
"I would have liked to see some examples explicitely coded."
Useful practical applications.
"This course can deploy in real life."
"The course is a great introduction to satisfiability problem and its wide range of applications in day to day life."
"Honors assignments really helped me understand the core concepts better."
Provides helpful concepts.
"Excellent Course. Concise and to the point. Well chosen examples. I had no background in the topic, but it is quite math-heavy. I am okay with it. "
"This was a great introductory course for satisfiability."
"The course is a great introduction to satisfiability problem and its wide range of applications in day to day life."
Some unclear assignments.
"The only downsido is that the questions on some quizzes are not very clear. Like how do you cont the number of steps required to end a DPLL prove etc."

Activities

Be better prepared before your course. Deepen your understanding during and after it. Supplement your coursework and achieve mastery of the topics covered in Automated Reasoning: satisfiability with these activities:
Review Linear Algebra Basics
Some of the advanced topics in this course make use of linear algebra, so reviewing the basics will help you succeed.
Browse courses on Linear Algebra
Show steps
  • Review your notes from a previous linear algebra course
  • Find some online resources on linear algebra
  • Do some practice problems
Review basics of propositional logic
Propositional logic is the foundation for SAT/SMT. Understand it better to master SAT/SMT.
Browse courses on Propositional Logic
Show steps
  • Go over course notes of an existing course on logic, if available.
  • Complete practice problems related to propositional logic.
SAT/SMT Tutorial Series
Following a tutorial series on SAT/SMT will give you a solid foundation in the basics of the subject.
Browse courses on SAT
Show steps
  • Find a SAT/SMT tutorial series online
  • Follow the tutorials and complete the exercises
Six other activities
Expand to see all activities and additional details
Show all nine activities
Review SAT/SMT Theory
SAT and SMT are based on propositional logic, so reading this book will strengthen your foundation for the course.
Show steps
  • Read Chapter 1: Propositional Logic
  • Do the exercises in Chapter 1
  • Read Chapter 2: Boolean Algebra
  • Do the exercises in Chapter 2
  • Read Chapter 3: Resolution
SAT/SMT Puzzle Practice
Solving SAT/SMT puzzles will help you develop your problem-solving skills and your understanding of the underlying concepts.
Browse courses on SAT
Show steps
  • Find some SAT/SMT puzzles online
  • Try to solve the puzzles by yourself
  • Check your solutions against the provided answers
Mentor a Junior Student
Mentoring a junior student will help you reinforce your understanding of the material and develop your leadership skills.
Show steps
  • Find a junior student who is interested in learning about SAT/SMT
  • Meet with the student regularly to discuss the material
  • Help the student with their homework and projects
  • Provide the student with encouragement and support
SAT/SMT Poster Presentation
Creating a poster presentation on SAT/SMT will help you synthesize your knowledge of the topic and improve your communication skills.
Show steps
  • Choose a topic related to SAT/SMT
  • Research your topic
  • Create a poster that explains your topic clearly and concisely
  • Present your poster to your classmates
SAT/SMT Competition
Participating in a SAT/SMT competition will test your skills and help you learn from others.
Browse courses on SAT
Show steps
  • Find a SAT/SMT competition online
  • Register for the competition
  • Practice for the competition
  • Compete in the competition
Contribute to an Open-Source SAT/SMT Solver
Contributing to an open-source SAT/SMT solver will give you hands-on experience with the technology and help you learn from others.
Browse courses on SAT
Show steps
  • Find an open-source SAT/SMT solver online
  • Read the documentation for the solver
  • Make a small contribution to the solver
  • Submit a pull request to the solver's repository

Career center

Learners who complete Automated Reasoning: satisfiability will develop knowledge and skills that may be useful to these careers:
Artificial Intelligence Engineer
A course in Automated Reasoning: satisfiability can provide individuals seeking a career as an Artificial Intelligence Engineer with a strong foundation in the fundamentals of AI. This course offers an overview of SAT/SMT basics, SAT and SMT applications, theory and algorithms for CNF-based SAT, theory and algorithms for SAT/SMT, and the simplex method for dealing with linear inequalities. This knowledge will be essential for developing AI systems that can solve complex problems.
Business Analyst
Those seeking a career as a Business Analyst may find that taking a course in Automated Reasoning: satisfiability can be helpful. This course offers an overview of SAT/SMT basics, SMT applications, theory and algorithms for CNF-based SAT, theory and algorithms for SAT/SMT, and the simplex method for dealing with linear inequalities. As a Business Analyst, you will often be tasked with finding ways to improve business processes and systems. The knowledge you gain in this course will help you to develop the skills necessary to do so.
Consultant
A course in Automated Reasoning: satisfiability can be useful for individuals looking to work as a Consultant. This is because the course provides an overview of SAT and SMT basics, SAT examples, SMT applications, theory and algorithms for CNF-based SAT, theory and algorithms for SAT/SMT, and the simplex method for dealing with linear inequalities. This knowledge can be applied to a range of consulting projects, such as helping businesses to improve their operations or develop new products.
Quantitative Analyst
For those interested in pursuing a career as a Quantitative Analyst, taking a course in Automated Reasoning: satisfiability may be beneficial. This course not only covers the basics of SAT/SMT and SMT applications, it also focuses on theory and algorithms for CNF-based SAT, theory and algorithms for SAT/SMT, and the simplex method for dealing with linear inequalities. As a Quant Analyst, you will need to be able to use mathematical and statistical techniques to solve complex problems, and this course will provide you with the tools to do so.
Actuary
Individuals seeking a career as an Actuary may find that taking a course in Automated Reasoning: satisfiability can be useful. This course offers an overview of SAT/SMT basics, SAT examples, SMT applications, theory and algorithms for CNF-based SAT, theory and algorithms for SAT/SMT, and the simplex method for dealing with linear inequalities. As an Actuary, you will be responsible for assessing and managing financial risks, and the knowledge you gain in this course will be invaluable in helping you to do so.
Systems Analyst
For those interested in pursuing a career as a Systems Analyst, taking a course in Automated Reasoning: satisfiability can be useful. This course provides an overview of SAT/SMT basics, SAT examples, SMT applications, theory and algorithms for CNF-based SAT, theory and algorithms for SAT/SMT, and the simplex method for dealing with linear inequalities. A Systems Analyst is responsible for designing and implementing computer systems, and the knowledge you gain in this course will provide you with a solid foundation for this.
Software Architect
Individuals interested in working as a Software Architect may find a course in Automated Reasoning: satisfiability useful. This course offers an overview of SAT/SMT basics, SMT applications, theory and algorithms for CNF-based SAT, theory and algorithms for SAT/SMT, and the simplex method for dealing with linear inequalities. As a Software Architect, you will be responsible for designing and developing software systems. The knowledge you gain in this course will help you to develop the skills necessary to do so.
Database Administrator
For those seeking a career as a Database Administrator, taking a course in Automated Reasoning: satisfiability can be useful. This course offers an overview of SAT/SMT basics, SMT applications, theory and algorithms for CNF-based SAT, theory and algorithms for SAT/SMT, and the simplex method for dealing with linear inequalities. As a Database Administrator, you will be responsible for the maintenance and performance of databases. The knowledge you gain in this course will help you to develop the skills necessary to do so.
Risk Analyst
A course in Automated Reasoning: satisfiability may be beneficial for individuals interested in working as a Risk Analyst. With this course you will get an overview of SAT and SMT basics, including SAT examples. You will also learn about SMT applications, theory and algorithms for CNF-based SAT, theory and algorithms for SAT/SMT, and the simplex method for dealing with linear inequalities. This knowledge can be applied to a range of risk management tasks, such as identifying and assessing risks, and developing mitigation strategies.
Product Manager
Individuals interested in a career as a Product Manager may find taking a course in Automated Reasoning: satisfiability beneficial. This course covers SAT/SMT basics, SMT applications, theory and algorithms for CNF-based SAT, theory and algorithms for SAT/SMT, and the simplex method for dealing with linear inequalities. As a Product Manager, you will be responsible for developing and launching new products. The knowledge you gain in this course will help you to develop the skills necessary to do so.
Operations Research Analyst
Those working as Operations Research Analysts may find value in taking a course in Automated Reasoning: satisfiability. As this course not only provides an overview of SAT/SMT basics and SMT applications, but it also gives you the opportunity to learn about theory and algorithms for CNF-based SAT, theory and algorithms for SAT/SMT. As an Operations Research Analyst, you will often be tasked with finding optimal solutions to complex problems. Taking this course will help you to develop the skills necessary to do so.
Software Engineer
While not strictly required to work as a Software Engineer, a course in Automated Reasoning: satisfiability may be useful as this course goes over theory and algorithms for CNF-based SAT, theory and algorithms for SAT/SMT, and of course SAT/SMT basics. This course also dives into SAT and SMT applications. With this course under your belt, you will be able to apply satisfiability (SAT/SMT) tools to solve a wide range of problems. Additionally, it can help you build a strong understanding of propositional satisfiability, linear inequalities, and the Simplex method for linear optimization.
Computer Programmer
A course in Automated Reasoning: satisfiability can be a valuable asset for those pursuing a career as a Computer Programmer. This course offers an overview of SAT/SMT basics and SMT applications, as well as the simplex method for dealing with linear inequalities. You will also learn about theory and algorithms for CNF-based SAT, and theory and algorithms for SAT/SMT. The skills you gain in this course will be directly applicable to your work as a Computer Programmer, as you will often be tasked with writing code that solves complex problems.
Information Security Analyst
For individuals interested in a career as an Information Security Analyst, taking a course in Automated Reasoning: satisfiability may be useful. With this course you will receive an overview of SAT/SMT basics and SMT applications, as well as theory and algorithms for CNF-based SAT, theory and algorithms for SAT/SMT, and the simplex method for dealing with linear inequalities. This knowledge can be applied to solving a range of problems related to information security, such as detecting and preventing cyberattacks.
Data Scientist
Individuals seeking to work as Data Scientists may find that taking a course in Automated Reasoning: satisfiability is useful. This course provides an overview of SAT/SMT basics, and SAT examples. You will also learn about the simplex method for dealing with linear inequalities, theory and algorithms for CNF-based SAT, and theory and algorithms for SAT/SMT. This knowledge can help you to better understand how to apply satisfiability (SAT/SMT) tools to solve a range of problems.

Reading list

We've selected ten books that we think will supplement your learning. Use these to develop background knowledge, enrich your coursework, and gain a deeper understanding of the topics covered in Automated Reasoning: satisfiability.
Demonstrates how to use satisfiability (SAT) solvers to solve a variety of computer science problems, including constraint solving and planning.
This textbook provides a foundation in logic design, including topics such as propositional logic, predicate logic, and digital circuits.
This textbook provides a comprehensive overview of algorithms and data structures, including sections on satisfiability and constraint satisfaction.
This classic work provides a foundation in set theory and mathematical logic, including topics such as propositional logic and predicate logic.
This textbook provides a foundation in logic for computer scientists, including topics such as propositional logic and predicate logic.
This textbook provides a foundation in logic, including topics such as propositional logic and predicate logic.
This textbook provides a foundation in logic and philosophy, including topics such as propositional logic and predicate logic.

Share

Help others find this course page by sharing it with your friends and followers:
Our mission

OpenCourser helps millions of learners each year. People visit us to learn workspace skills, ace their exams, and nurture their curiosity.

Our extensive catalog contains over 50,000 courses and twice as many books. Browse by search, by topic, or even by career interests. We'll match you to the right resources quickly.

Find this site helpful? Tell a friend about us.

Affiliate disclosure

We're supported by our community of learners. When you purchase or subscribe to courses and programs or purchase books, we may earn a commission from our partners.

Your purchases help us maintain our catalog and keep our servers humming without ads.

Thank you for supporting OpenCourser.

© 2016 - 2024 OpenCourser