The simple INDEPENDENT SET problem is the special case of the BEST INDEPENDENT SET problem where all the vertices have value 1. In other words: You are given an undirected graph G and a number K. The task is to find a set S of vertices of size K such that no two vertices are connected by an edge. For instance, in the graph below, {A,C,H,J} is an independent set of size 4 . An INDEPENDENT SET problem can be translated into propositional calculus as follows: Use atoms of the form v/ meaning that v is the Ith element in some listing of the set. For instance for the above example, there would be 40 atoms A1, A2, A3, A4, B1, B2 ... J4. One valuation corresponding to the ordering {H,A,C,J} would have H1,A2,C3,J4 assigned TRUE, and the other 36 atoms assigned FALSE. Describe the categories of propositions needed to encode an INDEPENDENT SET' problem as problem in propositional calculus. Illustrate each category with a particular proposition for the above example. Please note: For each category there are two separate things. First, there is a description of the category. That should be applicable to the INDEPENDENT SET problem on any graph, not just to the one above. It should not make reference to any features that are specific to the example above. Second, there is an example of one rule from this category as it would apply to the above example. The rules in programming assignment 2 are a good example of the kind of answer I am looking for here. ALSO NOTE: VERY IMPORTANT Your encoding absolutely should NOT reference the solution to the problem. If you propose that one of the sentences should be A C2H3J4 or anything like that, that's completely wrong. Your answer should be a set of clauses that can be input to a SAT solver such as Davis-Putnam so that it can find the solution