Algorithm for assigning items to one of two sets (2-CNF?)
There's a simpler approach, without using 2CNF.  Instead, build an undirected graph with edges between pairs of items that must be together, then find connected components (e.g., using DFS).  Now you can freely choose, for each component, which set it is associated with, and add all of its elements to that set; the result will be valid regardless of how you make those free choices.