2-SAT
Converting logic constraints into implication graphs. Using SCCs to determine satisfiability and construct valid assignments.
Lessons
1. Intro
(Logic meets graphs)
2. What is SAT
(Boolean satisfiability)
3. The 2-SAT Restriction
(Exactly two variables)
4. Variables and Negations
(True or false)
5. Implication Graphs
(Clauses become edges)
6. Converting OR to Implication
(The core transformation)
7. Why This Works
(Logic equivalence)
8. Example Conversion
(Building the graph)
9. Quiz: Implication Graph Construction
Knowledge check
10. The SCC Connection
(Satisfiability condition)
11. Why Same SCC Fails
(Contradiction proof)
12. Finding an Assignment
(Using SCC order)
13. Why Topological Order Works
Avoiding forced contradictions
14. Algorithm Summary
(Four steps)
15. Complexity Analysis
(Linear time)
16. Quiz: Satisfiability Check
Knowledge check
17. Problem - Giant Pizza
(Read statement)
18. Modeling as 2-SAT
(Toppings as variables)
19. Building the Implication Graph
(Converting constraints)
20. Checking Satisfiability
(SCC test)
21. Constructing the Assignment
(SCC topological order)
22. Giant Pizza - Implementation
(C++ solution)
23. Edge Case - All Positive
(Simplest satisfiability)
24. Edge Case - Contradiction
(Same topping opposite signs)
25. Lessons from Giant Pizza
(Recognition and modeling)
26. Quiz: Assignment Construction
Knowledge check
27. Constraint Pattern - At Most One
(Mutual exclusion)
28. Constraint Pattern - Exactly One
(One must be true)
29. Constraint Pattern - If-Then
(Implication directly)
30. Multiple Clauses on Same Variables
(Combining constraints)
31. Quiz: Clause Conversion
Knowledge check
32. Problem - Course Scheduling
(Time slot assignment)
33. Modeling Scheduling
(Binary time slots)
34. Scheduling Solution
(SCC assignment)
35. Lessons from Scheduling
(Binary choices)
36. When to Use 2-SAT
(Problem recognition)
37. Extensions Beyond 2-SAT
(Harder problems)
38. Common Mistakes
(Avoiding pitfalls)
39. Debugging 2-SAT Solutions
(Finding errors)
40. Quiz: Debugging 2-SAT
Knowledge check
41. Vocabulary - Clause
(OR of literals)
42. Vocabulary - Literal
(Variable or negation)
43. Vocabulary - Satisfiable
(Valid assignment exists)
44. Vocabulary - Implication
(If-then statement)
45. Practice Problem 1
(CSES - Giant Pizza)
46. Practice Problem 2
(Graph coloring variant)
47. Practice Problem 3
(Time slot assignment)
48. Visualization Tip
(Drawing the graph)
49. Connection to Other Topics
(Graph algorithms unite)
50. Quiz: Recognizing 2-SAT
Knowledge check
51. Section Recap
(What you learned)