For example, given the input [1, 4, 6, 14, 17, 20] the output could be {1, 4, 6, 20}, {14, 17}, since both partitions add up to 31. Given the input [3, 4, 6, 14, 17, 20] the output would be "FALSE" since no such partition exists. Consider the following solution to this problem using state space search: Let M = the sum of the elements in L.

- A
*state*is a triple < L1,U1,V1 > where L1 is a list; U1 and V1 are sets; and L1, U1, and V1 are a partition of L (that is, each element of L is in exactly one of L1, U1, and V1. - The operations on < L1,U1,V1 > are defined as follows: Delete the head of L1 and either add it to U1 or add it to V1, as long the sum of the elements in the new set is no more than M/2.
- The start state is < L, {}, {} >
- A goal state is one in which L1 is the empty list.

- A. Show the portion of the state space generated in a depth-first
search for the problem L=[1, 2, 3, 4]. Note that M=10.
(Note: To save writing, just label each state with the values of U1 and V1;
you can omit L1.)
[][] --- [1][] --- [1,2][] --- [1,2][3] fail | |- [1][2] --- [1,3][2] fail | |- [1][2,3] --- [1,4][2,3] succeed.

- B. Suppose that the list L has size 50. What is the branching factor?
What is the maximum depth
of the tree? Give an upper bound on the maximum size of the tree.
**Answer:**Branching factor: 2. Depth: 50. The size is certainly no more than 2^{50}(one can construct problems where the state space has size 2^{49}, so that's a pretty tight estimate.)

(P <=> Q) => R.

[(P => Q) ^ (Q => P)] => R ~[(~P V Q) ^ (~Q V P)] V R [(P ^ ~Q) V (Q ^ ~P)] V R.Finally, one attains four clauses

1. P V ~P V R 2. P V ~Q V R 3 Q V ~P V R 4. Q V ~Q V R.But clauses (1) and (4) are tautologies (true for all valuations, since they have a literal and its negation) and therefore can be dropped.

1. ~P V Q V RStep 1: ~A is a pure literal. Set A=FALSE. Delete 7 and 8.

2. P V ~Q

3. P V ~R

4. ~P V ~Q V S

5. ~Q V R V ~S

6. ~R V ~S

7. ~A V P.

8. ~A V R.

Set S1:

1. ~P V Q V RStep 2: No singleton clauses, no pure literals. Try P=TRUE. Delete clauses 2 and 3, delete ~P from 1 and 4.

2. P V ~Q

3. P V ~R

4. ~P V ~Q V S

5. ~Q V R V ~S

6. ~R V ~S

Set S2:

1. Q V RStep 3: No singleton clauses, no pure literals. Try Q=TRUE. Delete clause 1, delete ~Q from 4 and 5.

4. ~Q V S

5. ~Q V R V ~S

6. ~R V ~S

Set S3:

4. SStep 4: 4 is a singleton clause. Set S=TRUE. Delete clause 4, delete ~S from 5 and 6.

5. R V ~S

6. ~R V ~S

5. RStep 5: 5 is a singleton clause. Set R=TRUE. Delete clause 5, delete ~R from clause 6.

6. ~R

Step 6: 6 is now the empty clause. Fail. Go back to step 3, set S2. Try Q=FALSE. Delete clauses 4, 5. Delete Q from 1.

Set S4.

1. RStep 7: 1 is a singleton clause set R=TRUE. Delete clause 1. Delete ~R from 6.

6. ~R V ~S

6. ~S.Step 8: 6 is a singleton clause. Set S=FALSE. Delete 6.

There are now no clauses left, so succeed. Return the current valuation: A=FALSE, P=TRUE, Q=FALSE, R=TRUE, S=FALSE.

The INDEPENDENT SET problem is, given a graph G and an integer K, find an independent set in G of size K.

An instance of the INDEPENDENT SET problem can be translated into propositional satisfiability as follows: For each vertex V and for each integer I=1 .. K, define the atom V_I to be the assertion that V is the Ith vertex, alphabetically, in the set Z. Define the atom V_in to be the assertion that V is in the set Z. One then needs the following four types of constraints:

- V is in Z if and only if V is the Ith vertex in Z for some value of I.
- For I > 1, if V is the Ith vertex in Z then one of the vertices alphabetically before V is the (I-1)st vertex in Z. (If V is the first vertex alphabetically in G, then this amounts to the statement that V is not the second or third or fourth ... or Kth vertex in Z.)
- If U and V are connected in G then U and V are not both in Z.
- Some vertex is the Kth vertex in Z.

** Answer: **

1. A_in <=> A_1 V A_2 V A_3.

2. C_2 => A_1 V B_1

3. ~(A_in ^ D_in).

4. A_2 V B_2 V C_2 V D_2 V E_2 V F_2 V G_2 V H_2

(There are many possible answers.)

p(X,Y) --- Predicate. X is part of Y.

b(X,Y) --- Predicate. X borders Y.

ci(X) --- Predicate. X is a city.

co(X) --- Predicate. X is a country.

ll(X) --- Predicate. X is landlocked

s(X) --- Predicate. X is a sea.

paris, portugal, europe --- Constants.

Express the following sentences in L:

A. Every city is part of some country

** Answer: ** forall(X) ci(X) => exists(Y) co(Y) ^ p(X,Y).

B. No city is part of any sea.

** Answer: ** ~[exists(X,Y) ci(X) ^ s(Y) ^ p(X,Y).]

C. A region is landlocked if and only if it does not border any sea.

** Answer: **
forall(X) ll(X) <=> ~(exists(Y) s(Y) ^ b(X,Y)).

D. There exists a country that contains every city that borders Paris.

** Answer: **
exists(X) co(X) ^ [forall(Y) ci(Y) ^ b(Y,paris) => p(Y,X)].

E. There is at least one landlocked country in Europe.

** Answer: **
exists(X) co(X) ^ ll(X) ^ p(X,europe).

F. Portugal does not border any landlocked countries.

** Answer: **
~[exists(X) ll(X) ^ co(X) ^ b(portugal,X)]