Due: March 23.

- An undirected graph.
- A number K.

For instance, in graph I, { A,C,E } is a vertex cover of size 3. In graph II, { T } is a vertex cover of size 1.

An instance of the vertex cover problem can be translated into a Boolean satisfiability problem by using atoms of the form P-I, meaning that vertex P is the Ith element of set S (the order of elements in the set is arbitrary). For instance to solve the problem of finding a vertex cover for graph I, one would use the atoms A-1, A-2, A-3, B-1, B-2 ... F-1, F-2, F-3. One way to indicate the above solution to the problem would be the valuation A-2 => TRUE, C-1 => TRUE, E-3 => TRUE, and the remaining atoms are false.

Describe the propositional constraints that would be needed to express the vertex cover problem, and for each category of constraints give two examples from the encoding of Graph I.

- For each number K and for each pair of vertices U != V, assert that U and V are not both the Kth element. Examples: ~(A-1 ^ V-1). ~(C-2 ^ F-2).
- For each pair of numbers J != K and vertex U, assert that U is not both the Jth and Kth element. Examples: ~(A-1 ^ A-2). ~(D-2 ^ D-3). (This is actually optional; if it is omitted, the satisfaction algorithm may find covers with repeated elements.)
- For each edge U-V, assert that either U-I or V-J holds for some value
of I and J. Examples:

A-1 V A-2 V A-3 V B-1 V B-2 V B-3.

D-1 V D-2 V D-3 V E-1 V E-2 V E-3.

Describe how any instance of the edge cover problem can be encoded in the propositional calculus. As in problem 1, specify what the atoms are; describe the constraints; and illustrate each category of constraints with two examples from graph I.

** Propositions: **

- For each pair of edges U-V, W-X and each number I, assert that U-V and W-X are not both the Ith element. E.g. ~(A-B-1 ^ B-C-1). ~(A-C-3 ^ E-F^3).
- For each edge U-V and pairs of numbers I,J, assert that U-V is not both the Ith and Jth element. E.g. ~(A-B-1 ^ A-B-2). ~(D-E-1 ^ D-E-2). (Again this is optional, as in problem 1).
- For each vertex U, assert that that one of the edges ending at U is
in the set S at some index I. E.g.

For vertex A: A-B-1 V A-B-2 V A-B-3 V A-C-1 V A-C-2 V A-C-3 V A-F-1 V A-F-2 V A-F-3

For vertex D: C-D-1 V C-D-2 V C-D-3 V D-E-1 V D-E-2 V D-E-3

W(P,S) -- Person P works for store S.Express the following sentences in L.

C(P,S) -- Person P is a customer at store S.

B(P1,P2) -- Person P1 is a boss of person P2.

M(P1,P2) --- Person P1 is married to P2.

D(P,S) --- Person P is entitled to a discount at store S.

A, T, K, G --- Andy, Tara, K-Mart, Gristedes.

- A. Andy works at both K-Mart and Gristedes.

**Answer:**W(A,K) ^ W(A,G). - B. All of Tara's subordinates are married.

**Answer:**forall(p1) B(T,p1) => exists(p2) M(p1,p2). - C. Any employee of a store and their spouse are entitled a discount at
that store. (Note: employees get their discount whether or not they are
married).

**Answer:**forall(p1,p2,s) W(p1,s) => [D(p1,s) ^ [M(p1,p2) => D(p2,s)]]. - D. Tara is Andy's boss.

**Answer:**B(T,A). - E. There is no married couple both of whom work at Gristedes.

**Answer:**~ exists(p1,p2) M(p1,p2) ^ W(p1,G) ^ W(p2,G). - F. There exists someone who does not work at Gristedes but is nonetheless
entitled to a discount at Gristedes.

**Answer:**exists(p) ~W(p,G) ^ D(p,G). - G. There exists a store that only employs married couples (that is, the
store employs a person P only if P is married and P's spouse is likewise
an employee.)

**Answer:**exists(s) forall(p1) W(p1,s) => exists(p2) W(p2,s) ^ M(p1,p2).