UPI Study › Courses › Introduction to Artificial Intelligence › Free lessons › Lesson 6.5 Free with a free account
Algorithms for Propositional Reasoning
Introduction to Artificial Intelligence · Chapter 6: Logic, Reasoning, and Knowledge SystemsSection 6.5 · lesson 43 of 6914 min · free with a free account
Free preview
Create a free account to keep watching
It takes a minute and costs nothing. Your free account unlocks all of Chapter 1 and 3 more lessons of Introduction to Artificial Intelligence.
Lesson complete
Earn the 3 college credits for Introduction to Artificial Intelligence
Enrolling adds a quiz after each lesson, the graded work and the official transcript. Recommended for credit by NCCRS.
Next lesson: Resolution-Based Inference in Logical Systems →← Expressing Knowledge Through First-Order LogicNext lesson: Resolution-Based Inference in Logical Systems →
In this lesson
How model checking, DPLL and WalkSAT decide satisfiability and entailment.
- Restate entailment as an unsatisfiability question for a SAT solver
- Trace DPLL using early termination, pure symbols and unit propagation
- Explain how WalkSAT searches and why it is incomplete
- Describe the NP-completeness of SAT and the phase transition in random 3-SAT
Free study notes
Get this lesson's notes by email
The key points and 4 practice questions with answers, in your inbox. One email, free.
One email. Unsubscribe in one click.
Transcript
Everything said in the video, section by section (1,949 words). Read along, or search it.
Opening Question
Too Many Worlds to List
A knowledge base with a hundred symbols has more possible worlds than any computer could ever list. Each symbol can be true or false, and every extra symbol doubles the count: about one point three million trillion trillion worlds. No computer could check them one by one. So how can a program still decide what follows from such a knowledge base? The answer is a family of search algorithms, and they're among the most widely used reasoning tools in computing.
Model Checking
Listing Every Model to Test Entailment
Start with the direct method. A knowledge base entails a sentence, when that sentence is true in every model where the knowledge base is true. Model checking follows the definition. List every model, keep those where the knowledge base holds, and check the sentence in each one. Take this knowledge base: A or B, and, not A or C. Does it entail B or C? Three symbols give eight models. Each row is one model. The middle columns work out A or B, and not A or C, and the knowledge base is true only when both of them are. Reading down the KB column, the knowledge base is true in four of them: rows one, three, five, and six. And B or C is true in all four. So the answer is yes. B or C is false only in rows four and eight, and the knowledge base is false there anyway.
Satisfiability
Entailment as Unsatisfiability
A sentence is satisfiable if at least one model makes it true, and unsatisfiable if none does. That gives a neat way to restate entailment. The knowledge base entails S exactly when, the knowledge base AND not S, is unsatisfiable. Why? A model of the knowledge base that made S false would satisfy that combination. It would be a counterexample. This is proof by contradiction, as an algorithm. In our example, add not B and not C. Then A true fails, not A or C, and A false fails, A or B. No model survives, so the entailment holds. The same trick turns other reasoning questions into satisfiability questions. Is the knowledge base consistent? Check that it's satisfiable. Is S valid, true in every model? Check that not S is unsatisfiable. So one tool, a SAT solver, answers all three.
Cost
Two to the N Models
Model checking is simple, and it's always right. The trouble is size. With n symbols there are two to the n models, so each new symbol doubles the work. Picture a computer checking a billion models every second. Ten symbols take about a millionth of a second, twenty about a thousandth, and thirty about one second. Fifty symbols take about thirteen days. And a hundred take about forty trillion years. Real knowledge bases can have thousands of symbols. So smarter algorithms are essential.
Quick Check
C Alone Is Not Entailed
Quick check. Keep the same knowledge base: A or B, and, not A or C. Does it entail C on its own? Test it as satisfiability: add not C, and look for a model that survives. Is it entailed, because nothing survives? Or not, with A false and B true surviving? Or not, with A true and B false surviving? Pause, and decide. Not entailed. Adding not C makes, not A or C, force A false. Then A or B forces B true. A false, B true, C false satisfies everything, so it's a counterexample: the knowledge base allows C to be false. The third option fails, because with A true and C false, the clause not A or C is false. And no survivor would have meant entailment, as it did for B or C.
Conjunctive Normal Form
Clauses Built from Literals
Smarter solvers work on conjunctive normal form, or CNF: an AND of clauses. Each clause is an OR of literals, and a literal is a symbol or its negation. For example, A or not B, and, B or C, has two clauses. A clause is true when at least one of its literals is true, and a CNF sentence is true when every clause is. Any sentence can be rewritten this way, and we'll assume that's done.
DPLL Algorithm
Early Termination, Pure Symbols, Unit Propagation
The DPLL algorithm, named for Davis, Putnam, Logemann, and Loveland, searches assignments one symbol at a time, depth first. Several shortcuts make it fast. Early termination: stop as soon as a clause is already false, because later choices can't repair it. Or stop when every clause is true. Pure symbols: a symbol that appears with only one sign, in the remaining clauses, is set to make those literals true. It can only satisfy clauses, never falsify one. Unit propagation: when a clause has just one unassigned literal and no true one, that literal is forced true. Any other choice would make the clause false. When no shortcut applies, DPLL picks a symbol, tries true, and if that fails, tries false. It fails only if both do.
Worked Trace
Branching on A True Hits a Conflict
Watch it work on this sentence: six clauses over five symbols, A through E. First, E appears only as E, so it's pure. Set E true, and the second clause is satisfied. No other shortcut applies, so DPLL branches. Try A true. The first clause is satisfied, and the others shrink. Not A or C shrinks to C alone, a unit clause, so C is true. Then D or not C shrinks to D, so D is true. Now not B or not D becomes not B, so B must be false. But B or not D has both literals false. Conflict: backtrack.
Worked Trace
A False Leads to Success
Back up, and try A false. The first clause shrinks to D alone, and every clause containing not A is satisfied. What's left is D, and, B or not D. B now appears only as B, so it's pure: B is true. And the unit clause D makes D true. Every clause is true: success. A false, B true, D true, E true, and C can take either value. Only one real choice was needed, the branch on A. The conflict wiped out the whole A true half at once, and forced moves did the rest. A full truth table could have examined up to thirty-two rows.
Modern Solvers
Clause Learning and Smarter Branching
Modern SAT solvers are refinements of DPLL. They add clause learning, which remembers why a conflict happened, so the same dead end isn't explored again. They choose which symbol to branch on more cleverly, and they restart at random. In practice they handle problems with millions of symbols, such as checking the designs of computer chips.
Quick Check
Forced Moves Leave No Branching
Quick check. Run DPLL on a new sentence: P, and, not P or Q, and, not Q or R. What value does R get, and how many times must DPLL branch? R true, with no branching? R true, after one branch? Or R false, after backtracking? Pause, and decide. R is true, with no branching at all. P alone is a unit clause, so P is true. Then not P or Q shrinks to Q, so Q is true. And not Q or R shrinks to R, so R is true. Every step was forced, so DPLL never had to choose. It branches only when no shortcut applies, and here one always did.
Local Search
WalkSAT Repairs a Random Assignment
DPLL builds an assignment piece by piece. Local search, which you met in chapter four, does the opposite: start with a complete random assignment, and repair it. The score is the number of unsatisfied clauses, and the goal is zero. Each move flips one symbol. Purely greedy flipping tends to get stuck, so WalkSAT mixes in random moves. Start with random values. If every clause is true, stop. Otherwise, pick a random unsatisfied clause. With probability p, often about one half, flip a random symbol from that clause. Otherwise, flip the symbol in it that leaves the fewest unsatisfied clauses. Repeat until a flip limit, then give up. Flipping inside an unsatisfied clause is the only way to repair it, and random moves help escape spots where every flip looks worse. Here's one possible run on the six-clause sentence from before. Start with A, B, C, and E true, and D false. One clause is unsatisfied: not A or D or not C. A random move flips C. Now not A or C is the one unsatisfied clause. Greedy move: flipping A or C would each leave one unsatisfied clause. It's a tie, so flip A. Now A or D is unsatisfied. Greedy move: flip D, and zero clauses are unsatisfied. Solved. Another run would look different, because the choices are random. WalkSAT is often fast on big problems that have solutions. But it has an important limit: it's incomplete. If it stops without a solution, that proves nothing. The sentence may still be satisfiable, and WalkSAT can never show that a sentence is unsatisfiable. Compare the three methods. Truth tables always answer, and can prove unsatisfiability, but cost two to the n models. They suit tiny problems. DPLL also always answers, and can prove unsatisfiability, though its worst case is still exponential. Use it when you need a guaranteed answer. WalkSAT may give up, and it can't prove unsatisfiability. It suits large problems that probably have a solution.
Quick Check
Proving Door-Access Rules Safe
Quick check. A company must show that thousands of door-access rules can never let an unauthorized person in. It writes, the rules allow an unauthorized entry, as one big sentence, and hands it to a solver. Which result proves the rules safe? WalkSAT finds no solution? DPLL finds no solution? Or WalkSAT finds a solution? Pause, and decide. DPLL finding no solution. DPLL is complete, so no solution means the sentence is unsatisfiable: no assignment lets an unauthorized person in. WalkSAT finding nothing proves nothing. It may simply have run out of flips. And WalkSAT finding a solution shows the rules are unsafe, the opposite of what we hoped.
Complexity
NP-Complete, 2-SAT and Horn Clauses
Why is there no perfect method? SAT was the first problem proved NP-complete, by Stephen Cook, in nineteen seventy-one. A proposed solution is easy to check: just evaluate every clause. But no known algorithm finds solutions quickly for every sentence. Every known complete method takes exponential time in the worst case, and finding a fast one would settle one of the biggest open questions in computer science. Since entailment means the knowledge base AND not S is unsatisfiable, deciding entailment is the complementary problem, called co-NP-complete. Hardness starts early: with three literals per clause, three-SAT is still NP-complete. With at most two, two-SAT takes polynomial time. And Horn clauses take linear time, the basis of rule chaining. And the worst case isn't the typical case. Real problems often have structure that solvers exploit.
Phase Transition
Hard Instances Near a Ratio of 4.26
What makes some instances hard? Researchers study random three-SAT: m clauses over n symbols, each clause built from three random symbols with random signs. The key quantity is the ratio, m over n, clauses per symbol. With few clauses per symbol, almost every sentence is satisfiable, and solutions are found quickly. With many clauses per symbol, almost none are satisfiable, but conflicts appear early, so DPLL closes branches fast. In between, satisfiability drops sharply, from almost always to almost never, like water freezing. That's why it's called a phase transition, and the hardest instances cluster there. For large n, the switch happens near a ratio of about four point two six. So a problem's difficulty depends on how tightly it's constrained, not just on its size.
Key Takeaways
Model Checking, DPLL and WalkSAT
To sum up. The knowledge base entails S exactly when, the knowledge base AND not S, is unsatisfiable, so one SAT solver answers many questions. Truth tables are complete, but they need two to the n models. DPLL searches depth first, with early termination, pure symbols, and unit propagation. WalkSAT repairs a random assignment. It's fast, but its failure proves nothing. And SAT is NP-complete, with the hardest random instances near a ratio of four point two six.
About Introduction to Artificial Intelligence at UPI Study
Introduction to Artificial Intelligence (Computer Science 373) is a self-paced online course of 69 video lessons in 9 chapters, from intelligent agents and search to game strategy, neural networks, logic and reasoning, machine learning, language, robotics and AI ethics. It carries a NCCRS credit recommendation for 3 semester credits.
Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Enroll now → Course details Download the syllabus All Computer Science courses Every course with PRO →
Compare: AI vs Current Trends in CS and IT
Why take it here
Why students take Introduction to Artificial Intelligence with UPI Study
Where the credit goes
Universities that work with NCCRS
Introduction to Artificial Intelligence carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
Thomas Edison State UniversitySigned partner
University of the PeopleSigned partner
Charter Oak State CollegeSigned partner
Strayer UniversitySigned partner
Columbia Southern UniversitySigned partner
Indiana TechSigned partner
Penn StateWorks with NCCRS
Southern New Hampshire UniversityWorks with NCCRS
SUNYWorks with NCCRS
+many more cooperating universitiesFind my college →Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.
FAQ
Questions students ask us
About Algorithms for Propositional Reasoning
What is the DPLL algorithm?
What is unit propagation in SAT solving?
Why can't WalkSAT prove that a sentence is unsatisfiable?
What is the phase transition in random 3-SAT?
About the Introduction to Artificial Intelligence course
How many college credits is Introduction to Artificial Intelligence?
How much does Introduction to Artificial Intelligence cost and what is included?
Which universities accept UPI Study credits?
How long does Introduction to Artificial Intelligence take?
How are the exams done?
How do my credits reach my college?
Ready for the full course? Earn 3 credits in Introduction to Artificial Intelligence.
69 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.
3 credits · NCCRSEnroll →