propositional satisfiability
(45 minutes to learn)
Summary
Propositional satisfiability (SAT) is a computational problem where one is given a setence in propositional logic, and one wants to determine if there is a satisfying assignment (an assignment of truth values to all the variables which makes the assignment true). SAT is central to computer science because it is the prototypical NP-complete problem and because SAT solvers underly a lot of automated reasoning systems.
Context
This concept has the prerequisites:
Goals
- define the propositional satisfiability (SAT) problem
- give a brute force algorithm in terms of truth tables
- show that it suffices to consider inputs in conjunctive normal form
- show how one can use satisfiability to prove a conclusion from a set of premises
Core resources (read/watch one of the following)
-Free-
→ Coursera: Introduction to Logic (2014)
An introductory logic course geared towards computer scientists.
Location:
Lecture "Propositional satisfiability"
Other notes:
- Click on "Preview" to see the videos.
See also
-No Additional Notes-