ECE 4524 – PROJECT 5 – SPRING 2022
Boolean Satisfiability (SAT)
Overview. For this assignment, you are no longer concerned with Pacman and ghosts. Instead, you must write a Python program that determines Boolean satisfiability (SAT) for propositional logic sentences. Section 7.6 of the textbook discusses the SAT problem briefly, and provides a description of an algorithm known as DPLL. Your program should be able to read a text-based description of a propositional logic sentence, conduct a search for a satisfying model using the DPLL algorithm, and then report the result. As a second part of this assignment, you should test your program using randomly generated propositional logic sentences.
This project is worth 25 points. As described in a Canvas announcement last January, you have the option to earn 5 more points as extra credit. The extra-credit part is not required.
Copyright By PowCoder代写 加微信 powcoder
Academic integrity. This assignment must be completed independently. Please review the Honor Code statement in the syllabus. You are allowed to refer to code provided by the instructor, a Teaching Assistant, or the textbook’s web site. You should not share your code with anyone except the instructor or a TA.
Boolean satisfiability. Briefly stated, the SAT problem is to find a set of true/false assignments for a set of propositions that will cause a given propositional logic sentence to be true. For example, suppose that you have the following sentence in conjunctive normal form (CNF):
(A ∨ ¬D) ^ (B ∨ ¬D) ^ (¬A ∨ ¬B ∨ D)
Three propositions (A, B, and D) appear in this sentence, and the sentence consists of 3 clauses. For this particular example, the assignment A = 0, B = 1, D = 0 causes the entire sentence to be true. We say that the sentence is therefore satisfiable, and we refer to the assignment A = 0, B = 1, D = 0 as a satisfying model for this sentence. Several other satisfying models also exist for this particular sentence. However, if no assignment will cause the sentence to be true, then we would say that the sentence is unsatisfiable. Here is a simple example of a sentence that is unsatisfiable:
(A ∨ B ∨ C) ^ (¬A) ^ (¬B) ^ (¬C)
We will often refer to propositions as “symbols” or “variables.” As a reminder, in CNF each clause is required to be a disjunction (logical OR) of literals, and the clauses must be connected by conjunction (logical AND). A literal is either a single proposition or a negated proposition.
Your goal is to implement a SAT-solver, which is a program that searches for a satisfying model (such as A = 0, B = 1, D = 0 in the first example above) that causes a given CNF sentence to be true. For n variables, 2n different assignments are possible, so it is not feasible to try all possible cases when n becomes large. Instead, your program should implement the DPLL search algorithm that is introduced in section 7.6 of the textbook. The required I/O format for representing CNF sentences and for program output are described below. Try to write your code so that it will handle at least n = 50 propositions and several hundred clauses within a few minutes.
DPLL is essentially a recursive, depth-first enumeration of possible models, along with several heuristics that prune the search space. A nice property of DPLL is that it is complete, meaning that it is guaranteed to determine satisfiability if you have enough computational time and memory.
CNF representation. Use the DIMACS format for representing CNF sentences in text files, as described at http://people.sc.fsu.edu/~burkardt/data/cnf/cnf.html, with some minor simplifications as described below. As an example of this format, consider the following sentence:
(X1 ∨¬X4)^(X2 ∨¬X4)^(¬X1 ∨¬X2 ∨X4)^(¬X4 ∨X5)^(¬X3 ∨X5)^(X3 ∨X4 ∨¬X5) You may assume that the propositions Xi are numbered sequentially beginning at i = 1. The CNF
sentence shown above could be encoded in a text file, say testcase1.txt, as follows:
c Test case #1
All of our test cases will start with one or more comment lines, which your program can ignore. A comment line is a line of text that begins with the letter “c” as shown in the example above. After the comment lines, there will be a “problem” line, which you can assume will always start with “p cnf”. Next on the problem line is a value n, which tells your program the number of propositions in the sentence (here n = 5). The last item on the problem line is the number of clauses in the file (here it is 6).
The rest of the file will contain clauses, with one clause per line of text. Each clause will be represented as a sequence of integers that correspond to subscripts of the propositions Xi. A negative integer means that the proposition is negated, and a positive integer means that it is not negated. You may assume that all subscripts lie in the range [1, n]. You should assume that each clause can contain any number of literals from 1 up to n. (Empty clauses are not allowed.) In each clause, a particular proposition will appear at most once. A “0” will appear at the end of each line as a delimiter. Assume that every proposition (X1 to Xn) is used at least once in the sentence.
Running your program. Your top-level function should be named satsolve, and it should be invoked using the format satsolve(cnf_file.txt). Cnf_file.txt is a string that names a file containing a CNF sentence in DIMACS format. For example, satsolve(”testcase1.txt”) should cause the program to run for the example given above.
Your program should stop as soon as it has found any satisfying assignment, or when it has determined that the sentence is unsatisfiable. If the program finds an assignment, then it should print “SAT” or “Satisfiable” along with the satisfying model as a string of 1s and 0s in the order X1 X2 … Xn. For the example shown above, some of the solutions are 00000 and 00101 and 01101 and 10101 and 11011 and 11111. (Other satisfying assignments may also be possible.) If n2o solution can be found, your program should print “UNSAT” or “Not satisfiable”.
The program should also keep track of the number of recursive calls made to DPLL, and print that number as part of the output.
Another example. SAT solvers are used as core computational engines for many different applications. One important application is testing and verification of digital logic circuits. The examples shown so far were derived from simple combinational logic circuits. The following is a slightly larger example, and it is a test case taken from a popular set known as the ISCAS-85 benchmark circuits:
c ISCAS-85 benchmark circuit c17 p cnf 13 22
-6 -1 -3 0 730 740
-7 -3 -4 0 870 820
-8 -7 -2 0 970 950
-9 -7 -5 0 10 8 0
-10 -8 -6 0
-11 -8 -9 0
This CNF file will be provided to you as c17.txt. It corresponds to the following logic diagram:
Testing with randomly generated sentences. Write a separate high-level function to collect data so that you can create a graph for similar the one in Figure 1. (You only need to produce a graph for DPLL. You are not required to implement WalkSAT, unless you decide to do the extra-credit work as described below.) Your function should generate CNF sentences at random, and should invoke your DPLL code to determine satisfiability for each sentence. To conform to the graph below, each random sentence should contain n = 50 variables, and each clause of the sentence should contain k = 3 literals. Your program generates random sentences that contain m clauses, for different values of m.
Figure 1. Graph of the median run time (measured in number of recursive calls to DPLL, a good proxy) on random 3-CNF sentences. (In a 3-CNF sentence, each clause contains at most 3 literals.) The most difficult problems have a clause/symbol ratio of about 4.3. (Figure source: Chapter 7 of Russell & Norvig.)
The graph shows time (measured as a count of recursive calls to DPLL) vs. m/n. When m is small, most sentences are satisfiable, and DPLL should find a satisfying model quickly. When m is large, most sentences are unsatisfiable, and DPLL should reach that conclusion rather quickly also. Near m/n = 4.3, however, considerably more search may be needed reach a decision.
Code modularity and testing. Subdivide your code into Python source files as appropriate. A suggested set of files would be satsolve.py, containing your high-level method(s); your code for parsing input from files in fileparser.py; the actual SAT-solver in dpll.py; and your test code in sattest.py. (If you do extra-credit work, you might also add a file named extracredit.py to contain your WalkSAT code.)
The file names shown above are optional, except that one of your files must be named satsolve.py, and it should contain your top-level function named satsolve. Provide all of the files that the grader needs to run your program, with appropriate import statements so that only satsolve.py needs to be loaded manually by the grader in order to run the program.
The grader will test your program by running commands similar to the following in a Python 3 environment:
load satsolve.py 4 satsolve(“testcase1.txt”)
Your program should not request input from the command line. The grader will also run your code using test cases that are not provided to you.
Report. Create a short written report to describe your work. Use file name report.pdf. Near the beginning, state how well your program has satisfied the specification. If there are some parts that you did not implement, provide some guidance to the grader as to how partial credit could be decided. In a separate paragraph or two, briefly describe any parts of the assignment that were especially easy or difficult. What additional test cases did you try? How many variables and clauses can your program handle?
Finally, provide a graph that is similar to Figure 1. Briefly describe any problems that you encountered, or any interesting insights that you gained from this part of the project assignment.
Extra credit opportunity (optional). In addition to DPLL, you may also implement a second search technique that is based on local search methods. (Recall our discussion of local search for Constraint Satisfaction Problems.) Local search means that your code makes a full assignment to all variables, and then changes one variable at a time as it searches for a solution. The search is sometimes called a “walk” through the search space. In one version of an algorithm known as WalkSAT, on every iteration the algorithm picks an unsatisfied clause and then picks a symbol in the clause to flip. The symbol that is flipped may be chosen randomly.
If you decide to do extra-credit work, submit a second short report in a file named extracredit.pdf in addition to report.pdf. In this second report, provide an explanation of your approach to local search. Describe any problems that you encountered. Also include a plot similar to Figure 1 that shows a comparison of performance between your implementation of DPLL and your local-search technique.
Programming style. Your code should be neat and easy for the grader to read. Near the top of every source file that you submit, place a comment block listing the following information: “ECE 4524 Project 5”, your name, date, and a brief description of the file’s contents. Every class and every nontrivial function that you create should contain a useful comment block. Occasionally provide additional comments in line with the code, to explain interesting parts of the program. A lengthier discussion of Python style is provided at python.org/dev/peps/pep-0008.
Submitting your work. Place all of your files into a single zip file, including your written report(s). A suggested name for the zip file is p5_username.zip, using your own username. Submit that file to Canvas before the deadline. After uploading, please verify correct submission by downloading your zip file from Canvas and checking the contents. (The files that you submit to Canvas are the files that will be graded.)
Grading. The following breakdown will be used for grading this project: 15 correct DPLL program operation
5 program design (readability, indentation, modularity, interfaces, comments, etc.)
5 contents of written report 25 TOTAL
5 extra-credit opportunity (optional) 5
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com