As we will see, it turns out that this yields a condition that is both necessary and sufficient for merging states. Formally, if :((,) (,) ), then , are equivalent and can be merged. We begin by formalizing the notion of equivalent states. Define the relation ~ over as follows: ~ :A(,) (,)B Prove that ~ is an equivalence relation (i.e., it is reflexive, symmetric, and transitive).

As we will see, it turns out that this yields a condition that is both necessary and sufficient for merging states. Formally, if Vx *: (4(p, x) EF AA(q,x) e F), then p, q are equivalent and can be merged. We begin by formalizing the notion of equivalent states. Part 4. (3 points) Define the relation ~ over Q as follows: p~q def Vx *: (4(p, x) E F = 4(q,x)) e F Prove that - is an equivalence relation (i.e., it is reflexive, symmetric, and transitive)